notes：题目还没有放在题库里 所有链接都是比赛里的

资格赛（模拟）

思路

嗯大概就是我脑子抽了吧 交错代码了。

你不要妄想在我这里获得这道题的思路。

如果你这道题都不会 那你废了。

代码

#include <bits/stdc++.h>
using namespace std;
 
int main(){
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
    int n,k;
    string s;
    cin >>n>>k>>s;
    for(int i=0;i<s.size();i++){
    	if(s[i]=='o'&&k>0){
    		k--;
		}else if(s[i]=='o'&&k<=0){
			s[i]='x';
		}
	}
    cout <<s;
    return 0;
}

构成回文（数学）

思路

• 对序列中每对点连线：
  • 若 $a_i = a_j$，称为好线；
  • 若 $a_i \neq a_j$，称为坏线。

1. 预处理：

   • 对每个值 $x$，记录其出现位置集合 $P_x$。

2. 双指针计算：

   • 初始化 $l=0$，$r=|P_x|-1$。
   • 当 $l \leq r$ 时：$$\begin{cases} (r-l) \cdot P_x[l] & \text{if } P_x[l] < n+1-P_x[r] \\ (r-l) \cdot (n+1-P_x[r]) & \text{otherwise} \end{cases}$$并根据条件移动 $l$ 或 $r$。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=2e5+10;
vector<vector<int>> v(tt);

signed main(){
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
	int n;
	cin >>n;
	for(int i=1;i<=n;i++){
		int x;
		cin >>x;
		v[x].push_back(i);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans+=(n-i+1)*(i/2);
	}
	for(int i=1;i<=n;i++){
		int l=0,r=v[i].size()-1;
		while(l<r){
			ans-=(r-l)*min(v[i][l],n+1-v[i][r]);
			if(v[i][l]<(n+1-v[i][r])){
				l++;
			}else{
				r--;
			}
		}
	}
	cout <<ans;
	return 0;
}

最大直径（数学）

思路

解题思路分析

我们需要计算所有合法树的度数序列对应的最大直径之和。关键在于：

1. 确定什么样的度数序列是合法的（能构成树）
2. 对于每个合法序列，如何计算其能构造的树的最大直径
3. 如何高效地求和所有合法序列的最大直径

通过树的基本性质得出：

• 序列长度必须为$N$ ；
• 每个元素 $d_i \geq 1$ ；
• 所有元素之和必须等于 $2(N-1)$ 。

经过推导发现：

1. 最大直径与序列中非叶子节点（ $d_i \geq 2$ ）的数量直接相关；
2. 可以表示为：最大直径=(非叶子节点数)+1；
3. 进一步转化为： $D=(N-L)+1$ ，其中 $L$ 是叶子节点数。

需要计算：

1. 对于每个可能的叶子数 $L$ ，计算对应的序列数量；
2. 对每个 $L$ 计算其贡献值 $(N-L+1)$；
3. 总和为所有 $L$ 情况的贡献之和。

经过数学变换发现：

• 总和的表达式可以简化为组合数的线性组合
• 最终可以表示为两个组合数项的加权和

为了高效计算：

1. 预处理阶乘和逆元数组（ $f$ 和 $d$ ）；
2. 使用快速幂计算逆元；
3. 实现组合数查询函数 $solve(a,b)$ ；
4. 对每个测试用例$n$，直接套用推导出的公式计算：
   • $res1 = (n-3) \times C(2n-4,n-2)$；
   • $res2 = 2 \times C(2n-3,n-1)$；
   • 最终结果 = $(res1+res2) \mod 998244353$。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int tt=2e6+10,mod=998244353;
int f[tt],d[tt];

int qmi(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b=b>>1;
	}
	return res;
}

int solve(int a,int b){
	if(a<b||a<0||b<0) return 0;
	return f[a]*(d[a-b]*d[b]%mod)%mod;
}

signed main(){
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
	f[0]=1;
	for(int i=1;i<tt;i++){
		f[i]=(i*f[i-1])%mod;
	}
	d[tt-1]=qmi(f[tt-1],mod-2);
	for(int i=tt-1;i>=0;i--){
		d[i-1]=(d[i]*i)%mod;
	}
	int t;
	cin >>t;
	while(t--){
		int n;
		cin >>n;
		int res1=((n-3)*solve(2*n-4,n-2)%mod)%mod;
		int res2=(2*solve(2*n-3,n-1)%mod)%mod;
		cout <<(res1+res2)%mod<<endl;
	}
	return 0;
}

谢谢