1005.0 vs 1
博弈，模拟
题意
两人名为零和壹，在给定的 $01$ 串上进行博弈
零只能取走两端的某一个 $0$ ，壹只能取走两端的某一个 $1$ ，零执先
先不能取的人判负，若取完则判平局
解题思路
模拟博弈过程，当前操作者 $x$ 可以可以遵循以下策略：
- 两端不同，只能取 $x$ 的一端，交替操作权
- 两端相同
- 两端都不是 $x$ ，无法操作，失败
- 两端都是 $x$ ，假设取了某端
- 这端的下一个数字是 $x$ ，则两端都是 $x$ ，对方无法操作，获胜
- 这端的下一个数字是 $!x$ ，则对方只能取这一端
- 如果离任一端最近的连续两个相同的数都为 $x$ ，则根据上 $2$ 一直取到 $x$ 获胜
- 如果离两端最近的连续两个相同的数都为 $!x$ ，则不论选哪端，最终都会到达两端都为 $!x$ 的情况，失败
- 特判：如果整个串有且仅有 $1$ 段连续两个相同的 $!x$ ，则从两端向中间将各会取掉一个，达成平局
可以结合代码注释理解这一过程
时间复杂度
$O(n)$
参考代码
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
| void solve_s(deque<int> s,int now){
ll n=s.size(),i,j;;
if(s.empty()) {cout << "-1" << endl;return ;}
if(s.front()!=s.back()){
if(s.front()==now){
s.pop_front();solve_s(s,(now?0:1));return ;
}else{
s.pop_back(); solve_s(s,(now?0:1));return ;
}
}else{
if(s.front()!=now) {cout << (now?"0":"1") << endl;return ;}
for(i=0;i<n-1;i++) if(s[i]==s[i+1]) break;
if(i==n-1) {cout << "-1" << endl;return ;}
if(s[i]==now) {cout << (now?"1":"0") << endl;return ;}
for(j=n-1;j>i;j--) if(s[j]==s[j-1]) break;
if(s[j]==now) {cout << (now?"1":"0") << endl;return ;}
if(i+1==j) {cout << "-1" << endl;return ;}
{cout << (now?"0":"1") << endl;return ;}
}
}
void solve(){
ll n;cin >> n;
string ts;cin >> ts;
deque<int> s(n);for(ll i=0;i<=n-1;i++) s[i]=ts[i]-'0';
solve_s(s,0);
}
|
1007.Solubility
并查集/DFS
题意
给定 $n$ 个元素之间的 $m$ 对等价关系，问指定 $k$ 个元素是否属于同一等价类
解题思路
这里给出两种解题思路：
- DFS：建无向图，DFS判断指定元素是否在同一个连通分量里
- 并查集：标准并查集板子题，裸套即可
参考代码
- DFS
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
| #define N 100005
int visited[N]={0};
vector<vector<ll>> G;
void DFS(ll x){
visited[x]=1;
for(auto v:G[x]){
if(!visited[v]) DFS(v);
}
}
void solve()
{
ll m,n;cin >> n >> m;
G.clear();G.resize(n+1);
for(ll i=1;i<=n;i++) visited[i]=0;
ll u,v;
for(ll i=1;i<=m;i++){
cin >> u >> v;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
ll k;cin >> k;
vector<ll> s(k);for(auto &x:s) cin >> x;
DFS(s[0]);
for(auto x:s) if(!visited[x]) {cout << NO;return ;}
cout << YES;
}
|
- 并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void solve(){
ll n,m;cin >> n >> m;
DSU dsu(n);
ll a,b;
for(ll i=1;i<=m;i++){
cin >> a >> b;
dsu.merge(a,b);
}
ll k;cin >> k >> a;a=dsu.find(a);
for(ll i=2;i<=k;i++){
cin >> b;b=dsu.find(b);
if(b!=a) {cout << NO;for(ll j=i+1;j<=k;j++) cin >> n;return ;}
}cout << YES;
}
|
1008.Expectation of Rank
线性代数-矩阵与向量空间、期望、动态规划
题意
给定两个正整数 $n,p$ ，其中 $p$ 是质数
$n$ 阶矩阵 $\bf A$ 中的所有元素随机在 $p$ 的有限域 $\mathbb{F}_p$ 中产生，求矩阵 $\bf A$ 的秩的期望 $\mathbb{E}(rank(\bf A))$ ，答案取模
前置知识点
- 有限域 $\mathbb{F}_p$ ：在本题中可以粗略的理解为 $[0,p-1]$ 的整数集
- 线性代数-矩阵与向量空间基础知识：多维向量与向量组、线性相关、矩阵的秩与向量之间的关系、向量组张成向量空间的概念等
建议在学习过《线性代数》课程后再解决本题。
解题思路
一个含 $k$ 个向量的极大无关组可以张成一个 $k$ 维向量空间
在 $p$ 的有限域 $\mathbb{F}_p$ 下，每一维度上的坐标有 $p$ 种选择，故以该极大无关组为基，通过线性组合可以产生 $p^k$ 种不同的 $k$ 维向量（高维包含低维）
顺带一提，这并不意味着这 $p^k$ 种向量仅有 $k$ 位坐标非 $0$
矩阵 $\bf A$ 的每一行可以视为一个 $n$ 维向量，前 $i$ 行的秩表示了前 $i$ 个向量组成的向量组，其极大无关组中有多少个向量。这也意味着前 $i$ 行已经张成了一个多少维度的向量空间
构造DP数组， $dp_{i,k}$ 用以表示矩阵 $\bf A$ 前 $i$ 行的秩为 $k$ 的方案数
假设前 $i-1$ 行的秩为 $k$ ，那么其张成的向量空间为 $k$ 维，考虑状态转移：
- 第 $i$ 行中可以构造出 $p^k$ 个向量落在这个向量空间中，并不改变秩（或者说维数）
- 余下 $p^n-p^k$ 个向量将与前 $i-1$ 个向量线性无关，并使张成的空间增大一维，秩 $+1$
综上所述，构造出以下状态转移方程：
$$dp_{i,k}=
\begin{cases}
0 \qquad,k>i\quad(rank_i\le i恒成立) \newline
1 \qquad,k=0\quad(当且仅当全为 \bf{0} \text{向量}) \newline
\sum\limits_{j=1}^{i-1} dp_{i-1,j}\times p^j + dp_{i-1,j-1}\times (p^n-p^j) &,Otherwise
\end{cases}
$$
总方案数为 $(p^n)^n=p^{n^2}$ ，最终期望为 $\dfrac{1}{p^{n^2}}\sum\limits_{j=1}^{n} j\times dp_{n,j}$
时间复杂度
DP：$O(n^2)$
参考代码
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
| #define N 5005
ll n,p;
ll dp[N][N],powp[N];
void Init(ll n){
for(ll i=0;i<=n;i++)
for(ll j=0;j<=n;j++)
dp[i][j]=0;
powp[0]=1;
dp[0][0]=1;
for(ll i=1;i<=n;i++) powp[i]=mul(powp[i-1],p);
}
void solve()
{
cin >> n >> p;
Init(n);
for(ll i=1;i<=n;i++){
dp[i][0]=1;
for(ll k=1;k<=i;k++){
addto(dp[i][k],mul(dp[i-1][k],powp[k]));
addto(dp[i][k],mul(dp[i-1][k-1],sub(powp[n],powp[k-1])));
}
}
ll re=0,ninv=inv(qcpow(powp[n],n));
for(ll i=1;i<=n;i++) addto(re,mul(mul(i,dp[n][i]),ninv));
cout << re << endl;
}
|
1010.Rikka with Square Numbers
数学、贪心
题意
给定两个正整数 $a,b$ ，每次操作可以使 $a$ 增大或减小一个平方数 $x$ ，求把 $a$ 变成 $b$ 的最小操作次数
解题思路
即求 $a,b$ 之差最少可以用多少个平方数的和差表示。以下是一些思路：
- $a=b$ ， $0$
- $n^2$ ，平方数本身， $1$
- $n^2-(n-1)^2=2n-1$ ，用两个相邻平方数之差即可表示任意奇数
- $n^2-(n-2)^2=4(n-1)$ ，用两个距离为 $2$ 的平方数之差可以表示任意 $4$ 的倍数
- 结合以上两条可以归纳证明两个平方数之差一定为奇数或 $4$ 的倍数，$2$
- 模 $4$ 余 $2$ 的情况可能为两平方数加和，可以枚举判断， $2$
- 其余的数可以用第 $3$ 点得到任意奇数后加减 $1$ ， $3$
综上判定即可
时间复杂度
$O(\sqrt n)$
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| bool Is_Sqr(ll x){
ll t=sqrt(x);
if(t*t==x) return 1;
return 0;
}
void solve()
{
ll a,b;cin >> a >> b;
if(a<b) swap(a,b); ll dif=a-b;
if(a==b) {cout << 0 << endl;return ;}
if(Is_Sqr(dif)) {cout << 1 << endl;return ;}
if(dif%2||(dif%4==0)) {cout << 2 << endl;return ;}
for(ll i=1;i*i<=dif;i++) if(Is_Sqr(dif-i*i)) {cout << 2 << endl;return ;}
cout << 3 << endl;
}
|
