出题人题解
河南萌新联赛2024第（四）场：河南理工大学题解
河南萌新联赛2024第（四）场：
河南理工大学题解
预期难度：
A-该出奇兵了
B-小雷的神奇电脑
C-岗位分配
D-简单的素数
E-ANDF-小雷的算式
G-循环字符串
H-聪明且狡猾的恶魔
I-马拉松
J-尖塔第四强的高手
K-比赛
L-抓字符
预期难度：
easy：D,F
mid: B,C,E,H,K,L
mid_hard: A,I,J, L
hard: G
A-该出奇兵了
本题为割点的板子题。需要注意的地方有两点
1.本题给出的图不一定连通。
2.最终答案会超出long long能表示的范围。
把B国的城邦和道路看成节点和边。因为B国会尽量让所有联防体的攻克难度之和最大，所以联防体一定是图的连通分量。一次奇袭相当于删掉连通分量中的一个节点和与节点直接相连的边，这样会产生一个或者多个新的连通分量。记录原先连通分量对答案的贡献，再计算新的连通分量对答案的贡献，记录两者之间的差值。取最大的差值，用最初的连通分量的值之和减去这个差值就是答案。时间复杂度为O(n+m)。
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define F first
#define S second
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const int N = 2e5+10;
vector<pii> g[N];
int deep[N];//每个节点的深度
int up[N];//从该点向上的回边可以到达的最高高度
int dp[N];//经过该点向上的回边可以到达的最高高度
__int128 f[N];//子树内的士兵数量
ll a[N];
__int128 cnt,root;
void print(__int128 x){
if(x < 0){
cout<<'-';
x = -x;
}
if(x > 9)
print(x / 10);
cout<<char(x % 10 + '0');
}
void dfs1(int u, int fa)
{
up[u] = 1e9;
f[u] = a[u];
if(u==fa) deep[u] = 1;
else deep[u] = deep[fa] + 1;
for(auto& [v,flag]:g[u])
{
if(deep[v]>0)
{
if(v==fa) continue;//父边不是回边
if(deep[v] < deep[u])
{
flag = 1;//向上的回边
up[u]=min(up[u], deep[v]);
}
else
{
flag = 2;//向下的回边
}
continue;
}
dfs1(v,u);
f[u]+=f[v];
}
}
void dfs2(int u, int fa)
{
dp[u] = up[u];
__int128 part = f[root] - f[u];
__int128 res = 0;
for(auto [v,flag]:g[u])
{
if(flag != 0 || v==fa) continue;
dfs2(v, u);
if(dp[v]<deep[u]) //和u的祖先连通
{
dp[u] = min(dp[u], dp[v]);
part+=f[v];
}
else //产生新的连通分量
{
res += f[v]*f[v];
}
}
res+=part*part;
cnt = min(cnt, res);
}
void solve()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back({v,0});
g[v].push_back({u,0});
}
for(int i=1;i<=n;i++) cin>>a[i];
__int128 sum = 0;
__int128 dlt = 0;
for(int i=1;i<=n;i++)
{
if(deep[i]) continue;
cnt = 1e27;
root = i;
dfs1(i,i);
dfs2(i,i);
sum+=f[i]*f[i];
dlt = max(dlt, f[i]*f[i]-cnt);
}
print(sum-dlt);
}
B-小雷的神奇电脑
将 a_1, a_2, …, a_n 按非递减顺序排列。我们将证明答案是一对相邻的数字。假设答案是数字 a_i 和 a_j，且j - i > 1 。如果 a_i = a_j，那么就会有 a_i = a_{i+1} 。否则，它们有一个共同的比特前缀，之后有一个不同的比特。这意味着在某个位置 t，a_i 有一个 0，而 a_j 有一个 1。由于 j - i > 1，a_{i+1} 在这个位置上可以是 0 或 1。在第一种情况下，选择 a_i 和 a_{i+1} 作为答案更有利；而在第二种情况下，选择 a_{i+1} 和 a_j 作为答案更有利。所以只需要遍历一遍相邻位置的同或和。此解法的复杂度为O(n log n) 。
#include<iostream>
#include<vector>
#include<algorithm>
#include<bitset>
#include<map>
#include<set>
#include<queue>
#include<string>
#define int long long
#define B begin()
#define D end()
#define F first
#define S second
#define yes cout<<"Yes"<<'\n'
#define no cout<<"No"<<'\n'
#define sz size()
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e6+10;
const int mod= 19650827;
const int M=499;
const int INF = 2000000000;
void solve()
{
vector<int>a(32);
a[0]=1;int cnt=1;
for(int i=1;i<=30;i++)
{
cnt*=2;
a[i]=a[i-1]+cnt;
}
int n,m;cin>>n>>m;
vector<int>s(n);
for(int i=0;i<n;i++) cin>>s[i];
sort(s.B,s.D);
int ma=2e9;
for(int i=0;i<n-1;i++)
{
ma=min(s[i]^s[i+1],ma);
}
cout<<a[m-1]-ma;
}
C-岗位分配
已知每个志愿者之间没有区别，有不同的多个岗位且每个岗位至少有一个人，想到用组合数学隔板法来进行计数。 由于隔板法保证的是每个岗位至少分配一位志愿者，但是各个岗位的至少需求人数不一定为1，故需要现在需求人数大于1的岗位进行处理：对于需求人数至少为k的岗位，提前插入k-1位志愿者，并计所有提前插入的人数为sum，则对隔板的处理就是在m-sum的人数m-sum-1的空中加入隔板来分组。同时，注意到会有空闲的情况，这种情况可以多出一个实际没有的岗位来放这些人。答案分两种情况考虑，有空闲的情况，是在m-sum-1的空位中加入n个板子来完成C_{m-sum-1}^{n}，没有空闲的情况是C_{m-sum-1}^{n-1} ，相加即可。
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
const ll mod=998244353;
ll inv[maxn], fac[maxn]; //分别表示逆元和阶乘
//快速幂
ll quickPow(ll a,ll b){
ll ans=1;
while(b){
if(b&1)
ans=(ans*a)%mod;
b>>=1;
a=(a*a)%mod;
}
return ans;
}
void init(){
//求阶乘
fac[0]=1;
for(int i=1;i<maxn;i++){
fac[i]=fac[i-1]*i%mod;
}
//求逆元
inv[maxn-1]=quickPow(fac[maxn-1],mod-2);
for(int i=maxn-2;i>=0;i--){
inv[i]=inv[i+1]*(i+1)%mod;
}
}
ll C(int n,int m){
if(m>n){
return 0;
}
if(m==0)
return 1;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
init();
int n,m;
scanf("%d%d",&n,&m);
int sum=0;
for(int i=0;i<n;i++) {
int a;
cin>>a;
sum+=a-1;
}
m-=sum;
printf("%lld\n",(C(m-1,n)+C(m-1,n-1))%mod);
}
D-简单的素数
给你一些数，判断是否是素数（质数），如果直接遍历 1-n ，时间复杂度会太大，只需要遍历至 i^2\leq n 即可
#include<iostream>
using namespace std;
bool isPrime(int a) {
if (a < 2) return 0;
for (int i = 2; i*i <= a; ++i)
if (a % i == 0) return 0;
return 1;
}
int main()
{
int t;
cin>>t;
while(t--){
int x;
cin>>x;
if(isPrime(x))cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
E-AND
使用欧拉筛选出质数，存到vector中，然后二分查找区间在vector中的左右端点 l，r，区间内的质数个数 sum 为 r-l+1 。因为质数只有2为偶数，所以区间左端点包含2时，答案为 sum-2 ，特判左右端点都为2的情况。如果区间左端点不包含2，答案为0；
#include<iostream>
#include<vector>
using namespace std;
bool sum[100000010];
vector<int>prime;
void op(int n){
sum[1]=1;
for(int i=2;i<=n;i++){
if(!sum[i])prime.push_back(i);
for(int j:prime){
if(j*i>n)break;
sum[j*i]=1;
if(i%j==0)break;
}
}
}
int main(){
op(100000000);
int t;
cin>>t;
while(t--){
int x,y;
cin>>x>>y;
int sum=0,l1=0,r1=prime.size()-1,l2=0,r2=r1;
while(l1<r1){
int m=l1+r1>>1;
if(prime[m]<x)l1=m+1;
else r1=m;
}
while(l2<r2){
int m=l2+r2>>1;
if(prime[m]<y)l2=m+1;
else r2=m;
}
if(prime[l2]>y)l2--;
sum=l2-l1+1;
cout<<sum<<' ';
if(x>2||sum==1)cout<<"0\n";
else if(sum>=2)cout<<sum-2<<endl;
}
return 0;
}
F-小雷的算式
字符串处理+排序 将字符串中的数字提取出来从大到小排序，然后从大到小加加号输出出来，同时将答案计算出来。
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
bool cmp(int a,int b)
{
return a>b;
}
int main() {
string s;
cin>>s;
int num=0;
vector <int> ss;
int len=s.size();
for(int i=0;i<len;i++){
if(s[i]=='+'){
ss.push_back(num);
num=0;
}else{
num*=10;
num+=s[i]-'0';
}
}
ss.push_back(num);
sort(ss.begin(),ss.end(),cmp);
int len1=ss.size();
int ans=0;
for(int i=0;i<len1;i++){
if(i!=len1-1) cout<<ss[i]<<'+';
else cout<<ss[i]<<endl;
ans+=ss[i];
}
cout<<ans<<endl;
}
G-循环字符串
线段树维护区间的正反hash值，然后考虑计算循环节
比如对于1操作
记 len = r - l + 1
枚举 len 的约数是根号的做法，应该被卡掉
假设x是循环节，充要条件就是hash(l + len, r) = hash (l, r - len)
假设x = p_1 ^ {c1} * p_2 ^ {c2} * ... p_y ^ {cy}; 可以预见对于每一个c, 必定都为1
所以从len开始试除每个质因子并判断（len的因子分为循环节的因子和循环次数的因子，要把循环次数的因子除掉）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> PLL;
#define x first
#define y second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define lep(i,a,b) for(int i=(a);i>=(b);i--)
#define sci(x) cin >> (x)
#define pli(x) cout << (x) << " ";
#define pll(x) cout << (x) << '\n';
#define yes cout << "YES" << '\n';
#define no cout << "NO" << '\n';
#define ls u << 1
#define rs u << 1 | 1
const int N = 2e6 + 10;
ll n, m, k, p = 131;
ull P[N], hs[N], f[N];
ll a[N], b[N], ne[N];
char s1[N], s2[N], t[N];
ll st[N], mnz[N], cnt, pr[N];
void get()
{
st[1] = 1;
rep(i, 2, N - 1)
{
if(!st[i]) pr[++cnt] = i, mnz[i] = i;
for(int j = 1; j <= cnt && i * pr[j] <= N - 1; j++)
{
st[i * pr[j]] = 1, mnz[i * pr[j]] = pr[j];
if(i % pr[j] == 0) break;
}
}
}
struct node
{
ll l, r;
ull lh, rh, cg;
}tr[N];
void pushup(int u)
{
tr[u].lh = tr[ls].lh * P[tr[rs].r - tr[rs].l + 1] + tr[rs].lh;
tr[u].rh = tr[rs].rh * P[tr[ls].r - tr[ls].l + 1] + tr[ls].rh;
}
void pushdown(int u)
{
if(tr[u].cg == 0) return;
tr[ls].rh = tr[ls].lh = tr[u].cg * f[tr[ls].r - tr[ls].l];
tr[rs].rh = tr[rs].lh = tr[u].cg * f[tr[rs].r - tr[rs].l];
tr[ls].cg = tr[rs].cg = tr[u].cg; tr[u].cg = 0;
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if(l == r)
{
tr[u].lh = tr[u].rh = a[l];
return;
}
int mid = l + r >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
pushup(u);
}
void modify(int u, int ql, int qr, ll val)
{
if(tr[u].l >= ql && tr[u].r <= qr)
{
tr[u].cg = val;
tr[u].lh = tr[u].rh = tr[u].cg * f[tr[u].r - tr[u].l];
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(ql <= mid) modify(ls, ql, qr, val); if(qr > mid) modify(rs, ql, qr, val);
pushup(u);
}
pair<pair<ull, ull>, pair<ull, ull>> query(int u, int ql, int qr)
{
if(tr[u].l >= ql && tr[u].r <= qr)
{
return {{tr[u].lh, tr[u].r - tr[u].l + 1}, {tr[u].rh, tr[u].r - tr[u].l + 1}};
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(qr <= mid) return query(ls, ql, qr);
if(ql > mid) return query(rs, ql, qr);
pair<pair<ull, ull>, pair<ull, ull>> l = query(ls, ql, qr), r = query(rs, ql, qr), res;
res.x.x = l.x.x * P[r.x.y] + r.x.x, res.y.x = r.y.x * P[l.x.y] + l.y.x;
res.x.y = res.y.y = l.x.y + r.x.y;
return res;
pushup(u);
}
void solve()
{
get();
cin >> n >> m >> s1 + 1; P[0] = f[0] = 1;
unordered_map<ull, int> mp;
rep(i, 1, n)
{
a[i] = s1[i] - 'a' + 1;
P[i] = P[i - 1] * p, f[i] = f[i - 1] + P[i];
}
rep(i, 0, n) rep(j, 1, 26) mp[(ull)j * P[i]] = 1;
build(1, 1, n);
while(m--)
{
int op, l, r; char c; cin >> op >> l >> r;
if(op == 0)
{
cin >> c;
modify(1, l, r, (ull)(c - 'a' + 1));
}
if(op == 1)
{
if(l == r)
{
pll(1)
continue;
}
ll len = r - l + 1, ans = r - l + 1;
if(query(1, l + 1, r).x.x == query(1, l, r - 1).x.x)
{
pll(1)
continue;
}
while(len > 1)
{
if(query(1, l + ans / mnz[len], r).x.x == query(1, l, r - ans / mnz[len]).x.x) ans /= mnz[len];
len /= mnz[len];
}
pll(ans)
}
if(op == 2)
{
if(l == r)
{
pll(1)
continue;
}
ll len = r - l + 1, ans = r - l + 1;
if(query(1, l + 1, r).y.x == query(1, l, r - 1).y.x)
{
pll(1)
continue;
}
while(len > 1)
{
if(query(1, l + ans / mnz[len], r).y.x == query(1, l, r - ans / mnz[len]).y.x) ans /= mnz[len];
len /= mnz[len];
}
pll(ans)
}
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T; T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
H-聪明且狡猾的恶魔
分析题目我们可以知道这是一道博弈题，在明白这是博弈题之后，我们可以尝试去寻找一下让其他恶魔不得不为我投票的原因。我们先从后往前进行分析，假如现在只剩下了第n-1号恶魔和第n号恶魔，那么无论第n号恶魔同意还是反对，n-1号的方案都会被通过，因为第n-1号恶魔肯定会给自己投赞成票，满足了大于等于50%的条件，那么n号恶魔一枚金币都拿不到。所以n号恶魔一定不会让n-1号恶魔当上恶魔老大。那么我们现在继续往前推，n-2号恶魔为了争取n号的赞成票，那么他会给n号恶魔1枚金币，这样他的方案就会通过，那么n-2号恶魔可以获得x-1枚金币。继续这样往前推，n-1号恶魔肯定不希望n-2号恶魔成为恶魔老大，那么只要n-3号恶魔给他一枚金币，他就会赞成n-3号恶魔的方案，而不需要给另外两个恶魔额外的金币，那么他可以获得x-1枚金币。这样一直向前推就可以想明白其中的逻辑关系。
AC代码
#include <iostream>
using namespace std;
int n,x;
void solve()
{
cin>>x>>n;
if(n%2!=0) cout<<x-(n/2)<<endl;
else cout<<x-(n/2-1)<<endl;
}
int main()
{
int t;cin>>t;
while(t--) solve();
return 0;
}
I-马拉松
把城市视为一棵树。现在，可以求出小明无法选择的配对数，找出从 u 到 v 的最短路径是先经过 x 再经过 y 的顶点 (u, v) 的对数。 如果将顶点 y 作为树根，那么可以知道小明不能正常比赛的马拉松的每一对顶点都是从节点 x 的子树内的任意节点开始，并在节点y的子树且不包括在节点 z（节点 z 是 y 的直子节点，位于从 x 到 y 的最短路径上）的子树内的任意节点结束。我们要找的顶点对的总数等于 s[x]·(s[y] - s[z]) ，其中 s[i] 表示节点 i 的子树的大小，t表示的是y的直子节点，且该点可以使用 DFS 来实现。
#include <iostream>
#include <vector>
using namespace std;
const int N=3e5+10;
vector<int> g[N];
bool st[N];
long long sun[N];
bool check[N];
int n,x,y;
long long dfs(int u)
{
st[u]=1;
sun[u]=1;
if(u==x)check[u]=1;
for(int i:g[u])
{
if(!st[i])
{
sun[u]+=dfs(i);
check[u]|=check[i];
}
}
return sun[u];
}
int main()
{
cin>>n>>x>>y;
int m=n-1;
for(int i=0,u,v;i<m;i++)
{
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(y);
long long find=0;
for(int i:g[y])
{
if(check[i]==1)
{
find=sun[y]-sun[i];
}
}
long long ans=find*sun[x];
cout<<ans<<endl;
}
J-尖塔第四强的高手
题意是由斐波那契数列生成一个点集，求该点集的最近公共祖先。
注意到斐波那契数列增长很快，F_{25}=121393，因此当 k\ge 25 时直接输出 0。预处理出斐波那契数列前 24 项，每次询问可以暴力求出点集中的所有点，接下来就是求点集的最近公共祖先。
解法一：不难发现 \operatorname{LCA}(x_1,x_2,x_3,\dots)=\operatorname{LCA}(\operatorname{LCA}(x_1,x_2),x_3,\dots)。每次询问点集中至多有 24 个点，因此至多求 23 次 LCA，可以用倍增法求 LCA，总时间复杂度为 O(n\log n+23q\log n)。代码如下
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
vector<int> nxt[N];
int f[N][18],dep[N],F[26];
void dfs(int x,int FA)
{
dep[x]=dep[FA]+1;f[x][0]=FA;
for(auto y:nxt[x])
if(y!=FA) dfs(y,x);
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=17;i>=0;--i)
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
for(int i=17;i>=0;--i)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
void solve()
{
F[1]=1;F[2]=2;
for(int i=3;i<=25;++i) F[i]=F[i-1]+F[i-2];
int n,rt,q;
cin>>n>>rt>>q;
for(int i=1;i<n;++i) {
int x,y;
cin>>x>>y;
nxt[x].push_back(y);
nxt[y].push_back(x);
}
dfs(rt,0);
for(int j=1;j<=17;++j)
for(int i=1;i<=n;++i)
f[i][j]=f[f[i][j-1]][j-1];
while(q--) {
int x,k;
cin>>x>>k;
if(k>=25||x+F[k]>n) printf("0\n");
else {
int ans=0;
for(int i=k;x+F[i]<=n;++i) {
if(!ans) ans=x+F[i];
else ans=LCA(ans,x+F[i]);
}
printf("%d\n",ans);
}
}
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int T=1;
while(T--) {
solve();
}
return 0;
}
解法二：有一个结论，多个点的 LCA 等于这些点中 dfs 序最大和最小两个点的 LCA。每次询问只需要找出 dfs 序最大的点和最小的点，然后求这两个点的 LCA。 这里可以用 dfs 序求 LCA，具体来说，x,y(dfn_x<dfn_y) 两点的 LCA 就等于 dfs 序区间 [dfn_x+1,dfn_y] 中深度最小的结点的父亲。可以用 st 表预处理，单次查询复杂度 O(1)。总时间复杂度为 O(n\log n+24q)，代码如下
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
vector<int> nxt[N];
int dfn[N],dfn_tot=0,st[N][20],dep[N],fa[N],ex[20],lg2[N],F[26];
void dfs(int x,int FA)
{
dfn[x]=++dfn_tot;dep[x]=dep[FA]+1;fa[x]=FA;
st[dfn_tot][0]=x;
for(auto y:nxt[x])
if(y!=FA) dfs(y,x);
}
int check(int x,int y){return dep[x]<dep[y]?x:y;}
void solve()
{
F[1]=1;F[2]=2;
for(int i=3;i<=25;++i) F[i]=F[i-1]+F[i-2];
lg2[1]=0;
int n,rt,q;
cin>>n>>rt>>q;
for(int i=1;i<n;++i) {
lg2[i+1]=lg2[(i+1)/2]+1;
int x,y;
cin>>x>>y;
nxt[x].push_back(y);
nxt[y].push_back(x);
}
dfs(rt,0);
ex[0]=1;
for(int j=1;(1<<j)<=n;++j) {
ex[j]=1<<j;
for(int i=1;i+ex[j]-1<=n;++i)
st[i][j]=check(st[i][j-1],st[i+ex[j-1]][j-1]);
}
while(q--) {
int x,k;
cin>>x>>k;
if(k>=25||x+F[k]>n) printf("0\n");
else {
int Min=1e9,Max=0,ans=0;
for(int i=k;x+F[i]<=n;++i)
Min=min(Min,dfn[x+F[i]]),Max=max(Max,dfn[x+F[i]]);
if(Min==Max) ans=st[Min][0];
else {
int len=ex[lg2[Max-Min]];
ans=fa[check(st[Min+1][lg2[Max-Min]],st[Max-len+1][lg2[Max-Min]])];
}
printf("%d\n",ans);
}
}
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int T=1;
while(T--) {
solve();
}
return 0;
}
K-比赛
可以发现是不能对所有人能力值进行排序的，能够选择作为裁判的禁军最多 n - 2 个（除去两边的）。
暴力的来想直接求以第 i 个禁军为裁判，看符合的选手有多少种组合就行了，但是显示会超时.
其实不难想到，对于确定裁判为第 j 个人时，从要求出发，如果在 1, 2, \dots ,i - 1 选择的禁军 a_i >= a_j ，那么在 i + 1, i + 2, \dots, n 中选择的禁军必须满足 a_k <= a_j ,反之也是满足的。
那么就可以使用四个数组 l_{up}[i], l_{low}[i], r_{up}[i], r_{low}[i] ,维护第 i 个禁军左边比他能力值大的，比他能力值小的，右边比他能力值大的，比他能力值小的人数。
但是需要考虑到第 i 个禁军的左边和右边分别和他能力值相等的人数，不然会出现有重复的方案。再需要使用 l_{cnt}[i], r_{cnt}[i] 俩数组记录第 i 个禁军的左边和右边分别有多少个和他能力值相同的。
总结下来最终答案就是 \sum_{i=2}^{n - 1} l_{up}[i]*r_{low}[i]+l_{low}[i]*r_{up}[i] - l_{cnt}[i] * r_{cnt}[i]
树状数组前后各跑一遍就可以了。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int a[20010];
int tree[100010];
inline int lowbit(int x){return x&(-x);}
void update(int x,int k)
{
while(x<=100000)
{
tree[x]+=k;
x+=lowbit(x);
}
}
int query(int x)
{
int sum=0;
while(x!=0)
{
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}
int l_low[20010],l_up[20010],r_low[20010],r_up[20010];
int l_cnt[20010], r_cnt[20010];
int main()
{
int T;
scanf("%d",&T);
for(int _=1;_<=T;++_)
{
long long ans=0;
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
{
l_low[i]=query(a[i]);
l_up[i]=query(100000)-query(a[i]-1);
l_cnt[i] = query(a[i])-query(a[i] - 1);
update(a[i],1);
}
for(int i=1;i<=100000;++i)tree[i]=0;
for(int i=n;i>=1;--i)
{
r_low[i]=query(a[i]);
r_up[i]=query(100000)-query(a[i]-1);
r_cnt[i] = query(a[i])-query(a[i]-1);
update(a[i],1);
ans+=(long long)r_low[i]*(long long)l_up[i];
ans+=(long long)l_low[i]*(long long)r_up[i];
ans-=l_cnt[i]*r_cnt[i];
}
for(int i=1;i<=100000;++i)tree[i]=0;
printf("%lld\n",ans);
}
}
L-抓字符
每个字符都要进行取的操作，当取第i个字符时候，维护以si结尾的字符串的概率，和以其他字符结尾的字符串的概率。
因为求非严格单调串的概率，计算出非严格单调上升和非严格单调下降的串的概率后减去由相同字符组成的串的概率即可。
因为pi在1000000以内，所以预先处理出1到1000000的逆元可以通过，也可以使用exgcd求逆元通过。
#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
using pii=pair<int,int>;
using ll=long long;
constexpr int N=1e6+10,M=1e7+100,mod=998244353,INF=2e9;
ll n,m;
ll f[500][3],p[N];
ll fact[N],inv[N];
ll qmi(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
void init(){
fact[0]=1;
for(int i=1;i<=1000000;i++) fact[i]=fact[i-1]*i%mod;
ll infact=qmi(fact[1000000],mod-2);
for(int i=1000000;i>=1;i--){
inv[i]=infact*fact[i-1]%mod;
infact=(infact*i)%mod;
}
}
void solve(){
cin>>n;
string a;
cin>>a;
a=" "+a;
for(int i=1;i<=n;i++) cin>>p[i];
ll dlt=1;
for(int i=1;i<=n;i++){
ll bp1=f[a[i]][1],bp2=f[a[i]][2];
for(int j='a';j<='z';j++){
if(j<a[i]) f[a[i]][1]=(f[a[i]][1]+f[j][1]*inv[p[i]]%mod)%mod;
if(j>a[i]) f[a[i]][2]=(f[a[i]][2]+f[j][2]*inv[p[i]]%mod)%mod;
}
for(int j='a';j<='z';j++){
if(j==a[i]) continue;
for(int k=0;k<3;k++) f[j][k]=f[j][k]*((1-1*inv[p[i]]%mod+mod)%mod)%mod;
}
for(int j=0;j<3;j++) f[a[i]][j]=(f[a[i]][j]+dlt*inv[p[i]]%mod)%mod;
dlt=dlt*((1-inv[p[i]]+mod)%mod)%mod;
}
ll ans=0;
for(int i='a';i<='z';i++) ans=((ans+(f[i][1]+f[i][2])%mod)%mod-f[i][0]+mod)%mod;
cout<<ans<<'\n';
}
查看17道真题和解析