关键词：
T1 5483. 【清华集训2017模拟11.26】简单路径
T2 5484. 【清华集训2017模拟11.26】快乐树
T3 5485. 【清华集训2017模拟11.26】字符串
T1 结论题，结论很显然任意两条路径权异或后，会将两条路径的交的贡献删去。
然后用个桶存一下出现过的异或和，暴力判一下就可以了
code
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 #define fo(i,a,b) for(int i=a;i<=b;i++) 6 #define fd(i,a,b) for(int i=a;i>=b;i--) 7 #define fh(i,x) for(int i=head[x];i;i=next[i]) 8 typedef long long LL; 9 using namespace std; 10 inline int max(int x,int y) {return (x<y)?y:x;} 11 inline int min(int x,int y) {return (x<y)?x:y;} 12 inline int read() { 13 int x=0,f=1;char ch=getchar(); 14 while(ch<‘0‘||ch>‘9‘) f=(ch==‘-‘)?-1:f,ch=getchar(); 15 while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch-‘0‘),ch=getchar();return f*x; 16 } 17 const int N=1e3+100; 18 struct node { 19 int _lca,v; 20 node() {} 21 node(int a,int b):_lca(a),v(b) {} 22 }; 23 struct node1 { 24 int val,u,v,_lca; 25 node1() {} 26 node1(int _val,int _u,int _v,int l):val(_val),u(_u),v(_v),_lca(l){} 27 }to1[N*N],g[N*N]; 28 int to[N],w[N],next[N],head[N],tot,cnt,mx; 29 int tot1,next1[N*N],head1[N*N],fa[N],ans; 30 int dep[N],go[N][20],gw[N][20],n,x; 31 void add(int x,int y,int ww) {to[++tot]=y,w[tot]=ww,next[tot]=head[x],head[x]=tot;} 32 void add1(int val,int u,int v,int _lca) {to1[++tot1]=node1(val,u,v,_lca),next1[tot1]=head1[val],head1[val]=tot1;} 33 void dfs(int x) { 34 fh(i,x) { 35 dep[to[i]]=dep[x]+1,go[to[i]][0]=x,gw[to[i]][0]=w[i]; 36 dfs(to[i]); 37 } 38 } 39 void init_lca() { 40 dep[0]=1,dfs(0); 41 fo(i,1,17) fo(j,0,n-1) go[j][i]=go[go[j][i-1]][i-1],gw[j][i]=gw[j][i-1]^gw[go[j][i-1]][i-1]; 42 } 43 node lca(int a,int b) { 44 if(dep[a]>dep[b]) swap(a,b); 45 int f=dep[b]-dep[a],z=0; 46 fo(i,0,17) if(f&(1<<i)) z=z^gw[b][i],b=go[b][i]; 47 if(a==b) return node(a,z); 48 fo(i,0,17) { 49 if(go[a][i]!=go[b][i]) z^=gw[a][i]^gw[b][i],a=go[a][i],b=go[b][i]; 50 } 51 return node(go[a][0],z^gw[a][0]^gw[b][0]); 52 } 53 int main() { 54 n=read(); 55 fo(i,1,n-1) fa[i]=read(); 56 fo(i,1,n-1) x=read(),add(fa[i],i,x); 57 init_lca(); 58 fo(i,0,n-1) { 59 fo(j,i+1,n-1) { 60 node tmp=lca(i,j); 61 add1(tmp.v,i,j,tmp._lca); 62 g[++cnt]=node1(tmp.v,i,j,tmp._lca); 63 mx=max(mx,tmp.v); 64 } 65 } 66 fd(i,2048,mx) { 67 fo(j,1,cnt) { 68 if(!head1[i^g[j].val])continue; 69 else { 70 printf("%d ",i);return 0; 71 } 72 } 73 } 74 printf("%d ",max(mx,ans)); 75 return 0; 76 }
T2 算是一道dp题吧？有一个结论：“0”的影响范围一定是包括0的联通块。
先做一遍不考虑有“0”的dp，f[x]表示以x为子树的最优解。
然后g[x]表示x在“0”的联通块里，则g[x]=Σmax(f[son1],g[son1])
ans=max(f[0],g[0]);
Code
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 #define fo(i,a,b) for(int i=a;i<=b;i++) 6 #define fd(i,a,b) for(int i=a;i>=b;i--) 7 #define fh(i,x) for(int i=head[x];i;i=next[i]) 8 typedef long long LL; 9 using namespace std; 10 inline int max(int x,int y) {return (x<y)?y:x;} 11 inline int min(int x,int y) {return (x<y)?x:y;} 12 inline int read() { 13 int x=0,f=1;char ch=getchar(); 14 while(ch<‘0‘||ch>‘9‘) f=(ch==‘-‘)?-1:f,ch=getchar(); 15 while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch-‘0‘),ch=getchar();return f*x; 16 } 17 const int N=1e3+50; 18 int f[N],g[N],val[N],n,fa[N]; 19 int to[N],next[N],head[N],tot; 20 void add(int x,int y) {to[++tot]=y,next[tot]=head[x],head[x]=tot;} 21 void dfs(int x) { 22 f[x]=val[x]; 23 fh(i,x) dfs(to[i]); 24 fh(i,x) f[x]+=max(f[to[i]],0); 25 } 26 void dp(int x) { 27 fh(i,x) dp(to[i]); 28 fh(i,x) g[x]+=max(f[to[i]],g[to[i]]); 29 } 30 int main() { 31 n=read(); 32 fo(i,1,n-1) fa[i]=read(),add(fa[i],i); 33 fo(i,0,n-1) val[i]=read(); 34 dfs(0),dp(0); 35 printf("%d ",max(f[0],g[0])); 36 return 0; 37 }
T3
Code
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 #define fo(i,a,b) for(int i=a;i<=b;i++) 6 #define fd(i,a,b) for(int i=a;i>=b;i--) 7 #define fh(i,x) for(int i=head[x];i;i=next[i]) 8 typedef long long LL; 9 using namespace std; 10 inline int max(int x,int y) {return (x<y)?y:x;} 11 inline int min(int x,int y) {return (x<y)?x:y;} 12 inline int read() { 13 int x=0,f=1;char ch=getchar(); 14 while(ch<‘0‘||ch>‘9‘) f=(ch==‘-‘)?-1:f,ch=getchar(); 15 while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch-‘0‘),ch=getchar();return f*x; 16 } 17 const int N=1e5+50,inf=0x3f3f3f3f; 18 char s[N]; 19 int g[N][27],b[27],cnt[N][27],f[N][27],l,r,n,m,now; 20 int main() { 21 //freopen("c.in","r",stdin),freopen("c.out","w",stdout); 22 n=read(),m=read(); 23 scanf("%s",s+1); 24 fo(i,1,n) cnt[i][s[i]-‘a‘]++; 25 fo(j,0,25) fo(i,1,n) cnt[i][j]+=cnt[i-1][j]; 26 fo(j,1,26) g[0][j]=1; 27 fo(i,1,n) { 28 int t=s[i]-‘a‘; 29 fo(j,1,26) b[j]=n+1; 30 fo(j,1,26) { 31 if(cnt[i-1][t]-cnt[g[i-1][j]-1][t]==0) b[j+1]=min(b[j+1],g[i-1][j]); 32 else b[j]=min(b[j],g[i-1][j]); 33 } 34 b[1]=min(b[1],i); 35 fo(j,1,26) g[i][j]=b[j]; 36 } 37 fo(i,0,27) f[1][i]=1; 38 fo(i,2,n) { 39 fo(j,0,26) f[i][j]=n+1; 40 fo(j,0,26) { 41 fo(t,1,26) { 42 l=g[i][t],l--; 43 (t==1)?r=i:r=g[i][t-1]; 44 r--; 45 fo(st,0,j+1-t) f[i][j]=min(f[i][j],f[l][st]+1); 46 } 47 } 48 if(i<n) fo(j,1,26) f[i][j]=min(f[i][j],f[i][j-1]); 49 } 50 fd(j,26,0) { 51 if(f[n][j]<=m) now=j; 52 else break; 53 } 54 printf("%d ",m+now); 55 }
jzoj3539清华集训2014模拟数论高斯消元折射伤害(代码片段)
【清华集训2014模拟】折射伤害题面DescriptionInputOutputSampleInputSampleOutputDataConstraint解题思路Code题面Description在一个游戏中有n个英雄，初始时每个英雄受到数值为ai的伤害，每个英雄都有一个技能“折射”，即减少自己受... 查看详情
[loj#2327]「清华集训2017」福若格斯
[LOJ#2327]「清华集训2017」福若格斯试题描述小d是4xx9小游戏高手。有一天，小d发现了一个很经典的小游戏：跳青蛙。游戏在一个(5)个格子的棋盘上进行。在游戏的一开始，最左边的两个格子上各有一个向右的青蛙，最右边的两个... 查看详情
清华集训2017游记
Day0报到日火车上膜了一发附中大佬试机时感觉机房很热，头脑很不清醒晚上和cjl,xjt一起吃火锅，等了半天，感觉有毒Day1水落在酒店餐厅了，幸好赛场发水赛前松爷在群里发了一句GL&HF，非常慌开场看了三题，T1数学题，自己... 查看详情
[loj#2325]「清华集训2017」小y和恐怖的奴隶主
[LOJ#2325]「清华集训2017」小Y和恐怖的奴隶主试题描述"Afight?Countmein!"要打架了，算我一个。"Everyone,getinhere!"所有人，都过来！小Y是一个喜欢玩游戏的OIer。一天，她正在玩一款游戏，要打一个Boss。虽然这个Boss有(10^{100})点生命值，... 查看详情
*loj#2322.「清华集训2017」helloworld!
$n\leq50000$的树，有点权$\leq1e13$，$q\leq400000$次操作，有两种操作：从$s$跳到$t$每次$k$步，不到$k$步直接跳到$t$，每次把经过的点取根号；同样的跳法，对经过的点求和。首先一个数根号没几次就变0了因此可以大力修改。根号大力... 查看详情
「清华集训2017」无限之环(代码片段)
无限之WAhttps://www.luogu.org/problemnew/show/P4003本题如果知道是网络流的话，其实建图不算特别神奇，但是比较麻烦。数据范围过大，插头dp不能处理，而且是一个网格图，考虑网络流。先看是不是二分图？每个格子只会和相邻四个格... 查看详情
libreoj#2325.「清华集训2017」小y和恐怖的奴隶主（矩阵快速幂优化dp）
哇这题剧毒，卡了好久常数才过T_T 设$f(i,s)$为到第$i$轮攻击，怪物状态为$s$时对boss的期望伤害，$sum$为状态$s$所表示的怪物个数，得到朴素的DP方程$f(i,s)=sumfrac{1}{sum+1}*(f(i+1,s‘)+[s==s‘])$ 状态数只有$C_{8+3}^3=165$个，所... 查看详情
2017冬季24集训模拟-1.寻找幽灵
————————————————————————————————————————————题解把最短路处理出来然后做背包没有把head数组和all初始化qwq1#include<iostream>2#include<queue>3#include<set>4#include<cstdio... 查看详情
2017冬季24集训模拟-4.排座椅
————————————————————题解统计这一列或行放通道能隔开几个人，然后贪心输出没有排序QWQ1#include<iostream>2#include<queue>3#include<set>4#include<cstdio>5#include<cstring>6#include<vector>7#include&l 查看详情
2017冬季24集训模拟-3.耀西岛
——————————————————————————题解路径的长度是1-200000然后路径的条数有n*(n+1)/2根据鸽巢原理n*(n+1)/2> 200000就一定是YES所以复杂度只有n^21#include<iostream>2#include<queue>3#include<set>4#includ... 查看详情
清华集训2015v
#164.【清华集训2015】Vhttp://uoj.ac/problem/164 统计 描述 提交 自定义测试Picks博士观察完金星凌日后，设计了一个复杂的电阻器。为了简化题目，题目中的常数与现实世界有所不同。这个电阻器内有编号为 1∼n1&si... 查看详情
uoj#346.清华集训2017某位歌姬的故事动态规划
原文链接www.cnblogs.com/zhouzhendong/p/UOJ346.html题解首先按照$m_i$的大小排个序。如果某一个区间和一个m值比他小的区间有交，那么显然可以将这个区间控制的区域删除掉重合的那一段。如果一个区间被删没了，那么显然答案为0。在... 查看详情
luogup4002[清华集训2017]生成树计数(代码片段)
Link下文中的点指的是题目给的(n)个连通块。因为题目给的式子只与度数和点权相关，因此考虑Prufer序列。枚举每个点在Prufer序列中的出现次数，那么此时的贡献就是Prufer序列的个数乘上该生成树的价值。(ans=(n-2)!sumlimits_sumd_i=n-2p... 查看详情
2017.11.26计算机算法之分治与递归——汉诺塔
1、我的递归算法（纯粹的递归）#include<stdio.h>//当盘子数n等于15时，移动次数已经达到32767，运行时间已经达到15.540slonglongcount;voidhanoi(intn,chara,charb,charc)//借助C将A上的盘子全部移动到B{if(n==0)return;hanoi(n-1,a,c,b);printf("%c-->%c ",... 查看详情
2017.12.02noip提高组模拟赛a组
...IP提高组】模拟赛A组T13555【GDKOI2014模拟】树的直径T23542【清华集训2014】冒泡排序T33486【NOIP2013模拟联考10】道路改建(rebuild)T1树直径的一个性质，两棵树合并，形成新的树的直径的两个端点为原树中的四个端点之二。可以用反证... 查看详情
2014清华集训奇数国
3813:奇数国TimeLimit: 10Sec MemoryLimit: 256MBhttp://www.lydsy.com/JudgeOnline/problem.php?id=3813Description在一片美丽的大陆上有100000个国家，记为1到100000。这里经济发达，有数不尽的账房，并且每个国家有一个银行。某大公司的领... 查看详情
loj#6703-「清华集训2017」生成树计数(代码片段)
[sum_sumv_i=n-2prod(a_i^v_i+1*(v_i+1)^m/v_i!)*(sum(v_i+1)^m)]将(sum(v_i+1)^m)中的贡献分开算。我们有两个生成函数。第一个：[sum_ia^i+1*(v_i+1)^mx^i/i!]第二个：[sum_ia^i+1*(i+1)^2mx^i/i!]先将(proda)算到前面。令：[A(x)=sumx^i*(i+1)^m/i!B(x)=sumx^i*(i+1)^2m/i!]我们... 查看详情
清华集训2014玄学(代码片段)
清华集训2014玄学一列对象，常见的区间修改，单点询问，修改操作易于复合，但未必交换以及有逆。现在询问的时候忽视掉一段前缀与后缀，只留下中间一段连续的修改强制在线，(nleq10^5,qleq6*10^5)，保证修改操作不超过(10^5)。... 查看详情