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;
}