A.Clam and Fish

题意：

给定 $n$ 个时间，每个单位时间有四种状态: $0.$ 没蛤蜊、没鱼， $1.$ 有蛤蜊、没鱼， $2.$ 没蛤蜊、有鱼， $4.$ 有蛤蜊、有鱼。每个时间点有四种可能的动作：

若该时间点有鱼，则可以直接钓鱼。
若该时间点有蛤蜊，则可以用该蛤蛎制作一个鱼饵。
若该时间点身上有至少一个鱼饵，则可以用一个鱼饵钓一条鱼，钓完后就少了一个鱼饵。
什么事都不做。

询问最多能钓到多少条鱼

题解：

倒序遍历，记录空位的数量，如果为状态 $0$ 则空位的数量加 $1$ ，如果为状态 $3、4$ 则都直接钓鱼，鱼的数量加 $1$ ，如果为状态 $2$ ，先判断一下空位的数量是否为 $0$ ，不为 $0$ 说明当前时间制作一个鱼饵后面肯定有个空闲时间可以钓鱼，因此鱼的数量加 $1$ ，空位的数量减 $1$ ；如果空位的数量为 $0$ ，则将当前位置看成空位，以便前面的鱼饵可以在当前位置钓鱼，因此空位的数量加 $1$ 。最后鱼的数量就是所求

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e6 + 5;
const ll mod = 998244353;
char s[maxn];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        scanf("%s", s);
        int n1 = 0, ans = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            if (s[i] == '0')
                n1++;
            else if (s[i] == '1')
            {
                if (n1 == 0)
                    n1++;
                else
                    ans++, n1--;
            }
            else if (s[i] == '2' || s[i] == '3')
                ans++;
        }
        printf("%d\n", ans);
    }
}

B.Classical String Problem

题意：

给定一个字符串，有两种操作

询问第 $x$ 个字符。
把最左边的 $x$ 个字符搬到最右边或把最右边 $x$ 个字符搬到最左边。

题解：

可以把整个字符串看成一个环，那么不管是移动最左边的 $x$ 个字符还是移动最右边的 $x$ 字符本质就是改变环的起始位置，因此询问第 $x$ 个字符就是询问当前环起始位置的值+ $x-1$ 位置的值

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
const ll mod = 998244353;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    int t;
    cin >> t;
    int st = 0, len = s.length();
    while (t--)
    {
        char opt;
        int idx;
        cin >> opt >> idx;
        if (opt == 'A')
            cout << s[(st + idx - 1) % len] << "\n";
        else
        {
            if (idx >= 0)
                st = (st + idx) % len;
            else
            {
                idx = -idx;
                idx = len - idx;
                st = (st + idx) % len;
            }
        }
    }
}

C.Operation Love

题意：

给定一个机器人的手印，判断这个手印为左手还是右手

题解：

因为只存在一条边长度为 $9$ 和 $8$ ，因此可以确定手印的两条边，对两条边进行叉积，如果为正说明逆时针旋转，否则为顺时针旋转
图片说明

#include <bits/stdc++.h>
using namespace std;
const double eps=1e-5;
struct Point{
    double x,y;
}p[50];
double dist(Point a,Point b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main(){
    int t;cin>>t;
    while(t--){
        for(int i=0;i<20;i++){
            cin>>p[i].x>>p[i].y;
        }
        for(int i=0;i<20;i++){
            if(fabs(dist(p[i],p[(i+1)%20])-9)<=eps&&fabs(dist(p[(i+1)%20],p[(i+2)%20])-8)<=eps){
                reverse(p,p+20);
                break;
            }
        }
        bool flag;
        for(int i=0;i<20;i++){
            if(fabs(dist(p[i],p[(i+1)%20])-9)<=eps){
                Point a,b;
                a.x=p[i].x-p[(i+1)%20].x;
                a.y=p[i].y-p[(i+1)%20].y;
                b.x=p[(i+2)%20].x-p[(i+1)%20].x;
                b.y=p[(i+2)%20].y-p[(i+1)%20].y;
                flag = a.x * b.y - a.y * b.x > 0;
            }
        }
        puts(!flag?"left":"right");
    }
    return 0;
}

D.Points Construction Problem

题意：

在无限大的网格中，原本所有格子都是白色的，现在把其中 $n$ 个格子涂黑，使得满足格子 $x$ 和格子 $y$ 是上下左右相邻且 $x,y$ 异色的 $(x,y)$ 组数恰好为 $k$ 个( $(x,y)$ 和 $(y,x)$ 视为相同)。

题解：

首先要判断无解的情况，官方题解证明的挺好就直接贴过来了。

首先观察到 $m$ 是奇数时一定无解
考虑从某行无穷远的左端往右端通过，一定是白点->黑点->白点->黑点->白点的顺序交错，且起始和最终都一定是白点，所以每一行一定有偶数个相邻的相异色点对。对于列来说也是同要道理。
$m > 4 * n$ 一定无解因为每个黑点至多有 $4$ 个相邻的白点。
m 的下界判断
假设这 $n$ 个黑点共出现在相异的 $a$ 行和 $b$ 列，每行及每列都至少有 $2$ 个异色点对，所以至少有 $2(a+b)$ 个异色点对，且此下界能够构造出来。这 $a$ 行 $b$ 列的交集至多有 $a \times b$ 个黑点。 • 所以我们要找到 $a$ , $b$ 满足 $a \times b \geq n$ 且 $2(a + b)$ 最小。于是暴力枚举 $a, b$ 即可求出 $m$ 的最小可能值

当 $m>2n+2$ 时在对角线构造，否则则可以构造在一个 $\frac{m}{4} \times \frac{m+2}{4}$ 的矩阵内，具体构造见代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[256][256];
void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    if (m % 2 == 1 || m < 4 || m > n * 4 || (m / 4) * ((m + 2) / 4) < n)
    {
        puts("No");
        return;
    }
    puts("Yes");
    int ii = 0;
    while (m > (n * 2 + 2) && n > 0)
    {
        ii++;
        printf("%d %d\n", -ii, -ii);
        m -= 4;
        n--;
    }
    if (n == 0)
        return;
    for (int i = 1; i <= m / 4; i++)
        a[i][1] = 1;
    for (int i = 1; i <= (m + 2) / 4; i++)
        a[1][i] = 1;
    for (int i = 2; i <= m / 4; i++)
        for (int j = 2; j <= (m + 2) / 4; j++)
            a[i][j] = 0;
    n = n - (m / 2) + 1;
    int ni = 2, nj = 2;
    while (n > 0)
    {
        a[ni][nj] = 1;
        nj++;
        if (nj > (m + 2) / 4)
            ni++, nj = 2;
        n--;
    }
    for (int i = 1; i <= m / 4; i++)
        for (int j = 1; j <= (m + 2) / 4; j++)
            if (a[i][j] == 1)
                printf("%d %d\n", i, j);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.Two Matchings

题意：

定义序列 $a$ ，满足如下要求

长度为 $n$ 的序列 $a$ 由 $1,2,3...n$ 组成
$a_i \ne i$
$a_{a_i} = i$

这个排列的成本为 $\frac{\sum_{i=1}^{n}{abs(a_{i}-a_{p_i})}}{2}$ 。求两个满足上述对序列 $a$ 的描述的序列 $p,q$ 同时还要满足 $p_i \ne q_i$ 对于每一个 $i$ 都成立，则这两个排列的的成本最小值是多少

题解：

那么 $p,q$ ，一个为最小值一个为次小值。最小值很明显，将 $a$ 排序后，相邻两个匹配即可。
图片说明
再考虑次小值，在最小值的基础上，稍微改变一下，大致方案如下

由此可以发现 $4$ 个元素的次小即为 $a_4-a_2+a_3-a_1=a_4+a_3-a_2-a_1$

由此可以发现 $4$ 个元素的次小即为 $a_6-a_1+a_3-a_2+a_5-a_4=a_6+a_5+a_3-a_4-a_2-a_1$
而其余情况都可以拆分成 $4$ 和 $6$ 。因此次最小值就为 $dp_i=min(dp_{i-4}+a_i+a_{i-1}-a_{i-2}-a_{i-3},dp_{i-6}+a_{i}+a_{i-1}-a_{i-2}+a_{i-3}-a_{i-4}-a_{i-5})(i \geq 6)$ 。其中 $dp_2$ 不合法，令 $dp_2=INF$ 即可，每次取较小者不会取到包含 $dp_2$ 的贡献

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = 1e9 + 7;
ll a[maxn], dp[maxn];
int main()
{
    int t, n;
    ll ans;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        ans = 0;
        for (int i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
        sort(a + 1, a + 1 + n);
        for (int i = 2; i <= n; i += 2)
            ans += a[i] - a[i - 1];
        dp[2] = INF;
        dp[4] = a[4] + a[3] - a[2] - a[1];
        dp[6] = a[6] + a[5] - a[4] + a[3] - a[2] - a[1];
        for (int i = 8; i <= n; i += 2)
            dp[i] = min(dp[i - 4] + a[i] + a[i - 1] - a[i - 2] - a[i - 3],
                        dp[i - 6] + a[i] + a[i - 1] - a[i - 2] + a[i - 3] - a[i - 4] - a[i - 5]);
        printf("%lld\n", ans + dp[n]);
    }
}

F.Fraction Construction Problem

题意：

题解：

图片说明

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll p[maxn];
ll ex_gcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll tx, ty;
    ll g = ex_gcd(b, a % b, tx, ty);
    x = ty;
    y = tx - a / b * ty;
    return g;
}
void solve()
{
    ll a, b, c, d, e, f;
    scanf("%lld%lld", &a, &b);
    ll g = ex_gcd(a, b, e, f);
    if (g > 1)
    {
        printf("%lld %lld %lld %lld\n", a / g + 1, b / g, 1ll, b / g);
        return;
    }
    f = b;
    d = 1;
    while (p[b] > 1 && f % p[b] == 0)
    {
        d *= p[b];
        f /= p[b];
    }
    if (f == b || d == b)
    {
        printf("-1 -1 -1 -1\n");
        return;
    }
    ex_gcd(f, d, c, e);
    e = -e;
    c *= a;
    e *= a;
    if (c < 0 && e < 0)
    {
        c = -c;
        e = -e;
        swap(c, e);
        swap(d, f);
    }
    printf("%lld %lld %lld %lld\n", c, d, e, f);
}
int main()
{
    p[1] = 1;
    for (int i = 2; i < maxn; i++)
        if (p[i] == 0)
            for (int j = i; j < maxn; j += i)
                if (p[j] == 0)
                    p[j] = i;
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

G.Operating on a Graph

题意：

给定一个 $n$ 个点的图，第 $i$ 个点一刚开始是第 $i$ 种颜色，接着有 $k$ 次操作，第 $i$ 次操作有个参数 $o_i$ 代表颜色 $o_i$ 会侵略所有和自己相邻的颜色，于是所有和 $o_i$ 相邻的颜色全都变成 $o_i$ (若已没有颜色 $o_i$ 已被侵略，则该次操作无效)，求最终每个点的颜色

题解：

在所有操作过程中，对于每个点，至多只会有一次把相邻的点和自己变为同一种颜色的操作，经过该次操作后，就永远和相邻的点同色了。
因此用并查集来维护，每次判断当前点 $find(k)=k$ ，如果等于就说明这个点没有被染色过，遍历所有邻边，把所有邻边都染色，再相当于缩点，把所有邻边的邻边都与该点相邻，继续下一次操作即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 8e5 + 10;
int pre[maxn];
vector<int> edg[maxn];
inline int find(int x) { return x == pre[x] ? x : pre[x] = find(pre[x]); }
void merge(int n)
{
    vector<int> tmp = edg[n];
    edg[n].clear();
    for (int i : tmp)
    {
        int k = find(i);
        if (k != n)
        {
            pre[k] = n;
            if (edg[n].size() < edg[k].size())
                swap(edg[n], edg[k]);
            for (auto v : edg[k])
                edg[n].push_back(v);
            edg[k].clear();
        }
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; i++)
        {
            pre[i] = i;
            edg[i].clear();
        }
        for (int i = 0, u, v; i < m; i++)
        {
            cin >> u >> v;
            edg[u].push_back(v);
            edg[v].push_back(u);
        }
        int q;
        cin >> q;
        while (q--)
        {
            int k;
            cin >> k;
            if (find(k) != k)
                continue;
            merge(k);
        }
        for (int i = 0; i < n; i++)
            cout << find(i) << " ";
        cout << "\n";
    }
    return 0;
}

L.Problem L is the Only Lovely Problem

题意：

判断一个字符串是否以 $lovely$ 开头，不分大小写。

题解：

签到题，模拟即可

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++){
        if(isupper(s[i]))s[i]=s[i]-'A'+'a';
    }
    string t=s.substr(0,6);
    if(t=="lovely")puts("lovely");
    else puts("ugly");
    return 0;
}

2020牛客暑期多校训练营（第三场）