一直在期盼的联赛，真正来临时，却远不像我想象的样子。
有些事，真的不敢再想。
算法可以离线，时光却不能倒流。dfs可以回溯，现实却没有如果。
有些事，注定只能成为缺憾，抱恨终生。
不得不说今年Noip画风大变。
一是题目难度不循常规。D1难度如此之大，估计很多人都会很紧张。(比如我，下了场以为要有一群250+的，感觉自己要AFO了。)并且，D1T2居然比D1T3还难(D2也是如此)，把好多人给坑了(估计很多人都是死磕T2不放结果T3的76分暴力都没时间写了)。
PS：感觉题目难度应该是这样的，D1T1<D2T1<D1T3<D2T3<D2T2<D1T2
二是题目类型有所变化。今年的题基本没看见模板题，都是一些比较考察思维的题。
“综合来看，相比去年的题目偏重考察知识点，今年的题目在思维难度上有了明显的提升，可以有效的避免“东西学得多，分就高”的情况。在我看来，NOIP 虽然是一个普及形式的比赛，涉及知识点也有限，但并不意味着东西学得多就能 AK，竞赛竞赛，竞的是思维，赛的是心态，而不是仅仅拘泥于学习知识点的多少、学习时间的长短。让所有人都有收获，这可能是我心中比赛应有的样子吧。”——Sengxian
D1T2成功把自己坑了，考场上思路飘逸到树剖树分治和主席树，连一道树上差分都想不出来，都是因为思维能力太垃圾。还有D2T2(是怪我没学过Huffman树不知道用队列做的方法么……)。
联赛比的确实是思维和心态。
自己心态也比较差，考场上没能想出D1T2(放到平常考试估计想个1h也能想出来……)，暴力还写挂了，分数-=15；D1T3本来想到正解了，然而脑残的以为最后一维要开3，死活过不去(真是SB，我为什么不试试开2会怎样)；D2T1都能飘逸到Lucas定理，真是醉了；一直在叮嘱自己注意卡常，结果D2T2的make_heap()众给我贡献了2T，分数-=10；D2T3一眼看上去居然看成了搜索，明明不会剪枝还硬剪了半个小时，真是废了(放到平常考试估计很快就能看出状压的……)。
至于思维，向来是我的弱项。以前总是在学一些高端的东西，平衡树、主席树、树套树、CDQ……然而这些东西联赛都没能用上(平时最实用的主席树到了这儿也没能用上……)，反而学了这些东西之后做了好多模板题，对思维的锻炼就很少了。
联赛的6道题，D1T1和D2T1两道水题水过去了，D2T3一道状压傻逼题卡过去了，D1T2的树上差分、D1T3的期望DP和D2T2的队列都没想出来，写的暴力。
一场考试，6道题，我居然写了3个暴力，真是废了。幸亏暴力分给的足，要不然我早就AFO了。
现在离省选也没多少天了。唯一期盼的就是黑暗的高考生活赶快结束，WC和省选集训早日到来。
言归正传。
D1T1 玩具谜题
水题不解释。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m,a[maxn],x,d,cur=;
char s[maxn][];
int main(){
scanf("%d%d",&n,&m);
scanf("%d%s",&a[],s[]);
for(int i=n-;i;i--)scanf("%d%s",&a[i],s[i]);
while(m--){
scanf("%d%d",&x,&d);
if(x==a[cur])cur=(cur+d)%n;
else cur=(cur-d+n)%n;
}
printf(s[cur]);
return ;
}
D1T2 天天爱跑步
感觉这种题就该放在D2T3……
首先把每条路径(u,v)拆成两条路径(u,LCA)和(LCA,v)后分别考虑，然后对于每个x，考虑哪些点会对ans[x]产生贡献。
设每个点的深度为d，显然只有满足以下条件的u和v会对x的答案产生贡献：
(对u来说)d[u]-d[x]=w[x]
(对v来说)d[u]-d[LCA]+d[x]-d[LCA]=w[x]
把式子变形，得
d[u]=w[x]+d[x]
d[u]-2*d[LCA]=w[x]-d[x]
这样左边的值就不随x而改变，因为只有单点修改单点查询，用两个数组分别维护即可。
显然对于一个点x，只有(u,v)有一个在x的子树中的路径才能对ans[x]产生贡献。因此我们可以用树上差分，每个修改在u和v处进行，在LCA处撤销，在dfs到一个点之前记录答案，与dfs结束后的答案相减即为子树中的贡献之和。
可能是我写的比较渣，如果对LCA处有贡献的话会算重一次，需要手动去重。
LCA我写的是树剖，后来重写一遍Tarjan结果写挂了，算了反正树剖也挺快我就这么着吧……
细节问题：
a[]维护u的贡献，b[]维护v的贡献。
因为所有u的贡献都一样，直接压缩到cntu[]中表示这个点作为u的次数即可。
u[]是对LCA记录所有u(因为v的贡献只与u有关，所以不用记录v到底是谁)，v[]是对v记录所有u和LCA。
因为d[u]-2*d[LCA]可能是负的，因此加上一个2*n的偏移量。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=;
void dfs1(int);
void dfs2(int);
int LCA(int,int);
void dfs(int);
int prt[maxn],size[maxn],d[maxn],son[maxn],top[maxn];
vector<int>G[maxn],u[maxn];
struct pir{int u,lca;pir(int u,int lca):u(u),lca(lca){}};
vector<pir>v[maxn];
int n,m,w[maxn],cntu[maxn]={},ans[maxn]={},x,y;
int a[maxn]={},b[maxn<<]={};
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs1();dfs2();
for(int i=;i<=n;i++)scanf("%d",&w[i]);
while(m--){
scanf("%d%d",&x,&y);
int lca=LCA(x,y);
cntu[x]++;
u[lca].push_back(x);
v[y].push_back(pir(x,lca));
if(d[lca]+w[lca]==d[x])ans[lca]--;
}
dfs();
for(int i=;i<=n;i++)printf("%d ",ans[i]);
return ;
}
void dfs1(int x){
size[x]=;
for(int i=;i<(int)G[x].size();i++)if(G[x][i]!=prt[x]){
prt[G[x][i]]=x;
d[G[x][i]]=d[x]+;
dfs1(G[x][i]);
size[x]+=size[G[x][i]];
if(size[G[x][i]]>size[son[x]])son[x]=G[x][i];
}
}
void dfs2(int x){
if(x==son[prt[x]])top[x]=top[prt[x]];
else top[x]=x;
for(int i=;i<(int)G[x].size();i++)if(G[x][i]!=prt[x])dfs2(G[x][i]);
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]])swap(x,y);
x=prt[top[x]];
}
return d[x]<d[y]?x:y;
}
void dfs(int x){
ans[x]-=a[d[x]+w[x]]+b[w[x]-d[x]+(n<<)];
a[d[x]]+=cntu[x];
for(int i=;i<(int)v[x].size();i++)b[d[v[x][i].u]-(d[v[x][i].lca]<<)+(n<<)]++;
for(int i=;i<(int)G[x].size();i++)if(G[x][i]!=prt[x])dfs(G[x][i]);
ans[x]+=a[d[x]+w[x]]+b[w[x]-d[x]+(n<<)];
for(int i=;i<(int)u[x].size();i++){
a[d[u[x][i]]]--;
b[d[u[x][i]]-(d[x]<<)+(n<<)]--;
}
}
反思：
这题在考场上把我坑了0.5+h，当时什么都想，偏偏想不出来正解……加之前一天晚上睡得很不踏实，有点困，最终还是没想出来，打的60分暴力。结果有15分写挂了，真是废了……
反映出自己思维能力过弱，碰到稍微有点难度的题就想不出来。
一定要少刷模板题。
D1T3 换教室
期望DP模板题，我特么居然跪了……
设f[i][j][0/1]表示前i节课选了j节，0/1表示这节课选了没有的期望值。手玩各种转移就行了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=,maxv=;
int n,m,v,e,c[maxn],d[maxn],dis[maxn][maxn],x,y,z;
double p[maxn],f[maxn][maxn][],ans=1e50;
int main(){
memset(dis,,sizeof(dis));
scanf("%d%d%d%d",&n,&m,&v,&e);
m=min(n,m);
for(int i=;i<=v;i++)dis[i][i]=;
for(int i=;i<=n;i++)scanf("%d",&c[i]);
for(int i=;i<=n;i++)scanf("%d",&d[i]);
for(int i=;i<=n;i++)scanf("%lf",&p[i]);
while(e--){
scanf("%d%d%d",&x,&y,&z);
if(z<dis[x][y])dis[x][y]=dis[y][x]=z;
}
for(int k=;k<=v;k++)for(int i=;i<=v;i++)for(int j=;j<=v;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
for(int i=;i<=n;i++)for(int j=;j<=m;j++)f[i][j][]=f[i][j][]=1e50;
f[][][]=f[][][]=0.0;
for(int i=;i<=n;i++)for(int j=;j<=i&&j<=m;j++){
f[i][j][]=min(f[i-][j][]+(double)dis[c[i-]][c[i]],f[i-][j][]+p[i-]*dis[d[i-]][c[i]]+(1.0-p[i-])*dis[c[i-]][c[i]]);
if(j>)f[i][j][]=min(f[i-][j-][]+p[i]*dis[c[i-]][d[i]]+(1.0-p[i])*dis[c[i-]][c[i]],f[i-][j-][]+p[i-]*p[i]*dis[d[i-]][d[i]]+(1.0-p[i-])*p[i]*dis[c[i-]][d[i]]+p[i-]*(1.0-p[i])*dis[d[i-]][c[i]]+(1.0-p[i-])*(1.0-p[i])*dis[c[i-]][c[i]]);
else f[i][j][]=1e50;
}
for(int j=;j<=m;j++)ans=min(ans,min(f[n][j][],f[n][j][]));
printf("%.2lf",ans);
return ;
}
反思：
考场上想到了0/1，然后我脑残的以为应该分没选、选了成功和选了失败三种情况讨论，结果死调不出来，还是写的m<=2的76分暴力，这次倒是没写挂……
第一次好好写期望DP，被干穿了……自己弱不能怪社会……
D2T1 组合数问题
杨辉三角+二维前缀和随便水。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int q,n,m,p,c[maxn][maxn]={{}},a[maxn][maxn]={{}};
int main(){
scanf("%d%d",&q,&p);
c[][]=;
for(int i=;i<=;i++){
c[i][]=;
for(int j=;j<=i;j++){
c[i][j]=(c[i-][j]+c[i-][j-])%p;
if(!c[i][j])a[i][j]=;
}
}
for(int i=;i<=;i++){
a[i][]+=a[i-][];
a[][i]+=a[][i-];
for(int j=;j<=;j++)a[i][j]+=a[i-][j]+a[i][j-]-a[i-][j-];
}
while(q--){
scanf("%d%d",&n,&m);
printf("%d\n",a[n][m]);
}
return ;
}
反思：
考场上思路有点飘逸，结果费了10min……虽然费的时间不算多吧……
D2T2 蚯蚓
首先把所有蚯蚓变长改成切出来的蚯蚓变短，然后用三个队列分别维护原来的蚯蚓、砍出来的长的那段和短的那段，显然三个队列都是单调的，这样就可以线性了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<queue>
#define frt(que) ((que.empty()?-2147483647:que.front()))
using namespace std;
int n,m,t,u,v,q,o[],x,a,b,c;
queue<int>qa,qb,qc;
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
for(int i=;i<=n;i++)scanf("%d",&o[i]);
sort(o+,o+n+,greater<int>());
for(int i=;i<=n;i++)qa.push(o[i]);
for(int i=;i<=m;i++){
a=frt(qa);
b=frt(qb);
c=frt(qc);
if(a>=b&&a>=c)qa.pop();
else if(b>c){
a=b;
qb.pop();
}
else{
a=c;
qc.pop();
}
a+=q*(i-);
x=(long long)a*u/v;
qb.push(x-q*i);
qc.push(a-x-q*i);
if(i%t==)printf("%d ",a);
}
printf("\n");
for(int i=;!(qa.empty()&&qb.empty()&&qc.empty());i++){
a=frt(qa);
b=frt(qb);
c=frt(qc);
if(a>=b&&a>=c)qa.pop();
else if(b>c){
a=b;
qb.pop();
}
else{
a=c;
qc.pop();
}
a+=q*m;
if(i%t==)printf("%d ",a);
}
return ;
}
反思：
可能是没见过这种题吧，当时只想到了堆乱搞。也从一个侧面反映出自己做题太少，何况很多没见过这种题的也想到队列了呢……
D2T3 愤怒的小鸟
状压傻逼题。
话说各种被uoj hack，一开始eps设成1e-7被hack了，改成1e-8又被hack了，改成1e-9还被hack了，改成1e-10就A了，uoj这hack数据也太丧病了吧……
那个cnt_tbl是用来统计1数量卡边界用的，话说这玩意儿还挺好使……
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define popcnt(x) (cnt_tbl[(x)>>16]+cnt_tbl[(x)&65535])
using namespace std;
const int maxn=;
const double eps=1e-;
double dcmp(double);
double x[maxn],y[maxn];
int T,n,f[<<],cnt_tbl[]={};
int main(){
for(int i=;i<;i++)cnt_tbl[i]=cnt_tbl[i>>]+(i&);
scanf("%d",&T);
while(T--){
memset(f,,sizeof(f));
for(int s=;s<(<<);s++)f[s]=popcnt(s);
scanf("%d%*d",&n);
for(int i=;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
for(int i=;i<=n;i++)for(int j=;j<i;j++)if(dcmp(x[i]-x[j])){
double a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j])),b=(x[j]*x[j]*y[i]-x[i]*x[i]*y[j])/(x[i]*x[j]*(x[j]-x[i]));
if(dcmp(a)>-)continue;
int w=;
for(int k=;k<=n;k++)if(!dcmp(a*x[k]*x[k]+b*x[k]-y[k]))w|=(<<(k-));
for(int s=;s<(<<n);s++)f[s|w]=min(f[s|w],f[s]+);
}
printf("%d\n",f[(<<n)-]);
}
return ;
}
double dcmp(double x){
if(fabs(x)<eps)return ;
return x<0.0?-:;
}
反思：
第一眼看成了搜索，尝试剪枝浪费了很多时间。自己弱不能怪社会。
这次联赛，算是对自己一年多OI生涯的检验。结果自己却挂了，失误很多。(不知道这些到底该说是失误还是能力问题。)
别的，真的不想再说什么了。不敢再想。
很快就是WC，然后就是省选。结果如何，只能看自己了。
![[考试反思]0801NOIP模拟测试11](https://www.kunjuke.com/file/css/thumb/2.jpg/280-180.jpg)
