首页 > 其他分享 > Codeforces Round #822

Codeforces Round #822

时间：2022-09-25 15:02:03浏览次数：78  
标签：ch int Codeforces getchar 批脸 le include Round 822

目录

写在前面

比赛地址：https://codeforces.com/contest/1734。

复健后第一场 div2，感觉有 19 年水平了。

哈哈。

A

\(t\) 组数据，每组数据给定一长度为 \(n\) 的数列 \(a\)，给定一种操作，每次操作可以选定一个数，使该数加 \(1\) 或减 \(1\)。
要求进行多次操作后，数列中存在三个大小相等的数，求最小操作次数。
\(1\le t\le 100\)，\(3\le n\le 300\)，\(1\le a_i\le 10^9\)，\(\sum n \le 300\)
1S，256MB。

水。

排序后选三个最接近的数，求使它们相等的代价即可。

//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
const int kN = 300 + 10;
//=============================================================
int a[kN];
//=============================================================
inline int read() {
	int f = 1, w = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
	for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
	return f * w;
}
//=============================================================
int main() {
	int t = read();
  while (t --) {
    int n = read();
    long long ans = 1e10 + 10;;
    for (int i = 1; i <= n; ++ i) a[i] = read();
    std::sort(a + 1, a + n + 1);
    for (int i = 2; i + 1 <= n; ++ i) {
      long long sum = (a[i] - a[i - 1]) + (a[i + 1] - a[i]);
      if (ans > sum) ans = sum;
    }
    printf("%lld\n", ans);
  }
	return 0;
}

B

定义一种名为金字塔的建筑。对于有 \(n\) 层的金字塔，其第 \(i\) 层有 \(i\) 个房间，分别记为 \((i,1)\sim (i,i)\)。房间 \((i, i)\) 内有两条楼梯，可以单向地到达房间 \((i + 1, i)\) 与 \((i + 1, i + 1)\)。现在可以在房间中插一个火把，火把发出的光可以沿着楼梯一直延伸到金字塔的第 \(n\) 层，覆盖所有可到达的房间。
定义一个房间的亮度为能照到该房间的所有火把的数量。定义一个金字塔是好的，当且仅当金字塔同一层的所有房间亮度相同。对于一个好的金字塔，定义它的辉度为房间 \((1,1)\sim (n,1)\) 的亮度之和。
\(t\) 组数据，每组数据给定整数 \(n\)，要求构造一种插火把的方案，最大化 \(n\) 层的金字塔的辉度。
\(1\le t\le 100\)，\(1\le n\le 500\)，\(\sum n\le 500\)。
1S，256MB。

构造。

易知房间 \((i,1)\) 的亮度最大为 \(i\)，当且进当房间 \((1,1)\sim (i,1)\) 插满火把时取到。
考虑上述条件下如何使金字塔成为好的。则需使第 \(i\) 层的房间亮度全部为 \(i\)。从左向右手玩可以照到第 \(i\) 层的每个房间的火把的位置，发现you房间 \((i, j)\) 变为 \((i, j+1)\) 时，房间 \((i - j + 1, 1)\) 失去贡献，而房间 \((j, j)\) 变得可以有贡献。
则仅需使房间 \((1,1)\sim (n,1)\)，\((1,1)\sim (n,n)\) 插满火把即可。

//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
//=============================================================
//=============================================================
inline int read() {
	int f = 1, w = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
	for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
	return f * w;
}
//=============================================================
int main() {
	int t = read();
  while (t --) {
    int n = read();
    for (int i = 1; i <= n; ++ i) {
      if (i == 1) printf("1\n");
      if (i > 1) {
        printf("1 ");
        for (int j = 2; j < i; ++ j) printf("0 ");
        printf("1\n");
      }
    }
  }
	return 0;
}

C

\(t\) 组数据，每组数据给定整数 \(n\)，表示有一个数集 \(S\)，\(S=\{x|1\le x\le n, x\in \N\}\)。给定一个数集 \(T\)，且有 \(T\subseteq S\)。给定一种操作，每次操作可以选择任意整数 \(k\)，满足 \(1\le k\le n\)，将 \(S\) 中现存的 \(k\) 的最小倍数删去，代价为 \(k\)。
求进行任意次操作后，将 \(S\) 变为 \(k\) 的最小代价。
\(1\le t\le 10^4\)，\(1\le n\le 10^6\)，\(\sum n\le 10^6\)。
2S，256MB。

枚举，贪心。

显然，对于每一个数，要尽可能用较小的数将其删去，于是考虑正序枚举 \(1\sim n\) 进行操作，并尽量多次使用较小的数作为 \(k\) 进行操作，枚举的 \(k\) 的倍数大于 \(n\)，或\(S\) 中存在的 \(k\) 的最小倍数不应被删去时增大 \(k\) 即可。

极限复杂度为调和级数 \(n\sum\limits_{i = 1}^{n} \left( \dfrac{1}{i} \right) = n\log n\)。

//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
const int kN = 1e6 + 10;
//=============================================================
char a[kN];
long long ans;
//=============================================================
inline int read() {
	int f = 1, w = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
	for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
	return f * w;
}
//=============================================================
int main() {
	int t = read();
  while (t --) {
    int n = read();
    ans = 0;
    scanf("%s", a + 1);

    for (int i = 1; i <= n; ++ i) {
      for (int j = i; j <= n; j += i) {
        if (a[j] == '1') break;
        if (a[j] == '0') {
          ans += 1ll * i;
          a[j] = '2';
        }
      }
    }
    printf("%lld\n", ans);
  }
	return 0;
}

D

\(t\) 组数据，每组数据给定整数 \(n,k\)，给定一长度为 \(n\) 的数列。定义一种叫做批脸开润的游戏。游戏中有 \(n\) 个批脸从左到右排成一列，第 \(i\) 个批脸血量为 \(a_i\)，批脸的血量可能为负数。玩家可以操作第 \(k\) 个批脸，每次操作可以向左或向右移动一个位置。如果该位置上有一个批脸，则玩家的批脸将会吃掉该批脸，血量加上该批脸的血量，吃完后该批脸会被清除。
在位置 \(0\) 和 \(n+1\) 各有一个出口，当玩家清除沿途的所有批脸后即可到达出口并开润。试确定玩家能否在保证自己的批脸血量时刻不低于 \(0\) 的要求下，找到一种操作方案开润。
\(1\le t\le 2\times 10^4\)，\(3\le n\le 2\times 10^5\)，\(1\le k\le n\)，\(-10^9\le a_i\le 10^9\)，\(a_k\ge 0\)。对于 \(i\not = k\)，\(a_i\not= 0\)。
2S，256MB。

贪心，预处理，模拟。

一些显然的结论：

  1. 血量非负的批脸能吃就吃，连续的非负批脸同吃最好。
  2. 连续的血量为负的批脸连续吃掉和分开吃掉等价，可看做一个血量为它们血量之和的批脸。
  3. 如果吃了血量为负的批脸的目的，要么是之后能吃到血量为正的批脸，使得最终的血量不下降，要么是吃完之后可以开润。

综合上述结论（主要是结论 3），可以将连续的一些批脸进行合并。从位置 \(k\) 向左、向右分别开始，将最短的、血量和为非负的一段批脸合并。
以向左合并为例，记吃掉一段批脸 \((l,r)\) 的代价为它们的血量和，吃掉这段批脸的必要条件是吃的时候玩家血量不会变为负数，即有：

\[\operatorname{player's\ heal} +\min_{i=l}^{r}\left\{ \sum\limits_{j=i}^{r} a_i\right\} \ge 0 \]

向右合并时同理，必要条件变为：

\[\operatorname{player's\ heal} +\min_{i=l}^{r}\left\{ \sum\limits_{j=l}^{i} a_i\right\} \ge 0 \]

需要特判段的端点为 \(0\) 和 \(n\) 的情况。

可以发现，这样合并后，每一段批脸对玩家血量都会有贡献。记录合并后每段的代价和必要条件中涉及的最小的前缀/后缀和，之后模拟操作的过程，能吃就吃即可。

若存在某个时刻向左、向右都无法操作，则不存在合法的方案，否则存在。

合并过程中每个批脸只会被计入到一段中，模拟操作时每段也只会被吃一次，则总体复杂度为 \(O(n)\) 级别。

//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#define pair std::pair
#define mp std::make_pair
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, k, a[kN];
LL sum[kN];
std::vector <pair<LL,LL>> L, R;
//=============================================================
inline int read() {
	int f = 1, w = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
	for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
	return f * w;
}
void Split() {
  L.clear(), R.clear();
  for (int i = k - 1, r = k; i >= 0; -- i) {
    if (sum[i] - sum[r] >= 0 || i == 0) {
      LL sum1 = 0, need = 1e12;
      for (int j = r - 1; j >= i; -- j) {
        sum1 += a[j];
        need = std::min(need, sum1);
      }
      L.push_back(mp(sum1, need));
      r = i;
    }
  }

  for (int i = k + 1, l = k; i <= n + 1; ++ i) {
    if (sum[i] - sum[l] >= 0 || i > n) {
      LL sum1 = 0, need = 1e12;
      for (int j = l + 1; j <= i; ++ j) {
        sum1 += a[j];
        need = std::min(need, sum1);
      }
      R.push_back(mp(sum1, need));
      l = i;
    }
  }
  std::reverse(L.begin(), L.end());
  std::reverse(R.begin(), R.end());
}
void Solve() {
  LL now_hel = a[k];
  for (int i = 1; ; ++ i) {
    bool flag = true;
    if (now_hel + L.back().second >= 0) {
      now_hel += L.back().first;
      L.pop_back();
      flag = false;
    }
    if (flag && now_hel + R.back().second >= 0) {
      now_hel += R.back().first;
      R.pop_back();
      flag = false;
    }
    if (flag) {
      printf("NO\n");
      return ;
    }
    if (L.empty() || R.empty()) {
      printf("YES\n");
      return ;
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
	int t = read();
  while (t --) {
    n = read(), k = read();
    a[0] = a[n + 1] = 0;
    for (int i = 1; i <= n; ++ i) {
      a[i] = read();
      sum[i] = 0;
    }
    for (int i = k - 1; i >= 0; -- i) sum[i] = sum[i + 1] + a[i];
    for (int i = k + 1; i <= n + 1; ++ i) sum[i] = sum[i - 1] + a[i];
    Split();
    Solve();
  }
	return 0;
}

E

给定质数 \(n\)，给定一长度为 \(n\) 的数列 \(b_i\)，要求构造一个 \(n\times n\) 的矩阵 \(a\)，满足：

  • \(0\le a_{i,j}<n(1\le i,j\le n)\)。
  • \(a_{r_1,c_1}+a_{r_2,c_2}\not\equiv a_{r_1,c_2}+a_{r_2,c_1} \pmod{n}, 1\le r_1<r_2\le n, 1\le c_1<c_2\le n\)，即所有子矩阵角上四个数对角线之和对 \(n\) 不同余。
  • \(a_{i,i}=b_i\)。

\(2\le n<350\)，保证 \(n\) 为质数，\(0\le b_i<n\)。
1S，256MB。

构造。

首先有一个不太显然的性质，对一个满足条件1、2 的矩阵任意一行或任意一列，同加减同一个值并求余后，矩阵仍满足条件 1、2。代入条件 2 的式子即可显然证明。则可考虑构造一个与数列 \(b\) 无关的满足条件 1、2 的矩阵，再将其调整为合法矩阵。

以下是几种可行的构造方案：

\[\begin{align} a_{i,j} &\equiv i \times j &\pmod{n}\\ a_{i,j} &\equiv (i + j)^2 &\pmod{n}\\ a_{i,j} &\equiv \dfrac{(i + j)(i + j + 1)}{2} &\pmod n \end{align}\]

特别地，方案 2 要特判 \(n = 2\) 的情况。

可以证明，对于任意 \(a_{i,j} = A\times i^2 + B\times i\times j+C\times j^2 + D\times i+E\times j + f\)，当系数均为整数，且 \(B\not\equiv 0\pmod n\) 时均满足要求。

证明作差即可，易得：

\[(a_{r_1,c_1}+a_{r_2,c_2})- (a_{r_1,c_2}+a_{r_2,c_1}) = B(r_1-r_2)(c_1-c_2) + ...\pmod{n} \]

有 \(r_1\not= r_2\)，\(c_1\not= c_2\)，\(n\) 为质数，则当 \(B\not\equiv 0\pmod n\) 时，\(B(r_1-r_2)(c_1-c_2)\not\equiv 0\pmod n\)。又 \(...\) 中的项 \(i^2,j^2,i,j,1\) 在某行或某列上都是恒定的值，利用性质可以将它们在整行或整列上的影响消去，则仅需满足 \(B\not\equiv 0\pmod n\) 即可。

也因此方案 2 需要在 \(n = 2\) 时特判。

//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
const int kN = 350 + 10;
//=============================================================
int n, a[kN], ans[kN][kN];
//=============================================================
inline int read() {
	int f = 1, w = 0; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
	for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
	return f * w;
}
//=============================================================
int main() {
	n = read();
  for (int i = 1; i <= n; ++ i) a[i] = read();
  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= n; ++ j) {
      ans[i][j] = (i * j) % n;
    }
  }
  for (int i = 1; i <= n; ++ i) {
    int d = (a[i] - ans[i][i]);
    for (int j = 1; j <= n; ++ j) {
      ans[i][j] = (ans[i][j] + d + n) % n;
    }
  }
  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= n; ++ j) {
      printf("%d ", ans[i][j]);
    }
    printf("\n");
  }
	return 0;
}

F

以下是 Thue-Morse 序列的一种定义和构造方法：

  • Thue-Morse 序列 是一个无限不循环的 01 序列。
  • 构造 Thue-Morse 序列时从一个 0 开始，每次将已有的序列翻转并拼接到原序列之后，如：0 \(\rightarrow\) 01 \(\rightarrow\) 0110 \(\rightarrow\) 01101001 \(\rightarrow\) 0110100110010110 \(\rightarrow\) ……

给定 \(t\) 组数据，每组数据给定整数 \(n,m\)。将 Thue-Morse 序列的 \(0\sim m-1\) 位与 \(n\sim n+m-1\) 位分别取出，构成两个字符串，问这两个字符串对应位置有多少位不同。
\(1\le t\le 100\) \(1\le n,m\le 10^{18}\)。
3S，256MB。

结论，数位 DP。

一个结论：Thue-Morse 序列的第 \(i\) 位为 1，当且仅当 \(i\) 的二进制分解下，有奇数个位置为 \(1\)。证明不会。

然后是数位 DP，数位 DP 不会。

哈哈，摸了。

写在最后

  • 能枚举就枚举。
  • 考虑被研究的元素左移/右移一个单位时，能影响该元素的因素的变化。
  • 一眼贪心，找完结论用不用看题。
  • 构造时考虑由合法结构向外拓展至更一般性的合法结构。

标签：ch,int,Codeforces,getchar,批脸,le,include,Round,822
From： https://www.cnblogs.com/luckyblock/p/16727861.html

相关文章

  • Codeforces Round #822 (Div. 2)
    比赛链接CodeforcesRound#822(Div.2)D.SlimeEscape给一个长度为\(n\)的序列以及一个\(k\)，表示当前位于\(k\)这个位置，要求该位置的数往左或者右，每次只能加上......
  • Codeforces Round #822 (Div. 2) D
    https://codeforces.com/contest/1734/problem/D题意有n只史莱姆，每只都有一个值，其中第k只被你控制，你希望能走到0或n+1这两个位置，也就是说遇到路上的史莱姆需要......
  • CodeForces 比赛记录
    带星号的表示vp。\(*\)CFRound601Div.1做出A和B1。B2.SendBoxestoAlice(HardVersion)考虑\(a\)的前缀和数列\(S\)，在\(a\)中移动一个数，相当于在\(S......
  • Codeforces Round #822 D,E
    E.RectangularCongruence我们考虑对ar1,c1+ar2,c2≢ar1,c2+ar2,c1(modn)(同余情况下不同也是可以同时加任意数的可以感性理解一下）ar1,c1-ar1,c2≢ar2,c1......
  • CF Round 822 Div2 题解
    比赛链接A题SelectThreeSticks（签到）给定\(n\)根木棒，第\(i\)根木棒的长度为\(a_i\)。现在我们可以进行操作，每次操作选定一根木棒，将其长度增高或减少1。问至少需......
  • Codeforces Round #822 Div.2 整场题解
    目前还有E,F没有更新。A.SelectThreeSticks直接对\(a\)排序，选出来的木棍一定是相邻三项，都往中间靠更优。B.Bright,Nice,Brilliant最优方案就是每一行第一个......
  • python中round函数的一个小坑——奇进偶弃
    python中round函数的一个小坑——奇进偶弃 >>>round(3.1415,3)3.142>>>round(4.1415,3)4.141 >>>round(10.5)10>>>round(11.5)12 ......
  • Codeforces Round #640 (Div. 4) D. Alice, Bob and Candies
    CodeforcesRound#640(Div.4)翻译岛田小雅D.Alice,BobandCandies出题人MikeMirzayanov\(n\)个糖果排成一排，从左到右分别被编号为\(1\)到\(n\)。第\(i\)......
  • Roadside Trees (Simplified Edition) CodeForces - 265B
    RoadsideTrees(SimplifiedEdition)CodeForces-265B松鼠Liss喜欢坚果。一条街上有n棵树（从西到东编号为1到n），每棵树的顶部都有一颗美味的坚果。树的高度我很高。......
  • Nikita and string CodeForces - 877B
    NikitaandstringCodeForces-877B有一个全由a和b组成的字符串，可以切成三部分。满足如下规则：第一部分只包含a或者是空串。第二部分只包含b或者是空串。第三部分只......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99