The 2023 ICPC Asia Regionals Online Contest (1)

A Qualifiers Ranking Rules

思路：按位次为第一关键字，场次为第二关键字排序即可。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,m;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>m;
    set<string>s;
    vector<pair<array<int,2>,string>>v;
    int cnt = 0;
    for(int i = 1;i <= n;i++)
    {
        string x;
        cin>>x;
        if(s.find(x)==s.end())
            v.push_back({{++cnt,1},x});
        s.insert(x);

    }
    cnt = 0;
    s.clear();
    for(int i = 1;i <= m;i++)
    {
        string x;
        cin>>x;
        if(s.find(x)==s.end())
            v.push_back({{++cnt,2},x});
        s.insert(x);

    }
    sort(v.begin(), v.end());
    s.clear();
    for(auto [i,x]:v)
    {
        if(s.find(x)==s.end())
            cout<<x<<"\n";
        s.insert(x);
    }

    return 0;
}

D Transitivity

思路：\(n\)个点构成完全图需要\(\dfrac{(n-1)n}{2}\)条边。

如果这个连通块不是完全图，那么答案加上\(\dfrac{(n-1)n}{2}-m\)(m是当前连通块边数)

如果全都是完全图呢？由于至少连一条边，那么我们考虑选两个点数最少的使得它们成为完全图。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
ll fa[N],ret[N],d[N],sz[N];
bool vis[N];
int find(int x)
{
    if(x==fa[x])return x;
    return fa[x] = find(fa[x]);
}
ll fx(ll x)
{
    return (x-1)*x/2;
}
vector<pair<int,int>>vec;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i = 1;i <= n; i++)
        fa[i] = i,sz[i] = 1;
    for(int i = 1;i <= m; i++)
    {
        int u,v;
        cin>>u>>v;
        d[u]++,d[v]++;
        vec.push_back({u,v});
    }

    for(auto [u,v] : vec)
    {
        int fu = find(u),fv = find(v);
        if(fu != fv)
        {
            sz[fv] += sz[fu];
            d[fv] += d[fu];
            fa[fu] = fv;
        }
    }

    bool hav = false;
    int cnt = 0;
    ll ans = 0;
    for(int i = 1;i <= n; i++)
    {
        int x = find(i);
        if(!vis[x])
        {
            vis[x] = true;
            if(fx(sz[x])==d[x]/2)
                ret[++cnt] = sz[x];
            else{
                hav = true;
                ans += fx(sz[x])-d[x]/2;
            }
        }
    }

    if(hav)
    {
        cout<<ans<<"\n";
        return 0;
    }

    sort(ret+1,ret+1+cnt);
    ll ve = ret[1]+ret[2];
    ll ed = fx(ret[1])+fx(ret[2]);
    cout<<fx(ve)-ed<<"\n";

    return 0;
}

I Pa?sWorD

思路：状压\(dp\)+前缀和优化。

考虑从前往后枚举，

\(dp[i][j][k]\)表示当前第\(i\)位，第\(i\)位填\(j\)(0-25 小写,26-51大写,52-61数字,62什么都没有),状态是\(k\)(二进制表示：小写、大写、数字)。

如果当前位置\(i\)是\(?\)的话,那么当前位可以是小写，大写或者数字。

由于我们发现\(i\)只由\(i-1\)位转移过来，那么我们考虑用滚动数组。

枚举61种可能(i)，然后从前面62种状态(t)和所有k继去继承。

假如第\(i\)位是选择填上小写字母的话，由于相邻两位不能一样，于是：

//假设当前位填j，上一位填t
if(j==t)continue;
else{
	dp[now][j][k|(1<<2)] += dp[pre][t][k];
}

但是这个思路的复杂度是\(O(100000*62*62*8)\)，会\(T\),

其实我们考虑从上一位转移过来，考虑可转移的情况(\(k==(w|(1<<2))\))中只有当\(t==j\)（相邻两位一样了）的情况的不符合条件的。那么这里可以考虑做一个前缀和优化。我们可以把上一位转移过来的所有情况数加和，之后再减去不符合条件的。

还是以当前位是问号，填小写字母为例：

 for(int j = 0;j<26;j++)
                for(int k = 0; k < (1<<3); k++)
                    for(int w = 0; w < (1<<3); w++)if((w|(1<<2))==k){
                        dp[now][j][k] += ((a[w]-dp[pre][j][w])%mod+mod)%mod;
                        dp[now][j][k] %= mod;
                    }

以上思路对于这一位填上大写或者数字是同理的。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 2e5 + 10;
int n;
string s;
ll dp[2][70][8];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>s;
    s = "?"+s;
    //0~25,26~52,52~61,62
    for(int i = 1;i <= n; i++)
    {
        int now = i&1, pre = (i-1)&1;
        if(i==1)
            dp[pre][62][0] = 1;
        for(int j = 0;j <= 62; j++)
            for(int k = 0;k < (1<<3); k++)
                dp[now][j][k] = 0;
        vector<int>a(10);
        for(int j = 0;j <= 62; j++)
            for(int k = 0; k < (1<<3); k++)
                a[k] += dp[pre][j][k],a[k]%=mod;
        if(s[i]=='?')
        {
            for(int j = 0;j < 26; j++)
                for(int k = 0;k < (1<<3); k++)
                    for(int w = 0;w < (1<<3); w++)if((w|(1<<2))==k){
                        dp[now][j][k] += ((a[w]-dp[pre][j][w])%mod+mod)%mod;
                        dp[now][j][k] %= mod;
                    }

            for(int j = 26;j < 52; j++)
                for(int k = 0;k < (1<<3); k++)
                    for(int w = 0;w < (1<<3); w++)if((w|(1<<1))==k){
                        dp[now][j][k] += ((a[w]-dp[pre][j][w]+mod)%mod)%mod;
                        dp[now][j][k] %= mod;
                    }
           for(int j = 52;j < 62; j++)
                for(int k = 0;k < (1<<3); k++)
                    for(int w = 0;w < (1<<3); w++)if((w|(1<<0))==k){
                        dp[now][j][k] += ((a[w]-dp[pre][j][w])%mod+mod)%mod;
                        dp[now][j][k] %= mod;
                    }
        }
        else if(s[i]>='a'&&s[i]<='z')
        {
            int j = s[i]-'a';
            for(int k = 0;k < (1<<3); k++)
                for(int w = 0;w < (1<<3); w++)if((w|(1<<2))==k){
                    dp[now][j][k] += ((a[w]-dp[pre][j][w])%mod+mod)%mod;
                    dp[now][j][k] %= mod;
                }
            j += 26;
            for(int k = 0;k < (1<<3); k++)
                for(int w = 0;w < (1<<3); w++)if((w|(1<<1))==k){
                    dp[now][j][k] += ((a[w]-dp[pre][j][w])%mod+mod)%mod;
                    dp[now][j][k] %= mod;
                }
        }
        else if(s[i]>='A'&&s[i]<='Z')
        {
            int j = s[i]-'A'+26;
            for(int k = 0;k < (1<<3); k++)
                for(int w = 0;w < (1<<3); w++)if((w|(1<<1))==k){
                    dp[now][j][k] += ((a[w]-dp[pre][j][w])%mod+mod)%mod;
                    dp[now][j][k] %= mod;
                }
        }
        else
        {
            int j = s[i]-'0'+52;
            for(int k = 0;k < (1<<3); k++)
                for(int w = 0;w < (1<<3); w++)if((w|(1<<0))==k){
                    dp[now][j][k] += ((a[w]-dp[pre][j][w])%mod+mod)%mod;
                    dp[now][j][k] %= mod;
                }
        }
    }

    ll ans = 0;
    for(int j = 0;j <= 62; j++)
        ans += dp[n&1][j][7],ans%=mod;
    cout<<ans%mod<<"\n";
    return 0;
}