• 2022/8/5 拓扑排序+dp

    活动地址：CSDN21天学习挑战赛

    460B - Little Dima and Equation

    直接枚举x是不可行的，但是我们可以直接枚举位数和，位数和最小是0最大是81，所以我们可以全枚举一遍记录下来满足条件的x就可以了

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 2e5+5;
    5. ll a,b,c;
    6. vectorv;
    7. int main(){
    8.     ll siz=0;
    9.     scanf("%lld%lld%lld",&a,&b,&c);
    10.     for(ll i=0;i<=81;i++){
    11.         ll p=pow(i,a);
    12.         ll x=b*p+c,sum=0;
    13.         if(x>0&&x<1e9){
    14.             while(x){sum+=x%10;x/=10;}
    15.             if(sum==i) siz++,v.push_back(b*p+c);
    16.         }
    17.     }
    18.     printf("%lld\n",siz);
    19.     for(int i=0;isize();i++) printf("%lld ",v[i]);
    20.     system("pause");
    21.     return 0;
    22. }

    510C - Fox And Names 拓扑排序

    没看出来竟然是一个拓扑排序，大的字母向小的字母连一条边，然后跑一遍拓扑排序就能得到顺序，如果跑完不够26个字母，说明有冲突不符合条件，另外在加边的时候也要判断如果第i个字符串是第i-1个字符串的前缀时也是不符合条件的

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 2e5+5;
    5. ll n,g[30][30],in[30];
    6. char s[110][110];
    7. vector<char>v;
    8. void add(ll a,ll b){
    9.     a-='a';b-='a';
    10.     if(!g[a][b]){
    11.         g[a][b]=1;
    12.         in[b]++;
    13.     }
    14. }
    15. void bfs(){
    16.     queueq;
    17.     for(int i=0;i<26;i++) 
    18.         if(in[i]==0) q.push(i);
    19.     vectorans;
    20.     while(!q.empty()){
    21.         ll x=q.front();q.pop();
    22.         //cout<
    23.         ans.push_back(x);
    24.         for(int i=0;i<26;i++){
    25.             if(g[x][i]){
    26.                 in[i]--;
    27.                 if(in[i]==0) q.push(i);
    28.             }
    29.         }
    30.     }
    31.     //cout<
    32.     if(ans.size()!=26) printf("Impossible\n");
    33.     else{
    34.         for(int i=0;i<26;i++)
    35.             cout<<(char)(ans[i]+'a');
    36.             printf("\n");
    37.     }
    38. }
    39. int main(){
    40.     scanf("%lld",&n);
    41.     for(char i='a';i<='z';i++) v.push_back(i);
    42.     for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    43.     ll flag=0;
    44.     for(int i=2;i<=n;i++){
    45.         for(int j=1;j<=strlen(s[i-1]+1);j++){
    46.             if(strlen(s[i]+1)printf("Impossible\n");system("pause");return 0;}
    47.             if(s[i-1][j]!=s[i][j]){add(s[i-1][j],s[i][j]);break;}
    48.         }
    49.     }  
    50.     bfs();
    51.     system("pause");
    52.     return 0;
    53. }

    C - Robot in a Hallway

    一共就是两种方法走完全程，要么是蛇形走位，要么是蛇行的过程中突然直走到n再拐弯直走回去，在模拟蛇形走位的过程中不断地和直走比较就可以了，有很多地方取max的原因是a[i][j]会有等待秒数，所以是一个最好情况和最坏情况的比较，当然是要取最坏情况的秒数了

    Educational Codeforces Round 133 (Rated for Div. 2) A - D - 知乎 (zhihu.com)

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const int N = 2e5+5;
    5. ll t,n,a[2][200005];
    6. ll maxv1[2][200005],maxv2[2][200005],v[2][200005];
    7. int main(){
    8.     cin>>t;
    9.     while(t--){
    10.         cin>>n;
    11.     for(int i=0;i<2;i++){
    12.         for(int j=1;j<=n;j++) cin>>a[i][j],v[i][j]=0;
    13.         maxv1[i][n+1]=maxv2[i][n+1]=-1e18;
    14.         for(int j=n;j;j--){
    15.             maxv1[i][j]=max(maxv1[i][j+1],a[i][j]+j);
    16.             maxv2[i][j]=max(maxv2[i][j+1],a[i][j]-j);
    17.         }
    18.     }
    19.     ll x=0,y=1;
    20.     v[0][1]=1;
    21.     ll ans=1e18,t=0;
    22.     while(1){
    23.         if(!v[x^1][y]){
    24.             ll tmp=max(t+n-y,n+1+maxv2[x][y+1]);
    25.             //一直直走走到n再上/下去从n走到x^1,y和直接上/下去中取一个最大值
    26.             ans=min(ans,max(tmp+n-y+1,maxv1[x^1][y]-y+1));
    27.             x^=1;
    28.         }
    29.         else y++;
    30.         if(y>n) break;
    31.         v[x][y]=1;
    32.         t=max(t+1,a[x][y]+1);
    33.     }
    34.     cout<<min(ans,t)<
    35.     }
    36.     system("pause");
    37.     return 0;
    38. }

    D - Chip Move dp

    dp[j][i]表示走j步可以到达i的方案数，其实k要是从1开始的话他顶多能跳根号2*n步，如图

    dp方程为

     

    dp[t][i+k+j]=(dp[t][i+k+j]+dp[t][i])%mod;

    if(i||j) dp[!t][i+k+j+1]+=(dp[!t][i+k+j+1]+dp[t][i])%mod;

     第一个是可以不变j(t是变成滚动数组了)，i继续向后加一个整数倍；第二个是j+1，也就是k+1，因为一开始只能是走k步，所以i=0，j=0的时候要排除

    Educational Codeforces Round 133 (Rated for Div. 2) A~F - 知乎 (zhihu.com)

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. const ll mod=998244353;
    5. const int N = 2e5+5;
    6. ll n,k,dp[2][200005],ans[200005];
    7. int main(){
    8.     scanf("%lld%lld",&n,&k);
    9.     ll sq=sqrt(2*n),t=1;
    10.     dp[0][0]=1;
    11.     for(int j=0;j
    12.         t=!t;
    13.         for(int i=0;i<=n;i++) dp[!t][i]=0;
    14.         for(int i=0;i+k+j<=n;i++){
    15.             dp[t][i+k+j]=(dp[t][i+k+j]+dp[t][i])%mod;
    16.             //if(i+k+j>=n||j+1==sq) break;
    17.             if(i||j) dp[!t][i+k+j+1]+=(dp[!t][i+k+j+1]+dp[t][i])%mod;
    18.         }
    19.         for(int i=0;i<=n;i++) ans[i]=(ans[i]+dp[t][i])%mod;
    20.     }
    21.     for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
    22.     system("pause");
    23.     return 0;
    24. }

    Sitting in Line - HDU 5691 - Virtual Judge (vjudge.net) 状压dp

    f[s][j]表示s的二进制位中是1的表示已经有人坐下了，最右边是第j个人的最大的乘积和，三重循环枚举每个状态，如果第j个人已经被指定了座位，就看看他的座位是否是已经被坐的座位数加1，如果没被指定，就要看看要坐的座位是否已经有人了，之后再转移方程，在s的集合中填入j，并且最右边的人变成了j，即f[s|(1<

    hdu_5691_Sitting in Line(状压DP)_bin_gege的博客-CSDN博客

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include
    16. //HDU火车头
    17. //#include 
    18. #define __builtin_popcountll __popcnt
    19. #define __builtin_popcountlll __popcnt
    20. #define ll long long
    21. #define lowbit(x) ((x)&(-x))
    22. using namespace std;
    23. const ll mod=998244353;
    24. ll n,t,a[20],p[20],f[100005][20];
    25. int main(){
    26.     scanf("%lld",&t);
    27.     ll cas=0;
    28.     while(t--){
    29.         scanf("%lld",&n);
    30.         for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&p[i]),p[i]++;
    31.         for(int i=0;i<(1<
    32.         for(int j=1;j<=n;j++) f[i][j]=-1e18;
    33.         for(int i=1;i<=n;i++) 
    34.             if(!p[i]||p[i]==1) f[1<<(i-1)][i]=0;
    35.         for(int s=0;s<(1<
    36.         for(int i=1;i<=n;i++){
    37.             for(int j=1;j<=n;j++){
    38.                 if((s>>(j-1))&1) continue;
    39.                 if(i==j||p[j]&&p[j]!=__builtin_popcount(s)+1) continue;
    40.                 f[s|(1<<(j-1))][j]=max(f[s|(1<<(j-1))][j],f[s][i]+a[i]*a[j]);
    41.             }
    42.         }
    43.         ll ans=-1e18;
    44.         for(int i=1;i<=n;i++) ans=max(ans,f[(1<-1][i]);
    45.         printf("Case #%lld:\n%lld\n",++cas,ans);
    46.     }
    47.     system("pause");
    48.     return 0;
    49. }

    Victor and World - HDU 5418 - Virtual Judge (vjudge.net)状压dp

    这个题和上一个思路差不多，floyd处理出最短路后再用状态压缩求出跑完每个点所需要的最短路程然后枚举最小值时不要忘了加上最后的点到1的距离就行

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include
    16. //HDU火车头
    17. //#include 
    18. #define ll long long
    19. #define lowbit(x) ((x)&(-x))
    20. using namespace std;
    21. const ll mod=998244353;
    22. ll t,n,m,g[20][20],f[100005][20];
    23. void floyd(){
    24.     for(int k=1;k<=n;k++)
    25.     for(int i=1;i<=n;i++)
    26.     if(g[i][k]!=1e18)
    27.     for(int j=1;j<=n;j++)
    28.     g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    29. }
    30. int main(){
    31.     scanf("%lld",&t);
    32.     while(t--){
    33.         scanf("%lld%lld",&n,&m);
    34.         for(int i=1;i<=n;i++)
    35.         for(int j=1;j<=n;j++)
    36.             if(i==j) g[i][j]=0;
    37.             else g[i][j]=1e18;
    38.         for(int i=1;i<=m;i++){
    39.             ll u,v,w;
    40.             scanf("%lld%lld%lld",&u,&v,&w);
    41.             g[u][v]=min(g[u][v],w);
    42.             g[v][u]=min(g[v][u],w);
    43.         }
    44.         floyd();
    45.         for(int i=0;i<(1<
    46.         for(int j=1;j<=n;j++) f[i][j]=1e18;
    47.         f[0][0]=f[1][1]=0;
    48.         for(int s=0;s<(1<
    49.         for(int i=1;i<=n;i++)
    50.         for(int j=1;j<=n;j++){
    51.             if(i==j||(s>>(j-1))&1) continue;
    52.             f[s|(1<<(j-1))][j]=min(f[s|(1<<(j-1))][j],f[s][i]+g[i][j]);
    53.            // cout<
    54.         }
    55.         ll ans=1e18;
    56.         for(int i=1;i<=n;i++){
    57.             ans=min(ans,f[(1<-1][i]+g[i][1]);
    58.             //cout<
    59.         }
    60.         printf("%lld\n",ans);
    61.     }
    62.     system("pause");
    63.     return 0;
    64. }

  • 相关阅读:
    Hashmap经典高频问题,让面试成为你的主场
    二分模板代码
    Java项目—停车场管理系统（附源码+资料课件）
    Java面试连击发问：Http是短连接还是长连接该怎么回答？
    java/golang/csharp/c++/python生成pb文件的方法
    第1章 Spring Boot到底是什么？
    金仓数据库KingbaseES运维工具参考手册（6. 预防删除工具指南）
    Java1.8+ JUC包的ConcurrentHashMap源码分析
    数字工厂中的SCADA（数据采集与监控系统）
    Rust中的并发性：Sync 和 Send Traits
  • 原文地址：https://blog.csdn.net/weixin_52621204/article/details/126172105