题意：给一个长度为3∗1053*10^53∗105的字符串，判断有多个子串[l,r][l,r][l,r]重新排列之后可以是回文串 因为字符是′a′−′z′'a'-'z'′a′−′z′以及′A′−′Z′'A'-'Z'′A′−′Z′，那么我们可以用一个long long的二进制来标示某个区间该字符出现的次数，如果为奇数对应位则为1，如果为偶数则对应位为0。显然，如果该区间的字符可以重新排列组成回文串，那么该区间内1的个数<=1。 以上，以下。 假设知道区间[1,r][1,r][1,r]的“状态”，那么我们可以找是否存在lll，使得[l,r][l,r][l,r]的“状态”中1的个数<=1，也就是： 已知[1,r][1,r][1,r]，求 1)[1,l−1][1,l-1][1,l−1]^[l,r][l,r][l,r]==0中的lll的个数 2)[1,l−1][1,l-1][1,l−1]^[l,r][l,r][l,r]结果中1的个数=1中的lll的个数,l>1l>1l>1 然后枚举的时候 ...

题意：给定一颗n(n<=10000)个点的带权树，问这颗树中两点最短路小于等于K的点对有多少。 漆子超 的《分治算法在树的路径问题中的应用》中的例题之一。 因为是无根树，每次找树的重心，以重心转换为有根树，可以防止算法从O(NlogN)O(NlogN)O(NlogN)退化为O(n2)O(n^2)O(n2)，，然后求经过该点的最短路小于等于K的点对数。但是会算多，因此要减去算多的那些部分。。 代码： #include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long LL;const int MAXN=10000+100;struct Edge { int to,next,w; Edge(){} Edge(int _to,int _next,int _w):to(_to),next(_next),w(_w){}}e[MA ...

题意：给一个长度为n的序列(n≤200000n\leq200000n≤200000)，判断这个序列是不是无聊序列，若该序列中的任意连续子序列中存在一个数是唯一的，也就是只出现一次，那么这个序列就是非无聊子序列。 求第i个位置和它两边最近的下一个相同数的位置，对于任意长度的连续子序列[L,R][L,R][L,R]，一定要有X使得pre[X]<Lpre[X] < Lpre[X]<L && next[X]>Rnext[X] > Rnext[X]>R 成立，那么就可以将这个子序列分开为[L,X−1][L,X-1][L,X−1]和[X+1,R][X+1,R][X+1,R]以此判断。 注意要从两边开始扫，如果值从一边开始扫可能退化为O(n2)O(n^2)O(n2) 代码： #include <iostream>#include <cstdio>#include <cstring>#include <map>#include <algorithm>#include <limits& ...

题意：给定一些宏以及宏的定义，问指定宏展开后是否是某个字符串的匹配串。 比如 START = FIRST + SECND • FIRST = D + E • SECND = F + E • D = good • E = times • F = bad START的展开为goodtimesbadtimesgoodtimesbadtimesgoodtimesbadtimes，给定一个询问。debatedebatedebate，这个串在goodtimesbadtimesgoodtimesbadtimesgoodtimesbadtimes中顺序出现。。。。 给定的宏只有两种方式 一种是 宏 = 宏 + 宏 另一种是 宏 = 单词 这样我们可以建出一个单向无环图（题目保证无环），那么对于每个节点，可以求这个节点对于给的串第i个字符开始最多能匹配的个数。依次往上推即可~~ 代码： #include <iostream>#include <map>#include <cstdio>#include <cstdlib>#include <cstr ...

题意：有两个实验室，有n个实验和m对实验依赖(a,b)(a,b)(a,b)代表实验bbb必须在实验aaa之后才能进行，一开始可以在任意两个实验室进行实验，问最少要转移多少次实验室可以把这n个实验全部完成。 两次拓扑排序分别计算从1号实验室开始和从2号实验室开始所需要转移的次数就可以。。。 代码： #include <iostream>#include <cstdio>#include <cstring>#include <queue>using namespace std;const int MAXN = 100000+1;int n,m,T;struct Edge { int to,next; Edge(){} Edge(int _to,int _next):to(_to),next(_next){}}e[1000000+5];int head[100000+1],tot;void init(){for(int i=1;i<=n;i++)head[i]=-1; ...

题意：给一个n*m的象棋，给一些车的坐标，每个车可以攻击当前行或者当前列，给出一些子矩阵询问，问这个子矩阵中的每个格子是否都能被攻击到。 线段树维护下行和列就行了，对于询问的子矩阵，其对应的行都有车或者对应的列都有车就是Yes的，否则为No。 代码： //author: CHC//First Edit Time: 2015-09-26 22:02#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=100000+100;const int ...

题意：给定一个99的数独，要求判断是否为简单数独。 数独：对于每一行每一列或者子方格内，只能填1~9这几个数，并且每个数字只能出现一次，比如说： 如果一个99的数独是简单数独的话，这个数独的解是独一无二的 也就是说，每次可以推导出一个点，这个点的值是确定的，直到数独被填满。 对于下图，x只能填2 对于下图，x只能填1 判断数独是否是简单数独。如果是输出1，不是输出0. 这道题坑爹，质疑标程写错，数据出错。 其实仔细思考一番可以发现使用位运算来做，因为只有9个数，那么我们可以使用9位二进制来代表该数是否已经使用，若已经使用则为1，否则为0 那么我们可以很容易得到一个01的状态，它其实是个整数。 显然，可以容易每个点的可以放置的状态，第i位为1说明该点可以放置i，否则不能放置，若该状态只能放置1个点，也就是二进制中1的个数为1，那么就必然放置该点。 (这题训练赛的时候没有A，还被队友嘲讽了一发，队友敲了20分钟就过了，我勒个擦！) 这个代码其实早就出来了，因为我两种情况都考虑到了，诡异的一直wa 代码1： //author: CHC//First Edit Time: 2015-0 ...

题意：给定一有边权的单向图，然后要求从这个图中选择一些不相交的哈密顿路，并且所有的点都必须选择。 哈密顿路：除了起点以外，所有的点都只经过一次。 。。。如果一个点属于一条哈密顿路，那么它一定有且仅有一条出边，一条入边，但是对于每个点来说有很多条出边很多条入边，我们只需要匹配每一个点的出边和入边，就转换成了最小费用二分图匹配 建图：把每个点uuu拆开为uuu和u′u'u′ 若存在边e(u,v)e(u,v)e(u,v)，则建边e(u,v′)e(u,v')e(u,v′)，边权为1，费用为边e(u,v)e(u,v)e(u,v)的费用 对于所有的uuu，建边e(st,u)e(st,u)e(st,u)，边权为1，费用为0 对于所有的u′u'u′，建边e(u′,et)e(u',et)e(u′,et)，边权为1，费用为0 代码： //author: CHC//First Edit Time: 2015-09-23 22:37#include <iostream>#include <cstdio>#include <cstring& ...

题意：给一颗树，从树上找一个点集D，任意从树上选择一点，要么这个点属于点集D，要么这个点的邻居有且仅有一个点属于点集D。 看错题了。以为是最小支配集。因为看少一个条件：不在点集D中的点的邻居有且仅有一个点属于D。 设dp[i][j]dp[i][j]dp[i][j]为点i在j状态时所要的染色最少点数。 dp[i][0]dp[i][0]dp[i][0]为将点i染为黑色 dp[i][1]dp[i][1]dp[i][1]为将点i染为白色，儿子为白色 dp[i][2]dp[i][2]dp[i][2]为将点i染为白色，儿子有且仅有一黑色 那么有转移式子 dp[u][1]+=min(dp[v][0],dp[v][1])dp[u][1]+=min(dp[v][0],dp[v][1])dp[u][1]+=min(dp[v][0],dp[v][1]) vvv为uuu的儿子 dp[u][0]+=dp[v][2]dp[u][0]+=dp[v][2]dp[u][0]+=dp[v][2] vvv为uuu的儿子 dp[u][2]=∑vmin(dp[v][1]+∑v′!=vdp[v′][2])dp[u][2]=\ ...

题意：给n个点m条边的无向图，图中可能包含自环和重边，现在有两种操作： 1.删掉一条(a,b)边 2.询问a->b上有多少条关键边，关键边意思为：删掉该边，使得a不能到达b。 所有删除操作都保证图是连通的。 把删除操作倒着加边来搞。 先随便建一颗树，边权为1，若加边(a,b)，那么a到b的路径上的边权都赋值为0 询问a b则为a->b的边权和。用树链来搞。 //author: CHC//First Edit Time: 2015-09-21 23:32#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespac ...