Codeforces Round 886 (Div. 4) （D~H）---Day10
前言
差点AK...最后一题无向图建成有向图了，看了一小时没看出来
D.Balanced Round
题意：给定长度为n数组a和一个数字k，可以对数组任意排序，需要拿出若干个数字使得，求拿出数字的最小值。
思路：贪心思想，先对数组进行从小到大排序，这样能够尽可能的满足题意，同时保留的数字尽可能的多。根据题目可得，最终整个数组会分成若干个组，其中每个组内的数都满足条件，组之间的数不满足条件。最终只保留一个组，求这个组数量的最大值即可。
void solve()
{int n , k;cin>>n>>k;int a[n];for(int i = 0 ; i < n ; i++)cin>>a[i];sort(a,a+n,cmp);vectorans;int cnt = 1;for(int i = 1 ; i < n ; i ++){if(a[i] - a[i - 1] >k){ans.pb(cnt);cnt = 1;}else{cnt ++;}}ans.pb(cnt);int maxx = -1;for(int i = 0 ; i < ans.size() ; i ++){maxx = max(maxx,ans[i]);}cout< E - Cardboard for Pictures
题意：给定一个长度为n的数组a和一个目标数字c，求中的k值。
思路：二分找答案。
void solve()
{LL n , c;cin>>n>>c;LL a[n];LL ans = 0;for(int i =0 ; i < n ; i ++)cin>>a[i];LL l = 0 , r = sqrt(c);while(l < r){LL sum = 0;LL mid = (l + r) >> 1;for(int i = 0 ; i < n ; i ++){sum +=(a[i] + mid * 2) * (a[i] + mid * 2);if(sum > c){break;}}if(sum > c){r = mid;}else if (sum < c){l = mid + 1;}else{ans = mid;break;}}cout<F - We Were Both Children
题意：有n只青蛙，每只青蛙从0点起跳，青蛙每次会跳ai的距离，你可以在1~n任意的一个地方放置一个抓青蛙陷阱，求能抓住青蛙的最大值。
思路：类似于埃式筛的做法，将每个青蛙所能跳到的地方都+1。
void solve()
{int n;cin>>n;int cnt[n + 5];int f[n];memset(cnt,0,sizeof cnt);for(int i = 0; i < n ; i++){cin>>f[i];}sort(f,f+n,cmp);vector p;int path = f[0] , num = 1;for(int i = 1 ; i < n ; i ++){if(f[i] != path){p.pb({path,num});path = f[i];num = 1;}else{num ++ ;}}p.pb({path,num});for(int i = 0 ; i < p.size() ; i++){for(int j = 1 ; j * p[i].x <= n ; j ++){cnt[j * p[i].x] += p[i].y;}}int ans = 0;for(int i = 1 ; i <= n ; i ++){ans = max(ans,cnt[i]);}cout< G - The Morning Star
题意：二维平面上给定n个点，若两点的x坐标相同，y相同，斜率为1，斜率为-1，则k + 1 ， 求k值。
思路：写四个排序，按照x排序，按照y排序，按照x + y 排序 ， 按照x - y 排序，然后相同的放在一组，最终每组内两两组合。
int cmp1(Node a, Node b){if(a.x != b.x)return a.x < b.x;elsereturn a.y < b.y;
}
int cmp2(Node a, Node b){if(a.y != b.y)return a.y < b.y;elsereturn a.x < b.x;
}
int cmp3(Node a, Node b){return a.x + a.y < b.x + b.y;
}
int cmp4(Node a, Node b){return (a.x - a.y) < (b.x - b.y);
}
void solve()
{int n;cin>>n;Node a[n];LL ans = 0;for(int i = 0 ; i < n ; i++){cin>>a[i].x>>a[i].y;}sort(a , a + n , cmp1);LL cnt = 1 , tx = a[0].x;for(int i = 1 ; i < n ; i ++){if(a[i].x != tx){ans += cnt*(cnt - 1);tx = a[i].x;cnt = 1;}else{cnt++;}}ans += cnt * (cnt - 1);sort(a , a + n , cmp2);cnt = 1;int ty = a[0].y;for(int i = 1 ; i < n ; i ++){if(a[i].y != ty){ans += cnt*(cnt - 1);ty = a[i].y;cnt = 1;}else{cnt++;}} ans += cnt*(cnt - 1);sort(a , a + n ,cmp3);cnt = 1;int txy = a[0].x + a[0].y;for(int i = 1 ; i < n ; i ++){if(a[i].x + a[i].y != txy){ans += cnt * (cnt - 1);txy = a[i].x + a[i].y;cnt = 1;}else{cnt++;}}ans += cnt*(cnt - 1);sort(a , a + n , cmp4);cnt = 1,txy = a[0].x - a[0].y;for(int i = 1 ; i < n ; i ++){
// cout<<"txy:"<H - The Third Letter
题意：有n个士兵放在一个数轴之上，有m个约束，每个约束中包含a,b,d。表示了第b个士兵的坐标-第a个士兵的坐标 = d。求这n个士兵是否能满足这m个约束。
思路：将其抽象成n个点的建图问题，先存m个约束，然后遍历1~n，若当前点没有被建立过，则建立该点，设该点的坐标为一个初始值，同时用队列处理所有与之相关的点，若建立过程中某点的坐标已经确定了，但无法满足某个约束，则直接输出NO，若遍历完所有点之后都满足，则输出YES。
const LL INF = -1e16;
void solve()
{int n , m;cin>>n>>m;DSU dsu(n);LL pos[n + 5];bool isv[n + 5];for(int i = 0 ; i <= n ; i ++){pos[i] = INF;isv[i] = false;}vector v[n + 5];for(int i = 0 ; i < m ; i ++){int l , j , k;cin>>l>>j>>k;dsu.merge(l,j);v[l].pb({j,k});v[j].pb({l,-k});}for(int i = 1 ; i <= n ; i++){if(dsu.fa[i] == i){queueq;q.push(i);pos[i] = 0;isv[i] = true;while(!q.empty()){int t = q.front();q.pop();for(int j = 0 ; j < v[t].size() ; j ++){LL l = v[t][j].x , dis = v[t][j].y;if(pos[l] == INF){pos[l] = pos[t] + dis;}else{if((pos[t] + dis ) != pos[l]){cout<<"NO\n";return;}}if(isv[l] == false){q.push(l);isv[l] = true; }}}}else{continue;}}cout<<"YES\n";
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！