Difference between revisions of "BreakFast:2021-2022 ICPC网络赛two"

Latest revision as of 21:58, 26 September 2021

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，喜提最快补题奖两枚。

Soltion

戳我进入比赛

以下代码并非赛时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;
}

@@ Line 1: / Line 1: @@
+__TOC__
 == Replay ==
@@ Line 23: / Line 25: @@
 == 戳[https://pintia.cn/market/item/1442013218528759808 我]进入比赛 ==
+以下代码并非赛时AC代码, AC代码较为美观
 === Problem A. Sort ===

Difference between revisions of "BreakFast:2021-2022 ICPC网络赛two"

Latest revision as of 21:58, 26 September 2021

Contents

Replay

Soltion

戳我进入比赛

Problem A. Sort

题目大意

分析

代码实现

Problem G. Limit

题目大意

分析

代码实现

Problem H. Set

题目大意

分析

代码实现

Problem J. Leaking Roof

题目大意

分析

代码实现

Problem K. Meal

题目大意

分析

代码实现

Problem L. Euler Function

题目大意

分析

代码实现

Problem M. Addition

题目大意

分析

代码实现

Navigation menu

Search