比赛题单:2024“钉耙编程”中国大学生算法设计超级联赛(10)
(1008)HDU7548.SunBian
题意
有排成环形的 个横着的笋,Alice 和 Bob 轮流执行如下操作,Alice 先手:
- 选择 [1,k] 个连续的横着的笋,把它们变成竖着的
不能操作者输。
给定 ,求谁会赢。
解题思路
- 当 时,根据奇偶性判断赢家
- 当 时,先手直接将笋全部竖置,必胜
- 其余情况下,后手每次都可以尽可能保证剩余区域数为偶数,最终必胜
参考代码
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个字符串 ,找到一个最小长度的字符串 ,使得 和 在 中出现的次数相等且不为0,输出最小长度。
解题思路
分类讨论,不妨假设
- 若 在 中出现的次数大于 ,则不存在满足条件的
- 若 在 中出现的次数为 ,则 ,输出
- 若 在 中没有出现:
- 记 为 最大满足 的
- 记 为 最大满足 的
- 答案为
可以用字符串哈希进行检查和计数。
参考代码
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
题意
名选手进行 场比赛,排名定义为分数严格大于你的人数+1。
第 场比赛的分数上限为 ,你的排名为 。
最终按照每场比赛的总分排名,前 名选手将获得金牌。
问在给定条件下不管怎么比赛,是否一定能获得金牌。
解题思路
用最坏情况考虑:你始终为 分,在你前面的选手都有分数。
最终最坏排名为 。
参考代码
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; }
|