当前位置: 代码迷 >> 综合 >> AtCoder Grand Contest 020
  详细解决方案

AtCoder Grand Contest 020

热度:32   发布时间:2023-12-02 14:48:28.0

AtCoder Grand Contest 020

  • A - Move and Win
  • B - Ice Rink Game
  • C - Median Sum
  • D - Min Max Repetition

AGC难度上天,希望自己可以将题目陆陆续续的都给做出来。
这里的题目质量奇高,一定要好好刷起来,这是第二篇
只要是我做出来的题目,都会认真的写题解的~~

A - Move and Win

这题真是满满的童年啊,同年的龙虎斗什么的,双方都只剩一个棋子了,如果甲可以吃乙,如果最优的话,要是吃的到,要么吃不到。
当,两个相距一格的时候,现走的那人可以将另一个人的一个方向的路封死,一直追到最后,一定追到,那么奇数差也是如此,偶数差相反。

void work()
{
    int n, a, b; cin >> n >> a >> b;if (abs(a - b) % 2) cout << "Borys" << endl;else cout << "Alice" << endl;
}

B - Ice Rink Game

题意:给定一个长度为k的w数组,每个w大小为1e9,k大小为1e5 。初始时有n个人,到了i,会组成w[i]的倍数,多余的会去掉,k次后仅留下了2人。问最开始的时候,n的最小值和最大值。

解决:
解决这个题目,需要弄清楚两个信息,一是每一位的实际数值【从前一位的来的】,二是每一位的取整数值【从当前位想后转移的时候的值】。还有需要注意的是,我们的答案从后往前取,但是ans不会变小
我们后往前算,最小值很好考虑,就是我们的取整数值。每走到当前位的时候,保留取整后且要合法的值【如果正好整除,就取它,如果不能,需要上取整,因为下取整的话,就小于我们的ans,但是ans保留的是上一个的最小值,ans不会变小】,也就是(L/a[i])的上取整乘上a[i]。
最大值就是需要考虑实际值中的最大值,首先,在取整数值基础上加上当前w-1。结果就是R / ai * ai + ai - 1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
int n;
ll w[N];
ll a, b;
int main()
{
    cin >> n;for (int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);a = 2, b = 2;for (int i = n; i >= 1; i -- ){
    a = (a + w[i] - 1) / w[i] * w[i];b = (b / w[i] + 1) * w[i] - 1;cout << a << endl;// cout << b << endl;if (a > b){
    cout << -1 << endl;return 0;}}cout << a << " " << b << endl;
}

C - Median Sum

题目:
给定长度为n的a集合,其中n大小为2000,a大小也为2000,长度为n的集合可以组成2^n-1个非空子集。这些非空子集的和组成一个长度为2^n- 1的序列,请找到他的中位数。

解决:
上次也是,遇到将一个集合中取出一种合法方案,对应这剩下的哪些组成另外的非空集合。
我们同样考虑,我们从集合中抽出一部分数,组成一个集合,剩下的自然的会组成另外一个集合。那么,必出现一个子集的和小于等于sum/2,另一个集合的和一定是大于等于sum/2。而这样的集合个自会有2^(n-1)个,加上一个全集,就有2^n-1个子集了,那么我们的中位数因为加了一个全集,它一定是一个大于sum/2的数了。

做法:
bitset位运算来做。
初始化dp[0] = 1,然后遇到一个数a,就将dp左移a位,然后再异或起来,表示的意义为每个数都加上a,然后将新出现的数和原来的数都算上。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
int n;
int w[N];
ll s = 0;
bitset<N * N> dp;
int main()
{
    cin >> n;for (int i = 1; i <= n; i ++ ) cin >> w[i], s += w[i];dp[0] = 1;for (int i = 1; i <= n; i ++ )dp |= dp << w[i];s = (s + 1) >> 1;while (!dp[s]) s ++;cout << s << "\n";return 0;
}

D - Min Max Repetition

还是不太会,check函数没搞懂,留到以后再看吧

题目:让f(a,b)满足如下条件,其中a和b都是正整数
1.f(a,b)长度为a+b
2.f(a,b)恰好由a个A和b个B构成。
3.f(a,b)中长度最长的由相等字符组成的子串在满足上面情况下尽可能的小
4.f(a,b)是满足上面条件下的字典序最小的子串
有Q个询问,询问f(a,b)的从c到d的子串为什么

解决:
有条件3可知,在所有字符组合方案中,要让最长的由相同字符组成的子串的长度最小,那么这个答案就是(p+q)/(q+1)。【p整除q+1上取整】。设这个长度为L
下面就要考虑条件4了,要让我们的字典序最小,那么,我们要让A尽可能的在前面,让B尽可能的在后面。那么我们可以进行这样的构造。对于前缀,一定是A。…AB,其中A有L个,对于后缀,一定是AB…B,其中B有L个,那么我们需要考虑的就是在什么位置拼接。
当然,上面情况适用于a大于等于b的情况,对于a小于b的情况,我们可以按照a大于等于b来算,然后将所得字符串翻转,再将字符A换成B,将B换成A。
证明:在a大于等于b的情况下,所得的字符串s一定是合法情况下字典序最小的的情况,那么我们将字符串翻转,就得到了字符串字典序最大的情况。这时,我们将字符翻转,就得到了,a个B和b个A的字典序最小的情况。

#include <bits/stdc++.h>
using namespace std;
int a, b, c, d, k;
#if 0
inline bool check(int mid)
{
    int u1, v1, u2, v2;u1 = mid / (k + 1) * k + mid % (k + 1);v1 = (a + b - mid) / (k + 1);u2 = mid / (k + 1);v2 = (a + b - mid) / (k + 1) * k + (a + b - mid) % (k + 1);if (u1 + v1 <= a || u2 + v2 >= b) return 1;return 0;
}
#endif
#if 1
inline bool check(int o) {
    if (!o) return 1;if (!(o % (k + 1))) return check(o - 1);int x = a - (o - o / (k + 1)), y = b - o / (k + 1);return y <= 1ll * (x + 1) * k;
}
#endif
inline void work()
{
    cin >> a >> b >> c >> d;k = (max(a, b) - 1) / (min(a, b) + 1) + 1;int l = 0, r = a + b;while (l < r){
    int mid = (l + r + 1) >> 1;if (check(mid)) l = mid;else r = mid - 1;}for (int i = c; i <= min(l, d); i ++ )printf("%c", i % (k + 1) ? 'A' : 'B');for (int i = max(c, l + 1); i <= d; i ++ )printf("%c", (a + b - i + 1) % (k + 1) ? 'B' : 'A');cout << endl;
}
int main()
{
    int T; cin >> T;while (T -- ){
    work();}return 0;
}
  相关解决方案