相关链接
题目传送门:https://www.codechef.com/problems/MAGICSTR
解题报告
官方题解是$O(n^2)$的
不过我们有了去年SCOI D1T3的人生经验之后
就可以再后面将整个串折叠,然后单个回文串可以拆成两个区间相等
最后再整体用并查集搞一搞
时间复杂度:$O(n \log n)$,不知道比标算高到哪里去了
题目传送门:https://www.codechef.com/problems/MAGICSTR
官方题解是$O(n^2)$的
不过我们有了去年SCOI D1T3的人生经验之后
就可以再后面将整个串折叠,然后单个回文串可以拆成两个区间相等
最后再整体用并查集搞一搞
时间复杂度:$O(n \log n)$,不知道比标算高到哪里去了
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4773
神犇题解:http://www.cnblogs.com/lytccc/p/6616625.html
我们可以使用倍增Floyd来解决这个问题
具体来讲:
我们从大到小维护走$2^k$步后的最短路
如果出现负环,那么不继承,舍弃掉更改
如果没有出现负环,那么更新数组
时间复杂度:$O(n^3 \log n)$
题目传送门:http://codeforces.com/contest/781/problem/D
话说这个题,你看他的路径定义多么奇怪
构造方式就是倍增嘛!
那我们也来倍增吧!
于是搞一个bitset记录哪些点可以到达就可以辣!
时间复杂度:$O(\frac{n^3 \log 10^{18}}{64})$
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 501; const int M = N * N; const LL INF = 1000000000 * 1000000000ll; bitset<N> f[60][N][2],ans,pre; int n,m; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main() { n = read(); m = read(); for (int i=1,u,v;i<=m;i++) { u = read(); v = read(); f[0][u][read()][v] = 1; } for (int s=0;s<59;s++) { for (int i=1;i<=n;i++) { for (int t=0;t<=1;t++) { for (int j=1;j<=n;j++) { if (f[s][i][t][j]) { f[s+1][i][t] |= f[s][j][t^1]; } } } } } ans[1] = 1; LL vout = 0; for (int s=59,t=0;~s;s--) { pre = ans; ans.reset(); for (int i=1;i<=n;i++) if (pre[i]) ans |= f[s][i][t]; if (ans.count()) { vout += 1ll << s; t ^= 1; } else ans = pre; } printf("%lld\n",vout>INF?-1:vout); return 0; }
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4722
神犇题解Ⅰ:http://blog.csdn.net/werkeytom_ftd/article/details/54429577
神犇题解Ⅱ:http://www.cnblogs.com/wxxlouisa/p/6139165.html
看完题解后:果然是乱搞题!
先不管修改操作的话,如果询问的区间长度超过13的话,一定有解
相关证明可以参见:http://blog.csdn.net/werkeytom_ftd/article/details/54429577
现在考虑修改操作
因为单次询问最多涉及13个数
所以只需要支持单点查询+区间修改就可以了
于是用线段树打标记什么的就可以啦!
然而我们惊讶的发现,我们打的Tag在最后计算的时候会很大
More Formally:次数会爆 $ long long$
于是用不了快速幂了 QwQ
然后又不会了
于是接着去膜拜题解
发现我们可以用类似快速幂一样的东西搞出来
我们最终要求的是:$ {a_i}^{{3^x}}$
于是我们预处理出 $ f(i,j)$ 表示 $ {a_i}^{{3^{{2^j}}}}$
于是像快速幂一样搞一搞就可以啦!
最后我们求出了这13个数是什么,怎么判断有没有解呢?
我们可以 Meet in middle !
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4551
双倍经验:http://www.lydsy.com/JudgeOnline/problem.php?id=3319
神犇题解:http://medalplus.com/?p=1685
离线做法 O(nlogn)
考虑将每一次标记的时间记录到点上
然后使用倍增LCA的思想向上倍增
离线做法 O(nα(n))
考虑离线之后进行逆序操作
这样的话,操作就变成了删除标记
这个可以形象地想成:打通了向上走地道路
于是使用并查集即可
ps:和BZOJ_3319是一毛一样的
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100000+9; int head[N],to[N],nxt[N],anc[N],fa[N]; int n,m,tot,opt[N],tag[N],vout[N]; char pat[10]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline int find(int w) { int f=fa[w],tmp; while (fa[f] != f) f = fa[f]; while (w != f) tmp=fa[w], fa[w]=f, w=tmp; return f; } inline void Add_Edge(int u, int v) { static int T = 0; to[++T] = v; nxt[T] = head[u]; head[u] = T; } void DFS(int w, int last) { if (tag[w]) last = fa[w] = w; else fa[w] = last; for (int i=head[w];i;i=nxt[i]) { anc[to[i]] = w; DFS(to[i],last); } } int main(){ n = read(); m = read(); for (int i=1,u,v;i<n;i++) { u = read(); v = read(); Add_Edge(u,v); } for (int i=1;i<=m;i++) { scanf("%s",pat+1); opt[i] = read(); if (pat[1] == 'C') tag[opt[i]]++; else opt[i] *= -1; } tag[1]++; DFS(1,1); for (int i=m;i;i--) { if (opt[i] > 0) { if (!(--tag[opt[i]])) { fa[opt[i]] = anc[opt[i]]; } } else { vout[++tot] = find(-opt[i]); } } while (tot) printf("%d\n",vout[tot--]); return 0; }
题目传送门:http://codeforces.com/problemset/problem/309/B
鏼爷给的倍增的例题
先滑动窗口搞出每个单词开始的合法解
然后搞一搞倍增
于是枚举起点,总体O(nlogn)
然而我是面向数据编程的…..
感觉会被叉掉 ╥﹏╥…
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 6000000+9; const int M = 1000000+9; char pat[N]; int n,r,c,sta[M],len[M],trans[M][18],position,vout; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main(){ n = read(); r = read(); c = read(); gets(pat+1); for (int i=1,tmp=strlen(pat+1);i<=tmp;i++) if (pat[i] == ' ') { pat[i] = 0; } for (int i=1,w=0;i<=n;i++) { sta[i] = ++w; len[i] = strlen(pat+w); w += len[i]; } for (int i=1,tail=1,tmp=len[1];i<=n;i++) { if (len[i] > c) { tail = (i + 1) % (n + 1); tmp = len[tail]; } else { while (tail < n && tmp + len[tail+1] + 1 <= c) { tmp += len[++tail] + 1; } trans[i][0] = tail + 1; tmp -= len[i] + (tail > i); if (!tmp) { tail = (i + 1) % (n + 1); tmp = len[tail]; } } } trans[n][0] = n; for (int t=1;t<=17;t++) { for (int i=1;i<=n;i++) { trans[i][t] = max(trans[i][t-1],trans[trans[i][t-1]][t-1]); } } for (int i=1,tmp=0,p=i;i<=n;tmp=0,p=++i) { for (int j=17,w=1<<17;~j;j--,w>>=1) if (tmp+w <= r){ tmp += w; p = max(p,trans[p][j]); if (p == n+1) break; } if (p - i > vout) { vout = p - i; position = i; } } if (vout) for (int i=1,beg=position,end;i<=r&&beg<=n;i++) { end = trans[beg][0] - (beg != n || len[trans[beg][0]] > c); if (end < beg) break; for (int j=beg;j<=end;j++) { printf("%s%c",pat+sta[j],j==end?'\n':' '); } beg = end + 1; } return 0; }