比赛题单:2024“钉耙编程”中国大学生算法设计超级联赛(10)

(1008)HDU7548.SunBian

题意

有排成环形的 n 个横着的笋,Alice 和 Bob 轮流执行如下操作,Alice 先手:

  • 选择 [1,k] 个连续的横着的笋,把它们变成竖着的

不能操作者输。

给定 n,k ,求谁会赢。

解题思路

  • k=1 时,根据奇偶性判断赢家
  • kn 时,先手直接将笋全部竖置,必胜
  • 其余情况下,后手每次都可以尽可能保证剩余区域数为偶数,最终必胜

参考代码

cpp
1
2
3
4
5
6
7
void solve()
{
ll n,k;cin >> n >> k;
if(n<=k) cout << 'A';
else if(k==1) cout << (n%2?'A':'B');
else cout << 'B';
}

(1009)HDU7549.不基本子串结构

题意

给定2个字符串 a,b ,找到一个最小长度的字符串 c ,使得 abc 中出现的次数相等且不为0,输出最小长度。

解题思路

分类讨论,不妨假设 len(a)len(b)

  • ab 中出现的次数大于 1 ,则不存在满足条件的 c
  • ab 中出现的次数为 1 ,则 c=b ,输出 len(b)
  • ab 中没有出现:
    • l1 为 最大满足 a[0:l]=b[len(b)l:len(b)]l
    • l2 为 最大满足 a[len(a)l:len(a)]=b[0:l]l
    • 答案为 len(a)+len(b)max(l1,l2)

可以用字符串哈希进行检查和计数。

参考代码

cpp
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
void solve()
{
string s1,s2;
cin >> s1 >> s2;
if(s1.length()<s2.length()) swap(s1,s2);
strHash h1(s1),h2(s2);
ll n=s1.length(),m=s2.length();
ll cnt=h1.count(h2);
if(cnt>1){
cout << "-1" << endl;
return;
}
if(cnt==1){
cout << n << endl;
return;
}
ll ans=m+n;
FORLL_rev(len,m-1,1){
if(h1.findz(n-len+1,n)==h2.findz(1,len)){
chmin(ans,n+m-len);
break;
}
}
FORLL_rev(len,m-1,1){
if(h1.findf(1,len)==h2.findf(m-len+1,m)){
chmin(ans,n+m-len);
break;
}
}
cout << ans << endl;
}

(1011)HDU7551.NOI2024

题意

m 名选手进行 n 场比赛,排名定义为分数严格大于你的人数+1。
i 场比赛的分数上限为 bi ,你的排名为 ai
最终按照每场比赛的总分排名,前 k 名选手将获得金牌。
问在给定条件下不管怎么比赛,是否一定能获得金牌。

解题思路

用最坏情况考虑:你始终为 0 分,在你前面的选手都有分数。
最终最坏排名为 min(i=1nai,m)

参考代码

cpp
1
2
3
4
5
6
7
8
9
10
11
void solve()
{
ll n,m,k;cin >> n >> m >> k;
create_vec(a,n);
create_vec(b,n);
ll cnt=0;
FORLL(i,0,n-1) cnt+=max(0ll,a[i]-1);
chmin(cnt,m-1);
if(cnt>=k) cout << "NO" << endl;
else cout << "YES" << endl;
}