AB 两道题就不写题解了,直接从 C 题开始。
题目链接
https://atcoder.jp/contests/abc141
C. Attack Survival
大意
有 \(n\) 人参加一场比赛,每个人初始分数为 \(k\)。
有 \(q\) 个问题,每道题都只有一个人答对。当一个人答对一道题时,其他人都会扣除一分。求最后哪些人的分数为正数。
题解
逆向思考,给其他人扣一分相当于给这个人单独加一分。
问题就变成了判断每个人的加分是否大于 \(q-k\)。
#include <cstdio> int a[100005]; int main() { int n,k,q; scanf("%d%d%d",&n,&k,&q); for(int i=1;i<=q;i++) { int x; scanf("%d",&x); a[x]++; } for(int i=1;i<=n;i++) puts(k-q+a[i]>0?"Yes":"No"); return 0; }
D. Powerful Discount Tickets
大意
有 \(n\) 件商品,每个商品的原价是 \(a_i\)。
对于一个原价为 \(x\) 的商品,如果使用了 \(y\) 张优惠券,价格会变为 \(\left \lfloor \frac{X}{2^Y} \right \rfloor\)。
现在有 \(m\) 张优惠券,求买下所有商品的最小花费。
题解
一种比较显然的贪心解法是:每次用券都让优惠金额最大。
实现的时候可以把所有商品放入大根堆中,每次取出堆顶用一张优惠券,再将优惠后的商品插入堆中。
要证明这个贪心解法的正确性,我们需要证明一个定理:
$$\left \lfloor \frac {\left \lfloor \frac{x}{y} \right \rfloor}{z} \right \rfloor= \left \lfloor \frac{x}{yz} \right \rfloor$$
证明过程可以参考 ouuan 在 Codeforces 的非官方题解。
#include <iostream> #include <queue> #include <algorithm> using namespace std; priority_queue<int>q; long long ans; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { int x; cin>>x; ans+=x; q.push(x); } while(m--) { int x=q.top(); q.pop(); ans=ans-x+x/2; q.push(x/2); } cout<<ans<<endl; return 0; }
E. Who Says a Pun?
大意
给出字符串 \(S\),求出最长的子串,满足该字串在 \(S\) 中不重叠地出现了至少两次,输出其长度。
题解
Part 1 二分+哈希解法
注意到答案具有单调性,我们可以二分答案。
怎么检验答案 \(len\) 是否合法呢?我们从左到右枚举字符串,判断它与前面所有长度为 \(len\) 的串是否相同且不重叠。
判断字符串相同可以用字符串哈希。
时间复杂度:可以做到 \(O(n \log n)\)。然而下面的解法对于所有长度为 \(len\) 的字符串都重新算了一遍哈希值,事实上是 \(O(n^2 \log n)\) 的。
注:可能要用双哈希才能 AC。虽然这个做法能够通过本题,但个人认为并不十分清真,各位可以再看一下本题的其他两种解法。(其他两种做法的代码后面会补上)
#include <cstdio> #include <set> #define MOD 1000000007 #define MOD2 998244353 using namespace std; char s[5005]; int n; bool check(int len) { set<long long> se,se2; for(int i=1;i+len-1<=n;i++) { long long sum=0,sum2=0; if(i-len>0)//每次插入当前串前面的一个长度为 len 的串,确保不重叠 { for(int j=i-len;j<i;j++) sum=(sum*26+s[j]-'a')%MOD,sum2=(sum2*26+s[j]-'a')%MOD2; se.insert(sum),se2.insert(sum2); } sum=0,sum2=0; for(int j=i;j<=i+len-1;j++) sum=(sum*26+s[j]-'a')%MOD,sum2=(sum2*26+s[j]-'a')%MOD2; if(se.count(sum)&&se2.count(sum2))return true; } return false; } int main() { scanf("%d",&n); scanf("%s",s+1); int l=0,r=n/2; while(l<r) { int mid=(l+r+1)>>1; if(check(mid))l=mid; else r=mid-1; } printf("%d\n",l); return 0; }
Part 2 DP 解法
设 \(f_{i,j}\) 表示第一个串从 \(i\) 开始,第二个串从 \(j\) 开始时的最长合法长度。
则有:
$$f_{i,j}=\begin{cases} 0 & s[i] \ne s[j] \\ \min(j-i,f_{i+1,j+1}+1) & s[i]=s[j] \end{cases}$$
时间复杂度:\(O(n^2)\)
Part 3 后缀自动机解法
(ouuan 在他的非官方题解里提到了这个做法 Orz)
枚举断点 \(x\),将字符串分割为 \([1,x]\) 和 \([x+1,n]\) 两部分,则问题变成了求两个串的最长公共子串。
最终的答案则是所有合法断点答案的最大值。
然后就可以构造 SAM 做了。关于如何求两个字符串的最长公共子串,可以看 OI-wiki 中的介绍。
F. Xor Sum 3
大意
将若干个数分割成两个非空集合,使两个集合异或和加起来最大。
题解
我们统计每个二进制位上 \(1\) 的个数。
如果 \(1\) 的个数为奇数,则可以让一个集合的异或和在该位上为 \(1\),另一个集合在该位上的异或和为 \(0\)。(一个集合内 \(1\) 的个数为奇数,另外一个集合内为偶数)
否则两个集合异或和在该位上的值显然相同。
上面的推理说明了:我们只需让其中一个集合的异或和最大即可。
问题变成了求给定数组的最大异或和,线性基裸题。
(代码暂咕)
E题的dp那里应该是 dp[i][j]=min(dp[i+1][j+1]+1,j-i)…
谢谢提醒 QAQ