首页 > 其他分享 >Codeforces Round 897 (Div. 2) 考试总结

Codeforces Round 897 (Div. 2) 考试总结

时间：2023-09-14 15:48:59浏览次数：43  
标签：lfloor ch 897 int dfrac Codeforces read Div define

前言

这次打得很好，相较于 div3 的脑残题和签到题来说，div2 的思维难度更加的大。同时还有除传统题外，其他的题型出现。比如交互题等。这次能在考场上想出三道较于之前是有很大的进步的。

赛时实况：

A B C D E1 E2 F
√ √ √ × × × ×

赛后改题情况：

A B C D E1 E2 F
√ √ √ × √ √ ×

感觉 D、F 不是很会。

A. green_gold_dog, array and permutation

Problem

给定一个长度为 \(n\) 的数列 \(a\)，现在需要找到一个排列 \(b\)，使得 \(a_i - b_i\) 互不相同。若有多种答案，输出其中一种即可。

Solve

首先，\(b\) 数组是一个排列，考虑排列的性质：没有重复元素，每个数只出现一次，所有数的值小于数列长度 \(n\)。

现在要使 \(a_i - b_i\) 互不相同，其实就是在说 \(a_i - b_i\) 在数轴上的分布要相对分散。我们大胆猜测：最大的 \(a_i\) 匹配最小的 \(b_i\)，次大的 \(a_i\) 匹配次小的 \(b_i\)，\(\dots\)，最小的 \(a_i\) 匹配最大的 \(b_i\)。

可以用反证法证明：假如 \(\exists i<j,~c_i=c_j\)，此时 \(a_i \ge a_j,b_i<b_j\)。则有：\(c_i=a_i-b_i>a_j-b_j=c_j\)。产生矛盾，故 \(\forall i<j,~c_i\not=c_j\)，证毕。

时间复杂度 \(O(Tn\log n)\)。

Code

#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

const int N = 4e4 + 10;

int T, n, a[N], p[N], Ans[N]; 

bool cmp(int x, int y) {
  return a[x] > a[y];
}

void solve() {
  read(n);
  For(i,1,n) read(a[i]), p[i] = i;
  sort(p + 1, p + n + 1, cmp);
  For(i,1,n) Ans[p[i]] = i;
  For(i,1,n) cout << Ans[i] << ' ';
  cout << '\n';
}

signed main() {
  read(T);
  while(T--) {
    solve();
  }
  return 0;
}

B. XOR Palindromes

Problem

给定一个 \(n\) 位二进制 \(01\) 串。一个数 \(x\) 是好的定义为：存在一个长度为 \(n\) 二进制 \(01\) 串 \(l\)，使得按位操作 \(s_i \oplus l_i\) 后的串为回文串。

现有长度为 \(n+1\) 答案串 \(t\)，第 \(i(0\le i\le n+1)\) 位为 \(1\) 表示数字 \(i\) 是好的，为 \(0\) 表示数字 \(i\) 是不好的。求 \(t\)。

Solve

首先，肯定是从小到大找答案。考虑最小的，合法（“好的”）的数 \(x\) 为多少。也就是求将原串变为回文串的最小步数。

做法是从串的中点向左右扩展。若两数不同，则耗费一步数更改其中的一位。具体是哪一位不需要管。因为我们只需要将其变为回文串，不需要关心其形态。

然后知道最小的 \(x\)，考虑怎样将答案拓展。不难发现，当 \(n\) 为奇数时，介于 \(x\sim n-x\) 之间的数 \(y\) 都是“好的”；当 \(n\) 为偶数时，介于 \(x\sim n-x\) 之间的数 \(y\) 且 \(y-x\) 为偶数都是“好的”。

证明很简单，当 \(n\) 为偶数时，每次在中点的两边对称的地方同时更改不会改变其回文的状态。也就是说，当 \(y-x\) 为偶数且 \(y\in[x,n-x]\) 时，\(y\) 是好的。奇数时同理，不过在中心改也不会改变其回文的状态，这样可以组合出 \([x,n-x]\) 的所有数，自然其中的所有数也都是“好的”。

最后模拟即可。

时间复杂度 \(O(Tn)\)。

Code

#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

const int N = 1e5 + 10;

int T, n;

char a[N];

void solve() {
  read(n);
  For(i,1,n) cin >> a[i];
  if(n & 1) {
    int l = (1 + n) >> 1, r = l, ans1 = 0;
    while(l >= 1) {
      if(a[l] != a[r]) ans1++;
      l--, r++;
    }
    For(i,0,n) {
      if(i >= ans1 && i <= n - ans1) cout << 1;
      else cout << 0; 
    }
    cout << '\n';
  } else {
    int l = n >> 1, r = l + 1, ans1 = 0;
    while(l >= 1) {
      if(a[l] != a[r]) ans1++;
      l--, r++;
    }
    For(i,0,n) {
      if(i >= ans1 && i <= n - ans1 && (i - ans1) % 2 == 0) cout << 1;
      else cout << 0; 
    }
    cout << '\n';
  }
}

signed main() {
  read(T);
  while(T--) {
    solve();
  }
  return 0;
}

C. Salyg1n and the MEX Game

Problem

交互题。给定一个 \(n\) 个元素的集合 \(S\)，元素记为 \(s_i(1 \le i \le n)\)。每一回合，你可以选择一个数 \(x(0\le x \le 10^9)\) 插入集合中，交互机会选择一个 \(\le x\) 的数，并将其从 \(S\) 中删除，保证总回合数不超过 \(2n-1\)。

游戏最后的答案为 MEX，你要最大化这个结果，交互机要最小化这个结果。设 \(R\) 为你和交互机操作的最佳策略下的答案，请你规定一个策略，使最终答案至少为 \(R\)。

Solve

脑瘫交互。

注意到每次交互机会选择一个 \(\le x\) 的数，并将其从 \(S\) 中删除。那么就很有可能删除掉你的 MEX。不过，你是先手。那么就能将问题转化：你先选择一个数插入，再变为交互机先手，你后手。

你先选择并插入的的数肯定是数列的 MAX，因为你要最大化 MEX。然后交互机删什么，你就填什么即可。

时间复杂度 \(O(Tn)\)。

Code

#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

const int N = 1e5 + 10;

int T, n, y, a[N];

void solve() {
  read(n);
  For(i,1,n) cin >> a[i];
  sort(a + 1, a + n + 1);
  int MEX = 0;
  For(i,1,n) {
    if(a[i] == MEX) MEX++;
  }
  cout << MEX << '\n';
  fflush(stdout);
  while(cin >> y) {
    if(y == -1) return ;
    cout << y << '\n';
    fflush(stdout);
  }
}

signed main() {
  read(T);
  while(T--) {
    solve();
  }
  return 0;
} 

这可能是我人生第一次自己做的交互题了。

D. Cyclic Operations

Problem

（咕咕咕...）

Solve

（咕咕咕...）

Code

（咕咕咕...）

E1. Salyg1n and Array (simple version)

Problem

交互题。交互库有一个长度为 \(n\) 的数列 \(a\)，求其所有元素的异或和，每次你可以选择一个 \(i\)，询问 \([i,i+k-1]\) 中的异或和，并将其翻转。询问不能超过 \(100\) 次。保证 \(n\) 与 \(k\) 均为偶数。

\(1 \le k \le n \le k^2 \le 2500\)。

Solve

当 \(n\bmod k=0\) 时，直接分成 \(\frac{n}{k}\) 然后区间覆盖询问就行了。
当 \(n \bmod k=0\) 时，\([1,k\left\lfloor \dfrac{n}{k} \right\rfloor]\) 直接区间覆盖询问即可，对于 \([k\left\lfloor \dfrac{n}{k} \right\rfloor+1,n]\) ，选择 \([k\left\lfloor \dfrac{n}{k} \right\rfloor-k+2,n-k+1]\) 的所有 \(i\) 并且询问即可。

证明：原数组记为 \(a_i\)，询问 \(k\left\lfloor \dfrac{n}{k} \right\rfloor-k+2\) 时，\(k\left\lfloor \dfrac{n}{k} \right\rfloor+1\) 会被计算进去，而 \([k\left\lfloor \dfrac{n}{k} \right\rfloor-k+2,k\left\lfloor \dfrac{n}{k} \right\rfloor]\) 总共会被计算两次，即两次异或操作，抵消。以此类推，最后，\([k\left\lfloor \dfrac{n}{k} \right\rfloor+1,n]\) 的所有数将会被计算一次。而 \([k\left\lfloor \dfrac{n}{k} \right\rfloor-k+2,k\left\lfloor \dfrac{n}{k} \right\rfloor]\) 将会被计算 \((n \bmod k) + 1\) 次，而 \(n \bmod k\) 为偶数，则 \((n \bmod k) + 1\) 为奇数。则原数列每个数都可以不重不漏的计算一次。

区间覆盖询问时，操作数为 \(\left\lfloor \dfrac{n}{k} \right\rfloor\)，题目数据范围给出 \(1 \le k \le n \le k^2 \le 2500\)，所以 \(\left\lfloor \dfrac{n}{k} \right\rfloor \le k \le n \le 50\)，所以询问数最多不会超过 \(50\) 次。而 \((n \bmod k) + 1 = n-\left\lfloor \dfrac{n}{k} \right\rfloor+1\le 50\)，所以总询问数不会超过 \(100\) 次，可以通过本题。

时间复杂度 \(O(Tn)\)。

Code

#include <bits/stdc++.h>
#define ll long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

int n, T, k, res;

int ask(int i) {
  cout << "? " << i << '\n';
  fflush(stdout);
  int x; cin >> x;
  return x;
}

void solve() {
  res = 0; 
  cin >> n >> k;
  int i;
  for (i = 1; i + k - 1 <= n; i += k) {
    res ^= ask(i);
  } 
  if(n % k == 0) {
    cout << "! " << res << '\n';
    fflush(stdout);
  } else {
    res ^= ask(i - k + (n % k) / 2);
    res ^= ask(n - k + 1);
    cout << "! " << res << '\n';
    fflush(stdout);
  }
  return ;
}

signed main() {
  cin >> T;
  while(T--) {
    solve(); 
  }
  return 0;
}

E2. Salyg1n and Array (hard version)

Problem

交互题。交互库有一个长度为 \(n\) 的数列 \(a\)，求其所有元素的异或和，每次你可以选择一个 \(i\)，询问 \([i,i+k-1]\) 中的异或和，并将其翻转。询问不能超过 \(57\) 次。保证 \(n\) 与 \(k\) 均为偶数。

Solve

我们发现 E1 的程序不高效率的原因在于它有很多的冗余运算。比如，最后的剩余段会被询问 \((n \bmod k) + 1\) 次，这是很不高效的。我们发现前面的区间覆盖询问 \(\left\lfloor \dfrac{n}{k} \right\rfloor\) 次是无法避免的。这时候，留给我们的剩余询问数就只剩下了 \(7\) 个。所以我们要高效的处理剩余段的询问。

我们考虑将 \([k\left\lfloor \dfrac{n}{k} \right\rfloor+1,n]\) 折半，一半的长度记为 \(l\)。将左半段区间和 \([k\left\lfloor \dfrac{n}{k} \right\rfloor+1-l,k\left\lfloor \dfrac{n}{k} \right\rfloor]\) 一起询问，然后原数组 \([k\left\lfloor \dfrac{n}{k} \right\rfloor+1-l,k\left\lfloor \dfrac{n}{k} \right\rfloor]\) 将会被翻转到折半区间的左半段区间，再与右半段区间询问一次。这样，原本 \([k\left\lfloor \dfrac{n}{k} \right\rfloor+1,n]\) 将会被询问一次。\([k\left\lfloor \dfrac{n}{k} \right\rfloor+1-l,k\left\lfloor \dfrac{n}{k} \right\rfloor]\) 总共会被询问 \(3\) 次，贡献一次答案。刚好将原数组的所有元素包含。

这样最多只需要询问 \(52\) 即可，可以通过此题。

Code

#include <bits/stdc++.h>
#define ll long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

namespace Read {
  template <typename T>
  inline void read(T &x) {
    x=0;T f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args&... args) {
    read(t), read(args...);
  }
}

using namespace Read;

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

int n, T, k, res;

int ask(int i) {
  cout << "? " << i << '\n';
  fflush(stdout);
  int x; cin >> x;
  return x;
}

void solve() {
  res = 0; 
  cin >> n >> k;
  int i;
  for (i = 1; i + k - 1 <= n; i += k) {
    res ^= ask(i);
  } 
  if(n % k == 0) {
    cout << "! " << res << '\n';
    fflush(stdout);
  } else {
    res ^= ask(i - k + (n % k) / 2);
    res ^= ask(n - k + 1);
    cout << "! " << res << '\n';
    fflush(stdout);
  }
  return ;
}

signed main() {
  cin >> T;
  while(T--) {
    solve(); 
  }
  return 0;
}

F. Most Different Tree

Problem

（咕咕咕...）

Solve

（咕咕咕...）

Code

（咕咕咕...）

标签：lfloor,ch,897,int,dfrac,Codeforces,read,Div,define
From： https://www.cnblogs.com/Daniel-yao/p/17702654.html

相关文章

  • 9.12 div.1
    EducationalCodeforcesRound100(RatedforDiv.2)EducationalCodeforcesRound101(RatedforDiv.2)EducationalCodeforcesRound102(RatedforDiv.2)B-FindTheArray思路：相邻的数要有一方能整除另一方，那么一方为1的话一定可以，按奇偶位置将数分为两部分，求出a......
  • Codeforces 1868C/1869E Travel Plan 题解 | 巧妙思路与 dp
    题目链接：TravelPlan题目大意：\(n\)个点的完全二叉树，每个点可以分配\(1\simm\)的点权，定义路径价值为路径中最大的点权，求所有路径的价值和。对于任意长度（这里主要指包括几个节点）的路径\(t\)，最大点权不超过\(k\)的方案数有\(k^t\)个，因此最大点权恰好为\(k\)的方案数有......
  • Codeforces Round 781 (Div. 2) B. Array Cloning Technique
    给一个长度为\(n\)的数组\(a\)。开始只有一份所给\(a\)的副本。你可以做以下两种操作：选择任意一个副本并且克隆它，然后将会多出一个克隆副本。交换两个元素，他们属于任意两个副本（可能是同一个）。需要判断最小操作数，使有一个副本的所有元素相同。观察一：只需要在开始的副本......
  • Codeforces Round 787 (Div. 3) B. Make It Increasing
    给一个长为\(n\)的数组\(a_1,a_2,\cdots,a_n\quad(0\leqa_i\leq10^9)\)。可以执行以下操作任意次：选择任意一个\(a_i\)并且执行\(a_i=\lfloor\frac{a_i}{2}\rfloor\)。输出最小操作次数，使得数组所有元素变为严格递增。观察：数组一些位置变小，将数组变为严......
  • Codeforces Round 791 (Div. 2) A. AvtoBus
    已知有\(n\)个轮子，会有一个车队车来换轮，且恰好使用完这些轮子。只知道这些车中有\(4\)轮车和\(6\)轮车。你需要估计这个车队最少可能有多少车和最多可能有多少车，或判断这是完全不可能的。观察：\(4x+6y=n\)，由裴蜀定理，当\(2\midn\)有解且\(2x+3y=\frac{n}{2}\)......
  • Codeforces Round 897 (Div. 2)
    目录写在前面ABCDE1/E2F写在最后写在前面比赛地址：https://codeforces.com/contest/1867。简略题解。还好没掉分。A令原数列中第\(k\)大对应\(k\)即可。///*By:Luckyblock*/#include<bits/stdc++.h>#defineLLlonglongconstintkN=4e4+10;//============......
  • 【题解】Educational Codeforces Round 141（CF1783）
    评价：educationalA.MakeitBeautiful题目描述：如果一个数组中存在一个数恰好等于该数前面所有数之和，那么这个数组就是丑的。如果一个数组不是丑的，就是美的。比如说：数组$[6,3,9,6]$是丑的，因为\(9=6+3\)；数组$[5,5,7]$是丑的，因为第二个\(5=5\)。数组$......
  • Codeforces Round 897 (Div. 2)
    F.MostDifferentTree当\(n=2\)时，只能构造一条长度为\(2\)的链。当\(n\ge3\)时，对于\(i\)\((1\lei\len)\)，以\(i\)作为根的树记为\(h_i\)，考虑枚举树找一个大小为\(s\)的树\(t\)，使得不存在任何一个\(h_i=t\)，且\(s\)尽可能小，然后从\(1\)连一条链到该数的根......
  • html div && span 容器元素
    htmldiv&&span容器元素div标签定义HTML文档中的一个分隔区块或者一个区域部分,标签常用于组合块级元素，以便通过CSS来对这些元素进行格式化span用于对文档中的行内元素进行组合标签提供了一种将文本的一部分或者文档的一部分独立出来的方式<html><head>......
  • Codeforces Round 897 (Div. 2)
    CodeforcesRound897(Div.2)A.green_gold_dog,arrayandpermutation分析:由题意:\[c_i=a_i-b_i\]\(c_i\)种类最多就是\(n\)个数都不同。若\(a_i\)不断变大，\(b_i\)不断变小，那么\(c_i\)会不断变大。代码:#include<bits/stdc++.h>usingnamespacestd;usingll......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99