$$\newcommand{\Ord}{\mathcal{O}}$$

連結:https://tioj.ck.tp.edu.tw/problems/1331

題目大意

給定 $a,b,x,y$ 問下遞迴數列第 $n$ 項的數值是多少,取其除以 $2^{32}$ 的餘數:

$$\begin{cases}S_0&=a\\S_1&=b\\S_n&=xS_{n-2}+yS_{n-1}\end{cases}$$

題解

因為 $n$ 的範圍是 $10^9$,很顯然的要用矩陣快速冪來計算。矩陣的構造方法就如同費式數列

$$\begin{bmatrix}0&1\\x&y\end{bmatrix}^n\begin{bmatrix}S_0\\S_1\end{bmatrix}=\begin{bmatrix}S_n\\S_{n+1}\end{bmatrix}$$

利運快速冪來計算可以在 $O(2^3\times\log{n})$ 計算出答案。

AC Code

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
#include<bits/stdc++.h>
using namespace std;

using u32 = uint32_t;
using matrix = vector<vector<u32>>;
matrix A,T;
//a*=b;
inline void mul(matrix &a, const matrix &b)
{
//static matrix c(2, vector<u32>(2)); //highlight.js render bug...
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
c[i][j]=a[i][0]*b[0][j]+a[i][1]*b[1][j];
a.swap(c);
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

u32 n,a,b,x,y;
while( cin>>n, n<INT_MAX )
{
cin>>a>>b>>x>>y;

A = { { 0,1 },
{ x,y } };
T = { { 1,0 },
{ 0,1 } };
while( n )
{
if( n&1 ) mul(T,A);
mul(A,A);
n/=2;
}

u32 ans = a*T[0][0] + b*T[0][1];
cout<<ans<<'\n';
}
}

連結:

題目大意

有一個字串 $T$,詢問多個字串 $P_i$ 分別在 $T$ 中出現幾次。

題解

很久以前寫過這題,用的是雜湊,不過看起來WA了之後這題就被擱置了,無聊又點開這題,意外地找到當初WA的BUG… 給大家猜猜看:

1
2
3
4
5
6
7
ll pw(ll a,ll e)
{
if(e==0)return 1;
ll t = pow( a*a%MOD , e/2);
if( e&1 )return a*t%MOD;
return t;
}

字串的題目可以考慮使用雜湊的技巧來把題目水過,以這題來說,就可以用Rolling hash直接比對,不過實作上時限稍緊,要把細節處理好才能AC,比較要注意的重點是處理相減的取模時,用 (A-B+M)%MC=A-B; if(C<0)C+=M 慢上至少兩倍,再雜湊中,這常用的細節會大幅度的影響執行時間,要十分注意。

除了雜湊之外,這也是經典的AC自動機要解決的問題,AC自動機可以在 $O(T+\sum P_i)$ 找出每個$P$在$T$中出現幾次,不過OJ開的記憶體有點小,而AC自動機空間時間常數偏大,而且Trie的節點會造成大量閒置空間,會很浪費記憶體。個人是調參數加上靜態分配記憶體硬過的,直接開優化模板應該不會那麼卡。

下面的AC自動機是評演算法直覺裸刻上的版本,通常這東西會細節優化好放在模板中直接用。AC自動機大致上的步驟就是:

  1. 建立Trie
  2. 蓋出fail邊 (build)
  3. 開始走路 (eval)
  4. 把走路的獲得的資料蒐集起來 (calc)

這裡calc的實作是把所有node拓譜排序後,再把答案DP回來。

AC Code

AC 自動機

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
using namespace std;

struct node{
int next[26];
int fail;
int tag;
int hit;
};

int nwid;
vector<node> buf(310000);
int newnode()
{
nwid++;
if( nwid == buf.size() ) while(1);
memset(&buf[nwid], 0,sizeof(buf[0]));

return nwid;
}
using pnode = int;
#define nullptr 0

pnode root = nullptr;
vector<int> query;
map<int,int> ans;
map<string,int> sid;

void build()
{
queue<pnode> qu;
qu.push(root);

buf[root].fail = root;

while(!qu.empty())
{
pnode ptr = qu.front();
qu.pop();

int i=-1;
for(auto e:buf[ptr].next)
{
i++;
if(!e) continue;
qu.push(e);
auto tmp = buf[ptr].fail;
while( tmp!=root && !buf[tmp].next[i] )
tmp=buf[tmp].fail;
if( ptr!=root && buf[tmp].next[i] )
tmp = buf[tmp].next[i];
buf[e].fail = tmp;
}
}
}

void eval(const string &s)
{
pnode ptr = root;
for(int c:s)
{
c-='a';
while( ptr!=root && !buf[ptr].next[c] )
ptr = buf[ptr].fail;
if( buf[ptr].next[c])
ptr = buf[ptr].next[c];
buf[ptr].hit++;
}
}

map<pnode,int> deg;
void dfs(pnode r)
{
deg[r];
deg[buf[r].fail]++;
for(auto e:buf[r].next)
if(e) dfs(e);
}
void calc()
{
deg.clear();
ans.clear();
dfs(root);
deg[root]--;
queue<pnode> qu;
for(auto p:deg)
if(p.second==0)
qu.push(p.first);

while( !qu.empty() )
{
auto ptr = qu.front();
qu.pop();

if(buf[ptr].tag)
ans[buf[ptr].tag]=buf[ptr].hit;

deg[buf[ptr].fail]--;
if( deg[buf[ptr].fail] == 0 )
qu.push(buf[ptr].fail);
buf[buf[ptr].fail].hit += buf[ptr].hit;
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

int T,N;
string tmpl, str;
cin>>T;
while(T--)
{
query.clear();
sid.clear();
nwid=0;
root = newnode();
cin>>tmpl>>N;

for(int i=0;i<N;++i)
{
cin>>str;
if( sid[str] == 0 )
sid[str] = sid.size();
query.push_back(sid[str]);

auto ptr = root;
for(char c:str)
{
if( buf[ptr].next[c-'a'] == nullptr )
buf[ptr].next[c-'a'] = newnode();
ptr = buf[ptr].next[c-'a'];
}
buf[ptr].tag = query.back();
}
build();
eval(tmpl);
calc();
for(int i:query)cout<<ans[i]<<'\n';
}
}

Rolling 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
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;

typedef long long ll;
#define P1 26
#define MOD 1000000009

ll pw1[10005];
void init()
{
pw1[0]=1;
for(int i=1;i<10005;++i)
{
pw1[i]=pw1[i-1]*P1%MOD;
}
}

ll ht1[10001];
char tmpl[10001];

inline void build(char *str)
{
ht1[0]=0;
int i=1;
while( str[i-1] )
{
ht1[i] = (ht1[i-1]*P1+str[i-1])%MOD;
++i;
}
}

inline ll gethash1(int L, int R)
{
ll tmp = ht1[R] - ht1[L-1]*pw1[R-L+1]%MOD;
if( tmp < 0 ) tmp += MOD;
return tmp;
}

inline ll calc( char *str, ll p )
{
ll res = 0;
int i=0;
while(str[i])
{
res = ( res * p + str[i] ) % MOD;
++i;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T,N;
ll hA,lent,len;
cin>>T;
init();
while(T--)
{
cin>>tmpl;
lent = strlen(tmpl);
build(tmpl);
cin>>N;
while(N--)
{
cin>>tmpl;
len = strlen(tmpl);
hA = calc(tmpl,P1);

int sum = 0;
int pos = 0;
while( pos + len <= lent )
{
if( hA == gethash1( pos+1,pos+len ) ) sum++;
pos++;
}
cout<<sum<<'\n';
}
}
return 0;
}

連結:https://tioj.ck.tp.edu.tw/problems/1214

題目大意

判斷兩棵樹是否同構

題解

如果兩棵樹是一樣的,那可以先將樹上唯二的重心、或直徑中點找出來,那就可以一個相同的點,然後再比對樹的最小括號表示法即可完成題目要求。

AC Code

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
#include<bits/stdc++.h>
using namespace std;

vector<int> V[100];

int far,far2;
int dist=0;
void dfs(int v, int fa, int d)
{
if( d > dist ){
far=v;
dist=d;
}
for(int e:V[v])
{
if(e==fa)continue;
dfs(e,v,d+1);
}
}

vector<int> path;
bool findpath(int v, int fa)
{
path.push_back(v);
if( v == far2 ) return true;
for(int e:V[v])
{
if( e==fa ) continue;
if( findpath(e,v) ) return true;
}
path.pop_back();
return false;
}
vector<int> findMid()
{
vector<int> ans;
far=1;
dist=0;
dfs(1,1,0);
dist=0;
far2=far;
dfs(far,far,0);
path.clear();
findpath(far,far);

int sz = path.size();
ans.push_back(path[sz/2]);
if( sz%2 == 0 )
ans.push_back(path[sz/2-1]);
return ans;
}

string hash(int v,int fa)
{
vector<string> res;
for(int e:V[v])
{
if(e==fa)continue;
res.push_back( ::hash(e,v) );
}
sort(res.begin(),res.end());
string h="(";
for(auto &s:res) h+=s;
h+=")";
return h;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

int s,e,N;
while(cin>>N,N)
{
vector<string> h[2];
for(int _=0;_<2;_++)
{
for(int i=1;i<=N;++i)
V[i].clear();
for(int i=1;i<N;++i)
{
cin>>s>>e;
V[s].push_back(e);
V[e].push_back(s);
}
auto mids = findMid();
for(int v:mids)
h[_].push_back(::hash(v,v));
sort(h[_].begin(),h[_].end());
}
if( h[0]==h[1] )cout<<"Same\n";
else cout<<"Different\n";
}
}

連結:https://tioj.ck.tp.edu.tw/problems/1210

題目大意

給定一個度序列,問這個度序列是否能構成一張簡單圖?

題解

最近恰好讀了圖論的書,若一個度序列可以構造出一個簡單圖,該序列又可稱為圖序列,利用度序列判定是否為簡單圖(無自環、重邊)在這本書【演算法觀點的圖論】第一章就有提到了,有兩個定理可以使用:

  1. Erdős–Gallai theorem

若度序列 $d:d_1\geq d_2\geq\dots d_n$ 是圖序列 $\iff$ $\sum d$ 是偶數,且對於 $1\leq k \leq n$都有

$$\sum_{i=1}^k d_i\leq k(k-1) + \sum_{j=k+1}^n \min\{k,d_j\}$$

  1. Havel–Hakimi algorithm

對於$n\geq 2$,若度序列 $d:d_1\geq d_2\geq\dots d_n$ 是圖序列 $\iff$

$$d’:d_2-1, d_3-1, \dots, d_{1+d_1}-1, d_{2+d_1}, d_{2+d_1},\dots, d_n$$

也是圖序列

可以發現第二個方法比較好實作,就是把度數最大的點,都接一條邊到度數較多的邊上。由於數字都是整數,可以利用Counting Sort或是一些技巧,就能在$O(V)$的時間判定是否為簡單圖了。

AC Code

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
#include<bits/stdc++.h>
using namespace std;

int c[10001];
int tmp[10001];
bool test(int mx)
{
memset(tmp,0,sizeof(tmp));
while( mx > 0 )
{
int req = mx, la = mx;
c[mx]--;
while(req>0&&la>0)
{
int del = min(c[la],req);
c[la]-=del;
tmp[la-1]+=del;
req-=del;
la--;
}
if( req ) return false;
while(la<=mx)
{
c[la]+=tmp[la];
tmp[la]=0;
la++;
}
while( !c[mx] ) mx--;
}
return true;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N, tmp;

while(cin>>N,N)
{
int deg=0;
int mx=0;
memset(c,0,sizeof(c));
bool isSimple = true;

for(int i=0;i<N;++i)
{
cin>>tmp;
deg+=tmp;
mx=max(mx,tmp);
c[tmp]++;
}

if( deg%2!=0 ) isSimple = false;
else if( mx >= N ) isSimple = false;
else if( !test(mx) ) isSimple = false;

if( isSimple )cout<<"Yes\n";
else cout<<"No\n";
}
}

連結:https://tioj.ck.tp.edu.tw/problems/1201

題目大意

直線上有$K$個房間,每個房間要不就是社團的人,要不就是怪人(沒社團的人),任兩怪人之間要相隔$M$個房間,已知有$N$種不同的社團,總共有幾種,問有幾種合法的人員放置方法,取除以$P$的餘數。

題解

一開始想到數學解,由枚舉怪人的數量,再把方法數加起來,如果現在有$S$位怪人,顯然要滿足:

  • $ K \geq ( S+(S-1)\times M ) $
  • $ K \geq S + N $

可以先讓所有人以最緊密的方法排列進去,第一個是怪人,再下$M$個空房間,然後再一個怪人,以此類推。最後會剩下$K - ( S+(S-1)\times M )$間自由擺放的房間,數量用$L$表示。根據排列組合,$L$個相同物有$S+1$個相異位置可放入,共有$\binom{L+S}{L}$種方法,故總方法數是$\sum\binom{L+S}{L}\times {N}^{K-S}$,因為不能保證$P$是質數,硬幹$C^n_m$複雜度過高,化簡$C$找通項DP化很麻煩,因此該方法不太合適。

如果是排組問題,可以考慮回到DP的基本想法,因為怪人的數量是任意多的,前面的怪人數量不影響答案,因此狀態可以如無限背包問題一樣,設$dp[i]=$有$i$個房間時,答案為何,考慮最後一個房間的狀況:

  1. 是怪人:那樣要扣掉$1+M$個位置給怪人與空位,答案有$N^M\times dp[i-M-1]$那麼多種

  2. 不是怪人:最後一個格子有$N$種可能,答案有$N\times dp[i-1]$那麼多種

最後的答案即上兩狀況的和,狀態與轉移都超乾淨,複雜度是$O(K)$

AC Code

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll dp[65536+1];
ll pw[65536+1];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

ll N,M,K,P,ans;

while(cin>>N>>M>>K>>P,N)
{
ans = 0;
pw[0]=dp[0]=1;
for(ll i=1;i<=K;++i)
{
pw[i] = pw[i-1] * N % P;
ll v1 = dp[i-1] * N % P;
ll L = min(M,i-1) ;
ll v2 = dp[i-1-L]*pw[L]%P;
dp[i]=(v1+v2)%P;
}
cout<< dp[K] << '\n';
}
}

心得

平日練習隨意寫的

A

水題,略

B

水題,略

C. Covered Points Count

AC code

利用掃描線的概念,按照$x$軸順序排序,將事件排好記數即可。

D. Yet Another Problem On a Subsequence

AC code

可以利用動態規劃(DP)來計算答案,若子序列$p$是合法的,則將$p$的第一個 good array 去掉後剩餘的部分也是合法的,假定$dp[i]$表示子序列開頭在第$i$項時,有多少數列滿足題目的條件,若$a_i\leq 0 $,則答案為$0$,否則,可以在第$i$項後的$j$個數字任意挑$a_i$個數字,挑完後在乘上$dp[j+1]$,為剩下的部分有多少合法序列。最後的答案即為$dp$陣列的總和。

$$dp[i]=\begin{cases} 1 & i = N+1 \\ \sum_{j=i+a_i}^{N} \binom{j}{i}dp[j+1] & \text{otherwise} \end{cases}$$

E. We Need More Bosses

F

G