首页 > 其他分享 >ABC238 Editorial

ABC238 Editorial

时间：2023-04-27 21:22:58浏览次数：42  
标签：ch putchar int top write ABC238 Editorial define

A - Exponential or Quadratic

题意

给定一个 \(n\)，问 \(2^n>n^2\) 是否成立。

分析

手搓样例，发现只有 \(2,3,4\) 不满足条件，输入输出题。

code

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;

namespace IO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
    inline long long read() {
        char ch = gh();
        long long x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    template <typename _Tp>
    inline void write(_Tp x) {
    	static char stk[64], *top = stk;
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        do *top++ = x % 10, x /= 10;
        while (x);
        while (top != stk) putchar((*--top) | 48);  
    }
}

using IO::read;
using IO::write;

const int maxn(1e6 + 500);

inline void slv () {
	int n = read();
	if (n == 1 || n > 4) puts("Yes");
	else puts("No"); 
}

int main() {
	int T = 1;
	while (T--) slv();
}
// I love WHQ!

B - Pizza

题意

不好描述……

分析

暴力搓出所有切刀的地方，随便算。时间复杂度 \(\mathcal O(n)\)，语法入门题。

code

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;

namespace IO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
    inline long long read() {
        char ch = gh();
        long long x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    template <typename _Tp>
    inline void write(_Tp x) {
    	static char stk[64], *top = stk;
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        do *top++ = x % 10, x /= 10;
        while (x);
        while (top != stk) putchar((*--top) | 48);  
    }
}

using IO::read;
using IO::write;

const int maxn(507), mod(360);
int n, a[maxn], ans;

int main() {
	n = read(), a[0] = 0;
	for (int i = 1; i <= n; i++) a[i] = (a[i - 1] + read()) % mod;
	sort(a, a + n + 1);
	for (int i = 1; i <= n; i++) ans = max(ans, a[i] - a[i - 1]); ans = max(ans, mod - a[n]);
	write(ans);
}
// I love WHQ!

C - digitnum

题意

定义 \(f(x)\) 为十进制下和 \(x\) 位数相同的数的数量，求 \(\sum_{i=1}^nf(i)\bmod 998244353\)。

分析

考虑对于位数为 \(m\) 的 \(f(i)\) 之和为 \(1+2+\dots+9\times 10^{m-1}\)，公式套上 \(O(1)\) 算。所以对于所有位数比 \(n\) 小的数可以直接公式算，对于最后一部分贡献，将 \(m\)，从定义成 \(10^{m-1}\)，贡献就是 \((n-m+2)(n-m+1)\over 2\)。

复杂度 \(\mathcal O(\log_{10}n)\)。

code

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define int long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;

namespace IO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
    inline long long read() {
        char ch = gh();
        long long x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    template <typename _Tp>
    inline void write(_Tp x) {
    	static char stk[64], *top = stk;
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        do *top++ = x % 10, x /= 10;
        while (x);
        while (top != stk) putchar((*--top) | 48);  
    }
}

using IO::read;
using IO::write;

const int mod(998244353);
int n, m = 1, ans;

signed main() {
	n = read();
	while (m * 10 <= n) ans = ((9 * m % mod + 1) * (9 * m % mod) / 2 % mod + ans) % mod, m *= 10;
	ans = (ans + (n % mod - m % mod + 2 + mod) * (n % mod - m % mod + 1 + mod) / 2 % mod) % mod;
	write(ans);
}
// I love WHQ!

D - AND and SUM

题意

给定 \(a,s\)，问是否存在 \(x,y\) 满足：\(x\ \text{AND}\ y=a,a+b=s\)。

分析

首先考虑 \(a\) 中二进制位为 \(1\) 的位置，\(x,y\) 肯定都是 \(1\)，先从 \(s\) 中减掉。对于剩下的部分显然 \(x,y\) 在每一位上最多有一个 \(1\)，所以直接考虑剩下的 \(s\) 是否每个二进制位都对应一个 \(a\) 二进制位为 \(0\) 的位置。

复杂度 \(\mathcal O(T\log n)\)。

code

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;

namespace IO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
    inline long long read() {
        char ch = gh();
        long long x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    template <typename _Tp>
    inline void write(_Tp x) {
    	static char stk[64], *top = stk;
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        do *top++ = x % 10, x /= 10;
        while (x);
        while (top != stk) putchar((*--top) | 48);  
    }
}

using IO::read;
using IO::write;

inline void slv () {
	LL a = read(), s = read(), x = 0;
	for (int i = 0; i < 64; i++) if (a >> i & 1) s -= (1LL << i + 1);
	if (s < 0) return puts("No"), void();
	for (int i = 0; i < 64; i++) if ((s >> i & 1) && (a >> i & 1)) return puts("No"), void();
	puts("Yes");
}

int main() {
	int T = read();
	while (T--) slv();
}
// I love WHQ!

E - Range Sums

题意

假设你知道 \(m\) 个限制 \(\sum_{i=l}^ra_i\) 为某个定值，能否算出 \(\sum_{i=1}^na_i\)？

分析

考虑如果这些限制能完美的无重叠的覆盖 \([1,n]\)，那就直接结束了，写个并查集维护一下，正确性不会证？

复杂度 \(\mathcal O(n)\)。

code

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;

namespace IO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
    inline long long read() {
        char ch = gh();
        long long x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    template <typename _Tp>
    inline void write(_Tp x) {
    	static char stk[64], *top = stk;
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        do *top++ = x % 10, x /= 10;
        while (x);
        while (top != stk) putchar((*--top) | 48);  
    }
}

using IO::read;
using IO::write;

const int maxn(2e5 + 500);
int n, m, fa[maxn];

inline int find (int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
inline void merge (int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return;
	fa[x] = y;
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1, l, r; i <= m; i++) l = read(), r = read(), merge(l - 1, r); 
	puts(find(0) == find(n) ? "Yes" : "No");
}
// I love WHQ!

F - Two Exams

题意

给定 \(n\) 个点，每个点有两个属性 \((a_i,b_i)\)，要求从中选 \(m\) 个点满足不存在 \((x,y)\) 满足 \(x\) 被选中，\(y\) 没被选中，且 \(a_x>a_y,b_x>b_y\)。

分析

考虑排序再算显然不影响正确性，所以先按 \(a\) 排序。考虑能否选一个点 \(i\)，充要条件是前面没被选中的点 \(b\) 属性的最小值 \(mn<b_i\)。

看到数据范围 \(n\leq300\) 就直接上暴力 dp，设 \(f_{i,j,k}\) 表示前 \(i\) 个点，选了 \(j\) 个，其中没被选的 \(b\) 属性最小值为 \(k\)。转移考虑下一个数 \(b_{i+1}\) 与 \(k\) 的关系，很好写。复杂度 \(\mathcal O(n^3)\)。

code

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;

namespace IO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
    inline long long read() {
        char ch = gh();
        long long x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    template <typename _Tp>
    inline void write(_Tp x) {
    	static char stk[64], *top = stk;
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        do *top++ = x % 10, x /= 10;
        while (x);
        while (top != stk) putchar((*--top) | 48);  
    }
}

using IO::read;
using IO::write;

const int maxn(307), mod(998244353);
int n, m, f[maxn][maxn][maxn];
struct Node { int a, b; } p[maxn];

inline void add (int &x, const int &y) { x += y; x > mod && (x -= mod); }

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i++) p[i].a = read();
	for (int i = 1; i <= n; i++) p[i].b = read();
	sort(p + 1, p + n + 1, [](const Node &x, const Node &y) { return x.a < y.a; });
	f[0][0][n + 1] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			for (int k = 1; k <= n + 1; k++) {
				if (p[i + 1].b == k || !f[i][j][k]) continue;
				if (p[i + 1].b > k) add(f[i + 1][j][k], f[i][j][k]);
				else add(f[i + 1][j][p[i + 1].b], f[i][j][k]), add(f[i + 1][j + 1][k], f[i][j][k]);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n + 1; i++) add(ans, f[n][m][i]);
	write(ans);
}
// I love WHQ!

G - Cubic?

题意

给定序列 \(\{a_n\}\)，\(m\) 次询问：\(\prod_{i=l}^ra_i\) 是否是一个完全立方数。

分析

这相当于对于每一个质因数，\([l,r]\) 范围内出现的次数均为 \(3\) 的倍数。直接做的复杂度相当高。考虑优化一下，每个数之多只有一个 大于 \(\sqrt(a_i)\) 的因子，然而小于 \(1000\) 的因子数量仅有 \(168\) 个，于是这部分可以直接前缀和一下，在暴力判断。对于大于 \(1000\) 的因子，显然的想法是莫队，动态维护非 \(3\) 倍数的数量。复杂度 \(\mathcal O(n(k+\sqrt n))\)，其中 \(k=168\)。

code

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#define LL long long
#define writesp(x) write(x), putchar(' ')
#define writeln(x) write(x), putchar('\n')
#define FileIO(ch) freopen(ch".in", "r", stdin), freopen(ch".out", "w", stdout)
using namespace std;

namespace IO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
    inline long long read() {
        char ch = gh();
        long long x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    template <typename _Tp>
    inline void write(_Tp x) {
    	static char stk[64], *top = stk;
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        do *top++ = x % 10, x /= 10;
        while (x);
        while (top != stk) putchar((*--top) | 48);  
    }
}

using IO::read;
using IO::write;

const int maxn(2e5 + 500), maxk(1e6 + 500), maxp(180);
int n, m, sqn, a[maxn], pr[maxp], tot, cnt[maxn][maxp], ct[maxk], now;
bool vis[maxn], ans[maxn];

struct Node {
	int l, r, id;
	inline bool operator < (const Node &rhs) const {
		return (l / sqn == rhs.l / sqn) ?  (l / sqn & 1 ? r < rhs.r : r > rhs.r) : l < rhs.l;
	}
} q[maxn];

inline void seive (int N) {
	for (int i = 2; i <= N; i++) {
		if (!vis[i]) pr[++tot] = i;
		for (int j = 1; j <= tot && i * pr[j] <= N; j++) {
			vis[i * pr[j]] = 1;
			if (i % pr[j] == 0) break;
		}
	}
}

inline void add (int x) {
	if (x == 1) return;
	ct[x] = (ct[x] + 1) % 3;
	if (ct[x] == 1) now--;
	else if (ct[x] == 0) now++;
}
inline void del (int x) {
	if (x == 1) return;
	ct[x] = (ct[x] + 2) % 3;
	if (ct[x] == 2) now--;
	else if (ct[x] == 0) now++;
}

int main() {
	seive(1000);
	n = read(), m = read(), sqn = sqrt(n);
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= tot; j++) {
			cnt[i][j] = cnt[i - 1][j];
			if (a[i] % pr[j]) continue;
			int c = 0; while (a[i] % pr[j] == 0) a[i] /= pr[j], ++c;
			cnt[i][j] = (cnt[i][j] + c) % 3;
		}
	}
	for (int i = 1; i <= m; i++) q[i] = {read(), read(), i}, ans[i] = 1;
	sort(q + 1, q + m + 1);
	for (int i = 1, l = 1, r = 0; i <= m; i++) {
		while (l > q[i].l) add(a[--l]);
		while (r < q[i].r) add(a[++r]);
		while (l < q[i].l) del(a[l++]);
		while (r > q[i].r) del(a[r--]);
		if (now) ans[q[i].id] = 0;
		for (int j = 1; j <= tot && ans[q[i].id]; j++) if (cnt[q[i].r][j] != cnt[q[i].l - 1][j]) ans[q[i].id] = 0;
	}
	for (int i = 1; i <= m; i++) puts(ans[i] ? "Yes" : "No");
}
// I love WHQ!

Ex - Removing People

题意

没读懂啊！！！

分析

蒟蒻不会啊！！！

code

还没写呢……

标签：ch,putchar,int,top,write,ABC238,Editorial,define
From： https://www.cnblogs.com/BingAD/p/17360237.html

相关文章

  • [ABC238G] Cubic?
    ProblemStatementGivenasequence$A$of$N$numbers,answerthefollowing$Q$questions.Inthe$i$-thquestion,youaregivenintegers$L_i$and$R_i$.Is......
  • 「Editorial」Codeforces Contest 1149
    C.TreeGenerator™容易发现树上一条路径一定形如))...)((...(。也就是对于任意子段，去掉匹配了的括号后还剩下的部分。而这个东西还是不太好表示，我们有如下引理：这个值......
  • [Editorial] 2022 CCPC Guangzhou Onsite
    2022CCPCGuangzhouOnsite大概按题目难度顺序排序。这篇题解可能没那么口胡。GYM104053EElevator相当于每个电梯在\(-x_i\)，每次可以把最大的，编号最小的值减一，要求......
  • ABC238G
    ABC238G题目大意：给出序列\(\{a_i\}\)，每次询问给出一个区间\([l,r]\)，查询\(\prod_{i=l}^ra_i\)是否是立方数。根号分治，\(\sqrtn\)内的质因子直接分解出来前缀......
  • [Editorial] Codeforces Contest 878D
    中文题面好题，写篇题解记录一下。首先如果值域是\(\{0,1\}\)，那么直接搞一个bitset维护一下。由于只有\(2^k\)中不同的初始取值，所以维护\(2^k\)长度即可。然后考虑值......
  • editorial 专栏
    社论22.10.1社论22.10.2社论22.10.4社论22.10.7社论22.10.9......
  • [Travels & Editorial] NOI Online 2020 第二场
    游记DAY0因为这次不评奖也不干啥的所以也就没准备什么，颓了一天。DAY1其实也就一天上午8:00起床，吃个早饭就准备开始比赛了。这次登陆得很顺利，没怎么卡。先开T1，范围......
  • [Editorial] Codeforces Contest 1726
    A.MainakandArray显然如果\([l,r]\)不包括两端那么就不会对答案有影响，那么直接枚举包括两端的情况即可。/*author:Geminidate:September6th,2022url:htt......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99