T1
题意：
给一个由"("和")"组成的字符串s，\(ans_{i}\)表示\(i\)所在合法字符串的个数，求\(\sum_{i=1}^{n} (ans_{i}\times i\mod (10^{9}+7))\)
思路：
\(f_{i}\)表示\(i\)所对应的另一个括号，\(qian_{i}\)表示前面有几个和它同级的，\(hou_{i}\)表示后面有几个同级的。
\(f_{i}\)用栈求出。
\(qian_{i}=\left\{\begin{matrix}
s_{i}="(" &\left\{\begin{matrix}
s_{i-1}=")"& qian_{i-1}\\
s_{i-1}="(" &1
\end{matrix}\right.
\\
s_{i}=")" & qian_{f_{i}}
\end{matrix}\right.\)
\(hou_{i}=\left\{\begin{matrix} s_{i}=")" &\left\{\begin{matrix} s_{i+1}="("& hou_{i+1}\\ s_{i+1}=")" &1 \end{matrix}\right. \\ s_{i}="(" & hou_{f_{i}} \end{matrix}\right.\)
\(ans_{i}=\left\{\begin{matrix}
s_{i}=")"& \left\{\begin{matrix}
s_{i-1}=")"& ans_{i-1}-qian_{i-1}\times hou_{i-1}
\\
s_{i-1}="("& ans_{i-1}
\end{matrix}\right.
\\
s_{i}="("& \left\{\begin{matrix}
s_{i-1}="("& ans_{i-1}+qian_{i}\times hou_{i}
\\
s_{i-1}=")"& ans_{i-1}+qian_{i}\times hou_{i}-qian_{i-1}\times hou_{i-1}
\end{matrix}\right.
\end{matrix}\right.\)
代码：
#include<iostream>
#include<cstring>
#define mod 1000000007
#define int long long
using namespace std;
char s[10000010];
int qian[10000010];
int hou[10000010];
int zhan[10000010],top;
long long f;
long long ans=0;
int n;
signed main(){
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++){
if(s[i]=='('){
if(s[i-1]==')'){
qian[i]=qian[i-1]+1;
}
else{
qian[i]=1;
}
zhan[++top]=i;
}
else{
if(top>0){
qian[i]=qian[zhan[top]];
top--;
}
}
}
top=0;
for(int i=n;i>=1;i--){
if(s[i]==')'){
if(s[i+1]=='('){
hou[i]=hou[i+1]+1;
}
else{
hou[i]=1;
}
zhan[++top]=i;
}
else{
if(top>0){
hou[i]=hou[zhan[top]];
top--;
}
}
}
for(int i=1;i<=n;i++){
if(s[i]=='('){
f=(f+1ll*hou[i]*qian[i]%mod)%mod;
}
ans=ans+1ll*i*f%mod;
if(s[i]==')'){
f=((f-1ll*hou[i]*qian[i]%mod)%mod+mod)%mod;
}
}
cout<<ans;
return 0;
}
T2
题意：
将一个由数字字符组成的字符串，分成若干连续子串，是两相邻子串至少有一个被\(d\)整除，求方案数。
思路：
考虑\(\gcd(d,10)=1\)，设\(a_{i}\)表示\(s_{1\sim i}\)的十进制\(\times 10^{n-i}\)，用\(tong_{j,0/1}\)表示\(a_{i}=j\)，以\(i\)为结尾是否被\(d\)整除时总方案数，tot_{0/1}表示结尾是否被\(d\)整除时的总方案。
当\(\gcd(d,10)\ne 1\)，将\(d=d_{1}\times d_{2}\)，使\(\gcd(d_{1},10)=1\)，\(d_{2}=2^{k_{1}}\times 5^{k_{2}}\)，一段子串被\(d\)整除，就是被\(d_{1}\)和\(d_{2}\)同时整除。\(d_{1}\)同上，\(d_{2}\)暴力向前找20位。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#define mod 1000000007
#define int long long
using namespace std;
char s[1000010];
int a[1000010];
int b[1000010];
int cnt;
int n;
int d;
int d1;
int f;
int tot[2];
int tong[1000010][2];
int g[1000010][2];
signed main(){
scanf("%s",s+1);
n=strlen(s+1);
cin>>d;
d1=1;
while(d%2==0){
d/=2;
d1*=2;
}
while(d%5==0){
d/=5;
d1*=5;
}
for(int i=1;i<=n;i++){
b[i]=s[i]-'0';
a[i]=(a[i-1]*10+s[i]-'0')%d;
}
f=1;
for(int i=n;i>=1;i--){
a[i]=a[i]*f%d;
f=f*10%d;
}
tot[1]=1;
tong[0][1]=1;
g[0][1]=1;
for(int i=1;i<=n;i++){
int t=0;
int k=1;
for(int j=i;j>=i-20&&j>=1;j--){
t=(t+b[j]*k%d1)%d1;
k=k*10%d1;
}
int x=0,y=0;
if(t==0){
t=0;
k=1;
x=tong[a[i]][1],y=tong[a[i]][0];
for(int j=i;j>=i-20&&j>=1;j--){
t=(t+b[j]*k%d1)%d1;
if(t!=0&&a[i]==a[j-1]){
x=((x-g[j-1][1])%mod+mod)%mod;
y=((y-g[j-1][0])%mod+mod)%mod;
}
k=k*10%d1;
}
}
else{
t=0;
k=1;
for(int j=i;j>=i-20&&j>=1;j--){
t=(t+b[j]*k%d1)%d1;
if(t==0&&a[i]==a[j-1]){
x=(x+g[j-1][1])%mod;
y=(y+g[j-1][0])%mod;
}
k=k*10%d1;
}
}
g[i][0]=((tot[1]-x)%mod+mod)%mod;
g[i][1]=(x+y)%mod;
tot[0]=(tot[0]+g[i][0])%mod;
tot[1]=(tot[1]+g[i][1])%mod;
tong[a[i]][0]=(tong[a[i]][0]+g[i][0])%mod;
tong[a[i]][1]=(tong[a[i]][1]+g[i][1])%mod;
}
cout<<(g[n][0]+g[n][1])%mod;
return 0;
}
T3
题意：
给定一个由0和1组成的二维矩阵\(s_{i,j}\)，在每一行删掉一个数\(a_{i}\)，使得\(|a_{i}-a_{i-1}|\le k\)，问最后的矩阵有多少种情况。
思路：
\(f_{i,j}\)表示确定删除点\((i,j)\)有多少种不同的情况。
\(g_{i,j}\)表示确定删除点\((i,j)\)与确定删除点\((i,j-1)\)有多少种相同的情况。
\(f_{i,j}=\sum_{l=j-k}^{j+k} f_{i-1,l}-\sum_{l=j-k+1}^{j+k} g_{i-1,l}\)
\(g_{i,j}=\left\{\begin{matrix}
s_{i,j-1}=s_{i,j} & \sum_{l=j-k}^{j+k-1} f_{i-1,l}-\sum_{l=j-k+1}^{j+k-1} g_{i-1,l}\\
s_{i,j-1}\ne s_{i,j} & 0
\end{matrix}\right.\)
用前缀和维护即可。
代码：
#include<iostream>
#define mod 1000000007
using namespace std;
int kd(){
int x=0,f=1;
char a=getchar();
while(a<'0'||a>'9'){
if(a=='-'){
f=-1;
}
a=getchar();
}
while(a>='0'&&a<='9'){
x=x*10+a-'0';
a=getchar();
}
return x*f;
}
int n,m,k;
char s[3010][3010];
int a[3010][3010];
int f[3010][3010];
int g[3010][3010];
int qian[3010][3010];
int jian[3010][3010];
int main(){
n=kd();m=kd();k=kd();
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
for(int j=1;j<=m;j++){
a[i][j]=s[i][j]-'0';
}
}
for(int j=1;j<=m;j++){
f[1][j]=1;
qian[1][j]=j;
}
for(int j=2;j<=m;j++){
if(a[1][j]==a[1][j-1]){
g[1][j]=1;
}
jian[1][j]=jian[1][j-1]+g[1][j];
}
for(int i=2;i<=n;i++){
for(int j=1;j<=m;j++){
if(j<=k){
f[i][j]=(qian[i-1][min(j+k,m)]-jian[i-1][min(j+k,m)]+mod)%mod;
}
else{
f[i][j]=(0ll+((qian[i-1][min(j+k,m)]-qian[i-1][j-k-1])-(jian[i-1][min(j+k,m)]-jian[i-1][j-k]))%mod+mod)%mod;
}
qian[i][j]=(qian[i][j-1]+f[i][j])%mod;
if(j>=2&&a[i][j]==a[i][j-1]){
if(j<=k){
g[i][j]=(qian[i-1][min(j+k-1,m)]-jian[i-1][min(j+k-1,m)]+mod)%mod;
}
else{
g[i][j]=(0ll+((qian[i-1][min(j+k-1,m)]-qian[i-1][j-k-1])-(jian[i-1][min(j+k-1,m)]-jian[i-1][j-k]))%mod+mod)%mod;
}
}
jian[i][j]=(jian[i][j-1]+g[i][j])%mod;
}
}
cout<<(qian[n][m]-jian[n][m]+mod)%mod;
return 0;
}
T4
题意：
给定一个\(n\)个点，\(m\)条边的图，\(q\)次询问，问\(u\)和\(v\)简单路径的次大值的最小值。
思路：
将\(m\)从小到大，加入图中，当加入一条边后\(u\)和\(v\)差一条边，答案就是这条边的权值。
考虑使用set维护边和询问，使用并查集和启发式合并合并连通块。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#include<array>
#include<set>
using namespace std;
int kd(){
int x=0,f=1;
char a=getchar();
while(a<'0'||a>'9'){
if(a=='-'){
f=-1;
}
a=getchar();
}
while(a>='0'&&a<='9'){
x=x*10+a-'0';
a=getchar();
}
return x*f;
}
int n,m,q;
struct node{
int u,v,w;
}bian[400010];
bool cmp(node x,node y){
return x.w<y.w;
}
set<int> e[100010];
set<array<int,2> >ques[100010];
int fa[100010];
int ans[100010];
int cha(int u){
if(u==fa[u]){
return u;
}
return fa[u]=cha(fa[u]);
}
void work(int x,int y,int val){
for(auto u:e[x]){
while(1){
auto it=ques[y].lower_bound({u,-1});
if(it==ques[y].end()||(*it)[0]!=u){
break;
}
int id=(*it)[1];
ans[id]=val;
ques[y].erase({u,id});
ques[u].erase({y,id});
}
}
vector<array<int,3> >del;
for(auto u:ques[x]){
if(e[y].count(u[0])){
ans[u[1]]=val;
del.push_back({x,u[0],u[1]});
}
}
for(auto u:del){
ques[u[0]].erase({u[1],u[2]});
ques[u[1]].erase({u[0],u[2]});
}
del.clear();
for(auto u:e[x]){
if(u!=y){
e[y].insert(u);
e[u].insert(y);
}
e[u].erase(x);
}
e[x].clear();
for(auto u:ques[x]){
ques[y].insert(u);
ques[u[0]].insert({y,u[1]});
ques[u[0]].erase({x,u[1]});
}
ques[x].clear();
fa[x]=y;
}
int main(){
n=kd();m=kd();q=kd();
for(int i=1;i<=n;i++){
fa[i]=i;
}
for(int i=1;i<=q;i++){
ans[i]=-1;
}
for(int i=1;i<=m;i++){
bian[i].u=kd();bian[i].v=kd();bian[i].w=kd();
e[bian[i].u].insert(bian[i].v);
e[bian[i].v].insert(bian[i].u);
}
for(int i=1;i<=q;i++){
int u,v;
u=kd();v=kd();
if(e[u].count(v)){
ans[i]=0;
}
else{
ques[u].insert({v,i});
ques[v].insert({u,i});
}
}
sort(bian+1,bian+m+1,cmp);
for(int i=1;i<=m;i++){
bian[i].u=cha(bian[i].u);
bian[i].v=cha(bian[i].v);
if(bian[i].u!=bian[i].v){
if(ques[bian[i].u].size()+e[bian[i].u].size()>ques[bian[i].v].size()+e[bian[i].v].size()){
swap(bian[i].u,bian[i].v);
}
work(bian[i].u,bian[i].v,bian[i].w);
}
}
for(int i=1;i<=q;i++){
cout<<ans[i]<<endl;
}
return 0;
}