T1 先预处理，再暴力即可，AC代码
#include<bits/stdc++.h>
using namespace std;
int mp[100001];
int b[100001];
int c[100001];
long long ans=0;
int main(){
freopen("cross.in","r",stdin);
freopen("cross.out","w",stdout);
string s;
cin>>s;
for(int i=0;i<s.size();i++){
c[(int)s[i]]++;
if(c[(int)s[i]]%2==0){
b[i]=0;
b[mp[(int)s[i]]]=i;
mp[(int)s[i]]=0;
}
if(c[(int)s[i]]%2==1){
mp[(int)s[i]]=i;
}
}
for(int i=0;i<s.size();i++){
for(int j=i+1;j<b[i];j++){
if(b[j]>b[i])ans++;
}
}
cout<<ans;
return 0;
}
T2求[1+n+n^2+n^3+…n^(k-1)]%p的值
根据等比数列求和公式，原式=（n^k-1)/（k-1）%p
看到%70 p是质数，想到逆元
设n^k-1=a,k-1=b
由于p是质数，所以b^（p-2）是式子的一个逆元
设d=b^(p-2) 即由逆元性质得
a/b%p=a*d%p 最后再用快速幂优化即可 70分代码
#include<bits/stdc++.h>
using namespace std;
long long k,n,p;
long long pow1(long long a,long long b){
if(b==0){
return 1;
}
if(b==1){
return a%p;
}
if(b%2==0){
return (pow1(a,b/2)%p*pow1(a,b/2)%p)%p;
}
if(b%2==1){
return (pow1(a,b/2)%p*pow1(a,b/2)%p)%p*a%p;
}
}
int main(){
freopen("split.in","r",stdin);
freopen("split.out","w",stdout);
cin>>k>>n>>p;
n--;
cout<<(pow1(k,n)-1)*pow1(k-1,p-2)%p;
return 0;
}
T3 考场上没想到vector存图，还文件读写错误 0分
dp[i]=INT_MAX会被卡,随便换一个大数即可
dp即可过 AC代码
#include<bits/stdc++.h>
using namespace std;
int n,ml,md,dp[2000001];
vector <int> r[2000001][2];
int main(){
freopen("jogging.in","r",stdin);
freopen("jogging.out","w",stdout);
cin>>n>>ml>>md;
for(int i=1;i<=ml;i++){
int a,b,c;
cin>>a>>b>>c;
if(a>b)swap(a,b);
r[b][0].push_back(a);
r[b][1].push_back(c);
}
for(int i=1;i<=md;i++){
int a1,b1,c1;
cin>>a1>>b1>>c1;
if(a1>b1)swap(a1,b1);
r[b1][0].push_back(a1);
r[b1][1].push_back(-c1);
}
for(int i=2;i<=n;i++){
dp[i]=100100100;
for(int j=0;j<r[i][0].size();j++){
dp[i]=min(dp[i],dp[r[i][0][j]]+r[i][1][j]);
}
}
cout<<dp[n]<<endl;
if(dp[n]>0){
cout<<"NO";
}
else{
cout<<"YES";
}
return 0;
}