9 - 22 ~ 9 - 23 模拟赛报告

Dark's Blog / 2024-09-25 / 原文

24922

四个小时四道题

T1 字少果断开。

给定正整数 $n$，计算 $n$ 个元素的集合 $\{1, 2, \cdots, n\}$，所有非空子集和的乘积取模 $998244353$ 后的结果。

$taskid$	$n$
$1 \sim 3$	$= taskid$
$4 \sim 6$	$\le 20$
$7 \sim 9$	$\le 50$
$10$	$\le 200$

对于 $100\%$ 的数据，$n \le 200$。

一看不会正解，只能想非常智障的办法（

// Darkworldmystery 2023 ~ 2024
#include<bits/stdc++.h>

using namespace std;
using LL = long long;

const LL kMod = 998244353;

LL n, ans = 1, cnt;

int main()
{
    freopen("set.in", "r", stdin);
    freopen("set.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin >> n;
    for(LL i = 1; i < (1 << n); i++)
    {
        vector<LL> st;
        st.clear();
        for(LL j = 0; j < n; j++)
            if(i & (1 << j))
                st.push_back(j + 1);
        LL tmp = 0;
        for(LL j = 0; j < st.size(); j++)
            (tmp += st[j]) %= kMod;
        ans = (ans % kMod) * tmp % kMod;
    }
    cout << ans << "\n";
    return 0;
}

想法就是枚举非空子集然后手做，以为可以跑 $90pt$，结果 $n = 40$ 的样例错了。

[input]
40
[expected output]
133045141
[received output]
508487924

但是前面没错，不知道是溢出了还是怎么的。

期望 $60pt$，实际 $60pt$。

看了眼 T3 发现是图论，直接避雷，往回看 T2 感觉可做。

有 $1 \sim n$ $n$ 个点顺序排列，每个点可以放 $k$ 个元素。

第 $i$ 个元素需要放在 $[x \sim x + d]$ 的区间中，$d$ 是常量。

$m$ 次操作，每次操作会有 $y$ 个元素等待放置在 $[x \sim x + d]$ 的区间中，每次操作询问能不能放完所有的元素。

立刻知道了无解情况就是元素堆出了需要的区间：

如果在此区间 $[l, r]$ 人数 $> (r - l + 1 + d) \times k$ 就无解。

令元素数为 $tot$，提常数得到 $(r - l + 1) \times k + kd$，所以 $tot < (r - l + 1) \times k + kd$。

做个差：

\[\sum_{l} ^ {r} (tot - k) > kd \]

考虑求左边，哦，最大子段和，线段树果断秒了。

// Darkworldmystery 2023 ~ 2024
#include<bits/stdc++.h>

using namespace std;
using LL = long long;

#define ls(x) x << 1
#define rs(x) x << 1 | 1

const LL kMaxN = 5e5 + 5;

struct Edge
{
    LL lt, rt, sum, w;
} tree[kMaxN << 2];

LL n, m, k, d;

void pushup(LL x)
{
    tree[x].sum = tree[ls(x)].sum + tree[rs(x)].sum;
    tree[x].lt = max(tree[ls(x)].lt, tree[ls(x)].sum + tree[rs(x)].lt);
    tree[x].rt = max(tree[rs(x)].rt, tree[rs(x)].sum + tree[ls(x)].rt);
    tree[x].w = max(tree[ls(x)].w, max(tree[rs(x)].w, tree[ls(x)].rt + tree[rs(x)].lt));
    return ;
}
void build(LL x, LL l, LL r)
{
    if(l == r)
    {
        tree[x] = {0, 0, -k, -k};
        return ;
    }
    LL mid = l + r >> 1;
    build(ls(x), l, mid);
    build(rs(x), mid + 1, r);
    pushup(x);
    return ;
}
void update(LL x, LL l, LL r, LL lt, LL rt)
{   
    if(l == r)
    {
        tree[x].w += rt;
        tree[x].sum += rt;
        tree[x].lt = tree[x].rt = max(tree[x].sum, 0ll);
        return ;
    }
    LL mid = l + r >> 1;
    if(mid >= lt)
        update(ls(x), l, mid, lt, rt);
    else    
        update(rs(x), mid + 1, r, lt, rt);
    pushup(x);
    return ;     
}

int main()
{
    freopen("hire.in", "r", stdin);
    freopen("hire.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k >> d;
    build(1, 1, n);
    for(LL i = 1, x, y; i <= m; i++)
    {
        cin >> x >> y;
        update(1, 1, n, x, y);
        if(tree[1].w <= k * d)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

期望：$100pt$，实际：$100pt$。

24923

四道题目四小时。

先看 T1：

$a$ 个 $0$，$b$ 个 $1$，$c$ 个 $2$，Alice 和 Bob 轮流取一个数，Alice 先取，累计取数总和是 $3$ 的倍数或者无数可取算输。

$0$ 特殊先考虑了。首先 $0$ 不能开头取，而且 $0$ 不能加和，所以用这个可以转移自己的痛苦（

（错误原因看最后）

正解

$0$ 的判是没问题，但是很麻烦，因为这种转移操作什么时候都可以，先不要这种 EX 特性了。

只要 $1, 2$ 的话，现在我们列个表模拟一下俩人取数的情况：

Alice	Bob
$2$
	$2 ^ \alpha$
$1$
	$2$
$1$
	$2$
$\cdots$

此时 Alice 开局随便选一个数，选另一个就是 $3$ 的倍数了。

后面只能交替取，设一个数有 $x$ 个，另一个 $y$ 个，那么开 $x -= 2$ 时进入循环取数直到没数了。条件是你开始选的数数量要 $\ge 2$。

所以只要 $x - 2 \lt y$ 就可以了。不然就是输。

现在考虑有 $0$。

$0$ : 传递烂摊子的责任交给我吧！

显然如果 $0$ 只有偶数次，烂摊子又会回到我的手中。而且因为前面用 $0$ 点用没有，所以不存在前面消耗 $0$。

反之，本来很棘手的麻烦（比如 $x - 2 \ge y$）遇到了奇数个 $0$，那废话肯定丢给他啊，所以完了。

if(x >= 2)
{
	if((x - 2 < c && !(0 的个数 % 2)) || (x - 2 >= c && (0 的个数 % 2)))
		cout << "First\n";
}

那么如果 $x$ 只有 $1$ 呢？

那么 Alice 先取 $x$，Bob 肯定不会取 $y$，只能取 $0$，那么如果同样的，$0$ 的个数是偶数，那么烂摊子又会回到他的手中，只能取 $y$，我们就赢了。

else if(y == 1 && !(0 的个数 % 2))
	cout << "First\n";

接下来特判条件很简单：没有 $1$ 和 $2$，不用做了，直接 Second。

// Darkworldmystery 2023 ~ 2024
#include<bits/stdc++.h>

using namespace std;
using LL = long long;

#define solF {cout << "First\n"; continue;}
#define solS {cout << "Second\n"; continue;}

LL t, a, b, c;

int main()
{
    freopen("yiyi.in", "r", stdin);
    freopen("yiyi.out", "w", stdout);
    cin >> t;
    while(t--)
    {
        cin >> a >> b >> c;
        a %= 2;
        if(!b && !c)
            solS;
        if(b >= 2)
        {
            if((b - 2 < c && !a) || (b - 2 >= c && a))
                solF;
        }
        else if(b == 1 && !a)
            solF;
        if(c >= 2)
        {
            if((c - 2 < b && !a) || (c - 2 >= b && a))
                solF;
        }
        else if(c == 1 && !a)
            solF;
        solS;
    }
    return 0;
}

期望 $100pt$，实际 $0pt$。

原因：$x - 2 \rightarrow x - 1$。

毫米之差也会酿成大错。

T2 随便乱搞的，拿了 $10pt$。