本文主要是介绍Codeforces Round #707 (Div. 2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
比赛传送门：
Codeforces Round #707 (Div. 2）
A. Alexey and Train
思路：
按题意模拟即可
AC Code
#include<bits/stdc++.h>
using namespace std;
int a[105],b[105],t[105];
int main()
{int d;scanf("%d",&d);while(d--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);for(int i=1;i<=n;i++) scanf("%d",&t[i]);int res=0;for(int i=1;i<=n;i++){res=res+a[i]-b[i-1]+t[i];if(i==n) break;int f=(b[i]-a[i])/2;if((b[i]-a[i])%2) f++;res=res+f;if(res<b[i]) res=b[i];}printf("%d\n",res);}//system("pause");return 0;
}
B. Napoleon Cake
题目大意：
给你n层，第 i 层上面有 a i层奶油，奶油会向下渗透，多余的会浪费掉。问最后有每一层是否有奶油。
AC Code
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],f[N];
int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=0;i<=n+1;i++) f[i]=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]>0){int st=i-a[i]+1;st=max(st,1);f[st]++;f[i+1]--;}}for(int i=1;i<=n;i++){f[i]=f[i-1]+f[i];if(f[i]>=1) printf("1 ");else printf("0 ");}printf("\n");}//system("pause");return 0;
}
C. Going Home
题目大意：
给你一个整数序列，问你能不能找到下标不同的4个数使得 ax+ay=az+aw
思路：
我在正向考虑了很久之后一直都想不到一个合适的时间复杂度的思路。于是我移项了一下ax-az=aw-ay。也就是两对数的差相等。那么最坏的情况下就是没有两对数的差相等，那么排序之后相邻两数的差也都不相等，于是我们可以构造出一个
1 2 4 7 11 16 22……的序列
那么按照题目的数据范围这个序列的长度最多也就3e3左右。那么意味着什么呢，当n>3e3时，我们排序之后，相邻的两个数做差，必然有两对相邻的数的差是相等的。当n<3e3时，我们两个循环暴力找即可。还有一些需要注意的细节见代码。
AC Code
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=5e6+10;
pair<int,int>a[N];
map<int,int>mp;
int x[M],y[M];
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i].first);a[i].second=i;}sort(a+1,a+1+n);if(n<=3e3){for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){int p=a[i].first+a[j].first;mp[p]++;if(mp[p]==1){x[p]=a[i].second;y[p]=a[j].second;}else{if(x[p]!=a[i].second&&x[p]!=a[j].second&&y[p]!=a[i].second&&y[p]!=a[j].second){printf("YES\n");printf("%d %d %d %d\n",x[p],y[p],a[i].second,a[j].second);//system("pause");return 0;}}}}} else{for(int i=n;i>1;i--){int d;d=a[i].first-a[i-1].first;mp[d]++;if(mp[d]==1) x[d]=i;else {if(i+1!=x[d]){printf("YES\n");printf("%d %d %d %d\n",a[i-1].second,a[x[d]].second,a[i].second,a[x[d]-1].second);//system("pause");return 0;}}}}printf("NO\n");//system("pause");return 0;
}
侥幸上了波大分，快乐了，哈哈哈哈
这篇关于Codeforces Round #707 (Div. 2）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
