【五一qbxt】test1
（不知道為什么居然爆零了qwq）
（全員爆零誒，最高分10分？？？還是rand出來的？？？）
我freopen寫錯了？？？？自閉了
不行不行再寫一遍freopen加深印象，不能再寫錯了
freopen("文件名","r",stdin);
freopen("文件名","w",stdout);
行吧，還是來整一整老師給的題解吧qwq
忍不住bibi一句出題的這個哥哥好年輕啊qwq，我都不好意思叫人家老師，應該是哥哥
題目
Problem A.最近公共祖先
先列一個表格
這樣大概就理解71是怎么出來的了
30pts思路：
將整棵樹建出，共有 O(Kn) 個節點，計算任意兩個節點的LCA 復雜度 O(n)。
注意到沒有必要將所有點對的 LCA 都計算出來， 因為對于同一層的兩個節點 u 和 v，
∑ i ∈T depth(lca(i, u)) 和 ∑ i ∈Tdepth(lca(i, v)) 是相同的， 每一層只需要算一個節點就行， 時間復雜 度 O(n2K n) 。
（以上是老師的思路，但是我現在對建樹這種事有點蒙？？？當時考試的時候爆零了qwq，實際上我的暴力也是可以得30分的。下次一定得記得開long long）
先帶上一個七十多行的大暴力：
30分代碼：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define mo 998244353 using namespace std; long long k,n,ans,s,z;
int t[]; struct c{
int num1,num2;
//num1表示以這一層為根的子樹的結點數
//num2表示這一層的結點數
}ceng[]; int quick_pow(int a,int b) { //快速冪
int ans=;
if(b==)return ;
while(b){
if(b&)ans=(a*ans)%mo;
a=(a*a)%mo;
b/=;
}
return ans%mo;
} int num1(int n,int k){//求子樹點數 n層k叉樹
int z=n-;
int num=;
while(z){
num+=quick_pow(k,z);
z--;
}
return num+;
} void ych(){
for(int i=;i<=n;i++){
ceng[n-i+].num1=num1(i,k);//以這一層為根的子樹的結點數
ceng[i].num2=quick_pow(k,i-);//這一層的結點數
} } int main(){ scanf("%d%d",&n,&k); ych();//他本來叫做預處理，后來被我改成了于才鴻 for(int i=;i<=n;i++)
ans+=num1(n-i+,k)*quick_pow(k,i-)*i;//求的是子樹的
//這里算的是某個點以下的depth之和包括它自己 for(int i=;i<=n;i++)
s+=i*quick_pow(k,i-);//這里算的是每個點自己的depth和 ans-=s;
ans=ans*%mo; for(int i=;i<=n;i++){
for(int j=;j<i;j++){
z+=(k-)*ceng[i-j+].num1*(i-j)*quick_pow(k,i-);
//算的是同一深度的
}
} ans+=z;
ans%=mo; cout<<(ans+s)%mo<<endl;
return ;
}
60pts思路:
更一般的，題目計算的是任意兩個點 LCA 的深度，這個數量等于，任意兩個點公共的祖先共有多少個。考慮計算第 i 層的某個節點，是多少個點對的公共祖先，這個數量就是該節點子樹內節點數的平方。第 i 層的節點所在子樹節點數 1+K+···+K n−i=（Kn−i+1−1）/(K−1) 。答案就是 ∑n i=1 ( （Kn−i+1−1）/（K−1） ) 2 ∗ K i−1
即：
求任意兩點LCA深度=>任意兩點公共祖先數量=>a是多少個點對的公共祖先（枚舉對于每個數a，它是x，y的公共祖先=>x，y在a的子樹里。有多少個點在a的子樹中呢？）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
const int mo=; using namespace std; long long ans,k1; int n; long long pow(long long a,int b){
long long ans=;
if(b==)return ;
while(b){
if(b&)ans = (a*ans)%mo;
a = (a*a)%mo;
b/=;
}
return ans%mo;
} int main(){
scanf("%d%lld",&n,&k1); for(int i=;i<=n;i++)
ans=(ans+pow((long long)(pow(k1,n-i+)-)%mo*pow(k1-,mo-)%mo,)*pow(k1,i-))%mo;
//核心式子的編程語言 cout<<ans%mo<<endl;
}
100pts思路：
#include <bits/stdc++.h> using namespace std; const int mod = ;
typedef long long LL;
int fpm(int p, int k)
{
int res = ;
for (p %= mod; k; k >>= , p = (LL) p * p % mod)
if (k & ) res = (LL) res * p % mod;
return res;
}
int main()
{
// freopen("lca.in", "r", stdin);
// freopen("lca.out", "w", stdout);
int n, K; cin >> n >> K;
int e = fpm(K - , mod - ); //e=1/(K-1)
int x = (fpm(K, n) - ) * (LL) e % mod; //x=(K^n-1)/(K-1);
int ans = (fpm(K, n + ) + ) * (LL) x % mod;//ans=(K^(n+1)+1)*((K^n-1)/(K-1))
ans = (ans - * n * (LL) fpm(K, n)) % mod;//ans=(K^(n+1)+1)*((K^n-1)/(K-1))-2nK^n;
ans = ans * (LL) e % mod * (LL) e % mod;//ans*=(1/(K-1))^2;
cout << (ans < ? ans + mod : ans);//三目運算符，判斷是否為負數
}
Problem2：最長公共回文子序列：
50pts思路：
經典的做法：
設s，t的反串（eg：abbsf 反串fsbba）為sr，tr，那么求s和t的最長公共回文序列就是求s，sr，t，tr的最長公共子序列。
如何求最長公共子序列？
用DP！
怎么用？
粘一篇別人的博客吧：鏈接
對于二維的轉移方程：
dp[i][j]= dp[i-1][j-1] s[i]=t[j];
max{dp[i-1][j],dp[i][j-1]} s[i]!=t[j];
對于四維的：
用一個DP來做就可以得到50pts了：
然鵝我……寫炸了。
#include<bits/stdc++.h> using namespace std; int s[],t[],sr[],tr[];
int len_s,len_t,max1,max2;
int dp[][][][];
char s1[],t1[]; void scl(){
for(int i=;i<len_s;i++){
sr[len_s-i]=s1[i];
s[i+]=s1[i];
}
for(int i=;i<len_t;i++){
tr[len_t-i]=t1[i];
t[i+]=t1[i];
}
} int main(){
scanf("%s",s1);
scanf("%s",t1);
len_s=strlen(s1);
len_t=strlen(t1);
scl();
for(int i=;i<=len_s;i++){
for(int j=;j<=len_t;j++){
for(int k=;k<=len_s;k++){
for(int l=;l<=len_t;l++){
if(s[i]==sr[k]&&s[i]==t[j]&&s[i]==tr[l]&&sr[k]==t[j]&&sr[k]==tr[l]&&t[j]==tr[l])
//注意這里不能略寫為s[i]==t[j]==sr[k]==tr[l]{
dp[i][j][k][l]=dp[i-][j-][k-][l-]+;
}
else {
max1=max(dp[i-][j][k][l],dp[i][j-][k][l]);
max2=max(dp[i][j][k-][l],dp[i][j][k][l-]);
dp[i][j][k][l]=max(max1,max2);
}
}
}
}
}
cout<<dp[len_s][len_t][len_s][len_t]<<endl;
}
100pts：
暴力：一位一位的遍歷，O（n*2m）
顯然很慢啊qwq；
加速？？？
維護一個26*n的數組，記錄距離某個位置最近的某個字母（26個字母）在哪兒；
不會寫qwq自閉
Problem3：
直接講100pts的貪心：
這個題的原理忘記為啥了？？？
即解一個二元一次方程組13a+5b=t。
所以我們分別枚舉a，b找到最小的t；
復雜度O（30n）
總結
以上是生活随笔為你收集整理的【五一qbxt】test1的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 别了，DjVu！
- 下一篇： 基于Apache Hudi和Debezi