php网站开发外包,wordpress邮箱配置stmp,做网单哪个网站最好用,浙江手机网站建设文章目录考试复盘人生赢家黑红兔考试复盘 T1T1T1 subtask1:n≤5subtask1:n\le 5subtask1:n≤5#xff0c;暴搜点的颜色状态以及边的存在状态
对于一条连接相同颜色点的边#xff0c;可要可不要#xff0c;不会提供形态变化的贡献#xff0c;2edge2^{edge}2edge dpdpdp暴搜点的颜色状态以及边的存在状态
对于一条连接相同颜色点的边可要可不要不会提供形态变化的贡献2edge2^{edge}2edge
dpdpdp
设dp[i][j][0/1]dp[i][j][0/1]dp[i][j][0/1]表示前iii个点颜色为白/黑由前面jjj个点转移过来
好像转移不动。。pass
T2T2T2
n≤15n\le 15n≤15感觉给子任务编号是不同数据下的算法拼凑而来的呢(〃︶)人(︶〃)
subtask1:m≤20subtask1:m\le 20subtask1:m≤20直接2m2^m2m暴搜
竟然空间超限ε(д*)…哭晕在厕所
subtask2:1−2subtask2:1-2subtask2:1−2之间有唯一的一条简单路径
考虑枚举在这条路径上的iii点相遇则除了这条路径以外的边的方向都无所谓
subtask3:n≤10→m≤45subtask3:n\le 10\rightarrow m\le 45subtask3:n≤10→m≤45
subtask4:subtask4:subtask4:一般情况
考虑枚举在点xxx相遇暴搜1−x1-x1−x每一条路径在此基础上搜2−x2-x2−x的每一条路径没被打标记的边可选可不选
但是这里会出现重复的情况因为路径并不是唯一的
emmmmmm▼㉨▼メ难搞哦(・。・)
T3T3T3
字符匹配非常类似最近做的FFTFFTFFT题_(:3J∠)
可仔细想想又不太对劲pass
猜个小结论长度是每段只比上一段加一感觉就是对的
考虑dp[i][j]dp[i][j]dp[i][j]表示串[l,r][l,r][l,r]作为首串最多能接的段数
转移要枚举位置比较串kmpkmpkmphashhashhash好像时间复杂度有点大诶
算了吧。。。
考后
唯一想说的对于这场比赛就只有空间超限了(*Д)つ匚___
人生
n≤2e5n\le 2e5n≤2e5 设endiend_iendi表示以iii为结尾的路径条数
如果endjend_jendj是偶数条连向iii后endiend_iendi也只会加上偶数奇偶性不变
如果endjend_jendj是奇数条连向iii后endiend_iendi会加上奇数奇偶性变化
注意endiend_iendi要加上111自己到自己的路径
由此得知endiend_iendi奇偶性只跟前面与iii连边的点中endjend_jendj是奇数的点的个数有关与实际点是哪个无关
设f[i][j][k][h]f[i][j][k][h]f[i][j][k][h]表示前iii个点有jjj个白点和kkk个黑点的endendend是奇数且前iii个点endendend之和的奇偶性为hhh000偶111奇
对于一个nnn元集合n1n1n1选出一个偶数子集大小或者是一个奇数子集大小的方案数均为2n−12^{n-1}2n−1 简单证明一下(▽)
①nnn为奇数
假设选了iii个iii为奇数那么n−in-in−i个没有选n−in-in−i为偶数
说明每选一种奇数子集大小的方案就会存在一种偶数子集大小的方案
各自占一半2n22n−1\frac{2^n}{2}2^{n-1}22n2n−1
②nnn为偶数
设T(n,1)T(n,1)T(n,1)表示在nnn个中选奇数个的方案数T(n,0)T(n,0)T(n,0)表示在nnn个中选偶数个的方案数
考虑把nnn分成前后各一半
Ⅰ设n/2n/2n/2为奇数
T(n,1)T(n/2,1)∗T(n/2,0)T(n/2,0)∗T(n/2,1)2∗T(n/2,0)∗T(n/2,1)T(n,1)T(n/2,1)*T(n/2,0)T(n/2,0)*T(n/2,1)2*T(n/2,0)*T(n/2,1)T(n,1)T(n/2,1)∗T(n/2,0)T(n/2,0)∗T(n/2,1)2∗T(n/2,0)∗T(n/2,1)
T(n,0)T(n/2,1)∗T(n/2,1)T(n/2,0)∗T(n/2,0)T(n,0)T(n/2,1)*T(n/2,1)T(n/2,0)*T(n/2,0)T(n,0)T(n/2,1)∗T(n/2,1)T(n/2,0)∗T(n/2,0)
先前证明过当xxx为奇数时其选择奇数和偶数的方案数相等
T(n,0)T(n/2,1)∗T(n/2,0)T(n/2,0)∗T(n/2,1)2∗T(n/2,0)∗T(n/2,1)T(n,0)T(n/2,1)*T(n/2,0)T(n/2,0)*T(n/2,1)2*T(n/2,0)*T(n/2,1)T(n,0)T(n/2,1)∗T(n/2,0)T(n/2,0)∗T(n/2,1)2∗T(n/2,0)∗T(n/2,1)
⇒T(n,0)T(n,1)\Rightarrow T(n,0)T(n,1)⇒T(n,0)T(n,1)
Ⅱ设n/2n/2n/2为偶数
递归n/2n/2n/2不停的除以222总有一层是奇数就变成了Ⅰ
证毕 大力讨论列出转移方程
①点i1i1i1为白色且endendend为偶数总和奇偶性不变 f[i1][j][k][h]f[i][j][k][h]∗2k−1∗2i−kf[i1][j][k][h]f[i][j][k][h]*2^{k-1}*2^{i-k}f[i1][j][k][h]f[i][j][k][h]∗2k−1∗2i−k
2k−12^{k-1}2k−1会对i1i1i1奇偶性造成影响的kkk个黑色奇数点从中选择奇数个的方案数endi1end_{i1}endi1有这些黑色奇数点带来的奇数贡献再加上自己到自己本身一条路径就是偶数了
2i−k2^{i-k}2i−k剩下的点与i1i1i1可连可不连不会造成影响
②点i1i1i1为白色且endendend为奇数总和奇偶改变 f[i1][j1][k][h⨁1]f[i][j][k][h]∗2k−1∗2i−kf[i1][j1][k][h\bigoplus1]f[i][j][k][h]*2^{k-1}*2^{i-k}f[i1][j1][k][h⨁1]f[i][j][k][h]∗2k−1∗2i−k
2k−12^{k-1}2k−1会对i1i1i1奇偶性造成影响的kkk个黑色奇数点从中选择偶数个的方案数
③点i1i1i1为黑色且endendend为偶数总和奇偶性不变 f[i1][j][k][h]h[i][j][k][h]∗2j−1∗2i−jf[i1][j][k][h]h[i][j][k][h]*2^{j-1}*2^{i-j}f[i1][j][k][h]h[i][j][k][h]∗2j−1∗2i−j
2j−12^{j-1}2j−1会对i1i1i1奇偶性造成影响的jjj个白色奇数点从中选择奇数个的方案数
④点i1i1i1为黑色且endendend为奇数总和奇偶改变 f[i1][j][k1][h⨁1]f[i][j][k][h]∗2j−1∗2i−jf[i1][j][k1][h\bigoplus 1]f[i][j][k][h]*2^{j-1}*2^{i-j}f[i1][j][k1][h⨁1]f[i][j][k][h]∗2j−1∗2i−j
2j−12^{j-1}2j−1会对i1i1i1奇偶性造成影响的jjj个白色奇数点从中选择偶数个的方案数
如果点i1i1i1被钦定为黑色则没有①②的转移白色则没有③④的转移
观察到每个转移方程中后面两个222的幂乘积与j,kj,kj,k无关都为2i−12^{i-1}2i−1 当j,kj,kj,k为000时从中选偶数个为2i2^i2i选奇数个为000
于是不再需要j,kj,kj,k的实际值了
设f[i][0/1][0/1][h]f[i][0/1][0/1][h]f[i][0/1][0/1][h]表示前iii个点endendend和的奇偶为hhh是否有endendend为奇数的白/黑点
#include cstdio
#define int long long
#define mod 998244353
#define maxn 200005
int f[maxn][2][2][2];
int mi[maxn], c[maxn];
int n;signed main() {scanf( %lld, n );for( int i 1;i n;i ) scanf( %lld, c[i] );mi[0] 1;for( int i 1;i n;i ) mi[i] ( mi[i - 1] 1 ) % mod;f[0][0][0][0] 1;for( int i 0;i n;i )for( int j 0;j 1;j )for( int k 0;k 1;k )for( int h 0;h 1;h ) {if( ! f[i][j][k][h] ) continue;if( c[i 1] ! 1 ) {f[i 1][j][k][h] ( f[i 1][j][k][h] f[i][j][k][h] * ( k ? mi[i - 1] : 0 ) % mod ) % mod;f[i 1][j | 1][k][h ^ 1] ( f[i 1][j | 1][k][h ^ 1] f[i][j][k][h] * ( k ? mi[i - 1] : mi[i] ) % mod ) % mod;}if( c[i 1] ! 0 ) {f[i 1][j][k][h] ( f[i 1][j][k][h] f[i][j][k][h] * ( j ? mi[i - 1] : 0 ) % mod ) % mod;f[i 1][j][k | 1][h ^ 1] ( f[i 1][j][k | 1][h ^ 1] f[i][j][k][h] * ( j ? mi[i - 1] : mi[i] ) % mod ) % mod;}}int ans 0;for( int j 0;j 1;j )for( int k 0;k 1;k )ans ( ans f[n][j][k][1] ) % mod;printf( %lld\n, ans );return 0;
}赢家
n≤15,m≤n×(n1)2n\le 15,m\le \frac{n\times (n1)}{2}n≤15,m≤2n×(n1) 转化为用总数2m2^m2m减去不合法的方案数
不合法方案数即为111能到达的点集SSS222能到达的点集为TTTS∩T∅S∩T\emptysetS∩T∅
设f[S]f[S]f[S]表示能使111到达点集为SSS内所有点的方案数g[T]g[T]g[T]为能使222到达点集为TTT内所有点的方案数
枚举S,TS,TS,T两个集合内部的边的定向方案数即为f[S]×g[T]f[S]\times g[T]f[S]×g[T]不能有边跨越S,TS,TS,T
对于点集S∪TS∪TS∪T的补集中的点内部边可以随便定向2edge2^{edge}2edge而对于一个顶点在集合外另一个顶点在S,TS,TS,T集合内的边一定是从集合外指向集合内
枚举的时间复杂度为O(3n)O(3^n)O(3n)
接下来考虑怎么计算f[S]f[S]f[S]g[T]g[T]g[T]与之一样
一样的思路用总数减去不合法的数量
总数为2edge_S2^{edge\_S}2edge_S
减去不合法的方案枚举一个SSS的真子集s′ss′计算只能到达子集s′ss′内的点的方案数
点集s’s’s’内的方案数为f[s′]f[s]f[s′]点集外的方案数为2edge_S−edge_s’2^{edge\_S-edge\_s’}2edge_S−edge_s’
对于横跨s’,CSs′s’,C_{S}ss’,CSs′的边方向一定是从外面指向子集s′ss′内
所以此时减去的方案数为f[s′]×2edge_S−edge_s′f[s]\times 2^{edge\_S-edge\_s}f[s′]×2edge_S−edge_s′
枚举子集DPDPDP时间复杂度为O(3n)O(3^n)O(3n)
#include cstdio
#define mod 1000000007
#define int long long
#define maxn 20
#define maxm 1 15
int n, m, id;
bool edge[maxn][maxn];
int in[maxm], out[maxm], mi[maxn * maxn], f[maxm], g[maxm];signed main() {scanf( %lld %lld %lld, n, m, id );mi[0] 1;for( int i 1, u, v;i m;i ) {scanf( %lld %lld, u, v );edge[u][v] 1;mi[i] ( mi[i - 1] 1 ) % mod;}int cnt 1 n;for( int S 0;S cnt;S )for( int i 1;i n;i )for( int j 1;j n;j )if( edge[i][j] ) {if( ( 1 i - 1 S ) ( 1 j - 1 S ) ) in[S] ;//完全包含在点集S里面的边if( ( 1 i - 1 S ) || ( 1 j - 1 S ) ) out[S] ;//完全包含在点集S里面的边一个顶点在点集里一个顶点在点集外}for( int S 0;S cnt;S ) {if( ! ( S 1 ) ) continue;//如果没有包含点1 跳过f[S] mi[in[S]];for( int T ( S - 1 ) S;T;T ( T - 1 ) S ) {if( ! ( T 1 ) ) continue;//子集也必须包含点1f[S] ( f[S] - f[T] * mi[in[S ^ T]] % mod mod ) % mod;}}for( int S 0;S cnt;S ) {if( ! ( S 1 1 ) ) continue;g[S] mi[in[S]];for( int T ( S - 1 ) S;T;T ( T - 1 ) S ) {if( ! ( T 1 1 ) ) continue;g[S] ( g[S] - g[T] * mi[in[S ^ T]] % mod mod ) % mod;}}int ans mi[m];for( int S 0;S cnt;S ) { if( ! ( S 1 ) || ( S 1 1 ) ) continue;for( int T ( cnt - 1 ) ^ S;T;T ( T - 1 ) ( ( cnt - 1 ) ^ S ) ) {if( ! ( T 1 1 ) || in[S] in[T] in[S | T] ) continue;//如果没有包含点2 或 S,T点集有边横跨两个集合 为不合法划分 跳过ans ( ans - f[S] * g[T] % mod * mi[m - out[S | T]] % mod mod ) % mod;}}printf( %lld\n, ans );return 0;
}黑红兔
n≤5e5n\le 5e5n≤5e5 性质1存在一种方案最后一段长度为111每选出的段的长度都比上一段小111
很显然如果某一段比下一段长≥2\ge 2≥2可以在前面或者后面去掉若干字符只需要保证下一段是严格子串即可
设f[i][j]f[i][j]f[i][j]表示以子串[i,j][i,j][i,j]为首串能否找出j−i1j-i1j−i1段符合要求
fff为yes/noyes/noyes/no的boolboolbool数组
枚举下一段与f[i1,j]f[i1,j]f[i1,j]还是f[i][j−1]f[i][j-1]f[i][j−1]进行转移
用hashhashhash判断两个串是否相同
性质2答案不超过O(n)O(\sqrt{n})O(n)
最好的情况为12...k12...k12...k此时有k(k1)2≤n\frac{k(k1)}{2}\le n2k(k1)≤n
性质3假设以iii作为第一段开头如果第一个串长lenlenlen时可以选出lenlenlen段那么串长为len−1len-1len−1时也能选出len−1len-1len−1段
非常显然都删去一个首/尾跟下一段无关的字符最后一段被删去仍能保证严格子串性质
设f[i]f[i]f[i]为以iii开始的首串最长能选多少段
考虑二分答案问题转化为找[imid,n][imid,n][imid,n]内是否存在一个jjj满足
f[j]≥mid−1f[j]\ge mid-1f[j]≥mid−1
lcp(i,j)≥mid−1lcp(i,j)\ge mid-1lcp(i,j)≥mid−1或者lcp(i1,j)≥mid−1lcp(i1,j)\ge mid-1lcp(i1,j)≥mid−1看是首/尾是新添的多余字符
如果求出原串的后缀数组那么lcp(i,j)≥xlcp(i,j)\ge xlcp(i,j)≥x相当于rnkjrnk_jrnkj在某个区间内可以二分求出这个区间
此套路做法详情可见亲爱的佳媛姐姐正解做法——字符串LOJ2059
O(nlog2n)O(nlog^2n)O(nlog2n)
性质4f[i]≤f[i1]1f[i]\le f[i1]1f[i]≤f[i1]1
如果iii开始能接大于f[i1]1f[i1]1f[i1]1段那么i1i1i1开始一定能接大于f[i1]1−1f[i1]f[i1]1-1f[i1]f[i1]1−1f[i1]段有性质3得出
所以就不用二分了类似滑动窗口一样先把f[i]f[i]f[i]赋为f[i1]1f[i1]1f[i1]1然后判断是否可行不行就一直−1-1−1直到可行为止
类似于SASASA求heightheightheight数组O(nlogn)O(nlogn)O(nlogn)
预处理ststst表里面的logloglog快了整整三秒卡(ρ)了
终于过了()ノ~
#include cstdio
#include cstring
#include iostream
using namespace std;
#define maxn 500005
#define INF 0x7f7f7f7f
int n, m 255;
char s[maxn];
int tot[maxn], rnk[maxn 1], sa[maxn], id[maxn], x[maxn], h[maxn], lg[maxn];
int st[maxn][20];void init() {for( int i 1;i n;i ) tot[x[i] s[i]] ;for( int i 1;i m;i ) tot[i] tot[i - 1];for( int i n;i;i -- ) sa[tot[x[i]] --] i;for( int k 1;k n;k 1 ) {int num 0;for( int i n - k 1;i n;i ) id[ num] i;for( int i 1;i n;i ) if( k sa[i] ) id[ num] sa[i] - k;memset( tot, 0, sizeof( tot ) );for( int i 1;i n;i ) tot[x[i]] ;for( int i 1;i m;i ) tot[i] tot[i - 1];for( int i n;i;i -- ) sa[tot[x[id[i]]] --] id[i];for( int i 1;i n;i ) rnk[i] x[i];x[sa[1]] num 1;for( int i 2;i n;i )x[sa[i]] ( rnk[sa[i]] rnk[sa[i - 1]] rnk[sa[i] k] rnk[sa[i - 1] k] ) ? num : num;if( n num ) break;m num;}for( int i 1;i n;i ) rnk[sa[i]] i;int k 0;for( int i 1;i n;i ) {if( rnk[i] 1 ) continue;if( k ) k --;int j sa[rnk[i] - 1];while( i k n j k n s[i k] s[j k] ) k ;h[rnk[i]] k;}lg[0] -1;for( int i 1;i n;i ) lg[i] lg[i 1] 1;for( int i 1;i n;i ) st[i][0] h[i];for( int j 1;j 18;j )for( int i 1;i n;i )if( i ( 1 j - 1 ) n ) break;else st[i][j] min( st[i][j - 1], st[i ( 1 j - 1 )][j - 1] );
}int lcp( int l, int r ) {int i lg[r - l 1];return min( st[l][i], st[r - ( 1 i ) 1][i] );
}int cnt;
int rt[maxn], t[maxn * 30], lson[maxn * 30], rson[maxn * 30];void modify( int pre, int now, int l, int r, int pos, int val ) {if( ! now ) now cnt;if( l r ) { t[now] max( t[now], val ); return; }int mid ( l r ) 1;if( pos mid ) rson[now] rson[pre], modify( lson[pre], lson[now], l, mid, pos, val );else lson[now] lson[pre], modify( rson[pre], rson[now], mid 1, r, pos, val );t[now] max( t[lson[now]], t[rson[now]] );
}int query( int now, int l, int r, int L, int R ) {if( ! now || R l || r L ) return 0;if( L l r R ) return t[now];int mid ( l r ) 1;return max( query( lson[now], l, mid, L, R ), query( rson[now], mid 1, r, L, R ) );
}int find_l( int pos, int len ) {int l 1, r pos - 1;while( l r ) {int mid ( l r ) 1;if( lcp( mid 1, pos ) len ) r mid - 1;else l mid 1;}return l;
}int find_r( int pos, int len ) {int l pos 1, r n;while( l r ) {int mid ( l r ) 1;if( lcp( pos 1, mid ) len ) l mid 1;else r mid - 1;}return r;
}bool check( int pos, int len ) {if( query( rt[pos len], 1, n, find_l( rnk[pos], len - 1 ), find_r( rnk[pos], len - 1 ) ) len - 1 )return 1;if( query( rt[pos len], 1, n, find_l( rnk[pos 1], len - 1 ), find_r( rnk[pos 1], len - 1 ) ) len - 1 )return 1;return 0;
}int ans;
int f[maxn];int main() {scanf( %s, s 1 );n strlen( s 1 ); init();ans f[n] 1;modify( rt[n 1], rt[n], 1, n, rnk[n], f[n] );for( int i n - 1;i;i -- ) {f[i] f[i 1] 1;while( ! check( i, f[i] ) ) f[i] --;ans max( ans, f[i] );modify( rt[i 1], rt[i], 1, n, rnk[i], f[i] );}printf( %d\n, ans );return 0;
}
