2018.8.20 练习赛

T1 图论
题面：（待补）
搜索模拟，倒推

 1 #include<stdio.h>
 2 #define ll long long
 3 
 4 //1,2 == 1
 5 //0,1 == 1
 6 ll dfs(ll n,ll x,ll y)
 7 {
 8     if(n==1) return x==0&&y==1;
 9     ll k=1<<n-1;
10     if(x>=k) return dfs(n-1,x-k,y&k-1);
11     if(y>=k) return dfs(n-1,(k<<1)-1-y,x);
12     return dfs(n-1,y,k-x-1);
13 }
14 
15 ll n,a,b,c,d;
16 int main() {
17     scanf("%lld%lld%lld%lld%ld",&n,&a,&b,&c,&d);
18     a--,b--,c--,d--;
19     for(ll i=a; i<=c; i++,putchar(10))
20         for(ll j=b; j<=d; j++)
21             printf("%lld",dfs(n,i,j));
22 }

View Code

T2 数数
题面（同 [Jxoi2012]奇怪的道路）
记忆化搜索： f[u][l][v][s] u：起点 l：剩余边数 v：终点 s：[u,u-lim]度的奇偶性转移见code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define ll long long
 4 #define mod 998244353
 5 
 6 ll f[35][35][35][1<<9];
 7 ll n,m,lim;
 8 
 9 void inc(ll &a,ll b) {
10     a+=b;
11     a-=a<mod?0:mod;
12 }
13 
14 ll dfs(ll u,ll l,ll v,ll s) {
15     if(l==0) return s==0;
16     if(u==1) return 0;
17     if(f[u][l][v][s]!=-1) return f[u][l][v][s];
18     ll ans=0;
19     inc(ans,dfs(u,l-1,v,s^1^(1<<(u-v))));
20     if(v>1&&u-v+1<=lim) inc(ans,dfs(u,l,v-1,s));
21     else if(!(s&1)) inc(ans,dfs(u-1,l,u-2,s>>1));
22     return f[u][l][v][s]=ans;
23 }
24 
25 int main() {
26     memset(f,-1,sizeof(f));
27     scanf("%lld%lld%lld",&n,&m,&lim);
28     printf("%lld",dfs(n,m,n-1,0));
29 }

View Code

T3 树上路径
题面（待补）
RMQ区间极值，dfs序将子树问题转换为区间问题，ZKW线段树维护路径信息

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<cstring>
  4 #define ll long long
  5 #define MAXN 1000005
  6 using namespace std;
  7 
  8 char *p1,*p2,buf[1<<20];
  9 #define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
 10 inline int _R(){
 11     char s=GC;int v=0;
 12     while(s>57||s<48)s=GC;
 13     for(;s>47&&s<58;s=GC)v=v*10+s-48;
 14     return v;
 15 }
 16 
 17 int N,M,Q,w[MAXN];
 18 int en[MAXN],nex[MAXN],las[MAXN],etot;
 19 int dep[MAXN],fa[MAXN],In[MAXN],Out[MAXN],vt,E[MAXN],pos[MAXN];
 20 int Log[MAXN],RMQ[20][MAXN];
 21 ll C[MAXN];
 22 
 23 struct node{
 24     bool can;
 25     int u,v,lca;
 26 }T[MAXN<<2];int m;
 27 
 28 ll getsum(int x){
 29     int i;ll ret=0;
 30     for(i=x;i;i^=(i&-i))ret+=C[i];
 31     return ret;
 32 }
 33 
 34 void modify(int x,ll d){
 35     for(int i=x;i<=N;i+=(i&-i))C[i]+=d;
 36 }
 37 
 38 void link(int x,int y){
 39     en[++etot]=y;nex[etot]=las[x];las[x]=etot;
 40     en[++etot]=x;nex[etot]=las[y];las[y]=etot;
 41 }
 42 
 43 void dfs(int x,int pre){
 44     int i,y;
 45     dep[x]=dep[pre]+1;
 46     In[x]=++vt;
 47     fa[x]=pre;
 48     E[++E[0]]=x;pos[x]=E[0];
 49     for(i=las[x];i;i=nex[i]){
 50         y=en[i];if(y==pre)continue;
 51         dfs(y,x);
 52         E[++E[0]]=x;
 53     }
 54     Out[x]=vt;
 55 }
 56 
 57 int Min(int a,int b){
 58     return dep[a]<dep[b]?a:b;
 59 }
 60 
 61 int LCA(int x,int y){
 62     if(pos[x]>pos[y])swap(x,y);
 63     int d=pos[y]-pos[x]+1;
 64     return Min(RMQ[Log[d]][pos[x]],RMQ[Log[d]][pos[y]-(1<<Log[d])+1]);
 65 }
 66 
 67 int dis(int x,int y){return dep[x]+dep[y]-(dep[LCA(x,y)]<<1);}
 68 
 69 bool cmp(int a,int b){return dep[a]<dep[b];}
 70 
 71 node update(node a,node b){
 72     node ret;
 73     int tmp[4],x,y;
 74     if(!a.can||!b.can){ret.can=false;return ret;}
 75     if(dep[a.lca]<dep[b.lca])swap(a,b);
 76 
 77     if(dis(b.u,a.lca)+dis(b.v,a.lca)!=dis(b.u,b.v)){ret.can=false;return ret;}
 78     ret.can=true;
 79 
 80     tmp[0]=LCA(a.u,b.u);
 81     tmp[1]=LCA(a.v,b.u);
 82     tmp[2]=LCA(a.u,b.v);
 83     tmp[3]=LCA(a.v,b.v);
 84     sort(tmp,tmp+4,cmp);
 85     ret.u=tmp[3];ret.v=tmp[2];ret.lca=LCA(ret.u,ret.v);
 86 
 87     return ret;
 88 }
 89 
 90 node query(int l,int r){
 91     bool flag=false;node ret;
 92     for(l+=m-1,r+=m+1;l^r^1;l>>=1,r>>=1){
 93         if(~l&1)ret=flag?update(ret,T[l^1]):(flag=true,T[l^1]);
 94         if(r&1)ret=flag?update(ret,T[r^1]):(flag=true,T[r^1]);
 95     }
 96     return ret;
 97 }
 98 
 99 void init(){
100     int i,j,n;
101     dfs(1,0);
102     for(i=2;i<=2*N;i++)Log[i]=Log[i>>1]+1;
103     n=E[0];
104     for(i=1;i<=n;i++)RMQ[0][i]=E[i];
105     for(j=1;j<20;j++)
106     for(i=1;i+(1<<j-1)<=n;i++)RMQ[j][i]=Min(RMQ[j-1][i],RMQ[j-1][i+(1<<j-1)]);
107 }
108 
109 int main(){
110     int i,op,x,y,v,l,r;
111 
112     N=_R();
113     for(i=1;i<N;i++){
114         x=_R();y=_R();
115         link(x,y);
116     }
117 
118     init();
119 
120     for(i=1;i<=N;i++)w[i]=_R(),modify(In[i],w[i]),modify(Out[i]+1,-w[i]);
121     M=_R();
122     m=1;while(m<=M)m<<=1;
123     for(i=m;i<=(m<<1);i++)T[i].can=false;
124     for(i=1;i<=M;i++){
125         x=_R();y=_R();
126         T[m+i]=(node){true,x,y,LCA(x,y)};
127     }
128     for(i=m-1;i;i--)T[i]=update(T[i<<1],T[i<<1|1]);
129 
130     Q=_R();
131     while(Q--){
132         op=_R();
133         if(op==1){
134             x=_R(),v=_R();
135             int d=v-w[x];
136             modify(In[x],d);
137             modify(Out[x]+1,-d);
138             w[x]=v;
139         }
140         else {
141             l=_R(),r=_R();
142             node ret=query(l,r);
143             if(!ret.can)puts("0");
144             else printf("%lld
",getsum(In[ret.u])+getsum(In[ret.v])-(getsum(In[fa[ret.lca]])<<1)-w[ret.lca]);
145         }
146     }
147 }

View Code