POI21填坑计划
[Upd 12.24]：因为校内集训先坑在这里好了。。感觉剩下的题目好难啃。。
开新坑辣！先口胡一波再写好了。。
现在完成了：
15
[Couriers]：无脑主席树，当然也可以莫队
[Hotel]：无脑DP+乱搞。
[Salad Bar]：O(n log n)的感觉比较无脑。。不知道有没有O(n)的。。
[Around the world]：每次询问任意固定一个起点，然后O(n)求出每个点往左往右走到这个起点的步数和最后一步的距离，最后再看最后一步的距离能否两步缩成一步。O(nm)
[Bricks]：差不多大于1/2就不能放？感觉好想好证好构造。因为固定首尾所以多判几种情况乱搞搞就好了？
[Card]：拿棵线段树随便维护一下就好？反正一段区间只会有四种情况
[FarmCraft]：树形DP+SB贪心？
[Little Bird]：首先一段区间所包含的劳累值肯定是连续的。然后就每个值按高度维护一个单调队列以及维护一下这段区间内的劳累值区间左右端点。然后每次删除一个点就只要在单调队列里面删除。算当前劳累值就只要从最小劳累值和次小劳累值转移就好了。
[Solar Panels]：分成两种情况，第一种答案小于sqrt(1e9)，直接枚举判断就好。第二种n/gcd或者m/gcd小于sqrt(1e9)，那么设n/gcd=k，则gcd肯定等于[maxn/k]，然后按照m范围判断即可。因为不一定是n碰到上界所以m再来一遍即可。（因为两个都没有碰到上界的话gcd是可以加一的）复杂度O(sqrt(1e9)*t)
按照BZOJ上面的AC人数，貌似水题全都写完了。。好虚啊。。
[Solar Lamps]：把一个角度放大CF有一个题也用到过，其它部分直接上个树套树就好了？特判掉范围是一条线的情况就好。
[Rally]：之前想了一个做法发现是在瞎BB。堆+拓扑排序。。主要是一直在怎么找必经点而不是在维护答案上面想所以并不会做，而且答案是维护的一个割集的而不是维护整张图。智商是硬伤。。
[SuperComputer]：还是不会。。听说ans=max(i+[sum[i]/k])= =证明在这里。虽然想过类似结论但是还是没想到这个东西= =太弱= =。然后就可以斜率优化了。
[Criminals]：之前一直看漏了一个条件发现是神题不会做= =后来发现直接扫一遍求出每个点往两个方向的最短可以匹配的序列是在哪个位置就好了。。
[Ant colony]：之前一直没看懂题。。原来是每个叶子节点都会有。。只要处理出每个叶子节点的被除数是多少然后对询问还有这东西排序扫一遍就好了。。
[Freight]：找到一个并没很大用的性质，往那方面想了一个从后往前的贪心，但是明显前面的发车状态会对后面的贪心策略造成影响，于是还没写就弃疗了。后来找到另外一个比较显然的性质就是如果当前在回程的话就应该把所有在T的点全部回到S。因为这样最多会把后面的车推迟s分钟。但是如果这s辆车扣在这里等最后才放的话也要推迟s分钟。于是肯定是如果放车就都放掉比较好。于是可以设t[i]代表第i辆车作为那次回程的最后一辆车回到S的时间是多少。则我们从j<i转移。分两种情况：t[j]+i-j-1<=T[i]或者大于。首先t[j]肯定是单调递增的所以t[j]-j肯定单调不减，并且分界线肯定也是单调不减的。第一种情况t[i]=min(T[i]+s*2+i-j-1)，直接取最后一个即可。第二种情况t[i]=min(t[j]+(i-j-1+s)*2)，所以维护一棵线段树查询区间最小值即可。至于时间重合的情况直接预处理T[i]=max(T[i],T[i-1]+1)
[Snake]：感觉像是某种神奇的大讨论。。不会啊。。
[Tourism]：跪Claris神脑洞。
UOJ#132 小园丁与老司机
由于代码能力拙计，一直很想写这题，于是学了上下界网络流之后就开始写这题了。
感觉理清了思路没有想象中难写。但是感觉要在考场上面写出来确实比较厉害。。
首先第一问DP做法显然。第二问下界最小流有特殊的建图方式然后跑两遍Dinic就好了。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 50050
#define M 2000050
#define INF 0x3f7f7f7f
int sg[N],wz[N][2],dir[N][3],fi[N],c[M*2][3],Trs[N];
int ss=1,st,n,m,S=N-1,T=N-2,_S=N-3,_T=N-4,ans;
int Ans[N],cur[N],Wz[N][2],sign[N],ma[N],la[N],h[N];
queue <int> li;bool b[N],flag[N],vis[N];
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline void Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=0;fi[y]=ss;
}
inline bool cmp0(int x,int y)
{return wz[x][0]<wz[y][0]||(wz[x][0]==wz[y][0]&&wz[x][1]<wz[y][1]);}
inline bool cmp1(int x,int y)
{return Wz[x][0]<Wz[y][0]||(Wz[x][0]==Wz[y][0]&&wz[x][1]<wz[y][1]);}
inline bool cmp2(int x,int y)
{return Wz[x][1]<Wz[y][1]||(Wz[x][1]==Wz[y][1]&&wz[x][1]<wz[y][1]);}
inline bool cmp(int x,int y)
{return wz[x][1]>wz[y][1]||(wz[x][1]==wz[y][1]&&wz[x][0]<wz[y][0]);}
void Up(int x)
{
if (!x) return;
if (x!=n) printf("%d ",x);
if (!la[x]) Up(dir[x][Trs[x]]); else
{
int k=sign[x],l=sign[la[x]],e;
if (k<l)
{
e=k;
while (k-1&&wz[sg[k-1]][1]==wz[sg[k]][1])
printf("%d ",sg[--k]);
k=e+1;
for (;k<=l;k++) printf("%d ",sg[k]);
} else
{
e=k;
while (k<n&&wz[sg[k+1]][1]==wz[sg[k]][1])
printf("%d ",sg[++k]);
k=e-1;
for (;k>=l;k--) printf("%d ",sg[k]);
}
Up(dir[la[x]][Trs[la[x]]]);
}
return;
}
void DP()
{
for (int i=1;i<=n;i++)
Wz[i][0]=wz[i][0]+wz[i][1],
Wz[i][1]=wz[i][0]-wz[i][1];
sort(sg+1,sg+n+1,cmp0);
for (int i=1;i<=n;i++)
while (i<n&&wz[sg[i+1]][0]==wz[sg[i]][0])
i++,dir[sg[i-1]][1]=sg[i];
sort(sg+1,sg+n+1,cmp1);
for (int i=1;i<=n;i++)
while (i<n&&Wz[sg[i+1]][0]==Wz[sg[i]][0])
i++,dir[sg[i-1]][0]=sg[i];
sort(sg+1,sg+n+1,cmp2);
for (int i=1;i<=n;i++)
while (i<n&&Wz[sg[i+1]][1]==Wz[sg[i]][1])
i++,dir[sg[i-1]][2]=sg[i];
sort(sg+1,sg+n+1,cmp);
for (int i=1;i<=n;i++) sign[sg[i]]=i;
//la是从哪里过来，Trs只能从上面过来，ma是当前距离，Ans是答案距离
for (int i=1;i<=n;)
{
int ri=i;
while (ri<n&&wz[sg[ri+1]][1]==wz[sg[ri]][1]) ri++;
for (int j=i;j<=ri;j++)
for (int k=0;k<3;k++)
{
int l=Ans[dir[sg[j]][k]];
if (l>ma[sg[j]])
ma[sg[j]]=Ans[sg[j]]=l,Trs[sg[j]]=k;
}
int Ma=0;
for (int j=i;j<=ri;j++)
{
if (Ma&&ri-Ma+ma[sg[Ma]]>Ans[sg[j]])
Ans[sg[j]]=ri-Ma+ma[sg[Ma]],la[sg[j]]=sg[Ma];
if (!Ma||ri-j+ma[sg[j]]>ri-Ma+ma[sg[Ma]]) Ma=j;
}
Ma=0;
for (int j=ri;j>=i;j--)
{
if (Ma&&Ma-i+ma[sg[Ma]]>Ans[sg[j]])
Ans[sg[j]]=Ma-i+ma[sg[Ma]],la[sg[j]]=sg[Ma];
if (!Ma||j-i+ma[sg[j]]>Ma-i+ma[sg[Ma]]) Ma=j;
}
for (;i<=ri;i++) Ans[sg[i]]++;
}
cout <<Ans[n]-1<<endl;Up(n);puts("");
return;
}
bool BFS()
{
memset(h,0,sizeof(h));
for (int i=1;i<=n;i++) cur[i]=fi[i];
for (int i=_T;i<N;i++) cur[i]=fi[i];
int le=1,ri=1;h[_S]=1;li.push(_S);
while (!li.empty())
{
int k=li.front();li.pop();
for (int i=fi[k];i;i=c[i][1])
if (c[i][2]&&!h[c[i][0]])
h[c[i][0]]=h[k]+1,li.push(c[i][0]);
}
return h[_T]>0;
}
int DFS(int x,int y)
{
int k,l=0;
if (x==_T) return y;
for (int i=cur[x];i&&y;i=c[i][1])
if (c[i][2]&&h[c[i][0]]==h[x]+1)
{
k=DFS(c[i][0],min(y,c[i][2]));cur[x]=i;
if (k) l+=k,y-=k,c[i][2]-=k,c[i^1][2]+=k;
}
return l;
}
inline void line(int x,int y)
{Line(x,y,INF);Line(_S,y,1);Line(x,_T,1);flag[y]=true;}
void Trans(int x)
{
if (vis[x]) return;vis[x]=true;
for (int i=0;i<3;i++)
if (ma[x]==Ans[dir[x][i]]&&dir[x][i]) line(x,dir[x][i]);
}
void Clear()
{while (!li.empty()) li.pop();}
void Build()
{
flag[n]=true;
for (int i=n;i;)
{
int le=i,Ma=0;
while (le>1&&wz[sg[le-1]][1]==wz[sg[i]][1]) le--;
for (int j=le;j<=i;j++)
{
if (flag[sg[j]])
{
if (!la[sg[j]]) Trans(sg[j]);
if (Ma==Ans[sg[j]])
while (!li.empty())
Trans(li.front()),li.pop();
}
if (ma[sg[j]]+i-j+1>Ma)
Clear(),li.push(sg[j]),Ma=ma[sg[j]]+i-j+1; else
if (ma[sg[j]]+i-j+1==Ma)
li.push(sg[j]);
}
Ma=0;Clear();
for (int j=i;j>=le;j--)
{
if (flag[sg[j]]&&Ma==Ans[sg[j]])
while (!li.empty())
Trans(li.front()),li.pop();
if (ma[sg[j]]+j-le+1>Ma)
Clear(),li.push(sg[j]),Ma=ma[sg[j]]+j-le+1; else
if (ma[sg[j]]+j-le+1==Ma)
li.push(sg[j]);
}
i=le-1;
}
return;
}
void Flow()
{
for (int i=1;i<=n;i++)
Line(S,i,INF),Line(i,T,INF);
Build();
while (BFS()) DFS(_S,INF);
Line(T,S,INF);
while (BFS()) DFS(_S,INF);
cout <<c[ss][2]<<endl;
return;
}
int main()
{
n=Read()+1;
for (int i=1;i<n;i++)
wz[sg[i]=i][0]=Read(),wz[i][1]=Read();sg[n]=n;
DP();Flow();
return 0;
}
POI19填坑计划
等了好久终于可以开始填POI这种神坑了。。感觉如果能静下心来想的话其实有些题推起来也不算太过艰难。但我的智商是个大玄学。。打到一半才上线。。
[UPD 11.30] 因为感冒还有一些奇怪的事情再次推迟2天= =
现在完成了：
16
[Letters]：NOIP某题即视感。就是求个逆序对数。
[Distance]：大暴力？对于每个数处理出它所有因数打上标记，然后再每个数枚举因数求答案就好了
[Rendezvous]：一个环套树森林，随便乱搞搞就好了
[Well]：想了很久不会。。后来发现是有个玄学姿势没有get：二分答案的时候要从左往右扫一遍然后从右往左扫一遍使相邻的两个不超过x。其余部分就是比较愉快了，很容易发现以每个点为0点左右边界一定是单调的。所以是O(n log n)
[Vouchers]：n log n大暴力
[Tour de Byteotia]：把所有大于k的点的连通分量缩掉然后用剩下的总边数减去生成森林的边数就是答案。
[A Horrible Poem]：直接哈希就好了= =，一直在想些奇怪的东西= =，真是naive。我数了下因数个数naive地以为是n log n级别的。。然后T了。据说有两种特技可以加，一个是所有字母出现次数gcd一下，一个是这里。感觉第二种比较优美。改完之后果然跑的飞起。
[Fibonacci Representation]：首先很明显一个数只会出现一次。因为两个相同的这个数是可以分解成另外两个不同的Fibonacci数的。然后还有个性质就是肯定会包含值跟它相邻的两个数之一。所以直接上爆搜大力出奇迹？还有那个输入小于1e17是个坑= =应该是小于1e18
[Warehouse Store]：很明显是贪心从小到大取，每次取一个非0量。随便找个什么东西维护一下就是n log n的了。还要注意后面取的点对前面答案的影响。
[Squarks]：构造题。。TAT脑抽不会。。直接枚举第二个和第三个是哪个数就好了的。。n^3 log n真是厉害，事实是可以加很多剪枝所以根本就不会摸到上界。
[Salaries]：只会乱搞= =后来wa了以为不是正解= =别人做法都死麻烦= =后来才发现是正解，但是被我写的奇丑无比= =调好久发现处理上界的时候不能直接是父亲上界减一= =真是日
[Festival]：YY很久。首先差分约束系统显然，建出图来之后强连通分量之间答案独立显然。然后剩下的里面都是没有负环的强连通分量，我猜是里面的Max最短路的长度+1？感觉复杂度是个大玄学。还有判负环应该就是看a[i][i]是不是负数吧。wa了几个点调了好久最后发现我用了一年的我自己YY的Tarjan是错的TAT，不知道为什么一直都没错过。
[Cloakroom]：有人说n^2*k/32能过？真是厉害。。貌似只要改变设的状态就可以nk了？改为设b的最大值就好了。
[Bidding]：hehe，x可能的值只有不到100个。貌似BZOJ上面交这个有bug？
[Prefixuffix]：记得这题被数国队出到过NOIP模拟题里面。真是sxbk。。从中间往两边扫，左起点往左移一位答案的范围是原来答案范围+2以内。
[Minimalist Security]：这题放到后面才动。。主要是一开始被吓到了，看顶标什么的以为是权匹配相关。。于是感觉比较报警。。结果现在看是个SB题。。直接每个连通块设个x代表其中一个点应该减去多少，然后就可以得出整张图的量了，然后就是m个不等式求个交。如果图不可以黑白染色肯定就是解唯一。反正随便搞。。BZOJ上面的题面把背景省了我还以为z可以带小数TAT。
[Leveling Ground]：好神啊不会啊弃疗了留坑吧下次填好了。
所以就算完结了？
接下来一段时间准备把高一naive的时候参加过的培训资料过一遍好了，所以暂时不会开新坑。
NOIP2015流水账
[UPD 11.14]：程序发下来了，测了个叉车的数据感觉崩的爽爽哒，D1T3挂了40，D2T3也挂了那个大众分5分。还幻想什么595。不过好歹有个五百多还是没关系。
NOIP终于颓废完了，感觉像是难得的三天小长假
day0：LSP带我们去爬岳麓山，爬到顶发现贼爷丢了真是2333。下午在家颓废了一下就出发了，突然发现约好的几个人都TM不是跟我和克莱魔订的一个酒店，都是住高贵的国际交流中心。下午在颓废。。。晚上突然发现楼下什么时候开了个烤肉自助餐。怒作死一发！感觉冰淇淋还有饮料尤其是价格40块一个人很良心啊。。烤肉感觉并不怎么样。。回来晚上接着颓颓颓。。颓到一半发现还是应该写两道题。点开13年的day1T2写完发现就被坑了，因为不能两个一起排序。于是马上就虚了。。开始想象NOIP考挂还没有省选就已经AFO了的BE。
day1：晚上突然降温让人简直爽。也可能是因为昨天的烤肉结果madan10点上厕所之前一直肚子疼。。状态也一直不好。简直像是要走昨天晚上脑补的那个滚粗展开了让人虚的一笔。考前面基了Dash%%%。进了考场发现周围都是雅礼大爷，窝好像正好在MYY和YYT的中点？已吓哭。。开题之后发现day1的画风简直崩坏。T1smg题。。结果还是差点犯逗了。。T2smg题。。结果差点忘记了这是个森林。。多亏大样例。。T3一看就不对劲，在看到随机数据之前我就已经敢于写爆搜了，主要是没有其它靠谱的算法。码码码，尼玛细节真多啊，10:30调出大样例的时候真是感动，考到后面犯逗也少很多了。。下次再不能这么作死了。。后来包括PPT上面给出的问题调了很多错误。。目前看到的各种易错点好像没中一个？加了个手动计数卡时上去就交了。（不会linux计时函数的后果）考完怪怪的。。结果出来发现除了老司机高二没一个人写出来？大爷哥写了个怪怪的记忆化搜索，表示考场上面并没有往这方面想。。老司机考完兴奋异常，貌似对于调出了第三题感觉十分感动。。但是也有的人考完之后很萎的样子。day1的题目本来就不是很科学，不管怎么样我还是不说话的好。。中午吃饭听FY他妈预测今天没考DP明天一定会考，于是FY那天晚上一直都在被复习DP？真是2333。下午花式颓颓颓，先通了很久rop，然后入了IW这个坑，表示玩了玩I wanna be the M(ao)C(ha)果然高能。跳刺这东西真是不友好。然后扫雷、补番。膜拜了PJ题目表示比TG不知道高明到哪里去了。膜拜了Gromah T3的题解，才知道原来T3有靠谱解法= =Gromah是强啊，只是考场上面没写那种解法还是很可惜啊。
day2：晚上仍旧没睡好，隔壁学校真高能啊6:30钟就有老师叫人起床简直厉害。考前听老司机跟我BB昨天T3暴搜复杂度是可以接受的我表示hehe。考场上面状态好多了，还好带了肠胃药。题目画风也好多了，T1SB原题二分一下就好辣。T2一开始还艹蛋地用了两个前缀和简直naive，DP一下就好辣。T3终于是传统的数据结构题了，1s果然还是会卡常数啊，想写LCT不能。我有常数姿势！反正主体是倍增，一开始求出所有点对之间的距离，然后按距离从大到小排个序，然后用第一个点对中的一个点作为根重建树，然后再将询问扫一遍这样的求两条路径交就不会那么麻烦因为其中一条路径是竖着的。感觉比LCT和带线段树常数的树剖是要好点吧。。10点钟写完辣，110行我有特殊缩行技巧。感觉不太对的样子花了10分钟冷静一下然后调出了大样例然后数了一下T3常数（不会linux计时函数的后果）再把所有程序肉眼读了两遍就神游去了。平常也没有对拍习惯于是结束前半小时才想起来要写个对拍啊但只有半个小时还是算了= =剩下半个小时表示咖啡快抵挡不了我的睡意了。。考完高三大爷们普遍表示今天题目良心很多啊，人人都是一副AK了的样子。剩下作死不对拍的我如果哪题FST了岂不是药丸？不管了反正考完了。。高一的貌似考的不是很好，毕竟没基础，想当年我虽然有点基础但还是很naive，为了看输出结果写了个while(1);忘记删掉了，结果295实力二等奖，一等分数线是395。。当时看yali高一个个联赛500+还有后来的省选四人进队简直让人要有心理阴影了。
希望明年这个时候不会滚去搞高考吧。。
maya终于摆脱了考了6、70+套NOIP模拟题了我真是感动，这个月还有暑假里面每天都考简直考的人都要精分了，真不知道每天都考些水题有什么意义。目前先把NOIP那波题搞完然后填完CF坑然后就做做POI吧，poi =w=。进度要加快了，窝刷题速度这么慢= =不希望滚粗的话这个时候真心要多努力啊！
BZOJ乱炖
感觉CF单子上面的题目到后面越来越做不动
英文的题面、题解啃得人效率低下，时间一长就越来越萎
现在简直有种稍微要注意点细节的题都会挂的感觉
于是赶紧补一波BZOJ乱炖，感觉去年省选题很好玩的样子于是来一波好了
主要还是要找状态，找智商
现在完成了：
50/50
[UPD 11.10]：进度又要缓一缓了，决定现在去复习一下以前学的东西还有做过的题目，然后把CC打掉再回来继续填。感觉很多基础的东西学过都忘记了。
BZOJ4032：简直有毒啊这题，脑洞了好久终于把四问全部搞出来了。。跪拜考场还可以A掉这题的ZRT大爷。。第一问，SAM上面跑一跑。第二问枚举左端点然后每次右端点移一位，判断O(n)暴力。第三问，建出B串trie树然后遍历一遍，一开始觉得不行但是只要枚举不能到达的字符然后看A串这个点后面有没有对应字符就好了。第四问，DP求出A串每个位置能够对应B串哪些位置，而且两者都必须尽量往左靠，转移是O(n)的对于每个节点，因为要往左靠所以最多26个可达状态。。然后就可以搞一搞了。。（话说序列自动机呢。。）话说除了SAM还有少特判一些情况都一遍写对了真是感动啊。。把代码放上来好了。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 2050
#define M 2000050
#define P 26
struct Node
{
Node *suf,*go[P];int val,mi;bool b;
} statePool[N*2],*cur,*root,*last;
struct Point
{Point *go[P];int h;} StatePool[M],*Root,*Cur;
char a[N],b[N];int n,m,nA[N][P],nB[N][P],s[N][N];bool c[N][N];
void Pretreat()
{
for (int i=1;i<=n;i++) a[i]-='a';
for (int i=1;i<=m;i++) b[i]-='a';
for (int i=n-1;i>=0;i--)
memcpy(nA[i],nA[i+1],sizeof nA[i+1]),nA[i][a[i+1]]=i+1;
for (int i=m-1;i>=0;i--)
memcpy(nB[i],nB[i+1],sizeof nB[i+1]),nB[i][b[i+1]]=i+1;
for (int i=0;i<P;i++)
if (nA[0][i]&&!nB[0][i])
{puts("1\n1\n1\n1");exit(0);}
}
struct Get_Ans1
{
void extend(int w)
{
Node *p=last,*np=cur++;
np->val=p->val+1;
while (p!=NULL&&!p->go[w])
p->go[w]=np,p=p->suf;
if (p==NULL)
np->suf=root; else
{
Node *q=p->go[w];
if (q->val==p->val+1)
np->suf=q; else
{
Node *nq=cur++;
memcpy(nq->go,q->go,sizeof q->go);
nq->val=p->val+1;
nq->suf=q->suf;
q->suf=np->suf=nq;
while (p!=NULL&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;
}
void Get_Mi()
{
Node* li[N*2];int le=1,ri=1;
li[1]=root;
for (;le<=ri;le++)
for (int i=0;i<P;i++)
if (li[le]->go[i]&&!li[le]->go[i]->b)
li[++ri]=li[le]->go[i],li[ri]->b=true,
li[ri]->mi=li[le]->mi+1;
}
int Solve()
{
cur=statePool;root=last=cur++;
for (int i=1;i<=m;i++) extend(b[i]);
Get_Mi();int ri=0,ans=M;Node* now=root;
for (int i=1;i<=n;i++)
{
while (ri<n&&now->go[a[ri+1]])
now=now->go[a[++ri]];
if (ri==n) break;
ans=min(ans,ri-i+2);
if (now!=root&&now->mi==ri-i+1)
now=now->suf;
if (ri<i) ri=i;
}
return ans==M?-1:ans;
}
} GA1;
struct Get_Ans2
{
bool Check(char* a,int len)
{
for (int i=1,now=0;i<=len;i++)
if (!nB[now][a[i]]) return false; else
now=nB[now][a[i]];
return true;
}
int Solve()
{
int ri=0,ans=M;
for (int i=1;i<=n;i++)
{
while (ri<n&&Check(&a[i-1],ri-i+2)) ri++;
if (ri==n) break;ans=min(ans,ri-i+2);
}
return ans==M?-1:ans;
}
} GA2;
struct Get_Ans3
{
void Set(char* a,int len)
{
Point* now=Root;
for (int i=1;i<=len;i++)
{
if (!now->go[a[i]])
now->go[a[i]]=Cur,Cur->h=now->h+1,Cur++;
now=now->go[a[i]];
}
return;
}
int DFS(Point* now,int Now)
{
int ans=M;
for (int i=0;i<P;i++)
if (now->go[i]&&nA[Now][i])
ans=min(DFS(now->go[i],nA[Now][i]),ans); else
if (now->go[i]==NULL&&nA[Now][i])
ans=min(ans,now->h+1);
return ans;
}
int Solve()
{
Cur=StatePool;Root=Cur++;
for (int i=1;i<=m;i++) Set(&b[i-1],m-i+1);
int ans=DFS(Root,0);return ans==M?-1:ans;
}
} GA3;
struct Get_Ans4
{
inline void Update(int &x,int y)
{x=!x?y:min(x,y);}
int Solve()
{
int ans=M;
for (int i=0;i<P;i++)
c[nA[0][i]][nB[0][i]]=true,s[nA[0][i]][nB[0][i]]=1;
for (int i=1;i<n;i++)
for (int j=0;j<P;j++)
if (nA[i][j])
for (int k=1;k<=m;k++)
if (c[i][k])
if (nB[k][j])
c[nA[i][j]][nB[k][j]]=true,
Update(s[nA[i][j]][nB[k][j]],s[i][k]+1); else
ans=min(ans,s[i][k]+1);
return ans==M?-1:ans;
}
} GA4;
int main()
{
gets(a+1);gets(b+1);n=strlen(a+1);m=strlen(b+1);Pretreat();
printf("%d\n%d\n%d\n%d\n",GA1.Solve(),GA2.Solve(),GA3.Solve(),GA4.Solve());
return 0;
}
BZOJ4030：首先把妹计划必须要是升序的，这个显然，而且也证明的出来：首先可以把0位置上面放一个0还有第n+1位置上面放一个1答案不会改变，这是方便运算用的。i从1到n扫一遍当第i小的数不在位置i的时候它两边肯定都比它大（因为已经处理了1~i-1了），然后把它放到位置i答案肯定会变优，这个推下式子一下就可以很看出这个操作对答案的贡献是非正的。因为除了从小到大排序之外总可以找到这样的i所以只有从小到大排序是最优的2333。剩下不会了，当然我还是会喜闻乐见猜结论，写了个暴力玩了玩感觉答案是1~i和j~n的并，然后就是扫一遍的事情了。。（跟过了的大爷们的做法明明是一样的）写起来蛋疼的一笔。。我想我已经调到极限了，我拍了很久都没有错，可能是些特殊情况吧。。总之虽然没过代码先放上来好了。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 200050
#define fr first
#define sc second
#define ll long long
#define ld long double
ld ans;int n,m,t;ll Aha,s[N][2];
pair <ld,int> li[N],Emp;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline ld min(ld x,ld y)
{return x<y?x:y;}
inline ll min(ll x,ll y)
{return x<y?x:y;}
inline ld Calc(ld x,ld y)
{return x*(1-y);}
int main()
{
//freopen("input.txt","r",stdin);
t=Read();
while (t--)
{
n=Read();m=Read();Aha=0;
int st=0;
for (int i=1;i<=n;i++)
{
int k=Read(),l=Read();st++;
li[i].fr=1-(ld)(k)/l;
Aha+=(li[i].sc=Read());
if (!li[i].sc) st--;
}
li[n+1]=Emp;
n=st;sort(li+1,li+n+1);s[n+1][1]=0;
for (int i=1;i<=n;i++) s[i][0]=s[i-1][0]+li[i].sc;
for (int i=n;i>=1;i--) s[i][1]=s[i+1][1]+li[i].sc;
int le=0,cnt=0,ri=n+1;ld Ans=0;
while (s[ri][1]<m)
{
ri--;
if (ri!=n) Ans+=Calc(li[ri].fr,li[ri+1].fr);
Ans+=(min(s[ri][1],m)-s[ri+1][1]-1)*
Calc(li[ri].fr,li[ri].fr);
}
ans=Ans;
while (cnt!=m)
{
int k;
if (s[le][0]==cnt||s[ri+1][1]+1==m-cnt) k=1; else
k=min(m-cnt,min(s[le][0]-cnt,m-cnt-s[ri+1][1]-1));
if (s[le][0]==cnt)
Ans+=Calc(li[le].fr,li[le+1].fr),le++; else
Ans+=k*Calc(li[le].fr,li[le].fr);
if (s[ri+1][1]+1==m-cnt)
Ans-=ri==n?0:Calc(li[ri].fr,li[ri+1].fr),ri++; else
Ans-=k*Calc(li[ri].fr,li[ri].fr);
cnt+=k;
ans=min(ans,Ans+Calc(cnt==m?0:li[le].fr,li[ri].fr));
}
printf("%.6lf\n",(double)fabs(ans));
}
return 0;
}
BZOJ4028：简直smg。。开始搞了好久发现看错题了。。想了一想感觉复杂度好玄学。。这smg题啊劳资弃坑了！！
HEOI终于完结，贵省考的真瘠薄。（所以还是要膜这种狗哔题目能屠场的ZRT大爷啊
BZOJ4004：虽然不知道线性基这种高端东西，不过还是成功YY粗了做法。玛德eps开小了wa了n遍简直日。。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 505
#define eps 1e-5
double v[N][N],Aha[N][N];
int n,m,t[N],sg[N],st,ans;bool b[N];
inline bool cmp(int x,int y)
{return t[x]<t[y];}
void Solve(int x)
{
for (int i=1;i<=m;i++)
if (fabs(v[x][i])>eps)
if (!b[i])
{
for (int j=i;j<=m;j++) Aha[i][j]=v[x][j];
st++;b[i]=true;ans+=t[x];return;
} else
{
double k=v[x][i]/Aha[i][i];
for (int j=i;j<=m;j++) v[x][j]-=Aha[i][j]*k;
}
return;
}
int main()
{
cin >>n>>m;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) scanf("%lf",&v[i][j]);
for (int i=1;i<=n;i++)
scanf("%d",&t[i]),sg[i]=i;
sort(sg+1,sg+n+1,cmp);st=0;
for (int i=1;i<=n&&st!=m;i++) Solve(sg[i]);
cout <<st<<' '<<ans<<endl;
return 0;
}
BZOJ4002：看完题解才发现其实提示都还是蛮明显的= =主要是看那个下取整就不敢做了以为要用到一些特别高妙的方法。其实只要跟斐波那契数列递推式联系一下就会发现求的这东西是通项公式的一部分，另外一部分是小于1的。模数好诡异，乘二爆long long？
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll unsigned long long
const ll P=7528443412579576937LL;
ll n,m,p;
struct Point {ll a[2][2];} Ans,C;
ll Quick_Multi(ll x,ll y)
{
ll z=0;
while (y)
{
if (y&1) z=(z+x)%P;
x=(x+x)%P;y >>= 1;
}
return z;
}
inline void Add(ll &x,ll y)
{x+=y;if (x>=P) x-=P;}
Point operator* (const Point &x,const Point &y)
{
memset(C.a,0,sizeof(C.a));
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
for (int k=0;k<2;k++)
Add(C.a[i][k],Quick_Multi(x.a[i][j],y.a[j][k]));
return C;
}
void Quick_Power(ll y)
{
Point x=(Point){{{0,(m-n*n)/4},{1,n}}},
z=(Point){{{2,n},{0,0}}};
while (y)
{
if (y&1) z=z*x;
x=x*x;y >>= 1;
}
Ans=z;
}
int main()
{
cin >>n>>m>>p;
if (p==0) {puts("1");return 0;}
Quick_Power(p-1);
cout <<(Ans.a[0][1]+P-(m!=n*n&&!(p&1)))%P<<endl;
return 0;
}
BZOJ4007：萎爆了= =没想出来= =。直接DP就好了，设状态设的是所有父亲的状态，就是状压一下然后从下往上扫一遍就好了= =哦还有层限制，那就只要加一维状态当前子树有多少个打仗的就好了。日BZOJ上面的题面误我青春，我还以为说的是m<=2*n。总复杂度随便算下发现是2^(2*n)*n左右的，虚虚的但也不是不能过。恶心不过卡内存！也就是说重写了三次：第一次被狗哔题面卡住了，第二次脑洞大开写了个map真是2333，第三次用2^2n个vector存了这东西但是发现就算释放内存还是挂掉的真尼玛愉快啊2333。换成递归形式就能过？空间还只用了9M？难道递归完了里面的空间会回收的？
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define N 1050
#define M 22
int a2[M],n,m,a[N][N][2],A2[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
vector <int> Get_Ans(int x,int y,int z)
{
vector <int> s;
if (x>=a2[n-1])
{s.push_back(a[x][y][0]);s.push_back(a[x][y][1]);return s;}
vector <int> q,w,e,r;
q=Get_Ans(x*2,y*2,z+1);w=Get_Ans(x*2,y*2+1,z+1);
e=Get_Ans(x*2+1,y*2,z+1);r=Get_Ans(x*2+1,y*2+1,z+1);
int sz=a2[n-z]+1,len1=q.size(),len2=w.size(),len3=e.size(),len4=r.size();
for (int i=0;i<sz;i++) s.push_back(0);
for (int i=0;i<len1;i++)
for (int j=0;j<len3;j++) s[i+j]=max(s[i+j],q[i]+e[j]);
for (int i=0;i<len2;i++)
for (int j=0;j<len4;j++) s[i+j]=max(s[i+j],w[i]+r[j]);
return s;
}
int main()
{
n=Read();m=Read();a2[0]=1;
for (int i=1;i<=n;i++) A2[a2[i]=a2[i-1] << 1]=i;
for (int t=1;t>=0;t--)
for (int i=a2[n-1];i<a2[n];i++)
{
for (int j=1;j<n;j++)
{
int e=Read(),l=a2[n-1]-1-a2[j-1];
for (int k=l;k;k=(k-1)&l) a[i][k+a2[j-1]*t][t]+=e;
a[i][a2[j-1]*t][t]+=e;
}
}
vector <int> Ans=Get_Ans(1,0,0);int ans=0;
for (int i=0;i<=m;i++) ans=max(ans,Ans[i]);
cout <<ans<<endl;
return 0;
}
BZOJ4006：斯坦纳树显然，多出来的条件直接套个DP就好了。。复杂度很虚？管它的能过就行。。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define N 1050
#define M 6050
#define P 12
#define INF 0x3f7f7f7f
int fi[N],c[M][3],ss=1,mi[N][N],n,m,p,a[N],Sg[P],a2[P],v[P];
queue <int> li;bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int z,int y,int x)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
}
void Solve_Stainer()
{
for (int i=1;i<a2[p];i++)
{
for (int j=1;j<=n;j++) mi[i][j]=INF;
if (i-(i&(-i))==0)
for (int j=0;j<p;j++)
if (a2[j]==i) mi[i][Sg[j+1]]=0;
for (int j=(i-1)&i;j*2>=i;j=(j-1)&i)
for (int k=1;k<=n;k++)
mi[i][k]=min(mi[i][k],mi[j][k]+mi[i-j][k]);
for (int j=1;j<=n;j++)
if (mi[i][j]!=INF) li.push(j),b[j]=true;
while (!li.empty())
{
int k=li.front();li.pop();
for (int j=fi[k];j;j=c[j][1])
if (mi[i][k]+c[j][2]<mi[i][c[j][0]])
{
mi[i][c[j][0]]=c[j][2]+mi[i][k];
if (!b[c[j][0]])
b[c[j][0]]=true,li.push(c[j][0]);
}
b[k]=false;
}
}
return;
}
void Solve_DP()
{
for (int i=1;i<a2[p];i++)
{
int k=0;a[i]=INF;
for (int j=1;j<=p;j++) if (i&a2[j-1]) k|=v[j];
for (int j=1;j<=n;j++) a[i]=min(a[i],mi[k][j]);
for (int j=(i-1)&i;j;j=(j-1)&i)
a[i]=min(a[i],a[j]+a[i-j]);
}
return;
}
int main()
{
n=Read();m=Read();p=Read();a2[0]=1;
for (int i=1;i<=p;i++) a2[i]=a2[i-1] << 1;
for (int i=1;i<=m;i++) Line(Read(),Read(),Read());
for (int i=1;i<=p;i++)
v[Read()]|=a2[i-1],Sg[i]=Read();
Solve_Stainer();Solve_DP();
cout <<a[a2[p]-1]<<endl;
return 0;
}
JLOI还剩下一个神题找个时间填掉好了。。贵省考的真厉害。
BZOJ3996：玛德好久没做网络流什么建模的题都做不出了。调了好久发现是一个优化没加：如果这条路增广不了就把那个点的深度重置。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 505
#define M 260050
#define INF 0x3f7f7f7f
int sg[N][N],n,m,S=M-1,T=M-2,fi[M],c[M*10][3],li[M],h[M],ans,ss=1,st;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=0;fi[y]=ss;
}
bool BFS()
{
for (int i=1;i<=st;i++) h[i]=0;h[T]=0;
int le=1,ri=1;li[1]=S;h[S]=1;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!h[c[i][0]]&&c[i][2])
h[c[i][0]]=h[li[le]]+1,li[++ri]=c[i][0];
return h[T]>0;
}
int DFS(int x,int y)
{
int k,l=0;
if (x==T) return y;
for (int i=fi[x];i&&y;i=c[i][1])
if (c[i][2]&&h[c[i][0]]==h[x]+1)
{
k=DFS(c[i][0],min(y,c[i][2]));
if (k) y-=k,l+=k,c[i][2]-=k,c[i^1][2]+=k; else
h[c[i][0]]=0;
}
return l;
}
int main()
{
n=st=Read();
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
int k=Read();ans+=k;
Line(S,sg[i][j]=++st,k);
Line(sg[i][j],i,INF);
if (i!=j) Line(sg[i][j],j,INF);
}
for (int i=1;i<=n;i++) Line(i,T,Read());
while (BFS()) ans-=DFS(S,INF);
cout <<ans<<endl;
return 0;
}
BZOJ3997：脑洞了一个结论，答案就是最长的反链，猜了之后才发现这个确实可以对应到最小链覆盖问题的，有个Dilworth吧好像就是证明这个东西的。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1050
int n,m,v[N][N],t;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int main()
{
t=Read();
while (t--)
{
n=Read();m=Read();
memset(v,0,sizeof(v));
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) v[i][j]=Read();
for (int i=1;i<=n;i++)
for (int j=m;j>=1;j--)
v[i][j]=max(max(v[i-1][j],v[i][j+1]),v[i][j]+v[i-1][j+1]);
cout <<v[n][1]<<endl;
}
return 0;
}
BZOJ3998：一眼SAM。时间卡的人好虚
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 500050
#define M 26
#define ll long long
struct State
{
State *go[M],*suf;int val,s,d;ll cnt;
} statePool[N*2],*cur,*root,*last,*li[N*2];
int n,m,P,ans;char b[N];
void extend(int w)
{
State *p=last,*np=cur++;
np->val=p->val+1;
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p) np->suf=root; else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q; else
{
State* nq=cur++;
memcpy(nq->go,q->go,sizeof q->go);
nq->val=p->val+1;
nq->suf=q->suf;
q->suf=np->suf=nq;
while (p&&p->go[w]==q) p->go[w]=nq,p=p->suf;
}
}
last=np;np->s++;
}
void Pretreat()
{
int le=1,ri=0;
if (P==1)
{
for (State* i=root;i!=cur;i++)
if (i->suf) i->suf->d++;
for (State* i=root;i!=cur;i++)
if (!i->d) li[++ri]=i;
for (;le<=ri&&li[le]!=root;le++)
{
li[le]->suf->s+=li[le]->s;
if (!(--li[le]->suf->d))
li[++ri]=li[le]->suf;
}
}
root->s=0;le=1;ri=0;
for (State* i=root;i!=cur;i++)
for (int j=0;j<M;j++)
if (i->go[j]) i->go[j]->d++;
for (State* i=root;i!=cur;i++)
if (!i->d) li[++ri]=i;
for (;le<=ri;le++)
for (int i=0;i<M;i++)
if (li[le]->go[i]&&((--(li[le]->go[i]->d))==0))
li[++ri]=li[le]->go[i];
for (int i=ri;i>=1;i--)
{
if (!P) li[i]->s=1;
li[i]->cnt=li[i]->s;
for (int j=0;j<M;j++)
if (li[i]->go[j])
li[i]->cnt+=li[i]->go[j]->cnt;
}
root->cnt--;root->s=0;
if (root->cnt<m) {puts("-1");exit(0);};
return;
}
bool Solve(State* x,ll y)
{
y-=x->s;if (y<=0) return true;
for (int i=0;i<M;i++)
if (x->go[i])
if (x->go[i]->cnt>=y&&Solve(x->go[i],y))
{b[++ans]='a'+i;return true;} else
y-=x->go[i]->cnt;
}
int main()
{
gets(b+1);cin >>P>>m;n=strlen(b+1);
cur=statePool;root=last=cur++;
for (int i=1;i<=n;i++) extend(b[i]-'a');
Pretreat();Solve(root,m);
for (int i=ans;i>=1;i--) putchar(b[i]);
puts("");
return 0;
}
BZOJ4001：看了看。。狗哔概率题窝毫无思路。。再顺便看看代码长度。。！！！表一发然后就过了。。结论是n*(n+1)/(4n-2)
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
long double n;
cin >>n;
printf("%.9lf\n",(double)(n*(n+1)/(4*n-2)));
return 0;
}
BZOJ4000：在看懂题棋子位置是在第二行而不是第一行之前怎么搞不出，看懂题之后就是个裸裸的DP+矩阵快速幂优化了
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 10
#define M 70
#define ui unsigned int
struct Matrix
{ui a[M][M];} A,B,C;
int n,m,p,s,c[N],a2[N],st;ui ans;bool b[M];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
Matrix operator* (const Matrix &x,const Matrix &y)
{
memset(C.a,0,sizeof(C.a));
for (int i=0;i<st;i++)
for (int j=0;j<st;j++)
for (int k=0;k<st;k++)
C.a[i][k]+=x.a[i][j]*y.a[j][k];
return C;
}
void Quick_Power(int x)
{
for (int i=0;i<st;i++) B.a[i][i]=1;
while (x)
{
if (x&1) B=B*A;
A=A*A;x >>= 1;
}
return;
}
bool Intersect(int x,int y,int z)
{
for (int i=0;i<m;i++)
if (x&a2[i])
{
int k=z;
if (s<i) k <<= i-s; else
k >>= s-i;
if (k&y) return true;
}
return false;
}
void Pretreat()
{
for (int i=0;i<st;i++)
if (!Intersect(i,i,c[1])) b[i]=true;
for (int i=0;i<st;i++)
if (b[i])
for (int j=0;j<st;j++)
if (b[j]&&!Intersect(i,j,c[2])&&!Intersect(j,i,c[0]))
A.a[i][j]=true;
return;
}
int main()
{
n=Read();m=Read();p=Read();s=Read();a2[0]=1;st=1 << m;
for (int i=1;i<N;i++) a2[i]=a2[i-1] << 1;
for (int i=0;i<3;i++)
for (int j=0;j<p;j++)
c[i]|=Read() << j;
if (c[1]&a2[s]) c[1]-=a2[s];
Pretreat();Quick_Power(n);
for (int i=0;i<st;i++) ans+=B.a[0][i];
cout <<ans<<endl;
return 0;
}
TJOI还剩下一道SB数据结构题，既然BZOJ不屑于贴题面我也懒得写了。。（所以就完结了，e感觉TJOI考的好水= =）
BZOJ3930：一眼神题，后来发现H-L<=10^5所以只要暴力容斥就好了n log n的。之前交了一发才发现自己犯逗了。首先全部都除以k，GCD最多只会有2*(H-L)种情况：GCD=L~H的就是n个数全部为那一个数的情况。GCD=1~H-L+1的直接容斥一下就好了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define P 1000000007
#define ll long long
ll n,m,Le,Ri,a[N];
inline ll Quick_Power(ll x,ll y)
{
ll z=1;
while (y) {if (y&1) z=z*x%P;x=x*x%P;y >>= 1;}
return z;
}
int main()
{
cin >>n>>m>>Le>>Ri;Le=(Le-1)/m+1;Ri/=m;m=Ri-Le+1;
for (int i=m-1;i>=1;i--)
{
a[i]=Quick_Power((Ri/i)-(Le-1)/i,n);
for (int j=i+i;j<m;j+=i) a[i]=(a[i]+P-a[j])%P;
a[i]=(a[i]+P-(Ri/i-max((Le-1)/i,(m-1)/i)))%P;
}
cout <<a[1]<<endl;
return 0;
}
CQOI除去之前写过的两题还有两题一个像是花式乱搞一个像是花式DP感觉题目并不好玩已经不想写了= =贵省考的好良心= =
BZOJ3990：首先很容易看出如果找到了一个操作序列则答案等于(|操作序列|)!。因为操作只有覆盖关系而没有相交关系所以操作是互不影响的。然后求出其中一组操作序列可以从小到大看每一种操作，因为当前操作能够改变的只有两种情况21也就是交换的两个交换之后在同一个整体里面或者是1423这样不在同一个整体里面的。后者有的时候还要分两种情况比如1432的情况所以搜索一下就好了。复杂度：总共有2^n种操作方式，因为还要交换总共复杂度是差不多2^2n左右吧。。当然因为很多情况半路就不行了所以实际上跑的飞起。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 15
#define M 4100
#define ll long long
#define fr first
#define sc second
pair <int,int> li[N];
int v[M],n,m,JC[N],PX[N];ll ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Calc(int x,int y,int z,int o)
{
li[1]=make_pair(v[x+1],1);li[2]=make_pair(v[y+1],2);
li[3]=make_pair(v[z+1],3);li[4]=make_pair(v[o+1],4);
sort(li+1,li+5);PX[li[1].sc]=1;PX[li[2].sc]=2;
PX[li[3].sc]=3;PX[li[4].sc]=4;
}
void Swap(int x,int y,int z,int o)
{
void Solve(int x,int y);
for (int i=1;i<=z;i++) swap(v[x+i],v[y+i]);
Solve(o,z*2);
for (int i=1;i<=z;i++) swap(v[x+i],v[y+i]);
return;
}
void Solve(int x,int y)
{
int k=0,l=0;
if (y==m) {ans+=JC[x];return;}
for (int i=1;i<=m/y;i+=2)
if (v[i*y]!=v[(i+1)*y]-y||v[i*y]%(2*y)!=y)
{if (!k) k=i; else if (!l) l=i; else return;}
if (!k) Solve(x,y*2); else
if (!l)
Swap((k-1)*y,k*y,y,x+1); else
{
Calc((k-1)*y,k*y,(l-1)*y,l*y);
if ((PX[1]==1&&PX[4]==4)||(PX[1]==3&&PX[2]==1&&PX[3]==4))
Swap(k*y,(l-1)*y,y,x+1); else
if ((PX[2]==2&&PX[3]==3)||(PX[1]==2&&PX[2]==4&&PX[3]==1))
Swap((k-1)*y,l*y,y,x+1); else
if ((PX[1]==1&&PX[3]==3)||(PX[2]==2&&PX[4]==4))
Swap((k-1)*y,(l-1)*y,y,x+1),Swap(k*y,l*y,y,x+1);
}
return;
}
int main()
{
n=Read();m=1 << n;JC[0]=1;
for (int i=1;i<N-2;i++) JC[i]=JC[i-1]*i;
for (int i=1;i<=m;i++) v[i]=Read();
Solve(0,1);
cout <<ans<<endl;
return 0;
}
BZOJ3991：脑洞了好久动态树做法发现好麻烦= =突然发现脑抽了只要DFS序就可做了，就只要维护一个set然后倍增搞一搞就好了。一开始以为线段树是可以维护出树上任意两点距离写完之后才发现犯逗了。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
#define M 17
#define ll long long
multiset <int> li;
set <int> :: iterator it,ti;
int sg[N][2],nd[N*2],fi[N],c[N*2][3],fa[N][M],a2[M];
int Cnt,n,m,st,ss=1;ll up[N][M],h[N],ans,H[N];bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int z,int y,int x)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
}
void DFS(int x)
{
nd[sg[x][0]=++st]=x;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
fa[c[i][0]][0]=x,
h[c[i][0]]=h[x]+(up[c[i][0]][0]=c[i][2]),
H[c[i][0]]=H[x]+1,DFS(c[i][0]);
nd[sg[x][1]=++st]=x;
}
void Pretreat()
{
for (int i=1;i<M;i++)
for (int j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1],
up[j][i]=up[j][i-1]+up[fa[j][i-1]][i-1];
}
ll Dis(int x,int y)
{
x=nd[x];y=nd[y];
ll cnt=h[x]+h[y];
if (H[x]<H[y]) swap(x,y);
for (int i=M-1;i>=0&&H[x]!=H[y];i--)
if (H[x]-a2[i]>=H[y]) x=fa[x][i];
if (x!=y)
{
for (int i=M-1;i>=0;i--)
if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
x=fa[x][0];
}
return cnt-2*h[x];
}
void Delete(int x)
{
for (int i=0;i<2;i++)
{
it=ti=li.lower_bound(sg[x][i]);bool flag=false;
if (it!=li.begin())
ans-=Dis(*(--it),sg[x][i]),flag=true;ti++;
if (ti!=li.end())
{
ans-=Dis(sg[x][i],*ti);
if (flag) ans+=Dis(*it,*ti);
}
li.erase(sg[x][i]);
}
b[x]=false;Cnt--;return;
}
void Insert(int x)
{
for (int i=0;i<2;i++)
{
it=ti=li.lower_bound(sg[x][i]);bool flag=false;
if (it!=li.end())
ans+=Dis(sg[x][i],*it),flag=true;
if (ti!=li.begin())
{
ans+=Dis(sg[x][i],*(--ti));
if (flag)
ans-=Dis(*ti,*it);
}
li.insert(sg[x][i]);
}
b[x]=true;Cnt++;return;
}
ll Aha()
{
if (!Cnt) return 0;
it=li.begin();ti=li.end();return Dis(*it,*(--ti));
}
int main()
{
n=Read();m=Read();a2[0]=1;
for (int i=1;i<M;i++) a2[i]=a2[i-1] << 1;
for (int i=1;i<n;i++) Line(Read(),Read(),Read());
DFS(1);Pretreat();
while (m--)
{
int k=Read();
if (b[k]) Delete(k); else Insert(k);
printf("%lld\n",ans+Aha());
}
return 0;
}
BZOJ3992：求个原根然后将集合里面每个数用原根的幂表示出来。最后倍增一下NTT一下就好了。（我什么板子都不记得了~
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 32200
#define P 1004535809
#define G 3
#define ll long long
int n,m,p,s,v[N],rt,sg[N],rev[N],len,bit;ll wn[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline ll Quick_Power(ll x,ll y,ll z)
{
ll s=1;
while (y)
{if (y&1) s=s*x%z;x=x*x%z;y >>= 1;}
return s;
}
void Find_Rt()
{
if (m==2) {rt=1;return;}
for (rt=2;rt<m;rt++)
{
bool flag=false;
for (int i=2;i*i<m;i++)
if ((m-1)%i==0&&(Quick_Power(rt,i,m)==1
||Quick_Power(rt,(m-1)/i,m)==1)) {flag=true;break;}
if (!flag) break;
}
}
void Sign()
{int cnt=rt;for (int i=1;i<m-1;i++) sg[cnt]=i,cnt=cnt*rt%m;}
void Solve(ll* a,int n,int f)
{
for (int i=0;i<n-1;i++)
if (i<rev[i]) swap(a[i],a[rev[i]]);
int now=0;
for (int p=1;p<n;p <<= 1)
{
now++;
for (int i=0;i<n;i+=p << 1)
{
ll e=1;
for (int j=0;j<p;j++,e=e*wn[now]%P)
{
ll x=a[i+j],y=e*a[i+j+p]%P;
a[i+j]=(x+y)%P;a[i+j+p]=(x-y+P)%P;
}
}
}
if (f==-1)
{
for (int i=1;i<n >> 1;i++) swap(a[i],a[n-i]);
ll Inv=Quick_Power(n,P-2,P);
for (int i=0;i<n;i++) a[i]=a[i]*Inv%P;
}
}
struct NTT {ll a[N];} A,B,C;
void Multi(NTT &x,NTT &y)
{
memcpy(C.a,y.a,sizeof y.a);
Solve(x.a,len,1);Solve(C.a,len,1);
for (int i=0;i<len;i++) x.a[i]=x.a[i]*C.a[i]%P;
Solve(x.a,len,-1);
for (int i=m-1;i<=m-2<<1;i++) (x.a[i-(m-1)]+=x.a[i])%=P,x.a[i]=0;
}
void Quick_Powor(int y)
{while (y) {if (y&1) Multi(B,A);Multi(A,A);y >>= 1;}}
int main()
{
n=Read();m=Read();p=Read();s=Read();
for (int i=1;i<=s;i++) v[i]=Read();
Find_Rt();Sign();
for (int i=1;i<=s;i++)
if (v[i]) A.a[sg[v[i]]]=true;
len=1;
while (len<m*2-1) len <<= 1,bit++;
for (int i = 1;i < len;i ++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
for (int i=0;i<=20;i++)
wn[i]=Quick_Power(G,P - 1 >> i,P);
B.a[0]=1;Quick_Powor(n);
cout <<B.a[sg[p]]<<endl;
return 0;
}
BZOJ3993：二分+网络流，也没卡精度= =
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 105
#define M 6050
#define eps 1e-6
#define INF 0x3f7f7f7f
int S=N-1,T=N-2,fi[N],c[M][2],n,m,ss=1,sg[N],t[N],h[N],li[N];
double v[M],cnt;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline int Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];v[ss]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];v[ss]=0;fi[y]=ss;
return ss-1;
}
bool BFS()
{
memset(h,0,sizeof(h));
h[li[1]=S]=1;int le=1,ri=1;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!h[c[i][0]]&&fabs(v[i])>eps)
h[li[++ri]=c[i][0]]=h[li[le]]+1;
return h[T]>0;
}
inline double min(double x,double y)
{return x<y?x:y;}
double DFS(int x,double y)
{
if (x==T) return y;
double k,l=0;
for (int i=fi[x];i&&fabs(y)>eps;i=c[i][1])
if (h[c[i][0]]==h[x]+1&&fabs(v[i])>eps)
{
k=DFS(c[i][0],min(y,v[i]));
if (fabs(k)<eps) continue;
l+=k;y-=k;v[i^1]+=k;v[i]-=k;
}
return l;
}
bool Check(double x)
{
for (int i=1;i<=m;i++) v[sg[i]]=t[i]*x;
double k=0;
while (BFS()) k+=DFS(S,INF);
for (int i=2;i<ss;i+=2) v[i]+=v[i+1],v[i+1]=0;
return fabs(k-cnt)<eps;
}
double Half_Find(double x,double y)
{
double i=(x+y)/2;
if (fabs(x-y)<eps) return x;
if (Check(i)) return Half_Find(x,i); else
return Half_Find(i,y);
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++)
{
int k=Read();cnt+=k;
Line(i,T,k);
}
for (int i=1;i<=m;i++)
sg[i]=Line(S,i+n,0),t[i]=Read();
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
if (Read()) Line(i+n,j,INF);
printf("%.6lf\n",Half_Find(0,(int)1e7));
return 0;
}
BZOJ3994：搞完这一波真心要回去搞搞数论相关了。。好久都没做这种题现在没点手感= =推倒过程可以看这里好了。然后那个神结论的证明就看这里。感觉这题简直恶心。。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 50050
#define ll long long
ll miu[N],mis[N],F[N],ans;int t,n,m,st,Prime[N];bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void Pretreat()
{
miu[1]=mis[1]=1;
for (int i=2;i<N;i++)
{
if (!b[i]) miu[Prime[++st]=i]=-1;
for (int j=1;j<=st&&Prime[j]*i<N;j++)
{
b[i*Prime[j]]=true;
if (i%Prime[j]==0) break;
miu[i*Prime[j]]=-miu[i];
}
mis[i]=mis[i-1]+miu[i];
}
for (int i=1;i<=N;i++)
{
int k=sqrt(i);
for (int j=1;j<=k;j++)
{
int ri=i/j,le=i/(j+1)+1;
F[i]+=(ri-le+1)*j;
}
k=i/(k+1);
for (int j=1;j<=k;j++)
F[i]+=i/j;
}
return;
}
void Solve()
{
if (n>m) swap(n,m);
int rt=sqrt(n),now=m/n,Ri=n;
for (int i=1;i<=rt;i++)
while (true)
{
int le=max(n/(i+1)+1,m/(now+1)+1);
ans+=F[i]*F[now]*(mis[Ri]-mis[le-1]);Ri=le-1;
now=le==1?0:m/Ri;
if (Ri==n/(i+1)) break;
}
for (int i=1;i<=Ri;i++)
ans+=miu[i]*F[n/i]*F[m/i];
printf("%lld\n",ans);
return;
}
int main()
{
t=Read();Pretreat();
while (t--) n=Read(),m=Read(),ans=0,Solve();
return 0;
}
BZOJ3995：智商癌，并没有做出来= =。明明只要分类讨论维护一棵线段树就好了。那个分类讨论感觉很要死的样子。玛德状态这种东西真是玄学，都不知道什么时候会好的。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 60050
#define INF 0x3f7f7f7f
struct Node
{
int a0,a1,a2,a3,a4;
void Set() {a0=a1=a2=a3=a4=INF;}
} a[N*4];
int n,m,col[N],row[N][2];char b[20];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Set(int x,int z)
{a[z].Set();a[z].a0=col[x];a[z].a1=0;}
inline void Mi(int &x,int y)
{x=min(x,y);}
Node Merge(Node x,Node y,int z)
{
Node k;k.Set();
int q=row[z][0],w=row[z][1],e=q+w;q=min(q,w);
Mi(k.a0,x.a0+y.a0+q);Mi(k.a0,x.a0+y.a2+e);
Mi(k.a0,x.a0+y.a1+e);Mi(k.a3,x.a0+y.a1+q);
Mi(k.a3,x.a0+y.a3+q);Mi(k.a3,x.a0+y.a4+e);
Mi(k.a0,x.a1+y.a0+e);Mi(k.a2,x.a1+y.a0+q);
Mi(k.a1,x.a1+y.a1+e);Mi(k.a4,x.a1+y.a1+q);
Mi(k.a2,x.a1+y.a2+e);Mi(k.a3,x.a1+y.a3+e);
Mi(k.a4,x.a1+y.a3+q);Mi(k.a4,x.a1+y.a4+e);
Mi(k.a2,x.a2+y.a0+q);Mi(k.a2,x.a2+y.a1+e);
Mi(k.a4,x.a2+y.a1+q);Mi(k.a2,x.a2+y.a2+e);
Mi(k.a4,x.a2+y.a3+q);Mi(k.a4,x.a2+y.a4+e);
Mi(k.a0,x.a3+y.a0+e);Mi(k.a3,x.a3+y.a1+e);
Mi(k.a3,x.a3+y.a3+e);Mi(k.a2,x.a4+y.a0+e);
Mi(k.a4,x.a4+y.a1+e);Mi(k.a4,x.a4+y.a3+e);
return k;
}
void Set_up(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;
if (x==y) {Set(x,z);return;}
Set_up(x,i,j);Set_up(i+1,y,j+1);
a[z]=Merge(a[j],a[j+1],i);
return;
}
Node Query(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1;
if (x==o&&y==p) return a[z];
if (p<=i) return Query(x,i,j,o,p); else
if (o>i) return Query(i+1,y,j+1,o,p); else
return Merge(Query(x,i,j,o,i),Query(i+1,y,j+1,i+1,p),i);
}
void Modify(int x,int y,int z,int o)
{
int i=x + y >> 1,j=z << 1;
if (x==y) {Set(x,z);return;}
if (o<=i) Modify(x,i,j,o); else Modify(i+1,y,j+1,o);
a[z]=Merge(a[j],a[j+1],i);
return;
}
int main()
{
n=Read();m=Read();
for (int t=0;t<2;t++)
for (int i=1;i<n;i++) row[i][t]=Read();
for (int i=1;i<=n;i++) col[i]=Read();
Set_up(1,n,1);
while (m--)
{
scanf("%s",b);
if (b[0]=='Q')
{
int k=Read(),l=Read();
printf("%d\n",Query(1,n,1,k,l).a0);
} else
{
int k=Read(),l=Read(),q=Read(),w=Read(),e=Read();
if (k>q) swap(k,q); else
if (l>w) swap(l,w);
if (k==q) row[l][k-1]=e; else col[l]=e;
Modify(1,n,1,l);
}
}
return 0;
}
SDOI Round1完结！感觉题目质量还是蛮好的。
BZOJ4034：NOI Day1T2即视感。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define ll long long
int n,m,ss=1,st,fi[N],c[N*2][2],v[N],sg[N][2];
int fa[N],gf[N],li[N],sz[N];ll s[N*4],ad[N*4];
inline int Read()
{
int x=0;char y;bool z=false;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void DFS(int x)
{
sz[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x])
fa[c[i][0]]=x,DFS(c[i][0]),sz[x]+=sz[c[i][0]];
return;
}
void DSF(int x,int y)
{
int k=0;li[sg[x][0]=++st]=x;gf[x]=y;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&sz[c[i][0]]>sz[k]) k=c[i][0];
if (k) DSF(k,y);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x]&&c[i][0]!=k) DSF(c[i][0],c[i][0]);
sg[x][1]=st;
}
void Set_up(int x,int y,int z)
{
int i=x + y >> 1,j=z << 1;
if (x==y) {s[z]=v[li[x]];return;}
Set_up(x,i,j);Set_up(i+1,y,j+1);
s[z]=s[j]+s[j+1];
}
inline void adj(int x,int y,int z)
{
int j=z << 1;
s[z]+=ad[z]*(y-x+1);
if (x!=y) ad[j]+=ad[z],ad[j+1]+=ad[z];
ad[z]=0;
}
void Modify(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==o&&y==p) {ad[z]=u;adj(x,y,z);return;}
if (p<=i) Modify(x,i,j,o,p,u),adj(i+1,y,j+1); else
if (o>i) Modify(i+1,y,j+1,o,p,u),adj(x,i,j); else
Modify(x,i,j,o,i,u),Modify(i+1,y,j+1,i+1,p,u);
s[z]=s[j]+s[j+1];
}
ll Query(int x,int y,int z,int o,int p)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==o&&y==p) return s[z];
if (p<=i) return Query(x,i,j,o,p); else
if (o>i) return Query(i+1,y,j+1,o,p); else
return Query(x,i,j,o,i)+Query(i+1,y,j+1,i+1,p);
}
ll GetAns(int x)
{
ll cnt=0;
while (x)
cnt+=Query(1,n,1,sg[gf[x]][0],sg[x][0]),x=fa[gf[x]];
return cnt;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
DFS(1);DSF(1,1);Set_up(1,n,1);
while (m--)
{
int q,w,e=Read();
if (e<3)
q=Read(),w=Read(),
Modify(1,n,1,sg[q][0],sg[q][e-1],w); else
printf("%lld\n",GetAns(Read()));
}
return 0;
}
BZOJ4033：还是很水= =，n^2的树形DP一下就好了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 2050
#define ll long long
#define INF 12345678987654321LL
int n,m,ss=1,fi[N],c[N*2][3],sz[N];ll mi[N][N],b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int z,int y,int x)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
}
inline ll max(ll x,ll y)
{return x<y?y:x;}
void Merge(int x,int y,ll z)
{
int cnt=sz[x]+sz[y];
memset(b,0,sizeof(b));
for (int i=0;i<=sz[x];i++)
for (int j=0;j<=sz[y];j++)
b[i+j]=max(b[i+j],
mi[x][i]+mi[y][j]+(j*(m-j)+(sz[y]-j)*(n-m-sz[y]+j))*z);
memcpy(mi[x],b,sizeof b);
sz[x]=cnt;
return;
}
void DFS(int x,int fa)
{
sz[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa) DFS(c[i][0],x),Merge(x,c[i][0],c[i][2]);
return;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<n;i++) Line(Read(),Read(),Read());
DFS(1,0);
cout <<mi[1][m]<<endl;
return 0;
}
BZOJ4035：日，这题猜了个结论证了好久发现证明从一开始就是错的= =后来弃疗去看题解很久不知道是在干什么，反正是个玄学题我还是早早弃坑的好。
BZOJ4036：论文题。。简直smg。。
BZOJ4037：en明显这东西可以DP。首先建出递推矩阵，然后设Ai代表前i个数的答案，就可以用A0~i-1转移了。
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
#define P 998244353
#define N 505
#define M 6
struct Matrix
{ll a[M][M];} C,a[10][N],ans[N],I,Emp,a10;
char c[N];int n,m;
Matrix operator* (const Matrix &x,const Matrix &y)
{
memset(C.a,0,sizeof(C.a));
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++)
for (int k=1;k<=m;k++)
C.a[i][k]=(C.a[i][k]+x.a[i][j]*y.a[j][k]%P)%P;
return C;
}
Matrix operator+ (const Matrix &x,const Matrix &y)
{
memset(C.a,0,sizeof(C.a));
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++)
C.a[i][j]=(C.a[i][j]+x.a[i][j]+y.a[i][j])%P;
return C;
}
void Set_up()
{
for (int i=1;i<=n;i++) c[i]-='0';
for (int i=1;i<=m;i++) ans[0].a[i][i]=1;
for (int i=1;i<=m;i++) I.a[i][m]=I.a[i][i-1]=1;
a10=a[0][0]=ans[0];
for (int i=1;i<=9;i++) a10=a10*I,a[i][0]=a10;a10=a10*I;
for (int i=1;i<=n;i++)
{
a[0][i]=ans[0];a[1][i]=a[9][i-1]*a[1][i-1];
for (int j=2;j<10;j++)
a[j][i]=a[j-1][i]*a[1][i];
}
return;
}
int main()
{
cin >>c+1;n=strlen(c+1);cin >>m;
Set_up();
for (int i=1;i<=n;i++)
{
Matrix k=ans[0];
for (int j=i;j>=1;j--)
k=a[c[j]][i-j]*k,ans[i]=ans[i]+k*ans[j-1];
}
cout <<ans[n].a[m][m]<<endl;
return 0;
}
这届HAOI感觉比往届要凶。。
BZOJ4085：直接搞出递推矩阵然后线段树维护一下就好了？感觉既麻烦也好像会卡常的样子。。
BZOJ4084：感觉首先设长点的那个为S，S里面的串先提出前一半的那部分复制一份接在后面，对这部分建出SAM，再对S中多出来的那部分KMP一下看哪些位置可以匹配的。并在SAM里面对应的位置打上标记。然后T的每个串进去跑一遍就好了。画风不对啊，时限只有一秒是smg，O(26n)明显会爆啊。出题人好心态啊。其实感觉也不要变什么地方只要把SAM的部分换成Hash就好了？调的人不行了，感觉应该没什么问题啊。又没有数据这种东西怎么调= =只能理解为是哈希取模的值不够大的锅吧。管他的。。先把代码放上来好了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 5000050
#define M +10086
#define P 10000003
#define ll long long
char a[N],b[N];int fail[N],n,m,lena,lenb,now[P],s[P],mid;
ll ans,Power[N],val[N];
inline void GetHash(int ri,int x)
{
ri-=lena-mid;int le=ri-lenb+1;
if (le<0) return;
ll cnt=(val[ri]-(!le?0:val[le-1])*Power[ri-le+1]%P+P)%P;
if (now[cnt]!=x)
now[cnt]=x,s[cnt]++;
}
void Solve()
{
Power[0]=1;
for (int i=1;i<N;i++) Power[i]=Power[i-1]*M%P;
for (int i=1;i<=n;i++)
{
char *c=a+(i-1)*lena;
fail[0]=-1;
for (int j=mid+1;j<lena;j++)
{
fail[j-mid]=fail[j-1-mid];
while (fail[j-mid]!=-1&&c[fail[j-mid]+1+mid]!=c[j])
fail[j-mid]=fail[fail[j-mid]];
if (c[fail[j-mid]+1+mid]==c[j]) fail[j-mid]++;
}
val[0]=c[0];
for (int j=1;j<mid*2;j++)
val[j]=(val[j-1]*M+c[j%mid]*c[j%mid])%P;
if (mid==lena)
{
for (int j=0;j<mid;j++)
GetHash(mid+j,i);
continue;
}
int Now=-1;
for (int j=0;j<mid*2;j++)
{
if (Now==lena-mid-1) Now=fail[Now];
while (Now!=-1&&c[Now+mid+1]!=c[j%mid])
Now=fail[Now];
if (c[Now+mid+1]==c[j%mid]) Now++;
if (Now==lena-mid-1) GetHash(j,i);
}
}
for (int i=1;i<=m;i++)
{
ll cnt=0;char *c=b+(i-1)*lenb;
for (int j=0;j<lenb;j++)
cnt=(cnt*M%P+c[j]*c[j])%P;
ans+=s[cnt];
}
return;
}
void Swap()
{
swap(a,b);swap(n,m);swap(lena,lenb);
for (int i=1;i<=n;i++)
{
char *c=a+(i-1)*lena;
for (int j=0,k=lena-1;j!=k;j++,k--) swap(c[j],c[k]);
}
for (int i=1;i<=m;i++)
{
char *c=b+(i-1)*lenb;
for (int j=0,k=lenb-1;j!=k;j++,k--) swap(c[j],c[k]);
}
}
int main()
{
cin >>n>>m>>lena>>lenb;mid=lena + lenb >> 1;
for (int i=1;i<=n;i++) scanf("%s",a+(i-1)*lena);
for (int i=1;i<=m;i++) scanf("%s",b+(i-1)*lenb);
if (lena<lenb) Swap();
Solve();cout <<ans<<endl;
return 0;
}
BZOJ4086：这题什么鬼。。en我想说我会暴力我自豪。。正解是容斥+分类讨论？不明觉厉
玛德SDOI Round1还正常，Round2D1D2简直smg。弃坑了弃坑了！！
剩下的里面FJOI看通过人数就已经弃疗了。最近看的这几套题简直啃的人愉悦异常啊。
BZOJ3926：感觉可以枚举叶子节点的n-1个排列使得这些排列每个数的后继各不相同？然后建出来的SAM应该就是O(20cn)的吧。。标算好像是总的建出一棵trie树看起来比我的节点数应该要优些。。无脑背板果然被D了，get新姿势，last是可以替换成另外一个节点的，所以直接在trie树某个父亲节点对应的SAM节点下面直接插就好了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define M 4000050
#define ll long long
#define P 10
int n,m,fi[N],c[N*2][2],cl[N],ss=1,d[N];ll ans;
struct SAM
{
int go[M][P],suf[M],val[M],root,cur;
SAM() {cur=1;root=cur++;}
int extend(int p,int w)
{
int np=cur++;val[np]=val[p]+1;
while (p&&!go[p][w]) go[p][w]=np,p=suf[p];
if (!p) suf[np]=root; else
{
int q=go[p][w];
if (val[q]==val[p]+1)
suf[np]=q; else
{
int nq=cur++;
memcpy(go[nq],go[q],sizeof go[q]);
suf[nq]=suf[q];suf[q]=suf[np]=nq;
val[nq]=val[p]+1;
while (p&&go[p][w]==q)
go[p][w]=nq,p=suf[p];
}
}
return np;
}
void Solve()
{for (int i=2;i<cur;i++) ans+=val[i]-val[suf[i]];}
} Aha;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;d[x]++;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;d[y]++;
}
void DFS(int x,int y,int z)
{
int k=Aha.extend(z,cl[x]);
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=y) DFS(c[i][0],x,k);
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++) cl[i]=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
for (int i=1;i<=n;i++)
if (d[i]==1) DFS(i,0,1);
Aha.Solve();
cout <<ans<<endl;
return 0;
}
BZOJ3925：尼玛去年线性回归今年考求导是要组ZJ数学队么。。不会不会
BZOJ3924：感觉我简直数据结构无能= =en度数最大为20，满满的点分治即视感。但是尼玛就是搞不懂到底怎么搞的，为什么能在分治树上面移动来求出重心啊。。其实后来回来看的时候才发现之前一直脑抽了，en这肯定是可以做的啊。。感觉自己没救了。。首先找带权重心就是动态点分治，每次修改的时候树剖/LCT搞一搞，每个点维护子树和，然后找重心就是log层每层对比权值总和的一半和这个节点的子树和。log^2的。然后怎么求路径和呢？是的，怎么求呢？。。所以还是太弱。。只要把移动的时候的子树外的节点信息都放到子树内跟它第一个相连的节点那里，然后回溯的时候再删除就好了。。所以是O(n log^2 n)的。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 100050
#define M 20
#define ll long long
ll Ans[N],Sub[N][M],ans;
int dis[N][M],gf[N][M],cnt[N],fi[N],c[N*2][3],s[N],n,m,ss;
bool b[N],vis[N];int li[N],sg[N],Up[N][M],tot;
inline int Read()
{
int x=0;char y;bool z=false;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline void Line(int z,int y,int x)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
}
int DFS(int x,int y)
{
int le=1,ri=1;
li[1]=x;b[x]=true;dis[x][y]=0;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (!b[c[i][0]]&&!vis[c[i][0]])
{
b[c[i][0]]=true;
dis[c[i][0]][y]=dis[li[le]][y]+c[i][2];
li[++ri]=c[i][0];
}
for (int i=1;i<=ri;i++) b[li[i]]=false;
return ri;
}
int Get_Root(int x,int Cnt)
{
for (int i=Cnt;i>=1;i--)
{
s[li[i]]=true;
for (int j=fi[li[i]];j;j=c[j][1])
if (!vis[c[j][0]]) s[li[i]]+=s[c[j][0]];
}
int rt=li[1];
while (true)
{
bool flag=false;
for (int i=fi[rt];i;i=c[i][1])
if (!vis[c[i][0]]&&s[c[i][0]]<s[rt]&&s[c[i][0]]*2>=Cnt)
{flag=true;rt=c[i][0];break;}
if (!flag) break;
}
for (int i=1;i<=Cnt;i++) s[li[i]]=false;
return rt;
}
void Set_up(int x,int y)
{
int Cnt=DFS(x,y),rt=Get_Root(x,Cnt);DFS(rt,y);
for (int i=1;i<=Cnt;i++) gf[li[i]][y]=rt;
sg[rt]=y;vis[rt]=true;
for (int i=fi[rt];i;i=c[i][1]) Up[c[i][0]][y]=c[i][0];
for (int i=2;i<=Cnt;i++)
for (int j=fi[li[i]];j;j=c[j][1])
if (!vis[c[j][0]]&&!Up[c[j][0]][y])
Up[c[j][0]][y]=Up[li[i]][y];
for (int i=fi[rt];i;i=c[i][1])
if (!vis[c[i][0]]) Set_up(c[i][0],y+1);
return;
}
void Modify(int x,int y,int z)
{
for (int i=z;i<=sg[x];i++)
cnt[gf[x][i]]+=y,Ans[gf[x][i]]+=1LL*y*dis[x][i],
Sub[Up[x][i]][i]+=1LL*y*(dis[x][i]-dis[Up[x][i]][i]);
return;
}
void Get_Ans(int x)
{
int k=0,l=sg[x],e,w;
for (int i=fi[x];i;i=c[i][1])
if (sg[c[i][0]]>l&&cnt[gf[c[i][0]][l+1]]*2>=tot)
{k=c[i][0];w=c[i][2];break;}
if (!k) {printf("%lld\n",ans+Ans[x]);return;}
e=cnt[x]-cnt[gf[k][l+1]];
ans+=Ans[x]-Sub[k][l]+1LL*(e-cnt[gf[k][l+1]])*w;
Modify(k,e,l+1);
Get_Ans(gf[k][l+1]);
Modify(k,-e,l+1);
return;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<n;i++) Line(Read(),Read(),Read());
Set_up(1,1);
while (m--)
{
int k=Read(),l=Read();tot+=l;ans=0;
Modify(k,l,1);Get_Ans(gf[1][1]);
}
return 0;
}
下面就做一做数学相关冷静一下
BZOJ1101：水题。。反演一下然后分成根号n段然后就可以了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 50050
int t,n,m,d,st,Prime[N],miu[N],mis[N];bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void Pretreat()
{
miu[1]=mis[1]=1;
for (int i=2;i<=N-50;i++)
{
if (!b[i]) miu[Prime[++st]=i]=-1;
for (int j=1;Prime[j]*i<N;j++)
{
b[Prime[j]*i]=true;
if (i%Prime[j]==0) break;
miu[i*Prime[j]]=-miu[i];
}
mis[i]=mis[i-1]+miu[i];
}
return;
}
int Solve()
{
if (n>m) swap(n,m);n/=d;m/=d;
int cnt=0,rt=sqrt(n),ri=n,now=m/n;
for (int i=1;i<=rt;i++)
do
{
int le=max(n/(i+1)+1,m/(now+1)+1);
cnt+=(mis[ri]-mis[le-1])*(n/le)*(m/le);
ri=le-1;now=ri?m/ri:0;
} while (ri!=n/(i+1));
for (int i=1;i<=ri;i++)
cnt+=miu[i]*(n/i)*(m/i);
return cnt;
}
int main()
{
t=Read();Pretreat();
while (t--)
n=Read(),m=Read(),d=Read(),printf("%d\n",Solve());
return 0;
}
BZOJ2693：感觉自己在一顿乱推，然后莫名其妙地就推出来了。首先把lcm化成gcd，然后提出gcd。变成：Σ(k=1 to n)Σ(i=1 to n/k)Σ(j=1 to m/k)i*j*k*[gcd(i,j)==1]。然后后面东西反演一下把式子变一下型：Σ(k=1 to n)kΣ(t=1 to n/k)μ(t)*t^2*Sum(n/kt)*Sum(m/kt)，其中Sum(x)就是1到x的和。接着把kt提到前面来变成：Σ(i=1 to n)Sum(n/i)*Sum(m/i)*i*Σ(k|i)μ(k)*k，后面的东西因为是积性函数所以直接O(n)预处理，至于证明就是因为μ是积性函数，然后y=x也是积性函数，所以μ(k)*k也是积性函数，然后后面那个Σ我们可以套入Dirichlet卷积里面，en，因为y=1也是积性函数。前面的东西也明显分块一下就好了。。然后就是O(T*sqrt(N)+N)的了。。en话说一个东西我连续推错两次我是不是要废？然后拍的时候还get了新的分块技巧。感觉短多了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 10000050
#define P 100000009
#define ll long long
int Prime[N],st,t,n,m;ll F[N],s[N],ans;bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void Pretreat()
{
F[1]=s[1]=1;
for (int i=2;i<=N-50;i++)
{
if (!b[i]) Prime[++st]=i,F[i]=((ll)i*(1-i)%P+P)%P;
for (int j=1;j<=st&&Prime[j]*i<N;j++)
if (i%Prime[j])
F[Prime[j]*i]=F[Prime[j]]*F[i]%P,
b[Prime[j]*i]=true; else
{
F[Prime[j]*i]=Prime[j]*F[i]%P;
b[Prime[j]*i]=true;
break;
}
s[i]=(s[i-1]+F[i])%P;
}
return;
}
inline ll Sum(ll x)
{return x*(x+1)/2%P;}
ll Solve()
{
if (n>m) swap(n,m);
int ri;ans=0;
for(int i=1;i<=n;i=ri+1)
ri=min(n/(n/i),m/(m/i)),
ans=(ans+Sum(n/i)*Sum(m/i)%P*(s[ri]-s[i-1]+P)%P)%P;
return ans;
}
int main()
{
t=Read();Pretreat();
while (t--)
n=Read(),m=Read(),printf("%lld\n",Solve());
return 0;
}
BZOJ2111：式子很水，组合数随便搞搞。虽然知道会有n>p的情况但是忘记了有卢卡斯定理了。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1000050
#define fr first
#define sc second
#define ll long long
int n,P;ll JC[N],INV[N];
void Pretreat()
{
JC[0]=INV[0]=JC[1]=INV[1]=1;
for (int i=2;i<=min(N-50,P-1);i++)
JC[i]=JC[i-1]*i%P,INV[i]=(P-P/i)*INV[P%i]%P;
for (int i=2;i<=min(N-50,P-1);i++) INV[i]=INV[i-1]*INV[i]%P;
}
inline ll C(int x,int y)
{return JC[x]*INV[y]%P*INV[x-y]%P;}
inline ll ZHS(int x,int y)
{
ll cnt=1;
while (x) cnt=(cnt*C(x%P,y%P))%P,x/=P,y/=P;
return cnt;
}
pair <ll,int> DFS(int x)
{
if (x*2>=n) return make_pair(1,x*2==n?2:1);
pair <ll,int> le=DFS(x*2),ri=DFS(x*2+1);
int cnt=le.sc+ri.sc+1;
return make_pair(le.fr*ri.fr%P*ZHS(cnt-1,le.sc)%P,cnt);
}
int main()
{
cin >>n>>P;Pretreat();
cout <<DFS(1).fr<<endl;
return 0;
}
BZOJ3142：枚举所求序列的差分算出每个差分的可出现位置数加起来，这个式子化下简就好了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
ll n,t,m,P;
ll Quick_Power(ll x,ll y)
{
ll z=1;
while (y)
z=y&1?z*x%P:z,x=x*x%P,y >>= 1;
return z;
}
int main()
{
cin >>n>>t>>m>>P;n%=P;
if (!m) cout <<0<<endl; else
if (m==1) cout <<n<<endl; else
cout <<Quick_Power(m,t-2)*(n*m%P-m*(m+1)/2%P*(t-1)%P+P)%P<<endl;
return 0;
}
BZOJ3309：式子随便反演一下变成两个下取整和一个Dirichlet卷积的乘积的求和。但是卷积并不是积性函数。所以打表找规律可以发现：除了F(0)=0之外其余的质因数次数不相同的卷积值都为0，相同的值为(-1)^(质数个数+1)。然后线性筛随便搞搞就好了。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10000050
#define ll long long
ll ans,s[N];int F[N],Prime[N],n,m,st,t,a[N],c[N];bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void Pretreat()
{
for (int i=2;i<=N-50;i++)
{
if (!b[i]) F[Prime[++st]=a[i]=i]=1,c[i]=1;
for (int j=1;j<=st&&i*Prime[j]<N;j++)
{
b[i*Prime[j]]=true;
if (i%Prime[j]==0)
{
a[i*Prime[j]]=a[i];
c[i*Prime[j]]=c[i]*Prime[j];
if (c[i*Prime[j]]%a[i]==0)
c[i*Prime[j]]/=a[i];
if (c[i*Prime[j]]==1)
F[i*Prime[j]]=F[a[i]];
break;
} else
{
a[i*Prime[j]]=a[i]*Prime[j];
c[i*Prime[j]]=i/a[i];
if (c[i*Prime[j]]==1) F[i*Prime[j]]=-F[i];
}
}
s[i]=s[i-1]+F[i];
}
return;
}
ll Solve()
{
if (n>m) swap(n,m);
int ri;ans=0;
for (int i=1;i<=n;i=ri+1)
ri=min(n/(n/i),m/(m/i)),
ans+=n/i*(ll)(m/i)*(s[ri]-s[i-1]);
return ans;
}
int main()
{
t=Read();Pretreat();
while (t--)
n=Read(),m=Read(),printf("%lld\n",Solve());
return 0;
}
然后，换上口味清淡的HNOI赶快把这个坑填完好了。。
BZOJ3571：第一题就不会了。后来才知道是生成树姿势不够，赶快补一波论文。可以看唐文斌2012年的冬令营课件。这题虽然不是最小乘积生成树但是都一样的做法。首先按A和按B分别求一次最小权匹配。然后更改权值再递归求最远点。递归到距离非正。复杂度好玄学的样子。。好久没写过费用流了。。调都没调一遍写过也是挺爽，就是TM式子搞错了刚了好久才知道。。出现过几次这种情况了。。下次尼玛真的要先检查思路。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 160
#define INF 0x3f7f7f7f
#define ll long long
#define fr first
#define sc second
queue <int> li;bool b[N];
int la[N],c[N*N][4],fi[N],v[N][N][2],h[N],ss,n,m,t,S,T,ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z,int o)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;c[ss][3]=o;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=0;c[ss][3]=-o;fi[y]=ss;
}
void Rebuild(int x,int y)
{
int e=2;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++,e+=2)
c[e^1][3]=-(c[e][3]=x*v[i][j][0]+y*v[i][j][1]);
return;
}
bool SPFA()
{
for (int i=1;i<=n*2;i++) h[i]=INF;h[T]=INF;
h[S]=0;b[S]=true;li.push(S);
while (!li.empty())
{
int k=li.front();b[k]=false;li.pop();
for (int i=fi[k];i;i=c[i][1])
if (c[i][2]&&c[i][3]+h[k]<h[c[i][0]])
{
h[c[i][0]]=h[k]+c[i][3];la[c[i][0]]=i;
if (!b[c[i][0]])
b[c[i][0]]=true,li.push(c[i][0]);
}
}
return h[T]!=INF;
}
void Solve()
{
int q=T,w=INF;
while (q!=S)
w=min(w,c[la[q]][2]),q=c[la[q]^1][0];q=T;
while (q!=S)
c[la[q]][2]-=w,c[la[q]^1][2]+=w,q=c[la[q]^1][0];
return;
}
pair <int,int> Flow()
{
while (SPFA()) Solve();int e=2,s0=0,s1=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++,e+=2)
if (!c[e][2])
c[e][2]=1,c[e^1][2]=0,s0+=v[i][j][0],s1+=v[i][j][1];
ans=min(ans,s0*s1);
for (;e<=ss;e+=2) c[e][2]+=c[e^1][2],c[e^1][2]=0;
return make_pair(s0,s1);
}
void DFS(pair <int,int> x,pair <int,int> y)
{
int q=x.sc-y.sc,w=y.fr-x.fr,e=2;Rebuild(q,w);
pair <int,int> k=Flow();
if (-k.fr*(ll)q-k.sc*w-x.fr*y.sc+x.sc*y.fr>0)
DFS(x,k),DFS(k,y);
return;
}
int main()
{
t=Read();S=N-1;T=N-2;
while (t--)
{
ss=1;memset(fi,0,sizeof(fi));
n=Read();ans=INF;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
Line(i,j+n,1,v[i][j][0]=Read());
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) v[i][j][1]=Read();
for (int i=1;i<=n;i++)
Line(S,i,1,0),Line(i+n,T,1,0);
pair <int,int> k=Flow(),l;Rebuild(0,1);
l=Flow();DFS(k,l);
cout <<ans<<endl;
}
return 0;
}
BZOJ3572：感觉像是每次建出一棵虚树然后询问什么的就是BFS求出虚树每个节点最近节点还有距离。询问什么的倍增搞搞？SB东西调我好久。真是手贱的快感。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 300050
#define M 20
#define INF 0x3f7f7f7f
int s[N][M],h[N],fa[N][M],sg[N],qu[N],fi[N],c[N*2][2];
int Ans[N],mi[N][2],sz[N],rf[N][2],Stack[N],sn,m,n,Qu[N];
int Fi[N],C[N*2][2],a2[M],li[N],rt,st,ss=1,cnt;bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
void DFS(int x)
{
h[x]=h[fa[x][0]]+1;sz[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
fa[c[i][0]][0]=x,DFS(c[i][0]),sz[x]+=sz[c[i][0]];
sg[x]=++st;return;
}
void Pretreat()
{
DFS(1);
for (int i=2;i<=n;i++)
s[i][0]=sz[fa[i][0]]-sz[i];
for (int i=1;i<M;i++)
for (int j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1],
s[j][i]=s[j][i-1]+s[fa[j][i-1]][i-1];
}
inline bool cmp(int x,int y)
{return sg[x]<sg[y];}
int LCA(int x,int y)
{
if (h[x]<h[y]) swap(x,y);
for (int i=M-1;i>=0&&h[x]!=h[y];i--)
if (h[fa[x][i]]>=h[y]) x=fa[x][i];
if (x!=y)
{
for (int i=M-1;i>=0;i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
x=fa[x][0];
}
return x;
}
inline void line(int x,int y)
{
rf[x][0]=y;rf[x][1]=h[x]-h[y];
C[++ss][0]=y;C[ss][1]=Fi[x];Fi[x]=ss;
C[++ss][0]=x;C[ss][1]=Fi[y];Fi[y]=ss;
}
void Set_up()
{
int ri=1;Stack[ri]=qu[1];ss=1;st=0;
for (int i=2;i<=cnt;i++)
{
int k=LCA(qu[i-1],qu[i]);
while (ri&&h[Stack[ri]]>h[k])
line(Stack[ri],ri>1&&h[Stack[ri-1]]>h[k]?
Stack[ri-1]:k),li[++st]=Stack[ri--];
if (Stack[ri]!=k) Stack[++ri]=k;
if (Stack[ri]!=qu[i]) Stack[++ri]=qu[i];
}
while (--ri) line(Stack[ri+1],Stack[ri]),
li[++st]=Stack[ri+1];li[++st]=rt=Stack[1];
rf[rt][0]=0;rf[rt][1]=N;
return;
}
inline void Update(int x,int y,int z)
{
if (mi[x][1]>mi[y][1]+z||(mi[x][1]==mi[y][1]+z&&
mi[x][0]>mi[y][0]))
mi[x][0]=mi[y][0],mi[x][1]=mi[y][1]+z;
}
void DSF(int x)
{
if (b[x]) mi[x][0]=x,mi[x][1]=0; else mi[x][1]=INF;
for (int i=Fi[x];i;i=C[i][1])
if (C[i][0]!=rf[x][0])
DSF(C[i][0]),Update(x,C[i][0],rf[C[i][0]][1]);
}
void DSS(int x)
{
if (x!=rt) Update(x,rf[x][0],rf[x][1]);
for (int i=Fi[x];i;i=C[i][1])
if (C[i][0]!=rf[x][0]) DSS(C[i][0]);
return;
}
inline bool Check(int x,int y,int z)
{
int k=mi[y][1]+h[y]-h[x],l=mi[z][1]+h[x]-h[z];
return k<l||(k==l&&mi[y][0]<mi[z][0]);
}
int Get_Ans(int x)
{
int Cnt=sz[x],now=x,tot=0;
for (int i=Fi[x];i;i=C[i][1])
if (C[i][0]!=rf[x][0])
tot+=Get_Ans(C[i][0]);Cnt-=tot;
if (x!=rt)
for (int i=M-1;i>=0;i--)
if (h[fa[now][i]]>h[rf[x][0]]&&Check(fa[now][i],x,rf[x][0]))
Cnt+=s[now][i],now=fa[now][i];
Ans[mi[x][0]]+=Cnt;
return Cnt+tot;
}
void Solve()
{
DSF(rt);DSS(rt);Get_Ans(rt);
Ans[mi[rt][0]]+=sz[1]-sz[rt];
for (int i=1;i<=st;i++) Fi[li[i]]=0;
return;
}
int main()
{
n=Read();a2[0]=1;
for (int i=1;i<M;i++) a2[i]=a2[i-1] << 1;
for (int i=1;i<n;i++) Line(Read(),Read());
m=Read();Pretreat();
int Tot=0;
while (m--)
{
cnt=Read();Tot+=cnt;
for (int i=1;i<=cnt;i++) b[qu[i]=Qu[i]=Read()]=true;
sort(qu+1,qu+cnt+1,cmp);
Set_up();Solve();
for (int i=1;i<=cnt;i++)
printf("%d ",Ans[Qu[i]]),b[Qu[i]]=false,
Ans[Qu[i]]=0;
puts("");
}
return 0;
}
BZOJ3573：题面长的一笔。如果没理解错题意我感觉就只要每个节点存下其到一号节点的所有节点儿子数乘积，这东西随便模两个数就好了。然后乘以自身的值最后排个序判个重？
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 500050
#define P 998244353
#define M 1000000007
#define ll long long
#define fr first
#define sc second
pair <int,int> li[N];
int ans,n,m,ss=1,d[N],fi[N],c[N*2][2],v[N];ll h[N][2];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;d[x]++;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;d[y]++;
}
void DFS(int x,int fa)
{
d[x]-=fa>0;
h[x][0]=h[fa][0]*d[x]%P;h[x][1]=h[fa][1]*d[x]%M;
li[x].fr=h[fa][0]*v[x]%P;li[x].sc=h[fa][1]*v[x]%M;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa) DFS(c[i][0],x);
}
int main()
{
n=Read();
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
h[0][1]=h[0][0]=1;DFS(1,0);
sort(li+1,li+n+1);ans=n;
for (int i=1;i<=n;i++)
{
int k=i;
while (k<n&&li[k+1]==li[k]) k++;
ans=min(ans,n-k+i-1);i=k;
}
cout <<ans<<endl;
return 0;
}
BZOJ3574：为什么我感觉只要判断前缀后缀相不相同？就是每个字符串从前数从后数不到*的部分。感觉这东西能证：去掉前后缀每个字符串就只剩下一些*号开头*号结尾的东西了，所以我们就构造一个字符串是所有字符串的中间这东西拼起来的串。en貌似还要特判掉中间没有*号的一些情况，也就是一波KMP。话说BZOJ上面的题面能看。。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define M 30000050
char b[M],*a[N],c[M];int n,m,t,fail[M],len[N],bg[N],ed[N];
bool Check_Pre(int x,int y)
{
for (int i=0;i<bg[x];i++)
if (a[x][i]!=a[y][i]) return false;
return true;
}
bool Check_Suf(int x,int y)
{
for (int i=len[x]-1;i>=ed[x];i--)
if (a[x][i]!=a[y][len[y]-len[x]+i]) return false;
return true;
}
bool Solve0(int x,int y)
{
for (int i=1;i<=n;i++)
if (!Check_Pre(i,x)||!Check_Suf(i,y)) return false;
return true;
}
bool Solve1(int x)
{
for (int i=1;i<=n;i++)
if (ed[i]==-1)
{
if (len[i]!=len[x]) return false;
for (int j=0;j<len[i];j++)
if (a[i][j]!=a[x][j]) return false;
} else
{
if (bg[i]>=len[x]||!Check_Pre(i,x)||
len[i]-ed[i]>len[x]||!Check_Suf(i,x))
return false;
int le=bg[i]+1,now=bg[i]+1;
while (true)
{
while (le<len[i]&&a[i][le]=='*') le++;
if (le>=ed[i]) break;
int k=le,l=-1;
while (a[i][k+1]!='*') k++;
if (now+k-le+1>len[x]) return false;
fail[0]=-1;
for (int j=1;j<=k-le;j++)
{
fail[j]=fail[j-1];
while (fail[j]!=-1&&a[i][j+le]!=
a[i][fail[j]+1+le]) fail[j]=fail[fail[j]];
if (a[i][j+le]==a[i][fail[j]+1+le])
fail[j]++;
}
for (;now<len[x];now++)
if (l==k-le) break; else
{
while (l!=-1&&a[i][l+le+1]!=a[x][now])
l=fail[l];
if (a[i][l+le+1]==a[x][now]) l++;
}
if (l!=k-le||now>len[x]-(len[i]-ed[i]))
return false;
le=k+1;
}
}
return true;
}
bool Solve()
{
int rt=0,ma0=0,ma1=0;
for (int i=1;i<=n;i++)
{
bg[i]=len[i];ed[i]=-1;
for (int j=0;j<len[i];j++)
if (a[i][j]=='*')
bg[i]=min(bg[i],j-1),ed[i]=max(ed[i],j+1);
if (ed[i]==-1) rt=i; else
{
if (!ma0||bg[i]+1>bg[ma0]+1) ma0=i;
if (!ma1||len[i]-ed[i]>len[ma1]-ed[ma1]) ma1=i;
}
}
if (!rt) return Solve0(ma0,ma1); else return Solve1(rt);
}
int main()
{
cin >>t;
while (t--)
{
cin >>n;a[1]=&b[0];
for (int i=1;i<=n;i++)
scanf("%s",a[i]),len[i]=strlen(a[i]),
a[i+1]=a[i]+len[i];
puts(Solve()?"Y":"N");
}
return 0;
}
BZOJ3575：不行了，调了好久，感觉我的做法确实是有问题的。后来Orz了ydc的做法，感觉ydc真是太神了。en具体细节就看他的题解吧。只不过复杂度确实是个大玄学，我反正不知道复杂度，但是感觉随机情况下应该比较快吧。至于这样玩SPFA的正确性，因为反正那些最短路径边碰到就会停止所以正确性是没有问题的。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 100050
#define M 200050
#define INF 0x3f7f7f7f
struct Node
{int x,y;};
priority_queue <Node> Aha;
queue <int> li;bool b[N],d[N];
int n,m,p,ss,t,fi[N],c[M][3],dis[N],ln[N],pre[N],suf[N];
int cur[N],Po[N],sg[N],Li[N];
bool operator< (const Node &A,const Node &B)
{return A.x>B.x;}
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int z,int y,int x)
{c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;}
void SPFA(int x)
{
int ri=0;
li.push(x);dis[x]=pre[x];b[x]=true;
while (!li.empty())
{
int k=li.front();b[k]=false;li.pop();
for (int i=fi[k];i;i=c[i][1])
if (d[c[i][0]])
{
if (dis[k]+c[i][2]+suf[c[i][0]]<dis[c[i][0]]&&
sg[c[i][0]]>sg[x]&&i!=ln[t])
{
dis[c[i][0]]=suf[c[i][0]]+c[i][2]+dis[k];
if (cur[c[i][0]]!=t)
cur[Li[++ri]=c[i][0]]=t;
}
} else
if (dis[k]+c[i][2]<dis[c[i][0]])
{
dis[c[i][0]]=dis[k]+c[i][2];
if (!b[c[i][0]])
b[c[i][0]]=true,li.push(c[i][0]);
}
}
for (int i=1;i<=ri;i++)
Aha.push((Node){dis[Li[i]],sg[Li[i]]});
return;
}
int main()
{
n=Read();m=Read();p=Read();d[sg[Po[1]=1]=1]=true;
for (int i=1;i<=m;i++) Line(Read(),Read(),Read());
for (int i=1;i<=p;i++)
sg[Po[i+1]=c[ln[i]=Read()][0]]=i+1,d[Po[i+1]]=true;
for (int i=1;i<=n;i++) dis[i]=INF;
for (int i=1;i<=p;i++) pre[Po[i+1]]=pre[Po[i]]+c[ln[i]][2];
for (int i=p;i>=1;i--) suf[Po[i]]=suf[Po[i+1]]+c[ln[i]][2];
for (t=1;t<=p;t++)
{
SPFA(Po[t]);
while (!Aha.empty()&&Aha.top().y<=t) Aha.pop();
if (Aha.empty()) puts("-1"); else
printf("%d\n",Aha.top().x);
}
return 0;
}
BZOJ3576：半年前的我都会做！我记得好像是SG函数搞搞，然后还有个什么分块吧。因为很早以前做过了所以就不放上来了。
HNOI2014完结。
果然HNOI的画风才是最好的。不像浙江那样，人类何苦互相伤害嘛。（好吧其实事实是窝只会刷水= =
下面找些看上去比较好玩的题目好了。
BZOJ3622：一开始以为是之前NOIP考过的一个DP题，于是一开始wa了n遍，后来做这题的时候意识比较模糊了，结果犯逗没想出正解= =。明明只要在那个做法上面改动一点点就好了的。总有种把这题浪费了的感觉
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 2050
#define P 1000000009
#define ll long long
ll s[N][N],JC[N],C[N][N];int v[N],t[N],n,m;
inline int Read()
{
int x=0;char y;bool z=false;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
int main()
{
n=Read();m=Read();JC[0]=1;
for (int i=0;i<N;i++) C[i][0]=1;
for (int i=1;i<N;i++)
for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
for (int i=1;i<N;i++) JC[i]=JC[i-1]*i%P;
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<=n;i++) t[i]=Read();
if ((n-m)&1) {puts("0");return 0;}
m=m+(n - m >> 1);
sort(v+1,v+n+1);sort(t+1,t+n+1);
int ri=0;s[0][0]=1;
for (int i=1;i<=n;i++)
{
while (ri<n&&v[i]>t[ri+1]) ri++;s[i][0]=1;
for (int j=1;j<=ri;j++)
s[i][j]=(s[i-1][j]+s[i-1][j-1]*(ri-j+1))%P;
}
for (int i=0;i<=n;i++) s[n][i]=s[n][i]*JC[n-i]%P;
for (int i=n-1;i>=0;i--)
for (int j=i+1;j<=n;j++)
s[n][i]=(s[n][i]-s[n][j]*C[j][i]%P+P)%P;
cout <<s[n][m]<<endl;
return 0;
}
BZOJ3636：一直在想些奇怪的东西但是并没有想出来，TM无脑分治就好了啊。为毛每次我写东西总是会刚那种最麻烦最容易出错的写法然后调又调不出。代码能力太弱TAT
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define N 100050
#define M 52
#define fr first
#define sc second
vector <pair <int,int> > a[N];
int ma[N][M],n,m,p,v[N],s[N],Ans[N];
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
void Solve(int x,int y)
{
if (x==y) return;
int k=x + y >> 1;
for (int i=1;i<=p;i++) ma[k][i]=0;
for (int i=k-1;i>=x;i--)
for (int j=1;j<=p;j++)
ma[i][j]=max(ma[i+1][j],i+p-1<=k-j?s[i]+ma[i+p][j]:0);
for (int i=k+1;i<=y;i++)
for (int j=1;j<=p;j++)
ma[i][j]=max(ma[i-1][j],i-p+1>=k+j?s[i-p+1]+ma[i-p][j]:0);
for (int i=x;i<=k;i++)
{
int sz=a[i].size();
for (int j=sz-1;j>=0&&a[i][j].fr>k;j--)
{
int sg=a[i][j].sc,ed=a[i][j].fr;
Ans[sg]=ma[i][1]+ma[ed][1];
for (int e=k;e>=max(i,k-p+1);e--)
Ans[sg]=max(Ans[sg],(e+p-1>ed?0:s[e]+ma[ed][p-k+e])+
ma[i][k-e+1]);
a[i].pop_back();
}
}
Solve(x,k);Solve(k+1,y);
return;
}
int main()
{
n=Read();p=Read();
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<=n;i++)
for (int j=0;j<p;j++) s[i]+=v[i+j];
m=Read();
for (int i=1;i<=m;i++)
{
int k=Read(),l=Read();
if (k==l) Ans[i]=p==1?max(v[k],0):0; else
a[k].push_back(make_pair(l,i));
}
for (int i=1;i<=n;i++) sort(a[i].begin(),a[i].end());
Solve(1,n);
for (int i=1;i<=m;i++) printf("%d\n",Ans[i]);
return 0;
}
BZOJ3674：en首先可持久化那个father数组，然后按深度启发式合并并查集就好了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
#define M 10000050
#define fr first
#define sc second
struct Node
{int v;Node* c[2];} *Gf[N],statePool[M],*Cur;
int n,m,t,ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
Node* Set_up(int x,int y)
{
int i=x + y >> 1;Node* j=Cur++;j->v=-1;
if (x!=y) j->c[0]=Set_up(x,i),j->c[1]=Set_up(i+1,y);
return j;
}
int Query(int x,int y,Node* z,int o)
{
int i=x + y >> 1;
if (x==y) return z->v; else
return o>i?Query(i+1,y,z->c[1],o):Query(x,i,z->c[0],o);
}
pair <int,int> Find(int x)
{
while (true)
{
int k=Query(1,n,Gf[t-1],x);
if (k<0) return make_pair(x,k); else x=k;
}
}
Node* Insert(int x,int y,Node* z,int o,int p)
{
int i=x + y >> 1;Node *j=Cur++;
if (x==y) j->v=p; else
if (o>i)
j->c[1]=Insert(i+1,y,z->c[1],o,p),j->c[0]=z->c[0]; else
j->c[0]=Insert(x,i,z->c[0],o,p),j->c[1]=z->c[1];
return j;
}
void Merge(pair <int,int> x,pair <int,int> y)
{
if (x.sc>y.sc) swap(x,y);
Gf[t]=Insert(1,n,Gf[t-1],y.fr,x.fr);
Gf[t]=Insert(1,n,Gf[t],x.fr,min(y.sc-1,x.sc));
return;
}
int main()
{
n=Read();m=Read();
Cur=statePool;Gf[0]=Set_up(1,n);
for (t=1;t<=m;t++)
{
int e=Read();
if (e==1) Merge(Find(Read()^ans),Find(Read()^ans)); else
if (e==2) Gf[t]=Gf[Read()^ans]; else
printf("%d\n",ans=(Find(Read()^ans).fr==
Find(Read()^ans).fr)),Gf[t]=Gf[t-1];
}
return 0;
}
BZOJ3673：en好吧是凑数的，跟上题代码只删掉了那个强制在线
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
#define M 10000050
#define fr first
#define sc second
struct Node
{int v;Node* c[2];} *Gf[N],statePool[M],*Cur;
int n,m,t,ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
Node* Set_up(int x,int y)
{
int i=x + y >> 1;Node* j=Cur++;j->v=-1;
if (x!=y) j->c[0]=Set_up(x,i),j->c[1]=Set_up(i+1,y);
return j;
}
int Query(int x,int y,Node* z,int o)
{
int i=x + y >> 1;
if (x==y) return z->v; else
return o>i?Query(i+1,y,z->c[1],o):Query(x,i,z->c[0],o);
}
pair <int,int> Find(int x)
{
while (true)
{
int k=Query(1,n,Gf[t-1],x);
if (k<0) return make_pair(x,k); else x=k;
}
}
Node* Insert(int x,int y,Node* z,int o,int p)
{
int i=x + y >> 1;Node *j=Cur++;
if (x==y) j->v=p; else
if (o>i)
j->c[1]=Insert(i+1,y,z->c[1],o,p),j->c[0]=z->c[0]; else
j->c[0]=Insert(x,i,z->c[0],o,p),j->c[1]=z->c[1];
return j;
}
void Merge(pair <int,int> x,pair <int,int> y)
{
if (x.sc>y.sc) swap(x,y);
Gf[t]=Insert(1,n,Gf[t-1],y.fr,x.fr);
Gf[t]=Insert(1,n,Gf[t],x.fr,min(y.sc-1,x.sc));
return;
}
int main()
{
n=Read();m=Read();
Cur=statePool;Gf[0]=Set_up(1,n);
for (t=1;t<=m;t++)
{
int e=Read();
if (e==1) Merge(Find(Read()),Find(Read())); else
if (e==2) Gf[t]=Gf[Read()]; else
printf("%d\n",ans=(Find(Read()).fr==
Find(Read()).fr)),Gf[t]=Gf[t-1];
}
return 0;
}
BZOJ3489：这题脑洞了好久。。太弱。。首先提出每一个数值，数值v的位置是Av,1，Av,2,……，所以我们当Av,i-1<L<=Av,i且Av,i<=R<Av,i+1的时候v对答案是有贡献的，所以就有n个矩形，问题变成我们要求点(L,R)被覆盖上的数值的最大值。如果不是强制在线肯定就可以用扫描线+线段树套堆解决了。但是我们现在强制在线，于是考虑可持久化。对于每个横坐标我们建一棵线段树套线段树，每个矩形的纵坐标[D,H]套到线段树里面的log个节点。每次加入或者删除一段区间就是改变差不多log^2个线段树上面的节点。同时里面的线段树肯定不能直接复制一遍，于是我们里面还要可持久化，同样新建一条链，但是只要改变外层的log个线段树上面的节点所以空间改变也是log^2的。所以时空复杂度都是n log^2。写起来也是比较带感的。(劳资辛苦写的树套树就说MLE？管他的我不会特殊的卡空间卡常技巧。。拍了个小数据好像没问题的样子就弃疗了，以后或许会好雅兴回来填坑的）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100050
#define M 40000020
struct Set_Tree
{int c[M][2];} A;
struct Ment_Tree
{int c[M][2],sn[M];} B;
int sA,sB,n,m,ans,st,v[N],gf[N],now[N],ne[N],cz[N*2][4],sg[N*2];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void GetIn(int &x,int &y)
{x=(x+ans)%n+1;y=(y+ans)%n+1;if (x>y) swap(x,y);}
int Strick_Out(int x,int y,int z,int o)
{
int i=x + y >> 1,j=0,k,l;
if (x==y) return 0;
if (o<=i) k=Strick_Out(x,i,A.c[z][0],o),l=A.c[z][1]; else
l=Strick_Out(i+1,y,A.c[z][1],o),k=A.c[z][0];
if (k||l) A.c[j=++sA][0]=k,A.c[sA][1]=l;
return j;
}
int Delete(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=0,k,l;
if (x==o&&y==p)
{
k=Strick_Out(1,n,B.sn[z],u);
if (k||B.c[z][0]||B.c[z][1])
B.c[j=++sB][0]=B.c[z][0],B.c[j][1]=B.c[z][1],B.sn[j]=k;
return j;
}
if (i>=p) k=Delete(x,i,B.c[z][0],o,p,u),l=B.c[z][1]; else
if (o>i) k=B.c[z][0],l=Delete(i+1,y,B.c[z][1],o,p,u); else
k=Delete(x,i,B.c[z][0],o,i,u),
l=Delete(i+1,y,B.c[z][1],i+1,p,u);
if (k||l||B.sn[z])
B.c[j=++sB][0]=k,B.c[j][1]=l,B.sn[j]=B.sn[z];
return j;
}
int Infix(int x,int y,int z,int o)
{
int i=x + y >> 1,j=++sA;
if (x==y) return j; else
if (o<=i)
A.c[j][0]=Infix(x,i,A.c[z][0],o),A.c[j][1]=A.c[z][1]; else
A.c[j][1]=Infix(i+1,y,A.c[z][1],o),A.c[j][0]=A.c[z][0];
return j;
}
int Insert(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=++sB;
if (x==o&&y==p)
{
B.c[j][0]=B.c[z][0],B.c[j][1]=B.c[z][1];
B.sn[j]=Infix(1,n,B.sn[z],u);return j;
}
if (p<=i)
B.c[j][0]=Insert(x,i,B.c[z][0],o,p,u),
B.c[j][1]=B.c[z][1]; else
if (o>i)
B.c[j][1]=Insert(i+1,y,B.c[z][1],o,p,u),
B.c[j][0]=B.c[z][0]; else
B.c[j][0]=Insert(x,i,B.c[z][0],o,i,u),
B.c[j][1]=Insert(i+1,y,B.c[z][1],i+1,p,u);
B.sn[j]=B.sn[z];
return j;
}
int Enquiry(int x,int y,int z)
{
int i=x + y >> 1;
if (x==y) return x; else
if (A.c[z][1]) return Enquiry(i+1,y,A.c[z][1]); else
return Enquiry(x,i,A.c[z][0]);
}
int Query(int x,int y,int z,int o)
{
int i=x + y >> 1,Ans=B.sn[z]?Enquiry(1,n,B.sn[z]):0;
if (x==y) return Ans;
if (o<=i) return max(Ans,Query(x,i,B.c[z][0],o)); else
return max(Ans,Query(i+1,y,B.c[z][1],o));
}
inline bool cmp(int x,int y)
{return abs(cz[x][0])<abs(cz[y][0]);}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++)
ne[now[v[i]=Read()]]=i,now[v[i]]=i;
memset(now,0,sizeof(now));
for (int i=1;i<=n;i++)
{
int k=now[v[i]]+1,l=ne[i]==0?n:ne[i]-1;
cz[sg[++st]=st][0]=k;cz[st][1]=i;cz[st][2]=l;
cz[st][3]=v[i];cz[sg[++st]=st][0]=-i-1;cz[st][1]=i;
cz[st][2]=l;cz[st][3]=v[i];now[v[i]]=i;
}
sort(sg+1,sg+st+1,cmp);
gf[0]=sA=1;int Now=1;
for (int i=1;i<=n;i++)
{
int k=Now-1;while (k<st&&abs(cz[sg[k+1]][0])==i) k++;
gf[i]=gf[i-1];
for (;Now<=k;Now++)
if (cz[sg[Now]][0]<0)
gf[i]=Delete(1,n,gf[i],cz[sg[Now]][1],cz[sg[Now]][2],
cz[sg[Now]][3]); else
gf[i]=Insert(1,n,gf[i],cz[sg[Now]][1],cz[sg[Now]][2],
cz[sg[Now]][3]);
}
for (int i=1;i<=m;i++)
{
int k=Read(),l=Read();GetIn(k,l);
printf("%d\n",ans=Query(1,n,gf[k],l));
}
return 0;
}
BZOJ3809：首先莫队+线段树的做法很明显，也很明显会爆。所以我们考虑加特技！首先块大小为sqrt(n)，然后我们每次如果只覆盖了一块的就直接暴力，这是msqrt(n)的，否则询问右边部分、暴力左边小于sqrt(n)的部分，这是msqrt(n)+n sqrt(n)*log n的。感觉常数好难卡过的样子。。有的做法用分块代替树状数组？并没有想到= =感觉常数好像要比我优的样子。常数卡好死。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define M 400
int rt,n,m,Ans[N*10],qu[N*10][4],v[N],sg[N*10],s[N],cnt[M];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline int Sg(int x) {return (qu[x][0]-1)/rt;}
inline bool cmp(int x,int y)
{
int k=Sg(x),l=Sg(y);
return k<l||(k==l&&qu[x][1]<qu[y][1]);
}
int GetAns(int x,int y)
{
int ans=0,le=(x+rt-2)/rt,ri=y/rt-1;
if (y-x+1<rt)
{
for (int i=x;i<=y;i++) ans+=s[i]>0;
return ans;
}
for (int i=le;i<=ri;i++) ans+=cnt[i];
for (int i=x;i<=le*rt;i++) ans+=s[i]>0;
for (int i=(ri+1)*rt+1;i<=y;i++) ans+=s[i]>0;
return ans;
}
int main()
{
n=Read();m=Read();rt=sqrt(n);
for (int i=1;i<=n;i++) v[i]=Read();
for (int i=1;i<=m;i++)
qu[i][0]=Read(),qu[i][1]=Read(),qu[i][2]=Read(),
qu[i][3]=Read(),sg[i]=i;
sort(sg+1,sg+m+1,cmp);
for (int i=1;i<=m;i++)
{
memset(s,0,sizeof(s));memset(cnt,0,sizeof(cnt));
int k=i,le=qu[sg[i]][0],ri=qu[sg[i]][1];
while (k<m&&Sg(sg[k+1])==Sg(sg[i])) k++;
for (int j=le;j<=ri;j++)
if (s[v[j]]++==0) cnt[(v[j]-1)/rt]++;
Ans[sg[i]]=GetAns(qu[sg[i]][2],qu[sg[i]][3]);
for (int j=i+1;j<=k;j++)
{
int Le=qu[sg[j]][0],Ri=qu[sg[j]][1];
for (int l=le-1;l>=Le;l--)
if (s[v[l]]++==0) cnt[(v[l]-1)/rt]++;
for (int l=ri+1;l<=Ri;l++)
if (s[v[l]]++==0) cnt[(v[l]-1)/rt]++;
for (int l=le;l<Le;l++)
if (--s[v[l]]==0) cnt[(v[l]-1)/rt]--;
le=Le;ri=Ri;
Ans[sg[j]]=GetAns(qu[sg[j]][2],qu[sg[j]][3]);
}
i=k;
}
for (int i=1;i<=m;i++)
printf("%d\n",Ans[i]);
return 0;
}
BZOJ3747：从左往右扫一遍，顺便维护左端点到每个点的答案。每次改变也只会改变两个区间的答案。所以随便线段树搞搞。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1000050
#define INF 2333233323332333LL
#define ll long long
ll ma[N*4],ad[N*4],ans;int v[N],f[N],now[N],ne[N],n,m;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline ll max(ll x,ll y)
{return x<y?y:x;}
inline void adj(int x,int y,int z)
{
if (ad[z]==0) return;
if (x!=y) ad[z*2]+=ad[z],ad[z*2+1]+=ad[z];
ma[z]+=ad[z];ad[z]=0;
return;
}
void Insert(int x,int y,int z,int o,ll p)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==y) {ma[z]=p;return;}
if (o<=i) Insert(x,i,j,o,p),adj(i+1,y,j+1); else
Insert(i+1,y,j+1,o,p),adj(x,i,j);
ma[z]=max(ma[j],ma[j+1]);
return;
}
void Modify(int x,int y,int z,int o,int p,ll u)
{
int i=x + y >> 1,j=z << 1;adj(x,y,z);
if (x==o&&y==p) {ad[z]+=u;adj(x,y,z);return;}
if (p<=i) Modify(x,i,j,o,p,u),adj(i+1,y,j+1); else
if (o>i) Modify(i+1,y,j+1,o,p,u),adj(x,i,j); else
Modify(x,i,j,o,i,u),Modify(i+1,y,j+1,i+1,p,u);
ma[z]=max(ma[j],ma[j+1]);
return;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++)
f[i]=Read(),ne[now[f[i]]]=i,now[f[i]]=i;
memset(now,0,sizeof(now));
for (int i=1;i<=m;i++) v[i]=Read();
ll Now=0;
for (int i=1;i<=n;i++)
{
if (now[f[i]]==0) now[f[i]]=true,Now+=v[f[i]]; else
if (now[f[i]]==1) now[f[i]]=2,Now-=v[f[i]];
Insert(1,n,1,i,Now);
}
ans=ma[1];
for (int i=2;i<=n;i++)
{
Insert(1,n,1,i-1,-INF);
if (!ne[i-1]) Modify(1,n,1,i,n,-v[f[i-1]]); else
Modify(1,n,1,i-1,ne[i-1]-1,-v[f[i-1]]),
Modify(1,n,1,ne[i-1],ne[ne[i-1]]==0?n:ne[ne[i-1]]-1,
v[f[i-1]]);
adj(1,n,1);ans=max(ans,ma[1]);
}
cout <<ans<<endl;
return 0;
}
BZOJ3555：无脑Hash
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 205
#define M 6000050
#define P1 1000000007
#define P2 998244353
#define Base +10086
#define fr first
#define sc second
#define ll long long
pair <int,int> li[M];
int n,m,st;char b[N];ll ans,Power[N][2];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void GetHash()
{
ll cnt0=0,cnt1=0;
for (int i=1;i<=m;i++)
cnt0=(cnt0+b[i]*Power[i][0]%P1)%P1,
cnt1=(cnt1+b[i]*Power[i][1]%P2)%P2;
for (int i=1;i<=m;i++)
li[++st]=make_pair((cnt0+P1-b[i]*Power[i][0]%P1)%P1,
(cnt1+P2-b[i]*Power[i][1]%P2)%P2);
return;
}
int main()
{
n=Read();m=Read();Read();Power[0][0]=Power[0][1]=1;
for (int i=1;i<N;i++)
Power[i][0]=Power[i-1][0]*Base%P1,
Power[i][1]=Power[i-1][1]*Base%P2;
for (int i=1;i<=n;i++)
scanf("%s",b+1),GetHash();
sort(li+1,li+st+1);
for (int i=1;i<=st;i++)
{
int k=i;
while (k<st&&li[k+1]==li[i]) k++;
ans+=(ll)(k-i)*(k-i+1)/2;i=k;
}
cout <<ans<<endl;
return 0;
}
玛德不玩了直接来一波JOI来强行刷进度吧。感觉JOI有的题还是很有趣的。而且代码都不长。
BZOJ4236：无脑map
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
#define N 200050
#define fr first
#define sc second
map <pair <int,int>,int> li;
map <pair <int,int>,int> :: iterator it;
char a[N];int ans,n;
int main()
{
scanf("%d%s",&n,a+1);li[make_pair(0,0)]=0;
int cnt0=0,cnt1=0,cnt2=0;
for (int i=1;i<=n;i++)
{
if (a[i]=='J') cnt0++; else
if (a[i]=='O') cnt1++; else cnt2++;
pair <int,int> k=make_pair(cnt1-cnt0,cnt2-cnt1);
it=li.find(k);
if (li.end()==it) li[k]=i; else ans=max(ans,i-it->sc);
}
cout <<ans<<endl;
return 0;
}
BZOJ4237：按y坐标分治
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 200050
#define fr first
#define sc second
#define ll long long
int li[N],Li[N],n,m,wz[N][2],sg[N],ri,Ri;ll ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline bool cmp(int x,int y)
{return wz[x][1]<wz[y][1];}
inline bool Cmp(int x,int y)
{return wz[x][0]<wz[y][0];}
int Half_Find(int x,int y,int z)
{
int i=x + y >> 1;
if (x>y) return 0;
if (wz[li[i]][0]>z) return max(Half_Find(x,i-1,z),ri-i+1); else
return Half_Find(i+1,y,z);
}
void Solve(int x,int y)
{
if (x==y) return;
int k=x + y >> 1;
sort(sg+x,sg+y+1,cmp);
sort(sg+x,sg+k+1,Cmp);sort(sg+k+1,sg+y+1,Cmp);
int now=x,Now=k+1;
for (int i=x;i<=y;i++)
if (Now==y+1||(now<k+1&&wz[sg[now]][0]<wz[sg[Now]][0]))
{
while (ri&&wz[li[ri]][1]<wz[sg[now]][1]) ri--;
li[++ri]=sg[now++];
} else
{
while (Ri&&wz[Li[Ri]][1]>wz[sg[Now]][1]) Ri--;
ans+=Half_Find(1,ri,Ri?wz[Li[Ri]][0]:-1);
Li[++Ri]=sg[Now++];
}
ri=Ri=0;
Solve(x,k);Solve(k+1,y);
return;
}
int main()
{
n=Read();
for (int i=1;i<=n;i++) wz[i][0]=Read(),wz[i][1]=Read();
for (int i=1;i<=n;i++) sg[i]=i;
Solve(1,n);
cout <<ans<<endl;
return 0;
}
BZOJ4238：找出所有在所有奇环上面但是不在任何一个偶环上面的边，DFS就好。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define M 200050
#define fr first
#define sc second
bool cl[N],vis[N],b[N],Aha[M];
int fi[N],c[M*2][2],Add[N][2],s[M][2],st,ss=1,n,m,ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
}
pair <int,int> DFS(int x,int y)
{
vis[x]=b[x]=true;cl[x]=!cl[c[y][0]];
int cnt[2];cnt[0]=cnt[1]=0;Aha[y/2]=true;
for (int i=fi[x];i;i=c[i][1])
if (vis[c[i][0]]&&i!=y&&b[c[i][0]])
{
bool flag=cl[x]^cl[c[i][0]];
if (!flag) st++;
cnt[flag]++;Add[c[i][0]][flag]++;
} else
if (!vis[c[i][0]])
{
pair <int,int> k=DFS(c[i][0],i^1);
cnt[0]+=k.fr,cnt[1]+=k.sc;
}
s[y/2][0]=cnt[0]-Add[x][0];
s[y/2][1]=cnt[1]-Add[x][1];b[x]=false;
return make_pair(s[y/2][0],s[y/2][1]);
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++) Line(Read(),Read());
for (int i=1;i<=n;i++)
if (!vis[i]) DFS(i,0);
for (int i=1;i<=m;i++)
if (!s[i][1]&&s[i][0]==st&&Aha[i]) ans++;
if (st==1) ans++;
cout <<ans<<endl;
return 0;
}
BZOJ4239：询问和边按时间排序，边按时间加入，每次加入就跑一次SPFA，但是只能用那些还没有用来更新过的边，也就是每个点维护一个heap来存所有没更新过的边然后更新。这样就是一个log的复杂度了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 100050
#define M 300050
#define INF 0x3f7f7f7f
#define fr first
#define sc second
priority_queue <pair <int,int> > li[N];
pair <int,int> qu[N];queue <int> Li;bool b[N];
int n,m,p,fi[N],c[M*2][4],ss,dis[N],Ans[N],ln[M][3],sg[M];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int o,int z,int y,int x)
{
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;c[ss][3]=o;fi[y]=ss;
ln[ss][0]=o;ln[ss][1]=y;ln[ss][2]=sg[ss]=ss;
}
inline bool cmp(int x,int y)
{return ln[x][0]<ln[y][0];}
void Solve()
{
int cur=1;dis[n]=INF;
for (int i=1;i<=m;i++)
{
int now=ln[sg[i]][0];
while (cur<=p&&qu[cur].fr<now)
Ans[qu[cur++].sc]=dis[1];
li[ln[sg[i]][1]].push(make_pair(-now,ln[sg[i]][2]));
Li.push(ln[sg[i]][1]);b[ln[sg[i]][1]]=true;
while (!Li.empty())
{
int k=Li.front();Li.pop();b[k]=false;
while (!li[k].empty()&&-li[k].top().fr<=dis[k])
{
pair <int,int> l=li[k].top();li[k].pop();
if (dis[c[l.sc][0]]<c[l.sc][2])
{
dis[c[l.sc][0]]=c[l.sc][2];
if (!b[c[l.sc][0]])
b[c[l.sc][0]]=true,Li.push(c[l.sc][0]);
}
}
}
}
while (cur<=p) Ans[qu[cur++].sc]=dis[1];
return;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++) Line(Read(),Read(),Read(),Read());
p=Read();sort(sg+1,sg+m+1,cmp);
for (int i=1;i<=p;i++) qu[i]=make_pair(Read(),i);
for (int i=1;i<n;i++) dis[i]=-1;
sort(qu+1,qu+p+1);
Solve();
for (int i=1;i<=p;i++) printf("%d\n",Ans[i]);
return 0;
}
BZOJ4240：脑洞好大没想出来= =贪心+构造证明
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 300050
#define M 12000050
#define INF 0x3f7f7f7f
#define ll long long
int st,gf,c[M][2],v[N],s[M],Ans[N],n;ll ans;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int Query(int x,int y,int z,int o,int p)
{
int i=x + y >> 1;
if (x==o&&y==p) return s[z];
if (p<=i) return Query(x,i,c[z][0],o,p); else
if (o>i) return Query(i+1,y,c[z][1],o,p); else
return Query(x,i,c[z][0],o,i)+Query(i+1,y,c[z][1],i+1,p);
}
inline int New()
{st++;c[st][0]=c[st][1]=s[st]=0;return st;}
int Insert(int x,int y,int z,int o)
{
int i=x + y >> 1;
if (!z) z=New();
if (x!=y)
if (o<=i) c[z][0]=Insert(x,i,c[z][0],o); else
c[z][1]=Insert(i+1,y,c[z][1],o);
return s[z]++,z;
}
int main()
{
n=Read();
for (int i=1;i<=n;i++) v[i]=Read();
gf=st=1;
for (int i=1;i<=n;i++)
Ans[i]=Query(1,INF,gf,v[i]+1,INF),Insert(1,INF,gf,v[i]);
st=0;gf=New();
for (int i=n;i>=1;i--)
ans+=min(Ans[i],Query(1,INF,gf,v[i]+1,INF)),
Insert(1,INF,gf,v[i]);
cout <<ans<<endl;
return 0;
}
BZOJ4241：一眼莫队+set，当然时间会挂。于是考虑去掉删除操作，这样就可以直接维护最大值。于是可以每一个询问分成两份：小于sqrt(n)的和其余部分。左边的暴力处理，右边的跟原来一样。貌似直接跑的飞起？
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define fr first
#define sc second
#define ll long long
pair <int,int> li[N];
int v[N],sg[N],s[N],val[N],S[N][2],qu[N][2],Aha[N],n,m,rt,st;
ll ma,Ans[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void Pretreat()
{
for (int i=1;i<=n;i++) li[i]=make_pair(v[i],i);
sort(li+1,li+n+1);
for (int i=1;i<=n;)
{
int k=i;
while (k<n&&li[k+1].fr==li[i].fr) k++;
val[++st]=li[i].fr;
for (;i<=k;i++) v[li[i].sc]=st;
}
return;
}
inline bool cmp(int x,int y)
{return Aha[qu[x][0]]<Aha[qu[y][0]]||
(Aha[qu[x][0]]==Aha[qu[y][0]]&&qu[x][1]<qu[y][1]);}
inline ll max(ll x,ll y)
{return x>y?x:y;}
inline void Add(int x)
{ma=max(ma,(ll)(++s[x])*val[x]);}
void Solve(int x,int y,int z)
{
st++;Ans[z]=ma;
for (int i=x;i<=y;i++)
{
if (S[v[i]][1]!=st)
S[v[i]][1]=st,S[v[i]][0]=s[v[i]]+1; else
S[v[i]][0]++;
Ans[z]=max(Ans[z],(ll)S[v[i]][0]*val[v[i]]);
}
return;
}
int main()
{
n=Read();m=Read();rt=sqrt(n);
for (int i=1;i<=n;i++) v[i]=Read(),Aha[i]=(i-1)/rt;
Pretreat();
for (int i=1;i<=m;i++)
qu[i][0]=Read(),qu[i][1]=Read(),sg[i]=i;
sort(sg+1,sg+m+1,cmp);st=0;
for (int i=1;i<=m;)
{
memset(s,0,sizeof(s));ma=0;
int k=Aha[qu[sg[i]][0]],le=(k+1)*rt+1,ri=le-1;
for (i;i<=m&&Aha[qu[sg[i]][0]]==k;i++)
{
while (ri<qu[sg[i]][1]) Add(v[++ri]);
Solve(qu[sg[i]][0],min(qu[sg[i]][1],le-1),sg[i]);
}
}
for (int i=1;i<=m;i++) printf("%lld\n",Ans[i]);
return 0;
}
BZOJ4242：BFS一遍搜出每块地面最近的建筑物和距离，然后相邻不同的地面可以使对应的建筑物连一条边。然后跑MST。然后查询倍增搞搞。感觉性质显然。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 2050
#define M 200050
#define P 20
#define fr first
#define sc second
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
queue <pair <int,int> > li;
int mi[N][N][2],fa[M][P],h[M],rf[M],ma[M][P],c[M*2][3],fi[M];
int ss=1,sx,sy,st,n,m,sg[2*M*P],ln[2*M*P][3];
char d[N];bool b[N][N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y,int z)
{
c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
}
void BFS()
{
while (!li.empty())
{
pair <int,int> k=li.front();li.pop();
for (int i=0;i<4;i++)
{
int q=k.fr+dir[i][0],w=k.sc+dir[i][1];
if (b[q][w]||!q||!w||q==sx+1||w==sy+1||mi[q][w][1])
continue;
mi[q][w][1]=mi[k.fr][k.sc][1];
mi[q][w][0]=mi[k.fr][k.sc][0]+1;
li.push(make_pair(q,w));
}
}
return;
}
inline bool cmp(int x,int y)
{return ln[x][2]<ln[y][2];}
int Find(int x)
{return rf[x]==x?x:(rf[x]=Find(rf[x]));}
void DFS(int x)
{
h[x]=h[fa[x][0]]+1;
for (int i=fi[x];i;i=c[i][1])
if (c[i][0]!=fa[x][0])
fa[c[i][0]][0]=x,ma[c[i][0]][0]=c[i][2],DFS(c[i][0]);
return;
}
void Pretreat()
{
for (int i=1;i<sx;i++)
for (int j=1;j<=sy;j++)
if (!b[i][j]&&!b[i+1][j]&&mi[i][j][1]!=mi[i+1][j][1])
ln[++st][0]=mi[i][j][1],ln[st][1]=mi[i+1][j][1],
ln[st][2]=mi[i][j][0]+mi[i+1][j][0],sg[st]=st;
for (int i=1;i<=sx;i++)
for (int j=1;j<sy;j++)
if (!b[i][j]&&!b[i][j+1]&&mi[i][j][1]!=mi[i][j+1][1])
ln[++st][0]=mi[i][j][1],ln[st][1]=mi[i][j+1][1],
ln[st][2]=mi[i][j][0]+mi[i][j+1][0],sg[st]=st;
sort(sg+1,sg+st+1,cmp);
for (int i=1;i<=n;i++) rf[i]=i;
for (int i=1;i<=st;i++)
{
int k=Find(ln[sg[i]][0]),l=Find(ln[sg[i]][1]);
if (k==l) continue;rf[k]=l;
Line(ln[sg[i]][0],ln[sg[i]][1],ln[sg[i]][2]);
}
for (int i=1;i<=n;i++)
if (rf[i]==i) DFS(i);
for (int j=1;j<P;j++)
for (int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1],
ma[i][j]=max(ma[i][j-1],ma[fa[i][j-1]][j-1]);
}
int GetAns(int x,int y)
{
int Ma=0;
if (h[x]<h[y]) swap(x,y);
for (int i=P-1;i>=0&&h[x]!=h[y];i--)
if (h[fa[x][i]]>=h[y])
Ma=max(Ma,ma[x][i]),x=fa[x][i];
if (x!=y)
{
for (int i=P-1;i>=0;i--)
if (fa[x][i]!=fa[y][i])
Ma=max(Ma,max(ma[x][i],ma[y][i])),
x=fa[x][i],y=fa[y][i];
Ma=max(Ma,max(ma[x][0],ma[y][0]));
}
return Ma;
}
int main()
{
sx=Read();sy=Read();n=Read();m=Read();
for (int i=1;i<=sx;i++)
{
scanf("%s",d+1);
for (int j=1;j<=sy;j++)
if (d[j]=='#') b[i][j]=true;
}
for (int i=1;i<=n;i++)
{
int k=Read(),l=Read();
li.push(make_pair(k,l));
mi[k][l][1]=i;
}
BFS();Pretreat();
while (m--)
{
int k=Read(),l=Read();
printf("%d\n",Find(k)==Find(l)?GetAns(k,l):-1);
}
return 0;
}
BZOJ4243：感觉像是并查集乱搞搞？
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define M 200050
#define ll long long
ll ans;int fi[N],c[M*2][2],fa[M],s[M],n,m,ss,st;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int y,int x)
{c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;}
int Find(int x)
{return fa[x]==x?x:(fa[x]=Find(fa[x]));}
void DFS(int x,int y)
{
if (fa[x])
{
int k=Find(x);
if (k!=y) fa[k]=y,s[y]+=s[k];
} else
{
fa[x]=y;s[y]++;
for (int i=fi[x];i;i=c[i][1]) DFS(c[i][0],y);
}
return;
}
int main()
{
n=Read();m=Read();st=n;
for (int i=1;i<=m;i++) Line(Read(),Read());
for (int i=1;i<=n;i++)
if (!fa[i]&&c[fi[i]][1])
{
int k=++st;fa[k]=k;
for (int j=fi[i];j;j=c[j][1]) DFS(c[j][0],k);
}
for (int i=1;i<=n;i++)
for (int j=fi[i];j;j=c[j][1])
if (fa[i]&&fa[c[j][0]]&&Find(i)==Find(c[j][0]))
m--;
for (int i=n+1;i<=st;i++)
if (fa[i]==i) ans+=(ll)s[i]*(s[i]-1);
cout <<ans+m<<endl;
return 0;
}
BZOJ4244：想了很久不会= =。完全背包。。真尼玛有道理。果然DP太弱想不到。。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 3050
#define ll long long
ll mi[N][N];int u[N],v[N],d[N],e[N],n,m;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++)
u[i]=Read(),v[i]=Read(),d[i]=Read(),e[i]=Read();
memset(mi,0x3f,sizeof(mi));mi[0][0]=0;
for (int i=1;i<=n;i++)
{
for (int j=0;j<=n;j++)
mi[i-1][j]+=j*m*2;
for (int j=1;j<=n;j++)
mi[i][j]=min(mi[i][j],mi[i-1][j-1]+d[i]+v[i]);
for (int j=0;j<n;j++)
mi[i][j]=min(mi[i][j],mi[i-1][j+1]+u[i]+e[i]);
for (int j=1;j<=n;j++)
mi[i][j]=min(mi[i][j],mi[i-1][j]+d[i]+e[i]);
for (int j=0;j<=n;j++)
mi[i][j]=min(mi[i][j],mi[i-1][j]+v[i]+u[i]);
for (int j=1;j<=n;j++)
mi[i][j]=min(mi[i][j],mi[i][j-1]+d[i]+v[i]);
for (int j=n-1;j>=0;j--)
mi[i][j]=min(mi[i][j],mi[i][j+1]+u[i]+e[i]);
}
cout <<mi[n][0]+m*(n+1)<<endl;
return 0;
}
