「CF519X」Codeforces Round #294 (Div. 2)
「cf519A」A and B and Chess
模拟
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<set> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char ch[10][10]; int t1,t2; int main() { for(int i=1;i<=8;i++) scanf("%s",ch[i]+1); for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) { bool f=0; if(ch[i][j]>='a'&&ch[i][j]<='z') ch[i][j]=ch[i][j]-'a'+'A',f=1; int tmp=0; if(ch[i][j]=='Q')tmp=9; if(ch[i][j]=='R')tmp=5; if(ch[i][j]=='B')tmp=3; if(ch[i][j]=='N')tmp=3; if(ch[i][j]=='P')tmp=1; if(f)t1+=tmp; else t2+=tmp; } if(t1==t2)puts("Draw"); else if(t1>t2)puts("Black"); else puts("White"); return 0; } |
「cf519B」A and B and Compilation Errors
排序,双指针对比
用个hash/map统计下元素出现次数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<map> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int a[100005],b[100005],c[100005]; map<int,int> mp; void solve(int *a,int na,int *b,int nb) { mp.clear(); for(int i=1;i<=nb;i++) mp[b[i]]++; for(int i=1;i<=na;i++) { mp[a[i]]--; if(mp[a[i]]==-1){printf("%d\n",a[i]);break;} } } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<n;i++)b[i]=read(); for(int i=1;i<n-1;i++)c[i]=read(); solve(a,n,b,n-1); solve(b,n-1,c,n-2); return 0; } |
「cf519C」A and B and Team Training
实际上答案是min(n,m,(m+n)/3)
我分类讨论了TAT
还是很好yy的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<map> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int solve(int n,int m) { if(m>=2*n)return n; int t=m-n; m-=2*t;n-=t; t+=n/3*2; if(n%3==2)return t+1; else return t; } int main() { n=read();m=read(); if(n>m)swap(n,m); printf("%d\n",solve(n,m)); return 0; } |
「cf519D」A and B and Interesting Substrings
a[i][j]表示前缀和为i,字母j为末尾的前缀数量
每次查询(sum[i]-val[i],ch[i])
a[sum[i]][ch[i]]++
实现要用个map
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<map> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int l,x[30],num[100005],a[100005]; char ch[100005]; ll s[100005],ans; map<pair<ll,int>,int>mp; int main() { for(int i=1;i<=26;i++)x[i]=read(); scanf("%s",ch+1); l=strlen(ch+1); for(int i=1;i<=l;i++) { num[i]=ch[i]-'a'+1; a[i]=x[num[i]]; } for(int i=1;i<=l;i++) s[i]=s[i-1]+a[i]; for(int i=1;i<=l;i++) { ans+=mp[make_pair(s[i]-a[i],num[i])]; mp[make_pair(s[i],num[i])]++; } printf("%I64d\n",ans); return 0; } |
「cf519E」A and B and Lecture Rooms
倍增找出中点,以中点为根统计各个子树大小,不包含a,b所在子树
分类讨论下,注意x=y的情况
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<set> #include<map> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int bin[20]; int n,m,cnt; int deep[100005],size[100005],fa[100005][20],last[100005]; struct edge{ int to,next; }e[200005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void dp(int x) { size[x]=1; for(int i=1;bin[i]<=deep[x];i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa[x][0]) { deep[e[i].to]=deep[x]+1; fa[e[i].to][0]=x; dp(e[i].to); size[x]+=size[e[i].to]; } } int lca(int x,int y) { int t=deep[x]-deep[y]; for(int i=0;bin[i]<=t;i++) if(t&bin[i])x=fa[x][i]; for(int i=19;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; if(x==y)return x; return fa[x][0]; } int solve(int x,int y) { if(x==y)return n; int t=lca(x,y),l; if(t!=y)l=deep[x]+deep[y]-2*deep[t]; else l=deep[x]-deep[y]; if(l&1)return 0; l/=2; for(int i=0;bin[i]<=l-1;i++) if((l-1)&bin[i])x=fa[x][i]; int f=fa[x][0]; if(f==t) { int l=deep[y]-deep[t]; for(int i=0;bin[i]<=l-1;i++) if((l-1)&bin[i])y=fa[y][i]; return n-size[x]-size[y]; } return size[f]-size[x]; } int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v); } dp(1); m=read(); while(m--) { int u=read(),v=read(); if(deep[u]<deep[v])swap(u,v); printf("%d\n",solve(u,v)); } return 0; } |
第一题把K当做knight了……还好有人及时Hack