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

24922

四个小时四道题

T1 字少果断开。

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

对于 \(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\)。

做个差：

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

// 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 开局随便选一个数，选另一个就是 \(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\)。