Codeforces Round #464 (Div. 2) (A,B,C,D,E,)

本文主要是介绍Codeforces Round #464 (Div. 2) (A,B,C,D,E,)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                 Codeforces Round #464 (Div. 2)

题目链接：http://codeforces.com/contest/939

A题题意：给定N个点以及它们的相互关系，问是否存在三元环。

A题题解：遍历即可，遍历每个点和他们连接的下一个点，看下一个点与第一个点是否连通即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005;
int n,m,k,a[maxn][maxn];
vector<int> Q[maxn];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>m;Q[i].push_back(m);a[i][m]=1;}int ok = 0;for(int i=1;i<=n;i++){for(int j=0;j<Q[i].size();j++){int now = Q[i][j];for(int k=0;k<Q[now].size();k++){int now2 = Q[now][k];if(a[now2][i]==1){ok=1;break;}}if(ok)break;}if(ok)break;}if(ok)cout<<"YES"<<endl;else cout<<"NO"<<endl;return 0;
}

B题题意：你有N只仓鼠，K只箱子，每个箱子可以装ai个仓鼠，每个箱子必须装满，你只能选择一种箱子使得装下的总数量最大，输出你选择的箱子和箱子个数。

B题题解：直接每个数取余比大小即可。注意longlong。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100007;
long long n,k,a[maxn];
int main()
{cin>>n>>k;for(int i=1;i<=k;i++)cin>>a[i];long long ans = 1;long long kk = 1000000000000000007;for(int i=1;i<=k;i++){long long m = n%a[i];if(kk>m){ans = i;kk=m;}}long long num = n/a[ans];cout<<ans<<" "<<num<<endl;return 0;
}

C题题意：有N个地区，每个地区时差为1小时，每个地区人数为ai，给定区间[s,f)的时间里开启考试，想让参加考试的人数最多，输出开始考试的时候，第一个地区的时间。

C题题解：原题是环，将环拆成链，其实就是求f-s区间长度的最大区间和，然后倒推当时第一个地区时间即可。坑点是有多解需要输出最小值。（FST的源头...）

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200007;
int n,s,f,a[maxn];
long long sum[maxn];
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum[i]=a[i]+sum[i-1];}cin>>s>>f;int l = f-s;for(int i=1;i<=l;i++){sum[i+n]=sum[i]+sum[n];}long long ans = 0;int k;for(int i=0;i<=n;i++){long long num = sum[i+l]-sum[i];if(num>ans){ans = num;k = i;}else if(num==ans){int nn = s-k;int mm = s-i;if(nn<=0)nn+=n;if(mm<=0)mm+=n;if(nn>mm)k=i;}}int mm = k;s-=k;if(s<=0)s+=n;cout<<s<<endl;return 0;
}

D题题意：给定两个字符串，每次可以进行设定，设定将不同的两个字符为相同，为最小的设定数，使得两字符串相同。

D题题解：直接并查集即可。不是同一父节点就union一下，记录每次的设定即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100007;
char a[maxn],b[maxn];
int n,f[maxn*2];
map<char,int> Q;
vector<string> S;
int find(int x)
{return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{cin>>n;cin>>a>>b;int num = 1;for(int i=0;i<n;i++){if(!Q.count(a[i])){Q[a[i]]=num++;}}for(int i=0;i<n;i++){if(!Q.count(b[i])){Q[b[i]]=num++;}}for(int i=1;i<num;i++){f[i]=i;}for(int i=0;i<n;i++){int p = find(Q[a[i]]);int q = find(Q[b[i]]);if(p==q)continue;else{f[p]=q;string x = "";x.push_back(a[i]);x+=" ";x+=b[i];S.push_back(x);}}cout<<S.size()<<endl;for(int i=0;i<S.size();i++){cout<<S[i]<<endl;}return 0;
}

E题题意：有N个操作，操作1为添加一个大于当前集合里的任一个数，操作2为询问最大值max(s)-mean(s)。s为当前集合的子集。

E题题解：每次添加的是大于当前集合里的数，那么平均值肯定是增大的，那就看新加入的值-平均值和原来的差值相比谁大，因为每次加入的肯定是比前面加入的会更大，所以差值是不严格递增，那么新的询问的起点不需要从0开始，从上一次的终点就可以，那么只要遍历即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 500007;
int a[maxn];
double sum[maxn],ans;
int n;
bool check(int num,int mm)
{if(a[num]<(sum[num-1]+mm)/num)return true;else return false;
}
int main()
{cin>>n;int num = 1;int now = 0;for(int i=1;i<=n;i++){int x;cin>>x;if(x==1){int y;cin>>y;a[num]=y;sum[num]=sum[num-1]+y;num++;}else{int p = a[num-1];while(now<num-1&&check(now,p))now++;if(now)ans = p - (sum[now-1]+p)/now;printf("%.12f\n",ans);}}return 0;
}

F待更。

这篇关于Codeforces Round #464 (Div. 2) (A,B,C,D,E,)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---