A. Clam and Fish

签到。题意比较麻烦，注意桌子上只有饵料的时候也可以不拿，利用之前的饵料钓鱼

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

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n; scanf("%d",&n);
        string s; cin >> s;
        int ans = 0, er = 0;
        for(int i=0;i<n;i++) {
            if(s[i]=='0'&&er) ans++,er--;
            if(s[i]=='1') er++;
            if(s[i]=='2'|| s[i]=='3') ans++;
        }
        ans += er/2; //这一行是关键，把所有之前收饵料的环节的一半用来钓鱼，保证最大化
        printf("%d\n",ans);
    }
}

B. Classical String Problem

题意

两种操作，A x 代表输出字符串第x个字符，M x代表将字符串左移位/右移位x个位置。

解题

签到，本质是下标取模。注意由于字符串长度和询问组数比较多，所以变化量delta需要取模防止溢出。同时cin/cout可能超时。

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

int main() {
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    int len = s.length();
    int t; cin >> t;
    int d = 0;
    while(t--) {
        char a; cin >> a;
        int b; cin >> b;
        if(a=='A') cout<<s[(b-1+d)%len]<<endl;
        else d+=len+b;
        d = d%len+len;
    }
}

C. Operation Love

根据固定的几何图形判断左右手。比赛时由于精度过高一直WA。思路就是先判断好四个关键点，之后再根据左手和右手底边到下一条边叉积的正负不同来进行判断。注意，精度1e-4可以通过，但是更高的精度将无法通过。

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-4;
struct point {
    double x,y;
}data[25];

double dis(point aa, point bb) {
    return sqrt((aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y));
}

double cross(point aa, point bb, point cc) {
    return (bb.x-aa.x)*(cc.y-aa.y)-(cc.x-bb.x)*(bb.y-aa.y);
}

int same(double a, double b) {
    if(fabs(a-b)<eps) return 1;
    return 0;
}

int main() {
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d", &t);
    while(t--) {
        for(int i=0;i<20;i++) {
            scanf("%lf%lf", &data[i].x, &data[i].y);
        }    
        int d1=0, d2=0, d3=0, flag=0;
        for(int i=0;i<20;i++) {
            d1=i,d2=(i+1)%20,d3=(i+2)%20;
            if(same(dis(data[d1],data[d2]), 9)) {
                if(cross(data[d1],data[d2],data[d3]) > 0 && same(dis(data[d2],data[d3]),6) ||
                   cross(data[d1],data[d2],data[d3]) < 0 && same(dis(data[d2],data[d3]),8))  {
                       puts("left"); flag=1; break;
                }
            }
        }
        if(!flag) puts("right");
    }
}

F. Fraction Construction Problem

题意

给定正整数 ，
求，满足

数据范围

解题

化简得
首先若ab不互质，则可以轻松构造出一组解d=b/gcd(a,b), f=1
ab互质，则将b分解为互质的两个数之积（不互质则ab不互质），之后根据exgcd求解方程，注意符号的正负，暴力卡过去。
要尽量把不必要的long long开成int防止超时

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

inline int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

inline ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a%b, x, y);
    ll z = x;
    x = y;
    y = z - y * (a/b);
    return d;
}

int a, b, d, f;
ll c, e;

int main() {
//    freopen("in.txt", "r", stdin);
    int t;
    scanf("%d",&t);
    while(t--) {
        scanf("%lld%lld",&a,&b);
        int g = gcd(a,b);
        if(b == 1) printf("-1 -1 -1 -1\n");
        else if(g!=1) {
            printf("%d %d %d %d\n",(a+b)/g,b/g,1,1);
        } else {
            int flag = 0;
            for(int i=2; i*i<b; i++) {
                if(b%i==0 && gcd(i,b/i)==1) {
                    d = i;
                    f = b/i;
                    flag = 1;
                    break;
                }
            }
            if(!flag) printf("-1 -1 -1 -1\n");
            else {
                exgcd(f, d, c, e);
                c *= 1LL*a;
                e *= 1LL*a;
                if(c > 0 && e < 0)
                    printf("%lld %d %lld %d\n",c,d,-e,f);
                else 
                    printf("%lld %d %lld %d\n",e,f,-c,d);
            }
        }
    }
}

G. Operating on a Graph

题意

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

解题

并查集

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
vector <int> a[maxn], temp;
int fa[maxn];
void init(int n) {
    for(int i = 0; i<=n; i++) fa[i]=i;
}
int find(int x) {
    return (fa[x] == x)?x:fa[x] = find(fa[x]);
}
int n,m,x,y,q,o,t;

int main() {
//    freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        init(n);
        for(int i=0;i<=n;i++) a[i].clear();
        while(m--) {
            scanf("%d%d",&x,&y);
                a[x].push_back(y),
                a[y].push_back(x);
        }
        scanf("%d",&q);
        while(q--) {
            scanf("%d",&o);
            if(fa[o]!=o) continue; // 不存在这种颜色，直接取消操作
            temp = a[o];
            a[o].clear(); 
            for(int i=0;i<temp.size();i++) { // 遍历每个相邻的点
                int f = find(temp[i]);
                if(f != o) {
                    fa[f] = o;
                    // 本质上就是合并两个动态数组a[o]和a[f]
                    if(a[o].size()<a[f].size())
                        swap(a[o],a[f]);
                    for(int j=0; j<a[f].size(); j++)
                        a[o].push_back(a[f][j]);
                }
            }
        }
        for(int i=0;i<n;i++) {
            printf("%d ", find(i));
        }
        printf("\n");
    }
}

L. Problem L is the Only Lovely Problem

签到。判断字符串首是否有lovely，用了个新学的函数。

string :: find(string substring)
返回字符串在母串中的起始下标位置（下标记录），如果没有找到，那么会返回s.npos