A.进攻
https://ac.nowcoder.com/acm/contest/8564/A
题解：将战机攻击力从小到大排列，基地也如此。由于基地可以多次摧毁，线性扫描每个战机能获得的最大贡献。
#include<bits/stdc++.h> using namespace std; const int N=1e6+100; int a[N]; int n,m; struct node { int x,y; bool operator <(const node &a)const{ if(x==a.x) return y<a.y; return x<a.x; } }b[N]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) scanf("%d",&b[i].x); for(int i=1;i<=m;i++) scanf("%d",&b[i].y); sort(a+1,a+1+n); sort(b+1,b+1+m); long long ans=0; int j=1; int res=0; for(int i=1;i<=n;i++) { while(j<m&&a[i]>b[j].x) { res=max(res,b[j].y); j++; } ans+=res; } cout<<ans<<endl; }
B.二进制
https://ac.nowcoder.com/acm/contest/8564/B
题解：二进制每一位分开看
1.如果之前为0，现在为1；如果之前为1，现在为0.则该位可以通过异或操作得到。
2.如果之前为0，现在为1；如果之前为1，现在为1.则该位可以通过或操作得到。
3.如果之前为0，现在为0；如果之前为1，现在为0.则该位可以通过并0操作得到。
4.如果之前为0，现在为0；如果之前为1，现在为1.则不用操作。
因此可以用a=0,b=(1<<20)-1,分别代表每一位之前为0，每一位之前为1.然后观察操作后的值的每一位。然后通过三个操作的值即可得到。
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int a=0,b=(1<<20)-1; for(int i=0;i<n;i++) { int x,y; scanf("%d%d",&x,&y); if(x==1)a&=y,b&=y; else if(x==2)a|=y,b|=y; else a^=y,b^=y; } int or1=0,xor1=0,and1=(1<<20)-1; for(int i=19;i>=0;i--) { if(a>>i&1)//之前为0，现在为1 { if(b>>i&1)//之前为1，现在为1 or1+=1<<i; else//之前为1，现在为0 xor1+=1<<i; } else if(!(b>>i&1)) and1-=1<<i; } cout<<"3"<<endl; printf("1 %d ",and1); printf("2 %d ",or1); printf("3 %d ",xor1); return 0; }
C.积木
https://ac.nowcoder.com/acm/contest/8564/C
题解：对n*n*n方格涂黑白色，要求每个黑色相邻的有两个黑色，每个白色相邻的有两个白色的。
要求相同颜色的只有两个相邻的，因此只能由2*2*2的方案累积而成，当n为奇数时无解。当n为偶数时，则可以由若干个2*2*2的方案累计而成。
#include<bits/stdc++.h> using namespace std; const int N=110; int a[N][N][N]; int n; int main() { cin>>n; if(n%2) { puts("-1"); return 0; } a[1][1][1]=a[1][1][2]=1; a[1][2][1]=a[1][2][2]=0; for(int k=1;k<=n;k+=2) { for(int i=1;i<=n;i+=2) { for(int j=1;j<=n;j+=2) { int f; if(j==1&&i==1) f=!a[k-1][i][j]; else if(j==1) { f=a[k][i-2][j]; } else f=!a[k][i][j-2]; a[k][i][j]=a[k+1][i][j]=f; a[k][i][j+1]=a[k+1][i][j+1]=f; a[k][i+1][j]=a[k+1][i+1][j]=!f; a[k][i+1][j+1]=a[k+1][i+1][j+1]=!f; } } } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) printf("%d ",a[k][i][j]); puts(""); } puts(""); } return 0; }
D.种树
https://ac.nowcoder.com/acm/contest/8564/D
题解：对于这样的树，最多可以取m=（n/2+1）/2次max，贪心策略：由根结点到最大叶节点处取最大值。可以采用这样的策略取得最大值：在深度小于等于采用最大值操作。
#include<bits/stdc++.h> using namespace std; const int N=5e5+100; int h[N],e[N],ne[N],w[N],idx; int tr[N]; int n,m; int dep[N]; void add(int a,int b) { ne[idx]=h[a]; e[idx]=b; h[a]=idx++; } void dfs(int u,int fa) { dep[u]=dep[fa]+1; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(j==fa)continue; dfs(j,u); } } void dfs1(int u,int fa) { int l=0,r=0; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(j==fa)continue; if(!l)l=j; else r=j; dfs1(j,u); } if(l) { if(dep[u]>m) tr[u]=min(tr[l],tr[r]); else tr[u]=max(tr[l],tr[r]); } else tr[u]=w[u]; } int main() { memset(h,-1,sizeof h); cin>>n; m=(n/2+1)/2; for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); if(a) { add(i,a); add(i,b); } } for(int i=1;i<=n;i++) scanf("%d",&w[i]); dfs(1,0); dfs1(1,0); cout<<tr[1]<<endl; return 0; }
E.考试
https://ac.nowcoder.com/acm/contest/8564/E
签到
#include<bits/stdc++.h> using namespace std; const int N=1010; int a[N]; int main() { int n,k; cin>>n>>k; for(int i=1;i<=n;i++) scanf("%d",&a[i]); int x; int ans=0; for(int i=1;i<=n;i++) { scanf("%d",&x); if(x!=a[i])ans++; } int res=n-ans; if(ans>k) res+=k; else res=n-(k-ans); cout<<min(n,res)<<endl; }
F.项链
https://ac.nowcoder.com/acm/contest/8564/F
题解：直接采用双链表模拟即可，对于翻转操作，交换每个结点的左右结点值即可。
#include<bits/stdc++.h> using namespace std; const int N=1e4+1000; int l[N],r[N]; int n,m; int main() { cin>>n>>m; r[n]=1; l[1]=n; for(int i=2;i<=n;i++) { l[i]=i-1; r[i-1]=i; } for(int i=1;i<=m;i++) { int id,x,y; scanf("%d",&id); if(id==1) { scanf("%d%d",&x,&y); r[l[x]]=r[x]; l[r[x]]=l[x]; l[r[y]]=x; r[x]=r[y]; r[y]=x; l[x]=y; } else if(id==2) { scanf("%d%d",&x,&y); r[l[x]]=r[x]; l[r[x]]=l[x]; r[l[y]]=x; l[x]=l[y]; r[x]=y; l[y]=x; } else if(id==3) { for(int i=1;i<=n;i++) swap(l[i],r[i]); } else{ int cur=1; while(r[cur]!=1) { printf("%d ",cur); cur=r[cur]; } printf("%d ",cur); } } return 0; }
G.涂色
https://ac.nowcoder.com/acm/contest/8564/G
签到
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; cout<<n+1<<endl; return 0; }
H.圆
https://ac.nowcoder.com/acm/contest/8564/H
签到
#include<bits/stdc++.h> using namespace std; int main() { int T; cin>>T; while(T--) { double x1,y1,r1,x2,y2,r2; cin>>x1>>y1>>r1>>x2>>y2>>r2; double ans=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); if((ans<=(r1+r2)&&ans>=abs(r1-r2))) puts("YES"); else puts("NO"); } return 0; }
I.修改
https://ac.nowcoder.com/acm/contest/8564/I
题解：要使数组所有数都变为0，即要使差分数组都变为0.对于一个操作[l,r,w],可使差分数组第l位变为0，因此，如果所有位置都能与第n+1位联通，那么就存在一些操作让差分数组都变成0。那么如果将每个操作[l,r,w]视为一条边，求最小生成树即为最小解。
#include<bits/stdc++.h> using namespace std; const int N=2e5+100; struct node { int u,v,w; bool operator <(const node &a)const { return w<a.w; } }a[N]; int n,m; int p[N]; int find(int x) { if(p[x]!=x)p[x]=find(p[x]); return p[x]; } int main() { cin>>n>>m; for(int i=0;i<m;i++) { scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w); } for(int i=1;i<=n;i++) p[i]=i; int cnt=0; long long ans=0; sort(a,a+m); for(int i=0;i<m;i++) { int u=a[i].u,v=a[i].v,w=a[i].w; int fa=find(u); int fb=find(v+1); if(fa!=fb) { p[fa]=p[fb]; ans+=w; cnt++; } if(cnt==n)break; } if(cnt<n)puts("-1"); else cout<<ans<<endl; return 0; }
J.克隆
https://ac.nowcoder.com/acm/contest/8564/J
题解：求出2n-1的欧拉序，对于k个分身每个分身分配（2*n+k-1）/k个序列，则一定存在解。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10,M=4e5+10; int h[N],e[M],ne[M],p[M],idx,cnt,n,m,k; int vis[N]; void add(int a,int b) { ne[idx]=h[a]; e[idx]=b; h[a]=idx++; } void dfs(int u) { vis[u]=1; p[cnt++]=u; for(int i=h[u];i!=-1;i=ne[i]) { int j=e[i]; if(vis[j])continue; dfs(j); p[cnt++]=u; } } int main() { memset(h,-1,sizeof h); cin>>n>>m>>k; puts("YES"); for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } dfs(1); m=(2*n+k-1)/k; cnt--; int ans=cnt/m; int res=cnt%m,r=0; for(int i=1;i<=ans;i++) { printf("%d",m); for(int j=0;j<m;j++) printf(" %d",p[r++]); puts(""); } if(res) { printf("%d",res); for(int i=0;i<res;i++) printf(" %d",p[r++]); puts(""); } return 0; }