A Qualifiers Ranking Rules
思路：按位次为第一关键字，场次为第二关键字排序即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#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
思路：个点构成完全图需要条边。
如果这个连通块不是完全图，那么答案加上(m是当前连通块边数)
如果全都是完全图呢？由于至少连一条边，那么我们考虑选两个点数最少的使得它们成为完全图。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#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
思路：状压+前缀和优化。
考虑从前往后枚举，
表示当前第位，第位填(0-25 小写,26-51大写,52-61数字,62什么都没有),状态是(二进制表示：小写、大写、数字)。
如果当前位置是的话,那么当前位可以是小写，大写或者数字。
由于我们发现只由位转移过来，那么我们考虑用滚动数组。
枚举61种可能(i)，然后从前面62种状态(t)和所有k继去继承。
假如第位是选择填上小写字母的话，由于相邻两位不能一样，于是：
1
2
3
4
5
|
if(j==t)continue;
else{
dp[now][j][k|(1<<2)] += dp[pre][t][k];
}
|
但是这个思路的复杂度是$O(1000006262*8)T$,
其实我们考虑从上一位转移过来，考虑可转移的情况()中只有当（相邻两位一样了）的情况的不符合条件的。那么这里可以考虑做一个前缀和优化。我们可以把上一位转移过来的所有情况数加和，之后再减去不符合条件的。
还是以当前位是问号，填小写字母为例：
1
2
3
4
5
6
| 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;
}
|
以上思路对于这一位填上大写或者数字是同理的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#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;
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;
}
|
