围观到叉姐和shi哥都强力推荐大妈题.于是就切了一套.
给定n<=10^2000,求一个最大的k,使得满足1<=k<=n/2 && ( i*k mod n 能取遍所有0~n-1的值 )
分3种情况讨论:
给出一个裸的无源汇上下界网络流模型,让你求一个可行流.
这个太裸直接套经典模型.
有一棵树,它的根节点不能涂色,让你给他的一些结点涂色,使得满足以下条件的情况下,涂的点最多,输出点数*1000和涂色方案.
1,每个结点只能有一个儿子被涂色.
2,如果本结点涂色了,那么该节点所有儿子都不能涂色.
给定一个无向图G=(VE),这个无向图对应一个N*M的矩阵A,对于矩阵中(ij)这个格子,如果i是第j条边的其中一个端点,那么为1,否则为0.设另一M*N的矩阵B满足,B(ij)=A(ji).令B * A=C,求C这个M*M的矩阵里所有元素的和是多少.
C[ij]=Sum{ B[ik]*A[kj] },他们必须都为1才能算进结果,并且只会令结果+1.那么但看中间k这个点而言,对答案的贡献显然是他度数的平方......于是水之.
一个N*M的矩阵(N<=10^100 M<=5),里面每个格子要么涂白色要么涂黑色,假如矩阵里不存在2*2的子矩阵同色,那么是符合条件的.然后问,合法涂色方案有多少种.
状态压缩dp->矩阵乘法.
然后加了这个优化,还要注意变成unsigned int刚刚够(你们懂的):
COCO船长被众岛围观,他那只船是圆的,岛也是圆的,问能不能再不上岸的情况下跑出这个群岛.
给定n<=100000个元素,让你求最多能共存多少个元素,两元素能共存必须满足Si
排序+LIS不用解释的......但是要输出方案.n lg n的算法大家都知道最后在那个表里的不是LIS.但是当你插入到表中的时候,在你前面的那一个必然可以作为你得到当前这个F值的Father......这个很容易YY到.然后Father link回去就可以了.
给定n(n<=100)个数,每个数Ai<=10^9,然后这些数的素因子只能是前T个素数(T<=100).问有多少个非空子集,子集内的数之积为完全平方数.
然后可以根据这个列方程,每个变元Xi表示第i个数取还是不取,然后有T条方程,对应前T个素数与这n个数的奇偶关联.
一般我们guass消元的时候会发现无限解和无解的情况.无解很简单.平常的无限解就是某一步找不到主元了,这一个元其实是取true和false都可以  ,而且只对前面的方程有影响,也就是将答案*2.然后一直消下去,那么计算有多少个元酱油了,答案应该就是2^cnt.但是注意到要非空子集,而显然空的时候是符合方程的,所以将答案-1即可.