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
还没写呢……