• 欢迎光临~

多校联测3

开发技术 开发技术 2022-10-06 次浏览

T1.A

我12:10才打出来,因为一开始觉得这个题不可做。其实很简单,只关心与(a_1)的相对大小关系。定义(f_i)表示第(i)轮结束后有多少个比(a_1)小的数。对于修改第(x)轮,如果原来大,现在小,那么给所有在(x)后面的(f)加一;如果原来小,现在大,那么减一;否则不操作。线段树求一下区间(min),会被(out)掉显然是有一个地方的(f)小于(0)。注意修改区间要(lle r)

代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
#define rep(i, a, b) for (re (i) = (a); (i) <= (b); ++(i))
#define dwn(i, a, b) for (re (i) = (a); (i) >= (b); --(i))
#define aut(i, x) for (auto (i) = (x.begin()); (i) < (x.end()); ++(i))
using namespace std;
const int Z = 1e5 + 10;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f = c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
 
int n, m, q, ans;
int a[Z], root, f[Z];
vector <int> b[Z];
struct tree
{
    int min, lz;
    #define lk (rt << 1)
    #define rk (rt << 1 | 1)
    #define mid (L + R >> 1)
}; tree tr[Z << 2];
inline void change(int rt, int val) { tr[rt].min += val, tr[rt].lz += val; }
inline void pushup(int rt) { tr[rt].min = min(tr[lk].min, tr[rk].min); }
inline void pushdown(int rt) { if (tr[rt].lz) change(lk, tr[rt].lz), change(rk, tr[rt].lz), tr[rt].lz = 0; }
void build(int rt, int L, int R)
{
    if (L == R) { tr[rt].min = f[L]; return; }
    build(lk, L, mid), build(rk, mid + 1, R);
    pushup(rt);
}
void update(int rt, int L, int R, int l, int r, int val)
{
    if (l > r) return;
    if (l <= L && r >= R) { change(rt, val); return; }
    pushdown(rt);
    if (l <= mid) update(lk, L, mid, l, r, val);
    if (r > mid) update(rk, mid + 1, R, l, r, val);
    pushup(rt);
}
 
sandom main()
{
    n = read(), m = read(), q = read();
    rep(i, 1, n) a[i] = read(); root = a[1];
    rep(i, 1, m) dwn(j, read(), 1) b[i].push_back(read());
    rep(i, 1, n) if (a[i] < root) f[1]++;
    rep(i, 1, m)
    {
        aut(j, b[i]) f[i]--;
        f[i + 1] = f[i];
        aut(j, b[i]) if (*j < root) f[i + 1]++;
    }
    build(1, 1, m);
    while (q--)
    {
        int x = read(), y = read() - 1, z = read();
        if (b[x][y] > root && z < root) update(1, 1, m, x + 1, m, 1);
        if (b[x][y] < root && z > root) update(1, 1, m, x + 1, m, -1);
        b[x][y] = z;
        if (tr[1].min < 0) puts("0");
        else puts("1");
    }
    return 0;
}

T2.B

定义(dp[i][j])为长度为(i)的区间的电脑已经被全部打开,其中有(j)个是手动打开的。转移是显然的,枚举自动打开的那个点,设前面长度为(j),则后面长度为(i-j-1),强制前面(j)个手动,后面枚举手动了(k)个(强制的作用是去重,因为发现(k)的情况已经足够多);之后强制这个自动的电脑在最后,那么可以对其他的自由排列,但要保持两段内部的相对顺序,发现方案数为(frac{(j+k)!}{j!k!}),然后发现这个其实就是组合数。所以转移为(dp[i][j+k]+=dp[j][j]*dp[i-j-1][k]*C_{j+k}^k),因为赛时没看到模数是质数,所以采取了递推组合数。

代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define sandom signed
#include <bits/stdc++.h>
#define re register int
#define int long long 
#define rep(i, a, b) for (re (i) = (a); (i) <= (b); ++(i))
using namespace std;
const int Z = 410;

int n, m, p, ans;
int C[Z][Z], dp[Z][Z];
inline void init()//预处理组合数
{
    C[1][0] = C[1][1] = 1;
    rep(i, 2, n)
    {
        C[i][0] = 1;
        rep(j, 1, i) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % p;
    }
}

sandom main()
{
    cin >> n >> p;
    init(); rep(i, 1, n) dp[i][i] = 1;
    rep(i, 2, n)
    {
        rep(j, 1, i - 2) rep(k, 0, i - j - 1)
            (dp[i][j + k] += dp[j][j] * dp[i - j - 1][k] % p * C[j + k][k] % p) %= p;
        dp[i][i] = dp[i - 1][i - 1] * 2 % p;
    }
    rep(i, 1, n) (ans += dp[n][i]) %= p;
    cout << ans << endl;
    return 0;
}

T3.C

后缀数组和主席树,但是被暴力水过了。但因为我赛时偷懒,用的string,虽然string比较看起来人畜无害,但它实际上是(O(n))的,所以挂了。

代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define sandom signed
#include <bits/stdc++.h>
#define re register int
#define rep(i, a, b) for (re (i) = (a); (i) <= (b); ++(i))
using namespace std;

int n, m, k;
string s, t, ans;
sandom main()
{
    cin >> n >> s;
    m = (1 << n) - 1;
    ans = t = s;
    rep(k, 1, m)
    {
        bool op = 1;
        rep(i, 0, m) 
        {
            t[i] = s[i ^ k];
            if (op && t[i] > ans[i]) break;
            if (op && t[i] < ans[i]) op = 0;
            if (!op) ans[i] = t[i];
        }
    }
    cout << ans;
    return 0;
}

T4.D

观察样例,找到规律:80;第二个部分分:20——>100.
发现因为保证有解,所以先合并小的,肯定不会对大的造成错误,用并查集维护。这样操作完之后发现可能还有一坨没有连上,但它们之间不构成连通块,那我只需要保证相邻的两个数不直接相连就可以了。假设(i、j)属于两个不同的连通块,那么在(i)中寻找到一个(k),使得(j、k)的差值大于1,就可以连边。

代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define sandom signed
#include <bits/stdc++.h>
#define re register int
#define rep(i, a, b) for (re (i) = (a); (i) <= (b); ++(i))
using namespace std;
const int Z = 2010;

int n, m, k, ans;
char s[Z];
bool f[Z][Z];
int fa[Z];
inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
inline void un(int x, int y)
{
    int xx = find(x), yy = find(y);
    if (xx == yy) return;
    printf("%d %dn", x, y);
    fa[xx] = yy;
}

sandom main()
{
    cin >> n; rep(i, 1, n) fa[i] = i;
    rep(i, 1, n)
    {
        scanf("%s", s);
        rep(j, 0, n - i) f[i][i + j] = s[j] - '0';
    }
    rep(k, 1, n) rep(i, 1, n) if (f[i][i + k]) un(i, i + k);
    rep(i, 1, n) rep(j, i + 1, n)
    if (find(i) != find(j))
    {
        int x = find(i), y = find(j);
        rep(k, 1, n) if (find(k) == x && abs(k - j) > 1) un(k, j);
    }
    return 0;
}
程序员灯塔
转载请注明原文链接:多校联测3
喜欢 (0)