A
Description
给一个 01 串设为其 S，询问是否存在只出现两次的 01 串 T。
这里的出现定义为存在一串下标 
Input
一行，一个 01 串
Output
一行，字母 Y 表示存在，N 表示不存在
HINT
1.设串 S 的长度为 n，
2.设串 S 的长度为 n，
3.设串 S 的长度为 n，
4.数据为随机生成。
对于第一部分，随意骗一骗分？
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[],num0,num1;
int main()
{
scanf("%s",s);
int len=strlen(s);
for(int i=;i<len;i++)
if(s[i]=='')num0++;
else num1++;
if((num0%&&num1%)||num0==||num1==)printf("N");
else printf("Y");
return ;
}
对于第二部分，暴力dfs。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=<<;
int n,a[],calc[][N];
char s[];
bool f;
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(x=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void dfs(int x,int sum,int num,int k)
{
sum=sum*+a[x];
if(a[x]||k)k=;
else num++;
calc[num][sum]++;
for(int i=x+;i<=n;i++)dfs(i,sum,num,k);
}
int main()
{
scanf("%s",s);
n=strlen(s);
for(int i=;i<n;i++)a[i+]=s[i]-'';
for(int i=;i<=n;i++)dfs(i,,,);
int summ=<<n;
for(int i=;i<=n;i++)
for(int j=;j<summ;j++)
if(calc[i][j]==){f=true;break;}
if(f)printf("Y");
else printf("N");
return ;
}
对于第三部分，注意特判0和1的个数恰好为2的情况。
对于其他情况，若存在形如abcd（a!=b,b==c,c!=d）（即0110或1001）类型的子串，则输出Y：此时T为 b前面的所有数字+b（也是c）+后面的所有数字。若不存在，则输出N：对于相邻相同数字长度超过2的子串，在T中必定是全部出现，否则会出现3种及3种以上情况，不满足T的要求；对于相邻数字互不相同的子串，不管怎么选只有一种或多种情况，不满足出现次数恰好为2，此时对于这部分子串倾向于全选（保持出现次数小于2）。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,zero;
char s[];
bool f;
int main()
{
scanf("%s",s+);
n=strlen(s+);
for(int i=;i<=n;i++)
if(s[i]=='')zero++;
if(zero==||n-zero==)f=true;
for(int i=;i<n-;i++)
if(s[i]!=s[i+]&&s[i+]==s[i+]&&s[i+]!=s[i+])f=true;
if(f)printf("Y");
else printf("N");
return ;
}
B
Description
给长度为 n 的数列 A 和长度为 m 的数列 B，问有多少长度为 m 的数列 C 满足
Input
第一行俩整数 n 和 m
第二行 n 个整数 
第三行 m 个整数 
Output
一个整数，表示满足条件的数列 C 的个数模 
HINT
1.
2.
3.
对于第一部分，比赛时暴力dfs。（不要问我为什么不写dp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,ans,a[],b[];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(x=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void dfs(int x,int deep)
{
if(m-deep>n-x)return;
if(deep==m){ans++;return;}
for(int i=x+;i<=n;i++)
if(a[i]-a[x]+b[deep]>=)dfs(i,deep+);
}
int main()
{
n=read();m=read();
for(int i=;i<=n;i++)a[i]=read();
for(int i=;i<=m;i++)b[i]=read();
if(m==){printf("%d",n);return ;}
for(int i=;i<m;i++)b[i]=b[i+]-b[i];
for(int i=;i<=n;i++)dfs(i,);
printf("%d",ans);
return ;
}
对于第二、三部分，dp+树状数组。
为了方便操作，先进行离散化。num数组是一个队列，存的是原数列离散化后的编号所对应的原值（下标为1~cnt）；id[i]代表原数列中下标为i的数字离散化后的编号。
每次都枚举b[i]并重新计算g数组（g[j]代表满足num[k]+b[i-1]<=num[j]+b[i]中k的最大值）。
然后就是愉快的单点修改区间查询了√
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=;
const int mod=1e9+;
int n,m,cnt,ans;
int b[N],id[N],num[N],t[N],f[N],g[N];
struct node{int w,pos;}a[N];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(x=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
bool cmp(node a,node b){return a.w<b.w;}
int lowbit(int x){return x&-x;}
void insert(int x,int v)
{
while(x<=n)
{
t[x]=(t[x]+v)%mod;
x+=lowbit(x);
}
}
int query(int x)
{
int ans=;
while(x)
{
ans=(ans+t[x])%mod;
x-=lowbit(x);
}
return ans;
}
int main()
{
n=read();m=read();
for(int i=;i<=n;i++)
a[i].w=read(),a[i].pos=i,f[i]=;
sort(a+,a+n+,cmp);
for(int i=;i<=n;i++)
if(a[i].w==a[i-].w)id[a[i].pos]=cnt;
else id[a[i].pos]=++cnt,num[cnt]=a[i].w;
for(int i=;i<=m;i++)b[i]=read();
for(int i=;i<=m;i++)
{
for(int j=;j<=cnt;j++)
{
int u=g[j-];
while(u<cnt&&num[u+]+b[i-]<=num[j]+b[i])u++;
g[j]=u;
}
memset(t,,sizeof(t));
insert(id[i-],f[i-]);
for(int j=i;j<=n;j++)
{
int sum=f[j];
f[j]=query(g[id[j]]);
insert(id[j],sum);
}
}
for(int i=m;i<=n;i++)ans=(ans+f[i])%mod;
printf("%d",ans);
return ;
}
C
Description
给一个图，n 个点 m 条双向边，每条边有其长度。n 个点中有 k 个是特殊点，问任意两个特殊点的最短路是多少。
Input
第一行三个整数 n m k
第二行 k 个整数
接下来 m 行，每行三个整数 x y d，表示 x 到 y 有一条长度为 d 的边
Output
一个整数
HINT
1.
2.
3.
4.图为联通图
对于第一部分，Floyd水过。（注意重边和自环！）
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,k,x,y,d,t,ans=inf;
int dis[][];
bool f[];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(x=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int main()
{
n=read();m=read();k=read();
for(int i=;i<=k;i++)
{
t=read();
f[t]=true;
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(i!=j)dis[i][j]=inf;
for(int i=;i<=m;i++)
{
x=read();y=read();d=read();
dis[x][y]=dis[y][x]=min(dis[x][y],d);
if(f[x]&&f[y]&&x!=y)ans=min(ans,dis[x][y]);
}
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(dis[i][j]>dis[i][k]+dis[k][j] )
{
dis[i][j]=dis[i][k]+dis[k][j];
if(f[i]&&f[j])ans=min(ans,dis[i][j]);
}
printf("%d",ans);
return ;
}
对于第二部分，跑k次SPFA。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=;
const int inf=0x3f3f3f3f;
int n,m,k,x,y,t,cnt,ans=inf;
int first[N],a[N],dis[N],q[N];
bool f[N],in[N];
struct edge{int next,to,w;}e[N*];
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(x=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void ins(int x,int y,int w){cnt++;e[cnt].to=y;e[cnt].w=w;e[cnt].next=first[x];first[x]=cnt;}
void spfa(int S)
{
memset(in,,sizeof(in));
memset(dis,0x3f,sizeof(dis));
int head=,tail=;
q[]=S;in[S]=true;dis[S]=;
while(head!=tail)
{
int u=q[head++];in[u]=false;
if(head>)head=;
for(int i=first[u];i;i=e[i].next)
{
int v=e[i].to;
if(dis[u]+e[i].w<dis[v])
{
dis[v]=dis[u]+e[i].w;
if(f[v])ans=min(ans,dis[v]);
if(!in[v]){q[tail++]=v;in[v]=true;if(tail>)tail=;}
}
}
}
}
int main()
{
n=read();m=read();k=read();
for(int i=;i<=k;i++)a[i]=read(),f[a[i]]=true;
for(int i=;i<=m;i++)
{
x=read();y=read();t=read();
ins(x,y,t);ins(y,x,t);
}
for(int i=;i<=k;i++)spfa(a[i]);
printf("%d",ans);
return ;
}
对于第三部分，对于每个点，维护以下信息：离它最近的特殊点及路程，离它次近的特殊点及路程（且需保证两个特殊点不同）。最后再枚举点，用最短路+次短路来更新答案。（看到好多大佬都是枚举边……瑟瑟发抖。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=;
const int inf=0x3f3f3f3f;
int n,m,k,cnt,x,y,w,ans=inf;
int a[],first[N],fir[N],sec[N],firn[N],secn[N];
struct edge{int to,next,w;}e[N*];
struct node
{
int d,id;
bool operator <(const node& x)const{return x.d<d;}
};
priority_queue<node>q;
int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(x=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
void ins(int x,int y,int w)
{
cnt++;e[cnt].to=y;e[cnt].w=w;
e[cnt].next=first[x];first[x]=cnt;
}
void dijkstra()
{
memset(fir,0x3f,sizeof(fir));
memset(sec,0x3f,sizeof(sec));
for(int i=;i<=k;i++)
{
fir[a[i]]=;firn[a[i]]=a[i];
q.push((node){,a[i]});
}
while(!q.empty())
{
node x=q.top();q.pop();
if(x.d>fir[x.id])continue;
int now=x.id;
for(int i=first[now];i;i=e[i].next)
{
int to=e[i].to;
if(firn[now]==firn[to])
{
if(fir[now]+e[i].w<fir[to])
fir[to]=fir[now]+e[i].w,q.push((node){fir[to],to});
}
else if(fir[now]+e[i].w<fir[to])
{
sec[to]=fir[to];secn[to]=firn[to];
fir[to]=fir[now]+e[i].w;firn[to]=firn[now];
q.push((node){fir[to],to});
// printf("[fir]%d %d %d [n] %d %d\n",now,to,fir[to],firn[now],firn[to]);
}
else if(fir[now]+e[i].w<sec[to])
{
sec[to]=fir[now]+e[i].w;
secn[to]=firn[now];
// printf("[sec]%d %d %d [n] %d %d\n",now,to,sec[to],secn[now],secn[to]);
}
}
}
}
int main()
{
n=read();m=read();k=read();
for(int i=;i<=k;i++)a[i]=read();
for(int i=;i<=m;i++)
{
x=read();y=read();w=read();
ins(x,y,w);ins(y,x,w);
}
dijkstra();
for(int i=;i<=n;i++)ans=min(ans,fir[i]+sec[i]);
printf("%d",ans);
return ;
}