T1 签到题
结论题，找到规律就会做
规律是每个点的度数$\mod$颜色种数，如果不是$0$则贡献一个答案
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 #define out(x) cout<<#x<<":"<<x<<endl
6 #define fuck cout<<"fuck"<<endl
7 inline int read(){
8 int x=0,f=1;char ch=getchar();
9 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
11 }inline void write(int x,char opt='\n'){
12 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
13 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
14 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
15 }using namespace AE86;
16 const int NN=1e6+5;
17 int n,m,k,c,deg[NN],ans;
18 namespace WSN{
19 inline short main(){
20 // freopen("in.in","r",stdin); freopen("bao.out","w",stdout);
21 freopen("qiandao.in","r",stdin);
22 freopen("qiandao.out","w",stdout);
23 n=read(); m=read(); k=read(); c=read();
24 if(c==1) return puts("0"),0;
25 for(int i=1;i<=k;i++){
26 int u=read(),v=read()+n;
27 ++deg[u]; ++deg[v];
28 }
29 for(int i=1;i<=n+m;i++){
30 if(deg[i]%c!=0){
31 ++ans;
32 }
33 } write(ans);
34 return 0;
35 }
36 }
37 signed main(){return WSN::main();}
View Code
T2 M弟娃
树剖+线段树，每次判断两个点的$lca$是否为其中一个点，如果不是就将两个点的子树内加一
否则找到$lca$到另一个点的链上的那个儿子，分别操作：全局加一，儿子的子树减一，另一个点的子树加一
1 #include<bits/stdc++.h>
2 using namespace std;
3 namespace AE86{
4 #define out(x) cout<<"x="<<x<<endl
5 #define fuck cout<<"fuck"<<endl
6 inline int read(){
7 int x=0,f=1;char ch=getchar();
8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
9 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
10 }inline void write(int x,char opt='\n'){
11 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
12 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
13 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
14 }using namespace AE86;
15 const int NN=3e5+1;
16 int n,m;
17 struct SNOW{int to,next;}e[NN<<1]; int head[NN],rp;
18 inline void add(int x,int y){e[++rp]=(SNOW){y,head[x]};head[x]=rp;}
19 struct SNOWtree{
20 #define lid (id<<1)
21 #define rid (id<<1|1)
22 #define mid ((l+r)>>1)
23 int mx[NN<<2],laz[NN<<2];
24 inline void pushdown(int id){
25 laz[lid]+=laz[id];laz[rid]+=laz[id];
26 mx[lid]+=laz[id];mx[rid]+=laz[id];
27 laz[id]=0;
28 }
29 inline void update(int id,int l,int r,int ql,int qr,int v){
30 if(ql<=l&&r<=qr) return mx[id]+=v,laz[id]+=v,void();
31 if(l!=r&&laz[id]!=0) pushdown(id);
32 if(ql<=mid) update(lid,l,mid,ql,qr,v);
33 if(qr>mid) update(rid,mid+1,r,ql,qr,v);
34 if(l!=r) mx[id]=max(mx[lid],mx[rid]);
35 }
36 #undef mid
37 }tr;
38 namespace tree_division{
39 int dfn[NN],rk[NN],son[NN],top[NN],fa[NN],dep[NN],siz[NN],cnt;
40 inline void dfs1(int f,int x){
41 dep[x]=dep[f]+1; fa[x]=f; siz[x]=1;
42 for(int i=head[x];i;i=e[i].next){
43 int y=e[i].to; if(y==f) continue;
44 dfs1(x,y); siz[x]+=siz[y];
45 if(siz[son[x]]<siz[y]) son[x]=y;
46 }
47 }
48 inline void dfs2(int x,int t){
49 top[x]=t; dfn[x]=++cnt; rk[cnt]=x;
50 if(son[x]) dfs2(son[x],t);
51 for(int i=head[x];i;i=e[i].next){
52 int y=e[i].to;
53 if(y!=fa[x] && y!=son[x]) dfs2(y,y);
54 }
55 }
56 inline int LCA(int x,int y){
57 while(top[x]!=top[y]){
58 if(dep[top[x]]<dep[top[y]]) swap(x,y);
59 x=fa[top[x]];
60 }if(dfn[x]>dfn[y]) swap(x,y);
61 return x;
62 }
63 inline int find(int x,int y){
64 while(top[y]!=top[x]){
65 if(fa[top[y]]==x) return top[y];
66 y=fa[top[y]];
67 } return son[x];
68 }
69 }using namespace tree_division;
70
71 namespace WSN{
72 inline short main(){
73 freopen("magic.in","r",stdin);
74 freopen("magic.out","w",stdout);
75 n=read(); m=read();
76 if(n==1){
77 for(int i=1;i<=m;i++) printf("%lld\n",i);
78 return 0;
79 }
80 for(int i=1,u,v;i<n;i++)
81 u=read(),v=read(),add(u,v),add(v,u);
82 dfs1(0,1); dfs2(1,1); int x,y,lca;
83 while(m--){
84 x=read(),y=read();
85 if(x==y){
86 tr.update(1,1,n,1,n,1);write(tr.mx[1]);
87 continue;
88 }
89 lca=LCA(x,y);
90 if(lca!=x&&lca!=y){
91 tr.update(1,1,n,dfn[x],dfn[x]+siz[x]-1,1);
92 tr.update(1,1,n,dfn[y],dfn[y]+siz[y]-1,1);
93 write(tr.mx[1]);
94 continue;
95 }
96 if(lca==x||lca==y){
97 if(dfn[x]>dfn[y]) swap(x,y);
98 tr.update(1,1,n,1,n,1);
99 int sn=find(x,y);
100 tr.update(1,1,n,dfn[sn],dfn[sn]+siz[sn]-1,-1);
101 tr.update(1,1,n,dfn[y],dfn[y]+siz[y]-1,1);
102 write(tr.mx[1]);
103 }
104 }
105 return 0;
106 }
107 }
108 signed main(){return WSN::main();}
View Code
T3 变异大老鼠
这题比较容易打挂，而且是要么$100$要么$0$的那种
建树很容易看出，跑个最短路就行
反正我是被$dp$卡死了，调了$n$年没调出来，这一方面还是太弱
最后打的爆搜也是没调出来
设$f[u][k]$表示以$u$为根的子树中用了$k$个警察来抓住杨吞天的最大概率
那么背包合并的时候$f[x][j]=\max (f[x][l]+f[y][j-l] \times (\frac {1}{deg[x]}))$
累加贡献的时候$f[x][j]=\max (f[x][j-l]*(1-p[x][l])+p[x][l])$
关于枚举的时候需要倒序枚举，状态的更新不能用已知更新未知，会造成冲突
需要恶补树形$dp$和书上背包，记下了
1 #include<bits/stdc++.h>
2 using namespace std;
3 namespace AE86{
4 #define out(x) cout<<"x="<<x<<endl
5 #define fuck cout<<"fuck"<<endl
6 inline int read(){
7 int x=0,f=1;char ch=getchar();
8 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
9 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
10 }inline void write(int x,char opt='\n'){
11 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
12 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
13 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
14 }using namespace AE86;
15 const int MM=3e4+5,NN=305;
16 int n,m,k,deg[NN];
17 struct SNOW{int to,val,next;}e[MM<<1];int head[NN],rp;
18 inline void add(int x,int y,int z){
19 e[++rp]=(SNOW){y,z,head[x]};head[x]=rp;
20 e[++rp]=(SNOW){x,z,head[y]};head[y]=rp;
21 }
22 struct node{
23 int id,data;
24 friend bool operator<(node a,node b){
25 return a.data>b.data;
26 }
27 };priority_queue<node> Q;
28 int dis[NN];bool vis[NN];
29 inline void dij(){
30 int x,y; memset(dis,0x3f,sizeof(dis));
31 dis[1]=0; Q.push((node){1,0});
32 while(!Q.empty()){
33 x=Q.top().id,y=Q.top().data; Q.pop();
34 if(!vis[x]){ vis[x]=1;
35 for(int i=head[x];i;i=e[i].next)
36 if(dis[e[i].to]>dis[x]+e[i].val)
37 Q.push((node){e[i].to,dis[e[i].to]=dis[x]+e[i].val});
38 }
39 }
40 }
41 vector<int> g[NN];
42 inline void build(int f,int x,int d){
43 if(vis[x]) return;
44 if(dis[x]!=d) return;
45 vis[x]=1; g[f].push_back(x); ++deg[f];
46 for(int i=head[x];i;i=e[i].next){
47 int y=e[i].to;build(x,y,d+e[i].val);
48 }
49 }
50 double c[NN][NN];
51 double dp[NN][NN];
52 inline void dfs(int f,int x){
53 for(int i=0;i<g[x].size();i++){
54 int y=g[x][i]; dfs(x,y);
55 for(int j=k;j;--j){
56 for(int l=1;l<=j;l++){
57 dp[x][j]=max(dp[x][j],(1.0/deg[x])*dp[y][l]+dp[x][j-l]);
58 }
59 }
60 }
61 for(int j=k;j;--j){
62 for(int l=1;l<=j;l++){
63 dp[x][j]=max(dp[x][j],c[x][l]+(1.0-c[x][l])*dp[x][j-l]);
64 }
65 }
66 }
67 namespace WSN{
68 inline short main(){
69 // freopen("in.in","r",stdin);freopen("bao.out","w",stdout);
70 freopen("arrest.in","r",stdin);
71 freopen("arrest.out","w",stdout);
72 n=read(); m=read(); k=read();
73 for(int i=1,u,v,w;i<=m;i++){
74 u=read(),v=read(),w=read();
75 add(u,v,w);
76 } dij();
77 memset(vis,0,sizeof(vis));
78 build(0,1,0);
79 for(int i=1;i<=n;i++)
80 for(int j=1;j<=k;j++)
81 scanf("%lf",&c[i][j]);
82 dfs(0,1);
83 printf("%.6lf\n",dp[1][k]);
84 return 0;
85 }
86 }
87 signed main(){return WSN::main();}
View Code
T4 朝鲜时蔬
没看到任何关于朝鲜时蔬的信息，就一道纯打表加推式子的分类讨论题
这段不知道为啥老碰见测试点分治的题，就比较没意思
题目翻译：
从$n$个数里面选择$m$个构成的中集合，
要从这些中集合里面找 能除尽中集合总和的$k$个数字的总和，
以所有 可能的$k$个数字的小小集合 合在一起称为小集合，
找到小集合里面包含小小集合最多的那个个数，
最后叫你找到 小集合里面的小小集合的个数正好等于最大值 的中集合的个数
可能你更看不懂了，没事，真看不懂就看这个
没必要粘贴其实，只是为了偷税气氛，真正要理解怎么做也不是没有$pdf$，上面说的解法还是很详细的
不过比较烦的是它又有特判又有推式子，这种确实没啥大意义，给一个真正的纯推式子的题也行
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 #define out(x) cout<<"x="<<x<<endl
6 #define fuck cout<<"fuck"<<endl
7 inline int read(){
8 int x=0,f=1;char ch=getchar();
9 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
11 }inline void write(int x,char opt='\n'){
12 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
13 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
14 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
15 }using namespace AE86;
16 const int mod=1e9+7;
17 int n,m,k,v2,v12,v6,v4,v3;
18 inline int ksm(int a,int b,int ans=1){
19 int c=mod;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;
20 return ans;
21 }
22 inline int pws(int n){
23 return (n%mod)*((n+1)%mod)%mod*((2*n+1)%mod)%mod*v6%mod;
24 }
25 inline int sig(int l,int r){
26 return ((l+r)%mod)*((r-l+1)%mod)%mod*v2%mod;
27 }
28 namespace WSN{
29 inline short main(){
30 freopen("vegetable.in","r",stdin);
31 freopen("vegetable.out","w",stdout);
32 n=read(); m=read(); k=read(); v2=ksm(2,mod-2),v12=ksm(12,mod-2),v6=ksm(6,mod-2),v4=ksm(4,mod-2),v3=ksm(3,mod-2);
33 if(m==1&&k==1) n%=mod,cout<<n<<endl;
34 if(m==2&&k==2) n%=mod,cout<<n*(n-1)%mod*ksm(2,mod-2)%mod<<endl;
35 if(m==3&&k==3) n%=mod,cout<<n*(n-1)%mod*(n-2)%mod*ksm(6,mod-2)%mod<<endl;
36 if(m==4&&k==4) n%=mod,cout<<n*(n-1)%mod*(n-2)%mod*(n-3)%mod*ksm(24,mod-2)%mod<<endl;
37 if(m==2&&k==1){
38 int l=1,r,ans=0;
39 while(l<=n){
40 r=min(n/(n/l),n);
41 (ans+=(n/l)%mod*(r-l+1)%mod)%=mod;
42 l=r+1;
43 } write((ans%mod-n%mod+mod)%mod);
44 }
45 if(m==3&&k==1) cout<<(n/3)%mod<<endl;
46 if(m==3&&k==2){
47 int l=1,r,ans=0;
48 while(l<=n){
49 r=min(n/(n/l),n);
50 (ans+=(n/l)%mod*(((l+r-2)%mod)*((r-l+1)%mod)%mod*v2%mod*v2%mod-(r/2-(l-1)/2)%mod*v2%mod+mod)%mod)%=mod;
51 l=r+1;
52 } write(ans);
53 }
54 if(m==4&&k==1){
55 if(n==4||n==5) cout<<1<<endl;
56 else cout<<((n/6)%mod+(n/9)%mod+(n/10)%mod+(n/12)%mod+(n/15)%mod+(n/21)%mod)%mod<<endl;
57 }
58 if(m==4&&k==2){
59 if(n==4||n==5||n==6) cout<<1<<endl;
60 else if(n==7) cout<<3<<endl;
61 else if(n==8) cout<<6<<endl;
62 else if(n==9) cout<<9<<endl;
63 else if(n==10) cout<<10<<endl;
64 else cout<<((n/11)%mod+(n/29)%mod)%mod<<endl;
65 }
66 if(m==4&&k==3){
67 if(n==4) cout<<1<<endl;
68 else if(n==5) cout<<5<<endl;
69 else{
70 int l=1,r,ans=0;
71 while(l<=n){
72 int r=min(n/(n/l),n);
73 (ans+=(n/l)%mod*(((pws(r)-pws(l-1)+mod)%mod*v12%mod-sig(l,r)*v2%mod+mod)%mod+(5*(v12%mod)%mod)%mod*((r-l+1)%mod)%mod+((r/2-(l-1)/2)%mod)*v4%mod+((r/3-(l-1)/3)%mod)%mod*v3%mod)%mod)%=mod;
74 l=r+1;
75 } write(ans);
76 }
77 }
78 return 0;
79 }
80 }
81 signed main(){return WSN::main();}
别点开
稍稍总结一下这次为啥垫底
时间的分配不够好，思考的时间占用过长，导致暴力也没打完，正解也不好打，
然后就是太不自信，感觉想出来的都不是正解，也就不敢下手，其实要是敢打的话前几场也不至于很狼狈
还能把正解给注释掉，也是没谁了，这次的$T2$也是在稿纸上划出正解思路，然后感觉不会这么简单，害怕打到一半发现假了就死掉了
也是没敢打，暴力貌似更不会，就只打了菊花的。。。
以后还是要学着在打代码的同时思考正解，不要把两者的时间分化过偏