codeforces contest 1111

  • A. Superhero Transformation
  • 题意:
  • 元音和元音,辅音和辅音字母之间可以互相转换,问两个字符串是否想同;
  • 题解:直接判断即可;
  • codeforces contest 1111
     1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int N=1010;
     4 char s[N]; 
     5 int n,m,vis1[N],vis2[N]; 
     6 int judge(char x){return x=='a'||x=='e'||x=='i'||x=='o'||x=='u';} 
     7 int main(){
     8 //    freopen("A.in","r",stdin);
     9 //    freopen("A.out","w",stdout);
    10     scanf("%s",s+1);
    11     n=strlen(s+1); 
    12     for(int i=1;i<=n;++i)vis1[i]=judge(s[i]);
    13     scanf("%s",s+1);
    14     m=strlen(s+1);
    15     for(int i=1;i<=m;++i)vis2[i]=judge(s[i]);
    16     int fg=0;
    17     if(n!=m){
    18         puts("No");
    19         return 0;
    20     }
    21     for(int i=1;i<=n;++i){
    22         if(vis1[i]^vis2[i]){fg=1;break;}
    23     }
    24     puts(fg?"No":"Yes");
    25     return 0;
    26 }
    View Code
  • B. Average Superhero Gang Power
  • 题意:
  • 长度为$n$的数组$a$,最多执行$m$次操作,每次1.将一个数+1;2.删除一个数。其中操作2对每个数最多做$k$次
  • 题解:
  • 枚举2做了多少次,贪心删除最小的值,尽量将剩下的次数全部用到1;
  • codeforces contest 1111
     1 #include<bits/stdc++.h>
     2 #define ll long long 
     3 #define ld double
     4 #define Run(i,l,r) for(int i=l;i<=r;++i)
     5 using namespace std;
     6 const int N=100010;
     7 int n,m,k;
     8 ll sum[N],a[N];
     9 int main(){
    10 //    freopen("B.in","r",stdin);
    11 //    freopen("B.out","w",stdout);
    12     scanf("%d%d%d",&n,&k,&m);
    13     for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    14     sort(a+1,a+n+1);
    15     for(int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];
    16     ld ans=0;
    17     for(int i=0;i<=min(n-1,m);++i){
    18         ans=max(ans , (ld) ( sum[n]-sum[i]+min(1ll*k*(n-i) , (ll)m-i) ) / (n-i) );
    19     } 
    20     printf("%.20lf\n",ans);
    21     return 0;
    22 }
    View Code
  • C. Creative Snap
  • 题意:
  • [1,2^n]的区间,每次直接删除一个区间,如果区间没有数存在代价是$A$,否则代价是$l*B*n_{a}$,$l$为区间长度,$n_{a}$为数的个数
  • 题解:
  • 直接做$dp$,复杂度相当于所有点的查询线段并:$O(n logn)$
  • codeforces contest 1111
     1 #include<bits/stdc++.h>
     2 #define ll long long
     3 #define ls (k<<1)
     4 #define rs (k<<1|1)
     5 using namespace std;
     6 const int N=100010;
     7 int n,k,A,B,a[N];
     8 inline int find(int l,int r){
     9     return lower_bound(a+1,a+k+1,r+1)-lower_bound(a+1,a+k+1,l);
    10 }
    11 ll dfs(int l,int r){
    12     int t=find(l,r);
    13     if(!t)return A;
    14     if(l==r)return !t?A:(ll)t*B;
    15     int mid=(l+r)>>1; 
    16     return min(1ll*t*B*(r-l+1),dfs(l,mid)+dfs(mid+1,r));
    17 }
    18 int main(){
    19 //    #ifndef ONLINE_JUDGE
    20 //    freopen("C.in","r",stdin);
    21 //    freopen("C.out","w",stdout); 
    22 //    #endif
    23     scanf("%d%d%d%d",&n,&k,&A,&B);
    24     for(int i=1;i<=k;++i)scanf("%d",&a[i]);
    25     sort(a+1,a+k+1);
    26     printf("%I64d\n",dfs(1,1<<n));
    27     return 0;
    28 }
    View Code
  • D. Destroy the Colony
  • 题意:
  • 给定一个由大小写字符组成的长度为偶数的字符串,好的串定义为想同字符都出现在想同的半边,询问给出两个位置$x,y$约定$x$和$y$的字符也必须在同一边问方案数;
  • 题解:
  • 统计每个字符的个数做背包,乘以一个可重元素的排列数就是答案,每次询问的话删除物品再加入即可;
  • codeforces contest 1111
     1 #include<bits/stdc++.h>
     2 #define ll long long 
     3 #define mod 1000000007
     4 #define rg register 
     5 #define il inline 
     6 using namespace std;
     7 const int N=100010; 
     8 char s[N];
     9 int n,q,vis[200],fac[N],tot,v[N],f[N],g[N],ans[200][200],iv;
    10 char gc(){
    11     static char*p1,*p2,s[1000000];
    12     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
    13     return(p1==p2)?EOF:*p1++;
    14 }
    15 int rd(){
    16     char c=gc();int x=0; 
    17     while(!isdigit(c))c=gc();
    18     while(isdigit(c))x=x*10+c-'0',c=gc();
    19     return x;
    20 }
    21 char gt(){
    22     char c=gc();
    23     while(!isalpha(c))c=gc();
    24     return c;
    25 }
    26 int inv(int x){
    27     int re=1;
    28     for(int y=mod-2;y;y>>=1,x=(ll)x*x%mod){
    29         if(y&1)re=(ll)re*x%mod;
    30     }
    31     return re;
    32 }
    33 int solve(int x,int y){
    34     if(!vis[x]||!vis[y])return 0;
    35     for(rg int i=0;i<=n>>1;++i)g[i]=f[i];
    36     if(x!=y){
    37         int v1=vis[x];
    38         for(rg int i=0;i+v1<=n>>1;++i)f[i+v1]=(f[i+v1]-f[i]+mod)%mod;
    39         v1=vis[y];
    40         for(rg int i=0;i+v1<=n>>1;++i)f[i+v1]=(f[i+v1]-f[i]+mod)%mod;
    41         v1=vis[x]+vis[y]; 
    42         for(rg int i=(n>>1)-v1;i>=0;--i)f[i+v1]=(f[i+v1]+f[i])%mod;
    43     }
    44     int re = 1ll * iv * f[n>>1] %mod; 
    45     for(int i=0;i<=n>>1;++i)f[i]=g[i];
    46     return re;
    47 }
    48 int main(){
    49 //    freopen("D.in","r",stdin);
    50 //    freopen("D.out","w",stdout);
    51     scanf("%s",s+1);n=strlen(s+1);
    52     for(rg int i=1;i<=n;++i)vis[s[i]]++;
    53     for(rg int i=fac[0]=1;i<=n;++i)fac[i]=(ll)fac[i-1]*i%mod;
    54     iv = 1ll * fac[n>>1] * fac[n>>1] %mod;
    55     for(rg int i='A';i<='z';++i)if(vis[i])v[++tot]=vis[i],iv=1ll*iv*inv(fac[v[tot]])%mod;
    56     f[0]=1;
    57     for(rg int i=1;i<=tot;++i)
    58     for(rg int j=(n>>1)-v[i];j>=0;--j){
    59         f[j+v[i]] = (f[j+v[i]]+f[j])%mod;
    60     }
    61     for(rg int x='A';x<='z';++x)
    62     for(rg int y=x;y<='z';++y)
    63     ans[x][y] = solve(x,y);
    64     scanf("%d",&q);
    65     for(rg int i=1,x,y;i<=q;++i){
    66         scanf("%d%d",&x,&y);
    67         if(s[x]>s[y])swap(x,y);
    68         printf("%d\n",ans[s[x]][s[y]]);
    69     }
    70     /*
    71     {
    72         for(rg int i=0;i<=n>>1;++i)printf("%d\n",f[i]);
    73     }*/
    74     return 0;
    75 }
    View Code
  • E. Tree
  • 题意:
  • 给定一棵树,$q$次询问,每次$k$个询问点$a_{i}$,分成至多$m$组,同组之间以$r$为根不存在祖先关系,问方案数;$n \le 1e5 \ ,  \ \sum k \le 1e5$
  • 题解:
  • 按深度排序之后假设$h[i]$为i的祖先个数,f[i][j]表示前$i$个点分成$j$组的方案;
  • $$f[i][j] = f[i-1][j] * (j-h[i]) + f[i-1][j-1]  $$
  • 其实不一定要深度,只需要按照$h[]$排序即可;
  • $h$可以在$dfs$序上维护一下;
  • codeforces contest 1111
     1 #include<bits/stdc++.h>
     2 #define ll long long 
     3 using namespace std;
     4 const int N=100010,mod=1000000007;
     5 int n,q,k,m,r,a[N],fa[N][17],dep[N],hd[N],o=1,bin[20],h[N],f[N][310],st[N],ed[N],c[N],vis[N],idx;
     6 struct Edge{int v,nt;}E[N<<1];
     7 char gc(){
     8     static char*p1,*p2,s[1000000];
     9     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
    10     return(p1==p2)?EOF:*p1++;
    11 }
    12 int rd(){
    13     int x=0;char c=gc();
    14     while(c<'0'||c>'9')c=gc();
    15     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
    16     return x; 
    17 }
    18 void adde(int u,int v){
    19     E[o]=(Edge){v,hd[u]};hd[u]=o++;
    20     E[o]=(Edge){u,hd[v]};hd[v]=o++; 
    21 }
    22 void dfs(int u,int F){
    23     st[u]=++idx;
    24     fa[u][0]=F;
    25     dep[u]=dep[F]+1;
    26     for(int i=1;bin[i]<dep[u];++i)fa[u][i]=fa[fa[u][i-1]][i-1];
    27     for(int i=hd[u];i;i=E[i].nt){
    28         int v=E[i].v;
    29         if(v==F)continue;
    30         dfs(v,u);
    31     }
    32     ed[u]=idx;
    33 }
    34 int lca(int u,int v){
    35     if(dep[u]<dep[v])swap(u,v);
    36     for(int i=0;i<17;++i)if(bin[i]&(dep[u]-dep[v]))u=fa[u][i];
    37     if(u==v)return u;
    38     for(int i=16;~i;--i)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    39     return fa[u][0]; 
    40 }
    41 void add(int x,int y){for(;x<=n;x+=x&-x)c[x]+=y;}
    42 int ask(int x){int re=0;for(;x;x-=x&-x)re+=c[x];return re;}
    43 void update(int u,int x){
    44     vis[u]+=x;
    45     add(st[u],x);
    46     add(ed[u]+1,-x);
    47 }
    48 int query(int u){
    49     int t=lca(u,r);
    50     return ask(st[u])+ask(st[r])-ask(st[t])*2+vis[t];
    51 }
    52 int main(){
    53     #ifndef ONLINE_JUDGE
    54     freopen("E.in","r",stdin);
    55     freopen("E.out","w",stdout);
    56     #endif
    57     n=rd();q=rd();
    58     for(int i=bin[0]=1;i<=17;++i)bin[i]=bin[i-1]<<1;
    59     for(int i=1;i<n;++i)adde(rd(),rd());
    60     dfs(1,0);
    61     f[0][0]=1;
    62     for(int i=1;i<=q;++i){
    63         k=rd();m=rd();r=rd();
    64         for(int j=1;j<=k;++j)a[j]=rd(),update(a[j],1); 
    65         for(int j=1;j<=k;++j)h[j]=query(a[j])-1;
    66         sort(h+1,h+k+1);
    67         for(int j=1;j<=k;++j)
    68         for(int l=1;l<=m;++l){
    69             f[j][l] = ((ll)f[j-1][l]*max(0,l-h[j])%mod+f[j-1][l-1])%mod;
    70         }
    71         int ans=0;
    72         for(int l=0;l<=m;++l)ans=(ans+f[k][l])%mod;
    73         printf("%d\n",ans);
    74         for(int j=1;j<=k;++j)update(a[j],-1);
    75     }
    76     return 0;
    77 }
    View Code

     

上一篇:[CQOI2012]组装 (贪心)


下一篇:平面距离最短的三个点 (分治)