Codeforces Round #415 Div. 1-白红宇

Codeforces Round #415 Div. 1

阅读量：4956 次

发布时间：2019-06-12

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

　　A：考虑每对最大值最小值的贡献即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define N 300010#define P 1000000007 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,a[N],p[N],x,ans;signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1); p[0]=1;for (int i=1;i<=n;i++) p[i]=2ll*p[i-1]%P; for (int i=2;i<=n;i++) { ans=(ans+1ll*a[i]*(p[i-1]-1))%P; x=(2ll*x+a[i-1])%P; ans=(ans-x+P)%P; } cout<

　　B：考虑每次都询问x=i y=i+1。这样得到的是最近的被标记点是在左边还是右边。这样二分一下可以确定一个标记点的位置。同样二分找第二个点，由于要使其不和第一个点重复，对第一个点的两边分别考虑，二分过程中需要保证第一个点不对询问造成影响，讨论一下一些边界即可。

#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,k;char s[10];bool ask(int x,int y){ cout<<1<<' '<
           
            <<' '<
            
             <
             
              n) return 0; if (x==1) { return ask(1,2); } if (x==n) { return ask(n,n-1); } if (ask(x,x-1)&&ask(x,x+1)) return 1;else return 0;}signed main(){ n=read(),k=read(); int x=0; if (ask(n,n-1)) x=n; else { int l=1,r=n-1; while (l
              
               >1; if (ask(mid,mid+1)) { r=mid; } else { l=mid+1; } } x=l; } int l=1,r=x-1; while (l
               
                >1; if (ask(mid,mid+1)) r=mid; else l=mid+1; } if (check(l)&&x!=l) cout<<2<<' '<
                
                 <<' '<
                 
                  <
                  
                   >1; if (ask(mid+1,mid)) l=mid+1; else r=mid; } if (check(x)&&x!=l) cout<<2<<' '<
                   
                    <<' '<
                    
                     <
                     
                      1) if (ask(x-1,x)) {cout<<2<<' '<
                      
                       <<' '<
                       
                        <

　　C：打表可以发现，对于2^k*2^k的矩阵，将其分成左上左下右上右下四部分，其中左上和右下相同，左下和右上相同，且左下是左上+2^k-1复制而来。于是直接记搜即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           using namespace std;#define ll long long#define N 100010#define P 1000000007#define mp(x,y) make_pair((x),(y))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;}typedef pair
            
              pii;struct data{ int x,y,k; bool operator <(const data&a) const { return x
             
              
               
                 f;pii operator +(pii a,pii b){ return mp((a.first+b.first)%P,(a.second+b.second)%P);}pii calc(int x,int y,int k){ if (x==0||y==0||k<=0) return mp(0,0); if (x==1&&y==1) return mp(1,1); k=min(k,x+y-1); if (x>y) swap(x,y); data qwq=(data){x,y,k}; if (f.find(qwq)!=f.end()) return f[qwq]; int u=1; while ((u<<1)

　　D：搬上LIS的单调队列做法，设f[j]为前i位长度为j的单增序列的最后一位的最小值。考虑转移，显然f[j]=min(f[j],max(f[j-1]+1,l[i])) (f[j-1]<r[i])。注意到显然有f[j]<f[j+1]，所以不考虑l[i]限制的话，上述转移不需要取min，符合条件就可以直接赋值。那么二分找到l[i]和r[i]对应的边界，就相当于将区间平移并+1，然后区间内对l[i]取max。可以用splay维护。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define lson tree[k].ch[0]#define rson tree[k].ch[1]#define N 300010#define inf 1000000001char 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,a[N],b[N],root,cnt;struct data{int ch[2],fa,x,lazymax,lazyadd,s;}tree[N<<1];void up(int k){tree[k].s=tree[lson].s+tree[rson].s+1;}void access(int k){while (k) up(k),k=tree[k].fa;}int newnode(int v){ int k=++cnt; tree[k].s=1; tree[k].x=v; return k;}void build(int &k,int l,int r){ if (l>r) return; int mid=l+(r-l)/2; if (mid<=0) k=newnode(mid); else k=newnode(inf+mid); build(lson,l,mid-1); build(rson,mid+1,r); tree[lson].fa=tree[rson].fa=k; up(k);}int whichson(int k){return tree[tree[k].fa].ch[1]==k;} void update(int k,int lazymax,int lazyadd){ tree[k].x+=lazyadd; tree[k].x=max(tree[k].x,lazymax); tree[k].lazyadd+=lazyadd; tree[k].lazymax+=lazyadd; tree[k].lazymax=max(tree[k].lazymax,lazymax);}void down(int k){ update(lson,tree[k].lazymax,tree[k].lazyadd); update(rson,tree[k].lazymax,tree[k].lazyadd); tree[k].lazymax=tree[k].lazyadd=0;}void push(int k){if (k!=root) push(tree[k].fa);down(k);}void move(int k){ int fa=tree[k].fa,gf=tree[fa].fa,p=whichson(k); if (fa!=root) tree[gf].ch[whichson(fa)]=k;tree[k].fa=gf; tree[fa].ch[p]=tree[k].ch[!p];tree[tree[k].ch[!p]].fa=fa; tree[k].ch[!p]=fa,tree[fa].fa=k; up(fa),up(k);}void splay(int k,int rt){ push(k); while (tree[k].fa!=rt) { int fa=tree[k].fa; if (tree[fa].fa!=rt) if (whichson(fa)^whichson(k)) move(k); else move(fa); move(k); } if (rt==0) root=k;}int find(int k,int x){ if (tree[lson].s-1==x) return k; if (tree[lson].s-1>x) return find(lson,x); else return find(rson,x-tree[lson].s-1);}int findsuf(int k,int x){ if (k==0) return -2; down(k); if (tree[k].x<=x) return findsuf(rson,x); else { int t=findsuf(lson,x); if (t==-2) return k; else return t; }}int findpre(int k,int x){ if (k==0) return -2; down(k); if (tree[k].x>=x) return findpre(lson,x); else { int t=findpre(rson,x); if (t==-2) return k; else return t; }}int getrank(int k){ splay(k,0); return tree[lson].s-1;}int split(int l,int r){ int p=find(root,l-1),q=find(root,r+1); splay(p,0);splay(q,p); return tree[q].ch[0];}void del(int x){ int k=split(x,x); tree[tree[k].fa].ch[0]=0; access(tree[k].fa);}void ins(int x,int v){ int k=split(x,x); lson=newnode(v); tree[lson].fa=k; access(lson);}int query(int x){ return tree[split(x,x)].x;}void add(int l,int r){ int k=split(l,r); update(k,0,1);}void getmax(int l,int r,int x){ if (l>r) return; int k=split(l,r); update(k,x,0);}signed main(){#ifndef ONLINE_JUDGE freopen("a.in","r",stdin); freopen("a.out","w",stdout);#endif n=read(); for (int i=1;i<=n;i++) a[i]=read(),b[i]=read(); build(root,-1,n+1); for (int i=1;i<=n;i++) { int l=getrank(findsuf(root,a[i])); int r=getrank(findpre(root,b[i]))+1; if (l>r) continue; del(r);ins(l-1,query(l-1));add(l,r);getmax(l,r,a[i]); } for (int i=n;i>=1;i--) if (query(i)

　　E：众所周知φ(nm)=φ(n)*φ(m)*gcd(n,m)/φ(gcd(n,m))，于是莫比乌斯反演一下，最后大约要求f(D)=Σdis(u,v)*φ(a_u)*φ(a_v) (D|a_u,a_v)。考虑点分，可以转化为对每个点u求g(D,u)=2deep_u*φ(a_u)*φ(a_v) (D|a_u,a_v)，每个点对所有因子加一下贡献即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
             using namespace std;#define ll long long#define N 200010#define P 1000000007char 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,a[N],p[N],t;int prime[N],phi[N],mobius[N],inv[N],cnt;int deep[N],size[N],val[N],f[N],ans;bool flag[N];vector
            
              factor[N];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;}inline void inc(int &x,int y){x+=y;if (x>=P) x-=P;}void make(int k,int from){ size[k]=1; for (int i=p[k];i;i=edge[i].nxt) if (!flag[edge[i].to]&&edge[i].to!=from) { deep[edge[i].to]=deep[k]+1; make(edge[i].to,k); size[k]+=size[edge[i].to]; }}int findroot(int k,int from,int s){ int mx=0; for (int i=p[k];i;i=edge[i].nxt) if (!flag[edge[i].to]&&edge[i].to!=from&&size[edge[i].to]>size[mx]) mx=edge[i].to; if ((size[mx]<<1)>s) return findroot(mx,k,s); else return k;}void work(int k,int from,int op){ for (int i=0;i

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

你可能感兴趣的文章

Setting up a Passive FTP Server in Windows Azure VM（ReplyCode: 227, Entering Passive Mode ）