Codeforces Global Round 3 A. Another One Bites The Dust 有若干個a，有若干個b，有若干個ab。你現在要把這些串拼成一個串，使得任意兩個相鄰的位置都是不同字符，求可能的最長串長度。
枚舉一下\(a\) 開頭還是\(b\) 開頭，那么接下來就被唯一確定了。
#include<iostream>
#include<cstdio>
using namespace std;
int a,b,c;long long ans;
int main()
{scanf("%d%d%d",&a,&b,&c);ans=0ll+c*2+min(a,b+1)+min(a,b);if(b)--b,ans=max(ans,1ll+c*2+min(a,b+1)+min(a,b));printf("%lld\n",ans);return 0;
}
B. Born This Way 有\(n\) 個航班從\(A\) 前往\(B\) ，起飛時間分別是\(a_1,a_2,...,a_n\) ，飛行時間都是\(t_a\) 。有\(m\) 個航班從\(B\) 前往\(C\) ，起飛時間分別是\(b_1,b_2,...,b_m\) ，飛行時間是\(t_b\) 。現在有一個人要從\(A\) 到\(C\) ，你可以取消不超過\(k\) 個航班，使得這個人到達\(C\) 的時間最晚。\(-1\) 。
顯然這個人越早到達\(B\) 越好，所以我們取消掉的一定是\(a\) 的一段前綴。而到達\(B\) 之后一定會坐上最早出發的航班，所以同理刪去到達之后的一段連續的航班。\(a\) 刪掉的前綴長度就行了。\(n\le k,m\le k\) 的情況
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 200200
inline int read()
{int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x;
}
int n,m,ta,tb,k,ans;
int a[MAX],b[MAX];
int main()
{n=read();m=read();ta=read();tb=read();k=read();for(int i=1;i<=n;++i)a[i]=read();for(int i=1;i<=m;++i)b[i]=read();if(n<=k||m<=k){puts("-1");return 0;}for(int i=0,p=1;i<=n&&i<=k;++i){while(p<=m&&b[p]<a[i+1]+ta)++p;if(m-p+1+i<=k){puts("-1");return 0;}ans=max(ans,b[p+k-i]+tb);}printf("%d\n",ans);return 0;
}
C. Crazy Diamond 你有一個長度為\(n\) 的一個排列\(p\) ，其中\(n\) 是一個偶數。\(2|i-j|\ge n\) 。\(5n\) 的交換方式。
考慮順次把每個數歸位的過程。\(i\) 個數在位置\(p\) 。\(p,i\) 兩個位置可以直接交換，那么就直接交換。\(p,i\) 都可以和\(1\) 交換，那么通過\(1\) 進行交換就行。\(p,i\) 都可以和\(n\) 交換，那么通過\(n\) 進行交換就行。\(p\) 可以和\(1\) ，\(i\) 可以和\(n\) 交換，那么通過\((p,1),(i,n),(1,n),(p,1),(i,n)\) 這樣\(5\) 次操作就可以交換。\(5n\) 次。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define MAX 300300
inline int read()
{int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x;
}
int n,p[MAX],b[MAX];
bool chk(int i,int j){return 2*abs(i-j)>=n;}
vector<pair<int,int> > Ans;
void add(int i,int j){if(i==j)return;swap(p[i],p[j]);b[p[i]]=i;b[p[j]]=j;Ans.push_back(make_pair(i,j));}
int main()
{n=read();for(int i=1;i<=n;++i)b[p[i]=read()]=i;for(int i=1;i<=n;++i){if(i==b[i])continue;if(chk(b[i],i))add(i,b[i]);else{int p=b[i];if(chk(1,p)&&chk(1,i))add(1,p),add(1,i),add(1,p);else if(chk(n,i)&&chk(p,n))add(n,i),add(p,n),add(n,i);else if(chk(1,p)&&chk(i,n))add(1,p),add(i,n),add(1,n),add(1,p),add(i,n);}}printf("%d\n",(int)Ans.size());for(auto p:Ans)printf("%d %d\n",p.first,p.second);return 0;
}
D. Dirty Deeds Done Dirt Cheap 給定兩個長度為\(n\) 的數列\(a,b\) ，保證所有數都在\([1,2n]\) 中且各不相同。\([1,n]\) 的數，使他們構成一個數列\(\{i\}\) ，滿足數列：\(a_{i1}b_{i1}a_{i2}b_{i2}...a_{im}b_{im}\) 是一個波動序列。
首先數列有兩種形式，第一種是\(<><><>\) 這樣子，第二種是\(><><><\) 在這樣子。\((a_i,b_i)\) 組內的大小關系，可以把二元組分成兩類，兩類只能分別構造答案。\(b_i<a_j\) 或者\(b_i>a_j\) 。\(b_i<a_j\) 的情況?？紤]把所有數按照\(a_i\) 排序，這樣子每個二元組的出邊就是一個后綴，那么我們只需要貪心的把邊連到\(b\) 最小的上面去就行了，這樣子拿線段樹就可以維護了，或者進一步，發現\(b\) 是單增的，所以用堆之類的東西維護就行了。\(b\) 是單增的，所以我們直接按照\(b\) 排序，此時發現按照排序之后的結果就是合法的。\(a_{i}>b_{i}<b_{i+1},a_{i+1}>b_{i+1}\) ，\(a_{i}>b_{i}<a_{i+1}>b_{i+1}\) 。\(b_i>a_j\) 按照\(a\) 排序就行了。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 300300
inline int read()
{int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x;
}
int n,r,a[MAX],b[MAX],p[MAX];
bool cmpb(int x,int y){return b[x]<b[y];}
bool cmpa(int x,int y){return a[x]<a[y];}
int main()
{n=read();for(int i=1;i<=n;++i)a[i]=read(),b[i]=read(),r+=a[i]>b[i],p[i]=i;printf("%d\n",max(r,n-r));if(r>n-r){sort(&p[1],&p[n+1],cmpb);for(int i=1;i<=n;++i)if(a[p[i]]>b[p[i]])printf("%d ",p[i]);}else{sort(&p[1],&p[n+1],cmpa);for(int i=n;i;--i)if(a[p[i]]<b[p[i]])printf("%d ",p[i]);}puts("");return 0;
}
E. Earth Wind and Fire 數軸上有\(n\) 個石頭，一開始時第\(i\) 個石頭在位置\(s_i\) ，每次你可以選擇兩個石頭\(i,j\) ，滿足\(s_i<s_j\) ，然后選擇一個\(d\) ，滿足\(2d\le |s_i-s_j|\) ，然后把\(i\) 移動到\(s_i+d\) 位置，\(j\) 移動到\(s_j-d\) 位置。\(n\) 的數列\(t\) ，表示最終在\(t_i\) 位置要有一個石頭。
不難發現如果合法我們一定可以不改變相對順序。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAX 300300
#define mp make_pair
inline int read()
{int x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x;
}
int n,t[MAX],f;
pair<int,int> s[MAX],Q[MAX];
vector<pair<pair<int,int>,int> >Ans;
void add(int i,int j,int d)
{i=s[i].second,j=s[j].second;Ans.push_back(mp(mp(i,j),d));
}
int main()
{n=read();for(int i=1;i<=n;++i)s[i]=make_pair(read(),i);for(int i=1;i<=n;++i)t[i]=read();sort(&t[1],&t[n+1]);sort(&s[1],&s[n+1]);for(int i=1;i<=n;++i)if(s[i].first<t[i])Q[++f]=mp(i,t[i]-s[i].first);else{if(s[i].first==t[i])continue;int p=s[i].first-t[i];while(p&&f){int mv=min(p,Q[f].second);add(Q[f].first,i,mv);p-=mv;Q[f].second-=mv;if(!Q[f].second)--f;}if(p){puts("NO");return 0;}}if(f){puts("NO");return 0;}puts("YES");printf("%d\n",(int)Ans.size());for(auto p:Ans)printf("%d %d %d\n",p.first.first,p.first.second,p.second);return 0;
}
F. Foo Fighters 你有\(n\) 個物品，每個物品有兩個權值\(val\) 和\(mask\) 。\(s\) ，然后修改所有數的\(val\) ，如果\(val\& mask\) 有奇數個\(1\) 就把\(val\) 變成\(-val\) 。\(s\) ，使得權值和符號變反。
顯然可以把所有位分開考慮，如果選擇了這一位并且這一位的\(mask\) 上有\(1\) 就可以直接取反。
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
#define MAX 300300
inline ll read()
{ll x=0;bool t=false;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=true,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return t?-x:x;
}
int n,v[MAX];
ll a[MAX],s,sum;
int main()
{n=read();for(int i=1;i<=n;++i)v[i]=read(),a[i]=read(),sum+=v[i];if(sum<0)for(int i=1;i<=n;++i)v[i]=-v[i];for(int i=62;~i;--i){ll ss=0;for(int j=1;j<=n;++j)if(a[j]==(1ll<<i))ss+=v[j];if(ss>0)s|=1ll<<i;for(int j=1;j<=n;++j)if(a[j]&(1ll<<i)){a[j]^=1ll<<i;if(ss>0)v[j]=-v[j];}}printf("%lld\n",s);return 0;
}
G. Gold Experience 有\(n\) 個點，每個點有一個點權\(a_i\) ，如果兩個點權的\(gcd>1\) ，那么他們之間就會連上一條邊。\(k\) 的點集，滿足其中所有點都是好的或者所有點都是不好的。
咕咕咕咕
H. Holy Diver 咕咕咕
轉載于:https://www.cnblogs.com/cjyyb/p/10984063.html
總結
以上是生活随笔 為你收集整理的Codeforces Global Round 3 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
