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

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

时间：2023-10-01 16:11:36浏览次数：62  
标签：xor0 return 895 int 题解 ll Div now scanf

A. Two Vessels

Problem

题目

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, a, b, c;

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d %d", &a, &b, &c);
    double res = std::abs(b - a) / 2.0;
    printf("%d\n", (int)std::ceil(res / c));
  }
  return 0;
}

B. The Corridor or There and Back Again

Problem

题目

Sol & Code

对于每个陷阱（不考虑其他陷阱）求最多能平安到达的位置，最后对每个陷阱取最小值。

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

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, a[N];

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; ++i) {
      scanf("%d %d", &x, &y);
      a[i] = x + (int)std::floor((y - 1) / 2.0);
    }
    int ans = 114514;
    for (int i = n; i >= 1; --i) ans = min(ans, a[i]);
    printf("%d\n", ans);
  }
  return 0;
}

C. Non-coprime Split

Problem

题目

Sol & Code

考虑 \([l,r]\) 这个区间的长度。若长度为 \(2\)，\(l,r\) 一奇一偶，讨论可知 \([1,2],[2,3]\) 无解，其他情况答案可为将 \(l,r\) 中偶数分为两半。
若长度为 \(3\)，讨论可知 \([1,3]\) 无解，有解的情况答案容易得出不再详细说。长度大于 \(3\) 肯定有解，答案也容易得出。若长度为 \(1\)，考虑是 \(a+b =l\) 的情况，若 \(gcd(a,b) = 1\) 说明\(a,b\) 无公共质因数，可以根据算数基本定理可知不存在整除 \(l\) 且小于 \(l\) 的质数故 \(l\) 为质数，有解的情况即 \(l\) 不为质数，找个公共的质因子 \(p\)，令 \(a = p,b = l - p\) 即可。

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

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; }

bool vis[N];
int T, l, r, cnt, pri[N];

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

void getprime() {
  for (int i = 2; i < N; ++i) {
    if (!vis[i]) pri[++cnt] = i;
    for (int j = 1; j <= cnt; ++j) {
      if (1ll * i * pri[j] >= N) break;
      vis[i * pri[j]] = true;
      if (i % pri[j] == 0) break;
    }
  }
}

int main() {
  scanf("%d", &T);
  getprime();
  while (T--) {
    scanf("%d %d", &l, &r);
    if (r - l + 1 == 3) {
      if (l == 1) puts("-1");
      else {
        if (l & 1) printf("%d %d\n", (l + 1) / 2, (l + 1) / 2);
        else printf("%d %d\n", (l + 2) / 2, (l + 2) / 2);
      }
    } else if (r - l + 1 == 2) {
      if (l == 1 || l == 2) puts("-1");
      else {
        if (l & 1) printf("%d %d\n", (l + 1) / 2, (l + 1) / 2);
        else printf("%d %d\n", l / 2, l / 2);
      }
    } else if (l == r) {
      if (l & 1) {
        if (vis[l]) {
          int prt = 0;
          for (int i = 1; i <= cnt; ++i) {
            if (l % pri[i] == 0) {
              if ((l / pri[i]) & 1) { prt = pri[i]; break; }
            }
          }
          if (!prt) puts("-1");
          else printf("%d %d\n", prt, l - prt);
        } else puts("-1");
      } else {
        if (l != 2) printf("%d %d\n", l / 2, l / 2);
        else puts("-1");
      }
    } else {
      if (r & 1) printf("%d %d\n", (r - 1) / 2, (r - 1) / 2);
      else printf("%d %d\n", r / 2, r / 2);
    }
  }
  return 0;
}

D. Plus Minus Permutation

Problem

题目

Sol & Code

根据题意可知 \(x\) 的贡献有 \(\lfloor \dfrac{n}{x}\rfloor\) 个数记作 \(a\)，\(y\) 的贡献有 \(\lfloor \dfrac{n}{x}\rfloor\) 个数记作 \(b\)，其中两者共同的贡献有 \(\lfloor \dfrac{n}{\lcm(x,y)}\rfloor\)（其中 \(\lcm(x,y)\) 为 \(x,y\) 的最小公倍数）个数记作 \(c\)。

所以答案为 \(n + (n - 1) + \dots + [n - (a - c) + 1] - [1 + 2 + \dots + (b - c)]\)。

#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;
ll n, x, y;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } 
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%lld %lld %lld", &n, &x, &y);
    ll num1 = n / x - n / lcm(x, y), num2 = n / y - n / lcm(x, y);
    printf("%lld\n", (n + n - num1 + 1) * num1 / 2 - (1 + num2) * num2 / 2);
  }
  return 0;
}

E. Data Structures Fan

Problem

题目

Sol & Code

线段树可做

#include <bits/stdc++.h>
#define N 100001
#define lson now << 1
#define rson now << 1 | 1 

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; }

std::string s;
int T, n, q, w[N];
struct Node {
  int l, r, xor0, xor1, lazy;
}t[N << 2];

void build(int l, int r, int now) {
  t[now].l = l, t[now].r = r, t[now].xor0 = 0, t[now].xor1 = 0, t[now].lazy = 0;
  if (l == r) {
    if (s[l - 1] == '0') t[now].xor0 = w[l];
    else t[now].xor1 = w[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, lson), build(mid + 1, r, rson);
  t[now].xor0 = t[lson].xor0 ^ t[rson].xor0;
  t[now].xor1 = t[lson].xor1 ^ t[rson].xor1;
}

void pushdown(int now) {
  if (t[now].l == t[now].r) return;
  t[lson].lazy ^= 1, t[rson].lazy ^= 1;
  int tmp1 = t[lson].xor0, tmp2 = t[rson].xor0;
  t[lson].xor0 = t[lson].xor1, t[lson].xor1 = tmp1;
  t[rson].xor0 = t[rson].xor1, t[rson].xor1 = tmp2;
  t[now].lazy = 0;
}

void fix(int x, int y, int now) {
  if (t[now].l >= x && t[now].r <= y) {
    t[now].lazy ^= 1;
    int tmp = t[now].xor0;
    t[now].xor0 = t[now].xor1;
    t[now].xor1 = tmp;
    return ;
  }
  if (t[now].lazy) pushdown(now);
  int mid = (t[now].l + t[now].r) >> 1;
  if (x <= mid) fix(x, y, lson);
  if (y > mid) fix(x, y, rson);
  t[now].xor0 = t[lson].xor0 ^ t[rson].xor0;
  t[now].xor1 = t[lson].xor1 ^ t[rson].xor1;
}

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    std::cin >> s;
    build(1, n, 1);
    scanf("%d", &q);
    for (int i = 1, opt, x, y; i <= q; ++i) {
      scanf("%d %d", &opt, &x);
      if (opt == 1) {
        scanf("%d", &y);
        fix(x, y, 1);
      } else printf("%d ", x ? t[1].xor1 : t[1].xor0);
    }
    puts("");
  }
  return 0;
}

总结

C. 分类讨论好像复杂了。

E. 现在是只会暴力数据结构的 fw 了（甚至数据结构都不会），异或前缀和。

标签：xor0,return,895,int,题解,ll,Div,now,scanf
From： https://www.cnblogs.com/poi-bolg-poi/p/17738939.html

相关文章

  • AT_abc254_h [ABC254Ex] Multiply or Divide by 2 题解
    打篇题解巩固一下。题意给你两个集合\(A\)和\(B\)，对于任意\(A\)集合中的元素，我们可以进行\(2\)种操作：\(a_i\gets\left\lfloor\frac{a_i}{2}\right\rfloor\)或\(a_i\gets2\timesa_i\)。问最少要多少次才能使\(A\)和\(B\)中的元素相等。分析首先我们可以令\(a......
  • UVA12655 Trucks 题解
    题目传送门前言中文题目可以看link。前置知识Kruskal重构树|最近公共祖先简化题意给定一个\(N\)个点\(M\)条边的有向图，共有\(S\)次询问，每次询问从\(L\)到\(H\)所有的路径中最小的权值的最大值（多组数据）。本题即最大瓶颈路问题。解法使最小的权值最大，不难......
  • 【洛谷 P1305】新二叉树 题解（结构体数组+先序遍历+二叉树）
    新二叉树题目描述输入一串二叉树，输出其前序遍历。输入格式第一行为二叉树的节点数。()后面行，每一个字母为节点，后两个字母分别为其左右儿子。特别地，数据保证第一行读入的节点必为根节点。空节点用*表示输出格式二叉树的前序遍历。样例#1样例输入#16abcbdicj*d**i**j**......
  • SP16113 SUBTLEBA - Trucks Transportation 题解
    题目传送门前言本题样例有问题，如果想要样例可以去vjudge上。本题提交后可能会出现UKE，建议前往link提交，而且本篇题解中所提供的代码也为link代码。前置知识Kruskal重构树|最近公共祖先简化题意给定一个\(N\)个点\(M\)条边的有向图，共有\(S\)次询问，每次询问......
  • Codeforces Round 901 (Div. 2)
    CodeforcesRound901(Div.2)A-JellyfishandUndertale解题思路:卡在最后秒放。若\(x_i>(a-1)\):那么该\(x_i\)的贡献为\(a-1\)。否则，该\(x_i\)的贡献为\(x_i\)。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;typedefpair<int,in......
  • 901DIV2 (A~D)
    901DIV2A~DA:大于等于\(a-1\)的贡献都是a-1.voidsolve(){intans=0;inta,b,n;cin>>a>>b>>n;ans+=b;for(inti=1;i<=n;i++){intx;cin>>x;if(x>=a)x=a-1;ans+=x;}cout<<......
  • 题解 CF1875D【Jellyfish and Mex】
    显然，除非\(\operatorname{mex}a=0\)，否则不会删除\(>\operatorname{mex}a\)的数。而\(\operatorname{mex}a=0\)时不对答案产生贡献，因此任意时刻我们都可以忽略\(a\)中\(>\operatorname{mex}a\)的数。又显然，一旦我们开始删一个数，就会先把所有与之相等的数删光。否则，设最先......
  • Educational Codeforces Round 155 (Rated for Div
    B.ChipsontheBoard题解：贪心显然我们可以把题意转化为：对于任意一个\((i,j)\)，我们可以花费\(a_{i,j}\)的代价占据第\(i\)行和第\(j\)列，求占据所有格子的最小代价考虑两种情况：在每一行选一个格子在每一列选一个格子贪心选即可intn,a[N],b[N];voidsolve......
  • Codeforces Round 898 (Div. 4)
    由于题目补完才来写总结，导致前面的有的题目都需要重新再看一遍，只好当作复习了。但考虑到趁热打铁，先看H.H题：从小白视角来看乍一看是博弈论，仔细思考以后发现是图论。本题给的是基环树，意识到这一点很重要，这个条件是让本题不是很复杂的关键。n个点n条边且没有重边保证这个联通图中......
  • counting题解
    \(N,M\le1e7\)接着反射容斥，考虑这道题怎么做如果去枚举不动步数，加上反射容斥，直接T飞了把-1/0/1操作转换一下，就成了0/1/2如果没有限制（不能<0或>m），n步方案就是\((1+x+x^2)^n\)设\(H=1+x+x^2\quadF=H^n\)那么对两边求导：\[nH^{n-1}H'=F'\]\[F'H=nFH'\]我们知道\[H=1+x+x^2......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99