The 2021 ICPC Asia Regionals Online Contest (II)【解题报告】

本文主要是介绍The 2021 ICPC Asia Regionals Online Contest (II)【解题报告】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

戳我进入比赛

---

Problem A. Sort

题目大意

$T$ 组，每组给出一个长度为 $n$ 的序列 $a[]$ 和 整数 $k$.

定义一次操作为将序列 $a[]$ 分割成 $v_i$ 段，再对段做置换 $p_i$.

若在有限次数操作中，无法使得序列 $a[]$ 变成非降序，则输出 $-2$.

若在有限次数操作中，可以使得序列 $a[]$ 变成非降序，且 $\sum v_i\le 3n$，则输出方案，否则输出 $-1$.

$1\le T\le 10^3,1\le k,n\le 10^3,1\le a[i]\le 10^9,\sum n\le 3\times 10^4$.

分析

不难发现，当 $k\ge 3$ 时，总可以构造出合法方案，就是一傻逼模拟题（被细节搞炸

当 $k=2$ 时，注意这个样例

2
3 2
1 2 1
2 1 2

代码实现

#include <bits/stdc++.h>
using namespace std;const int M = (int)1e3;int n, k;
int a[M + 5];
int b[M + 5];bool is_sort(int p)
{for(int i = 1; i < n; ++i){if(a[(i + p - 2) % n + 1] > a[(i + p - 1) % n + 1]) return 0;}return 1;
}void work()
{scanf("%d %d", &n, &k);for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);if(n == 1) printf("0\n");else if(k == 1){if(is_sort(1)) printf("0\n");else           printf("-2\n");}else if(k == 2){if(is_sort(1)) printf("0\n");else{for(int i = 1; i <= n; ++i){if(is_sort(i)){printf("1\n");printf("2\n");printf("%d %d %d\n", 0, i - 1, n);printf("2 1\n");for(int j = 1; j <= n; ++j) b[j] = a[j];for(int j = 1; j <= n - i + 1; ++j) a[j] = b[j - 1 + i];for(int j = n - i + 2; j <= n; ++j) a[j] = b[j - n + i - 1];return;}}printf("-2\n");}}else if(k >= 3){printf("%d\n", n - 1);for(int i = 1; i < n; ++i){int p = i; for(int j = i; j <= n; ++j) if(a[p] > a[j]) p = j;if(i == p){printf("2\n");printf("%d %d %d\n", 0, 1, n);printf("1 2\n");}else if(i == 1){printf("2\n");printf("%d %d %d\n", 0, p - 1, n);printf("2 1\n");for(int j = 1; j <= n; ++j) b[j] = a[j];for(int j = 1; j <= n - p + 1; ++j) a[j] = b[j + p - 1];for(int j = n - p + 2; j <= n; ++j) a[j] = b[j - n + p - 1];}else{printf("3\n");printf("%d %d %d %d\n", 0, i - 1, p - 1, n);printf("1 3 2\n");for(int j = 1; j <= n; ++j) b[j] = a[j];for(int j = 1; j <= i - 1; ++j) a[j] = b[j];for(int j = i; j <= i + n - p; ++j) a[j] = b[j - i + p];for(int j = i + n - p + 1; j <= n; ++j) a[j] = b[j - n + p - 1];}}}
}int main()
{int T; scanf("%d", &T);for(int ca = 1; ca <= T; ++ca){work();}return 0;
}

Problem G. Limit

题目大意

给出 $n,a_i,b_i,t$，求 $\underset{x\to 0}{\lim }\frac{{\sum }_{i=1}^n{a}_{i}ln(1+b_{i}x)}{x^t}$.

$1\le n\le 10^5,-100\le a,b\le 100,0\le t\le 5$.

分析

神他喵抓大头，直接无脑泰勒展开（赛时还想多项式卷积

结论：三个人都不会高数

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;int n, t;
ll c[10];void work()
{scanf("%d %d", &n, &t);for(int i = 1, a, b; i <= n; ++i){scanf("%d %d", &a, &b);ll cur = a;for(int j = 1; j <= t; ++j){cur *= b;c[j] += ((j&1) ? cur : -cur);}}if(!t) printf("0\n");else{for(int i = 1; i < t; ++i){if(c[i]){printf("infinity\n");return;}}if(c[t] == 0) printf("0\n");else{ll d = (ll)abs(__gcd(1ll * t, c[t]));ll up = c[t] / d, dn = t / d;if(dn == 1) printf("%lld\n", up);else       printf("%lld/%d\n", up, dn);}}
}int main()
{work();return 0;
}

Problem H. Set

题目大意

定义集合 S = { 1 , 2 , ⋯ , 256 } S=\{1,2, \cdots, 256\} S={1,2,⋯,256}，给出两个整数 $k$ 和 $r$.

要求构造集合 $S$ 的 $k$ 个子集 $I_i$，要求对任意的 $1\le i_1<i_2<\cdots <i_r\le n$ 满足 $|{\bigcup }_{j=1}^r{I}_{i_j}|\ge 128$，且 m a x { ∣ I i ∣ } ≤ ⌈ 512 r ⌉ max\{|I_i|\} \leq \lceil \frac{512}{r} \rceil max{∣Ii​∣}≤⌈r512​⌉.

$3\le r\le k\le 26$.

分析

直接 rand 所有子集就行了…

证明以后再补（咕咕咕

代码实现

#include <bits/stdc++.h>
using namespace std;int Rand(int l, int r)
{return rand() % (r - l + 1) + l;
}void work()
{int k, r; scanf("%d %d", &k, &r);for(int i = 1; i <= k; ++i){set<int> st;while((int)st.size() < (512 + r - 1) / r) st.insert(Rand(1, 256));for(int j = 1; j <= 256; ++j){printf("%d", st.count(j));}printf("\n");}
}int main()
{srand(time(NULL));work();return 0;
}

Problem J. Leaking Roof

题目大意

给一个 $n\times n$ 的矩阵 $h_{ij}$ 表示 $(i,j)$ 的高度.

现在每个单元都下了 $m$ 单位的雨水，$(i,j)$ 的雨水会平均地流向四周高度比它低的单元.

若高度为 $0$ 的点有雨水，则这个点会漏水.

求足够长时间后，每个点的漏水量.

$1\le n\le 500,0\le m,h_{ij}\le 10^4$.

分析

按照高度依次处理雨水的流动，模拟就行了.

代码实现

#include <bits/stdc++.h>
using namespace std;const int M = (int)5e2;int n, m;
int h[M + 5][M + 5];
int id[M * M + 5];
double a[M + 5][M + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};bool cmp(int a, int b)
{return h[a / n][a % n] > h[b / n][b % n];
}void work()
{scanf("%d %d", &n, &m);for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){id[i * n + j] = i * n + j;scanf("%d", &h[i][j]);a[i][j] = 1.0 * m;}}sort(id, id + n * n, cmp);for(int i = 0; i < n * n; ++i){int x = id[i] / n, y = id[i] % n, c = 0;for(int j = 0; j < 4; ++j){int xx = x + dx[j], yy = y + dy[j];if(xx >= 0 && xx < n && yy >= 0 && yy < n && h[xx][yy] < h[x][y]) ++c;}if(c){for(int j = 0; j < 4; ++j){int xx = x + dx[j], yy = y + dy[j];if(xx >= 0 && xx < n && yy >= 0 && yy < n && h[xx][yy] < h[x][y]) a[xx][yy] += a[x][y] / c;}a[x][y] = 0;}}for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) printf("%.9f%c", h[i][j] ? 0 : a[i][j], j == n - 1 ? '\n' : ' ');
}int main()
{work();return 0;
}

Problem K. Meal

题目大意

有 $n$ 个人，$n$ 道菜，第 $i$ 个人对第 $j$ 道菜的好感度为 $a_{ij}$.

初始，集合 S = { 1 , 2 , ⋯ , n } S = \{1,2,\cdots ,n\} S={1,2,⋯,n}.

$n$ 个人按照序号轮流点菜，对于第 $i$ 个人，他点到第 $j$ 道菜的概率为 $\frac{a_{ij}}{{\sum }_{k\in S}{a}_{ik}}$，然后把 $j$ 从 $S$ 中删除.

求第 $i$ 个人点到第 $j$ 道菜的概率.

$1\le n\le 20,1\le a_{ij}\le 100$.

分析

状压DP模板题~

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int M = (int)20;
const ll mod = (ll)998244353;int n, a[M][M];
int f[1<<M];
int s[1<<M];
int p[M][M];ll quick(ll a, ll b, ll p = mod)
{ll s = 1;while(b){if(b & 1) s = s * a % p;a = a * a % p;b >>= 1;}return s % p;
}ll inv(ll n, ll p = mod)
{return quick(n, p - 2, p);
}void work()
{scanf("%d", &n);for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d", &a[i][j]);for(int i = 0; i < (1<<n); ++i){int c = __builtin_popcount(i);for(int j = 0; j < n; ++j) if(!(i>>j&1)) s[i] += a[c][j];s[i] = inv(s[i]);}f[0] = 1;for(int i = 1; i < (1<<n); ++i){int c = __builtin_popcount(i) - 1;for(int j = 0; j < n; ++j){if(!(i>>j&1)) continue;(p[c][j] += 1ll * f[i^(1<<j)] * a[c][j] % mod * s[i^(1<<j)] % mod) %= mod;(f[i] += 1ll * f[i^(1<<j)] * a[c][j] % mod * s[i^(1<<j)] % mod) %= mod;}}for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) printf("%d%c", p[i][j], j == n - 1 ? '\n' : ' ');
}int main()
{work();return 0;
}

Problem L. Euler Function

题目大意

$n$ 个数 $a[]$ 和 $m$ 次操作.

操作分为两种

$0lrw$ 表示 $a[i]\ast =wi\in [l,r]$.

$1lr$ 表示查询 ${\sum }_{i=l}^r\phi (a[i])$.

$1\le n,m\le 10^5,1\le a_i,w\le 100,1\le l\le r\le n$.

分析

势能线段树（之前见过，但这是第一次知道还有这个名字

改了改线段树的码风

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int M = (int)1e5;
const int N = (int)1e2;
const ll mod = (ll)998244353;bool is_prime[N + 5];
int prime[N + 5], cnt;
int pw[N + 5][M + 5];void init()
{memset(is_prime, 1, sizeof(is_prime));cnt = is_prime[0] = is_prime[1] = 0;for(int i = 2; i <= N; ++i){if(is_prime[i]) prime[++cnt] = i;for(int j = 1; j <= cnt && i * prime[j] <= N; ++j){is_prime[i * prime[j]] = 0;if(i % prime[j] == 0) break;}}for(int i = 1; i <= cnt; ++i){pw[i][0] = 1; for(int j = 1; j <= M; ++j) pw[i][j] = 1ll * pw[i][j - 1] * prime[i] % mod;}
}int n, m;
struct tnode
{int s[M * 4 + 5], lz[M * 4 + 5][26]; bool is[M * 4 + 5][26];inline int lc(int k) {return k<<1;}inline int rc(int k) {return k<<1|1;}inline void push_up(int k){int l = lc(k), r = rc(k);s[k] = (s[l] + s[r]) % mod;for(int i = 1; i <= cnt; ++i) is[k][i] = (is[l][i]&is[r][i]);}inline void push_down(int k){int l = lc(k), r = rc(k);for(int i = 1; i <= cnt; ++i){if(!lz[k][i]) continue;s[l] = 1ll * s[l] * pw[i][lz[k][i]] % mod, lz[l][i] += lz[k][i];s[r] = 1ll * s[r] * pw[i][lz[k][i]] % mod, lz[r][i] += lz[k][i];lz[k][i] = 0;}}void build(int k, int l, int r){if(l == r){int x; scanf("%d", &x);s[k] = x;for(int i = 1; i <= cnt && prime[i] * prime[i] <= x; ++i){if(x % prime[i] == 0){s[k] = s[k] / prime[i] * (prime[i] - 1);is[k][i] = 1;while(x % prime[i] == 0) x /= prime[i];}}if(x > 1) s[k] = s[k] / x * (x - 1), is[k][lower_bound(prime + 1, prime + cnt + 1, x) - prime] = 1;return;}int mid = (l + r) >> 1;build(lc(k), l, mid);build(rc(k), mid + 1, r);push_up(k);}void update(int k, int l, int r, int a, int b, int p, int c){if(l >= a && r <= b && is[k][p]){s[k] = 1ll * s[k] * pw[p][c] % mod;lz[k][p] += c;return;}if(l == r){s[k] = 1ll * s[k] * (pw[p][c] - pw[p][c - 1]) % mod;is[k][p] = 1;return;}push_down(k);int mid = (l + r) >> 1;if(a <= mid) update(lc(k), l, mid, a, b, p, c);if(mid < b)  update(rc(k), mid + 1, r, a, b, p, c);push_up(k);}int query(int k, int l, int r, int a, int b){if(l >= a && r <= b) return s[k];push_down(k);int mid = (l + r) >> 1, sum = 0;if(a <= mid) (sum += query(lc(k), l, mid, a, b)) %= mod;if(mid < b)  (sum += query(rc(k), mid + 1, r, a, b)) %= mod;return sum;}
} tr;void work()
{scanf("%d %d", &n, &m);tr.build(1, 1, n);for(int i = 1, op, l, r, w; i <= m; ++i){scanf("%d", &op);if(op == 0){scanf("%d %d %d", &l, &r, &w);for(int j = 1; j <= cnt && prime[j] * prime[j] <= w; ++j){if(w % prime[j]) continue;int c = 0;while(w % prime[j] == 0) ++c, w /= prime[j];tr.update(1, 1, n, l, r, j, c);}if(w > 1) tr.update(1, 1, n, l, r, lower_bound(prime + 1, prime + cnt + 1, w) - prime, 1);}else{scanf("%d %d", &l, &r);printf("%d\n", (tr.query(1, 1, n, l, r) % mod + mod) % mod);}}
}int main()
{
//    freopen("input.txt", "r", stdin);init();work();return 0;
}

Problem M. Addition

题目大意

定义 $n$ 位 $2$ 进制数表示为 ${\sum }_{i=0}^{n}va{l}_i\times 2^i\times sgn[i]$.

给出 $n,sgn[]$ 和 $va{l}_{a_i},va{l}_{b_i}$，令 $c=a+b$，求出 $c$ 的上述表示.

32 ≤ n ≤ 60 , s g n i ∈ { − 1 , 1 } , v a l a i ∈ { 0 , 1 } , v a l b i ∈ { 0 , 1 } 32 \leq n \leq 60, sgn_i \in \{-1, 1\}, val_{a_i} \in \{0,1\}, val_{b_i} \in \{0,1\} 32≤n≤60,sgni​∈{−1,1},valai​​∈{0,1},valbi​​∈{0,1}.

分析

连续的低位会构成连续的值域，因此只需要从高到低扫一遍，逐一确认每一位即可.

代码实现

#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int M = (int)1e2;int n;
int sgn[M + 5];
ll mi[M + 5], mx[M + 5];
int ans[M + 5];void work()
{scanf("%d", &n);for(int i = 0; i < n; ++i) scanf("%d", &sgn[i]);if(sgn[0] == 1) mi[0] = 0, mx[0] = 1;else            mi[0] = -1, mx[0] = 0;for(int i = 1; i < n; ++i){if(sgn[i] == 1) mi[i] = mi[i - 1], mx[i] = mx[i - 1] + (1ll<<i);else            mi[i] = mi[i - 1] - (1ll<<i), mx[i] = mx[i - 1];}ll a = 0; for(int i = 0, x; i < n; ++i) scanf("%d", &x), a += (1ll<<i) * x * sgn[i];ll b = 0; for(int i = 0, x; i < n; ++i) scanf("%d", &x), b += (1ll<<i) * x * sgn[i];ll c = a + b;for(int i = n - 1; i >= 0; --i){if(i){if(mi[i - 1] <= c && c <= mx[i - 1]) ans[i] = 0;else    c -= sgn[i] * (1ll<<i), ans[i] = 1;}else if(c) ans[i] = 1;}for(int i = 0; i < n; ++i) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
}int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);work();return 0;
}

这篇关于The 2021 ICPC Asia Regionals Online Contest (II)【解题报告】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---