『XYGOI round1』三个数
题目描述
MX 有一个有 \((w-2)\) 个数的集合 \(S=\{3,4,5,\cdots ,w\}\)。要求构造一个只包含非负整数的集合（无重复元素），使得 \(S\) 里面的任何一个数都能被这个集合里面大于等于 \(3\) 个不同的数相加得到，求这个集合中至少包含多少个元素。
输入格式
本题包含多组测试数据。
第一行输入一个整数 \(T\)，表示数据组数。
接下来 \(T\) 行每行输入一个整数 \(w\)。
输出格式
共 \(T\) 行，每行输出一个整数 \(n\)，表示集合至少应该含有的元素个数。
样例 #1
样例输入 #1
1
4
样例输出 #1
4
样例 #2
样例输入 #2
5
3
18
999
9999
9999999999
样例输出 #2
3
6
12
15
35
提示
样例 1 说明：
集合元素可以为 \(0,1,2,3\)。
数据范围：
本题采用捆绑测试。
对于所有数据，保证 \(1\le T \le 10^5\)，\(3\le w \le 10^{12}\)。
| Subtask | \(T\) | \(w\) | 分值 |
|---|---|---|---|
| 0 | \(=1\) | \(w\le 10\) | 5 |
| 1 | \(1\le T\le 10^3\) | \(w\le 20\) | 10 |
| 2 | \(1\le T\le 50\) | \(w\le 10^{3}\) | 25 |
| 3 | \(1\le T\le 10^3\) | \(w\le 10^{5}\) | 30 |
| 4 | \(1\le T\le 10^5\) | \(3\le w\le 10^{12}\) | 30 |
可以打表找规律。
打表
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
int maxx;
bool g[200];
vector<int> ans, tmp;
void dfs(int u, int limt, int sum, int num, int tnum) {
if (sum > limt || u > limt) {
return ;
}
if (sum == limt && num < maxx && num + tnum >= 3) {
ans.clear();
ans = tmp;
maxx = num;
return ;
}
if (sum == limt && num == maxx && num + tnum >= 3) {
if (ans.empty() || (!tmp.empty() && tmp.back() > ans.back())) {
ans.clear();
ans = tmp;
maxx = num;
}
return ;
}
sum += u;
if (!g[u]) {
++ num;
tmp.emplace_back(u);
}
else {
++ tnum;
}
dfs(u + 1, limt, sum, num, tnum);
sum -= u;
if (!g[u]) {
-- num;
tmp.pop_back();
}
else {
-- tnum;
}
dfs(u + 1, limt, sum, num, tnum);
}
int main() {
int n;
cin >> n;
for (int i = 3; i <= n; ++ i) {
maxx = 1e9;
ans.clear(), tmp.clear();
dfs(0, i, 0, 0, 0);
for (int j : ans) {
g[j] = 1;
// cout << j << ' ';
}
// putchar('\n');
int cnt = 0;
for (int j = 0; j <= n; ++ j) {
if (g[j] == 1) {
++ cnt;
}
}
cout << i << ": " << cnt << '\n';
}
// n -= 1;
// ll ans = 3 + (n / 3);
// cout << ans << '\n';
return 0;
}
发现答案的覆盖范围是 \(3\) 的整数倍。
100ts
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
void work() {
ll n = read<ll>();
if (n == 3) {
puts("3");
}
else {
ll sum = 3, jump = 3;
int ans = 3;
while (sum < n) {
sum += jump;
jump <<= 1;
++ ans;
}
cout << ans << '\n';
}
}
int main() {
int T;
T = read<int>();
while (T --) {
work();
}
return 0;
}
『XYGOI round1』一些数
题目背景
MX 在研究排列所具有的性质。这一天，她拿出了 \(n\) 张卡片排成一排，想要在上面填数以写成一个 \(1\sim n\) 的排列。
Piggy 趁 MX 不注意，偷偷在一些卡片上写了数。
题目描述
MX 很快发现了这一切。不过她并不生气，而是考虑一个有趣的问题：如果我在上面填一些数，让它依然构成一个排列，且它的最长上升子序列长度为 \(n-1\)，MX 有多少种填数方法呢？
Piggy 比较良心。他没有在不同的位置上填相同的数。
输入格式
本题有多组测试数据。
第一行一个整数 \(T\) 代表数据组数。
对于每组数据：
- 第一行两个整数 \(n,q\) 代表卡牌个数和 Piggy 已经填上了多少个数。
- 第二行 \(2q\) 个整数，第 \(2i-1,2i\) 个整数 \((x,y)\) 代表第 \(x\) 个数被 Piggy 填成了 \(y\)。
输出格式
输出 \(T\) 行，每行一个整数代表答案。
样例 #1
样例输入 #1
2
10 4
2 2 4 8 6 5 7 6
2 0
样例输出 #1
1
1
样例 #2
样例输入 #2
2
40 21
1 1 2 2 6 6 7 7 8 8 9 9 10 10 11 11 15 15 16 16 23 23 24 24 25 25 26 26 30 30 34 35 35 36 36 37 37 38 38 39 40 40
40 15
3 3 4 4 14 14 15 15 17 17 19 19 24 23 25 24 27 26 30 29 31 30 33 32 35 34 39 38 40 39
样例输出 #2
4
4
提示
样例解释
用 \(-1\) 代表此位置数字还未确定。
样例 \(1\)：第一组给定的排列为 \(-1,2,-1,8,-1,5,6,-1,-1,-1\)。容易发现，只有 \(1,2,3,8,4,5,6,7,9,10\) 的最长上升子序列长度为 \(10-1=9\)。第二组给定的排列为 \(-1,-1\)，\(2,1\) 为唯一满足要求的序列。
本题采用捆绑测试。
| Subtask | \(\sum n\) | \(\sum q\) | 分值 |
|---|---|---|---|
| 0 | \(\le 10\) | \(\le 10\) | 10 |
| 1 | \(\le 15\) | \(\le 10\) | 20 |
| 2 | \(\le 5\times 10^3\) | \(\le 5\times 10^3\) | 30 |
| 3 | \(\le 5\times 10^5\) | \(\le 5\times 10^5\) | 40 |
保证 $ 0\le q\le n$，\(1\le n\le 5\times 10^5\)，\(1\le T\le 10^5\)，\(1 \le x,y \le n\)。
30pts
dfs 搜索即可拿到 \(30\) 分。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 5e5 + 5;
int T, n, ans, cnt;
int card[N];
bool use[N], tak[N];
vector<int> dp;
void check() {
dp.clear();
for (int i = 1; i <= n; ++ i) {
if (dp.empty() || card[i] > dp.back()) {
dp.emplace_back(card[i]);
}
else {
int j = lower_bound(dp.begin(), dp.end(), card[i]) - dp.begin();
dp[j] = card[i];
}
}
if ((int)dp.size() == n - 1) {
++ ans;
}
}
void dfs(int u, int fg) {
if (u == n + 1) {
check();
return ;
}
if (tak[u]) {
if (card[u] > u) fg = 1;
dfs(u + 1, fg);
return ;
}
for (int i = 1; i <= n; ++ i) {
if (use[i]) continue;
card[u] = i;
use[i] = 1;
if (i > u) {
dfs(u + 1, 1);
}
else {
dfs(u + 1, 0);
}
use[i] = 0;
card[u] = 0;
}
}
void work() {
n = read<int>();
int q = read<int>();
for (int i = 1; i <= n; ++ i) {
card[i] = tak[i] = use[i] = 0;
}
for (int i = 1, p, g; i <= q; ++ i) {
p = read<int>(), g = read<int>();
card[p] = g;
tak[p] = 1;
use[g] = 1;
}
ans = 0;
dfs(1, 0);
cout << ans << '\n';
}
int main() {
T = read<int>();
while (T --) {
work();
}
return 0;
}
100pts
恶心的大分讨！
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 5e5 + 5;
int T, n, cnt, l, r;
ll ans;
int card[N];
void solve1() {
int l = 0;
ll ans = 0;
for (int i = 1; i <= n; ++ i) {
if (!card[i]) {
++ l;
}
else if (l) {
ans = ans + pow(l - 1, 2);
l = 0;
}
}
if (l) ans = ans + pow(l - 1, 2);
printf("%lld\n", ans);
}
bool check() {
int fg = 0;
for (int i = 1; i <= n; ++ i) {
if (!card[i]) continue;
if (abs(card[i] - i) >= 2) {
if (!fg) fg = i;
else return false;
}
}
if (fg) {
int val = card[fg];
if (val > fg) {
int l = fg, r = val;
for (int i = 1; i <= n; ++ i) {
if (!card[i]) continue;
if ((i < l || i > r) && card[i] != i) return false;
if ((i > l && i <= r) && card[i] != i - 1) return false;
}
}
else {
int l = val, r = fg;
for (int i = 1; i <= n; ++ i) {
if (!card[i]) continue;
if ((i < l || i > r) && card[i] != i) return false;
if ((i >= l && i < r) && card[i] != i + 1) return false;
}
}
return true;
}
else {
bool ok = 0;
for (int i = 1; i <= n; ++ i) {
if (card[i] == 0 || card[i] == i) continue ;
if (card[i] == i + 1 && card[i + 1] == i && !ok) {
ok = 1;
++ i;
}
else {
return false ;
}
}
if (ok) return true ;
else return false ;
}
}
void deal(int x) {
int lcnt = 0, rcnt = 0;
for (int i = l - 1; i && !card[i]; -- i) lcnt++;
for (int i = r + 1; i <= n && !card[i]; ++ i) rcnt++;
ans = 1ll * lcnt * rcnt;
if (x == 1) {
ans += rcnt;
}
else if (x == -1) {
ans += lcnt;
}
}
void solve2() {
int fg = 0, dif = 0;
l = r = 0;
for (int i = 1; i <= n; ++ i) {
if (card[i] == 0) continue ;
if (card[i] == i) {
if (fg == 1) {
fg = 2;
}
}
else {
r = i;
if (!fg) {
fg = 1;
l = i;
dif = card[i] - i;
}
else {
if (fg != 1 || (fg == 1 && card[i] - i != dif)) return ;
}
}
}
deal(dif);
return ;
}
void work() {
n = read<int>();
int q = read<int>();
for (int i = 1; i <= n; ++ i) {
card[i] = 0;
}
bool fg1 = 1;
for (int i = 1, p, g; i <= q; ++ i) {
p = read<int>(), g = read<int>();
card[p] = g;
if (p != g) {
fg1 = 0;
}
}
if (fg1) {
solve1();
return ;
}
if (check()) {
puts("1");
return ;
}
ans = 0;
solve2();
printf("%lld\n", ans);
return ;
}
int main() {
T = read<int>();
while (T --) {
work();
}
return 0;
}
『XYGOI round1』一棵树
题目背景
java 今天带了一棵树到出题组，然后被不讲理的 MX 占为己有了。
题目描述
于是 MX 有一棵 \(n\) 个节点的树，每个点上有一个数字 \(a_i\)。
定义一条路径 \((x,y)\) 的权值 \(w(x,y)\) 为，从 \(x\) 走到 \(y\) 的最短路径上，所有节点上的数字顺次写下后得到的数。如，顺次经过写有数字 \(3,21,0,5\) 的四个节点，那么这个路径的权值为 \(32105\)。
MX 想知道这棵树所有路径的权值之和，即 \(\sum\limits_{x=1}^n\sum\limits_{y=1}^nw(x,y)\) 为多少。
答案可能很大，对 \(998244353\) 取模。
输入格式
第一行一个正整数 \(n\)。
第二行 \(n\) 个非负整数 \(a_i\)。
第三行 \(n-1\) 个正整数，第 \(i\) 个数 \(p_i\) 表示节点 \(p_i\) 与节点 \(i+1\) 之间有边。保证 \(1\le p_i\le i\)。
输出格式
一行一个整数，表示答案。答案对 \(998244353\) 取模。
样例 #1
样例输入 #1
3
1 2 3
1 2
样例输出 #1
538
样例 #2
样例输入 #2
3
5 21 0
1 2
样例输出 #2
6418
样例 #3
样例输入 #3
4
1 2 3 4
1 2 2
样例输出 #3
1900
样例 #4
样例输入 #4
6
10 23 16 3 125 1
1 1 1 1 1
样例输出 #4
7680868
提示
样例解释
样例一解释：\(1+12+123+2+21+23+3+32+321=538\)。
样例二解释：\(5+521+5210+21+215+210+0+021+0215=6418\)。
数据范围
本题采用捆绑测试。
记 \(V=\max\{a_i\}+1\)。
| Subtask | 分值 | \(n\le\) | $V\le $ | 特殊性质 |
|---|---|---|---|---|
| 0 | 5 | \(1000\) | \(10\) | |
| 1 | 15 | \(8000\) | \(10^9\) | |
| 2 | 15 | \(10^6\) | \(10^9\) | \(p_i=i\) |
| 3 | 15 | \(10^6\) | \(10^9\) | \(p_i=1\) |
| 4 | 50 | \(10^6\) | \(10^9\) |
对于 \(100\%\) 的数据，\(1\le n\le 10^6\)，\(0\le a_i<10^9\)。
5pts
暴力
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 1e6 + 5;
const int mod = 998244353;
int n;
bool jh = 1;
ll ans;
ll a[N];
vector<int> e[N];
void dfs(int u, int fat, ll w) {
for (int v : e[u]) {
if (v == fat) continue ;
ll res = w, tmp = a[v];
int sw = 0;
while (tmp) {
tmp /= 10;
++ sw;
}
tmp = a[v];
if (a[v] == 0) {
res *= 10;
}
while (sw) {
res *= 10;
res += tmp / pow(10, sw - 1);
tmp %= (ll)pow(10, sw - 1);
-- sw;
}
ans = (ans + res) % mod;
dfs(v, u, res);
}
}
int main() {
n = read<int>();
for (int i = 1; i <= n; ++ i) {
a[i] = read<ll>();
}
for (int i = 1, p; i < n; ++ i) {
p = read<int>();
e[p].emplace_back(i + 1);
e[i + 1].emplace_back(p);
if (p != 1) {
jh = 0;
}
}
for (int i = 1; i <= n; ++ i) {
ans += a[i];
dfs(i, 0, a[i]);
}
cout << ans << '\n';
return 0;
}
35pts
面向特殊性质 “链”、“菊花图”。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 3e6 + 7;
const int mod = 998244353;
int k[N], a[N], n;
int dep[N], siz[N], tmpsiz, tmp, sum, rot, ans;
int to[N], hd[N], nxt[N], cnt;
int ksm(int a, int k) {
int ans = 1;
while (k) {
if (k & 1) ans = ans * a %mod;
a = a * a %mod; k >>= 1;
}
return ans;
}
void sol_chain() {
tmp = 0; ans = 0;
for (int i = 1; i <= n; i ++ ) {
tmp = ((tmp * ksm(10, k[i]) %mod) + (a[i] * i %mod)) %mod;
ans = (ans + tmp) %mod;
}
tmp = 0;
for (int i = n; i >= 1; i -- ) {
tmp = ((tmp * ksm(10, k[i]) %mod)+ (a[i] * (n - i + 1) %mod)) %mod;
ans = (ans + tmp) %mod;
}
for (int i = 1; i <= n; i ++ ) ans = ((ans - a[i]) %mod + mod) %mod;
cout << ans << '\n';
return ;
}
void sol_star() {
sum = 0; ans = 0;
for (int i = 1; i <= n; i ++ ) {
ans = (ans + (a[i] * n %mod)) %mod;
}
for (int i = 2; i <= n; i ++ ) {
ans = (ans + (ksm(10, k[1]) * a[i] %mod)) %mod;
ans = (ans + ((ksm(10, k[i]) * a[1] %mod) * (n - 1) %mod) ) %mod;
sum = (sum + ksm(10, k[i] + k[1])) %mod;
}
for (int i = 2; i <= n; i ++ ) {
tmp = ((sum - ksm(10, k[i] + k[1])) %mod + mod) %mod;
ans = (ans + (tmp * a[i] %mod)) %mod;
}
cout << ans << '\n';
return ;
}
void init(int u, int fa) {
siz[u] = 1;
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if (v == fa) continue;
init(v, u);
siz[u] += siz[v];
}
}
void dfs(int u,int fa) {
for (int i = hd[u]; i; i = nxt[i]) {
int v = to[i];
if (v == fa) continue;
dep[v] = dep[u] + k[v];
if (u == rot) tmpsiz = n - siz[v];
ans += (a[rot] * ksm(10, dep[v]) %mod) * tmpsiz %mod;
dfs(v, u);
}
}
void sol_tree() {
for (int i = 1; i <= n; i ++ ){
dep[rot = i] = 0;
init(i,0); dfs(i, 0);
}
for (int i = 1; i <= n; i ++) ans = (ans + a[i] * n %mod) %mod;
cout << ans << '\n';
}
void addedge(int u, int v) {
to[++ cnt] = v;
nxt[cnt] = hd[u];
hd[u] = cnt;
}
int main() {
n = read<int>();
for (int i = 1, tmp; i <= n; i ++ ) {
tmp = a[i] = read<int>();
if (!tmp) k[i] = 1;
while (tmp) {
k[i] ++; tmp /= 10;
}
}
for (int u = 2, v; u <= n; u ++ ) {
v = read<int>();
addedge(u, v); addedge(v, u);
}
return 0;
}
『XYGOI round1』好多数
题目背景
小 X 在和小 L 一起玩。他们走到了公园，发现了一棵长得很奇怪的参天大树。这棵树，按照 OIer 们的习惯，它有一个明显特征，那就是严重右偏。
题目描述
小 X 想到了另外一个东西，也是严重右偏的。
首先，他写下一个数字 \(n\)。
接着，对于所有 \(n\) 的因数 \(x\notin\{1,n\}\)，让 \(x\) 从小到大的成为 \(n\) 的儿子节点。
递归的建这棵树，这棵树就建成了。小 X 把这棵树称为一个“\(n\) 号数学树”。小 X 想知道，给定 \(q\) 个正整数 \(x\)，它在 \(n\) 号数学树出现了几次。
因为 \(n\) 很大，他只能告诉你 \(n\) 的质因数分解。
答案对 \(998244353\) 取模。
输入格式
第一行若干对整数 \((a_i,b_i)\)，表示 \(n=\prod a_i^{b_i}\)，以 0 0 结尾。题目保证，\(a_i\) 是质数，\(b_i\in N^*\)。
第二行一个整数，表示 \(q\)，含义如题面所示。
第三行 \(q\) 个整数，代表这组数据的 \(q\) 次询问。
输出格式
输出一行 \(q\) 个整数，表示每个询问的答案对 \(998244353\) 取模的结果。
样例 #1
样例输入 #1
2 3 3 1 0 0
1
2
样例输出 #1
8
样例 #2
样例输入 #2
2 3 3 1 0 0
3
3 5 7
样例输出 #2
4 0 0
样例 #3
样例输入 #3
7 3 0 0
3
49 1 343
样例输出 #3
1 0 1
提示
样例解释：前两组数据均为 \(24\) 号数学树。这棵树绘制以后如下：
其中，\(2\) 出现了 \(8\) 次，\(3\) 出现了 \(4\) 次，\(5,7\) 则没有出现过。
对于第三组数据，你需要注意 \(343\) 在 \(343\) 号数学树的树根出现了一次，\(1\) 不会在数学树中出现。
| Subtask | \(n\) | \(q\) | 保证 \(n\) 是质数的幂 | 分值 |
|---|---|---|---|---|
| 0 | \(\le 10^3\) | \(\le 20\) | Yes | 10 |
| 1 | \(\le 10^6\) | \(\le 20\) | No | 10 |
| 2 | \(\sum b_i\le5000\) | \(\le 20\) | Yes | 40 |
| 3 | \(\sum b_i\le5000\) | \(\le 20\) | No | 40 |
对于 \(100\%\) 的数据，\(1\le b_i \le 5000\)，\(\sum b_i\le5000\)，\(2\le a_i\le 10^9\)，\(1\le x\le 10^{18}\)。
20pts
暴力
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int mod = 998244353;
ll x;
int cnt[100010];
void dfs(int g) {
int limt = sqrt(g) + 0.5;
for (int i = 2; i <= limt; ++ i) {
if (g % i == 0) {
++ cnt[g / i];
cnt[g / i] %= mod;
dfs(g / i);
if (g / i != i) {
++ cnt[i];
cnt[i] %= mod;
dfs(i);
}
}
}
}
int main() {
int a = read<int>(), b = read<int>(), q;
ll n = 1;
while (a != 0 && b != 0) {
n = n * pow(a, b);
a = read<int>(), b = read<int>();
}
cnt[n] = 1;
dfs(n);
q = read<int>();
while (q --) {
x = read<ll>();
cout << cnt[x] % mod << ' ';
}
return 0;
}