首页 > 其他分享 >「题解」Codeforces Round 905 (Div. 3)

「题解」Codeforces Round 905 (Div. 3)

时间：2023-10-26 12:11:17浏览次数：36  
标签：return 905 int 题解 scanf long ans Pair Div

before

终于有一篇题解是一次性更所有题的了。

A. Morning

Problem

A. Morning

Sol&Code

根据题意模拟即可。

#include <bits/stdc++.h>

typedef long long ll;

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int T;

int main() {
  scanf("%d", &T);
  while (T--) {
    std::string s;
    std::cin >> s;
    int now = 1, ans = 1;
    for (int i = 0; i < 4; ++i) {
      if (now == s[i] - '0') ++ans;
      else {
        ans += std::abs(((s[i] - '0') ? (s[i] - '0') : 10) - (now ? now : 10)) + 1;
        now = s[i] - '0';
      }
    }
    printf("%d\n", ans - 1);
  }
  return 0;
}

B. Chemistry

Problem

B. Chemistry

Sol&Code

回文与否只与字符出现次数有关。

从长为 \(n\) 的字符串中删去 \(k\) 个字符，若最后的串长度 \((n - k)\) 为奇数，首先需要原串中出现奇数次的字符的数量不超过 \(k + 1\)，若最后的串长度 \((n - k)\) 为奇数，需要原串中出现奇数次的字符的数量不超过 \(k\)。保证出现奇数次的字符数量合适后只需要剩下的删除字符次数为偶数即可。分类讨论可得，只要满足了前者，后者就得到了保证。（真神奇）

#include <bits/stdc++.h>

typedef long long ll;

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int T, n, k, odd, cnt[648];
std::string s;

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d", &n, &k);
    std::cin >> s;
    for (int i = 'a'; i <= 'z'; ++i) cnt[i] = 0;
    for (int i = 0; i < n; ++i) ++cnt[s[i]];
    bool okay = true;
    if ((n - k) & 1) {
      odd = 0;
      for (int i = 'a'; i <= 'z'; ++i) {
        if (cnt[i] & 1) ++odd;
      }
      if (odd - 1 > k) okay = false;
    } else {
      odd = 0;
      for (int i = 'a'; i <= 'z'; ++i) {
        if (cnt[i] & 1) ++odd;
      }
      if (odd > k) okay = false;
    }
    puts(okay ? "YES" : "NO");
  }
  return 0;
}

C.Raspberries

Problem

C.Raspberries

Sol&Code

\(k\) 只有四种情况。

对每种情况分类讨论凑出因子的情况即可。

#include <bits/stdc++.h>
#define N 100001

typedef long long ll;

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

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

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    if (k == 2) {
      int ans = 1;
      for (int i = 1; i <= n; ++i) {
        if (!(a[i] & 1)) ans = 0;
      }
      printf("%d\n", ans);
    }
    if (k == 3) {
      int ans = 2;
      for (int i = 1; i <= n; ++i) {
        if (a[i] % 3 == 0) { ans = 0; break; }
        if (a[i] % 3 == 2) { ans = 1; }
      }
      printf("%d\n", ans);
    }
    if (k == 4) {
      int cnt = 0, ans = 3;
      for (int i = 1; i <= n; ++i) {
        if (a[i] % 4 == 0) { ans = 0; break; }
        if (a[i] % 4 == 3) { ans = min(ans, 1); }
        if (a[i] % 4 == 2) { ans = min(ans, 2); }
        if (a[i] % 4 == 1) { ans = min(ans, 3); }
        if (a[i] % 2 == 0) ++cnt;
      }
      if (cnt >= 2) printf("%d\n", 0);
      if (cnt == 1) printf("%d\n", min(1, ans));
      if (cnt == 0) printf("%d\n", min(2, ans));
    }
    if (k == 5) {
      int ans = 4;
      for (int i = 1; i <= n; ++i) {
        if (a[i] % 5 == 0) { ans = 0; break; }
        if (a[i] % 5 == 2) { ans = min(ans, 3); }
        if (a[i] % 5 == 3) { ans = min(ans, 2); }
        if (a[i] % 5 == 4) { ans = min(ans, 1); }
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}

D. In Love

Problem

D. In Love

Sol&Code

不相交即满足最小的右端点的位置小于最大的左端点的位置

multiset可以满足插入、删除、有序的需求

#include <bits/stdc++.h>
#define N 100001
#define fir first
#define sec second

typedef long long ll;
typedef std::pair<int, int> pii;

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int T;
class Pair {
  public:
    Pair(int x, int y) : a(x), b(y) {}
    int a, b;
};

bool cmp1(const Pair& p1, const Pair& p2) {
  if (p1.a == p2.a) return p1.b < p2.b;
  return p1.a < p2.a;
}

bool cmp2(const Pair& p1, const Pair& p2) {
  if (p1.b == p2.b) return p1.a < p2.a;
  return p1.b < p2.b;
}

std::multiset<Pair, decltype(cmp1)*> s1(cmp1);
std::multiset<Pair, decltype(cmp2)*> s2(cmp2);

int main() {
  scanf("%d", &T);
  while (T--) {
    getchar();
    char ch;
    int a, b;
    ch = getchar();
    scanf("%d %d", &a, &b);
    if (ch == '+') {
      s1.insert(Pair(a, b));
      s2.insert(Pair(a, b));
    } else {
      s1.erase(s1.find(Pair(a, b)));
      s2.erase(s2.find(Pair(a, b)));
    }
    bool okay = true;
    if (s1.size() < 2) okay = false;
    else if ((*s2.begin()).b >= (*(--s1.end())).a) okay = false;
    puts(okay ? "YES" : "NO");
  }
  return 0;
}

E. Look Back

Problem

E. Look Back

Sol&Code

取 \(log\) 后避免了爆炸的问题 \(·2\) 变为 \(+1\)。

#include <bits/stdc++.h>
#define N 100001
#define eps 1e-10

typedef long long ll;

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

double b[N];
int T, n, a[N];

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) b[i] = std::log(a[i]) / std::log(2.0);
    long long ans = 0;
    for (int i = 2; i <= n; ++i) {
      if (b[i - 1] - b[i] >= eps) {
        double cha = b[i - 1] - b[i];
        int ad = cha;
        if (cha - ad >= eps) ans += ad + 1, b[i] += ad + 1;
        else ans += ad, b[i] += ad;
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}

F. You Are So Beautiful

Problem

F. You Are So Beautiful

Sol&Code

对于原文中的一串 \(s_l s_{l + 1} s_{l + 2} \dots s_r\) 只出现一次即保证 \(l\) 前没有出现过 \(s_l\)，\(r\) 后没有出现过 \(s_r\)。若其中任意一个出现过则与 \(s_l s_{l + 1} s_{l + 2} \dots s_r\) 相同的子序列不唯一，没有出现过则左端点与右端点固定了。题目转化为了维护第一次出现的字符的个数。

#include <bits/stdc++.h>
#define N 100001
#define lowbit(x) (x & -x)

typedef long long ll;

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

void add(int x) {
  while (x <= n) {
    ++bit[x];
    x += lowbit(x);
  }
}

ll ask(int x, ll res = 0) {
  while (x > 0) {
    res += bit[x];
    x -= lowbit(x);
  }
  return res;
}

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) bit[i] = 0;
    std::map<int, int> mp;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = n; i >= 1; --i) {
      ++mp[a[i]];
      if (mp[a[i]] == 1) add(n - i + 1);
    }
    std::map<int, int> mp2;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
      ++mp2[a[i]];
      if (mp2[a[i]] == 1) ans += ask(n - i + 1);
    }
    printf("%lld\n", ans);
  }
  return 0;
}

G1. Dances (Easy version)

Problem

Dances (Easy version)

Sol&Code

贪心的用双指针从小到大匹配 \(a\) 中元素与 \(b\) 中比该元素稍大的元素。

#include <bits/stdc++.h>
#define N 100001

int T, n, m, a[N], b[N];

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d", &n, &m);
    a[1] = m;
    for (int i = 2; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
    std::sort(a + 1, a + n + 1);
    std::sort(b + 1, b + n + 1);
    int l = 1, r = 1, ans = 0;
    while (l <= n && r <= n) {
      while (l <= n && r <= n && b[r] > a[l]) ++l, ++r, ++ans;
      ++r;
    }
    printf("%d\n", n - ans);
  }
  return 0;
}

G2. Dances (Hard Version)

Problem

G2. Dances (Hard Version)

Sol&Code

一个数在不断变大的过程中最多使答案变大 \(1\) 一次。即该数由匹配到不匹配。

二分找什么时候变大即可。

#include <bits/stdc++.h>
#define N 100001

int T, n, m, k, a[N], b[N], c[N];

bool check(int x, int res = 0) {
  c[1] = x;
  for (int i = 2; i <= n; ++i) c[i] = a[i];
  std::sort(c + 1, c + n + 1);
  int p1 = 1, p2 = 1;
  while (p1 <= n && p2 <= n) {
    while (p1 <= n && p2 <= n && c[p1] < b[p2]) ++p1, ++p2, ++res;
    ++p2;
  }
  return res < k;
}

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d", &n, &m); a[1] = 1;
    for (int i = 2; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
    std::sort(a + 1, a + n + 1);
    std::sort(b + 1, b + n + 1);
    int p1 = 1, p2 = 1; k = 0;
    while (p1 <= n && p2 <= n) {
      while (p1 <= n && p2 <= n && a[p1] < b[p2]) ++p1, ++p2, ++k;
      ++p2;
    }
    int l = 1, r = m;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (check(mid)) r = mid - 1;
      else l = mid + 1;
    }
    printf("%lld\n", 1ll * (n - k) * (l - 1) + 1ll * (n - k + 1) * (m - l + 1));
  }
  return 0;
}

After

赛时 \(E\) 精度除了问题，害怕，救救。

还是做的太慢。

\(G2\) 好像有不用二分的做法。

标签：return,905,int,题解,scanf,long,ans,Pair,Div
From： https://www.cnblogs.com/poi-bolg-poi/p/17789018.html

相关文章

  • CF888C题解
    分析容易想到可以枚举每个字母，分别求其最小\(k\)取\(\min\)。思考对于一个\(k\)，如何判其不合法。容易想到如果存在一个没有这个字符的长度大于等于\(k\)的子段，那么这个\(k\)就不合法。那么我们就知道如何求最小合法\(k\)了。找到最长的没有这个字符的子段，其长度加......
  • 【算法题】2905. 找出满足差值条件的下标 II
    题目：给你一个下标从0开始、长度为n的整数数组nums，以及整数indexDifference和整数valueDifference。你的任务是从范围[0,n-1]内找出2个满足下述所有条件的下标i和j：abs(i-j)>=indexDifference且abs(nums[i]-nums[j])>=valueDifference返回整数数组a......
  • CF888A题解
    分析因为一个数不可能同时大于并小于它两边的数，所以两种数的集合不存在交集。所以分别扫一遍两种数的个数加在一起即可。代码#include<iostream>usingnamespacestd;constexprintMAXN(1000007);inta[MAXN];intn,ans;inlinevoidread(int&temp){cin>>t......
  • Redisson分布式锁主从一致性问题解决
    Redis联锁联锁（RedissonMultiLock）对象可以将多个RLock对象关联为一个联锁，实现加锁和解锁功能。每个RLock对象实例可以来自于不同的Redisson实例。如果负责储存分布式锁的某些Redis节点宕机以后，而且这些锁正好处于锁住状态，就会出现死锁问题。为了避免这种情况的发生，Redisson内部提供......
  • Codeforces 1786 / Codeforces Round #850 (Div.2)
    CodeforcesRound#850(Div.2)https://codeforces.com/contest/1786ProblemA1Non-alternatingDeck(easyversion)ProblemA2AlternatingDeck(hardversion)注意到最多进行\(O(\sqrtn)\)步，直接模拟即可。ProblemBCakeAssemblyLine题目保证了一定是\(n\)个蛋......
  • AGC304Ex Constrained Topological Sort 题解
    AT一个直接的想法是拓扑排序时从小到大标号：每次在入度为\(0\)的点中找到\(l_{u}\lei\)且\(r_{u}\)最小的\(u\)，令\(p_{u}=i\)问题是如果\(r_{u}\)很大，那么\(u\)被标号的优先级很低，会连累\(u\)的后继中\(r\)较小的点做法是倒着拓扑一遍，令\(r_{u}\leftarrow\m......
  • [ARC164D]1D Coulomb 题解
    [ARC164D]1DCoulomb题解题意在长为\(2N\)的数轴上放有\(2N\)个小球，第\(i\)个小球在坐标\(i\)的位置。\(2N\)个小球中有\(N\)个小球带正电，有\(N\)个小球带负点。记第\(i\)个小球带\(a_i\)单位电荷（\(a_i\in\{1,-1\}\)），小球之间受到力的作用，第\(i\)个小球受到......
  • P3214 [HNOI2011] 卡农 题解
    感觉不是很麻烦，可能就组合排列转化绕一点。。。抽象化题意给定\(n\)个元素，从中选出\(m\)个集合，要求：集合不为空，集合里不能有相同的元素\(m\)个集合都互不相同所有元素被选出的次数为偶数求方案数，并对\(100000007\)取模凭感觉是DP+组合数设\(dp[i][0/1]\)......
  • P6109 [Ynoi2009] rprmq1 题解-猫树+Segment Tree Beats
    20231025P6109[Ynoi2009]rprmq1题解-猫树+SegmentTreeBeats不愧是学长出的题。。。让我更深刻地理解了猫树。Statement传送门有一个\(n\timesn\)的矩阵\(a\)，初始全是\(0\)，有\(m\)次修改操作和\(q\)次查询操作，先进行所有修改操作，然后进行所有查询操作。一次修......
  • P5156 [USACO18DEC] Sort It Out P 题解
    题意有一个长度为\(n\)的排列\(a_1,a_2,\cdots,a_n\)，选出\(\{1,2,\cdots,n\}\)的一个子集，对这个子集中的数依次进行如下操作：设当前数为\(v\)，则若\(a_v\)大于\(a_{v+1}\)（如果有的话），就交换。如果小于，则若\(a_v<a_{v-1}\)（如果有的话），就交换。重复上述操作知道\(a_{v-1}<......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99