BreakFast:2021-2022 ICPC网络赛two

Replay

一开始读G题，极限不会

待有人过M题时，转头去读 M，想了一段时间，发现可以形成连续的区间，从高到低位扫一遍逐一确定，但因为忘记符号位，喜提WA，改后AC

然后继续想极限，lz抽空去看了J题，之后开始写J,一发AC

然后再继续想极限，推了一堆奇怪的东西，与hr的尝试相悖（期间还妄想拿本高数书现学，洛必达起来还极其麻烦，走投无路之下手推了 ln(1+x) 的泰勒展开，又因为一些逻辑有问题，WA++。改后AC

接下来陷入L题一万年，hr迅速口胡出一个错误想法，带着lz和wx走上歧路，写了半天，修了修细节，诶，样例过不去！！！lz指出状态之间有交叉，是没法维护的

xj读完A题后跟hr讲了讲，hr觉得挺对，因为时间复杂度分析失误，迟迟没有让lz去写

后来跟lz讲了一下，lz：“你们在说怪话！！”

于是lz迅速实现完A题，又get一个WA，比赛结束...

赛后光速补完A和L，喜提最快补题奖两枚。

戳我进入比赛

以下代码并非赛时AC代码, AC代码较为美观

Problem A. Sort

题目大意

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

定义一次操作为将序列 ${\textstyle a[]}$ 分割成 ${\textstyle v_{i}}$ 段，再对段做置换 ${\textstyle p_{i}}$.

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

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

${\textstyle 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}}$.

分析

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

当 ${\textstyle 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

题目大意

给出 ${\textstyle n,a_{i},b_{i},t}$，求 ${\textstyle \lim \limits _{x\rightarrow 0}{\frac {\sum _{i=1}^{n}{a_{i}ln(1+b_{i}x)}}{x^{t}}}}$.

${\textstyle 1\leq n\leq 10^{5},-100\leq a,b\leq 100,0\leq t\leq 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

题目大意

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

要求构造集合 ${\textstyle S}$ 的 ${\textstyle k}$ 个子集 ${\textstyle I_{i}}$，要求对任意的 ${\textstyle 1\leq i_{1}<i_{2}<\cdots <i_{r}\leq n}$ 满足 ${\textstyle |\bigcup _{j=1}^{r}{I_{i_{j}}}|\geq 128}$，且 ${\textstyle max\{|I_{i}|\}\leq \lceil {\frac {512}{r}}\rceil }$.

${\textstyle 3\leq r\leq k\leq 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

题目大意

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

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

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

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

${\textstyle 1\leq n\leq 500,0\leq m,h_{ij}\leq 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

题目大意

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

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

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

求第 ${\textstyle i}$ 个人点到第 ${\textstyle j}$ 道菜的概率.

${\textstyle 1\leq n\leq 20,1\leq a_{ij}\leq 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

题目大意

${\textstyle n}$ 个数 ${\textstyle a[]}$ 和 ${\textstyle m}$ 次操作.

操作分为两种

${\textstyle 0\;l\;r\;w}$ 表示 ${\textstyle a[i]*=w\quad i\in [l,r]}$.

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

${\textstyle 1\leq n,m\leq 10^{5},1\leq a_{i},w\leq 100,1\leq l\leq r\leq 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

题目大意

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

给出 ${\textstyle n,sgn[]}$ 和 ${\textstyle val_{a_{i}},val_{b_{i}}}$，令 ${\textstyle c=a+b}$，求出 ${\textstyle c}$ 的上述表示.

${\textstyle 32\leq n\leq 60,sgn_{i}\in \{-1,1\},val_{a_{i}}\in \{0,1\},val_{b_{i}}\in \{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;
}