首页 > 其他分享 >CF2B The least round way

CF2B The least round way

时间:2024-08-01 19:28:54浏览次数:14  
标签:f2 f5 int back else -- way CF2B round

设 \(f_{i, j}\) 表示走到点 \((i, j)\) 获得因数 2 的最小数量。

设 \(g_{i, j}\) 表示走到点 \((i, j)\) 获得因数 5 的最小数量。

那么到点 \((i, j)\) 胃部获得的最小 0 的个数为 \(\min(f_{i,j}, g_{i, j})\),因为如果选择数量小的那个因数,另外一个因数的个数一定多于它,就会往后加一个 0,这样就使得 0 的个数最小。

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, a[N][N], y2[N][N], y5[N][N], f2[N][N], f5[N][N];
pair<int, int> lz2[N][N], lz5[N][N];
int num_0_x;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            if (!a[i][j]) {
                num_0_x = i;
            }
            else {
                while (a[i][j] % 2 == 0) {
                    y2[i][j]++;
                    a[i][j] /= 2;
                }
                while (a[i][j] % 5 == 0) {
                    y5[i][j]++;
                    a[i][j] /= 5;
                }
            }
        }
    }
    
    memset(f2, 0x3f, sizeof(f2));
    memset(f5, 0x3f, sizeof(f5));
    f2[0][1] = f5[0][1] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (f2[i - 1][j] < f2[i][j - 1]) {
                f2[i][j] = f2[i - 1][j] + y2[i][j];
                lz2[i][j] = {i - 1, j};
            }
            else {
                f2[i][j] = f2[i][j - 1] + y2[i][j];
                lz2[i][j] = {i, j - 1};
            }
            if (f5[i - 1][j] < f5[i][j - 1]) {
                f5[i][j] = f5[i - 1][j] + y5[i][j];
                lz5[i][j] = {i - 1, j};
            }
            else {
                f5[i][j] = f5[i][j - 1] + y5[i][j];
                lz5[i][j] = {i, j - 1};
            }
        }
    }
    int ans = min(f2[n][n], f5[n][n]);
    string s;
    if (ans == f2[n][n]) {
        int x = n, y = n;
        while (x >= 1 && y >= 1) {
            if (lz2[x][y].first == x - 1) {
                x--;
                s.push_back('D');
            }
            else {
                y--;
                s.push_back('R');
            }
        }
    }
    else {
        int x = n, y = n;
        while (x >= 1 && y >= 1) {
            if (lz5[x][y].first == x - 1) {
                x--;
                s.push_back('D');
            }
            else {
                y--;
                s.push_back('R');
            }
        }
    }
    s.pop_back();
    reverse(s.begin(), s.end());
    if (num_0_x && ans > 1) {
        cout << "1\n";
        for (int i = 2; i <= num_0_x; i++) cout << "D";
        for (int i = 2; i <= n; i++) cout << "R";
        for (int i = num_0_x + 1; i <= n; i++) cout << "D";
    }
    else {
        cout << ans << '\n';
        cout << s << '\n';
    }
    return 0;
}

标签:f2,f5,int,back,else,--,way,CF2B,round
From: https://www.cnblogs.com/Yuan-Jiawei/p/18337321

相关文章

  • Educational Codeforces Round 168 (Rated for Div. 2) 赛后总结
    比赛链接赛时提交情况:CF1997A.StrongPassword赛时思路首先看到题目可以想到的是,我们要加入的这个字符不能与其相邻字符相同,所以我没有多想就写出了第一份代码:if(s[0]=='a')cout<<'b';elsecout<<'a';cout<<s<<endl;交上之后喜提WA1。于是冷静了一会儿仔细观察了一......
  • N-way K-shot Few shot learning
    首先需要明确的是少样本领域的数据划分和大规模监督学习方法的数据划分不一样。在大规模监督学习方法中,训练集和测试集是混合后按比例随机切分,训练集和测试集的数据分布一致。以分类问题为例,切分后训练集中的类别和测试集中的类别相同,区别是样本数量不同。但是,在少样本领域,训练......
  • spring整合Sa-token+gateway实现微信无业务关联登录
    1、RBAC是什么?Role-BasedAccessControl,中文意思是:基于角色(Role)的访问控制。这是一种广泛应用于计算机系统和网络安全领域的访问控制模型。简单来说,就是通过将权限分配给➡角色,再将角色分配给➡用户,来实现对系统资源的访问控制。一个用户拥有若干角色,每一个角色拥有若干权限。这......
  • 洛谷题单指南-前缀和差分与离散化-P2882 [USACO07MAR] Face The Right Way G
    原题链接:https://www.luogu.com.cn/problem/P2882题意解读:一个有F、B组成的序列,每次可以翻转k个连续子序列,翻转:F->B,B->F,计算最少翻转多少次可以将序列都变成F,并求相应的k。解题思路:为方便处理,设F为1,B为01、朴素做法枚举k:1~n  枚举序列,一旦遇到0,就将连续k个字符翻转,如果可......
  • CF Pinely Round 4
    https://codeforces.com/contest/1991\(-122=2019\)D\(1,3,4,6\)构成团,所以答案下界为\(4\)按模\(4\)染色。同色的二进制后两位相同,异或和有约数\(4\)E判二分图写了booldfs(intu,intx){vis[u]=x;for(intv:e[u])if(vis[v]){......
  • 题解:Pinely Round 4 (Div. 1 + Div. 2) C
    C.AbsoluteZerotimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouaregivenanarray\(a\)of\(n\)integers.Inoneoperation,youwillperformthefollowingtwo-stepmove:Choose......
  • Spring框架 配置Gateway网关/spring cloud gateway 基础入门案例教程
    文章目录目录文章目录安装流程小结概要安装流程技术细节小结概要网关作为微服务集群唯一的对外入口,可以实现很多功能.例如:统一的解决跨域(一个ajax请求origin域名和请求目标url中域名不同,ip不同,域名不同,端口不同,都会引发的问题)问题.统一的身份认证.认证解......
  • Codeforces Round 943 (Div. 3)A~E
    A.Maximize?题目大意:给你一个数x,你需要找到一个数y(1<=y<x),使得gcd(x,y)+y值最大,然后输出这个y思路:看范围暴力即可voidsolve(){inta,b=0,maxx=0,bj=0;cin>>a;for(inti=1;i<a;i++){b=__gcd(a,i);b+=i;if(maxx<b)......
  • Spring Cloud Gateway 实现 gRpc 代理
    SpringCloudGateway在3.1.x版本中增加了针对gRPC的网关代理功能支持,本片文章描述一下如何实现相关支持.本文主要基于SpringCloudGateway的官方文档进行一个实践练习。有兴趣的可以翻看官方文档。由于Grpc是基于HTTP2协议进行传输的,因此SrpingCloudGateway......
  • Educational Codeforces Round 168 (Rated for Div. 2) (4/6)
    比赛链接:https://codeforces.com/contest/1997solve:ABCD开头:终于能上青名了,本来以为还得打个两三场,看来这暑假必须上蓝名了,不过这一场说实话感觉运气成分大一点,先稳住青名,最近感觉有点懒惰了,欠了好几场补题,牛客多校还有好多场qwq,得努力了A.StrongPassword思路:......