【解题报告】SRM-08

A

Description

给一个 01 串设为其 S，询问是否存在只出现两次的 01 串 T。

这里的出现定义为存在一串下标 $a_1,a_2,...,a_m$ ，满足 $a_1<a_2<...<a_m$ 且 $S_{a_i}=T_i$ 。

Input

一行，一个 01 串

Output

一行，字母 Y 表示存在，N 表示不存在

HINT

1.设串 S 的长度为 n， $2leq nleq 3$ 。

2.设串 S 的长度为 n， $2leq nleq 10$ 。

3.设串 S 的长度为 n， $2leq nleq 5000$ 。

4.数据为随机生成。

对于第一部分，随意骗一骗分？

 1 #include<cstdio>
 2 #include<algorithm> 
 3 #include<cstring>
 4 using namespace std;
 5 char s[5],num0,num1;
 6 int main()
 7 {
 8     scanf("%s",s);
 9     int len=strlen(s);
10     for(int i=0;i<len;i++)
11         if(s[i]=='0')num0++;
12         else num1++;
13     if((num0%2&&num1%2)||num0==3||num1==3)printf("N");
14     else printf("Y");
15     return 0;
16 }

View Code

对于第二部分，暴力dfs。

 1 #include<cstdio>
 2 #include<algorithm> 
 3 #include<cstring>
 4 using namespace std;
 5 const int N=1<<12;
 6 int n,a[15],calc[15][N];
 7 char s[15];
 8 bool f;
 9 int read()
10 {
11     int x=0,f=1;char c=getchar();
12     while(c<'0'||c>'9'){if(x=='-')f=-1;c=getchar();}
13     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
14     return x*f;
15 }
16 void dfs(int x,int sum,int num,int k)
17 {
18     sum=sum*2+a[x];
19     if(a[x]||k)k=1;
20     else num++;
21     calc[num][sum]++;
22     for(int i=x+1;i<=n;i++)dfs(i,sum,num,k);
23 }
24 int main()
25 {
26     scanf("%s",s);
27     n=strlen(s);
28     for(int i=0;i<n;i++)a[i+1]=s[i]-'0';
29     for(int i=1;i<=n;i++)dfs(i,0,0,0);
30     int summ=1<<n;
31     for(int i=0;i<=n;i++)
32         for(int j=0;j<summ;j++)
33             if(calc[i][j]==2){f=true;break;}
34     if(f)printf("Y");
35     else printf("N");
36     return 0;
37 }

View Code

对于第三部分，注意特判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）。

 1 #include<cstdio>
 2 #include<algorithm> 
 3 #include<cstring>
 4 using namespace std;
 5 int n,zero;
 6 char s[5010];
 7 bool f;
 8 int main()
 9 {
10     scanf("%s",s+1);
11     n=strlen(s+1);
12     for(int i=1;i<=n;i++)
13         if(s[i]=='0')zero++;
14     if(zero==2||n-zero==2)f=true;
15     for(int i=0;i<n-1;i++)
16         if(s[i]!=s[i+1]&&s[i+1]==s[i+2]&&s[i+2]!=s[i+3])f=true;
17     if(f)printf("Y");
18     else printf("N");
19     return 0;
20 }

View Code

B

Description

给长度为 n 的数列 A 和长度为 m 的数列 B，问有多少长度为 m 的数列 C 满足

$1 leq C_1<C_2<...<C_mleq n$ 且 $(A_{c_1}+B_1) leq (A_{c_2}+B_2) leq ... leq (A_{c_m}+B_m)$

Input

第一行俩整数 n 和 m

第二行 n 个整数 $A_i$ ，表示数列 A

第三行 m 个整数 $B_i$ ，表示数列 B

Output

一个整数，表示满足条件的数列 C 的个数模 $10^9+7$ 后的值。

HINT

1. $1 leq A_i, B_i leq 10^9$ $1 leq m leq n$ $1 leq n leq 50, 1leq m leq 5$

2. $1 leq A_i, B_i leq 10^9$ $1 leq m leq n$ $1 leq n leq 500, 1leq m leq 50$

3. $1 leq A_i, B_i leq 10^9$ $1 leq m leq n$ $1 leq n leq 2000, 1leq m leq 1000$

对于第一部分，比赛时暴力dfs。（不要问我为什么不写dp

 1 #include<cstdio>
 2 #include<algorithm> 
 3 #include<cstring>
 4 using namespace std;
 5 int n,m,ans,a[55],b[10];
 6 int read()
 7 {
 8     int x=0,f=1;char c=getchar();
 9     while(c<'0'||c>'9'){if(x=='-')f=-1;c=getchar();}
10     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
11     return x*f;
12 }
13 void dfs(int x,int deep)
14 {
15     if(m-deep>n-x)return;
16     if(deep==m){ans++;return;}
17     for(int i=x+1;i<=n;i++)
18         if(a[i]-a[x]+b[deep]>=0)dfs(i,deep+1);
19 }
20 int main()
21 {
22     n=read();m=read();
23     for(int i=1;i<=n;i++)a[i]=read();
24     for(int i=1;i<=m;i++)b[i]=read();
25     if(m==1){printf("%d",n);return 0;}
26     for(int i=1;i<m;i++)b[i]=b[i+1]-b[i];
27     for(int i=1;i<=n;i++)dfs(i,1);
28     printf("%d",ans);
29     return 0;
30 }

View Code

对于第二、三部分，dp+树状数组。

为了方便操作，先进行离散化。num数组是一个队列，存的是原数列离散化后的编号所对应的原值（下标为1~cnt）；id[i]代表原数列中下标为i的数字离散化后的编号。

每次都枚举b[i]并重新计算g数组（g[j]代表满足num[k]+b[i-1]<=num[j]+b[i]中k的最大值）。

然后就是愉快的单点修改区间查询了√

 1 #include<cstdio>
 2 #include<algorithm> 
 3 #include<cstring>
 4 using namespace std;
 5 const int N=2010;
 6 const int mod=1e9+7;
 7 int n,m,cnt,ans;
 8 int b[N],id[N],num[N],t[N],f[N],g[N];
 9 struct node{int w,pos;}a[N];
10 int read()
11 {
12     int x=0,f=1;char c=getchar();
13     while(c<'0'||c>'9'){if(x=='-')f=-1;c=getchar();}
14     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
15     return x*f;
16 }
17 bool cmp(node a,node b){return a.w<b.w;}
18 int lowbit(int x){return x&-x;}
19 void insert(int x,int v)
20 {
21     while(x<=n)
22     {
23         t[x]=(t[x]+v)%mod;
24         x+=lowbit(x);
25     }
26 }
27 int query(int x)
28 {
29     int ans=0;
30     while(x)
31     {
32         ans=(ans+t[x])%mod;
33         x-=lowbit(x);
34     }
35     return ans;
36 }
37 int main()
38 {
39     n=read();m=read();
40     for(int i=1;i<=n;i++)
41         a[i].w=read(),a[i].pos=i,f[i]=1;
42     sort(a+1,a+n+1,cmp);
43     for(int i=1;i<=n;i++)
44         if(a[i].w==a[i-1].w)id[a[i].pos]=cnt;
45         else id[a[i].pos]=++cnt,num[cnt]=a[i].w;
46     for(int i=1;i<=m;i++)b[i]=read();
47     for(int i=2;i<=m;i++)
48     {
49         for(int j=1;j<=cnt;j++)
50         {
51             int u=g[j-1];
52             while(u<cnt&&num[u+1]+b[i-1]<=num[j]+b[i])u++;
53             g[j]=u;
54         }
55         memset(t,0,sizeof(t));
56         insert(id[i-1],f[i-1]);
57         for(int j=i;j<=n;j++)
58         {
59             int sum=f[j];
60             f[j]=query(g[id[j]]);
61             insert(id[j],sum);
62         }
63     }
64     for(int i=m;i<=n;i++)ans=(ans+f[i])%mod;
65     printf("%d",ans);
66     return 0;
67 }

View Code

C

Description

给一个图，n 个点 m 条双向边，每条边有其长度。n 个点中有 k 个是特殊点，问任意两个特殊点的最短路是多少。

Input

第一行三个整数 n m k

第二行 k 个整数 $A_i$ ，为各个特殊点

接下来 m 行，每行三个整数 x y d，表示 x 到 y 有一条长度为 d 的边

Output

一个整数

HINT

1. $1 leq A_i,x,y leq n$ $1 leq d leq 10000$ $2 leq n leq 300$ $n-1 leq m leq 100000$ $2 leq k leq n$

2. $1 leq A_i,x,y leq n$ $1 leq d leq 10000$ $2 leq n leq 100000$ $n-1 leq m leq 100000$ $2 leq k leq 10$

3. $1 leq A_i,x,y leq n$ $1 leq d leq 10000$ $2 leq n leq 100000$ $n-1 leq m leq 300000$ $2 leq k leq 10000$

4.图为联通图

对于第一部分，Floyd水过。（注意重边和自环！）

 1 #include<cstdio>
 2 #include<algorithm> 
 3 #include<cstring>
 4 using namespace std;
 5 const int inf=0x3f3f3f3f;
 6 int n,m,k,x,y,d,t,ans=inf;
 7 int dis[305][305];
 8 bool f[305];
 9 int read()
10 {
11     int x=0,f=1;char c=getchar();
12     while(c<'0'||c>'9'){if(x=='-')f=-1;c=getchar();}
13     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
14     return x*f;
15 }
16 int main()
17 {
18     n=read();m=read();k=read();
19     for(int i=1;i<=k;i++)
20     {
21         t=read();
22         f[t]=true;
23     }
24     for(int i=1;i<=n;i++)
25         for(int j=1;j<=n;j++)
26             if(i!=j)dis[i][j]=inf;
27     for(int i=1;i<=m;i++)
28     {
29         x=read();y=read();d=read();
30         dis[x][y]=dis[y][x]=min(dis[x][y],d);
31         if(f[x]&&f[y]&&x!=y)ans=min(ans,dis[x][y]);
32     }
33     for(int k=1;k<=n;k++)
34         for(int i=1;i<=n;i++)
35             for(int j=1;j<=n;j++)
36                 if(dis[i][j]>dis[i][k]+dis[k][j] )   
37                  {
38                      dis[i][j]=dis[i][k]+dis[k][j];
39                      if(f[i]&&f[j])ans=min(ans,dis[i][j]);
40                  }
41     printf("%d",ans);
42     return 0;
43 }

View Code

对于第二部分，跑k次SPFA。

 1 #include<cstdio>
 2 #include<algorithm> 
 3 #include<cstring>
 4 using namespace std;
 5 const int N=100010;
 6 const int inf=0x3f3f3f3f;
 7 int n,m,k,x,y,t,cnt,ans=inf;
 8 int first[N],a[N],dis[N],q[N];
 9 bool f[N],in[N];
10 struct edge{int next,to,w;}e[N*2];
11 int read()
12 {
13     int x=0,f=1;char c=getchar();
14     while(c<'0'||c>'9'){if(x=='-')f=-1;c=getchar();}
15     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
16     return x*f;
17 }
18 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;}
19 void spfa(int S)
20 {
21     memset(in,0,sizeof(in));
22     memset(dis,0x3f,sizeof(dis));
23     int head=0,tail=1;
24     q[0]=S;in[S]=true;dis[S]=0;
25     while(head!=tail)
26     {
27         int u=q[head++];in[u]=false;
28         if(head>100000)head=0;
29         for(int i=first[u];i;i=e[i].next)
30         {
31             int v=e[i].to;
32             if(dis[u]+e[i].w<dis[v])
33             {
34                 dis[v]=dis[u]+e[i].w;
35                 if(f[v])ans=min(ans,dis[v]);
36                 if(!in[v]){q[tail++]=v;in[v]=true;if(tail>100000)tail=0;}
37             }
38         }
39     }
40 }
41 int main()
42 {
43     n=read();m=read();k=read();
44     for(int i=1;i<=k;i++)a[i]=read(),f[a[i]]=true;
45     for(int i=1;i<=m;i++)
46     {
47         x=read();y=read();t=read();
48         ins(x,y,t);ins(y,x,t);
49     }
50     for(int i=1;i<=k;i++)spfa(a[i]);
51     printf("%d",ans);
52     return 0;
53 }

View Code

对于第三部分，对于每个点，维护以下信息：离它最近的特殊点及路程，离它次近的特殊点及路程（且需保证两个特殊点不同）。最后再枚举点，用最短路+次短路来更新答案。（看到好多大佬都是枚举边……瑟瑟发抖。

 1 #include<cstdio>
 2 #include<algorithm> 
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int N=100010;
 7 const int inf=0x3f3f3f3f;
 8 int n,m,k,cnt,x,y,w,ans=inf;
 9 int a[10010],first[N],fir[N],sec[N],firn[N],secn[N];
10 struct edge{int to,next,w;}e[N*6];
11 struct node
12 {
13     int d,id;
14     bool operator <(const node& x)const{return x.d<d;}
15 };
16 priority_queue<node>q;
17 int read()
18 {
19     int x=0,f=1;char c=getchar();
20     while(c<'0'||c>'9'){if(x=='-')f=-1;c=getchar();}
21     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
22     return x*f;
23 }
24 void ins(int x,int y,int w)
25 {
26     cnt++;e[cnt].to=y;e[cnt].w=w;
27     e[cnt].next=first[x];first[x]=cnt;
28 }
29 void dijkstra()
30 {
31     memset(fir,0x3f,sizeof(fir));
32     memset(sec,0x3f,sizeof(sec));
33     for(int i=1;i<=k;i++)
34     {
35         fir[a[i]]=0;firn[a[i]]=a[i];
36         q.push((node){0,a[i]});
37     }
38     while(!q.empty())
39     {
40         node x=q.top();q.pop();
41         if(x.d>fir[x.id])continue;
42         int now=x.id;
43         for(int i=first[now];i;i=e[i].next)
44         {
45             int to=e[i].to;
46             if(firn[now]==firn[to])
47             {
48                 if(fir[now]+e[i].w<fir[to])
49                     fir[to]=fir[now]+e[i].w,q.push((node){fir[to],to});
50             }
51             else if(fir[now]+e[i].w<fir[to])
52             {
53                 sec[to]=fir[to];secn[to]=firn[to];
54                 fir[to]=fir[now]+e[i].w;firn[to]=firn[now];
55                 q.push((node){fir[to],to});
56 //                printf("[fir]%d %d %d [n] %d %d
",now,to,fir[to],firn[now],firn[to]);
57             }
58             else if(fir[now]+e[i].w<sec[to])
59             {
60                 sec[to]=fir[now]+e[i].w;
61                 secn[to]=firn[now];
62 //                printf("[sec]%d %d %d [n] %d %d
",now,to,sec[to],secn[now],secn[to]);
63             }
64         }
65     }
66 }
67 int main()
68 {
69     n=read();m=read();k=read();
70     for(int i=1;i<=k;i++)a[i]=read();
71     for(int i=1;i<=m;i++)
72     {
73         x=read();y=read();w=read();
74         ins(x,y,w);ins(y,x,w);
75     }
76     dijkstra();
77     for(int i=1;i<=n;i++)ans=min(ans,fir[i]+sec[i]);
78     printf("%d",ans);
79     return 0;
80 }

View Code