Believe it

相信不屈不挠的努力,相信战胜死亡的年轻

给个n,让你构造一个\(n\times n\)的矩阵满足每一行每一列都是1-n的排列且对于所有的i!=j都有A[i,j]!=A[j,i]

​ 奇数很好处理,但是偶数不好搞,

​ 对于一个偶数2k

​ 我们假设构造出了k*k的矩阵B是成立的了

​ 看这个矩阵C[i,j]=B[i,j]+k

​ C B1

​ B2 C

​ 我们把B1沿着自己的主对角线翻转

​ 那么现在B2与B1关于2k*2k主对角线对称

​ 我们让B2中的1变成2,2变成3,3变成4

​ 构造完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// 最低位的1 ->                  x&-x
// 去掉最低位的1 -> x&(x-1)
// 有效数字全是1 -> (x&(x+1))==0
//把最低位的0 变成1-> x|(x+1)
//取出最低位的0并变成1 (~x)&(x+1)
//取出第k位(约定最低位为第0位) x&(1<<k)


/* all

bit cnt one -> cnt_one(x) -> int __builtin_popcount (unsigned int x);
bit rev -> rev_dig(x) ->
high bit -> high_one(x)
count leading zero -> cnt_leading_zero(x) -> int __builtin_clz (unsigned int x);
count trailing zero -> cnt_trailing_zero(x) -> int __builtin_ctz (unsigned int x);
get trailing one -> get_trailing_one(x) -> x&(x^(x+1))

*/
typedef unsigned int u32;
namespace bit{

//count the digits of one in binary number
u32 co[65536u];//bit cnt one
void cnt_one_ini() {
for (u32 i = 1; i < 65536u; i++)
co[i] = co[i >> 1] + (1 & i);
}
u32 cnt_one(u32 x) {
return co[x & 0xffffu] + co[x >> 16];
}


//reverse the digits in binary number
u32 rd[65536u];//bit rev data
void rev_digit_ini() {
for (u32 i = 1; i < 65536u; i++)
rd[i] = (rd[i >> 1] >> 1) | ((i & 1) << 15);
}
u32 rev_dig(u32 x) {
return rd[x >> 16] | (rd[x & 0xffffu] << 16);
}


//get the highest digit one in binary number
u32 ho[65536u];//high bit data
void high_one_ini(){
ho[1]=1;
for(u32 i=2;i<65536u;i++){
ho[i]=ho[i>>1]<<1;// only the one have the highest digit one 1;
}
}
u32 high_one(u32 x){
return x<65536u ? ho[x]:(ho[x>>16]<<16);
}


//count leading zero
u32 clz[65536u];//leading zero count
void cnt_leading_zero_int(){
clz[0]=16;
for(u32 i=1;i<65536u;i++){
clz[i]=clz[i>>1]-1;
}
}
u32 cnt_leading_zero(u32 x){
if(x<65536u){
return clz[x]+16;
}
else {
return clz[x>>16];
}
}

//count trailing zero
u32 ctz[65536u];//trailing zero count
void cnt_trailing_zero_int(){
ctz[0]=16;
for(u32 i=1;i<65526u;i++){
ctz[i]=i&1 ? 0: ctz[i>>1]+1;
}
}
u32 cnt_trailing_zero(u32 x){
if(x<65536u){
return ctz[x];
}
else {
return ctz[x&65535u];
}
}

//count leading one is more diffcult using count leading zero


//提取第k个1
int kthbit(u32 x, int k) {
int s[5], ans = 0, t;
s[0] = x;
s[1] = x - ((x & 0xAAAAAAAAu) >> 1);
s[2] = ((s[1] & 0xCCCCCCCCu) >> 2) + (s[1] & 0x33333333u); s[3] = ((s[2] >> 4) + s[2]) & 0x0F0F0F0Fu;
s[4] = ((s[3] >> 8) + s[3]) & 0x00FF00FFu; t = s[4] & 65535u;
if (t < k) k -= t, ans |=16, x >>=16;
t = (s[3] >> ans) & 255u;
if (t < k) k -= t, ans |= 8, x >>= 8; t = (s[2] >> ans) & 15u;
if (t < k) k -= t, ans |= 4, x >>= 4; t = (s[1] >> ans) & 3u;
if (t < k) k -= t, ans |= 2, x >>= 2; t = (s[0] >> ans) & 1u;
if (t < k) k -= t, ans |= 1, x >>= 1; return ans;
}
};

博弈常常是acm中的签到题,能不能快速拿下,这得看本事。

局面决定一切

首先有以下的结论:

  • 胜负取决于局面
  • 如果当前局面能转移给对手的一个输的局面,那么对手就输
  • 如果当前局面转转移给对手的全是赢的局面,那么对手就赢

依据上诉三条规则,博弈题目也可以通过模拟来实现找规律

例题1

有a,b两个数字,两人轮流操作,每次可以选择两个之中较小的数字,然后另一个数字减去选择数字的任意倍数(不能减到负数),直到其中一个为0,不能操作为败。比如2,8可以转移为(2,6)(2,4)(2,2)(2,0)

题解

不妨设\(a\ge 2b\)

  • 如果局面(a%b+b,b)先手赢,则局面(a,b)先手就赢

  • 如果局面(a%b+b,b)先手输,则a,b先手可以花样拿使得后手得到(a%b+b,b), 最后先手还是赢

对于其他a,b其实只有一种拿法,简单处理一下,细心就行了

例题2

有一个从1到n的连续自然数序列,两人轮流操作,可以选取一个数字,拿走它的所有因子(如果序列中存在),直到一方无法拿,该方输。

题解

我们先考虑一个这个序列2,3,4,5,6......n,

  • 如果先手输,题目的序列中我们就拿1,题目中先手赢

  • 如果先手赢,先手总得拿一个吧,假设他拿的x,题目中我们也拿x,题目中先手赢

例题3

鲍勃和爱丽丝正在玩一款新游戏。 有n个盒子从1到n编号。 每个盒子都是空的或包含几张卡片。 鲍勃和爱丽丝依次移动卡片。 在每个回合中,相应的玩家应该选择非空框A,然后选择另一个框B,其中B <A &&(A + B)%2 = 1 &&(A + B)%3 = 0。 然后,从方框A取任意数量(但不是零)的牌到方框B。最后一个可以进行合法移动的人获胜。 爱丽丝是第一个玩家。 请预测谁将赢得比赛。

题解

我们发现1,3,4是无法操作的盒子

有且仅有这三个盒子,

我们按照n%6=1,3,4和n%6=0,2,5把所有的盒子分为两类

考虑二分图模型,这就是一个二分图模型

除了1 3 4以外,所有其他点都存在出度,我们可以想象,比赛结束时所有卡片都在1 3 4 中

那么第一类盒子,不影响比赛结果,

因为每当对手操作了第一类盒子,我们可以操作第二类盒子让这些卡转移到1 3 4 中并恢复到对手上一次操作前到第二类盒子状态,

那么右边的盒子问题就是一个NIM问题

例题4

有一个\(n\times n\)的网格,左下角有一个东西可以在格子里面走,可以往相邻的格子走,已经走过的格子不能再走,两人轮流走,谁不能走谁输

题解

只要当前可以走的区域数目为奇数那么就可以赢,除非对手想打破这个僵局,也就是说,对手走了一步之后,把可以走的区域分成了两部分,只能选择其一,那么我们肯定选取走完之后剩余可以走的格子数为奇数部分那边走啊,也就是说\(n*n-1\)为奇数先手就赢了,也就是n为偶数先手就赢了。

例题5

有n张牌,两个人轮流抓牌,只能抓二的某个幂次方张牌,谁拿最后一张牌谁赢

题解

n%3==0,先手一定输,因为先手拿了以后一定会变成非三的倍数,后手可以拿1张或两张使得n回到三的倍数,局面还原,直到n=3,先手就输了。

至于其他的博弈题目,一般不是那么容易找到规律的,所以产生了新的算法来模拟博弈进行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//sgf是转移方法
//sgs是前一个状态的集合
int sgf[N],sg[N];
bool sgs[N];
void sgf_ini(){
sgf[0]=1;
sgf[1]=1;
sgf[2]=2;
for(int i=3;i<20;i++){
sgf[i]=sgf[i-1]+sgf[i-2];
//cout<<sgf[i]<<endl;
}
}
void sg_ini(int n){
sgf_ini();
//sg[0]=0;
for(int i=1;i<=n;i++){
memset(sgs,0,sizeof(sgs));
for(int j=1;/**/i-sgf[j]>=0;j++)sgs[sg[i-sgf[j]]]=true;
for(int j=0;;j++)if(!sgs[j]){
sg[i]=j;
break;
}
}
//for(int i=0;i<=n;i++){
// printf("%4d %2d",i,sg[i]);
// if(i%10==9)cout<<endl;
//}
}

博弈并不是公平的,博弈的胜负取决于博弈当前的局面。

必胜态的后继中一定有一个必败态

必败态的后继中一定全是必胜态

这其实可以对应到一个运算法则mex集合运算

mex运算:集合中不存在的最小的非负整数

我们定义0为失败,其他数字为胜利,(这里我并不理解为什么要用其他数字而不是1,肯能是还有其他用途)

对于sg[i],我们参考dp算法

假设nex是i的后继,那么sg[i]=mex{sg[nex1],sg[nex2],sg[nex3]。。。

给你一个括号数组,里面有不同种类的括号,每个种类都有左右两种括号,左右括号可以结合,很多组询问,问你一个区间内括号是否匹配, 1.一个空的字符串是一个合法的文档。 2.如果A,B都是合法的文档,那么AB也是合法的文档。 3.如果S是合法的文档,那么aSb也是合法的文档,其中a,b是同一种括号,并且a是左括号,b是右括号

用栈来模拟,对于每一个括号,我们用数组L记录当处理完这个括号(压入栈并完成当前匹配)的栈顶元素的下标,当我们判断[l,r]时之用比较L[l-1]与L[r]即可

对于尺取法,一般用于线性表的处理。

我们有两个指针一样的东西,l和r分别指向两个元素,l于r之间的东西就是我们尝试维护的东西。

例题1

询问序列中和大于s的子串的最小长度。

题解

初始左端点为0,右端点为n-1, 长度为n-1

如果当前区间不满足,同时右移左右端点

如果当前区间满足,最小长度自减

例题2

询问序列中以第k个元素为起点的长度为n的子串的前缀和的最小值大于s的最小i

题解

设立一个前缀和最小值,以及区间和,让尺子长度逐渐增大,增大到N时结束

如果当前区间最小值满足,右移右端点,更新区间和,如果区间和小于于最小值,那么当我们右移左端点时当前最小前缀和在右端点不动时永远都是整个区间和,右移左端点直到区间和大于s,迭代

例题3

询问序列中与值t相差最小的子串和

题解

​ 对前缀和排序,再尺取

​ 如果右端点减去左端点大于t,尝试用此时的端点来更新答案,然后右移左端点,如果右端点减去左端点依旧大于t,迭代,反之先尝试更新答案,然后右移右端点直到右端点减去左端点大于t(最后一次移动前尝试更新答案),迭代

例题4

询问序列中包含所有值的最短子串

题解

​ 建立map记录有没有,cnt记录种类,以加快判断,

​ 如果当前区间不满足,右移右端点,如果此时长度大于或等于已经找到的最小长度(初始化为无穷大),右移左端点,迭代

​ 如果当前区间满足,更新最小长度,右移右端点,迭代

无限大的棋盘有一只走‘日’的马呆在0,0处,也是坐标原点,(存在四个象限),给你(x,y)问你要至少跳多少步才能跳过去

不妨设\(x>y\)

\(x\le2y\),可以证明当x和y足够大的时候

\((x+y)\mod3=0\)时,我们只需要\(\frac{x+y}{3}\)步,这些步数由两种跳跃组成,他们分别是(1,2)和(2,1)

\((x+y)\mod 3=1\)时,我们选择(1,-2)或者(-2,1)来跳跃,跳跃之后\((x+y)\mod3=0\)所以一共需要\(\frac{x+y}{3}+1\)

同理\((x+y)\mod 3=2\)时一共需要\(\frac{x+y}{3}+2\)

综合为需要\(\frac{x+y}{3}+((x+y)\mod 3)\)

同样分析出\(x>2y\)\(x\)\(y\)足够大的时候,需要\(y+\frac{x-2y}{4}\times2+(x-2y)\%4\)

那么这个足够大是多少呢?是x>3&&y>3

就像cantor映射一样,字符串hash采取一种更加随机化的映射,它的通项公式为\(hash[i]=\sum _{j=0}^{i}s[j]*p^{i-j}\),如此将一个字符串随机映射到了一个数字上,

我们来看这个公式的意义,他把一个字符串映射到了一个p进制数字上,位数代表着字符串的长度,然后我们将这个p进制数转化为十进制数并对1e9+7取模来存储,通项公式不好求,但是我们可以通过递推公式来求

\(hash[i]=hash[i-1]\cdot p+s[i]\)

这个公式就比较友好了,另外对于任意区间,我们有这个公式

\(hash[l~r] = hash[r] - hash[l - 1] \cdot pow(p, r - l + 1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
struct str_hash {//单hash
static const int maxn = 3e5 + 5, p = 47, mod = 1e9 + 7;
static int pw[maxn], pr[maxn];
int h1[maxn], h2[maxn], len;

str_hash() {
if (pw[0] == 1) return;
pw[0] = pr[0] = 1;
int rev = qpow(p, mod - 2, mod);
for (int i = 1; i < maxn; i++) {
pw[i] = 1ll * pw[i - 1] * p % mod;
pr[i] = 1ll * pr[i - 1] * rev % mod;
}
}

void extend(char c) {
len++;
h1[len] = (1ll * h1[len - 1] * p + c) % mod;
h2[len] = (h2[len - 1] + 1ll * c * pw[len - 1]) % mod;
}

void ini() { len = 0; }

int query(int l, int r) { return (h1[r] + 1ll * h1[l - 1] * (mod - pw[r - l + 1])) % mod; }//注意没有下标检查
int qurev(int l, int r) { return 1ll * (h2[r] - h2[l - 1] + mod) * pr[l - 1] % mod; }//注意没有下标检查
};

int str_hash::pw[maxn], str_hash::pr[maxn];


//双hash,双倍常数,1e6 的数据 nlgn的做法 1s的时限 不建议使用
typedef unsigned long long ull;

struct double_hash {
static const ull maxn = 1e3 + 666, p = 26, mod1 = 1e9 + 7, mod2 = 1e9 + 9;
static ull pw1[maxn], pw2[maxn];
ull hash1[maxn], hash2[maxn], len;

double_hash() {
if (pw1[0] == 1)return;
pw1[0] = pw2[0] = 1;
for (ull i = 1; i < maxn; i++) {
pw1[i] = pw1[i - 1] * p % mod1;
pw2[i] = pw2[i - 1] * p % mod2;
}
}

void build(char *s, ull _len) {
len = _len;
for (ull i = 1; i <= len; i++) {
hash1[i] = (hash1[i - 1] * p + s[i] - 'a') % mod1;//无边界
hash2[i] = (hash2[i - 1] * p + s[i] - 'a') % mod2;//same
}
}

ull query1(ull l, ull r) { return (hash1[r] - hash1[l - 1] * pw1[r - l + 1] % mod1 + mod1) % mod1; }

ull query2(ull l, ull r) { return (hash2[r] - hash2[l - 1] * pw2[r - l + 1] % mod2 + mod2) % mod2; }

ull query(ull l, ull r) { return query1(l, r) * mod2 + query2(l, r); }//注意没有下标检查
} hash_a, hash_b;

ull double_hash::pw1[maxn], double_hash::pw2[maxn];

http://codeforces.com/contest/727/problem/E

给你一个长度为n×k的环,环上每一个位置有一个字符。现在给你g个长度为k的字符串,问是否可以在g个字符串中选出n个构成这个环。 1 ≤ n ≤ 10^5, 1 ≤ k ≤ 10^5, n*k ≤ 10^6, n ≤ g ≤ 10^5, g*k ≤ 2*10^6

枚举起点,hash.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
inline void GetNext(char *s) {
int l = strlen(s), t;
next[0] = -1;
for (int i = 1; i < l; ++i) {
t = next[i - 1];
while (s[t + 1] != s[i] && t >= 0)
t = next[t];
if (s[t + 1] == s[i])
next[i] = t + 1;
else
next[i] = -1;
}
}

inline void KMP(char *s1, char *s2) {
ans.clear();
GetNext(s2);//预处理next数组
int len_1 = strlen(s1);
int len_2 = strlen(s2);
int i = 0, j = 0;
while (j < len_1) {
if (s2[i] == s1[j]) {
++i;
++j;
if (i == len_2) {
ans.push_back(j - len_2 + 1);
i = next[i - 1] + 1;
}
} else {
if (i == 0)
j++;
else
i = next[i - 1] + 1;
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const double eps=1e-8;
struct MCMF{
static const int maxn=200,maxm=40000;
struct star{int v,nex;double c,w;} edge[maxm<<1];
int head[maxn],cnt,n;
int inq[maxn],pre[maxn];
double dist[maxn];

void ini(int n){
cnt=-1;this->n=n;
for(int i=0;i<=n;i++) head[i]=-1;
}
void add_star(int u, int v, double c, double w){
//cout<<" "<<u<<" "<<v<<" "<<c<<" "<<w<<endl;
edge[++cnt]=star{v,head[u],c, w}; head[u]=cnt;
edge[++cnt]=star{u,head[v],0,-w}; head[v]=cnt;
}
void minCostMaxFlow(int s, int t,double&flow,double&cost){
flow=cost=0;
while(true){
for(int i=0;i<=n;i++) dist[i]=1e9;
queue<int>que; que.push(s);
inq[s]=1; dist[s]=0;

while(!que.empty()){
int u=que.front();
que.pop(); inq[u]=0;
for(int i=head[u];~i;i=edge[i].nex){
int v=edge[i].v;
double c=edge[i].c,w=edge[i].w;
if(c>eps&&dist[v]>dist[u]+w+eps){
// if(c>0&&dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
pre[v]=i;
if(!inq[v]) que.push(v);
inq[v]=1;
}
}
}
if(dist[t]==1e9) return ;
double addf=1e9;
for(int x=t;x!=s;x=edge[pre[x]^1].v) addf=min(addf,edge[pre[x]].c);
for(int x=t;x!=s;x=edge[pre[x]^1].v){
edge[pre[x]].c-=addf;
edge[pre[x]^1].c+=addf;
}
flow+=addf;
cost+=dist[t]*addf;
}
}
} g;