Atcoder Beginner Contest 141

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$ 的个数为奇数，另外一个集合内为偶数）

否则两个集合异或和在该位上的值显然相同。

上面的推理说明了：我们只需让其中一个集合的异或和最大即可。

问题变成了求给定数组的最大异或和，线性基裸题。

（代码暂咕）