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\) 的个数为奇数,另外一个集合内为偶数)

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

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

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

(代码暂咕)

《Atcoder Beginner Contest 141》上有2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注