题目链接：https://atcoder.jp/contests/abc282/tasks

A – Generalized ABC

#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
const int INF=0x3f3f3f3f,MOD=998244353,P=131,N=15, M=20010;

int n, m;

void solve()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        printf("%c",i+'A');
    }
}
 
 
 
int main()
{
    #ifdef LOCAL
        freopen("D:\\Procedure\\vs_code\\in.txt","r",stdin);
    #endif
    solve();
    return 0;
}

B – Let’s Get a Perfect Score

#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
const int INF=0x3f3f3f3f,MOD=998244353,P=131,N=110, M=20010;

int n, m;
string s[N];

void solve()
{
    cin>>n>>m;
    rep(i,1,n) cin>>s[i];

    int res=0;
    rep(i,1,n){
        rep(j,i+1,n){
            bool f=true;
            rep(k,0,s[i].size()-1){
                if(s[i][k]=='o' || s[j][k]=='o') continue;
                else{
                    f=false;
                    break;
                } 
            }
            if(f) res++;
        }
    }

    cout<<res<<endl;
}
 
 
 
int main()
{
    #ifdef LOCAL
        freopen("D:\\Procedure\\vs_code\\in.txt","r",stdin);
    #endif
    solve();
    return 0;
}

C – String Delimiter

#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
const int INF=0x3f3f3f3f,MOD=998244353,P=131,N=110, M=20010;

int n, m;
string s;

void solve()
{
    cin>>n>>s;
    int res=0;
    bool f=false;
    for(int i=0;i<s.size();i++){
        if(s[i]=='"') {
            if(f) f=false;
            else f=true;
            continue;
        }

        if(!f && s[i]==',') {
            s[i]='.';
        }
    }

    cout<<s<<endl;
}
 
 
 
int main()
{
    #ifdef LOCAL
        freopen("D:\\Procedure\\vs_code\\in.txt","r",stdin);
    #endif
    solve();
    return 0;
}

D – Make Bipartite 2

题解：给你一张图，让你求加一条边使其成为二分图的方案数。（图有可能不连通或者本身就不是二分图）

考虑每一个联通的块来计算。col[i] 数组表示颜色为 v 的点数，由于同一个二分图最多就只有两种颜色，因此总点数为 $col[i]+col[i+1]$。

1. 在一个连通块内加边，加边方案数=二分图两边点数量相乘-边数。公式表示为：$$S_1=col[i]*col[i+1]-cnt$$，由于边数最终之和为 $m$，所以可以等最后再减 m 就行了
2. 在连通块之间加边，加边方案数=该联通块内点数*（总点数-该联通块内点数）公式表示为：$$S_2=(col[i]+col[i+1])*n$$（ps：前面计算过的就不用计算了，比如a连b，b连a是同一种方案。

• 用这种方法一定要col数组一定要开两倍点数的大小，血的教训！！！

#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
const int INF=0x3f3f3f3f,MOD=998244353,P=131,N=200010, M=2*N;

int n, m;
int e[M], ne[M], h[N], idx;
int st[N];
LL col[2*N]; 

void add(int a, int b)
{
    e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}

bool dfs(int u, int fa, int v) //染色法
{
    if(st[u]!=-1 && v!=st[u]) return false;
    if(st[u]!=-1) return true;
    st[u]=v, col[v]++;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=fa){
            if(!dfs(j, u, v^1))
                return false;
        }
    }

    return true;
}

void solve()
{
    cin>>n>>m;
    memset(h, -1, sizeof h);
    memset(st, -1, sizeof st);
    
    rep(i,1,m){
        int a,b; scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    int f=1, pa=0;
    for(int i=1;i<=n;i++)
    {
        if(st[i]==-1) {
            f&=dfs(i, -1, pa);
            pa+=2;
        }
    }

    if(f) { //存在
        LL s=0, res=0;
        for(int i=0;i<pa;i+=2)
        {
            s+=col[i]*col[i+1]; //块内方案
            n-=col[i]+col[i+1];
            res+=(col[i]+col[i+1])*n; //块外方案
        }
        cout<<s-m+res<<endl;
    } else puts("0");
}
 
 
int main()
{
    #ifdef LOCAL
        freopen("D:\\Procedure\\vs_code\\in.txt","r",stdin);
    #endif
    solve();
    return 0;
}

E – Choose Two and Eat One

• 这题气的我脑血栓，看出是图论题：走所有边走一遍求最长路。然而一顿操作在用dijkstra搞最长（短）路。（下意识以为最长的一个dist就是走完所有边，忽略了生成树这茬了）

题解

说到这份上了，可以抽象题目出来发现要选出 n-1 个点，每次选出都有一个权值，要让总和最大，就容易看出是最大生成树问题。

#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
const int INF=0x3f3f3f3f,MOD=998244353,P=131,N=510, M=2*N;

int n, m, a[N];
LL dist[N];
int pre[N], cnt;

int find(int x)
{
    return x==pre[x]?x:pre[x]=find(pre[x]);
}

struct Node
{
    int a, b, w;
    bool operator < (const Node &oo)
    {
        return w>oo.w;
    };
}edge[N*N];

int qmi(int a, int b)
{
    LL res=1;
    while(b)
    {
        if(b&1) res=res*a%m;
        a=(LL)a*a%m;
        b>>=1;
    }
    return res%m;
}

void solve()
{
    cin>>n>>m;
    rep(i,1,n) pre[i]=i;
    rep(i,1,n){
        scanf("%d", &a[i]);
        rep(j,1,i-1){
            //预处理每两个点之间的边
            edge[cnt++]={i,j,(qmi(a[i], a[j])+qmi(a[j], a[i]))%m}; 
        }
    }

    sort(edge, edge+cnt);

    LL res=0;
    rep(i,0,cnt-1){
        int pa=find(edge[i].a), pb=find(edge[i].b), w=edge[i].w;
        if(pa!=pb){
            pre[pa]=pb;
            res+=w;
        }
    }

    cout<<res<<endl;
}
 
 
int main()
{
    #ifdef LOCAL
        freopen("D:\\Procedure\\vs_code\\in.txt","r",stdin);
    #endif
    solve();
    return 0;
}