补题链接：Dashboard - The 2025 Sichuan Provincial Collegiate Programming Contest - Codeforces

I. Essentially Different Suffixes

题目大意：

给定 N 个由小写英文字母组成的字符串，需要计算所有字符串的本质不同的后缀的总数。

其中，“字符串的后缀” 定义为：从字符串的某个位置开始到结尾的子段（例如，字符串 abc 的后缀有 abc、bc、c）；“本质不同” 指的是这些后缀的内容互不相同。

解题思路：

将每个字符串反转（使后缀变为前缀），通过字典树插入这些反转字符串，插入过程中新增节点的数量即为所有本质不同后缀的总数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
int mod=998244353;
int n;
int ans;
int son[N][26];
int idx;
int cnt[N];
void insert(string s){
	int p=0;
	for(int i=0;i<s.size();i++){
		int u=s[i]-'a';
		if(!son[p][u]){
			son[p][u]=++idx;
			ans++;
		}
		p=son[p][u];
	}
	cnt[p]++;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
	string ss;
	cin>>ss;
	reverse(ss.begin(),ss.end());
	insert(ss);
	// ans+=ss.size();
	
	}
	
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--){
        solve();
    }
  
}

H. Hututu

题意：

求解思路：

     设横纵距离分别为 d1=|x-xx|、d2=|y-yy|，最大距离 d=max (d1,d2)。由于每次移动可同时减少两个方向的距离（如用 (2,1) 移动可减少 2 单位横距和 1 单位纵距），因此最少步数由最大距离 d 决定，需满足 “覆盖最大距离”。

     当两点共线（x 或 y 坐标相同，即 d1=0 或 d2=0）时，因移动必须同时改变两个方向的距离，无法直接沿单一坐标轴移动。此时：

（1）若 d=1 或 2：无法一步到达（一步至少会让另一个方向产生 1 或 2 的偏移），需 2 步抵消偏移；

（2）若 d>2：可通过组合移动（如 (2,1) 与 (1,2)）覆盖距离，步数为⌈d/2⌉（即 (d+1)/2）。

    在不共线的情况，可通过灵活选择移动方式（如 (1,2) 或 (2,1)）同时减少 d1 和 d2，步数直接由最大距离 d 的⌈d/2⌉决定。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int mod=1e9+7;


void solve(){
	int x,y,xx,yy;
	cin>>x>>y>>xx>>yy;
	if(x==xx&&y==yy){
		cout<<"0"<<endl;
	}
	else if(x==xx||y==yy){
		int d1=abs(x-xx);
		int d2=abs(y-yy);
		int d=max(d1,d2);
		if(d==1||d==2){
			cout<<2<<endl;
		}
		else{
			cout<<(d+1)/2<<endl;
		}
	}
	else{
		int d1=abs(x-xx);
		int d2=abs(y-yy);
		int d=max(d1,d2);
		cout<<(d+1)/2<<endl;
	}
	
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int T=1;
    cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}

F. Inversion Pairs

题目大意

每组给定一个长度为 n 的字符串（由 0、1、? 组成，? 表示待确定的位置），需将 ? 替换为 0 或 1，使得最终由 0 和 1 组成的序列的逆序对数量最大化，输出每组的最大逆序对数量。

求解思路：

1. 预处理前缀数组v0（前 i 个字符中 '0' 的数量）、v1（前 i 个字符中非 '0' 的数量），以及后缀数组vv0（从 i 到结尾非 '1' 的数量）、vv1（从 i 到结尾 '1' 的数量）。

2. 计算初始状态（所有 '?' 视为 '1'）的逆序对数量ans：每个 '1' 贡献其后方非 '1' 的数量（即vv0[i+1]）。

3. 枚举每个 '?'，模拟将其从 '1' 改为 '0' 的情况：减少该位置前非 '0' 字符形成的逆序对（v1[i-1]），增加该位置后非 '1' 字符形成的逆序对（vv0[i+1]），动态更新最大逆序对数量。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int mod=1e9+7;
void solve(){
	string s;
	int n;
	cin>>n;
	cin>>s;
	s=" "+s;
	vector<int>v0(n+10,0);
	vector<int>v1(n+10,0);
	for(int i=1;i<s.size();i++){
		v0[i]=v0[i-1]+(s[i]=='0');
		v1[i]=v1[i-1]+(s[i]!='0');
	}
	vector<int>vv0(n+10,0);
	vector<int>vv1(n+10,0);
	//后缀全为0
	for(int i=n;i>=1;i--){
		vv0[i]=vv0[i+1]+(s[i]!='1');
		vv1[i]=vv1[i+1]+(s[i]=='1');
	}
	int ans=0;
	//当前全部为1
	for(int i=1;i<s.size();i++){
		if(s[i]=='1'){
			ans+=vv0[i+1];
		}
	}
	int cnt=ans;
	//假设当前？变为0
	//一定是有一个分界点的，最优的解为前一段全是1，后一段全是0
	//枚举？是将1变为0的情况
	for(int i=1;i<s.size();i++){
		if(s[i]=='?'){
			cnt-=v1[i-1];
			cnt+=vv0[i+1];
			ans=max(cnt,ans);
		}
	}
	cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int T=1;
    cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}

J. Sichuan Provincial Contest

题目大意：

每组给定一棵含 n 个节点的树（每个节点对应一个大写英文字符），需统计树中恰好包含 5 个节点的简单路径数量，要求这些路径上 5 个节点的字符依次构成字符串 "SCCPC"。求出满足条件的路径数量。

求解思路：

1. 首先构建图的邻接表，并预处理两个计数数组：m1[x]记录 'C' 节点 x 连接的 'S' 节点数，m2[x]记录 'P' 节点 x 连接的 'C' 节点数。

2. 遍历每个 'C' 节点作为中心，检查其所有邻居：

   • 若邻居是 'C'，累加该邻居连接的 'S' 节点数（m1[x]）到ans1；
   • 若邻居是 'P'，累加该邻居连接的 'C' 节点数（m2[x]-1，减 1 是排除当前中心 'C'）到ans2。

3. 每个中心 'C' 的贡献为ans1*ans2（表示通过该中心形成的有效组合数），累加所有中心的贡献即为最终结果。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+100;
int mod=1e9+7;
int i;
vector<int>v[N];
int m1[N],m2[N];


void solve(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	s=" "+s;
	for(int i=1;i<=n+10;i++){
		v[i].clear();
		m1[i]=0;
		m2[i]=0;
	}
	//把SCCPC拆成SC、PC两个部分
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
		if(s[x]=='C'&&s[y]=='S'){
			m1[x]++;
		}
		if(s[y]=='C'&&s[x]=='S'){
			m1[y]++;
		}
		if(s[x]=='C'&&s[y]=='P'){
			m2[y]++;
		}
		if(s[x]=='P'&&s[y]=='C'){
			m2[x]++;
		}
	}
	//枚举中心点C
	int ans=0;
	for(int i=1;i<=n;i++){
		if(s[i]!='C'){
			continue;
		}
		int ans1=0;
		int ans2=0;
		for(auto x:v[i]){
			string ss="";
			ss+=s[i];
			ss+=s[x];
			if(ss=="CP"||ss=="CC"){
				if(s[x]=='C'){//计算CS的个数
					ans1+=m1[x];
				}
				if(s[x]=='P'){
					ans2+=(m2[x]-1);
					//因为PC相连的C也有一个贡献度，所以要减去1
				}
			}
		}
		ans+=ans1*ans2;
	}
	cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int T=1;
    cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}