Codeforces round 1111-白红宇

Codeforces round 1111

阅读量：5750 次

发布时间：2019-06-18

本文共 5581 字，大约阅读时间需要 18 分钟。

CF Div 2 537

感觉题目难度OK，五个题都能做，后俩题考察人的翻译水平...

另外，$Claris$太强了...

A

直接按照题意模拟，不知道为啥有人会被×

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 1005char s[N],t[N];int main(){ int n,m;scanf("%s%s",s+1,t+1);n=strlen(s+1),m=strlen(t+1); if(n!=m)return puts("No"),0; for(int i=1;i<=n;i++) { if(s[i]==t[i])continue; if((s[i]=='a'||s[i]=='u'||s[i]=='e'||s[i]=='i'||s[i]=='o')&&(t[i]=='a'||t[i]=='u'||t[i]=='e'||t[i]=='i'||t[i]=='o'))continue; if((s[i]!='a'&&s[i]!='u'&&s[i]!='e'&&s[i]!='i'&&s[i]!='o')&&(t[i]!='a'&&t[i]!='u'&&t[i]!='e'&&t[i]!='i'&&t[i]!='o'))continue; puts("No");return 0; }puts("Yes");}

B

一开始以为是贪心，后来觉得，可以二分，最后发现，连二分都不用，直接枚举就行...

非常简单，枚举也需要用到一些贪心思想的...

显然，留下的一定是最大的几个，所以先从小到大排个序，然后剩下的随便加就行...

那么枚举删掉几个...

剩下的$O(1)$求答案，需要维护一个后缀和...

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 100005#define ll long longint a[N],n,m,k;ll s[N];long double ans;int main(){ scanf("%d%d%d",&n,&k,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1); for(int i=n;i;i--)s[i]=a[i]+s[i+1]; for(int i=1;i<=n&&i<=m+1;i++) { long double tmp=min((ll)m-i+1,(ll)k*(n-i+1)); ans=max(ans,(tmp+s[i])/(n-i+1)); } printf("%.7lf\n",(double)ans);}

最后发现，除了枚举之外的做法都被×了...

C

感觉比B要简单？

直接动态开点线段树+暴力分治即可...

因为每段区间直接是互相不影响的...

时间复杂度为线段树节点个数，也就是$O(kn)$

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 100005#define ll long long#define lson l,m,tr[rt].ls#define rson m+1,r,tr[rt].rsstruct Segment{int ls,rs,siz;}tr[N*31];int n,k,A,B,rot,cnt;void insert(int x,int l,int r,int &rt){ if(!rt)rt=++cnt;tr[rt].siz++;if(l==r)return ;int m=(l+r)>>1; if(x<=m)insert(x,lson);else insert(x,rson);}ll solve(int l,int r,int rt){ if(!rt)return A;if(l==r)return (ll)B*tr[rt].siz;int m=(l+r)>>1; return min((ll)B*(r-l+1)*tr[rt].siz,solve(lson)+solve(rson));}int main(){ scanf("%d%d%d%d",&n,&k,&A,&B); for(int i=1,x;i<=k;i++)scanf("%d",&x),insert(x,1,1<

D

这个题真的是看不懂题意是啥，多亏了Claris的题意.jpg

可以发现，不钦定相同集合的话，就是裸的背包。

那么钦定相同集合的话...也是裸的背包。

差别就是，需要把背包中钦定的部分回退，然后更新答案，再加回来...

记忆化搜索真快！

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            using namespace std;#define N 100005#define ll long long#define mod 1000000007map
             
              
                ,int >mp;int fac[N],inv[N],f[N],t[N],n,Q,w;char s[N];int q_pow(int x,int n){int ret=1;for(;n;n>>=1,x=(ll)x*x%mod)if(n&1)ret=(ll)ret*x%mod;return ret;}void ins(int x){for(int i=n;i>=x;i--)(f[i]+=f[i-x])%=mod;}void del(int x){for(int i=x;i<=n;i++)(f[i]+=mod-f[i-x])%=mod;}int calc(int x,int y){ if(x>y)swap(x,y);if(x+y>(n>>1))return 0;if(mp.find(make_pair(x,y))!=mp.end())return mp[make_pair(x,y)];int ret=0; del(x),del(y);ret=f[(n>>1)-x-y];ins(x);ins(y);return mp[make_pair(x,y)]=(((ret<<1)%mod)+mod)%mod;}int main(){ scanf("%s%d",s+1,&Q);n=strlen(s+1);f[0]=fac[0]=1; for(int i=1;i<=n;i++)t[s[i]]++,fac[i]=(ll)i*fac[i-1]%mod;inv[n]=q_pow(fac[n],mod-2); for(int i=n;i;i--)inv[i-1]=(ll)i*inv[i]%mod;w=(ll)fac[n>>1]*fac[n>>1]%mod; for(int i=0;i<=128;i++)if(t[i])ins(t[i]),w=(ll)w*inv[t[i]]%mod; while(Q--) { int x,y;scanf("%d%d",&x,&y); if(s[x]==s[y])printf("%lld\n",(ll)w*f[n>>1]%mod); else printf("%lld\n",(ll)w*calc(t[s[x]],t[s[y]])%mod); }}

E

这个题真的是有意思...

首先$\sum k\le 10^5$就一眼虚树...

然后钦定$r$的话就直接把$r$也建在虚树里，然后建双向边，以$r$为根遍历...

然后的话...

考试的时候，我写了一个$O(nm^2)$的树形背包，没调出来，不知道哪里GG了...

考完发现自己强行把插板问题转化为了背包做，就很绝望...

那么就直接说正解了...

我们考虑，枚举一个集合数量。

然后每次转移的时候，只需要这个节点和它的所有祖先不在同一个集合即可。

那么不论它的祖先怎么分配，它的方案数一定是$m-siz$，其中$m$是枚举的集合大小，$siz$是祖先个数...

每次转移的话，要么新建一个集合，也就是$f[i]+=f[i-1]$，要么$f[i]=f[i]\times (m-siz)$

附上代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 100005#define ll long long#define mod 1000000007struct node{int to,next;}e[N<<1];int head[N],cnt,fa[N],anc[N],dep[N],siz[N],son[N],idx[N],tims,n,Q;void add(int x,int y){e[cnt]=(node){y,head[x]};head[x]=cnt++;}void dfs1(int x,int from){ siz[x]=1,fa[x]=from,dep[x]=dep[from]+1; for(int i=head[x];i!=-1;i=e[i].next) { int to1=e[i].to; if(to1!=from)dfs1(to1,x),siz[x]+=siz[to1],siz[son[x]]
            
             =now;i--)(f[i+1]+=f[i])%=mod,f[i]=(ll)f[i]*(i-now)%mod;now++;} for(int i=head[x];i!=-1;i=e[i].next)if(e[i].to!=from)dfs(e[i].to,x); head[x]=-1;if(vis[x])now--;vis[x]=0; // printf("%d\n",x); // for(int i=0;i<=m;i++)printf("%d ",f[x][i]);puts("");}void build(int r){ f[0]=1;for(int i=1;i<=m;i++)f[i]=0; bool used_r=0;top=0;cnt=0; for(int i=1;i<=size;i++)if(q[i]==r){used_r=1;break;}if(!used_r)q[++size]=r;sort(q+1,q+size+1,cmp); sta[++top]=1; for(int i=1;i<=size;i++) { int x=q[i],lca=get_lca(sta[top],x);if(!used_r&&r==q[i])vis[x]=0;else vis[x]=1; while(top>1&&dep[sta[top-1]]>=dep[lca])add(sta[top-1],sta[top]),add(sta[top],sta[top-1]),top--; if(sta[top]!=lca)add(lca,sta[top]),add(sta[top],lca),sta[top]=lca;if(x!=sta[top])sta[++top]=x; }while(top>1)add(sta[top-1],sta[top]),add(sta[top],sta[top-1]),top--; dfs(r,0);int ans=0; for(int i=1;i<=m;i++)ans=(ans+f[i])%mod;printf("%d\n",(ans+mod)%mod);}int main(){ scanf("%d%d",&n,&Q);memset(head,-1,sizeof(head)); for(int i=1,x,y;i