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

Codeforces Round 901 (Div. 2)

时间:2023-10-03 15:35:24浏览次数:39  
标签:ch int Codeforces long 901 isdigit Div operatorname getchar

目录

写在前面

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

爱丽数码我真的好喜欢你啊为了你我要定制你的帆布包口牙!!!!

A

显然只会在剩余时间为 1 时使用工具,模拟即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
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 --) {
    int a = read(), b = read(), n = read();
    LL ans = 0;
    for (int i = 1; i <= n; ++ i) {
      ans += b - 1;
      b = 1;
      b += read();
      b = std::min(b, a);
    }
    ans += b;
    printf("%lld\n", ans);
  }
  return 0;
}

B

看到 \(k\) 这么大果断猜想若干次操作后一定会陷入某个拉扯的状态。

手玩下发现几轮操作后每次都是用自己手上的全局最小值换对面的全局最大值。

赛时懒得推具体几轮操作了,写了个暴力,出现上述情况后就可以直接判了。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 60;
const int kInf = 1e9 + 2077;
//=============================================================
int n, m, k, a[kN], b[kN];
int maxx, minx;
//=============================================================
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;
}
bool Judge(int now_) {
  if (now_ % 2 == 1) {
    return a[1] == minx && b[m] == maxx;
  } else {
    return b[1] == minx && a[n] == maxx;
  }
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read(), m = read(), k = read();
    maxx = -kInf, minx = kInf;
    for (int i = 1; i <= n; ++ i) {
      a[i] = read();
      maxx = std::max(maxx, a[i]);
      minx = std::min(minx, a[i]);
    }
    for (int i = 1; i <= m; ++ i) {
      b[i] = read();
      maxx = std::max(maxx, b[i]);
      minx = std::min(minx, b[i]);
    }
    for (int i = 1; i <= k; ++ i) {
      std::sort(a + 1, a + n + 1);
      std::sort(b + 1, b + m + 1);
      if (Judge(i)) {
        int r = k - i + 1;
        if (i % 2 == 1) {
          if (r % 2 == 1) std::swap(a[1], b[m]);
        } else {
          if (r % 2 == 1) std::swap(b[1], a[n]);
        }
        break;
      }
      if (i % 2 == 1) {
        if (a[1] < b[m]) std::swap(a[1], b[m]);
      } else {
        if (b[1] < a[n]) std::swap(b[1], a[n]);
      }
    }
    LL sum = 0;
    for (int i = 1; i <= n; ++ i) sum += a[i];
    printf("%lld\n", sum);
  }
  return 0;
}

C

只能把林檎切成原来的 \(\frac{1}{2^k}\),已知最后要全部拼成 \(\frac{n}{m}\) 的形式,则有解当且仅当 \(\frac{n}{m}\) 约分后分母为 \(2\) 的幂次。

显然拼起来的方案是唯一的,考虑每种大小的林檎块需要多少即可。于是考虑按照降序枚举林檎块的大小,将还未使用的所有林檎块都切成该大小,检查加上这些林檎块后能否恰好拼成 \(\frac{n}{m}\),如果不能恰好拼成则减去所需的此大小的林檎块,再重复上述过程。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kInf = 1e9 + 2077;
//=============================================================
int n, m, tempn, tempm, g, flag;
std::map <int, int> mylog2;
LL 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 gcd(int x_, int y_) {
  return y_ ? gcd(y_, x_ % y_) : x_;
}
LL Solve(int m_, int remain_) {
  if (remain_ % m_ == 0) return 0;
  LL ret = 1ll * remain_ * g;
  remain_ *= 2;
  return ret + Solve(m_, remain_ - remain_ / m_ * m_);
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  for (int i = 1, j = 0; i <= kInf; i <<= 1ll, ++ j) {
    mylog2[i] = j;
  }

  int T = read();
  while (T --) {
    ans = flag = 0;
    
    n = tempn = read(), m = tempm = read(), g = gcd(n, m);
    tempn /= g, tempm /= g;
    if (!mylog2.count(tempm)) {
      printf("-1\n");
      continue;
    }
    ans = Solve(tempm, tempn - tempn / tempm * tempm);
    printf("%lld\n", ans);
  }
  return 0;
}

D

经过大力手玩可以发现下列显然结论:

  • \(n\le 5000\),则 \(\operatorname{mex} \le 5000\)。
  • 删除后有贡献的数为 \(0\sim \operatorname{mex} - 1\)。
  • 每次删除的数的权值是递减的,否则删除之后对 \(\operatorname{mex}\) 的减小没有贡献。
  • 删除到某种权值时肯定是连续地把这一权值全部删完。
  • 删完 0 之后代价也变为 0,相当于结束状态。

考虑删除权值直到把 0 删完的顺序,可以得到一个显然的 DP。设 \(f_{i}\) 表示恰好删到 \(\operatorname{mex}=i\) 时所需的最小代价,初始化 \(f_{\operatorname{mex}} = 0\),考虑倒序枚举 \(f_{i}(0\le i\le \operatorname{mex})\) 即当前的 \(\operatorname{mex}\),填表法更新 \(f_{j}(0\le j< i)\)(\(j\) 为当前正在删除的权值),预处理 \(\operatorname{cnt}_j\) 表示权值 \(j\) 的出现次数,则有转移 \(f_{j}\leftarrow f_{i} + (\operatorname{cnt}_j - 1) + j\)。

最终答案即为 \(f_{0}\),总时间复杂度 \(O(n^2)\) 级别,可过。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5010;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, m, a[kN], cnt[kN];
LL f[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 Solve() {
  int mex = 0;
  while (cnt[mex]) ++ mex;
  for (int i = 0; i <= mex; ++ i) f[i] = kInf;

  f[mex] = 0;
  for (int i = mex; i >= 0; -- i) {
    for (int j = i - 1; j >= 0; -- j) {
      f[j] = std::min(f[j], f[i] + (cnt[j] - 1) * i + j);
    }
  }
  printf("%lld\n", f[0]);
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  int T = read();
  while (T --) {
    n = read();
    for (int i = 1; i <= n; ++ i) {
      a[i] = read(); 
      if (a[i] <= 5000) cnt[a[i]] ++;
    }
    Solve();
    for (int i = 1; i <= n; ++ i) {
      if (a[i] <= 5000) cnt[a[i]] = 0;
    }
  }
  return 0;
}

E

咕咕

写在最后

学到了什么:

  • B:进行轮数超多的过程定是有其独门绝技口牙!
  • D:飞舞别惦记你那 b 贪心了,这 DP 都看不出来?

标签:ch,int,Codeforces,long,901,isdigit,Div,operatorname,getchar
From: https://www.cnblogs.com/luckyblock/p/17741170.html

相关文章

  • 「题解」Codeforces Round 894 (Div. 3)
    A.GiftCarpetProblem题目Sol&Code签到题#include<bits/stdc++.h>#defineN21typedeflonglongll;intmin(inta,intb){returna<b?a:b;}intmax(inta,intb){returna>b?a:b;}intT,n,m,a[4];std::strings[N];i......
  • CodeForces-1276#B 题解
    正文这是样例1第1组数据的图。让我们观察一下,路径1->6、1->7、2->6、2->7是可行的,所以答案为4。上述路径中好像点4没有贡献?再看看样例1第2组数据的图。发现点1和点4相互之间存在其他路径,无需经过点\(a\)和点\(b\)。综上,我们可以知道:在\(a\)和\(b\)......
  • Codeforces Round 730 (Div. 2) B. Customising the Track
    有\(n\)条高速公路,第\(i\)条告诉公路上的车流为\(a_i\)。现在可以执行以下操作任意次:将第\(i\)条高速公路上的一辆车移到第\(j\)条高速公路。需要求最小的\(\sum_{i=1}^{n}\sum_{j=i+1}^{n}|a_i-a_j|\)。不难发现可以构造\(\foralli,j,a_i=a_j\)使任......
  • Educational Codeforces Round 112 (Rated for Div. 2) A. PizzaForces
    有三种披萨:\(6\)、\(8\)、\(10\)块披萨。制作时间分别需要:\(15\)、\(20\)、\(25\)分钟。现在有\(n\)个人,每人需要一块披萨。询问使所有人能获得披萨的最快时间。观察:发现三种披萨的性价比都一样。(否则按最优性价比贪心)需要让得到的披萨数量\(m\geqn\)。不妨让\(n\)对......
  • 题解 Codeforces Round 901 (Div. 1) / CF1874A~E
    题解CodeforcesRound901(Div.1)/CF1874A~E比赛情况:过了AB。赛后发现B是假复杂度。https://codeforc.es/contest/1874A.JellyfishandGameProblemAlice&Bob又在博弈,Alice手上有\(n\)个苹果,第\(i\)个苹果的价值是\(a_i\);Bob手上有\(m\)个苹果,第\(i\)......
  • Codeforces Round #885 (Div. 2)
    赛时A题意理解错误,导致A调试半小时没出样例,直接提前下班-->https://codeforces.com/contest/1848A.JellyfishandUndertale题意:初始时长为b的定时炸弹,没秒从n个工具中选一个加时长\(x_i\),每次加时不能超过a,并流失一秒。问:炸弹爆炸前的最长时间是多长?思路:贪心枚举每个工具,每次......
  • Codeforces 1765H 题解
    题目大意题目大意给定一个\(n\)个点和\(m\)条边的有向图,并给定\(p_1,p_2,\cdots,p_n\)表示第\(i\)个点的拓扑序必须小于等于\(p_i\),求出每个点的最小拓扑序。题解题解题目要求拓扑序尽量小,转换一下就是在反图上拓扑序尽量大。考虑拓扑排序,当一个点不得不入队......
  • div 让a内容居中方法
    <div>标签是HTML中的一个重要标签,它代表了一个文档中的一个分割区块或一个部分。在<div>标签中,我们可以放置各种内容,包括文本、图像、链接等等。有时候,我们需要将其中的链接<a>标签的内容水平居中显示,这就需要使用CSS设置div内部链接的居中显示。本文将详细讲解如何使用CSS使得<di......
  • Codeforces Round 901 (Div
    C.JellyfishandGreenApple题解显然\(n\%m=0\),答案一定为\(0\)如果\(n>m\),我们显然可以将\(n/m\)的苹果分给每个人,然后再处理$n%m$如果\(n<m\),我们一定会将所有苹果一直对半切直到\(n>m\),所以答案每次对半切一定会加\(n\)直到\(n\%m=0\)的时......
  • Codeforces Round 895 (Div. 3)
    A题简单的模拟计算,注意上取整的实现。B题计算每个房间对应的每个最迟时间点,在这些时间点最取最小值,保证能安全通过所有房间。D题拿到手就可以发现是贪心,但发现两部分会有冲突,也就是重复计算的部分。故提前找到两个数的lcm然后不计算lcm的倍数,为其他参与计算的数安排剩余数种的最......