AtCoder Beginner Contest 157
A - Duplex Printing
#include <bits/stdc++.h> #define ll long long using namespace std; int main() { //freopen("in.txt","r",stdin); int n; scanf("%d",&n); printf("%d\n",(n+1)/2); return 0; }
B - Bingo
#include <bits/stdc++.h> #define ll long long using namespace std; int a[5][5]; bool vis[5][5]; int main() { //freopen("in.txt","r",stdin); for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { scanf("%d",&a[i][j]); } } int n; scanf("%d",&n); for(int i=0,x;i<n;i++) { scanf("%d",&x); for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { if(a[i][j]==x) vis[i][j]=true; } } } bool f=false; for(int i=0;i<n;i++) { if(vis[i][0]&&vis[i][1]&&vis[i][2]) f=true; if(vis[0][i]&&vis[1][i]&&vis[2][i]) f=true; } if(vis[0][0]&&vis[1][1]&&vis[2][2]) f=true; if(vis[0][2]&&vis[1][1]&&vis[2][0]) f=true; printf("%s\n",f?"Yes":"No"); return 0; }
C - Guess The Number
题意：有M个要求，从高位起第si位为ci，找最小的不包含前导零的N位数，若不存在，输出-1。
数据范围：1<=N<=3,1<=M<=5,1<=si<=N,0<=ci<=9。
题解：讨论起来太麻烦了，很多神奇的样例卡，数据范围小，可以直接暴力枚举每个值，然后判断是否合法即可。
#include <bits/stdc++.h> #define ll long long using namespace std; int n,m,x[10],y[10]; int cal() { if(n==1) { for(int i=0;i<10;i++) { bool f=true; for(int j=0;j<m;j++) { if(i!=y[j]) f=false; } if(f) return i; } return -1; } if(n==2) { for(int i=10;i<100;i++) { bool f=true; for(int j=0;j<m;j++) { if(x[j]==1&&i/10!=y[j]) f=false; if(x[j]==2&&i%10!=y[j]) f=false; } if(f) return i; } return -1; } for(int i=100;i<1000;i++) { bool f=true; for(int j=0;j<m;j++) { if(x[j]==1&&i/100!=y[j]) f=false; if(x[j]==2&&(i/10)%10!=y[j]) f=false; if(x[j]==3&&i%10!=y[j]) f=false; } if(f) return i; } return -1; } int main() { //freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d",&x[i],&y[i]); } printf("%d\n",cal()); return 0; }
D - Friend Suggestions
题意：N个人，有M个朋友关系，K个敌对关系，定义候选朋友关系为存在不同的两人a，b，a和b没有朋友和敌对关系，且a和b存在间接的朋友关系，求每个人的候选朋友关系个数。
数据范围：2<=N<=1e5，0<=M,K<=1e5
题解：并查集求出每个人的直接间接的朋友数求出来，然后减去直接朋友数和自己本身，然后遍历敌对关系，判断两个是否存在间接朋友关系，若有，则两人数目减1。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+5; int f[N],a[N],ma[N],ans[N]; int Find(int x) { if(x==f[x]) return x; return f[x]=Find(f[x]); } int main() { //freopen("in.txt","r",stdin); int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) f[i]=i; for(int i=0,x,y;i<m;i++) { scanf("%d%d",&x,&y); a[x]++,a[y]++; f[Find(x)]=Find(y); } for(int i=1;i<=n;i++) { ma[Find(i)]++; } for(int i=1;i<=n;i++) { ans[i]=ma[f[i]]-a[i]-1; } for(int i=0,x,y;i<k;i++) { scanf("%d%d",&x,&y); if(f[x]==f[y]) ans[x]--,ans[y]--; } for(int i=1;i<=n;i++) { printf("%d%c",ans[i],i==n?‘\n‘:‘ ‘); } return 0; }
E - Simple String Queries
题意：有一个长度为N的字符串（只包含小写字母），现有Q个操作，操作1是把第x位的字符改成y，操作2是查询[l,r]内去重后有多少个字符。
数据范围：1<=N<=5e5，1<=Q<=2e4
题解：由于只有小写字母，可以对每一个字母进行讨论，那么就是一个单点修改，区间查询的问题，用树状数组进行维护。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N=5e5+5; char s[N],ss[5]; int f[N][26]; int n,q; void update(int id,int pos,int val) { for(int i=pos;i<=n;i+=(i&-i)) { f[i][id]+=val; } } int query(int id,int pos) { int ans=0; for(int i=pos;i;i-=(i&-i)) { ans+=f[i][id]; } return ans; } int main() { //freopen("in.txt","r",stdin); scanf("%d%s%d",&n,s+1,&q); for(int i=1;i<=n;i++) { int x=s[i]-‘a‘; update(x,i,1); } for(int i=0,op,x,y;i<q;i++) { scanf("%d",&op); if(op==1) { scanf("%d%s",&x,ss); update(s[x]-‘a‘,x,-1); update(ss[0]-‘a‘,x,1); s[x]=ss[0]; } else { scanf("%d%d",&x,&y); int ans=0; for(int j=0;j<26;j++) { if(query(j,y)-query(j,x-1)) ans++; } printf("%d\n",ans); } } return 0; }
F - Yakiniku Optimization Problem
题意：二维坐标系上有N个点(Xi,Yi)，每个点有一个系数Ci，要求找一个点，每一个点到这个点的权值为两点之间的欧几里得距离乘上系数Ci，最小化第K小的权值。
数据范围：1<=K<=N<=60，-1000<=Xi,Yi<=1000，1<=Ci<=100
题解：待补。
原文：https://www.cnblogs.com/zdragon1104/p/12396167.html