题解|2023暑期牛客多校04
|字数总计:2616|阅读时长:11分钟|阅读量:
A.Bobo String Construction
构造
题意
给定一个标识01串 $t$ ，构造一个长度为 $n$ 的信息01串 $s$ ，使得串 $m=t+s+t$ 中，串$t$ 仅在开头和结尾各出现过一次。（其中 $+$ 表示字符串连接运算）
解题思路
考虑构造 $s$ 全为 $0$ 或 $1$
对于特殊情况， $t$ 全为 $0$ 或 $1$ ，则使 $s$ 全为 $1$ 或 $0$ 即可
如果 $t$ 中兼有 $0$ 和 $1$ ，则 显然 $s$ 中不可能有子串 $t$
但对于 $m=t+s+t$ ，可能有 $t的后缀+s+t的前缀=t$ 的情况出现，导致不满足题设条件//
那么下面感性证明一下两种方案至少有一种成立。
假设对于兼有 $0$ 和 $1$ 的 $t$ ，在 $s$ 全为 $0$ 的情况下出现：
$t的后缀+s+t的前缀=t$
那么构造 $s$ 全为 $1$ 即可，反之亦然
于是问题就转化为在 $s$ 全为 $1$ 或 $0$ 的方案中选择一种使得串$t$ 仅在开头和结尾各出现过一次
先使 $s$ 全为 $1$ 将 $m=t+s+t$ 去掉首尾一个字符，判断中间有无字串 $t$ 即可
归纳发现特殊情况也可以用这种方法构造
时间复杂度
数据范围小（ $n\le 1000,|t|\le 1000$ ），BF即可
参考程序
1
2
3
4
5
6
7
8
9
10
| void solve()
{
string t;ll n;
cin >> n >> t;
string s;FORLL(i,1,n) s.push_back('1');
string m=t+s+t;m.erase(m.begin());m.pop_back();
if(m.find(t)!=string::npos) FORLL(i,1,n) cout << '0';
else FORLL(i,1,n) cout << '1';
cout << endl;
}
|
F.Election of the King
签到、模拟
题意
$n$ 个人竞选国王，每个人的从政理念用 $a_i$ 量化表示
每人每轮可以进行投票，对于个人而言，他会将票投给和他自己的政治理念相差最大的人
票数最多的人将被淘汰。如果票数相同，则淘汰值最大的；如果最大值有多个，则淘汰序号最大的人。
重复直到剩余一人成为国王，问最后谁会竞选上国王
解题思路
对于其中某一个人，和他相差最大的，一定是最大值与最小值之一
那么每次一定淘汰最大值或最小值
因此对所有人进行排序，每轮投票处于中间位置的人代表着多数人的意志
因此每轮看中间的人投最大值还是最小值，踢到只剩一人即可
参考程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void solve()
{
ll n,t;
cin >> n;
deque<pll> v;
FORLL(i,1,n){
cin >> t;
v.emplace_back(t,i);
}SORT(v);
float mid;
while(n>1){
mid=1.*(v.front().first+v.back().first)/2;
if(v[(n+1)/2-1].first<=mid) v.pop_back();
else v.pop_front();
n--;
}cout << v.front().second << endl;
}
|
H.Merge the squares!
几何、分治
题意
给定一个 $n\times n$ 的矩阵，它由 $n\times n$ 个小正方形组成
每次操作可以选择 $2\le x\le50$ 个正方形并把它们组合成一个更大的正方形（组合后的形状也必须为正方形）
求合并到整个边长为 $n$ 大小的正方形的操作过程
解题思路
这道题可以采用分治的思想
对于边长不大于 $7$ 的正方形，它的面积不大于 $49$ ，可以直接合并
对于边长较大的正方形，可以考虑将其分解为更小的正方形，递归处理
接下来考虑一种通用可行的分解方法如下图
这种分法将大正方形分解成两个小正方形和两个矩形
假设小正方形在递归处理中合并完成，占用块数为 $2$ ，那么每个长方形部分允许占用的块数为 $(50-2)/2=24$ 块
对于每个长方形，按照宽分割成一个正方形和一个矩形，对两部分分别递归处理
代码中预处理了一个切割方案，用于决定在大正方形边长为 $i$ 的情况下，满足矩形 $(i-j)\times j$ 即长方形的部分，占用分割块数不超过 $24$ 时，左上角的正方形边长，以此保证每次递归处理大正方形都满足条件
参考代码
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
| ll len[1005]={0};
void pre_len(ll n){
FORLL(i,2,n)
FORLL(j,1,i-1){
ll cnt=0;
ll a=j,b=i-j;
while(b){
cnt+=a/b;
a%=b;
swap(a,b);
}
if(cnt <= 24){
len[i]=j;
break;
}
}
}
struct node_op{
ll x,y,n;
}top;
vector<node_op> op;
void dfs(ll x1,ll y1,ll x2,ll y2)
{
ll difx=x2-x1+1,dify=y2-y1+1;
if(difx==1||dify==1) return;
if(difx>dify){
dfs(x1,y1,x1+dify-1,y2);
dfs(x1+dify,y1,x2,y2);
}else if(difx<dify){
dfs(x1,y1,x2,y1+difx-1);
dfs(x1,y1+difx,x2,y2);
}else{
if(difx==1) return;
if(difx>7){
dfs(x1,y1,x1+len[dify]-1,y1+len[difx]-1);
dfs(x1+len[dify],y1+len[difx],x2,y2);
dfs(x1+len[dify],y1,x2,y1+len[difx]-1);
dfs(x1,y1+len[difx],x1+len[dify]-1,y2);
}
top.x=x1;top.y=y1;top.n=difx;
op.emplace_back(top);
}
}
void solve()
{
op.clear();
ll n;
cin >> n;
if(n==1) {cout << "0" << endl;return;}
pre_len(n);
dfs(1,1,n,n);
cout << op.size() << endl;
for(auto i:op){
cout << i.x << ' ' << i.y << ' ' << i.n << endl;
}
}
|
J.Qu’est-ce Que C’est?
动态规划
题意
给定两个正整数 $n,m$ ，要求构造长度为 $n$ 的整数序列 $a$ ，满足：
- $\forall i\in [1,n],-m\le a_i\le m$
- 任意长度大于 $1$ 的连续子段之和不小于 $0$
求满足以上条件的整数序列的个数，结果取模
解题思路
计数取模，比起DP我会首先考虑猜通项
赛时根据样例1：$n=3,m=3\Rightarrow130$ 以及手算的 $n=2,m=3\Rightarrow28$ ，结合题目特征，拟出了一个满足上面两个情况的很奇怪的式子//然后样例2过不了，开摆
DP的思想是先计算出第 $i$ 个位置前已经满足题设条件，且最小后缀和为 $j$ 的方案数量（ $j$ 可以是负数，因为最后一个数可以单独为负数）
考虑如何进行状态转移
对每个位置从大到小遍历当前位置填数后的最小后缀和 $j$ ，记当前遍历到 $i$ ，填入的数为 $x$
- 对于非负整数 $j$ ，填入 $x$ 时的方案数为 $dp_{i-1,j-x}$
其中 $j-x\in[-m,m],x\in[-m,m],j\ge 0 \Rightarrow x\in [j-m,m]$，此时 $dp_{i,j}=\sum\limits_{x=j-m}^m dp_{i-1,x}$
- 对于负整数 $j$ ，此时 $x=j$ ，其方案数为允许 $x$ 填入的所有方案数之和，即 $dp_{i,j}=\sum\limits_{x=-j}^m dp_{i-1,x}$
由于每次计算都用到了前一个位置的以 $m$ 为上界的区间和，因此可以对每个位置的dp数组从 $m$ 到 $-m$ 维护一个前缀和，以降低时间复杂度
复杂度
时间复杂度： $O(n^2)$
空间复杂度： $M(Cn^2)$ ， $C$ 是常数，开LL可能会导致MLE
7/30：开L都MLE了//进行了空间优化，只保留 $dpsum$ 数组
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #define O 5000
long dp[5005][10005]={0};
long dpsum[5005][10005]={0};
void solve()
{
ll m,n;
cin >> n >> m;
for(ll j=m;j>=-m;j--) {dp[1][j+O]=1;dpsum[1][j+O]=dpsum[1][j+1+O]+dp[1][j+O];}
FORLL(i,2,n){
for(ll j=m;j>=-m;j--){
if(j>=0) dp[i][j+O]=dpsum[i-1][j-m+O];
else dp[i][j+O]=dpsum[i-1][-j+O];
dpsum[i][j+O]=Get_Mod(dpsum[i][j+1+O]+dp[i][j+O]);
}
}cout << dpsum[n][-m+O] << endl;
}
|
7/30：空间优化后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #define O 5000
long dpsum[5001][10001]={0};
void solve()
{
ll m,n;
cin >> n >> m;
for(ll j=m;j>=-m;j--){
dpsum[1][j+O]=dpsum[1][j+1+O]+1;
}
FORLL(i,2,n){
for(ll j=m;j>=-m;j--){
if(j>=0) dpsum[i][j+O]=Get_Mod(dpsum[i][j+1+O]+dpsum[i-1][j-m+O]);
else dpsum[i][j+O]=Get_Mod(dpsum[i][j+1+O]+dpsum[i-1][-j+O]);
}
}cout << dpsum[n][-m+O] << endl;
}
|
L.We are the Lights
思维题
题意
有 $n\times m$ 的电灯矩阵，初始全为关闭状态
每次操作会打开或关闭某一行/列的所有灯
问在给定的 $q$ 次操作后，共有多少盏灯亮着
解题思路
这道题和某刷墙小游戏类似（）玩过的话应该不难想到做法
后面的行动会覆盖前面的行动，用数组记录当前行/列是否已被覆盖
从后往前遍历操作即可
参考代码
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
| bool rc[N]={0},op[N]={0},rowvd[N]={0},colvd[N]={0};
ll x[N]={0},cnt=0,cntr=0,cntc=0;
void solve()
{
ll n,m,q;
cin >> n >> m >> q;
string trc,top;ll t;
FORLL(i,1,q){
cin >> trc >> t >> top;
if(trc=="row") rc[i]=1;else rc[i]=0;
if(top=="on") op[i]=1;else op[i]=0;
x[i]=t;
}
for(ll i=q;i>0;i--){
if(rc[i]){
if(rowvd[x[i]]==0){
rowvd[x[i]]=1;cntr++;
if(op[i]==1) cnt+=m-cntc;
}
}else{
if(colvd[x[i]]==0){
colvd[x[i]]=1;cntc++;
if(op[i]==1) cnt+=n-cntr;
}
}
}cout << cnt << endl;
}
|
