csps模拟83最大异或和简单的括号序列旅行计划题解

题面：https://www.cnblogs.com/Juve/articles/11733280.html

最大异或和：

简单博弈，小Q一定不会输，如果异或和为0，则平局，因为无论小Q如何拿，小T都会拿到和小Q一样

如果异或和不为0，则小Q只要取走二进制下最高位的那个数即可

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 using namespace std;

 const int MAXN=1e5+;

 int t,n,w[MAXN],tot=;

 signed main(){

     scanf("%lld",&t);

     while(t--){

         tot=;

         scanf("%lld",&n);

         for(int i=;i<=n;++i) scanf("%lld",&w[i]),tot^=w[i];

         for(int i=,u,v;i<n;++i) scanf("%lld%lld",&u,&v);

         if(tot!=) puts("Q");

         else puts("D");

     }

     return ;

 }

简单的括号序列：

组合数学，记住不要重复

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 #define re register

 using namespace std;

 const int MAXN=,mod=1e9+;

 int len,ans=,f[MAXN],g[MAXN];

 char s[MAXN];

 int fac[MAXN],inv[MAXN];

 int q_pow(int a,int b,int p){

     int res=;

     while(b){

         if(b&) res=res*a%p;

         a=a*a%p;

         b>>=;

     }

     return res;

 }

 void get_c(int N){

     fac[]=fac[]=inv[]=;

     for(int i=;i<=N;++i) fac[i]=fac[i-]*i%mod;

     inv[N]=q_pow(fac[N],mod-,mod);

     for(int i=N-;i>=;--i) inv[i]=inv[i+]*(i+)%mod;

 }

 int C(int n,int m){

     if(m>n) return ;

     if(m==n) return ;

     return fac[n]*inv[m]%mod*inv[n-m]%mod;

 }

 signed main(){

     scanf("%s",s+);

     len=strlen(s+);

     get_c(len+);

     for(re int i=;i<=len;++i){

         f[i]=f[i-];

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

     }

     for(re int i=len;i>;--i){

         g[i]=g[i+];

         if(s[i]==')') ++g[i];

     }

     for(int i=;i<=len;++i){

         if(s[i]=='(') ans=(ans+C(f[i]+g[i]-,g[i]-))%mod;

     }

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

     return ;

 }

旅行计划：

floyed终于用上了。。。

设f[i][j][k]表示从i到j走k步的最短距离，这很好转移

然后设g[i][j][k]表示从i到j走k×100步的最短距离，用f数组转移

然后把f数组按照k从大到小更新，把f数组转化为i到j走至少k步的最短距离

然后询问时的答案就是min(g[s][i][k/100]+f[i][t][k%100]),$i\in[1,n]$

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define re register

 using namespace std;

 const int inf=0x3f3f3f3f;

 int n,m,mp[][],q,ans,s,t,k,f[][][],g[][][];

 void floyed(){

     for(int i=;i<=n;++i) f[i][i][]=g[i][i][]=;

     for(int k=;k<=;++k){

         for(int i=;i<=n;++i)

             for(int j=;j<=n;++j)

                 for(int p=;p<=n;++p)

                     f[i][j][k]=min(f[i][j][k],f[i][p][k-]+mp[p][j]);

     }

     for(int k=;k<=;++k){

         for(int i=;i<=n;++i)

             for(int j=;j<=n;++j)

                 for(int p=;p<=n;++p)

                     g[i][j][k]=min(g[i][j][k],g[i][p][k-]+f[p][j][]);

     }

     for(int i=;i<=n;++i){

         for(int j=;j<=n;++j)

             for(int k=;k>=;--k)

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

     }

 }

 signed main(){

     scanf("%d%d",&n,&m);

     memset(mp,0x3f,sizeof(mp));

     memset(f,0x3f,sizeof(f));

     memset(g,0x3f,sizeof(g));

     for(re int i=,u,v,w;i<=m;++i){

         scanf("%d%d%d",&u,&v,&w);

         mp[u][v]=min(mp[u][v],w);

     }

     floyed();

     scanf("%d",&q);

     while(q--){

         ans=inf;

         scanf("%d%d%d",&s,&t,&k);

         for(int i=;i<=n;++i)

             ans=min(ans,g[s][i][k/]+f[i][t][k%]);

         if(ans>=inf) ans=-;

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

     }

     return ;

 }