A.Chess Placing

题意就是给你$n$个黑白相间的位置，其中放$n/2$个棋子，求把所有棋子从初始位置摆放成在全白或者全黑位置最少的移动次数。

由于棋子个数固定，显然是要么全放白要么全放黑，sort一遍暴力试一下两种情况取最小值即可。

代码：

#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 pb(x) push_back(x)
#define sf(x) scanf("%d", &x)
#define all(a) (a).begin(),(a).end()
#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 complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 110;
int a[N];

int main(void)
{
    int n, i;
    sf(n);
    for (i = 1; i <= n / 2; ++i)
        scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n / 2);
    int ans = INF;
    int w = 0, pos = 2;
    for (i = 1; i <= n / 2; ++i)
    {
        w += abs(a[i] - pos);
        pos += 2;
    }
    ans = min(ans, w);
    w = 0, pos = 1;
    for (i = 1; i <= n / 2; ++i)
    {
        w += abs(a[i] - pos);
        pos += 2;
    }
    ans = min(ans, w);
    printf("%d\n", ans);
    return 0;
}

B.Switches and Lamps

题意就是给你$n$个开关，各自控制$m$盏灯中某些灯，问是否能不按某一个开关使得按下剩下的开关后所有的灯都会打开（灯一开始全部关闭且打开后不会再关闭）。

暴力检查一下是否剩余的开关能控制到所有$m$盏灯。

#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 pb(x) push_back(x)
#define sf(x) scanf("%d", &x)
#define all(a) (a).begin(),(a).end()
#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 complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 2005;
char s[N][N];
int n, m;
int sz[N];

int main(void)
{
    int i, j;
    sf(n), sf(m);
    for (i = 0; i < n; ++i)
    {
        scanf("%s", s[i]);
        for (j = 0; j < m; ++j)
        {
            if (s[i][j] == '1')
                ++sz[j];
        }
    }
    for (i = 0; i < n; ++i)
    {
        int ig = 1;
        for (j = 0; j < m; ++j)
            if (s[i][j] == '1')
                --sz[j];
        for (j = 0; j < m; ++j)
        {
            if (sz[j] == 0)
            {
                ig = 0;
                break;
            }
        }
        if (ig)
        {
            puts("YES");
            return 0;
        }
        else
        {
            for (j = 0; j < m; ++j)
            {
                if (s[i][j] == '1')
                    ++sz[j];
            }
        }
    }
    puts("NO");
    return 0;
}

C.Liebig’s Barrels

题意就是给你$n\times k$个木条，做$n$个水桶，每一个水桶的体积$v_i$为选择$k$条木条的最小值，且木桶的体积最大最小之差不能超过$l$，求最大的体积总和。

首先从大到小sort一下，最坏情况下用$a[nk-n+1]…a[nk]$分别作为第$i$个木桶的最小值，如果差值大于$l$说明无法构成。

否则贪心地从大到小地记录一下当前可用的木条数$res$，如果$res>=k$且当前的$a[i]-a[nk]<=l$，那么就可以把当前的$k$根木条拿去做桶且体积刚好是$a[i]$。

代码：

#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 complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
ll a[N];
int n, k, m;
ll l;

int main(void)
{
    int i;
    while (cin >> n >> k >> l)
    {
        m = n * k;
        for (i = 1; i <= m; ++i)
            scanf("%I64d", a + i);
        sort(a + 1, a + 1 + m, greater<ll>());
        if (a[m - n + 1] - a[m] > l)
        {
            return puts("0"), 0;
        }
        ll ans = 0, res = 0;
        for (i = 1; i <= m; ++i)
        {
            ++res;
            if (a[i] - a[m] <= l && res >= k)
            {
                res -= k;
                ans += a[i];
            }
        }
        printf("%I64d\n", !res ? ans : 0ll);
    }
    return 0;
}

D.Sand Fortress

题意就是给你$n$个沙袋和第一堆堆积高度的最大值$h$，求相邻堆积高度差不超过$1$的前提下最少要堆几堆。

首先可以肯定用贪心地方法去堆，由于最后要递减到$0$，因此后端一定是从最高高度$H$等差数列地下降，然后如果$H$大于$h$就还要算上左边堆砌到$H$的代价，也是一个等差数列求和。这样子二分出一个最高高度$H$，那么答案用$H$算就行了。这里有个细节就是如果右边堆砌到$H(\gt h)$，那么左边只需要堆砌到$H-1$就能接上了，不需要到$H$。

代码：

#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 complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
ll n, h;

int check(ll H)
{
    ll t = n;
    t -= (H * (H + 1ll)) / 2ll;
    if(t < 0)
        return 0;
    if(H > h)
        t -= (h + H - 1) * (H - h) / 2ll;
    if(t < 0)
        return 0;
    return 1;
}
int main(void)
{
    while (cin >> n >> h)
    {
        ll l = 1, r = 2e9 + 10ll, one = n;
        while (l <= r)
        {
            ll mid = MID(l, r);
            if(check(mid))
            {
                one = mid;
                l = mid + 1ll;
            }
            else
                r = mid - 1ll;
        }
        n -= one * (one + 1ll) / 2ll;
        ll day = one;
        if(one > h)
        {
            day += one - h + 1ll;
            n -= ((h + one) * (one - h + 1ll) / 2ll);
        }
        printf("%I64d\n", day + (ll)ceil(1.0 * n / one));
    }
    return 0;
}

E.Pencils and Boxes

给你$n$支笔和对应长度，将这些笔分成许多组，每一组的大小要大于等于$k$，且同组内长度差的最大值不能超过$d$，求是否存在这种方案。

按照题解说的有个结论，如果将笔按长度有序排好那么如果方案存在，那么用连续的区间划分一定也可以作为方案，那么用$dp[i]$表示前$i$支笔是否能成功分配，那么有$dp[i] = dp[i] \;|\; dp[j]$，其中$a[i]-a[j+1]<=d\&\&i-j \ge k$，那么就把$a$排序之后用指针实时调整到符合的位置，然后树状数组更新维护一下即可。

代码：

#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 pb(x) push_back(x)
#define sf(x) scanf("%d", &x)
#define all(a) (a).begin(),(a).end()
#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 complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 5e5 + 7;
int a[N], n, k, d;
int dp[N], T[N];

void add(int x, int v)
{
    ++x;
    while (x <= n)
    {
        T[x] += v;
        x += (x & -x);
    }
}
int sum(int x)
{
    ++x;
    int w = 0;
    while (x)
    {
        w += T[x];
        x -= (x & -x);
    }
    return w;
}
inline int S(const int  &l, const int &r)
{
    if (l > r)
        return 0;
    return sum(r) - sum(l - 1);
}
void init()
{
    clr(dp, 0);
    clr(T, 0);
}
int main(void)
{
    int i;
    while (cin >> n >> k >> d)
    {
        init();
        for (i = 1; i <= n; ++i)
            sf(a[i]);
        sort(a + 1, a + 1 + n);
        dp[0] = 1;
        add(0, 1);
        int j = 1;
        for (i = 1; i <= n; ++i)
        {
            while (a[i] - a[j] > d)
                ++j;
            if (S(j - 1, i - k))
                dp[i] = 1, add(i, 1);
        }
        puts(dp[n] ? "YES" : "NO");
    }
    return 0;
}

F.Isomorphic Strings

题意就是给你一个长度为$n$的字符串$s$和$m$个询问，问你某两个子串$S[x…x+d-1]$和$S[y…y+d-1]$是否是同构的，同构的意思就是把字符重新一一映射（置换）一下可以互相变成对方。

由于题解看不太懂，还是用别人的想法实现的，其实实现挺简单的，首先考虑如何判断字符串的同构，可以记录字符串中各个字母的出现位置，然后如果$s1$中的字符$a$和$s2$中的字符$b$出现位置集合一样，那么就可以将$a$映射到$b$，那么如果有多个字母就每个都验证一下，是否各自出现位置可以一一对应起来，那如何快速得到子串某个字母的出现位置集合信息呢？可以用$H[i][j]$表示长度为$i$的字符串字符$j$的目前所有出现位置的位置的哈希值，如果$S[i]==j$那么该位权值就是$1$否则就是$0$，这样每次把两个串的$26$个字母的位置集合哈希值都拿出来排个序看看是否可以一一对应即可。这题数据卡ull的自然溢出会WA16，~~还是某个质数好用233333~~

代码：

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define pb(x) push_back(x)
#define sf(x) scanf("%d", &x)
#define all(a) (a).begin(),(a).end()
#define clr(arr,val) memset(arr,val,sizeof(arr))
#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 = 2e5 + 7;
const ll mod = 19260817ll;
const ll bas = 1e9 + 9ll;
char s[N];
ll pre[N], H[N][26], v[2][26];
int n, m;

int check(int x, int y, int d)
{
    for (int i = 0; i < 26; ++i)
    {
        v[0][i] = (H[x + d - 1][i] - H[x - 1][i] * pre[d]) % mod;
        if(v[0][i] < 0)
            v[0][i] += mod;

        v[1][i] = (H[y + d - 1][i] - H[y - 1][i] * pre[d]) % mod;
        if(v[1][i] < 0)
            v[1][i] += mod;
    }
    sort(v[0], v[0] + 26);
    sort(v[1], v[1] + 26);
    for (int i = 0; i < 26; ++i)
        if(v[0][i] != v[1][i])
            return 0;
    return 1;
}
int main(void)
{
    int i, j;
    pre[0] = 1ll;
    for (i = 1; i < N; ++i)
        pre[i] = pre[i - 1] * bas % mod;
    sf(n), sf(m);
    scanf("%s", s + 1);
    for (i = 1; i <= n; ++i)
    {
        for (j = 0; j < 26; ++j)
        {
            H[i][j] = (H[i - 1][j] * bas + (s[i] == j + 'a' ? 1ll : 0ll)) % mod;
        }
    }
    while (m--)
    {
        int x, y, d;
        scanf("%d%d%d", &x, &y, &d);
        puts(check(x, y, d) ? "YES" : "NO");
    }
    return 0;
}

Blackops

CF Educational #44 A B C D E F