Solutions A. Choose Two Numbers 題意：\(A,B\) 兩個集合，\(A,B\) 集合分別選一個數\(a,b\) ，使得\(a+b\notin\ A,B\)
//#define DEBUG
#include<bits/stdc++.h>
using namespace std;
#define lson (rt<<1)
#define rson (rt<<1|1)
const int N=100010;
const int inf=0X3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
typedef long long ll;int a[110];
int main() {#ifdef DEBUGfreopen("in.txt","r",stdin);#endifint n,m,ans1,ans2;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);ans1=*max_element(a+1,a+n+1);scanf("%d",&m);for(int i=1;i<=m;i++) scanf("%d",&a[i]);ans2=*max_element(a+1,a+m+1);printf("%d %d\n",ans1,ans2);
}
B. Make Product Equal One 題意：\(a_1,a_2,\dots,a_n\) ，可以進行任意次操作：選擇其中任意一個數\(+1,-1\) ，使得最后\(a_1{\ast}a_2{\ast}\dots{\ast}a_n=1\) 。\(-1\) ，整數就變為\(1\) ，但是若負數個數為奇數，則需要有一個變為\(1\) ，但是存在\(0\) 的話，則不需要。
//#define DEBUG
#include<bits/stdc++.h>
using namespace std;
#define lson (rt<<1)
#define rson (rt<<1|1)
const int N=100010;
const int inf=0X3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
typedef long long ll;int main() {#ifdef DEBUGfreopen("in.txt","r",stdin);#endifint n;scanf("%d",&n);ll ans=0,ok=0,res=1;for(int i=1;i<=n;i++) {int x;scanf("%d",&x);if(x>=1) ans+=x-1;else if(x<0) ans+=-1-x,res*=-1;else if(!x) ans+=1,ok=1;}if(ok||res==1) printf("%lld\n",ans);else printf("%lld\n",ans+2);
}
C. Almost Equal 題意：\(n\) ，你需要安排的數為\(1\sim2n\) ，組成一個環。每連續\(n\) 個數求一次和\(sum_i\) ,輸出一個合法的序列，使得\({\forall}i,j,\ {\mid}sum_i-sum_j{\mid}{\leq}1\) \(check\) 代碼，構造時發現分為兩部分，右邊最上面寫一個最大的，左邊最下面寫次大的，然后左邊再寫次次大的，右邊再寫次次次大的，交替進行。可以理解為右邊為先手，然后左邊變為先手。構造完以后，用數組模擬成環，然后前綴和搞一搞模擬\(check\) 即可。\(s_i=a_i+a_{i+1}+a_{i+2}+{\dots}+a_{i+n-1}\) ，\(S_{i+1}-S_{i}=\left(a_{i+1}+a_{i+2}+a_{i+3}+\cdots+a_{i+n}\right)-\left(a_{i}+a_{i+1}+a_{i+2}+\cdots+a_{i+n-1}\right)=a_{i+n}-a_{i}\) 根據題意有\({\mid}a_{i+n}-a_i{\mid}{\leq}1\) ，因為\(a\) 數組都是不同的，所以\({\mid}a_{i+n}-a_i{\mid}=1\) \(a_{i+n}-a_i,a_{i+n+1}-a_{i+1}\) 有相反的符號。 證：若他們都等于\(1\) ，則\(S_{i+2}-S_i=(S_{i+2}-S_{i+1})+(S_{i+1}-S_{i})=(a_{i+n+1}-a_{i+1})+(a_{i+n}-a_i)=2\) ，若都為\(-1\) 也一樣。因此，對于\(a_{i+n}-a_i\) ，他們是交替的\(1,-1,1,\dots\) 。
如果\(n\) 為偶數，存在矛盾\(a_{i+n}-a_i=-(a_{(i+n)+n}-a_{i+n})\) ，但是由于交替，所以他們應該是相等的 如果\(n\) 為奇數，\(i:1{\sim}n\) 若\(i\) 為奇數，\(a_i=2i,a_{i+n}=2i-1\) 若\(i\) 為偶數，\(a_i=2i-1,a_{i+n}=2i\) //#define DEBUG
#include<bits/stdc++.h>
using namespace std;
#define lson (rt<<1)
#define rson (rt<<1|1)
const int N=100010;
const int inf=0X3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
typedef long long ll;int a[N],b[N],c[4*N];
ll ans[4*N];
int main() {#ifdef DEBUGfreopen("in.txt","r",stdin);#endifint n;scanf("%d",&n);bool flag=true;int cura=0,curb=0;int x=2*n;while(x) {if(flag) {b[++curb]=x--;a[++cura]=x--;} else {a[++cura]=x--;b[++curb]=x--;}flag=!flag;}int cur=0;for(int i=cura;i>=1;i--) c[++cur]=a[i];for(int i=curb;i>=1;i--) c[++cur]=b[i];int len=cur;for(int i=1;i<=len;i++) c[++cur]=c[i];//for(int i=1;i<=cur;i++) printf("%d\n",c[i]);set<ll> s;for(int i=1;i<=n;i++)ans[i]=ans[i-1]+c[i];s.insert(ans[n]);for(int i=n+1;i<=3*n;i++){ans[i]=ans[i-1]-c[i-n]+c[i];s.insert(ans[i]);}if(s.size()>2)puts("NO");else if(s.size()==2){set<ll>::iterator it=s.begin();ll s1,s2;s1=*it;it++;s2=*it;if(abs(s1-s2)!=1)puts("NO");else {puts("YES");for(int i=1;i<=2*n;i++)printf("%d%c",c[i],i==2*n?'\n':' ');}}else {puts("YES");for(int i=1;i<=2*n;i++)printf("%d%c",c[i],i==2*n?'\n':' ');}
}
//#define DEBUG
#include<bits/stdc++.h>
using namespace std;
#define lson (rt<<1)
#define rson (rt<<1|1)
const int N=100010;
const int inf=0X3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
typedef long long ll;int a[2*N];
int main() {#ifdef DEBUGfreopen("in.txt","r",stdin);#endifint n;scanf("%d",&n);if(n%2==0) {puts("NO");return 0;}puts("YES");for(int i=1;i<=n;i++) {if(i&1) a[i]=2*i,a[i+n]=2*i-1;else a[i]=2*i-1,a[i+n]=2*i;}for(int i=1;i<=2*n;i++) printf("%d%c",a[i],i==2*n?'\n':' ');
}
D. Shortest Cycle 題意：\(a_1,a_2,{\dots},a_n\) ，當作圖中的\(n\) 個點，對于\({\forall}i,j(i{\neq}j),a_i\&a_j{\neq}0\) ，\(a_i\) 和\(a_j\) 連一條邊，然后求最小環。\(60\) 個位置畫出來了。我也準備好\(floyd\) 最小環了。但是沙雕了，感覺每個位置都連邊，復雜度太大emmmmmm。其實二進制對應位置\(1\) 的個數大于\(2\) ，那么最小環就是\(3\) ，然后最多\(120\) 個點\(60\) 條邊（可能不確切），然后\(floyd\) 跑最小環即可。\(floyd\) 求最小環：\(d[i][j]\) 為\(i\) 到\(j\) 不包含\(k\) 點的最短距離。所以對于當前\(k\) ，我們已經求得\(1{\sim}k-1\) 的\(d[i][j]\) ，然后枚舉\(1{\sim}k-1\) 的\(d[i][j]\) ，然后更新答案，\(ans=min(ans,a[i][k]+a[k][j]+d[i][j])\) ，表示包含\(k\) 的環，其中\(a\) 數組為最初距離。
//#define DEBUG
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
const int inf=0X3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
typedef long long ll;int ans=60;
ll b[N],a[150][150],d[150][150];
int tot;int main() {#ifdef DEBUGfreopen("in.txt","r",stdin);#endifint n;scanf("%d",&n);ll x;for(int i=1;i<=n;i++) {scanf("%lld",&x);if(x) b[++tot]=x;}for(int i=0;i<=60;i++) {int cnt=0;for(int j=1;j<=tot;j++) {if(b[j]&(1ll<<i)) ++cnt;}if(cnt>=3) {puts("3");return 0;}}for(int i=1;i<=tot;i++) {for(int j=1;j<=tot;j++)if(i==j) d[i][j]=a[i][j]=0;else d[i][j]=a[i][j]=inf;}for(int i=1;i<=tot;i++) {for(int j=1;j<=tot;j++) {if(i==j) continue;if(b[i]&b[j]) a[i][j]=d[i][j]=1;}}//memcpy(d,a,sizeof(a));for(int k=1;k<=tot;k++) {for(int i=1;i<=k-1;i++) {for(int j=1;j<=k-1;j++)if(i!=j&&a[i][k]+a[k][j]+d[i][j]<ans)ans=a[i][k]+a[k][j]+d[i][j];}for(int i=1;i<=tot;i++) {for(int j=1;j<=tot;j++)if(d[i][j]>d[i][k]+d[k][j])d[i][j]=d[i][k]+d[k][j];}}if(ans==60) puts("-1");else printf("%d\n",ans);
}
轉載于:https://www.cnblogs.com/ACMerszl/p/11396093.html
總結
以上是生活随笔 為你收集整理的Codeforces Round #580 (Div. 2) 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
