2017.8.1 Noip2018模拟测试赛（十七）

日期：	八月第一天	总分：	300分
难度：	提高 ~ 省选	得分：	100分（不应该啊！）

题目目录：

T1：战争调度

T2：选数

T3：由乃的OJ

赛后心得：

MMP，首先第一题花了大概一半的时间，碰巧想到了正解。

好吧，作为数学渣的我看到T2肯定是懵的啦！T3又那么难，导致我后半场比赛都在发呆……

看来我要恶补数学了！！……

题解：

T1：战争调度

树形dp，暴力枚举每个点的染色情况，发$f[i][j]$表示$i$的子树中，有$j$个黑点，所产生的最大贡献。

时间复杂度 $O(2^{2n+1})$

CODE：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int n,m,ans=0,f[2005][2005],v[2005][2005][2];
 7 bool p[20];
 8 
 9 void dfs(int x,int d){
10     memset(f[x],0,sizeof(f[x]));
11     if(d==1){
12         for(int j=1;j<=n-1;j++){
13             if(p[j+1])f[x][1]+=v[x][j][1];
14             else f[x][0]+=v[x][j][0];
15         }
16         return;
17     }
18     p[d]=true,dfs(x<<1,d-1),dfs(x<<1|1,d-1);
19     for(int i=0;i<(1<<d-1);i++){
20         for(int j=0;j<(1<<d-1);j++)
21             f[x][i+j]=max(f[x][i+j],f[x<<1][i]+f[x<<1|1][j]);
22     }
23     p[d]=false,dfs(x<<1,d-1),dfs(x<<1|1,d-1);
24     for(int i=0;i<(1<<d-1);i++){
25         for(int j=0;j<(1<<d-1);j++)
26             f[x][i+j]=max(f[x][i+j],f[x<<1][i]+f[x<<1|1][j]);
27     }
28 }
29 
30 int main(){
31     scanf("%d%d",&n,&m);
32     for(int i=(1<<n-1);i<(1<<n);i++){
33         for(int j=1;j<=n-1;j++)
34             scanf("%d",v[i][j]+1);
35     }
36     for(int i=(1<<n-1);i<(1<<n);i++){
37         for(int j=1;j<=n-1;j++)
38             scanf("%d",v[i][j]+0);
39     }
40     dfs(1,n);
41     for(int i=0;i<=m;i++)ans=max(ans,f[1][i]);
42     printf("%d",ans);
43 }

T2：选数

推公式应该不算太难，只不过这题要用杜教筛。

egin{aligned}
ans&=sum^H_{x_i=L}[gcd(x_i)=K]\
&=sum^h_{x_i=l}[gcd(x_i)=1] &(l=lfloorfrac{L-1}{K} floor,h=lfloorfrac{H}{K} floor)\
&=sum^h_{x_i=l}sum_{dmid gcd(x_i)}mu(d)\
&=sum^h_{x_i=l}sum_{dmid x_i}mu(d)\
&=sum^h_{d=1}sum_{l<x_i h,dmid x_i}mu(d)\
&=sum^h_{d=1}(lfloorfrac{h}{d} floor-lfloorfrac{l}{d} floor)^nmu(d)\
end{aligned}

CODE：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<map>
 4 using namespace std;
 5 
 6 #define mod 1000000007
 7 int n,k,l,r,ans=0;
 8 int mu1[2000005],pri[2000005],cnt=0;
 9 bool vis[2000005];
10 map<int,int> mu2; 
11 
12 int qpow(int x,int y){
13     int ans=1;
14     while(y){
15         if(y&1)ans=1LL*ans*x%mod;
16         y>>=1,x=1LL*x*x%mod;
17     }
18     return ans;
19 }
20 
21 int init(){
22     mu1[1]=1;
23     for(int i=2;i<=2000000;i++){
24         if(!vis[i]){
25             mu1[i]=-1;
26             pri[++cnt]=i;
27         }
28         for(int j=1;j<=cnt&&i*pri[j]<=2000000;j++){
29             vis[i*pri[j]]=true;
30             if(i%pri[j]==0){
31                 mu1[i*pri[j]]=0;break;
32             }else mu1[i*pri[j]]=-mu1[i];
33         }
34     }
35     for(int i=1;i<=2000000;i++)mu1[i]+=mu1[i-1];
36 }
37 
38 int get_mu(int x){
39     if(x<=2000000)return mu1[x];
40     if(mu2.count(x))return mu2[x];
41     long long ans=1;
42     for(int i=1,pos;i<=(x>>1);i=pos+1){
43         pos=x/(x/i);
44         ans-=1LL*(get_mu(pos)-get_mu(i-1))*(x/i-1);
45     }
46     return mu2[x]=(ans+mod)%mod;
47 }
48 
49 int main(){
50     scanf("%d%d%d%d",&n,&k,&l,&r);
51     init();
52     l=(l-1)/k,r=r/k;
53     for(int i=1,pos;i<=r;i=pos+1){
54         pos=min(r/(r/i),l/i?(l/(l/i)):(int)2e9);
55         ans=(ans+1LL*qpow(r/i-l/i,n)*(get_mu(pos)-get_mu(i-1)))%mod;
56     }
57     printf("%d",(ans+mod)%mod);
58 }

T3：由乃的OJ

强烈建议先做简化版——起床困难综合症；

核心：位运算每位独立，互不影响，不像加法、乘法会有进位！！

这个只不过变为了多组查询，树上操作。

用树剖啊！！线段树维护每一位正着和反着，每一位 1 与 0 的情况，压在一个 unsigned long long 里

会做那题，肯定能想到这题的正解，只不过很考验代码实现能力。

CODE：

  1 #include<iostream>
  2 #include<cstdio>
  3 using namespace std;
  4 
  5 #define LL long long
  6 #define lch (o<<1)
  7 #define rch (o<<1|1)
  8 int n,m,k,ot,x,y,tot=0,cnt=0,h[100005];
  9 int fa[100005],dep[100005],son[100005],opt[100005];
 10 int siz[100005],tp[100005],tid[100005],rak[100005];
 11 unsigned long long z,val[100005];
 12 struct Node{
 13     unsigned long long L0,L1,R0,R1;
 14 }v[400005],ans1[100005],ans2[100005];
 15 struct Edge{
 16     int x,next;
 17 }e[200005];
 18 
 19 void add_edge(int x,int y){
 20     e[++tot].x=y;
 21     e[tot].next=h[x],h[x]=tot;
 22 }
 23 
 24 void dfs1(int x,int father,int deep){
 25     fa[x]=father,dep[x]=deep,siz[x]=1;
 26     for(int i=h[x];i;i=e[i].next){
 27         if(e[i].x==father)continue;
 28         dfs1(e[i].x,x,deep+1);
 29         siz[x]+=siz[e[i].x];
 30         if(siz[e[i].x]>siz[son[x]])son[x]=e[i].x;
 31     }
 32 }
 33 
 34 void dfs2(int x,int top){
 35     tp[x]=top,tid[x]=++cnt,rak[cnt]=x;
 36     if(son[x])dfs2(son[x],top);
 37     for(int i=h[x];i;i=e[i].next){
 38         if(e[i].x==fa[x]||e[i].x==son[x])continue;
 39         dfs2(e[i].x,e[i].x);
 40     }
 41 }
 42 
 43 unsigned LL opr(unsigned LL x,int opt,unsigned LL y){
 44     if(opt==1)return x&y;
 45     if(opt==2)return x|y;
 46     if(opt==3)return x^y;
 47 }
 48 
 49 Node merge(Node l,Node r){
 50     Node o;
 51     o.L0=o.L1=o.R0=o.R1=0;
 52     o.L0=(l.L0&r.L1)|((~l.L0)&r.L0);
 53     o.L1=(l.L1&r.L1)|((~l.L1)&r.L0);
 54     o.R0=(r.R0&l.R1)|((~r.R0)&l.R0);
 55     o.R1=(r.R1&l.R1)|((~r.R1)&l.R0);
 56     return o;
 57 }
 58 
 59 void build(int o,int l,int r){
 60     if(r==l){
 61         v[o].L0=v[o].R0=opr(0,opt[rak[l]],val[rak[l]]);
 62         v[o].L1=v[o].R1=opr(-1,opt[rak[l]],val[rak[l]]);
 63     }else{
 64         int mid=l+r>>1;
 65         build(lch,l,mid),build(rch,mid+1,r);
 66         v[o]=merge(v[lch],v[rch]);
 67     }
 68 }
 69 
 70 void update(int o,int l,int r,int x){
 71     if(r==l){
 72         v[o].L0=v[o].R0=opr(0,opt[rak[l]],val[rak[l]]);
 73         v[o].L1=v[o].R1=opr(-1,opt[rak[l]],val[rak[l]]);
 74     }else{
 75         int mid=l+r>>1;
 76         if(x<=mid)update(lch,l,mid,x);
 77         else update(rch,mid+1,r,x);
 78         v[o]=merge(v[lch],v[rch]);
 79     }
 80 }
 81 
 82 Node query(int o,int l,int r,int x,int y){
 83     if(l>=x&&r<=y)return v[o];
 84     else{
 85         int mid=l+r>>1,pd=false;
 86         Node ans;
 87         if(x<=mid)ans=query(lch,l,mid,x,y),pd=true;
 88         if(y>mid){
 89             if(pd)ans=merge(ans,query(rch,mid+1,r,x,y));
 90             else ans=query(rch,mid+1,r,x,y);
 91         }
 92         return ans;
 93     }
 94 }
 95 
 96 Node solve(int x,int y){
 97     int cnt1=0,cnt2=0;
 98     while(tp[x]!=tp[y]){
 99         if(dep[tp[x]]>dep[tp[y]]){
100             ans1[++cnt1]=query(1,1,n,tid[tp[x]],tid[x]);
101             x=fa[tp[x]];
102         }
103         else{
104             ans2[++cnt2]=query(1,1,n,tid[tp[y]],tid[y]);
105             y=fa[tp[y]];
106         }
107     }
108     if(dep[x]<dep[y])
109         ans2[++cnt2]=query(1,1,n,tid[x],tid[y]);
110     else
111         ans1[++cnt1]=query(1,1,n,tid[y],tid[x]);
112     for(int i=1;i<=cnt1;i++)
113         swap(ans1[i].L0,ans1[i].R0),swap(ans1[i].L1,ans1[i].R1);
114     Node sum; 
115     if(cnt1)sum=ans1[1];
116     else sum=ans2[cnt2];
117     for(int i=2;i<=cnt1;i++)sum=merge(sum,ans1[i]);
118     if(cnt1&&cnt2)sum=merge(sum,ans2[cnt2]);
119     for(int i=cnt2-1;i>=1;i--)sum=merge(sum,ans2[i]);
120     return sum;
121 }
122 
123 int main(){
124     scanf("%d%d%d",&n,&m,&k);
125     for(int i=1;i<=n;i++)
126         scanf("%d%llu",opt+i,val+i);
127     for(int i=1;i<n;i++){
128         scanf("%d%d",&x,&y);
129         add_edge(x,y);
130         add_edge(y,x);
131     }
132     dfs1(1,-1,0),dfs2(1,1);
133     build(1,1,n);
134     for(int i=1;i<=m;i++){
135         scanf("%d%d%d%llu",&ot,&x,&y,&z);
136         if(ot==1){
137             Node a=solve(x,y);
138             unsigned LL ans=0;
139             for(int j=63;j>=0;j--){
140                 if(a.L0&(1ULL<<j))ans+=1ULL<<j;
141                 else if(a.L1&(1ULL<<j)&&(1ULL<<j)<=z)
142                     ans+=1ULL<<j,z-=1ULL<<j;
143             }
144             printf("%llu
",ans);
145         }
146         if(ot==2){
147             opt[x]=y,val[x]=z;
148             update(1,1,n,tid[x]);
149         }
150     }
151 }

可怕！！