前言

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/cfround653/

概述

赛后一天补题，虚拟参赛，2h只写完了前四题，E1没调出来，结束后看数据才调好。
整体难度不大，不少靠猜结论，E2实现有点麻烦。

CF1374A Required Remainder

求 $\max k \in [0,n],k \equiv y \pmod{x}$，多组数据。

即：$k = i \times x + y$，要求 $i$ 最大。不考虑 $y$ 时，$\max i = \left \lfloor \dfrac{n}{x} \right \rfloor$，代回计算，可以依次减 $x$ ，满足 $k \leq n$ 时即为答案。

其中 $y < x$，因此当 $\left \lfloor \dfrac{n}{x} \right \rfloor \times x + y > n$ 时，$(\left \lfloor \dfrac{n}{x} \right \rfloor – 1) \times x + y< n$ 一定成立。

#include <cstdio>
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
int T;
long long x,y,n;
int main()
{
    read(T);
    while(T--)
    {
        read(x),read(y),read(n);
        long long p = (n / x) * x + y;
        if(p > n) p -= x;
        printf("%lld\n",p);
    }
    return 0;
}

CF1374B Multiply by 2, divide by 6

给定 $n$，可以 $\div 6$ 或 $\times 2$，问几步后可得到 $1$。

顺序不会影响答案，若答案存在，则 $n \div 6^a \times 2^b = 1$，求 $a + b$。

化简为 $n \div 6^{a-b} \div 3^b = 1$，$\times 2 \div 6 = \div 3$ 计算两步贡献，直接统计。

#include <cstdio>
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
int T;
long long x;
int main()
{
    read(T);
    while(T--)
    {
        read(x);
        long long ans = 0;
        while(x % 6 == 0) ++ans, x /= 6;
        while(x % 3 == 0) ans += 2,x /= 3;
        if(x == 1) printf("%lld\n",ans);
        else puts("-1");
    }
    return 0;
}

CF1374C Move Brackets

给一个括号序列，每次可将任意括号移至首尾，求最少步数后括号串合法。

将左括号看做 $1$，右括号看做 $-1$，要求任意位置前缀和非负，即括号匹配。数据保证有解。

途中某位置前缀和为 $-1$ 时，将当前右括号移至末尾，统计答案，再将前缀和归零。

大致证明：

当前串设为 $s_1 + ) + s_2$，其中 $s_1$ 有 $a$ 个左括号，$a$ 个右括号，那么 $s_2$ 中有 $n – 2 \times a – 1$ 个括号，其中 $(n – 2 \times a) \div 2$ 是左括号，$(n – 2 \times a) \div 2 – 1$ 是右括号，将该右括号移至末尾一定能与某左括号匹配。

数据范围比较仁慈，把 $O(n^2)$ 做法放过去了，实际上无须真的移到末尾。

#include <cstdio>
const int maxn = 60;
int T,n;
char s[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %s",&n,s+1);
        int ans = 0,sum = 0;
        for(int i = 1;i<=n;++i)
        {
            sum += (s[i] == '(' ? 1 : -1);
            if(sum < 0) ++ans,sum = 0;
        }
        printf("%d\n",ans);
    }
    return 0;
}

CF1374D Zero Remainder Array

初始 $x = 0$，每次操作后 $+1$，两种操作：

1. $a_i += x$
2. 什么都不干

操作1对每个数最多进行一次。
求 $\forall a_i \equiv 0 \pmod{k}$ 的最小步数。
将所有数模 $k$ 处理，对于 $a_i$，$x = k – a_i$ 是唯一操作方法。
进行操作与什么都不干等代价，则能使 $a_i += x$ 时一定会进行操作。
由于 $x$ 单调递增，每次找到最小的 $x \leq a_i$，再进行计算转移，一定是最优的。
可以用set来处理。

#include <cstdio>
#include <set>
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
#define int long long
const int maxn = 2e5 + 100;
int T,n,k,a[maxn];
std::multiset<int> s;
signed main()
{
    read(T);
    while(T--)
    {
        s.clear();
        read(n),read(k);
        for(int i = 1;i<=n;++i) read(a[i]),a[i] = k - (a[i] % k);
        for(int i = 1;i<=n;++i) if(a[i] != k) s.insert(a[i]);
        int ans = 0,x = 0;
        while(!s.empty())
        {
            std::set<int>::iterator it = s.lower_bound(x);
            if(it == s.end())  ans += k - x,x = 0;//找不到则归零
            else ans += *it - x + 1,x = (*it) + 1,s.erase(it);
            x %= k;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

CF1374E1 Reading Books (easy version)

每本书都有权值，每本书可能被 A 喜欢，可能被 B 喜欢，要求选出的书中，A 与 B 都至少喜欢 $k$ 本，求最小权值和。
可以给书分类：

1. A 与 B 都不喜欢
2. A 喜欢
3. B 喜欢
4. A 与 B 都喜欢

不难发现，二人都不喜欢的书是完全无效的。
给每类书排序，做一遍前缀和。
设选 $i$ 本 A 与 B 都喜欢的书，就要选 $k – i$ 本 A 喜欢的书， $k – i$ 本 B 喜欢的书。
枚举 $i$ 求最小答案。

#include <cstdio>
#include <algorithm>
template<typename T>
void read(T &r)
{
    static char c;r=0;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(;c>='0'&&c<='9';r=(r<<1)+(r<<3)+(c^48),c=getchar());
}
const int maxn = 2e6 + 100;
int n,k;
int A[maxn],B[maxn],C[maxn],acnt,bcnt,ccnt;
long long SA[maxn],SB[maxn],SC[maxn];
int main()
{
    read(n),read(k);
    for(int i = 1;i<=n;++i)
    {
        int t,a,b;
        read(t),read(a),read(b);
        if(a && b) C[++ccnt] = t;
        else if(a) A[++acnt] = t;
        else if(b) B[++bcnt] = t;
    }
    std::sort(A + 1,A + 1 + acnt);
    std::sort(B + 1,B + 1 + bcnt);
    std::sort(C + 1,C + 1 + ccnt);
    for(int i = 1;i<=acnt;++i) SA[i] = SA[i-1] + A[i];
    for(int i = 1;i<=bcnt;++i) SB[i] = SB[i-1] + B[i];
    for(int i = 1;i<=ccnt;++i) SC[i] = SC[i-1] + C[i];
    long long ans = 1ll << 60;
    for (int i = std::max(0,k - std::min(acnt, bcnt)); i <= ccnt && i <= k; ++i) 
        ans = std::min(ans, SA[k - i] + SB[k - i] + SC[i]);
    if (ans == 1ll << 60) puts("-1");
    else printf("%lld",ans);
    return 0;
}

总结

笔者只会做水题了。E2的题解会单独发。