T1 辣鸡

首先吐嘈一下，这题的测试点就离谱，不说了，附上我65分代码：

震撼我，这不相邻的矩形咋这么多！！！

但是当时没有敢打，可惜可惜。。

然而这题正解也是暴力，所以就不说什么了，上代码

1 #include
2 #define int long long
3 using namespace std;
4 inline int read(){
5 int x=0,f=1; char ch=getchar();
6 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
7 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } 8 return x*f; 9 } 10 int n,wsn; 11 struct SNOW{int x1,y1,x2,y2;};SNOW s[100005]; 12 bool cmp(SNOW a,SNOW b){return a.x11) break;
24 if(min(s[i].x2,s[j].x2)-max(s[i].x1,s[j].x1)>=0){
25 if(s[j].y1-s[i].y2==1){
26 wsn+=(min(s[i].x2,s[j].x2)-max(s[i].x1,s[j].x1))*2;
27 if(s[i].x1!=s[j].x1) wsn++;
28 if(s[j].x2!=s[i].x2) wsn++;
29 }
30 if(s[i].y1-s[j].y2==1){
31 wsn+=(min(s[i].x2,s[j].x2)-max(s[i].x1,s[j].x1))*2;
32 if(s[i].x1!=s[j].x1) wsn++;
33 if(s[j].x2!=s[i].x2) wsn++;
34 }
35 }
36 if(min(s[i].y2,s[j].y2)-max(s[i].y1,s[j].y1)>=0){
37 if(s[j].x1-s[i].x2==1){
38 wsn+=(min(s[i].y2,s[j].y2)-max(s[i].y1,s[j].y1))*2;
39 if(s[i].y1!=s[j].y1) wsn++;
40 if(s[j].y2!=s[i].y2) wsn++;
41 }
42 if(s[i].x1-s[j].x2==1){
43 wsn+=(min(s[i].y2,s[j].y2)-max(s[i].y1,s[j].y1))*2;
44 if(s[i].y1!=s[j].y1) wsn++;
45 if(s[j].y2!=s[i].y2) wsn++;
46 }
47 }
48 if(s[j].x1-s[i].x2==1&&(s[j].y1-s[i].y2==1||s[i].y1-s[j].y2==1)) wsn++;
49 }
50 }
51 printf("%lld\n",wsn);
52 return 0;
53 }
54 }
55 signed main(){return WSN::main();}

T2 模板（线段树合并）

这题目暴力很好想注意一下细节就可以很好拿到30分了，然而我现在还没有学习线段树合并，就先贴上暴力代码了。

1 #include
2 using namespace std;
3 inline int read(){
4 int x=0,f=1; char ch=getchar();
5 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
6 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } 7 return x*f; 8 } 9 const int NN=1e5+10; 10 int n,m,q,fa[NN],k[NN]; 11 bool v[NN],typ[NN]; 12 vector co[NN];
13 struct SNOW{ int to,next;}; SNOW g[NN<<1]; int r[NN<<1],tot; 14 inline void add(int x,int y){g[++tot]=(SNOW){y,r[x]}; r[x]=tot;} 15 inline void dfs1(int x){ 16 v[x]=true; 17 for(int i=r[x];i;i=g[i].next) 18 if(!v[g[i].to]){ 19 fa[g[i].to]=x; 20 dfs1(g[i].to); 21 } 22 } 23 inline void dfs2(int x,int val){ 24 if(k[x]>0) co[x].push_back(val);
25 k[x]--;
26 if(!fa[x]) return;
27 dfs2(fa[x],val);
28 }
29 namespace WSN{
30 inline int main(){
31 n=read();
32 for(int i=1;i<n;i++){
33 int u=read(),v=read();
34 add(u,v); add(v,u);
35 }
36 dfs1(1);
37 for(int i=1;i<=n;i++) k[i]=read();
38 m=read();
39 for(int i=1;i<=m;i++){
40 int x=read(),c=read();
41 dfs2(x,c);
42 }
43 q=read();
44 for(int i=1;i<=q;i++){
45 memset(typ,false,sizeof(typ));
46 int x=read(),maxn=0,minn=0x3fffffff;
47 for(int j=0;j<co[x].size();j++){
48 typ[co[x][j]]=true;
49 maxn=max(co[x][j],maxn);
50 minn=min(co[x][j],minn);
51 }
52 int wsn=0;
53 for(int j=minn;j<=maxn;j++){
54 if(typ[j]) wsn++;
55 }
56 printf("%d\n",wsn);
57 }
58 return 0;
59 }
60 }
61 signed main(){return WSN::main();}

回来补坑，线段树以时间开，在启发式合并的时候判断时间和颜色的先后位置，然后在合并。

1 #include
2 #define mid ((l+r)>>1)
3 using namespace std;
4 inline int read(){
5 int x=0,f=1; char ch=getchar();
6 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
7 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } 8 return x*f; 9 10 } 11 12 const int NN=1e5+10; 13 int n,m,q,k[NN]; 14 vector vc[NN];
15 int rt[NN];
16 int son[NN],ans[NN],siz[NN];
17
18 struct snow{int x,c;}; snow wk[NN]; int dis[NN],m_new;
19 struct SNOW{ int to,next;}; SNOW e[NN<<1]; int head[NN],tot; 20 inline void add(int x,int y){e[++tot]=(SNOW){y,head[x]}; head[x]=tot;} 21 22 inline void discrete(){ 23 sort(dis+1,dis+m+1); m_new=unique(dis+1,dis+m+1)-dis-1; 24 for(int i=1;i<=m;i++){ 25 wk[i].c=lower_bound(dis+1,dis+m_new+1,wk[i].c)-dis; 26 vc[wk[i].x].push_back(i); 27 } 28 } 29 30 inline void init(){ 31 n=read(); 32 for(int i=1;it){
65 insert(rt[x],1,m,t,1,1);
66 insert(rt[x],1,m,pre[co],0,1);
67 pre[co]=t; return;
68 }
69 }
70
71 inline void merge(int x,int l,int r,int p){
72 if(!x) return;
73 if(l==r&&sum[x]){ gather(p,l,wk[l].c); return; }
74 merge(ls[x],l,mid,p);
75 merge(rs[x],mid+1,r,p);
76 }
77
78 inline int query(int x,int l,int r,int res){
79 if(!x||!res) return 0;
80 if(l==r) return kin[x];
81 int an=0;
82 if(ls[x]&&ressiz[son[x]]) son[x]=y;
102 }
103 }
104
105 inline void dfs(int f,int x){
106 for(int i=head[x];i;i=e[i].next){
107 int y=e[i].to;
108 if(y==f||y==son[x]) continue;
109 dfs(x,y); tr.clear();
110 }
111 if(son[x]) dfs(x,son[x]);
112 rt[x]=rt[son[x]];
113 for(int i=0;i<vc[x].size();i++)
114 tr.gather(x,vc[x][i],wk[vc[x][i]].c);
115 for(int i=head[x];i;i=e[i].next){
116 int y=e[i].to;
117 if(y==f||y==son[x]) continue;
118 tr.merge(rt[y],1,m,x);
119 }
120 ans[x]=tr.query(rt[x],1,m,k[x]);
121 }
122
123 namespace WSN{
124 inline int main(){
125 init();
126 find_heavyson(0,1);
127 dfs(0,1);
128 q=read();
129 for(int i=1;i<=q;i++) printf("%d\n",ans[read()]);
130 return 0;
131 }
132 }
133 signed main(){return WSN::main();}

T3 大佬（概率与期望）

首先，这题分数取莫，想到用费马小定理求逆元

然后就是推柿子：

$ans=\frac{\sum\limits_{i=1}^{m}g(i)*w[i]}{m^k}*(n-k+1)$

此柿子何来？

$g[x]=x^k-(x-1)^k$

每道题有x种选择，要除掉不合法的状态，即最大难度不是x，根据容斥可得。

然而仔细推一下可以发现他的每一个项都是由递推得到的，则代码：

T4 宝藏（状压dp）

看到这数据，是不是想状压，而且二维数组求距离还特别方便，现在这么一想，感觉还是比较水的

代码表现的非常明白，是一个按层推的思想。这样dp才可以找到dian的加和值

1 #include
2 using namespace std;
3 inline int read(){
4 int x=0,f=1; char ch=getchar();
5 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
6 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } 7 return x*f; 8 } 9 int n,m,k,wsn=0x3fffffff,f[13][1<<12],dis[13][13],g[13][13]; 10 inline void dfs(int st,int x){ 11 for(int i=1;i<=n;i++){ 12 if(!(x&(1<f[st][x]+dis[st][i]*g[i][j]){
17 f[st][x|(1<<j-1)]=f[st][x]+dis[st][i]*g[i][j];
18 dis[st][j]=dis[st][i]+1;
19 dfs(st,x|(1<<j-1));
20 }
21 }
22 }
23 }
24 namespace WSN{
25 inline int main(){
26 memset(f,0x3f,sizeof(f));
27 for(int i=0;i<=12;i++)
28 for(int j=0;j<=12;j++) g[i][j]=999999999;
29 n=read(),m=read();
30 for(int i=1;i<=m;i++){
31 int x=read(),y=read(),z=read();
32 if(z<g[x][y]) g[x][y]=g[y][x]=z;
33 }
34 for(int i=1;i<=n;i++){
35 f[i][1<<i-1]=0;
36 dis[i][i]=1;
37 dfs(i,1<<i-1);
38 wsn=min(wsn,f[i][(1<<n)-1]);
39 }
40 printf("%d\n",wsn);
41 return 0;
42 }
43 }
44 signed main(){return WSN::main();}