Codeforces Round #581 (Div. 2)

A:暴力。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

  

 const int N=;

 int n;

 char s[N];

  

 int main(){

     scanf("%s",s+); n=strlen(s+); bool flag=;

     rep(i,,n) if (s[i]=='') flag=;

     if (s[]==''){ puts(""); return ; }

     if (flag) printf("%d",(n+)/); else printf("%d\n",n/);

     return ;

 }

B:一定是1,2,4,...,2^k。最小和最大分别让1和2^k最多即可。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

  

 int n,l,r;

  

 int main(){

     cin>>n>>l>>r;

     ll s1=n-l+; rep(i,,l-) s1+=1ll<<i;

     ll s2=(1ll<<(r-))*(n-r+); rep(i,,r-) s2+=1ll<<i;

     cout<<s1<<' '<<s2<<endl;

     return ;

 }

C:先floyd求最短路，然后每次找到当前点至多往后多少个点可以保证p走的一直都是最短路，然后走到那个点去。由于p如果某时刻走的不是最短路了，那么之后走的一定也都不是最短路。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

  

 const int N=,M=,inf=1e8;

 char s[N];

 int n,m,tot,f[N][N],p[M],q[M];

  

 int main(){

     scanf("%d",&n);

     rep(i,,n) rep(j,,n) f[i][j]=inf;

     rep(i,,n) f[i][i]=;

     rep(i,,n){

         scanf("%s",s+);

         rep(j,,n) if (s[j]=='') f[i][j]=;

     }

     rep(k,,n) rep(i,,n) rep(j,,n) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

     scanf("%d",&m);

     rep(i,,m) scanf("%d",&p[i]);

     for (int i=,j; i<m; i=j){

         q[++tot]=p[i];

         rep(k,i+,m) if (f[p[i]][p[k]]==k-i) j=k; else break;

     }

     printf("%d\n",tot+);

     rep(i,,tot) printf("%d ",q[i]); printf("%d\n",p[m]);

     return ;

 }

D1/D2:首先0不会变成1，然后考虑1变成0的必要条件并证明它是充分的。1能变成0，当且仅当存在一个以这个位置开头的子序列，满足它是这个位置到n的LIS。于是边倒着DP做LIS边判断每个1是否可以变成0即可。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

  

 const int N=;

 char s[N],s2[N];

 int n,sm,ans[N],f[N][];

  

 int main(){

     scanf("%s",s+); n=strlen(s+);

     rep(i,,n) s2[i]=s[i];

     for (int i=n; i; i--){

         if (s[i]=='') f[i][]=max(f[i+][],f[i+][])+,f[i][]=f[i+][],sm++;

             else f[i][]=f[i+][]+,f[i][]=f[i+][];

         ans[i]=max(f[i][],f[i][])-sm;

     }

     for (int i=n; i; i--) if (ans[i]!=ans[i+]) s2[i]='';

     rep(i,,n) putchar(s2[i]);

     return ;

 }

E:考虑求F[i]表示最大前缀和不小于i的数列个数，最后差分一下即可求出期望。先给结论：F[i]=C(n+m,n-i)。归纳证明，若数列最后一个数是-1，则前n+m-1个数的最大前缀和一定是i，这部分的贡献是C(n+m-1,n-i)。若是1，由于不能保证这个1一定在最大前缀和里，于是前n+m-1个数的最大前缀和仍然是i，这部分的贡献是C(n+m-1,n-i-1)。于是F[i]=C(n+m-1,n-i)+C(n+m-1,n-i-1)=C(n+m,n-i)。

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

  

 const int N=,mod=;

 int n,m,ans,x,y,C[N][N];

  

 int main(){

     scanf("%d%d",&n,&m); C[][]=;

     rep(i,,n+m){ C[i][]=; rep(j,,i) C[i][j]=(C[i-][j-]+C[i-][j])%mod; }

     for (int i=n; i && i>=n-m; i--) x=(C[n+m][n-i]-y+mod)%mod,ans=(ans+1ll*x*i)%mod,y=(y+x)%mod;

     printf("%d\n",ans);

     return ;

 }

巴特西

Codeforces Round #581 (Div. 2)

最新文章

热门文章