CSP-S 题目选讲

· · 个人记录

CSP-S 题目选讲

题目列表：

CSP-S 2024

A P11231 [CSP-S 2024] 决斗

简单的说，就是严格的高攻击力打低攻击力，但每张卡只能打一次，问最后最多能活几张卡。

第一种方法，可以直接模拟整个过程，为了活的卡牌更少，就要让死的卡牌更多，所以更高攻击力的卡牌应该留着打尽可能强的卡牌，然后我们发现最优的方法就是从低到高扫，每张卡牌去打当前能打过的牌。在这种情况下，打哪张卡是无所谓的，所以不妨从最低攻击力的卡牌开始打，因为这样好模拟。

::::info[CSP-S 2024 A1]

int t[100005] , canatk[100005];
signed main()
{
    int n;
    read(n);
    for(int i = 1 ; i <= n ; i++)
    {
        int a;
        read(a);
        t[a]++ , canatk[a]++;
    }
    int l = 1 , r = l + 1;
    for( ; l <= 100000 && r <= 100000 ; )
    {
        while(t[l] == 0 && l <= 100000)
        {
            l++;
        }
        r = l + 1;
        while(canatk[r] == 0 && r <= 100000)
        {
            r++;
        }
        int p = min(t[l] , canatk[r]);
        t[l] -= p , canatk[l] -= p;
        canatk[r] -= p;
    }
    int ans = 0;
    for(int i = 1 ; i <= 100000 ; i++)
    {
        ans += t[i];
    }
    printnl(ans);
    return 0;
}

::::

第二种方法，可以直接取众数的出现次数。简要证明过程如下：我们可以把整个游戏分成若干轮，如果攻击力为某个值的卡牌还有至少一张，我们就挑出正好一张。这个时候我们会挑出当前可选出的最多数量的不同卡牌，然后让这些卡牌最高打次高，次高打第三高，直到打完为止。这样一轮中，所有卡牌利用都达到了最大化，也就是活的卡牌达到了最小值。我们还可以发现，这个操作能且仅能进行的轮数为众数出现的次数（多个众数只考虑一个）。而每轮只会活最高攻击力的卡牌（如果只有一个卡牌也是同理），所以最终活着的卡牌数量为众数出现的次数（多个众数只考虑一个），且能证明为最小值。

::::info[CSP-S 2024 A2]

map < int , int > m;
signed main()
{
    int n;
    read(n);
    int ans = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        int a;
        read(a);
        ans = max(ans , ++m[a]);
    }
    printnl(ans);
    return 0;
}

::::

B P11232 [CSP-S 2024] 超速检测

第一问可以用 double 直接求，但我觉得不保险，用的是手动模拟分数形式和整数转换。

我们考虑知道起点 d、初速度 v、加速度 a 和超速速度 V（注意是严格大于 V 才会被判超速）时，如何求超速区间。这里使用区间或集合的形式书写，中括号代表能取到，小括号代表取不到。

首先一些一定不超速或者一定超速的情况需要判断：

然后还有两段需要计算，根据上文已知条件，可以选择题目提示中最后一个公式来计算，据此得到：

我们发现这里面有能取到端点的，也有取不到端点的，让我们非常难受。我们自然可以把所有的区间都变成开区间（即端点取不到），但我们也可以变成闭区间（即端点能取到）。这两种方法差别不大，这里简单说一下怎么变成闭区间。

首先，我们容易发现上述两个分数都是正数，而第二个分数的分子分母都是负数，所以我们可以将其变为正数，方便操作。之后，如果左端点取不到，就给分子加一；右端点取不到，就给分子减一。这样我们发现一定会将整个数往中间移动一点，但不会影响原来可以取到的整数。然后我们对左端点和右端点分别上取整和下取整即可。

为了方便统计答案，我们可以处理出每个点向右的第一个测速仪，统计答案时判断起点向右的第一个测速仪是否在区间中即可。

第二问是一种贪心模型，我们把第一问中超速的区间挑出来，然后就变成了用最少的测速仪使其覆盖每个区间。当然为了方便，我们也可以把区间的左右端点从具体的位置换为能被测速仪测试到的区间（这里我没换）。对于这个模型，我们按照右端点排序，从第一个开始记录下当前的区间交集（即所有区间都包含的区间中最大的一个），这个交集一定是连续的一段。不断往这堆区间中添加新区间，直到交集中不包含任何一个测速仪（判断方法同上），就把前面的一堆区间记一次答案，从这个区间开始继续添加区间，直到遍历完为止。

::::info[CSP-S 2024 B]

struct number
{
    long long fenzi , fenmu;
};
int n , m , L , vmax;
struct car
{
    long long v , delv , st;
    number start , end;
    void get_()
    {
        IntRead(st);
        IntRead(v);
        IntRead(delv);
    }
    void init()
    {
        if(v <= vmax && delv <= 0)
        {
            start.fenzi = 1 , end.fenzi = 0;
            start.fenmu = end.fenmu = 1;
        }
        else if(v > vmax && delv >= 0)
        {
            start.fenzi = st , start.fenmu = 1;
            end.fenzi = L , end.fenmu = 1;
        }
        else if(v <= vmax && delv > 0)
        {
            start.fenzi = st * 2 * delv + (vmax * vmax - v * v) + 1 , start.fenmu = 2 * delv;
            end.fenzi = L , end.fenmu = 1;
        }
        else if(v > vmax && delv < 0)
        {
            start.fenzi = st , start.fenmu = 1;
            end.fenzi = st * 2 * delv + (vmax * vmax - v * v) , end.fenmu = -2 * delv;
            end.fenzi = -end.fenzi - 1;
        }
    }
};
car a[100005];
pair < long long , long long > osp[100005];
long long nxtchk[1000005];
int cnt = 0;
pair < long long , long long > sp[100005];
namespace solve
{
    signed main()
    {
        read(n , m , L , vmax);
        cnt = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            a[i].get_();
            a[i].init();
            osp[i].first = (a[i].start.fenzi + a[i].start.fenmu - 1) / a[i].start.fenmu;
            osp[i].second = a[i].end.fenzi / a[i].end.fenmu;
            osp[i].first = min(osp[i].first , L + 1ll);
            osp[i].second = min(osp[i].second , L + 0ll);
        }
        for(int i = 1 ; i <= m ; i++)
        {
            int x;
            read(x);
            nxtchk[x] = x;
        }
        for(int i = 1e6 , now = 2e9 ; i >= 1 ; i--)
        {
            if(nxtchk[i] == i)
            {
                now = i;
            }
            nxtchk[i] = now;
        }
        int ans1 = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            if(nxtchk[osp[i].first] <= osp[i].second)
            {
                ans1++;
                sp[++cnt].first = osp[i].first , sp[cnt].second = osp[i].second;
            }
        }
        auto cmp1 = [] (pair < long long , long long > a , pair < long long , long long > b) { return a.second < b.second; };
        int ans2 = 0;
        sort(sp + 1 , sp + cnt + 1 , cmp1);
        for(long long i = 1 , minr , maxl ; i <= cnt ; )
        {
            minr = sp[i].second , maxl = sp[i].first;
            while(i <= cnt)
            {
                maxl = max(maxl , sp[i].first);
                if(maxl > minr)
                {
                    break;
                }
                if(nxtchk[maxl] > minr)
                {
                    break;
                }
                i++;
            }
            ans2++;
        }
        print(ans1 , ' ' , m - ans2 , '\n');
        return 0;
    }
}
signed main()
{
    int t;
    read(t);
    while(t--)
    {
        memset(a , 0 , sizeof(a));
        memset(osp , 0 , sizeof(osp));
        memset(nxtchk , 0 , sizeof(nxtchk));
        memset(sp , 0 , sizeof(sp));
        solve::main();
    }
    return 0;
}

::::

C P11233 [CSP-S 2024] 染色

我们发现将所有红色和蓝色全部反转之后答案不变，所以每个位置具体什么颜色不重要。

我们考虑最简单的状态，f_i 表示 1 \sim i 的最优答案，这里不需要记录 i 的颜色，因为全部颜色反转之后答案显然不变。

首先 f_i 可以继承 f_{i - 1} 的答案，此时表示 i 选的颜色对答案没有影响。当然我们也可以让 i 点成为答案的一部分，此时需要让 i 的颜色和上一个同值的颜色相同，而上一个同值的位置可以预处理出来（具体见代码）。

设存在上一个同值的位置，且为 lst。此时有一个强制条件，就是 lst + 1 \sim i - 1 这一段的颜色一定是 lst , i 这两个位置的异色。

此时答案变为两部分，分别是 f_{lst + ?} 和 lst \sim i 的答案。第一部分可以直接拿来用，但具体的下标是多少还需要额外分析。如果从 f_{lst - 1} 转移，就丢失了 lst 的答案。具体原因是，原题的描述会将同值同色的点中，靠右的一个拿来贡献答案，则左边的一个，即 lst，如果也有答案的话，从 f_{lst - 1} 转移就会丢失这部分答案。

而考虑到本题有两种颜色，如果 lst + 1 这个位置也有贡献，则这个位置的颜色一定是 lst , i 这两个位置的异色。根据上文的分析，lst \sim i 段的答案一定不会包括 lst + 1，因为端点和这个位置是异色的。而如果上一个和 lst + 1 同色的位置正好也同值，则 lst + 1 也可能在答案中，而由于和 lst \sim i 段的端点异色，lst + 1 位置的答案不会在这一段中被统计，那只能在第一部分被统计，所以第一部分的值应该是 f_{lst + 1}。

那么第二部分的答案还可以分成两块，一块是同色的 lst + 1 \sim i - 1，这一段若想对答案有贡献，只能是相邻位置的颜色相同，这个值同样可以前缀和预处理，需要时作差得出。还有一块答案是 lst , i 同色的答案，这个就是 a_i，直接加上就可以了。

::::info[CSP-S 2024 C]

long long lx[200005];
long long a[200005];
long long lst[1000005] , f[200005];
namespace solve
{
    signed main()
    {
        int n;
        read(n);
        readarray(a , 1 , n);
        for(int i = 1 ; i <= n ; i++)
        {
            lx[i] = lx[i - 1] + (a[i] == a[i - 1] ? a[i] : 0);
        }
        for(int i = 1 ; i <= n ; i++)
        {
            f[i] = f[i - 1];
            if(lst[a[i]])
            {
                f[i] = max(f[i] , f[lst[a[i]] + 1] + a[i] + lx[i] - lx[lst[a[i]] + 1]);
            }
            lst[a[i]] = i;
        }
        printnl(f[n]);
        return 0;
    }
}
signed main()
{
    int t;
    read(t);
    while(t--)
    {
        memset(a , 0 , sizeof(a));
        memset(lx , 0 , sizeof(lx));
        memset(lst , 0 , sizeof(lst));
        memset(f , 0 , sizeof(f));
        solve::main();
    }
    return 0;
}

::::

CSP-S 2023

A P9752 [CSP-S 2023] 密码锁

需要注意的是，转动后密码不变，不管是转了多少整圈，都会被认为没转动密码锁。

一个显然的方法，就是判断每种密码能否转出所有状态。我们发现一共只有 00000 \sim 99999 共 10 ^ 5 个状态，非常好写，而且也能过。

::::info[CSP-S 2023 A1]

int n;
int mode[10][10];
bool check(int nn)
{
    int now[10];
    for(int i = 5 ; i >= 1 ; i--)
    {
        now[i] = nn % 10;
        nn /= 10;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        bool ok = 0;
        for(int j = 1 ; j <= 5 ; j++)
        {
            for(int k = 1 ; k <= 9 ; k++)
            {
                now[j] += k;
                now[j] %= 10;
                if(now[1] == mode[i][1] && now[2] == mode[i][2] && now[3] == mode[i][3] && now[4] == mode[i][4] && now[5] == mode[i][5])
                {
                    ok = 1;
                }
                now[j] -= 2 * k;
                now[j] = (now[j] % 10 + 10) % 10;
                if(now[1] == mode[i][1] && now[2] == mode[i][2] && now[3] == mode[i][3] && now[4] == mode[i][4] && now[5] == mode[i][5])
                {
                    ok = 1;
                }
                now[j] += k;
                now[j] %= 10;

            }
        }
        for(int j = 1 ; j <= 4 ; j++)
        {
            for(int k = 1 ; k <= 9 ; k++)
            {
                now[j] += k;
                now[j + 1] += k;
                now[j] %= 10;
                now[j + 1] %= 10;
                if(now[1] == mode[i][1] && now[2] == mode[i][2] && now[3] == mode[i][3] && now[4] == mode[i][4] && now[5] == mode[i][5])
                {
                    ok = 1;
                }
                now[j] -= 2 * k;
                now[j + 1] -= 2 * k;
                now[j] = (now[j] % 10 + 10) % 10;
                now[j + 1] = (now[j + 1] % 10 + 10) % 10;
                if(now[1] == mode[i][1] && now[2] == mode[i][2] && now[3] == mode[i][3] && now[4] == mode[i][4] && now[5] == mode[i][5])
                {
                    ok = 1;
                }
                now[j] += k;
                now[j + 1] += k;
                now[j] %= 10;
                now[j + 1] %= 10;
            }
        }
        if(!ok)
        {
            return 0;
        }
    }
    return 1;
}
signed main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> mode[i][1] >> mode[i][2] >> mode[i][3] >> mode[i][4] >> mode[i][5];
    }
    int ans = 0;
    for(int i = 0 ; i <= 99999 ; i++)
    {
        ans += check(i);
    }
    cout << ans << endl;
}

::::

还有一个显然的方法，就是从每个终止状态反推出有多少个密码可以转出这个终止状态，最后统计有多少个密码可以转出所有终止状态即可。

::::info[CSP-S 2023 A2]

int n;
int cnt[100005];
int turn(int a[])
{
    return (a[1] * 10000 + a[2] * 1000 + a[3] * 100 + a[4] * 10 + a[5]);
}
int cntp[100005];
void g(int nn)
{
    int now[7];
    memset(cntp , 0 , sizeof(cntp));
    for(int i = 5 ; i >= 1 ; i--)
    {
        now[i] = nn % 10;
        nn /= 10;
    }
    for(int i = 1 ; i <= 5 ; i++)
    {
        for(int j = 1 ; j <= 9 ; j++)
        {
            int bef = now[i];
            now[i] = (now[i] + j) % 10;
            cntp[turn(now)] = 1;
            now[i] = bef;
        }
    }
    for(int i = 1 ; i <= 4 ; i++)
    {
        for(int j = 1 ; j <= 9 ; j++)
        {
            int bef1 = now[i] , bef2 = now[i + 1];
            now[i] = (now[i] + j) % 10;
            now[i + 1] = (now[i + 1] + j) % 10;
            cntp[turn(now)] = 1;
            now[i] = bef1;
            now[i + 1] = bef2;
        }
    }
    for(int i = 0 ; i <= 99999 ; i++)
    {
        cnt[i] += cntp[i];
    }
}
signed main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        int _ , __ , ___ , ____ , _____;
        cin >> _ >> __ >> ___ >> ____ >> _____;
        g(_ * 10000 + __ * 1000 + ___ * 100 + ____ * 10 + _____);
    }
    int ans = 0;
    for(int i = 0 ; i <= 99999 ; i++)
    {
        ans += (cnt[i] == n);
    }
    cout << ans << endl;
}

::::

B P9753 [CSP-S 2023] 消消乐

容易发现这个操作过程其实就是栈。我们需要做一个转化：如果一段区间可以被消掉，那么这段区间第一个元素加入之前和最后一个元素加入之后的栈内元素应该是一样的。因为我们无法储存整个字符串，所以就可以把它变成一个数。虽然小概率会冲突（就是不同的两个字符串对应了一个相同的数），但只要你写的够好，出题人就很难卡你。

这种做法纯粹是栈的部分，其实只有模拟整个游戏过程。当然在加入和弹出字符的时候也需要顺带着把字符和哈希值打成一个 pair < char , unsigned long long > 一起存储，当然你把字符转成数字也可以，反正需要同时存下哈希值。

同时存下哈希值的原因也很简单，因为 unsigned long long 的溢出是不可逆的，这就导致如果减完再乘上逆元，会得到一个错误的结果，此时就需要存下哈希值。

哈希过程怎么样都行，只要出题人没卡到你就行了。我的方法是乘上 27，然后对于 'a' 到 'z' 的每个字母都随便敲了一个数字，在乘完 27 之后就加上这个数字，然后用 unsigned long long 自然溢出即可。

::::info[CSP-S 2023 B]

stack < pair < unsigned long long , long long > > s;
unsigned long long a[2000005];
unsigned long long ch[2000005] = {
    231   , 353   , 745   , 1043  , 1353  , 1636  ,
    1983  , 2435  , 3646  , 4649  , 5301  , 6942  ,
    7342  , 8823  , 8934  , 9342  , 9643  , 11435 ,
    12535 , 13546 , 14636 , 15342 , 16438 , 17232 ,
    18235 , 19532 , 20024 , 21534 , 22489 , 23908};
map < unsigned long long , long long > mp;
signed main()
{
    long long n;
    cin >> n;
    for(long long i = 1 ; i <= n ; i++)
    {
        char character;
        cin >> character;
        a[i] = character - 'a' + 1;
    }
    unsigned long long hash = 0;
    for(long long i = 1 ; i <= n ; i++)
    {
        unsigned long long fst = (s.size() ? s.top().second : -1);
        if(fst == a[i])
        {
            s.pop();
            if(!s.size())
            {
                hash = 0;
            }
            else
            {
                hash = s.top().first;
            }
        }
        else
        {
            hash *= 27;
            hash += ch[a[i]];
            s.push(make_pair(hash , a[i]));
        }
        mp[hash]++;
    }
    long long ans = 0;
    mp[0]++;
    for(pair < unsigned long long , long long > i : mp)
    {
        ans += i.second * (i.second - 1) / 2;
    }
    cout << ans;
    return 0;
}

::::

D P9755 [CSP-S 2023] 种树

首先，我们可以把每天树生长的长度分析一下，拆掉 \max 符号后发现，只有当 c_i < 0 且 b_i + x \times c_i < 1 时，树会稳定每天生长 1 米，否则都是生长 b_i + x \times c_i 米。

直觉告诉我们，这道题一定需要大量求类似于 l \sim r 这段时间内第 i 棵树生长的高度的问题。为了方便表述，不妨先表示出 M = \lfloor \dfrac{1 - b_i} {c_i} \rfloor，即最大的满足 b_i + x \times c_i \ge 1 的值。那么由等差数列的求和公式，我们不难得到 l \sim r 这段时间内第 i 棵树生长的高度的公式。

r - l + 1 , & M < l \\ b_i \times (r - l + 1) + \dfrac {c_i \times (r - l + 1) \times (l + r)} 2 , & M > r \\ b_i \times(M - l + 1) + \dfrac {c_i \times (M - l + 1) \times (l + M)} 2 + r - M , & M \in [l , r] \end{cases}

对于求答案，我们不妨使用二分。因为对于小的答案，其种树方案同样适用于更大的答案。而对于一个给定的答案，我们需要判断是否存在一种方案使得能完成任务。

对于这个部分，我们一定是从 1 号点出发向外扩散，直到所有叶子都种上树为止。这个过程中我们不好判断下一步种哪棵树最优，因为我们不单单需要考虑一个点，而是需要考虑一整棵子树，然后情况就会变得很复杂。这个时候不如倒着考虑拔掉每棵树，情况就会变得很简单。此时就是考虑每棵树最晚能什么时候被种下，所以在上述 calc(i , l , r) 的基础上，我们再写一层二分 get(i , r , need) 表示第 i 棵树生长到第 r 天的高度不低于 need 时，最晚可以第几天种下这棵树。然后我们把这个值从最晚的开始拔，一直倒着拔回第一棵树，然后同时标记一下每棵树是第几个被拔掉的。

显然按照被拔掉的顺序从最后到最前作为种树顺序一定是不劣的，而且提前种上某棵树不会影响答案。所以我们真正的种树策略应该是第 1 \sim n 天按顺序种树，这个时候我们判断一下每棵树被种下的时间是否不大于要求的时间，否则就说明不可行。

还有一些基本的 dfs 等内容不多说了。

:::info[CSP-S 2023 D]

#define INT __int128
pair < long long , pair < int , int > > a[100005];
long long xmax[100005];
vector < int > v[100005];
int fa[100005];
int in[100005];
int n;
long long calc(int p , int st , int ed);
long long get(int p , int ed , long long need);
bool check(long long maxD);
void dfs(int now , int f)
{
    fa[now] = f;
    for(int i : v[now])
    {
        if(i == f)
        {
            continue;
        }
        dfs(i , now);
        in[now]++;
    }
}
signed main()
{
    read(n);
    for(int i = 1 ; i <= n ; i++)
    {
        read(a[i].first , a[i].second.first , a[i].second.second);
        if(a[i].second.second < 0)
        {
            xmax[i] = (a[i].second.first - 1) / (-a[i].second.second);
        }
        else
        {
            xmax[i] = LONG_LONG_MAX;
        }
    }
    for(int i = 1 ; i < n ; i++)
    {
        int x , y;
        read(x , y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1 , 0);
    long long l = n , r = 1e9;
    long long ans = 1e9;
    while(l <= r)
    {
        long long mid = (l + r) >> 1;
        bool chk = check(mid);
        if(chk)
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    printnl(ans);
    return 0;
}
long long calc(int p , int st , int ed)
{
    INT y = a[p].second.first , z = a[p].second.second;
    if(xmax[p] < st)
    {
        return (ed - st + 1);
    }
    else if(xmax[p] > ed)
    {
        INT ans = y * (ed - st + 1) + z * (st + ed) * (ed - st + 1) / 2;
        return min(ans , (INT) 2e18);
    }
    else
    {
        INT ans = (ed - xmax[p]) + y * (xmax[p] - st + 1) + z * (st + xmax[p]) * (xmax[p] - st + 1) / 2;
        return min(ans , (INT) 2e18);
    }
}
long long get(int p , long long ed , long long need)
{
    if(calc(p , 1 , ed) < need)
    {
        return -1;
    }
    long long l = 1 , r = ed , ans = 1;
    while(l <= r)
    {
        long long mid = (l + r) >> 1;
        if(calc(p , mid , ed) >= need)
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return ans;
}
bool check(long long maxD)
{
    vector < int > nowsiz(in , in + n + 1);
    vector < long long > ord(n + 1);
    vector < long long > mind(n + 1);
    priority_queue < pair < long long , int > > q;
    for(int i = 1 ; i <= n ; i++)
    {
        mind[i] = get(i , maxD , a[i].first);
        if(mind[i] == -1)
        {
            return 0;
        }
        if(nowsiz[i] == 0)
        {
            q.push(make_pair(mind[i] , i));
        }
    }
    int lst = n;
    while(q.size())
    {
        pair < long long , int > b = q.top();
        q.pop();
        ord[lst--] = b.second;
        nowsiz[fa[b.second]]--;
        if(nowsiz[fa[b.second]] == 0)
        {
            q.push(make_pair(mind[fa[b.second]] , fa[b.second]));
        }
    }
    for(long long i = 1 ; i <= n ; i++)
    {
        if(i > mind[ord[i]])
        {
            return 0;
        }
    }
    return 1;
}

::::