A.Protect Sheep

题意就是给你一个$n*m$的农场，有羊和狼，你可以在任意空位放牧羊犬，使得狼不能走放了牧羊犬的位置，求让所有羊都不被吃的方案，不存在就输出$No$

贪心地把所有空位都放置牧羊犬，然后这时显然狼已经不能动了，再看狼的四邻域是否存在羊即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int T;scanf("%d",&T);for (int q=1; q<=T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 510;
char s[N][N];

int main(void)
{
    int n, m, i, j;
    cin >> n >> m;
    for (i = 1; i <= n; ++i)
    {
        scanf("%s", s[i] + 1);
        for (j = 1; j <= m; ++j)
        {
            if (s[i][j] == '.')
                s[i][j] = 'D';
        }
    }
    int flag = 0;
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= m; ++j)
        {
            if (s[i][j] == 'W' && (s[i + 1][j] == 'S' || s[i - 1][j] == 'S' || s[i][j + 1] == 'S' || s[i][j - 1] == 'S'))
            {
                flag = 1;
                break;
            }
        }
    }
    if (flag)
        puts("No");
    else
    {
        puts("Yes");
        for (i = 1; i <= n; ++i)
            puts(s[i] + 1);
    }
    return 0;
}

B.Primal Sport

题意就是给你一种构造方案和$X_2$，找到一个符合构造方案的最小的$X_0$

比赛的时候没做出来，看了题解发现主要还是找规律，用$P_i$表示$X_i$的最大素因子，可以发现每一次都是从$[X_i-P_i+1,X_i]$中找到一个素数去构造$X_{i+1}$，由于要让$X_0$尽量小，那么往回推的时候找的素数应该尽量地大，然后就枚举$X_1$，$X_0$要最小肯定取$X_1-P_1+1$即可，$P$数组用欧拉筛得到即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int T;scanf("%d",&T);for (int q=1; q<=T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e6 + 7;

int prime[N];

void init()
{
    prime[0] = 0, prime[1] = 0;
    for (register int i = 2; i < N; ++i)
    {
        if (!prime[i])
        {
            prime[i] = i;
            for (register int j = i << 1; j < N; j += i)
                prime[j] = i;
        }
    }
}
int main(void)
{
    init();
    int n;
    while (~scanf("%d", &n))
    {
        int ans = INF;
        for (int x1 = n - prime[n] + 1; x1 <= n; ++x1)
        {
            if (x1 - prime[x1] + 1 <= 1)
                continue;
            ans = min(ans, x1 - prime[x1] + 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}

C.Producing Snow

题意就是给你$n$天，每一天你会造体积为$V_i$的雪，然后每天的温度会达到$T_i$度，所有存在的雪堆均会融化体积$T_i$（体积不够化就直接变成$0$），问你每一天一共融化了多少体积的雪

比赛的时候也没做出来，考虑的方向错了，考虑每一个雪堆，它的融化体积过程总是先被经过几天融化没化完，最后到某一天完全融化到$0$，那么我们对每一个雪堆二分一个它没融化完的最后一天，然后在这天的后一天把剩余的全部加，即算每一个雪堆对它后面的天数的贡献，然后用差分数组标记一下，~~写线段树的时候用的区间最大最小值剪枝，知道肯定会被凹凸凹凸的数据卡，不写又不行~~

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int T;scanf("%d",&T);for (int q=1; q<=T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
LL V[N], T[N], pt[N];
LL res[N], cnt[N];

inline LL sum(int l, int r)
{
    return pt[r] - pt[l - 1];
}
int main(void)
{
    int n, i;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        scanf("%I64d", V + i);
    }
    for (i = 1; i <= n; ++i)
    {
        scanf("%I64d", T + i);
        pt[i] = pt[i - 1] + T[i];
    }
    for (i = 1; i <= n; ++i)
    {
        int l = i, r = n, x = i - 1;
        while (l <= r)
        {
            int mid = MID(l, r);
            if (V[i] >= sum(i, mid))
            {
                x = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        ++cnt[i];
        --cnt[x + 1];
        res[x + 1] += V[i] - sum(i, x);
    }
    for (i = 1; i <= n; ++i)
    {
        cnt[i] += cnt[i - 1];
        printf("%I64d%c", cnt[i]*T[i] + res[i], " \n"[i == n]);
    }
    return 0;
}

D.Perfect Security

题意就是给你一个序列$A$和序列$B$，让每一个$A_i$都去异或一个$B_j$，使得构造出来的$A’$序列字典序最小，每个$B_j$只能用一次。

一开始被BC搞方了，根本没去看这题，最后有人说这题水题才去看的。由于要让字典序最小，肯定是贪心地让越前面的$A_i$越小，然后这就是很模板的$01$字典树了，燃鹅常见的是用来求异或最大值的，最小值的话就把正反两路的策略换一下就行了；最后针对$B_j$只能用一次的条件，加一个路径覆盖次数，加数的时候把整个路径所有点权加$1$，取出来的时候把这个数的路径所有点权$-1$，代表把这个数删掉了，每次只走路径权值大于$0$的点即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int T;scanf("%d",&T);for (int q=1; q<=T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 300005;
struct Trie
{
    int nxt[2], cnt, v;
    void init() {
        nxt[0] = nxt[1] = 0;
        cnt = v = 0;
    }
} L[N * 31];
int sz;
int A[N], B[N];

void init()
{
    sz = 0;
    L[sz++].init();
}
inline int newnode()
{
    L[sz].init();
    return sz++;
}
void ins(int val)
{
    int u = 0;
    for (int i = 30; i >= 0; --i)
    {
        int v = (val >> i) & 1;
        if (!L[u].nxt[v])
            L[u].nxt[v] = newnode();
        u = L[u].nxt[v];
        ++L[u].cnt;
    }
    L[u].v = val;
}
void update(int val, int c)
{
    int u = 0;
    for (int i = 30; i >= 0; --i)
    {
        int v = (val >> i) & 1;
        u = L[u].nxt[v];
        L[u].cnt += c;
    }
}
int query(int val)
{
    int u = 0;
    for (int i = 30; i >= 0; --i)
    {
        int v = (val >> i) & 1;
        if (L[L[u].nxt[v]].cnt)
            u = L[u].nxt[v ];
        else
            u = L[u].nxt[v ^ 1];
    }
    return L[u].v;
}
int main(void)
{
    int n, i;
    scanf("%d", &n);
    init();
    for (i = 1; i <= n; ++i)
        scanf("%d", &A[i]);
    for (i = 1; i <= n; ++i)
    {
        scanf("%d", &B[i]);
        ins(B[i]);
    }
    for (i = 1; i <= n; ++i)
    {
        int v = query(A[i]);
        update(v, -1);
        A[i] ^=  v;
    }
    for (i = 1; i <= n; ++i)
        printf("%d%c", A[i], " \n"[i == n]);
    return 0;
}

E.Picking Strings

题意就是给你三种变换规则和$S$串，$T$串，$Q$个询问，每次问你能否把$S_{a…b}$变换到$T_{c…d}$。

脑洞+分类讨论神题，通过这三个变换规则可以发现

$B$和$C$等价，直接把字符串中所有$C$变成$B$即可。
$AAA \to empty$，好吧这是题目给的条件，不过也比较重要
$A \to BB$，即$A$可以构造偶数个$B$。
$B \to AB$，加上上面这条，又可以得到：$B \to BBB$，即$B$可以加上任意偶数个$B$。
$AB \to B$，即$B$前面的$A$可以直接消掉。
$B$不能被消掉，$B$后面的$A$字符不能被构造出来，即作为后缀的$A$只能减少不能增加。

然后就可以得到以下不能被构造的情况：

$S$的$B$比$T$的$B$多，或$S$和$T$的$B$字符差不为偶数。
$S$的后缀$A$比$T$的少。
$S$和$T$的$B$相同但是多出来的$A$不为$3$的倍数，即不能通过规则$3$被消掉
并没有多出来的$A$去构造一个$B$且$S$串也不存在$B$去构造$B$。

代码：

#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int T;scanf("%d",&T);for (int q=1; q<=T; ++q)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
char s[N], t[N];
int cbs[N], cbt[N], cas[N], cat[N];
char ans[N];

void debug(int l, int r, char S[])
{
    for (int i = l; i <= r; ++i)
        putchar(S[i]);
    puts("");
}
int main(void)
{
    int i, n, m, a, b, c, d, q;
    while (~scanf("%s%s", s + 1, t + 1))
    {
        n = strlen(s + 1), m = strlen(t + 1);
        for (i = 1; i <= n; ++i)
        {
            if (s[i] == 'C')
                s[i] = 'B';
            cbs[i] = cbs[i - 1] + (s[i] == 'B');
            cas[i] = s[i] == 'A' ? cas[i - 1] + 1 : 0;
        }
        for (i = 1; i <= m; ++i)
        {
            if (t[i] == 'C')
                t[i] = 'B';
            cbt[i] = cbt[i - 1] + (t[i] == 'B');
            cat[i] = t[i] == 'A' ? cat[i - 1] + 1 : 0;
        }
        scanf("%d", &q);
        for (int i = 0; i < q; ++i)
        {
            scanf("%d%d%d%d", &a, &b, &c, &d);
            int CBS = cbs[b] - cbs[a - 1], CBT = cbt[d] - cbt[c - 1];
            if (CBS > CBT || ((CBT - CBS) & 1))//S的'B'比T多或者不能通过+2k个B补成T
                ans[i] = '0';
            else//用多出来的A补
            {
                int CAS = min(b - a + 1, cas[b]), CAT = min(d - c + 1, cat[d]);
                int resA = CAS - CAT;
                if (resA < 0)//S的后缀连续A比T少
                    ans[i] = '0';
                else
                {
                    if (CBS == CBT)//B相同，消掉一部分A
                        ans[i] = resA % 3 == 0 ? '1' : '0';
                    else
                        ans[i] = (resA || CBS) + '0';
                }
            }
        }
        puts(ans);
    }
    return 0;
}

Blackops

CF #470 Div.2题解

A.Protect Sheep

代码：

B.Primal Sport

代码：

C.Producing Snow

代码：

D.Perfect Security

代码：

E.Picking Strings

代码：