首页 > 其他分享 >Codeforces Round 964 (Div. 4)

Codeforces Round 964 (Div. 4)

时间：2024-08-07 13:38:53浏览次数：6  
标签：964 10 ch int ll Codeforces long while Div

比赛链接：Codeforces Round 964 (Div. 4)

A

思路

       水题

代码

#include <iostream>
using namespace std;
#define ll long long

inline int read(void) {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
      ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
      ch = getchar();
  }
  return f * x;
}

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

#include <cstring>
#define ll long long
const int N = 1e5 + 10;

void solve() {
  int n;
  cin >> n;
  cout << n / 10 + n % 10 << endl;
}
int main() {
  int t;
  cin >> t;
  
  while (t--) {
    solve();
  }

  return 0;
}

B

思路

       模拟两个人随机翻开任意一张牌的四种情况。

代码

#include <iostream>
using namespace std;
#define ll long long

inline int read(void) {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
      ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
      ch = getchar();
  }
  return f * x;
}

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

#include <cstring>
#define ll long long
const int N = 1e5 + 10;

void solve() {
  int a[4];
  cin >> a[0] >> a[1] >> a[2] >> a[3];
  

  ll res = 0;

  for (int i = 0;i < 2; i++) {
    for (int j = 2; j < 4; j++) {
      int count = 0;
      if (a[i] > a[j]) {
        count++;
      } else if (a[i] < a[j]) {
        count--;
      }
      if (a[i ^ 1] > a[j ^ 1]) {
        count++;
      } else if (a[i ^ 1] < a[j ^ 1]) {
        count--;
      }
      if (count > 0) {
        res++;
      }
    }
  }
  cout << res << endl;
}
int main() {
  int t;
  cin >> t;
  
  while (t--) {
    solve();
  }
  return 0;
}

C

思路

       将每个忙碌的区间按左端点大小排序，然后逐个遍历每个区间将前i - 1个区间的最大右端点和第i个区间的左端点比较，若第i个区间的左端点大于前i - 1个区间的右端点，则这两个时间点之间就是空闲时间，逐个求出最大的空闲时间和洗澡的时间进行比较。

代码

#include <iostream>
using namespace std;
#define ll long long

#include <algorithm>
#define ll long long
const int N = 2e5 + 10;
 pair<ll, ll>p[N];
void solve() {
  ll n, m, s;
  cin >> n >> s >> m;

 
  for (int i = 1; i <= n; i++) {
    cin >> p[i].first >> p[i].second;
  }

  sort(p + 1, p + 1 + n);

  ll r =  0, res =0;
  for (int i = 1; i <= n; i++) {
    res = max(res, p[i].first - r);
    r = max(r, p[i].second);
  }
  res = max(res, m - r);

  if (res >= s) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}
int main() {
  int t;
  cin >> t;
  
  while (t--) {
    solve();
  }

  return 0;
}

D

思路

       从前往后遍历字符串s并和字符串t匹配，字符串s中遇到问号时，直接赋值为字符串t中的对应的字符，当字符串t匹配完之后，将剩下的字符串s中的问号赋值为任意字符。

代码

#include <iostream>
using namespace std;
#define ll long long

// inline int read(void) {
//   int x = 0, f = 1;
//   char ch = getchar();
//   while (ch < '0' || ch > '9') {
//     if (ch == '-') f = -1;
//       ch = getchar();
//   }
//   while (ch >= '0' && ch <= '9') {
//     x = x * 10 + ch - '0';
//       ch = getchar();
//   }
//   return f * x;
// }

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

#include <algorithm>
#define ll long long
const int N = 2e5 + 10;
 pair<ll, ll>p[N];
void solve() {
  string s, target;
  cin >> s >> target;
  int lens = s.length(), lent = target.length();

  int j = 0, i;
  for (i = 0; i < lent; i++) {
    while (j < lens && s[j] != target[i] && s[j] != '?') {
      j++;
    }
    if (j < lens && s[j] == '?') {
      s[j++] = target[i];
    } else if (i < lent && j >= lens) {
      cout << "NO" << endl;
      return;
    } else {
      j++;
    }
  }
  for (; j < lens; j++) {
    if (s[j] == '?') {
      s[j] = 'a';
    }
  }
  cout << "YES" << endl;
  cout << s << endl;
}
int main() {
  int t;
  cin >> t;
  
  while (t--) {
    solve();
  }
  return 0;
}

E

思路

       将3的幂次数组计算出来，然后在幂次数组num[i]和num[i + 1]之间的数字（不包括num[i + 1]）变成0的操作次数都是i + 1，所以优先将最小的数字变成0，然后选择0和其他数字，将03，其他数字/3，就得到了结果（注意将最小的数字变成0的时候，也有其他数字3）。

代码

#include <iostream>
using namespace std;
#define ll long long

inline ll read(void) {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
      ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
      ch = getchar();
  }
  return f * x;
}

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

#include <cstring>
#define ll long long
const int N = 1e5 + 10;
ll num[N];
void init() {
  num[0] = 1;
  for (int i = 1; i <= 15; i++) {
    num[i] = num[i - 1] * 3;
  }
}
void solve() {
  ll l, r;
  l = read(), r = read();
  ll res = 0;

  int i ;
  for (i = 0; i <= 15; i++) {
    if (num[i] * 3 > l) {
      break;
    }
  }
  res = i + 1;
  for (; num[i] <= r; i++) {
    res += (min(num[i + 1] - 1, r) - max(num[i], l) + 1) * (i + 1);
  }
  cout << res << endl;  
}
int main() {
  int t;
  cin >> t;
  init();
  while (t--) {
    solve();
  }
  return 0;
}

F

思路

       取k个数的中位数，所以将数组排序，然后从第(k + 1) / 2个数字开始枚举到(n - k / 2)个数字，对于每个数字，可以从左边选择k / 2个数字，从右边选择k / 2个数字，所以发现很多数字是重复使用的，所以现预处理出阶乘和阶乘的逆元，因为直接处理c(n, m)数组要开[2e5][2e5]可能会内存超限。

代码

#include <iostream>
using namespace std;
#define ll long long

inline int read(void) {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
      ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
      ch = getchar();
  }
  return f * x;
}

inline void write(ll x) {
  if (x < 0)
    putchar('-'), x = -x;
  if (x > 9)
    write(x / 10);
  putchar(x % 10 + '0');
  return;
}

#include <algorithm>
#define ll long long
const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
ll a[N], num[N], rev[N];

ll qsm(ll x, ll y) {
  ll res = 1;
  while (y) {
    if (y & 1) {
      res *= x;
      res %= mod;
    }
    x *= x;
    y >>= 1;
    x %= mod;
  }
  return res;
}

void init() {
  num[0] = 1;
  for (int i = 1; i <= 200000; i++) {
    num[i] = num[i - 1] * i;
    num[i] %= mod;
  }
  for (int i = 0; i <= 200000; i++) {
    rev[i] = qsm(num[i], mod - 2);
  }
}
void solve() {
  int n, k;
  cin >> n >> k;
  ll res = 0;
  k = k / 2 + 1;

  for (int i = 1; i <= n; i++) {
    a[i] = read();
  }
  sort(a + 1, a + 1 + n);

  for (int i = k; i + k - 1 <= n; i++) {
    res += num[i - 1] * rev[k - 1] % mod * rev[i - k] % mod * a[i] % mod *
           num[n - i] % mod * rev[k - 1] % mod * rev[n - i - k + 1] % mod;
    res %= mod;
  }
  write(res);
  puts("");
}
int main() {
  int t;
  cin >> t;
  init();
  while (t--) {
    solve();
  }
  return 0;
}

G1

思路

       直接使用二分。

代码

#include <iostream>
using namespace std;
#define ll long long

// inline int read(void) {
//   int x = 0, f = 1;
//   char ch = getchar();
//   while (ch < '0' || ch > '9') {
//     if (ch == '-') f = -1;
//       ch = getchar();
//   }
//   while (ch >= '0' && ch <= '9') {
//     x = x * 10 + ch - '0';
//       ch = getchar();
//   }
//   return f * x;
// }

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

#include <algorithm>
#define ll long long
const int N = 2e5 + 10;
void solve() {
  int l = 1, r = 1000, result, num = 10;
  while (num--) {
    int res = 0, mid  = (l + r) / 2;
    cout << "? " << l << " " << mid << endl;
    cin >> res;
    if (res == l * (mid + 1)) {
      r = mid - 1;
      result = mid;
    } else if (res == l * mid) {
      l = mid + 1;
    } else {
      cout << "! " << l << endl;
      return;
    }
  }
  cout << "! " << result << endl;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

G1

思路

       三分

标签：964,10,ch,int,ll,Codeforces,long,while,Div
From： https://www.cnblogs.com/againss/p/18346862

相关文章

  • 题解：Codeforces Round 964 (Div. 4) A
    A.A+BAgain?timelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputGivenatwo-digitpositiveinteger\(n\),findthesumofitsdigits.InputThefirstlinecontainsaninteger\(t\)(\(1......
  • Codeforces Round 964 (Div. 4) 补题记录（A~G2）
    难绷事实：Bwa一发A......#include<bits/stdc++.h>#definepbpush_back#defineintlonglongusingnamespacestd;constintN=500100;inta[N];signedmain(){intT;cin>>T;while(T--){intn;cin>>n;strings=......
  • Codeforces Round 964 (Div. 4)
    CodeforcesRound964(Div.4)A计算数位和。voidsolve(){ inta=0,n; cin>>n; while(n)a+=n%10,n/=10; cout<<a<<'\n';}B模拟，直接枚举4种出牌顺序，按题目给的规则判断即可。boolchk(intx1,inty1,intx2,inty2){ intc1=(x1&g......
  • Codeforces Round 963 (Div. 2)
    第一次上蓝名，指不准哪天掉下来就可以第二次蓝名了，好耶B.ParityandSum(CF1993B)首先特判原数组奇偶性相同的情况，奇偶不同时，由于替换过程只能产生奇数，故目标是将所有偶数变成奇数。假设当前选中奇数\(a_i\)和偶数\(a_j\)，若\(a_i<a_j\)，第一次操作时\(a_i:=a_j+a_i\)，故最多......
  • CodeForces - 765F
    不妨套用P9058的套路，记点对\((i,j),a_i\gea_j\)被支配当且仅当存在\(i<k<j\)，满足\(a_i\gea_k\gea_j\)，同样，猜测对于\(i\)，不被支配的点对\((k,i)\)只满足\(k<i\)最大且\(a_k>a_i\)。证明不妨使用反证法，记\(pre\)，满足\(pre<j<i\)且\(a_{pre},a_j>a_i\)，假设\((p......
  • Codeforces Round 963 (Div. 2)
    A.QuestionMarks题目大意有4n道题，每道题有4个选项，且正确答案中每个选项各占有n个。给定一个字符串s，s中ABCD分别代表4个选项，？代表放弃这道题，求可能的最大正确数解题思路统计每个选项的出现次数，假设每次选的都对，即ans+=min(x,n)点击查看代码#include<bits/stdc++.h>usi......
  • Codeforces Round 963 (Div. 2)
    CodeforcesRound963(Div.2)A对A,B,C,D的数量和\(n\)取个\(\min\)相加B只有奇数或只有偶数答案为\(0\)，否则，只能把所有的偶数改为奇数，因为不可能把所有奇数改为偶数。然后就是改的大小问题了。考虑找到最大的奇数，然后把偶数从小到大依次修改。C显然对\(2k\)......
  • Educational Codeforces Round 168 (Rated for Div. 2)
    没有时间参赛直接补几道简单题吧~B.MakeThreeRegions题意：给一个2行的字符串，有block和其他东西，问把一个位置变成block让联通的部分变成3个部分，有多少种方法思路：找规律，找所哟符合条件的块即可voidsolve(){ intn; cin>>n; array<string,2>s; cin>>s[0]>>s[1];......
  • CodeForces-765F
    首先，如果你写过P9058的话，应该会想到支配点对这个trick,我们不妨将此题的套路搬到这套题上.定义点对\((i,j),a_i\lea_j\)，当\((i,j)\)被支配当且仅当存在\(i<k<j\)满足\(a_i\lea_k\lea_j\)。相应的，一个有效的点对\((i,j)\)，其中\(i\)满足\(i\)最大且\(a_i<a_j\)。......
  • Codeforces Round 963 (Div. 2) A - C 详细题解(思路加代码,C++,Python) -- 来自灰名
    比赛链接:Dashboard-CodeforcesRound963(Div.2)-Codeforces之后有实力了再试试后面的题目，现在要做那些题，起码要理解一个多小时题目A:链接:Problem-A-Codeforces题目大意理解:        极少数不考翻译能读懂的cf题目(bushi)每个测试用例第一行一个n，......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99