戳我进入比赛
Problem A. Sort
题目大意
T T T 组，每组给出一个长度为 n n n 的序列 a [ ] a[] a[] 和 整数 k k k.
定义一次操作为将序列 a [ ] a[] a[] 分割成 v i v_i vi 段，再对段做置换 p i p_i pi.
若在有限次数操作中，无法使得序列 a [ ] a[] a[] 变成非降序，则输出 − 2 -2 −2.
若在有限次数操作中，可以使得序列 a [ ] a[] a[] 变成非降序，且 ∑ v i ≤ 3 n \sum{v_i} \leq 3n ∑vi≤3n，则输出方案，否则输出 − 1 -1 −1.
1 ≤ T ≤ 1 0 3 , 1 ≤ k , n ≤ 1 0 3 , 1 ≤ a [ i ] ≤ 1 0 9 , ∑ n ≤ 3 × 1 0 4 1 \leq T \leq 10^3, 1 \leq k,n \leq 10^3,1 \leq a[i] \leq 10^9, \sum{n} \leq 3\times 10^4 1≤T≤103,1≤k,n≤103,1≤a[i]≤109,∑n≤3×104.
分析
不难发现，当 k ≥ 3 k \geq 3 k≥3 时，总可以构造出合法方案，就是一傻逼模拟题（被细节搞炸
当 k = 2 k=2 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 n, a_i, b_i, t n,ai,bi,t，求 lim x → 0 ∑ i = 1 n a i l n ( 1 + b i x ) x t \lim\limits_{x \rightarrow 0}{\frac{\sum_{i=1}^n{a_i ln(1+b_ix)}}{x^t}} x→0limxt∑i=1nailn(1+bix).
1 ≤ n ≤ 1 0 5 , − 100 ≤ a , b ≤ 100 , 0 ≤ t ≤ 5 1 \leq n \leq 10^5, -100 \leq a, b \leq 100, 0 \leq t \leq 5 1≤n≤105,−100≤a,b≤100,0≤t≤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 k k 和 r r r.
要求构造集合 S S S 的 k k k 个子集 I i I_i Ii，要求对任意的 1 ≤ i 1 < i 2 < ⋯ < i r ≤ n 1 \leq i_1 < i_2 < \cdots < i_r \leq n 1≤i1<i2<⋯<ir≤n 满足 ∣ ⋃ j = 1 r I i j ∣ ≥ 128 |\bigcup_{j=1}^{r}{I_{i_j}}| \geq 128 ∣⋃j=1rIij∣≥128，且 m a x { ∣ I i ∣ } ≤ ⌈ 512 r ⌉ max\{|I_i|\} \leq \lceil \frac{512}{r} \rceil max{∣Ii∣}≤⌈r512⌉.
3 ≤ r ≤ k ≤ 26 3 \leq r \leq k \leq 26 3≤r≤k≤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 × n n \times n n×n 的矩阵 h i j h_{ij} hij 表示 ( i , j ) (i,j) (i,j) 的高度.
现在每个单元都下了 m m m 单位的雨水， ( i , j ) (i,j) (i,j) 的雨水会平均地流向四周高度比它低的单元.
若高度为 0 0 0 的点有雨水，则这个点会漏水.
求足够长时间后，每个点的漏水量.
1 ≤ n ≤ 500 , 0 ≤ m , h i j ≤ 1 0 4 1 \leq n \leq 500, 0 \leq m,h_{ij} \leq 10^4 1≤n≤500,0≤m,hij≤104.
分析
按照高度依次处理雨水的流动，模拟就行了.
代码实现
#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 n 个人， n n n 道菜，第 i i i 个人对第 j j j 道菜的好感度为 a i j a_{ij} aij.
初始，集合 S = { 1 , 2 , ⋯ , n } S = \{1,2,\cdots ,n\} S={1,2,⋯,n}.
n n n 个人按照序号轮流点菜，对于第 i i i 个人，他点到第 j j j 道菜的概率为 a i j ∑ k ∈ S a i k \frac{a_{ij}}{\sum_{k \in S}{a_{ik}}} ∑k∈Saikaij，然后把 j j j 从 S S S 中删除.
求第 i i i 个人点到第 j j j 道菜的概率.
1 ≤ n ≤ 20 , 1 ≤ a i j ≤ 100 1 \leq n \leq 20, 1 \leq a_{ij} \leq 100 1≤n≤20,1≤aij≤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 n n 个数 a [ ] a[] a[] 和 m m m 次操作.
操作分为两种
0 l r w 0 \; l \; r \; w 0lrw 表示 a [ i ] ∗ = w i ∈ [ l , r ] a[i] *= w \quad i \in [l, r] a[i]∗=wi∈[l,r].
1 l r 1 \; l \; r 1lr 表示查询 ∑ i = l r φ ( a [ i ] ) \sum_{i=l}^{r}{\varphi(a[i])} ∑i=lrφ(a[i]).
1 ≤ n , m ≤ 1 0 5 , 1 ≤ a i , w ≤ 100 , 1 ≤ l ≤ r ≤ n 1 \leq n,m \leq 10^5, 1 \leq a_i,w \leq 100, 1 \leq l \leq r \leq n 1≤n,m≤105,1≤ai,w≤100,1≤l≤r≤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 n n 位 2 2 2 进制数表示为 ∑ i = 0 n v a l i × 2 i × s g n [ i ] \sum_{i=0}^n{val_i \times 2^i \times sgn[i]} ∑i=0nvali×2i×sgn[i].
给出 n , s g n [ ] n,sgn[] n,sgn[] 和 v a l a i , v a l b i val_{a_i}, val_{b_i} valai,valbi，令 c = a + b c = a + b c=a+b，求出 c c 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;
}