T1:小豪的花园
Problem:
小豪有一个花园，里面有 n 个花棚，编号 1~n，每个花棚里有一定数量的花 ai。小豪花园的路十分神奇，可以使得任意两个花棚之间仅有一条最短路，即形成树结构，其中根节点是 1 号花棚。
现在小豪打算修缮一下他的花园，重新分配每个花棚里花的数量。为了能方便快捷地知道花园的情况，小豪现在需要你的帮助。具体地说，小豪共有 m 个操作。操作有三种：
1 u k 表示如果一个花棚在以 u 号花棚为根的子树中，那么小豪会把这个花棚花的数量模 k；
2 u x 表示小豪将 u 号花棚花的数量变成 x；
3 u v 表示小豪询问从 u 号花棚走到 v 号花棚总共能看到的花的数量。
你能帮助小豪吗?
Solution:
难解决的是操作 1，但可以发现在 u 的子树中不是每个数字都需要取模。
考虑一种做法：每次找出 u 的子树的最大值，检查是否需要取模，直到最大值小于要取模的值。那么对于任意一个数 x ，每次取模至少能减少一半，因此取模的次数至多O(log x)次，总的时间复杂度O((n + m) log n log x + m log
2 n) 。
Code:
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 inline void put(int x){
5 if(x>9) put(x/10);
6 putchar(x%10+48);
7 return ;
8 }
9 const int N=1e5+5,M=2e5+5,L=4e5+5;
10 int dep[N],fa[N],val[N],sze[N],son[N],pos[N],idx[N],top[N];
11 ll sum[L];
12 int mx[L],n,m,T;
13 struct Edge{
14 int to;
15 Edge *nxt;
16 }p[M],*lst[N],*P=p;
17 inline void addEdge(int x,int y){
18 (++P)->nxt=lst[x];
19 lst[x]=P;
20 P->to=y;
21 (++P)->nxt=lst[y];
22 lst[y]=P;
23 P->to=x;
24 return ;
25 }
26 inline void dfs1(int x){
27 dep[x]=dep[fa[x]]+1;
28 sze[x]=1;
29 for(Edge *e=lst[x];e;e=e->nxt){
30 int y=e->to;
31 if(y==fa[x]) continue;
32 fa[y]=x;
33 dfs1(y);
34 sze[x]+=sze[y];
35 if(sze[y]>sze[son[x]]) son[x]=y;
36 }
37 return ;
38 }
39 inline void dfs2(int x){
40 if(son[x]){
41 top[son[x]]=top[x];
42 pos[son[x]]=++T;
43 idx[T]=son[x];
44 dfs2(son[x]);
45 }
46 int y;
47 for(Edge *e=lst[x];e;e=e->nxt){
48 if(!top[y=e->to]){
49 top[y]=y;
50 pos[y]=++T;
51 idx[T]=y;
52 dfs2(y);
53 }
54 }
55 return ;
56 }
57 inline void init(){
58 dfs1(1);
59 top[1]=pos[1]=idx[1]=T=1;
60 dfs2(1);
61 return ;
62 }
63 template <class T>
64 inline T idMax(T x,T y){return val[x]>val[y]?x:y;}
65 inline void Uptdate(int s){
66 mx[s]=idMax(mx[s<<1],mx[s<<1|1]);
67 sum[s]=sum[s<<1]+sum[s<<1|1];
68 return ;
69 }
70 inline void Build(int s,int l,int r){
71 if(l==r) return (void)(mx[s]=idx[l],sum[s]=val[idx[l]]);
72 int mid=(l+r)>>1;
73 Build(s<<1,l,mid);
74 Build(s<<1|1,mid+1,r);
75 Uptdate(s);
76 return ;
77 }
78 inline void Modify(int s,int l,int r,int x,int v){
79 if(l==r) return (void)(sum[s]=v);
80 int mid=(l+r)>>1;
81 if(x<=mid) Modify(s<<1,l,mid,x,v);
82 else Modify(s<<1|1,mid+1,r,x,v);
83 Uptdate(s);
84 return ;
85 }
86 inline ll querySum(int s,int l,int r,int x,int y){
87 if(l==x&&r==y) return sum[s];
88 int mid=(l+r)>>1;
89 if(y<=mid) return querySum(s<<1,l,mid,x,y);
90 else if(x>mid) return querySum(s<<1|1,mid+1,r,x,y);
91 else return querySum(s<<1,l,mid,x,mid)+querySum(s<<1|1,mid+1,r,mid+1,y);
92 }
93 inline int queryMax(int s,int l,int r,int x,int y){
94 if(l==x&&r==y) return mx[s];
95 int mid=(l+r)>>1;
96 if(y<=mid) return queryMax(s<<1,l,mid,x,y);
97 else if(x>mid) return queryMax(s<<1|1,mid+1,r,x,y);
98 else return idMax(queryMax(s<<1,l,mid,x,mid),queryMax(s<<1|1,mid+1,r,mid+1,y));
99 }
100 inline ll pathQuery(int x,int y){
101 ll res=0;
102 while(top[x]!=top[y]){
103 if(dep[top[x]]<dep[top[y]]) swap(x,y);
104 res+=querySum(1,1,T,pos[top[x]],pos[x]);
105 x=fa[top[x]];
106 }
107 if(dep[x]<dep[y]) swap(x,y);
108 return res+querySum(1,1,T,pos[y],pos[x]);
109 }
110 int main(){
111 scanf("%d%d",&n,&m);
112 for(int i=1,u,v;i<n;++i){
113 scanf("%d%d",&u,&v);
114 addEdge(u,v);
115 }
116 for(int i=1;i<=n;++i) scanf("%d",&val[i]);
117 init();
118 Build(1,1,T);
119 int opt,u,v,w;
120 while(m--){
121 scanf("%d%d%d",&opt,&u,&v);
122 switch(opt){
123 case 1:while(w=queryMax(1,1,T,pos[u],pos[u]+sze[u]-1),val[w]>=v)
124 val[w]%=v,Modify(1,1,T,pos[w],val[w]);break;
125 case 2:val[u]=v;Modify(1,1,T,pos[u],val[u]);break;
126 case 3:put(pathQuery(u,v)),putchar('\n');break;
127 }
128 }
129 return 0;
130 }
T2:遗传病
Problem:
众所周知，近亲结婚的后代患遗传病的概率会大大增加。如果某一基因按常染色体隐性遗传方式，其子女就可能因为是突变纯合子而发病。因此，近亲婚配增加了某些常染色体隐性遗传疾病的发生风险。
现在有 n 个人，每个人都有一个遗传特征值 ai，设第 i 个人和 j 个人结婚，那么风险系数为 gcd(ai,aj)，法律规定只有风险系数为 1 时两个人才能结婚。
F 同学开了一个婚姻介绍所，这 n 个人可能会来登记，当然也有可能登记后取消，也有可能取消后再登记。F 同学的任务就是，求出当前所有登记的人中，有多少对人是可以结婚的。刚开始所有人都没有登记。
为出题需要，不考虑性别，基因突变和染色体变异等 QAQ。
Solution:
容易想到容斥，与该值互质的特征值个数即总的特征值个数-与该值的最大公约数是 2 的倍数的特征值个数-与该值的最大公约数是 3 的倍数的特征值个数-与该值的最大公约数是5 的倍数的特征值个数-...+与该值的最大公约数是 2×3 的倍数的特征值个数+与该值的最大公约数是 2×5 的倍数的特征值个数+...。
可以用一个数组 num[i]记录含有约数i 的特征值个数，对每个删去或加入的特征值质因数分解，O(2
互不相同的质因数个数) 暴力容斥即可。
根据特征值的数据范围，互不相同的质因数个数最多只有 8 个，实际情况下跑得飞快
Code:
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 const int maxn=210000;
5 const int maxm=510000;
6 int n,q,m,a[maxn],p[maxm];
7 int cnt,flag[maxm],prime[maxm];
8 vector<int> b[maxn];
9 int in[maxn],table[maxm];
10 ll res;
11 void init(){
12 for(int i=2;i<=m;i++){
13 if(!flag[i]) prime[++cnt]=i;
14 for(int j=1;j<=cnt&&i*prime[j]<=m;j++){
15 flag[i*prime[j]]=1;
16 p[i*prime[j]]=prime[j];
17 if(i%prime[j]==0) break;
18 }
19 }
20 for(int i=1;i<=n;i++){
21 int x=a[i];
22 while(x!=1){
23 int t=flag[x]?p[x]:x;
24 b[i].push_back(t);
25 while(x%t==0) x/=t;
26 }
27 }
28 }
29 inline void dfs(int x,int k,int mult,int f){
30 if(k==(b[x].size())){
31 res+=in[x]==1?table[mult]*in[x]*f:(table[mult]-1)*in[x]*f;
32 table[mult]+=in[x];
33 return ;
34 }
35 dfs(x,k+1,mult*b[x][k],-f);
36 dfs(x,k+1,mult,f);
37 }
38 int main(){
39 freopen("disease.in","r",stdin);
40 freopen("disease.out","w",stdout);
41 scanf("%d%d",&n,&q);
42 for(int i=1;i<=n;i++){
43 scanf("%d",&a[i]);
44 if(m<a[i]) m=a[i];
45 }
46 init();
47 fill(in+1,in+1+n,1);
48 while(q--){
49 int x;
50 scanf("%d",&x);
51 dfs(x,0,1,1);
52 in[x]=-in[x];
53 printf("%d\n",res);
54 }
55 return 0;
56 }
T3:道路
Problem:
我们看见了一个由 m 行 n 列的 1*1 的格子组成的矩阵，每个格子(i,j)有对应的高度 h[i][j]和初始的一个非负权值 v[i][j]。我们可以随便选择一个格子作为起点，然后在接下来的每一步当中，我们能且只能到达与当前格子有边相邻的四个格子中的高度不超过当前格子高度的格子，每当我们到达一个新格子（包括一开始选择的初始格子），我们就能得到该格子的权值分，然后该格子的权值就会等概率变成不比当前的权值大的一个非负权值。每一个格子在满足前面条件情况下，可以走任意多次。
我们希望得到一个最大的期望权值和路径，并给出这个最大的期望权值和。
Solution:
打表可以发现 f [i] = 2i ，可用数学归纳法证明。
Code:
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
5 const int N=1005,M=1e6+5;
6 int h[N][N],v[N][N],num[N][N],rin[M];
7 int dfn[M],low[M],stk[M],col[M],point[M],val[M];
8 ll f[M],unt[M],ans;
9 int n,m,G,C,top,tis;
10 bool inv[M];
11 struct Edge{
12 int to;
13 Edge *nxt;
14 };
15 struct Graph{
16 Edge p[M<<2],*lst[M],*P;
17 inline void Init(){
18 P=p;
19 }
20 inline void addEdge(int x,int y){
21 (++P)->nxt=lst[x];
22 lst[x]=P;
23 P->to=y;
24 }
25 }newG, oldG;
26 inline bool check(int x,int y){
27 return x>=1&&x<=n&&y>=1&&y<=m;
28 }
29 inline void Tarjan(int x){
30 dfn[x]=low[x]=++tis;
31 int y;
32 stk[++top]=x;
33 inv[x]=true;
34 for(Edge *e=oldG.lst[x];e;e=e->nxt){
35 if(!dfn[y=e->to]){
36 Tarjan(y);
37 if(low[x]>low[y]) low[x]=low[y];
38 }
39 else if(inv[y]){
40 if(low[x]>dfn[y]) low[x]=dfn[y];
41 }
42 }
43 if(dfn[x]==low[x]){
44 inv[x]=false;
45 col[x]=++C;
46 point[C]=1;
47 unt[C]=val[x];
48 while(y=stk[top--],y!=x){
49 inv[y]=false;
50 col[y]=C;
51 unt[C]+=val[y];
52 ++point[C];
53 }
54 }
55 }
56 int main(){
57 oldG.Init();
58 newG.Init();
59 scanf("%d%d",&n,&m);
60 for(int i=1;i<=n;++i){
61 for(int j=1;j<=m;++j){
62 scanf("%d",&h[i][j]);
63 }
64 }
65 for(int i=1;i<=n;++i){
66 for(int j=1;j<=m;++j){
67 scanf("%d",&v[i][j]);
68 }
69 }
70 for(int i=1;i<=n;++i){
71 for(int j=1;j<=m;++j){
72 num[i][j]=++G;
73 val[G]=v[i][j];
74 }
75 }
76 for(int i=1;i<=n;++i){
77 for(int j=1;j<=m;++j){
78 for(int k=0;k<4;++k){
79 int tx=i+dx[k],ty=j+dy[k];
80 if(check(tx,ty)&&h[tx][ty]<=h[i][j]){
81 oldG.addEdge(num[i][j],num[tx][ty]);
82 }
83 }
84 }
85 }
86 for(int i=1;i<=G;++i){
87 if(!dfn[i]) Tarjan(i);
88 }
89 for(int i=1;i<=C;++i){
90 if(point[i]>1) unt[i]=unt[i]<<1ll;
91 }
92 for(int i=1;i<=G;++i){
93 for(Edge *e=oldG.lst[i];e;e=e->nxt){
94 int y=e->to;
95 if(col[i]==col[y]) continue;
96 newG.addEdge(col[i],col[y]);
97 ++rin[col[y]];
98 }
99 }
100 for(int i=1;i<=C;++i){
101 if(!rin[i]){
102 stk[++top]=i;
103 f[i]=unt[i];
104 }
105 }
106 int x,y;
107 while(top){
108 x=stk[top--];
109 for(Edge *e=newG.lst[x];e;e=e->nxt){
110 if(!--rin[y=e->to]) stk[++top]=y;
111 if(f[y]<f[x]+unt[y]) f[y]=f[x]+unt[y];
112 }
113 }
114 for(int i=1;i<=C;++i){
115 if(ans<f[i]) ans=f[i];
116 }
117 cout<<ans<<endl;
118 return 0;
119 }