发现自己构造太菜了
于是决定上cf按tag找题来做
不定期更新
是CF上2000-2500的构造题
CF1506F
题意太长不翻译了(
把原图路径画一画,大概是一堆这样的东西
构造路径的时候,按照斜线分组
如果两个点在同一组的话,那么看它是奇数还是偶数
奇数的话要把所有的路径变向,否则消耗为0
如果不在同一组,那么产生的消耗就是跨越组的消耗。
#include <bits/stdc++.h> using namespace std; struct Node{ int r,c,d; }a[200005]; int temp(Node a,Node b){ return a.r<b.r; }; int ans=0; int main(){ int T; scanf("%d",&T); while(T--){ int N; ans=0; scanf("%d",&N); a[0].r=1,a[0].c=1,a[0].d=0; for (int i=1;i<=N;i++) scanf("%d",&a[i].r); for (int i=1;i<=N;i++) scanf("%d",&a[i].c); sort(a+1,a+N+1,temp); for (int i=1;i<=N;i++) a[i].d=a[i].r-a[i].c; for (int i=1;i<=N;i++){ if (a[i].d==a[i-1].d){ if (!(a[i].d%2)) ans+=a[i].c-a[i-1].c; } else{ if (a[i-1].d%2){ ans+=(a[i].d-a[i-1].d+1)/2; } else ans+=(a[i].d-a[i-1].d)/2; } } printf("%d\n",ans); } return 0; }
CF925C
题意:
给你一堆数字,排列这些数字,让他们前缀异或和递增
sol:
考虑当前获得了异或和$sum$
那么,对下一个数字的情况做分类讨论
情况1:下一个数字位数比自己高
那么肯定比这个大
情况2:
下一个数字和这个数字的最高位一样,都是$1$
那么显然是变小的
情况3:
下一个数字和$sum$在最高位不同,且$sum$在某个位置上是$0$
那么,其实我们找到一个最高位是这个位置的数字,把它放上去就好了,新的数字肯定比这个数字大
那么我们就得到了一个做法
枚举$N$个位置,记录当前的$sum$,每次从低位到高位考虑,找到一个$0$,找最高位为这个位置的数字,有就塞,没有就继续找就行了。
#include <bits/stdc++.h> using namespace std; int N; long long a[100005]; vector<long long> anss; queue<long long >bit[65]; int main(){ scanf("%d",&N); for (int i=1;i<=N;i++){ scanf("%lld",&a[i]); for (int j=60;j>=0;j--) if ((a[i]>>j)&1ll) { bit[j].push(a[i]); break; } } sort(a+1,a+N+1); long long ans=0; for (int i=1;i<=N;i++){ bool flag=false; for (int j=0;j<=60;j++){ if (!((ans>>j)&1ll)&&!(bit[j].empty())) { long long x=bit[j].front(); bit[j].pop(); ans^=x; flag=true; anss.push_back(x); break; } } if (!flag) { printf("No\n"); return 0; } } printf("Yes\n"); for (auto x:anss){ printf("%lld ",x); } return 0; }