好久之前的题了。
A. 弹珠游戏
\(R, G, B\) 任意时刻只能出现两种，出现第三种时优先匹配剩下两种的组合，再考虑形成新的组合，匹配啥是一样的，于是每次乘上方案数
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int mod = 998244353;
const int maxn = 600005;
int n, ans;
string s;
map <string, int>f;
int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
cin >> n >> s;
n = n * 3;
f[s.substr(0, 1)] = ans = 1;
for(int i = 1; i < n; ++i)
if(s[i] == 'R'){
if(f["GB"]){ans = 1ll * ans * f["GB"] % mod; --f["GB"]; continue;}
if(f["G"]){ans = 1ll * ans * f["G"] % mod; --f["G"]; ++f["RG"]; continue;}
if(f["B"]){ans = 1ll * ans * f["B"] % mod; --f["B"]; ++f["RB"]; continue;}
++f["R"];
}else if(s[i] == 'G'){
if(f["RB"]){ans = 1ll * ans * f["RB"] % mod; --f["RB"]; continue;}
if(f["R"]){ans = 1ll * ans * f["R"] % mod; --f["R"]; ++f["RG"]; continue;}
if(f["B"]){ans = 1ll * ans * f["B"] % mod; --f["B"]; ++f["GB"]; continue;}
++f["G"];
}else{
if(f["RG"]){ans = 1ll * ans * f["RG"] % mod; --f["RG"]; continue;}
if(f["R"]){ans = 1ll * ans * f["R"] % mod; --f["R"]; ++f["RB"]; continue;}
if(f["G"]){ans = 1ll * ans * f["G"] % mod; --f["G"]; ++f["GB"]; continue;}
++f["B"];
}
for(int i = 1; i <= n / 3; ++i)ans = 1ll * ans * i % mod;
cout << ans << endl;
return 0;
}
B. 晚会
建立一棵生成树，考虑非树边
发现合法情况会形成类似等腰三角形的情况并且底边长要大于等于腰长
那么建立最大生成树，判断时查询路径最小值，合法情况下等于当前非树边边权
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
int n, m;
const int maxn = 600005;
struct DSU{
int f[maxn];
void init(){for(int i = 1; i <= n + n; ++i)f[i] = i;}
int fa(int x){return f[x] == x ? x : f[x] = fa(f[x]);}
}S;
struct EDGE{
int u, v, w;
friend bool operator < (const EDGE &x, const EDGE &y){
return x.w > y.w;
}
}E[maxn];
int cnt, val[maxn];
vector<int>g[maxn];
int dep[maxn], son[maxn], fa[maxn], siz[maxn], top[maxn], leaf[maxn];
void dfs(int x){
siz[x] = 1;if(x <= n)leaf[x] = 1;
for(int v : g[x]){
fa[v] = x; dep[v] = dep[x] + 1;
dfs(v);
leaf[x] += leaf[v];
siz[x] += siz[v]; son[x] = siz[son[x]] > siz[v] ? son[x] : v;
}
}
void dfs2(int x, int tp){
top[x] = tp;
if(son[x])dfs2(son[x], tp);
for(int v : g[x])if(v != son[x])dfs2(v, v);
}
int lca(int x, int y){
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]])swap(x, y);
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
vector <int> notree;
bool check(){
for(int i : notree){
if(val[lca(E[i].u, E[i].v)] != E[i].w)return false;
}
return true;
}
ll ans;
void solve(int x){
if(x <= n)return;
int sil = 0, sir = 0;
for(int v : g[x]){
solve(v);
if(sil) sir = leaf[v];
else sil = leaf[v];
}
ans = ans - 1ll * sil * sir + 1ll * sil * sir * val[x];
}
ll sol(){
ans = 1ll * n * (n - 1) / 2;
for(int i = cnt; i >= 1; --i)if(!fa[i])solve(i);
return ans;
}
int main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
n = read(), m = read(); S.init();
for(int i = 1; i <= m; ++i)E[i].u = read(), E[i].v = read(), E[i].w = read();
sort(E + 1, E + m + 1); cnt = n;
for(int i = 1; i <= m; ++i)if(S.fa(E[i].u) != S.fa(E[i].v)){
int u = S.fa(E[i].u), v = S.fa(E[i].v);
val[++cnt] = E[i].w;
g[cnt].push_back(u);
g[cnt].push_back(v);
S.f[u] = S.f[v] = cnt;
}else notree.push_back(i);
for(int i = cnt; i >= 1; --i)if(!siz[i])dfs(i), dfs2(i, i);
if(check())printf("%lld\n",sol());
else printf("-1\n");
return 0;
}
C. 优美的字符串
DP 套 DP
D. 选举
回滚莫队+分块
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c))c = getchar();
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 300005;
int n, m, Q;
int len, bl[maxn];
int lem, bm[maxn];
int a[maxn], b[maxn];
struct node{
int l, r, ql, qr, id;
friend bool operator < (const node &x, const node &y){
return bl[x.l] == bl[y.l] ? x.r < y.r : x.l < y.l;
}
}q[maxn];
ll cnt[maxn], ans[maxn], mx[maxn], rem[maxn];
void Ckmx(ll &x, ll y){if(y > x)x = y;}
void Add(int pos){
cnt[a[pos]] += b[pos];
rem[pos] = mx[bm[a[pos]]];
Ckmx(mx[bm[a[pos]]], cnt[a[pos]]);
}
void Del(int pos){
cnt[a[pos]] -= b[pos];
mx[bm[a[pos]]] = rem[pos];
}
void clear(int r){
while(r && cnt[a[r]] > 0){
mx[bm[a[r]]] = 0;
cnt[a[r]] -= b[r];
--r;
}
}
ll query(int l, int r){
ll ans = 0;
if(bm[l] == bm[r]){
for(int i = l; i <= r; ++i)Ckmx(ans, cnt[i]);
return ans;
}
for(int i = bm[l] * lem; i >= l; --i)Ckmx(ans, cnt[i]);
for(int i = (bm[r] - 1) * lem + 1; i <= r; ++i)Ckmx(ans, cnt[i]);
for(int i = bm[l] + 1; i < bm[r]; ++i)Ckmx(ans, mx[i]);
return ans;
}
void sol(){
int r = 0;
for(int i = 1; i <= Q; ++i){
if(bl[q[i].l] != bl[q[i - 1].l]){clear(r); r = min(bl[q[i].l] * len, n);}
while(r < q[i].r)Add(++r);
int up = min(q[i].r, bl[q[i].l] * len);
for(int j = q[i].l; j <= up; ++j)Add(j);
ans[q[i].id] = query(q[i].ql, q[i].qr);
for(int j = up; j >= q[i].l; --j)Del(j);
}
}
int main(){
freopen("D.in","r",stdin);
freopen("D.out","w",stdout);
n = read(), m = read(), Q = read();
for(int i = 1; i <= n; ++i)a[i] = read();
for(int i = 1; i <= n; ++i)b[i] = read();
for(int i = 1; i <= Q; ++i){
q[i].l = read(), q[i].r = read();
q[i].ql = read(), q[i].qr = read();
q[i].id = i;
}
len = sqrt(n); for(int i = 1; i <= n; ++i)bl[i] = (i + len - 1) / len;
lem = sqrt(m); for(int i = 1; i <= m; ++i)bm[i] = (i + lem - 1) / lem;
sort(q + 1, q + Q + 1); sol();
for(int i = 1; i <= Q; ++i)printf("%lld\n",ans[i]);
return 0;
}