KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200）_a - centur atcoder

导读：
简单的题目，只说明题意，或者直接说明结论
下面的难题，会做详细的解释和证明

A - Century

按照题意模拟

void work()
{
  int n;
  cin >> n;
  cout << (n + 99) / 100 << endl;
}
1
2
3
4
5
6

B - 200th ABC-200

按照题意模拟

void work()
{
  LL n, k; cin >> n >> k;
  while (k -- )
  {
    if (n % 200 == 0) n /= 200;
    else n = n * 1000 + 200;
  }
  cout << n << endl;
}
1
2
3
4
5
6
7
8
9
10

C - Ringo’s Favorite Numbers 2

给一个长度为n的数组，询问有多少个数对满足ai - aj == 200的倍数
我们可以先排个序，然后，记录模200的的值出现的次数，累加起来即可。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i ++ )
#define ll long long
const int N = 200010;
int n;
map<int, int> mp, mmp;
int a[N];
int main(void)
{
  cin >> n;
  rep(i, n) scanf("%d", &a[i]);
  sort(a, a + n);
  ll ans = 0;
  rep(i, n)
  {
    // int t = mp[a[i] % 200] - mmp[a[i]];
    int t = mp[a[i] % 200];
    ans += t;
    // printf("t = %d, a[i] = %d, mp = %d, mmp = %d\n", t, a[i], mp[a[i] % 200], mmp[a[i]]);
    mp[a[i] % 200] ++;
    // mmp[a[i]] ++;
  }
  cout << ans << endl;
  return 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

D - Happy Birthday! 2

题意：给定一个长度为n的数组，对应可以组成2 ^ n - 1个集合，问这里面是否存在两个集合的元素的和可以让他们对200取模的集合相等

做法：这里的n只有200大，而且我们的集合是对200取的模，那么，取模后的结果最多也只有200个，显然，当n大于等于8的时候，一定可以合法，毕竟2 ^ 8 = 256，由鸽巢原理，（有n+1个鸽子，n个笼子，现在将所有鸽子放到笼子里，一定存在一个笼子至少有两只鸽子），我们可以很显然的理解结论为何成立。
那么，我们就可以对n取值为min(n, 8)。然后，我们可以通过二进制来枚举一下集合的选取发方案，1代表选0代表必选，下面是代码。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i ++ )
const int N = 210;
int n;
int a[N];
pair<int, int> s[N];
int main()
{
  cin >> n;
  rep(i, n) scanf("%d", &a[i]), a[i] %= 200;
  n = min(n, 8);
  rep(i, 1 << n)
  {
    int sum = 0, cnt = 0;
    rep(j, n)
    {
      if (i >> j & 1) sum += a[j], cnt ++;
    }
    sum %= 200;
    if (s[sum].first)
    {
      cout << "Yes" << "\n";
      cout << s[sum].first << " ";
      rep(j, n)
        if (s[sum].second >> j & 1) cout << j + 1<< " ";
      cout << endl;
      cout << cnt << " ";
      rep(j, n)
        if (i >> j & 1) cout << j + 1 << " ";
      cout << endl;
      return 0;
    }
    s[sum] = {cnt, i};
  }
  cout << "No" << "\n";
  return 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
32
33
34
35
36
37
38
39

E - Patisserie ABC 2

题意：一个三元组，（beauty，taste，popular），每个元素大小都在1到n之间，这样我们可以得到3^n个元组，现在按照总和为第一关键字，beauty为第二关键字，taste为第三关键字，按照从小到大的顺序排序，问你第k个元组是多少？

分析：
首先，令x为beauty，taste和popular的和，并且x是从3到3 * n中间的一个数字。我们现在来看一下当x = k的时候，有什么性质。
x反应了我们从{1,2, …, n}集合中抽了三次且所得的和为k
用dp来求解，dp[i][j]的集合意义为已经选择了i个数（i从0到3），选择的这i个数字的和为j，满足这种选择的方案数为多少。
我们可以看到，dp[i][j]是dp[i+1][j+1], dp[i+1][j+2], dp[i+1][j+3], ... , dp[i+1][j+n]的一部分。拿dp[1][j}和dp[2][j + 5]来说，就是只选了一个数，当前总和为j（选的只是j），是选了2个数，且总和是j + 5(也就是第二次选择是5）的一种方案数。
当我们求完dp后，我们可以用我们题目中的k（第k个数）不断的减去dp[3][j]，直到我们找到位于第k个数范围的x，然后，枚举beauty，然后可以求taste和popular了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3000005;
int main()
{
  int n;
  ll k;
  ll dp[4][N] = {0};
  cin >> n >> k;
  dp[0][0] = 1;
  for (int i = 0; i < 3; i ++ ) 
  {
    for (int j = 0; j <= i * n; j ++ ) 
    {
      //只在1~n之间加上
      dp[i + 1][j + 1] += dp[i][j];
      dp[i + 1][j + n + 1] -= dp[i][j];      
    }
    for (int j = 1; j <= (i + 1) * n; j ++ )
      dp[i + 1][j] += dp[i + 1][j - 1];
  }
  int x;
  for (int i = 3; i <= 3 * n; i ++ )
    if (k <= dp[3][i]) {x = i; break;}
    else k -= dp[3][i];
  for (int i = 1; i <= n; i ++ )
  {
    //现在i是确定的，那么j和k就只会在l到r这个区间变换
    //而且，变化的个数也就是r-1+1个
    int l = max(1, x - n - i);
    int r = min(n, x - i - 1);
    if (l > r) continue;
    if (k > r - l + 1) {k -= r - l + 1; continue;}
    int y = l + k - 1;
    int z = x - i - y;
    cout << i << " " << y << " " << z << endl; 
    return 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
32
33
34
35
36
37
38
39
40