Codeforces开坑
于是开始被虐了= =不知道能撑多久，有的题目还真是sxbk。尤其是乱搞题智商有限没办法= =
玛德英文题面看起来真尼玛蛋疼啊
计数器应该是手动计数的吧。。
UPD 10.14 一直颓废到现在才差不多半百，接下来效率++吧。
UPD 11.1 感觉做到现在状态越来越萎废，于是先来一波BZOJ找找状态好了。
UPD 11.25 玛德不管了。弃坑了弃坑了= =
464E：毛子脑洞还真是大，一开始乱搞了一个搞法并没有过，膜了一发题解原来是用主席树搞高精度。还要加什么优化感觉就很蛋痛于是先留坑好了= =
464D：一开始还设期望和概率DP，因为i比较大的时候概率基本上没有所以直接设一个范围就好了。结果T地爽爽的。后来膜了一发Tourist的卡常技巧才过。
301D：对数只有n log n个，所以询问和关系都变成点然后排个序用树状数组维护一下扫一遍就好了
463E：之前还一直在想些奇怪的做法但是并弄不出来。原来是DFS一遍顺便每个质数维护一个栈，复杂度50*n log n，因为单点时限10s所以不虚。
319D：暴力能A实在厉害。正解分段搞？不明觉厉，然而sxbk出题人题解都没有贴出来= =
342D：裸状压DP
273E：首先把SG函数值打出来发现段数不多，于是暴力预处理出每一段，然后算出值为0~2的SG值分别有多少个，就可以矩阵快速幂搞了。
257E：裸的模拟题，搞几个set就好了
305E：看错题了，结果一直卡在第二问，后来重新看题才发现好水= =
316E3：线段树维护所需答案，合并用矩阵乘法。常数卡的好紧
263E：花式前缀和乱搞
293B：一种奇怪的爆搜姿势，想了很久状压、爆搜还有其它奇怪的东西都没搞出来。后来还是膜了tourist的code= =
关键的剪枝是没出现过的颜色用组合数算
325E：奇怪的结论题，不会捉= =
241B：奇怪的乱搞题，不过最后还是搞出来了= =
260E：主席树。
338E：Splay裸题。
249E：python写这个常数真是大，连T6次爽爽爽
306B：水
339E：记得以前有人讲课讲过吧。反正乱搞就好了，反正可以作为翻转的端点的一定是什么断点，然后设个常数什么的，如果断点超过一定个数就退出，否则枚举端点然后递归。
286E：颓了很久题面勉强看懂了点，然后颓了很久都不会做。看了代码我才知道一个袋子最多只能装两个的，a set of原来是一对而不是一堆的意思。真是报警。题意懂了就是个比较明显的FFT
332D：题意艹蛋，式子很水，但是一开始低估了long double的范围，以为还要用高精度除法或者要用python写，感觉不管哪一个都很虚啊，没想到ld是存的下600位的数的，不过也应该是没保证精度的吧。
261D：想很久没想出来，后来get了个新DP姿势才A：设一个f数组，f数组中值为k的最小的下标i代表扫到目前这个位置的时候长度为k的最长上升子序列的最右边元素的最小值为i，于是把t*n个元素扫一遍，同时如果当前元素的值减一的f值等于当前元素的f值就暴力往右更新f数组。题目里面的限制保证了t在一定范围内所以枚举t并不会爆，复杂度最多也就是f数组的数值和也就是O(min(maxb^2,n*maxb))的样子。
335D：由于坐标大小被限制，所以有很多个量都被限制在一定范围内所以就可以花式前缀和乱搞了。
235C：首先对于每个xi KMP一下求出最长循环节，预处理出母串的SAM和每个节点的ri集合大小和最短长度，然后放到母串的SAM上面跑，ans加上此节点的ri集合大小，调整位置就是如果当前状态是当前节点的最短长度就调整到pre位置否则不动，然后再加上一个字符。玛德隔了个把月已经不会写SAM了TAT。
311E：最小割= =就是每个富人和狗都建个点，然后分别跟S或T连对应权值边，两者之间连INF，具体连哪边需要根据0/1判断
295D：DP
258D：没想到设a[i][j]为ti>tj的概率，全程在想些奇怪的搞法。人弱智商低没办法
286D：set、heap一起乱搞
273D：小狗好像也讲过，反正花式乱搞。真是写的人想☀狗
283E：好萎，没想出来= =比赛结果是一个n*n的矩阵，每次翻转一个子矩阵中的值，所以是扫描线+线段树维护求出每个人赢了多少场，最后答案是C(n,3)减去每个人赢得场数k的C(k,2)（因为一个非环的结果有且仅有一个人赢了两盘）
305D：乱搞
261E：满足要求的数个数有限，所以求出来之后DP出每个数的最小次数。复杂度虽然是很虚但是还是能过
253E：二分答案
243C：一开始没睡醒的时候想了很久平面图还有扫描线相关做法。看到数据范围之后就是离散化之后暴力矩阵染色+BFS了。
316G3：一开始没想到把所有串建在一个SAM上面而是准备让两个指针在两个SAM上面一起跑，但是母串的SAM每个节点还要维护可行集合，感觉虽然貌似可以卡过的样子但是写到一半100行还是弃疗了，果然还是有更优美的做法= =
256D：N^4DP，还要打表真是差评
303D：狗哔结论题= =首先n+1必须是质数，然后从大到小枚举b，b必须不是n+1的倍数，如果不存在任何n的因子k使得b^k%(n+1)==1||b^(n/k)%(n+1)==1就输出b。你问我怎么证我怎么知道
338D：范围艹蛋
266E：线段树维护每段区间六种值。
332E：乱搞，但是要注意细节，在160+的测试点wa了也真是爽快
584E：考场上一直naive地以为这个就是把环上面最长的边去掉，但其实答案就是每个点到目标点的距离和。构造方法是：枚举目标位置从1~n的点，然后让其与一直往前面扫，如果遇到一个目标位置在其后面的点就与其交换，这样的最大交换次数是n^2的。由于其前面总会有目标位置在其后面的点所以其总能够移动到目标点。
333C：恶心乱搞，很久没有搞出来。
240F：裸线段树
235D：一棵树上的情况就是分别算对于每个点i，删第i个点的时候j点对它的贡献就是1/(dis(i,j)+1)，环套树就是如果有的点有两个距离就1/len1+1/len2-2/(len1+len2+R-2)，len1、len2、R分别为路径1、路径2、环的点数。但是犯逗了很多次
301C：英语弱看不懂题（话说后来问了英语大神还是看不懂TAT），看代码更看不懂，毛子语文题真是厉害
301E：182这场这两题怎么这么神啊，有的人n^5时间还能在100ms内实在厉害，而且DP也好神。按数值从小到大DP，然后方案总数只跟上一个数值的个数有关，所以预处理出组合数，DP设的是算到第i个数、这一个数值有j个、一共用了k个并且有s种方案的时候的方法数。当然以上都是在一个前提下：把所有从上往下的路径除了最下面那个数其它的数全部删掉。
309B：预处理出每个单词最多能到后面哪个单词都能组成一行，然后就O(n)乱搞了。有点卡常
309D：推了个式子，但是各种被卡常，看了标程维护方程解的姿势还真是厉害，没有实数运算所以能卡过
277D：英语果弱看漏了条件，更神奇的是样例也看错了于是想了很久想不出来，后来看到条件推下式子之后就是很显然的贪心+背包。不过好像在一些奇怪的地方卡了精度
341E：完全没有头绪。。。感觉这种弃疗状态下做不了智商题= =正解是任意三个数都可以通过倍增+辗转相消变成两个
323B：奇数情况很快想出来了，就是每个点i连向i+1然后i+2到i-1交替连向i、连向i+k，但是被偶数情况卡住了TATQAQ2333，原来只要多出来那个点连向1和2就可以了。。。
325C：有印象小狗讲过，翻课件还翻到了翻译感觉真是良心，只是记得讲课的时候好像全程在颓。。不过纯码农题没听思路也没什么关系。首先求无法停止的分裂方式就是先找出所有无后继的分裂方式，对于每个怪物如果可停止的方式这个怪物也是可停止的，如此BFS求出。则得出所有无法停止的怪物，删掉这些点及相关方案。剩下点求SCC，用所有被缩的点更新其所有前驱，被标记点都是最大值无穷大的。剩下点的最大值可以拓扑排序求出最大值。所有点的最小值就是SPFA了。做这题简直像是NOIP图论四合一，不过没调多久还是很开心的。（en不对为什么CF上面的代码都写得这么短）
266D：Floyd之后枚举每条边，每个点在这条边上面的最短距离可以看作一条两段共端点的斜率为1、-1的射线，排序之后扫一遍就可以统计答案了
311C：1操作就是模k之后SPFA，另外两个操作用个set就好了。
316D3：推公式推的人萌萌哒，发现了同一置换中最多只能有两个1，通过优化时空都是n^2的，然后就不会了。。。题解里面的自行证明简直厉害。看老司机的博客这题的题解发现了“不求甚解”这句话，感觉真是很有道理。
323C：离线有个经典做法扫描线+线段树，在线直接主席树好了。第二种方法好像代码比第一种短好多。分块做法因为复杂度跟n无关所以常数要小些。
343E：en就是ZJOI那个题，最小割互不相交，于是求n次最小割然后建出树贪心就好了。有个地方的标记打错了调了好久TAT
267C：一开始被题意卡了好久，思路也是好神的高斯消元，并没有想到。。对于每个顶点设从1到它的最短距离为未知数，则可以通过每个点入流量和出流量相等列方程。最后得出来的答案再缩放一下就好了。精度还有细节都有点卡。
314E：我说怎么神题这么多，TM又看错题了TATQAQ2333。以为输入里面大小写字母都有的。首先所有小写字母都是一样的显然。然后设a[i][j]为前i个字符处理完了之后又j的多出来的左括号。常数艹蛋
240E：看了好久不会= =后来才发现是朱刘裸题，不过好像有一些很明显是错误的算法都过了而且n和m都是10w的朱刘算法O(VN)的都过的毫无压力，数据是有多弱。话说朱刘这种东西还要输出方案写起来还真是异常爽快。我真是不会写了。。。
303E：真是不明白为什么什么不科学的复杂度都有，正解n^5还真是爽快。。
285E：好狗哔神，并没想出来= =容斥+DP，直接DP不知道可不可做，但是可做也好麻烦的样子= =首先状态是前i个数造了j个GN，其它的数都无视的方案数，然后就可以求出至少有j个GN的方案数，然后容斥一下就好了。。
331C3：人弱没想到这种DP。。。贪心选最大数位减去显然。设a[i][j][k]为后面i位为999..k，前面位的最大值为i的时候把后面i位减完的总次数。
293E：一眼点分治，对于每次计算答案将所有节点按权值和排序，然后在树状数组里面维护到重心长度。这煞笔东西调了好久都是肥爷的锅。最后发现有个地方爆long long了。。。我个煞笔。。。
288E：花式数位DP，细节好多。。
241F：什么狗哔题面啊。。。
274C：这题的题解的结论都是错的，是锐角三角形和能够任意能够构成至少两个直角三角形的四边形。
319E：en线段相交但不重合之后是可以并成一条线段的，至于找相交线段明显转换成二维平面问题之后K-D Tree搞一搞就可以了。至于线段树解法好像是离散化之后线段树每个节点维护个vector，然后每次插入的时候就合并，询问就是并查集。感觉很厉害，并没有想到。
235E：DP，DP[i,j,k,p]代表a<=i&&b<=j&&c<=k且用到第1~p个质数的时候的答案。则其等于sum DP[i/p^a1,j/p^a2,k/p^a3,p-1]。
306C：组合数学，水
241E：差分约束系统，但是不知道哪里看错题了一直在wa。。
268D：DP。。开始设状态的时候完全没考虑怎么写起来方便。。
254D：先判掉rats>=327的点，然后所有ratsBFS一遍找出所有可以到达rats个数至少为总数一半的点，然后剩下的ratsBFS一遍找出可以覆盖剩下rats的点即为答案。简直跑的飞起。
269D：按高度排序之后用set维护水平区间被覆盖的情况。感觉最近写什么都跑的飞起？
264D：一开始想维护左端点右端点发现不对劲，转换成二维平面之后维护斜线上的左右端点发现也不对，还想了些奇怪的东西，然后就不会了。。原来只要判掉所有后缀分别为AB-BA的情况就好了。。感觉好厉害。。
总感觉后面的题会很愉悦啊。。。
280C：先玩个C冷静一下，虽然是看D题解的时候看这题的所以被剧透了一脸，但是感觉还是比较显然，因为对于每个点只要它和它的父亲都在的时候先选择它而不是它的祖先的概率都是1/(h[1][i]+1)。
280D：岛娘场简直SXBK。。。线段树维护费用流？。。。感觉用费用流建模证明贪心有点不明所以啊。感觉我有证明？：对于选取k块和k+1块的两种最优状态，如果两者不是能由一次翻转得到的则其中必定能选取一段被翻转的连续部分使得只翻转这一部分能增加块数为1，因为翻转一部分的状态这部分连通块数改变的绝对值最大为1。其余部分不跟这个相连而且选取了能使答案更优肯定在只有k块的时候就选取肯定能使答案更优，由此k块的状态不是最优状态，由此相邻块数的两种最优状态肯定是由一次翻转得到的。en比想象中好写。。
590E：这题我真是做的好感动。一开始并不知道怎么做，而且没有题解，于是膜拜标程发现是用AC自动机上面标记每个字符串的结束位置，然后求fail还有最近的带标记的fail祖先，于是就可以n个字符串在上面跑一遍通过带标记fail求出两两之间的关系。至于求最长反链是很水只要一个dinic，但是还要求方案就sxbk了吧。。。我看了半天真心没看懂他求方案的操作的原理。。。留坑好了。然后准备不求甚解先写了再说的时候TM总是TLE在第66个test。最后爆了10+次终于知道了Dinic跑二分稠密图爆炸了。。（但是为什么我记得这是msqrt(n)的比其它姿势都要快啊）。。总之这题终于A了。。。。。。（UPD：好像有人贴出证明来了？戳这里）
329D：en思路当然就肯定是要重复利用。。。
335F：第一眼SB贪心，看了样例感觉神神的，看完standing不敢做了。。感觉思路确实脑洞，总感觉不会证明。。。
294D：en有结论：边上所有点都走过的时候刚好完成任务。感觉怎么搞都可以？暴力建图然后直接搞？有点恶心= =
241D：狗哔结论题，只要管小于等于二十几的就能过？
249D：缩放坐标变成直角？并没有想到= =而且数学弱不会推公式= =
274E：像是294D去掉了结论？将所有点黑白染色之后发现所有点只会走同色的格子，所以说不会出现两次路径相交的情况，所以长度不用去重。然后就是把所有的边界上面的点还有黑格子上面的点排序之后维护一些东西连下边就好了？细节比294D恶心多了。。。我竟然A了。。感觉整个人真是愉快。。
317E：想到一个做法：先一直往影子靠近，然后如果到了外面就通过四个顶点调整。但是感觉好虚总感觉除了不连通之外是不是还存在什么-1情况？关键是这做法感觉一点都不优美= =然后膜拜正解发现就是这样我真是naive。。。感觉乱搞模拟题什么的真是够了。。
后面的题目怎么都这么丧病啊，老湿我可以弃疗了么TAT
325D：en感觉做的时候智商并不在线= =复制一遍原图然后判断两点能否在八连通图里面互相到达= =实在不知道把八连通格子的并查集root标记然后看两个点有没有重复标记是怎么错的。。最后发现还是自己犯逗了= =
360D：感觉要去补数学了= =首先推导一下就可以发现第i项的集合是一个等比数列，比是所有b值还有p-1的gcd，循环节的长度一定是p-1的因数，所以就可以枚举最小的循环节长度leni，则leni、2leni……p-1都在这个集合里面了。一开始求这东西我还想用BSGS。。然后很明显就是个容斥一开始我还想枚举子集求答案我真是naive，这种容斥明显是n^2。
264E：这题不会我是不是要废。。维护两棵线段树分别以高度和位置为下标，然后两种操作就是暴力乱搞。第一个测试点TLE的人不知道什么鬼。。明明就是样例数据本机上面怎么跑怎么过，爆了几发OJ发现h数组值在我还什么事情都没干的情况下就改变值了？反正在上面坑了几组数据没问题之后就弃坑了= =UPD：后来借了个号子在tsinsen上面测了可能是常数原因吧，除了T了三个点之外其他的都是过的。。管他的。。
329E：神题。。不会。。一开始猜了个结论是错的，后来弃疗看题解也都是些smg。。
346E：为什么随便挑了个又是结论题。看了还是感觉不明觉厉。。代码长度应该是唯一良心的地方吧。。
251D：犯逗了。。一开始看到10w数据范围就没往高斯消元方向想。
248E：关键在于数据范围很小。。于是可以记录每个点记录下有i个满罐子的概率。然后暴力枚举取出的满罐子个数转移。
351D：首先我们要求的问题是：询问区间内不同数个数。还有判断区间内存不存在某一个数使得所有这个数的位置是个等差数列。前者就是DQUERY，主席树搞搞。后者我们扫一遍处理出n个矩形之后扫描线+线段树搞搞。基本上一遍写对还是挺爽的。
HEOI2015乱做
我已经不好意思把这个东西叫做题解了
这东西我记得之前CTSC的时候被XL叫去推HEOI，结果当时就smg都没搞出来，只弄出来Day1T3。感觉吧现在看起来还是很艹蛋
Day1T1兔子和樱花
不会做，还是看这里磨出来的代码。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 2000050
int sg[N][2],c[N],n,m,st,s[N],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 s[x]<s[y];}
void DFS(int x)
{
for (int i=sg[x][0];i<=sg[x][1];i++)
DFS(c[i]);
sort(c+sg[x][0],c+sg[x][1]+1,cmp);
s[x]+=sg[x][1]-sg[x][0]+1;
for (int i=sg[x][0];i<=sg[x][1];i++)
if (s[x]+s[c[i]]-1<=m)
s[x]+=s[c[i]]-1,ans++;else break;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++) s[i]=Read();
for (int i=1;i<=n;i++)
{
int k=Read();sg[i][0]=st+1;
while (k--) c[++st]=Read()+1;
sg[i][1]=st;
}
DFS(1);
cout <<ans<<endl;
return 0;
}
Day1T3
当时的我都能做出来的煞笔题
#include <iostream>
#include <string.h>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
int n,m,t,v;
ll mi;
inline int ans(ll x)
{
int i=0;
while (x%10==0) x/=10;
if (x%10==5) i=-1;
while (x) x/=10,i+=2;
return i;
}
inline void Try(ll x)
{
if (x<n||x>m) return;
int i=ans(x);
if (v<=i||(v==i&&x>mi)) return;
v=i;mi=x;
return;
}
void aa(ll x,ll y)
{
ll i;
if (x>m) return;
if (x%y==0)
aa(x,y*10);else
{
if ((x%y)/(y/10)<5)
{
i=x-x%y;i+=y/10*5;Try(i);
}else
{
i=x-x%y;i+=y/10*5+y;Try(i);
}
i=x;i-=x%y;i+=y;Try(i);
aa(i,y*10);
}
return;
}
int main()
{
int i,j,k,l,q,w,e;
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&n,&m);
mi=n;v=ans(n);
aa(n,10);
printf("%lld\n",mi);
}
return 0;
}
Day2T2
一眼Matrix-Tree（然而当时并不知道这种东西），当然也可以用插头DP（现在都不会这种狗哔东西）
需要注意的是模数是合数，妈蛋在这里被卡了。后来突然发现算行列式并不需要真的去除而是两行相消所以是辗转相除就行了。
我真是个煞笔。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 105
#define M 1000000000
#define ll long long
ll t[N][N],ans=1;bool b[N][N];int sg[N][N],st,n,m;char c[N];
inline void Check(int x,int y,int z,int o)
{
if (!z||!o||b[z][o]) return;
t[sg[x][y]][sg[z][o]]=t[sg[z][o]][sg[x][y]]=M-1;
t[sg[x][y]][sg[x][y]]++;t[sg[z][o]][sg[z][o]]++;
}
inline ll abs(ll x)
{return x<0?-x:x;}
void Gauss()
{
for (int i=1;i<st;i++)
{
ll k=i,l;
while (k<st&&!t[k][i]) k++;
if (k==st) {ans=0;return;}
if (k!=i) swap(t[k],t[i]),ans=-ans;
for (int j=i+1;j<st;j++)
if (t[j][i])
{
k=t[i][i];l=t[j][i];
while (l)
{
ll e=k/l;
for (int q=1;q<st;q++)
t[i][q]=(t[i][q]-t[j][q]*e%M+M)%M;
k%=l;swap(k,l);swap(t[i],t[j]);ans=-ans;
}
}
}
ans+=M;
for (int i=1;i<st;i++)
ans=ans*t[i][i]%M;
return;
}
int main()
{
cin >>n>>m;
for (int i=1;i<=n;i++)
{
scanf("%s",c);
for (int j=0;j<m;j++)
if (c[j]=='*') b[i][j+1]=1;else
sg[i][j+1]=++st;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (!b[i][j])
Check(i,j,i-1,j),Check(i,j,i,j-1);
Gauss();
cout <<ans<<endl;
return 0;
}
剩下题目都在后面接着的那个BZOJ乱做里面放粗来了
BZOJ 2595 游览计划
斯坦纳树早在6月份吧小狗就讲过了然而当时并没有填这个坑
感觉写起来还是很轻松愉快的不过虽然这么说还是被细节卡了好久
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 13
#define M 1024
#define INF 0x3f7f7f7f
int v[N][N],st,S,la[N][N][M][4],li[M*M][3];
int s[N][N][M],a[N][2],n,m;bool b[N][N][M];
const int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
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 Trans(int x,int y,int z,int o,int p,int *ri)
{
if (!o||!p||o>n||p>m||v[o][p]+s[x][y][z]>=s[o][p][z])
return;
s[o][p][z]=v[o][p]+s[x][y][z];
la[o][p][z][0]=x;la[o][p][z][1]=y;la[o][p][z][2]=z;
la[o][p][z][3]=0;
if (!b[o][p][z])
(*ri)++,b[li[*ri][0]=o][li[*ri][1]=p][li[*ri][2]=z]=1;
}
void SPFA(int t)
{
int le=1,ri=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (s[i][j][t]!=INF)
li[++ri][0]=i,li[ri][1]=j,li[ri][2]=t,
b[i][j][t]=1;
for (;le<=ri;le++)
{
int q=li[le][0],w=li[le][1],e=li[le][2];
for (int i=0;i<4;i++)
Trans(q,w,e,dir[i][0]+q,dir[i][1]+w,&ri);
b[q][w][e]=0;
}
return;
}
void Solve()
{
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int k=1;k<S;k++)
s[i][j][k]=INF;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
s[i][j][0]=v[i][j];
for (int i=1;i<=st;i++)
s[a[i][0]][a[i][1]][1 << i - 1]=0;
for (int t=0;t<S;t++)
{
for (int i=(t-1)&t;i;i=(i-1)&t)
for (int j=1;j<=n;j++)
for (int k=1;k<=m;k++)
if (s[j][k][t]>s[j][k][i]+s[j][k][t-i]-v[j][k])
{
s[j][k][t]=s[j][k][i]+s[j][k][t-i]-v[j][k];
la[j][k][t][0]=j;la[j][k][t][1]=k;
la[j][k][t][2]=i;la[j][k][t][3]=t-i;
}
SPFA(t);
}
}
void DFS(int x,int y,int z)
{
if (v[x][y]) v[x][y]=-1;
if (!la[x][y][z][0]) return;
if (la[x][y][z][3])
DFS(x,y,la[x][y][z][2]),DFS(x,y,la[x][y][z][3]);else
DFS(la[x][y][z][0],la[x][y][z][1],la[x][y][z][2]);
}
void Print()
{
DFS(a[1][0],a[1][1],S-1);
printf("%d\n",s[a[1][0]][a[1][1]][S-1]);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
if (!v[i][j]) putchar('x');else
if (v[i][j]==-1) putchar('o');else
putchar('_');
puts("");
}
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
v[i][j]=Read();
if (!v[i][j])
a[++st][0]=i,a[st][1]=j;
}
S=1 << st;
Solve();
Print();
return 0;
}
BZOJ 1006
膜了一上午CDQ的弦图课件
真尼玛一堆性质/定理
不过基本上懂了
这题就是直接用，首先用MCS求完美消除序列。然后有一个性质：最大团=最小染色数。
看网上一堆人写的好长贪心求染色的都是没看到这个性质就弃坑了么= =。
然后就直接求个最大团就可以了。还有个性质就是最大团为每个点跟其完美消除序列位置后面相连的点的导出子图是一个团
所以只要枚举每个点看其连的点里面有多少个在其前面就可以了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 10050
#define M 1000050
#define fr first
#define sc second
int c[M*2][2],ss=1,fi[N],n,m,ans,sg[N],s[N];bool b[N];
priority_queue <pair<int,int> > li;
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 Solve()
{
for (int i=1;i<=n;i++)
li.push(make_pair(0,i));
for (int t=n;t>=1;t--)
{
do sg[t]=li.top().sc,li.pop(); while (b[sg[t]]);
b[sg[t]]=1;
for (int i=fi[sg[t]];i;i=c[i][1])
if (!b[c[i][0]])
li.push(make_pair(++s[c[i][0]],c[i][0]));
}
for (int i=n;i>=1;i--)
{
int k=0;b[sg[i]]=0;
for (int j=fi[sg[i]];j;j=c[j][1])
if (!b[c[j][0]]) k++;
ans=max(ans,k+1);
}
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++)
Line(Read(),Read());
Solve();
cout <<ans<<endl;
return 0;
}
HNOI2015填坑
UPD 9.20 我真心想吐槽这东西我交了3遍重写了两遍刷了一个小时这篇题解才交上去TATQAQ2333
HNOI滚粗半年之后才来填坑= =
主要是当时姿势水平不够，现在回去看题目应该会好些了
至少现在不会一道都不会只能打暴力了
亚瑟王：
想了很久TM就是想不出来，后来Orzei题解。
原来是设的第i个卡牌有j个机会的时候的概率，因为不会用LaTeX之类的东西放公式太丑了还是点链接里的看好了
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 505
long double ans,p[N],v[N],f[N][N];int n,m,t;
inline long double s(int x,int y)
{return pow(1-p[x],y);}
int main()
{
cin >>t;
while (t--)
{
memset(f,0,sizeof(f));
cin >>n>>m;ans=0;f[0][m]=1;
for (int i=1;i<=n;i++)
{
double k,l;
scanf("%lf%lf",&k,&l);
p[i]=k;v[i]=l;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
f[i][j]=f[i-1][j]*s(i-1,j)+f[i-1][j+1]*(1-s(i-1,j+1)),
ans+=f[i][j]*(1-s(i,j))*v[i];
printf("%.10lf\n",(double)ans);
}
return 0;
}
接水果：
maya我一直以为这个是树套树，YY了一下感觉一般二分答案的搞法还是n log^3 n的，感觉要线段树套线段树然后先找出第一层的log n的节点然后边比较log n个节点的子树大小边往左右走才能搞到n log^2 n的，但是空间复杂度也是O(n log^2 n)的真是好虚啊
所以果断就弃坑了
后来感觉不行还是要来填坑，结果NM发现*利的代码只有100h缩行比我还屌，才知道这题要用整体二分。
一开始刚看到这东西感觉还是非常玄幻的
但是在二分的同时不仅减小了答案范围的大小，同时询问的规模还有盘子的个数也是同时在减小的
所以就不虚了。
具体来说就是先搞出DFS序，然后分两种情况讨论，
对于每个盘子如果两个点没有祖先关系它所能接到的水果的两点的DFS序分别在两个子树里面
否则的话设较深的那个点为v，另外一个点为u，v的比u深1的祖先为k，这个倍增求一下
则水果上两个点的DFS序分别在v的子树里面
另外一个要不就比k的DFS序小要不就比k子树内的最大DFS序大
所以每个盘子就相当于最多两个矩形
然后每个询问也对应了一个点
问题就变成了求每个点被覆盖的矩形里面的第k小值
这东西就整体二分搞了
首先对于当前二分的区间，我们弄出其中值小于等于mid的盘子
然后排个序，询问也排个序，然后扫一遍，球当前所有点分别被多少盘子覆盖，线段树明显可以搞
最后比较涉及的所有询问和求得的个数
如果个数小于询问的k则询问的k减去求得个数然后把这个询问放到b序列
否则这个询问放到a序列
a序列的答案就在[L,mid]里面，b序列的答案就在[mid+1,R]里面
并且盘子中值小于mid的都可以归到a里面，其余的都归到b里面。
所以询问规模每次都是减半的
算上线段树还有排序的复杂度这东西就是O(n log^2 n)的了，而且空间也顶多有一个倍增数组的O(n log n)
感觉理清思路之后其实也还好写
然而一开始开的线段树的空间是3n的挂掉了，虽然一般说是3n就够用了但是空间还够用的时候还是开4n比较保险
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 50050
#define INF 0x7f7f7f7f
struct Point
{int tp,x,y,z,v;} li[N*5];
int fi[N],c[N*2][2],n,m,sg[N][2],ss=1,st,St,p,t[N],fa[N][20];
int s[N*4],ad[N*4],ans[N],h[N],S[N*5];
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)
{
sg[x][0]=++st;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,DFS(c[i][0]);
sg[x][1]=st;
}
int Find(int x,int y)
{
for (int i=16;i>=0&&fa[x][0]!=y;i--)
if (h[fa[x][i]]>h[y]) x=fa[x][i];
return x;
}
inline void Push(int x,int y,int z,int o,int p)
{li[++st].tp=x;li[st].x=y;li[st].y=z;li[st].z=o;li[st].v=p;}
inline bool cmp(Point x,Point y)
{return x.x<y.x;}
inline void adj(int x,int y,int z)
{
if (!ad[z]) return;
if (x!=y) ad[z*2]+=ad[z],ad[z*2+1]+=ad[z];else
s[z]+=ad[z];
ad[z]=0;
}
void Insert(int x,int y,int z,int o,int p,int u)
{
int i=x + y >> 1,j=z << 1;
if (x==o&&y==p) {ad[z]+=u;return;}
if (o<=i) Insert(x,i,j,o,min(p,i),u);
if (p>i) Insert(i+1,y,j+1,max(o,i+1),p,u);
}
int Query(int x,int y,int z,int o)
{
int i=x + y >> 1,j=z << 1;
adj(x,y,z);if (x==y) return s[z];
return o<=i?Query(x,i,j,o):Query(i+1,y,j+1,o);
}
void Half_Find(int x,int y,int z,int o,int p,int u)
{
if (x>y||z>o||p>u) return;
if (x==y)
{
for (int i=p;i<=u;i++) ans[li[i].v]=t[x];
return;
}
int mid=x + y >> 1,ri=z-1,r1=z,r2=p;
for (int i=z;i<=o;i++)
if (li[i].v<=t[mid]) swap(li[i],li[++ri]);
sort(li+z,li+ri+1,cmp);sort(li+p,li+u+1,cmp);
while (r1<=ri||r2<=u)
if (r1<=ri&&(r2>u||(li[r1].x<=li[r2].x)))
Insert(1,n,1,li[r1].y,li[r1].z,li[r1].tp==1?1:-1),r1++;else
S[r2]=Query(1,n,1,li[r2].y),r2++;
r2=p-1;
for (int i=p;i<=u;i++)
if (S[i]>=li[i].z)
swap(li[++r2],li[i]);else
li[i].z-=S[i];
Half_Find(x,mid,z,ri,p,r2);
Half_Find(mid+1,y,ri+1,o,r2+1,u);
}
int main()
{
n=Read();m=Read();p=Read();
for (int i=1;i<n;i++) Line(Read(),Read());
DFS(1);st=0;
for (int i=1;i<=16;i++)
for (int j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
for (int i=1;i<=m;i++)
{
int q=Read(),w=Read(),e=Read();t[i]=e;
if (sg[q][0]>sg[w][0]) swap(q,w);
if (sg[q][1]<sg[w][0])
Push(1,sg[q][0],sg[w][0],sg[w][1],e),
Push(2,sg[q][1]+1,sg[w][0],sg[w][1],e);else
{
q=Find(w,q);
Push(1,1,sg[w][0],sg[w][1],e);
Push(2,sg[q][0],sg[w][0],sg[w][1],e);
if (sg[q][1]!=n)
Push(1,sg[w][0],sg[q][1]+1,n,e),
Push(2,sg[w][1]+1,sg[q][1]+1,n,e);
}
}
sort(t+1,t+m+1);St=st;
for (int i=1;i<=p;i++)
{
int q=Read(),w=Read(),e=Read();
if (sg[q][0]>sg[w][0]) swap(q,w);
Push(3,sg[q][0],sg[w][0],e,i);ans[i]=INF;
}
Half_Find(1,m,1,St,St+1,st);
for (int i=1;i<=p;i++)
printf("%d\n",ans[i]);
return 0;
}
菜肴制作：
建图，j->i，然后每次选出入度为0的最大点，倒序输出就是答案。
YY一下感觉是对的，泥要问我怎么证这东西我怎么会知道。
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define INF 0x7f7f7f7f
int a[N],n,m,fi[N],c[N][2],s[N],li[N],ri;
inline void Insert(int x)
{
int i=++ri;
li[i]=x;
while (i!=1&&li[i]>li[i/2])
swap(li[i],li[i/2]),i/=2;
return;
}
inline void Delete()
{
int i=1,k;
li[1]=li[ri--];
while (i*2<=ri)
{
k=i*2+(i*2<ri&&li[i*2+1]>li[i*2]);
if (li[k]<li[i])
break;
swap(li[k],li[i]);i=k;
}
return;
}
int main()
{
int i,j,k,l,q,w,e,ss;
scanf("%d",&ss);
while (ss--)
{
memset(fi,0,sizeof(fi));memset(c,0,sizeof(c));
memset(s,0,sizeof(s));memset(li,0,sizeof(li));
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d%d",&k,&l);
c[i][0]=k;c[i][1]=fi[l];fi[l]=i;s[k]++;
}
ri=0;
for (i=n;i>=1;i--)
if (!s[i])
li[++ri]=i;
w=0;
while (ri&&w!=n)
{
e=li[1];Delete();
for (i=fi[e];i;i=c[i][1])
{
s[c[i][0]]--;
if (!s[c[i][0]])
Insert(c[i][0]);
}
a[++w]=e;
}
if (w!=n)
{
printf("Impossible!\n");
continue;
}
for (i=n;i>=1;i--)
printf("%d ",a[i]);
printf("\n");
}
return 0;
}
落忆枫音
madan记得看题面的时候当场就喷了，这还是我第一次推的galgame，而且当时被虐的要死，虽然说原画是有点崩的，不过当时感觉是很不错啊，如果TM不是某个素质低下的人剧透感觉会推起来更带感。顺便一提个人是比较萌海音的。话说好像扯远了= =
感觉吧如果没有多出来的那条边就是直接把除1之外所有点的出边个数乘起来，然而当时我这都没想出来= =
多了一条边就是拓扑图DP了，先把原图反过来建，然后拓扑排序一下，然后从多出来的那条边的终点开始更新它的出边上的点j的答案就是当前的Si*Multi(i+1,j-1)，Multi是从i+1到j-1的所有点的出边个数之积，这东西前缀和处理下然后逆个元什么的就好了。终点的S值是1~T-1的乘积，最后得到起点的答案之后还要乘以Multi(S+1,n)，最后得到的这个东西cnt，答案就是加上那条多余的边之后的所有点出度乘积-cnt。感觉并没有讲人话，反正就是按照原来的方法统计答案会出现问题，也就是会有包含了那个多余边的环也算进了答案，所以我们拓扑图DP统计这东西并减去就可以了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 100050
#define M 1000000007
#define ll long long
int fi[N],c[N*2][2],fa[N],S,T,n,m,ss=1,cnt[N],li[N],sg[N];
ll ans,s[N][2],tot[N];queue <int> a;
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;fa[x]++;cnt[y]++;}
ll Quick_Power(ll x,int y,ll z)
{ll k=1;while (y) k=y&1?k*x%z:k,x=x*x%z,y >>= 1;return k;}
inline ll Query(int x,int y)
{return s[y][0]*s[x-1][1]%M;}
void Top_Sort()
{
for (int i=1;i<=n;i++)
if (!cnt[i]) a.push(i);
s[0][0]=s[0][1]=1;
for (int i=1;i<=n;i++)
{
sg[li[i]=a.front()]=i;a.pop();
s[i][0]=s[i-1][0]*fa[li[i]]%M;
s[i][1]=Quick_Power(s[i][0],M-2,M);
for (int j=fi[li[i]];j;j=c[j][1])
{
cnt[c[j][0]]--;
if (!cnt[c[j][0]])
a.push(c[j][0]);
}
}
for (int i=1;i<=n;i++)
{
if (li[i]==S)
tot[S]=Query(1,i-1);else
if (li[i]==T)
ans=(ans-tot[T]*Query(i+1,n)%M+M)%M;
for (int j=fi[li[i]];j;j=c[j][1])
tot[c[j][0]]=(tot[c[j][0]]+Query(i+1,sg[c[j][0]]-1)*tot[li[i]]%M)%M;
}
return;
}
int main()
{
n=Read();m=Read();S=Read();T=Read();
for (int i=1;i<=m;i++) Line(Read(),Read());
if (S==T) S=T=0;ans=1;
for (int i=2;i<=n;i++)
ans=ans*(fa[i]+(i==T))%M;
if (T!=1)
fa[1]=1,Top_Sort();
cout <<ans<<endl;
return 0;
}
开店
一眼点分治，一开始还准备用线段树，但是空间怎么算都是会爆炸的，于是前缀和就好了。
如果真在考场上面碰到这题真心写起来需要勇气啊
1A（主要是样例数据良心），正好卡时过= =时间常数这么大肯定是人丑没办法
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200050
#define M 8000050
#define ll long long
int fi[N],c[N*2][3],gf[N][21],n,m,p,ss=1,sg[N][21],st=0;ll ans;
int h[N][21],sum[N],li[N],s[N],t[N],cnt[N],la[N],Rt[N][20];
struct Point {int x,y,z;} a[N];
inline ll max(ll x,ll y)
{return x<y?y:x;}
struct ST
{
ll s[M*3];int t[M][2],cnt;
inline void Push(int x,int y,int z)
{t[++cnt][0]=x;t[cnt][1]=y;s[cnt]=z;}
void Set_up()
{for (int i=2;i<=cnt;i++) s[i]+=s[i-1];}
ll Query(int x,int y,int z,int o,ll p)
{
int i=x + y >> 1;
if (x>y) return -1;
if (t[i][0]<z||(t[i][0]==z&&t[i][1]<=o))
return max(Query(i+1,y,z,o,p),i*p+s[i]);else
return Query(x,i-1,z,o,p);
}
} A;
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 void Calc(int* x,int* y)
{
int k=(*x+ans)%p,l=(*y+ans)%p;
*x=min(k,l);*y=max(k,l);
}
inline bool cmp(Point x,Point y)
{return x.x<y.x||(x.x==y.x&&x.y<y.y);}
inline bool cpm(Point x,Point y)
{return x.y<y.y;}
int BFS(int x,int y)
{
int le=1,ri=1;li[1]=x;h[x][y]=la[x]=0;
for (;le<=ri;le++)
for (int i=fi[li[le]];i;i=c[i][1])
if (c[i][0]!=la[li[le]]&&!cnt[c[i][0]])
h[c[i][0]][y]=h[li[le]][y]+c[i][2],
li[++ri]=c[i][0],la[c[i][0]]=li[le];
return ri;
}
int Find(int x,int y)
{
for (int i=1;i<=y;i++) sum[li[i]]=0;
for (int i=y;i>=1;i--) sum[la[li[i]]]+=++sum[li[i]];
while (1)
{
int k=0;
for (int i=fi[x];i;i=c[i][1])
if (!cnt[c[i][0]]&&c[i][0]!=la[x]&&sum[c[i][0]]*2>y)
{x=c[i][0];k=1;break;}
if (!k) return x;
}
}
void Set_up(int x,int y)
{
int tot=BFS(x,y),rt=Find(x,tot),ri=1;BFS(rt,y);
sg[rt][cnt[rt]=y]=++st;
for (int i=2;i<=tot;i++)
if (la[li[i]]==rt)
gf[li[i]][y]=li[i],sg[li[i]][y]=++st;else
gf[li[i]][y]=gf[la[li[i]]][y];
for (int i=1;i<=tot;i++)
a[i].x=sg[gf[li[i]][y]][y],a[i].y=t[li[i]],a[i].z=h[li[i]][y],
Rt[li[i]][y]=rt;
sort(a+1,a+tot+1,cpm);
for (int i=1;i<=tot;i++)
A.Push(sg[rt][y],a[i].y,a[i].z);
sort(a+1,a+tot+1,cmp);
for (int i=2;i<=tot;i++)
A.Push(a[i].x,a[i].y,a[i].z);
for (int i=fi[rt];i;i=c[i][1])
if (!cnt[c[i][0]]) Set_up(c[i][0],y+1);
return;
}
ll query(int x,int y,int z,int o)
{
ll k=A.Query(1,A.cnt,x,z,o),l=A.Query(1,A.cnt,x,y-1,o);
if (k==-1) k++;if (l==-1) l++;
return k-l;
}
ll Query(int x,int y,int z)
{
ans=query(sg[x][cnt[x]],y,z,0);
for (int i=cnt[x]-1;i>=1;i--)
ans+=query(sg[Rt[x][i]][i],y,z,h[x][i])-
query(sg[gf[x][i]][i],y,z,h[x][i]);
return ans;
}
int main()
{
n=Read();m=Read();p=Read();A.cnt=0;
for (int i=1;i<=n;i++) t[i]=Read();
for (int i=1;i<n;i++) Line(Read(),Read(),Read());
Set_up(1,1);A.Set_up();
while (m--)
{
int q=Read(),w=Read(),e=Read();
Calc(&w,&e);
printf("%lld\n",Query(q,w,e));
}
return 0;
}
实验比较
感觉思路还是比较好想的，就是优化一个DP
首先设Ai,j,k代表我们合并两个长为i和j的只有小于的链成一个长为k的链的方案数
就等于Σ(b=0 to j) Ai-1,b,k-j+b-1 + Σ (b=0 to j-1) Ai-1,b,k-j+b
分别是枚举的i链第一个点在哪个位置和第一个点和哪个点合并。这东西是n^4的
所以考虑前缀和优化，可以观察到Σ里面的Ai,j,k里面的k-j都是一定的
所以我们再设一个Si,j,k代表Σ(b=0 to k) Ai,k,k+j 这东西边求Ai,j,k的时候就可以边处理出这个数组
最后就是树形DP，可以设个超级根连掉所有的根，然后DFS一遍就好了。
合并的时候就是枚举两条链的长度以及生成链的长度用A转移
这东西看上去是n^4的，虽然实际上我也不知道它复杂度多少但是我们可以记录每个子树所生成的链最大最小的长度多少来优化
所以就非常愉快了
还要注意的是狗哔题面并没有说会有环但是是有这种情况的
所以要特判掉环的情况输出0
建边就是并查集搞一搞
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 105
#define M 1000000007
#define ll long long
int s[N][N][N],a[N][N][N],fa[N],len[N][2],S[N][N],n,m,ans;
int fi[N],c[N*2][2],ss=1,ln[N][3],li[N];char b[20];bool d[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 bool cmp(int x,int y)
{return ln[x][2]<ln[y][2];}
int Find(int x)
{return fa[x]==x?x:(fa[x]=Find(fa[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 Set_up()
{
n++;
for (int i=0;i<=n;i++)
a[0][i][i]=1,s[0][0][i]=i+1;
for (int i=1;i<=n;i++)
for (int j=0;j<=n-i;j++)
for (int k=max(i,j);k<=i+j;k++)
a[i][j][k]=((k==j?0:s[i-1][k-j-1][j])+s[i-1][k-j][j-1])%M,
s[i][k-j][j]=(s[i][k-j][j-1]+a[i][j][k])%M;
n--;
}
void Merge(int x,int y)
{
ll Aha[N];memset(Aha,0,sizeof(Aha));
for (int i=len[x][0];i<=len[x][1];i++)
for (int j=len[y][0];j<=len[y][1];j++)
for (int k=max(i,j);k<=i+j;k++)
Aha[k]=(Aha[k]+(ll)(S[x][i])*S[y][j]%M*a[i][j][k]%M)%M;
len[x][0]=max(len[x][0],len[y][0]);
len[x][1]=len[x][1]+len[y][1];
for (int i=len[x][0];i<=len[x][1];i++)
S[x][i]=Aha[i];
}
void DFS(int x)
{
d[x]=S[x][0]=1;
for (int i=fi[x];i;i=c[i][1])
if (!d[c[i][0]])
DFS(c[i][0]),Merge(x,c[i][0]);
len[x][0]++;len[x][1]++;
for (int i=len[x][1];i>=len[x][0];i--)
S[x][i]=S[x][i-1];
}
bool DSF(int x,int y)
{
d[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (d[c[i][0]]&&c[i][0]!=y) return 1;else
if (!d[c[i][0]]&&DSF(c[i][0],x)) return 1;
return 0;
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++)
{
int k=Read();scanf("%s",b);int l=Read();
ln[i][0]=k;ln[i][1]=l;ln[i][2]=b[0]=='<';li[i]=i;
}
sort(li+1,li+m+1,cmp);
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=m;i++)
if (ln[li[i]][2])
Line(Find(ln[li[i]][0]),Find(ln[li[i]][1])),
d[Find(ln[li[i]][1])]=1; else
fa[Find(ln[li[i]][1])]=Find(ln[li[i]][0]);
for (int i=1;i<=n;i++)
if (!d[i]&&Find(i)==i) Line(n+1,i);
memset(d,0,sizeof(d));
int check=DSF(n+1,0);
for (int i=1;i<=n;i++)
if (!d[i]&&Find(i)==i) check=1;
if (check) {puts("0");return 0;}
memset(d,0,sizeof(d));
Set_up();DFS(n+1);
for (int i=len[n+1][0];i<=len[n+1][1];i++)
ans=(ans+S[n+1][i])%M;
cout <<ans<<endl;
return 0;
}
相比Day1的题感觉Day2的题良心多了
