首页 > 其他分享 >Codeforces Round 905 (Div. 2)

Codeforces Round 905 (Div. 2)

时间:2023-10-23 15:44:23浏览次数:39  
标签:cnt ch 905 int Codeforces kN printf Div getchar

目录

写在前面

比赛地址:https://codeforces.com/contest/1884

oonp 这场 div2 怎么才 2k5 人打啊我草

里面还不知道多少大神的小号,呃呃

打了 1k3 掉了 75 分也是牛逼

A

考虑如何拼出一个长度为 \(n-k\) 的回文串,先一对一对地拼,再看需不需要再顶上去一个单的即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, k, cnt[30];
char s[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() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read(), k = read();
    scanf("%s", s + 1);
    int r = n - k;
    
    for (int i = 0; i < 26; ++ i) cnt[i] = 0;
    for (int i = 1; i <= n; ++ i) cnt[s[i] - 'a'] ++;
    for (int i = 0; i < 26; ++ i) {
      while (r >= 2 && cnt[i] >= 2) r -= 2, cnt[i] -= 2;
    }
    for (int i = 0; i < 26; ++ i) {
      if (r == 1 && cnt[i] >= 1) -- r;
    }
    printf("%s\n", r ? "NO" : "YES");
  }
  return 0;
}

B

发现 \(2\le k\le 5\),懒得多想了,于是直接无脑大力特判。

见代码吧。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, k, a[kN];
int cnt[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;
}
void Solve2() {
  int r = 1;
  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    r = r * a[i] % 2;
  }
  printf("%d\n", (r == 1));
}
void Solve3() {
  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    cnt[a[i] % 3] ++;
  }
  if (cnt[0]) printf("0\n");
  else if (cnt[2]) printf("1\n");
  else if (cnt[1]) printf("2\n");
}
void Solve4() {
  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    cnt[a[i] % 4] ++;
  }
  if (cnt[0] || cnt[2] >= 2) printf("0\n");
  else if (cnt[3]) printf("1\n");
  else if (n >= 2 && cnt[2] >= 1) printf("1\n");
  else if (n == 1 && cnt[2] == 1) printf("2\n");
  else if (n == 1 && cnt[1] == 1) printf("3\n");
  else printf("2\n");
}
void Solve5() {
  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    cnt[a[i] % 5] ++;
  }
  if (cnt[0]) printf("0\n");
  else if (cnt[4]) printf("1\n");
  else if (cnt[3]) printf("2\n");
  else if (cnt[2]) printf("3\n");
  else if (cnt[1]) printf("4\n");
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read(), k = read();
    for (int i = 0; i <= 10; ++ i) cnt[i] = 0;
    // printf("-------");
    if (k == 2) Solve2();
    if (k == 3) Solve3();
    if (k == 4) Solve4();
    if (k == 5) Solve5();
  }
  return 0;
}

C

我的想法可能比较奇怪呃呃

首先考虑求补集,求不合法区间数量。记权值 \(i\) 的出现位置为 \(p_i = \{ p_{i, 1}, p_{i, 2}, \dots, p_{i, k} \}\) 手玩之后发现以 \(p_{i, 1}\sim p_{i, k-1}\) 为右端点的区间一定不合法,以 \(p_{i, 2}\sim p_{i, k}\) 为左端点的区间一定不合法。又发现考虑上述区间一定可以覆盖所有不合法区间,于是仅需考虑减去左右端点均为上述位置,即 \([p_{j, \dots}, p_{k, \dots}]\) 型的区间的贡献。

考虑枚举权值的同时维护两个树状数组,维护某个位置是否作为左端点/右端点被统计了贡献,然后在枚举每种权值的上述两种出现位置的同时使用树状数组求对应的端点数量即可。

总时间复杂度 \(O(n\log n)\) 级别。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, idnum, a[kN];
std::map <int, int> id;
std::vector <int> pos[kN], val;
//=============================================================
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;
}
namespace BIT1 {
  #define lowbit(x) ((x)&(-x))
  const int kL = kN;
  int t, lim, time[kN];
  LL f[kN];
  void Init(int n_) {
    ++ t;
    lim = n_;
  }
  void Insert(int pos_, int val_) {
    for (int i = pos_; i <= lim; i += lowbit(i)) {
      if (time[i] != t) time[i] = t, f[i] = 0; 
      f[i] += val_;
    }
  }
  LL Sum(int pos_) {
    LL ret = 0;
    for (int i = pos_; i; i -= lowbit(i)) {
      if (time[i] != t) time[i] = t, f[i] = 0; 
      ret += f[i];
    }
    return ret;
  }
  LL Query(int l_, int r_) {
    return Sum(r_) - Sum(l_ - 1);
  }
  #undef lowbit
}
namespace BIT2 {
  #define lowbit(x) ((x)&(-x))
  const int kL = kN;
  int t, lim, time[kN];
  LL f[kN];
  void Init(int n_) {
    ++ t;
    lim = n_;
  }
  void Insert(int pos_, int val_) {
    for (int i = pos_; i <= lim; i += lowbit(i)) {
      if (time[i] != t) time[i] = t, f[i] = 0; 
      f[i] += val_;
    }
  }
  LL Sum(int pos_) {
    LL ret = 0;
    for (int i = pos_; i; i -= lowbit(i)) {
      if (time[i] != t) time[i] = t, f[i] = 0; 
      ret += f[i];
    }
    return ret;
  }
  LL Query(int l_, int r_) {
    return Sum(r_) - Sum(l_ - 1);
  }
  #undef lowbit
}
void Init() {
  n = read();
  BIT1::Init(n), BIT2::Init(n);
  for (int i = 1; i <= n; ++ i) pos[i].clear();
  val.clear();
  id.clear();
  idnum = 0;

  for (int i = 1; i <= n; ++ i) {
    a[i] = read();
    if (!id.count(a[i])) id[a[i]] = ++ idnum, val.push_back(a[i]);
    pos[id[a[i]]].push_back(i);
  }
}
void Solve() {
  LL ans = 1ll * n * (n + 1) / 2ll;
  for (auto x: val) {
    if (pos[id[x]].size() == 1) continue;
    for (int i = 0, sz = pos[id[x]].size(); i < sz - 1; ++ i) {
      int p = pos[id[x]][i];
      ans -= p - BIT1::Query(1, p);
      BIT2::Insert(p, 1);
    }
    for (int i = pos[id[x]].size() - 1; i >= 1; -- i) {
      int p = pos[id[x]][i];
      ans -= (n - p + 1) - BIT2::Query(p, n);
      BIT1::Insert(p, 1);
    }
    // ans -= s - BIT2::Query(s, n);
  }
  printf("%lld\n", ans);
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    Solve();
  }
  return 0;
}

D1/D2

先手玩下这个游戏。当 \(a, b\) 确定时,发现最优的策略是先分别对 \(a, b\) 排序,每轮删掉 \(a\) 中最大的和 \(b\) 中最小的。对于排序后的两个数组,记 \(p_i = \min_{b_j >a_i} j\),特别地若这样的 \(j\) 不存在则 \(p_i=n+1\),手玩下可以发现某轮游戏的答案即 \(\max p_i\)。

于是 D1 就是傻逼题了,排序后再 \(O(n)\) 地模拟上述过程即可。

再考虑 \(m\not= 1\) 的情况。记 \(f(k)\) 表示当 \(a_1 = k\) 时某轮游戏的答案。手玩下发现当 \(k\) 很大时仅有 \(f(k) = f(1) + 1\),考虑实际意义即插入了一个很大的数使得原来的 \(\max p_i\) 对应的位置 \(i\) 左移了一位从而使 \(\max p_i\) 增大了 1。于是猜测不同游戏的答案仅与是否影响了这个位置有关,且 \(k\) 越大越有可能影响,于是猜测存在一个阈值 \(K\) 使得:

\[\begin{cases} f(k) = f(1) &k \le K\\ f(k) = f(1) + 1 &k > K \end{cases}\]

可以通过二分+重复 D1 中的模拟来求得 \(K\),答案即 \(K\times f(1) + (m - K)\times (f(1) + 1)\)。

总时间复杂度 \(O(n\log n\log m)\) 级别。

有更牛逼的找阈值的不用二分的做法但是懒了,就这样吧。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, m, oria[kN], orib[kN], a[kN], b[kN];
int maxp;
//=============================================================
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 Init() {
  n = read(), m = read();
  for (int i = 2; i <= n; ++ i) oria[i] = read();
  for (int i = 1; i <= n; ++ i) b[i] = read();
  std::sort(b + 1, b + n + 1);
}
int Solve(int val_) {
  a[1] = val_;
  for (int i = 2; i <= n; ++ i) a[i] = oria[i];
  std::sort(a + 1, a + n + 1);

  maxp = 0;
  for (int p = 1, q = 1; p <= n; ++ p) {
    while (a[p] >= b[q] && q <= n) ++ q;
    maxp = std::max(maxp, q - p);
  }
  return maxp;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    Init();
    int f = Solve(1), pos = m;
    for (int l = 1, r = m; l <= r; ) {
      int mid = (l + r) >> 1;
      if (Solve(mid) == f) {
        pos = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    printf("%lld\n", 1ll * pos * f + 1ll * (m - pos) * (f + 1));
  }
  return 0;
}

E

写在最后

学到了什么:

  • D:阈值

标签:cnt,ch,905,int,Codeforces,kN,printf,Div,getchar
From: https://www.cnblogs.com/luckyblock/p/17782633.html

相关文章

  • Codeforces Round 905 - div.3(A B C D E)
    目录CodeforcesRound905(Div.3)A.MorningB.ChemistryC.RaspberriesCodeforcesRound905(Div.3)A.Morning模拟光标移动即可voidsolve(){ stringss; cin>>ss; charch='1'; intans=0; for(autoc:ss){ if(c!=ch){ intx=c,y=c......
  • Codeforces Round 904 (Div. 2)
    目录写在前面ABCD写在最后写在前面比赛地址:https://codeforces.com/contest/1884捏吗我不会容斥,我是飞舞。A\(k\le10\),于是直接枚举\(x\simx+20\)检查即可。///*By:Luckyblock*/#include<bits/stdc++.h>#defineLLlonglong//=================================......
  • Codeforces Round 855 (Div. 3) C. Powering the Hero
    有\(n\)张卡的卡堆,你可以自顶向下抽卡。装备卡显示数值为\(a_i(a_i>0)\),英雄卡显示数值为\(a_i=0\)。如果是装备卡,你可以将卡抽出放在装备堆。如果是英雄卡,你可以将装备堆顶端的一张数值为\(x\)的装备卡装备给英雄,英雄数值\(+x\)。无论是否装备,都加入英雄堆。询问......
  • Codeforces Round 857 (Div. 2) B. Settlement of Guinea Pigs
    你非常喜欢豚鼠。每个笼子可以住两只豚鼠,且你不想把每个笼子放入不同性别的豚鼠。豚鼠只有两种性别。假设你买到豚鼠时并不知道性别,只有医生能够分辨。接下来的\(n\)天方案中,若第\(i\)天为\(1\),你买入一只豚鼠;若为\(2\),你请医生分辨你的豚鼠性别。给出方案,你最少需要准......
  • Nebius Welcome Round (Div. 1 + Div. 2) B. Vaccination
    你管理一个疫苗接种站,将会有\(n\)个人前来接种疫苗。第\(i\)个到来的人时间为\(t_i\),已知每个人的等待时间不会超过\(w\)分钟。疫苗存放在特质冰箱中,一袋疫苗有\(k\)支,当一袋疫苗在\(x\)时刻打开时,它的有效时间为\(d\)。现在询问最少需要打开多少袋疫苗满足\(n\)......
  • Educational Codeforces Round 145 (Rated for Div. 2) B. Points on Plane
    给一个二维平面,你需要在上面放\(n\)个芯片。将一个芯片放在\((x,y)\)的代价为\(|x|+|y|\)。放\(n\)个代价的代价为,所有芯片中耗费的最大代价。并且你需要保证任意两个芯片之间的距离严格\(>1\)。现在给出\(n\)给芯片,询问放\(n\)个芯片的最小代价。一:不难想到......
  • 使一个div垂直+水平居中的几种方法
    使一个div垂直+水平居中的几种方法思路1:绝对定位居中(原始版)思路2:绝对定位居中(改进版之一)思路3:绝对定位居中(改进版之二)思路4:flex布局居中思路1:绝对定位居中(原始版)这个是我回答出来的,也是被各位所熟知的一种方法,设外层div相对定位,内层div绝对定位,top、left分别设为50%,然后通过设置m......
  • Educational Codeforces Round 149 (Rated for Div. 2)
    这场D被切穿了。A题答案为x或者x-11B题答案就是最长的连续一段的长度+1证明的话大概可以将它看成是几段连续上升和下降的段,然后在峰谷、峰顶分别填上最小、最大,剩下的就依次递增或递减就行。C题将一段连续的0/1视作一个块,那么我们最小化这个块的数量就行。D题如果猜到......
  • Codeforces Round 863 (Div. 3) B. Conveyor Belts
    给一个\(n\timesn\)的矩阵,\(n\)是偶数。将矩阵按圈分割,同一圈的位置可以不消耗代价移动,可以消耗一个代价移动到相邻圈。给出\(n,x_1,y_1,x_2,y_2\),询问\((x_1,y_1)\)移动到\((x_2,y_2)\)的代价最小是多少。显然对每个圈可以选择左上角作为定点。显然直线\(......
  • Codeforces Round 865 (Div. 2) B. Grid Reconstruction
    给一个\(2\timesn\)的网格,且\(n\)是偶数。你需要将\(1\sim2\timesn\)填入这个网格。一条路径是从\((1,1)\)开始,每次只能向右或向下,到\((2,n)\)结束时,所经过的位置。按经过点的顺序标号,一两条路径的代价是\(cost=a_1-a_2+a_3-a_4+\cdots=\sum_{i=1......