博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
Mail.Ru Cup 2018 Round 3
阅读量：5217 次
发布时间：2019-06-14

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

　　A：签到

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 110char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,cnt[N];signed main(){/*#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d\n";#endif*/ n=read(); for (int i=1;i<=n;i++) { int m=read(); while (m--) cnt[read()]++; } for (int i=1;i<=100;i++) if (cnt[i]==n) cout<
           <<' '; return 0; //NOTICE LONG LONG!!!!!}

　　B：考虑模意义下每个数的贡献即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 1100char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,cnt[N];ll ans;signed main(){/*#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d\n";#endif*/ n=read(),m=read(); for (int i=1;i<=m;i++) cnt[i*i%m]+=n/m+(n%m>=i); ans=1ll*cnt[0]*cnt[0]; for (int i=1;i

　　C：如果上一轮对方选择了某一组英雄中的一个，而另一个还没被选，显然只能选择他。否则显然应该先把每一组英雄中价值较大的选中，这样对方必须选择另一个，最后再将剩余英雄从大到小选取即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 2100char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,a[N<<1],match[N<<1],cnt;bool flag[N<<1];signed main(){/*#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d\n";#endif*/ n=read(),m=read(); for (int i=1;i<=2*n;i++) a[i]=read(); for (int i=1;i<=m;i++) { int x=read(),y=read(); match[x]=y,match[y]=x; } int t=read(),x=0; if (t==2) {x=read();flag[x]=1;cnt++;} while (cnt<2*n) { if (match[x]&&!flag[match[x]]) cout<
           
            <
            
             a[match[i]]) cout<
             <
              
               a[u]) u=i; cout<
               <

 

　　D：大胆猜想答案等于子树内叶子数量。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 100010char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,fa[N],size[N],p[N],t;struct data{int to,nxt;}edge[N<<1];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}void dfs(int k){ size[k]=(p[k]==0); for (int i=p[k];i;i=edge[i].nxt) { dfs(edge[i].to); size[k]+=size[edge[i].to]; }}signed main(){/*#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d\n";#endif*/ n=read(); for (int i=2;i<=n;i++) fa[i]=read(),addedge(fa[i],i); dfs(1); sort(size+1,size+n+1); for (int i=1;i<=n;i++) printf("%d ",size[i]); return 0; //NOTICE LONG LONG!!!!!}

　　E：暴力枚举0串的长度，显然1串的长度可以由此确定，然后哈希暴力匹配判断即可。复杂度大约线性。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define int long long#define N 2000010char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,cnt0,cnt1,ans,Hash[2][N],P[2],Q[2][N];char a[N],b[N];int get(int x,int y,int op){ return (Hash[op][y]-1ll*Hash[op][x-1]*Q[op][y-x+1]%P[op]+P[op])%P[op];}signed main(){/*#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout); const char LL[]="%I64d\n";#endif*/ scanf("%s",a+1);n=strlen(a+1); scanf("%s",b+1);m=strlen(b+1); for (int i=1;i<=n;i++) if (a[i]=='0') cnt0++;else cnt1++; P[0]=1000000007,P[1]=19260817; for (int i=1;i<=m;i++) Hash[0][i]=(Hash[0][i-1]*509ll+b[i])%P[0]; for (int i=1;i<=m;i++) Hash[1][i]=(Hash[1][i-1]*509ll+b[i])%P[1]; Q[0][0]=Q[1][0]=1; for (int i=1;i<=m;i++) Q[0][i]=Q[0][i-1]*509ll%P[0]; for (int i=1;i<=m;i++) Q[1][i]=Q[1][i-1]*509ll%P[1]; for (int i=1;i<=m;i++) if (m>cnt0*i&&(m-cnt0*i)%cnt1==0) { int j=(m-cnt0*i)/cnt1; int cur=1,pos0=0,pos1=0; for (int x=1;x<=n;x++) if (a[x]=='0') pos0=cur,cur+=i; else pos1=cur,cur+=j; cur=1;int tot=1; if (i==j) { tot=0; for (int x=1;x<=i;x++) if (b[pos0+x-1]!=b[pos1+x-1]) {tot=1;break;} } if (tot==0) continue; for (int x=1;x<=n;x++) if (a[x]=='0') { tot=(get(cur,cur+i-1,0)==get(pos0,pos0+i-1,0)&&get(cur,cur+i-1,1)==get(pos0,pos0+i-1,1)); cur+=i; if (tot==0) break; } else { tot=(get(cur,cur+j-1,0)==get(pos1,pos1+j-1,0)&&get(cur,cur+j-1,1)==get(pos1,pos1+j-1,1)); cur+=j; if (tot==0) break; } ans+=tot; } cout<

　　F：先不考虑training。显然如果确定了切题集合，应该按照难度从高到低做。于是按难度从高到低排序，设f[i][j][k]为前i个题切j个，得到的分数和为k时的最小耗时。复杂度T*10*n^3。training时间可以三分，但套上去就多了个log跑不过了。事实上training时间不影响决策，并且有training后可以直接算出答案，dp完解方程即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 110#define inf 10000000000000000char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int T,n;const double eps=1E-8;double c,t,f[N][N][N*10],p[N];struct data{ int x,y; bool operator <(const data&a) const { return x>a.x; }}a[N];double work(double a,double b,double c){ return (-b+sqrt(b*b-4*a*c))/(2*a);}int calc(){ for (int i=n*10;i>=0;i--) for (int j=0;j<=n;j++) {//c*x^2+(1-c(t-10*j))x+f[j][i]-(t-10*j) double u=max(0.0,work(c,1-c*(t-10*j),f[n][j][i]+10*j-t)); if (f[n][j][i]/(u*c+1)+10*j+u<=t+eps) return i; }}signed main(){#ifndef ONLINE_JUDGE freopen("f.in","r",stdin); freopen("f.out","w",stdout); const char LL[]="%I64d\n";#endif T=read(); p[0]=1;for (int i=1;i<=100;i++) p[i]=p[i-1]*0.9; while (T--) { n=read(); cin>>c>>t; for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(); sort(a+1,a+n+1); for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) for (int k=0;k<=n*10;k++) f[i][j][k]=inf; f[0][0][0]=0; for (int i=1;i<=n;i++) for (int j=0;j<=i;j++) for (int k=0;k<=j*10;k++) { f[i][j][k]=f[i-1][j][k]; if (k>=a[i].y&&j) f[i][j][k]=min(f[i][j][k],f[i-1][j-1][k-a[i].y]+a[i].x/p[j]); } printf("%d\n",calc()); } return 0; //NOTICE LONG LONG!!!!!}

　　G：先暴力让t%n==0。然后考虑预处理出当t=n时每个点到达的位置，如果能求出，将该过程进行t/n轮即可，可以倍增。注意到对于t=n~1的每一步，实际上是对每个点将到达的位置做一个区间复制与平移操作，可持久化treap维护即可。

　　注意到如果使用普通的随机优先级treap，我们区间操作时会改变每个点的优先级，这样实际上是无法保证复杂度的。（我一直以为写挂了调了一天）考虑使用clj论文中的随机化合并方法，即

　　然而即使这样还是会出现深度变得很大的情况。使用朝鲜树式重构，超过一定深度直接拍扁重构即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 100010#define lson tree[k].ch[0]#define rson tree[k].ch[1]#define pii pair
            
             char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int n,m,s,to[N][50],cnt,root;ll t;struct data{int ch[2],x,size,d;}tree[N<<8];int jump(ll x,ll y){if (x<=m) x+=y;else x-=y;if (x>n) x=(x-1)%n+1;else x=(x%n+n-1)%n+1;return x;}void up(int k){tree[k].size=tree[lson].size+tree[rson].size+1;tree[k].d=max(tree[lson].d,tree[rson].d)+1;}int newpoint(int x){cnt++;tree[cnt].x=x,tree[cnt].size=1,tree[cnt].d=1;tree[cnt].ch[0]=tree[cnt].ch[1]=0;return cnt;}void getto(int k){ if (lson) getto(lson); to[++cnt][0]=tree[k].x; if (rson) getto(rson);}int merge(int x,int y){ if (!y||!x) {tree[++cnt]=tree[x|y];return cnt;} int k=++cnt; if (1ll*rand()*(tree[x].size+tree[y].size)<1ll*tree[x].size*RAND_MAX) { tree[k]=tree[x]; rson=merge(rson,y); up(k); } else { tree[k]=tree[y]; lson=merge(x,lson); up(k); } return k;}pii split(int x,int u){ if (!x) return make_pair(0,0); int k=++cnt;tree[k]=tree[x]; if (u==tree[k].size) return make_pair(k,0); if (u==0) return make_pair(0,k); if (tree[lson].size>=u) { pii t=split(lson,u); lson=t.second;up(k); return make_pair(t.first,k); } else if (tree[lson].size+1==u) {int t=rson;rson=0;up(k);return make_pair(k,t);} else { pii t=split(rson,u-tree[lson].size-1); rson=t.first;up(k); return make_pair(k,t.second); }}void build(){root=cnt=0;for (int i=1;i<=n;i++) root=merge(root,newpoint(to[i][0]));}signed main(){#ifndef ONLINE_JUDGE freopen("g.in","r",stdin); freopen("g.out","w",stdout); const char LL[]="%I64d\n";#endif srand(20020509); n=read(),m=read(),s=read();cin>>t; for (;t%n;t--) s=jump(s,t);t/=n; for (int i=1;i<=n;i++) to[i][0]=i; build(); for (int i=1;i
             
              0) { pii a=split(lastroot,n-i),b=split(a.first,m-i); root=merge(root,b.second); } else { pii a=split(lastroot,m+n-i),b=split(a.first,n-i); root=merge(root,merge(a.second,b.first)); } if (tree[root].d>200) cnt=0,getto(root),build(); } cnt=0;getto(root); for (int j=1;j<50;j++) for (int i=1;i<=n;i++) to[i][j]=to[to[i][j-1]][j-1]; for (int j=49;~j;j--) if (t&(1ll<

　　H：相当于判断是否存在首尾相同但本质不同的子串。因为只需要判断是否存在，在比较两个首尾相同的字符串时，可以只比较字符串第二位，因为如果其相同我们仍会继续比较以这个第二位为首的字符串。

　　考虑根号分块，将字符串长度以u=√Σk为界分为两组。

　　对于长度均小于u的组，考虑固定子串的末位字符，找到该字符的所有出现位置，然后暴力判断是否存在某一对位置，其前缀中有相邻字符满足第一位相同但第二位不同。这显然可以做到O(uΣk)。

　　然后考虑长度大于u的组，显然组内字符串数量不会超过u个，我们将其中每一个与其他所有字符串进行考虑。如果能将每一对以O(较短字符串长度)的复杂度check即可做到O(uΣk)。枚举长度较小的字符串中的每个相邻字符对，在较长字符串中找到首字符的出现位置，若第二个字符不同则记录；然后枚举末位字符在较长字符串中找到出现位置，如果前缀记录的东西有小于该位置的说明存在这样的字符串。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define ll long long#define N 300010#define pii pair
             
              char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}int gcd(int n,int m){return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int T,n,m,nxt[N],pos[N];vector
              
                a[N],b[N],c[N];vector< pii > app[N];signed main(){#ifndef ONLINE_JUDGE freopen("h.in","r",stdin); freopen("h.out","w",stdout); const char LL[]="%I64d\n";#endif T=read(); while (T--) { n=read(),m=read(); bool flag=0; int p=0,q=0,K=0; for (int i=1;i<=m;i++) { c[i].clear(); c[i].push_back(read());K+=c[i][0]; for (int j=1;j<=c[i][0];j++) c[i].push_back(read()); } int u=sqrt(K); for (int i=1;i<=m;i++) if (c[i][0]>u) a[++p]=c[i];else b[++q]=c[i]; for (int i=1;i<=n;i++) app[i].clear(); for (int i=1;i<=q;i++) for (int j=1;j<=b[i][0];j++) app[b[i][j]].push_back(make_pair(i,j)); memset(nxt,255,sizeof(nxt)); for (int i=1;i<=n;i++) if (app[i].size()>1) { for (int j=0;j
               
                first) {flag=1;break;} if (pos[a[j][k]]&&k
                
                 
                  first) {flag=1;break;} if (pos[b[j][k]]&&k

 

　　

 

转载于:https://www.cnblogs.com/Gloid/p/10388719.html

你可能感兴趣的文章
哈希表1
查看>>
用Data Url (data:image/jpg;base64,)将小图片生成数据流形式
查看>>
实验2-2
查看>>
C#初识
查看>>
String,StringBuffer与StringBuilder的区别?? .
查看>>
JavaScript（三） 数据类型
查看>>
移动端rem布局屏幕适配插件（放js中便可使用）
查看>>
Docker
查看>>
bzoj2259 [Oibh]新型计算机
查看>>
对位与字节的深度认识
查看>>
C++编程基础二 16-习题4
查看>>
MongoDB遇到的疑似数据丢失的问题。不要用InsertMany！
查看>>
服务器被疑似挖矿程序植入107.174.47.156，发现以及解决过程（建议所有使用sonatype/nexus3镜像的用户清查一下）...
查看>>
JQuery 学习
查看>>
session token两种登陆方式
查看>>
C# ArrayList
查看>>
IntelliJ IDEA 12集成Tomcat 运行Web项目
查看>>
java，多线程实现
查看>>
个人作业4-alpha阶段个人总结
查看>>
android smack MultiUserChat.getHostedRooms( NullPointerException)
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-23 08:46:18   当前IP: 18.118.119.129   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我