CF2B The least round way 题解
alt

都是泪呀。。。↑

题目传送门

题意(直接复制了QWQ)

题目描述

给定由非负整数组成的$n \times n$的正方形矩阵,你需要寻找一条路径:
以左上角为起点,
每次只能向右或向下走,
以右下角为终点 并且,如果我们把沿路遇到的数进行相乘,积应当是最小“round”,换句话说,应当以最小数目的0的结尾.

输入格式

第一行包含一个整数 $(2 \leq n \leq 1000)$,$n$为矩阵的规模,接下来的$n$行包含矩阵的元素(不超过$10^9$的非负整数).

输出格式

第一行应包含最小尾0的个数,第二行打印出相应的路径(译注:D为下,R为右)

思路

楼下其实说得蛮清楚了,我主要就是说一下坑。。。
构成末尾是0的只能是$2^a$与$5^b$相乘,所得的0的个数为$min(a,b)$,所以,只要2、5分别dp一遍,取一下上与左的最小值就好啦。。。最后求路径时递归求一遍就好啦。。。

TLE的小朋友们看这里啦。。。

TLE的小朋友们看这里啦。。。

TLE的小朋友们看这里啦。。。

(重要的事情说三遍)

此题特别会卡时。
比如说一开始预处理每个数是$2^a$与$2^b$时,需要将此数不间断地除下去,为什么呢?因为卡常数。。。也许时我RP的原因吧。。。卡了半天,终于卡过去了。。。

感谢$Seanq$提供hack数据:

3
0 1 1 
1 1 1
1 1 1

现已添加特判,第一个格子必须要走且第一个格子为0,使得结果为0的情况。
感谢$Liuyuzhuo$提供hack数据:

3
1 1 1
1 1 1
1 1 0 

现已添加特判,最后一个格子如果为0,结果为0。
具体详见代码:

代码

(我知道你要看这个)

#include<bits/stdc++.h>
//#define int long long 
using namespace std;//奇丑无比的码风
inline int read(){//cf数据加强,只能加读优了。
    int res=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
int n,a[1010][1010],f[2][1010][1010],dp[2][1010][1010];
int ans,qx,qy;
bool ff;
inline int get2(register int x,register int y){
    if(a[x][y]==0){return 0;} //特判
    register int pt=0;
    while(a[x][y]%2==0) ++pt,a[x][y]/=2; //卡常数
    return pt;
}
inline int get5(register int x,register int y){
    if(a[x][y]==0){return 0;} //特判
    register int pt=0;
    while(a[x][y]%5==0) ++pt,a[x][y]/=5; //卡常数
    return pt;
}
inline void print(register int k,register int x,register int y,register int first){
    if(x==1&&y==1) ;
    else if(x==1) print(k,x,y-1,0);
    else if(y==1) print(k,x-1,y,1);
    else if(dp[k][x][y]==dp[k][x-1][y]+f[k][x][y]) print(k,x-1,y,1);
    else print(k,x,y-1,0);
    if(first==6666) return ;
    putchar(first==0?'R':'D'); //一开始在n,n点时不需要输出
    return ;
}
signed main(){
    n=read();
    ff=0;qx=0;qy=0;
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++){
            a[i][j]=read();
            if(a[i][j]==0){
                qx=i;qy=j;
                ff=1;
            } 
        }
    }
    if(a[1][1]==0||a[n][n]==0){
        puts("1");
        for(int i=1;i<=n-1;i++) putchar('D');
        for(int i=1;i<=n-1;i++) putchar('R');
        return 0;
    } 
    for(register int i=1;i<=n;i++){
        for(register int j=1;j<=n;j++){
            f[0][i][j]=get2(i,j);
            f[1][i][j]=get5(i,j);
        }
    }
    memset(dp,63,sizeof(dp));
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n;j++){
            dp[0][i][j]=min(dp[0][i][j],dp[0][i-1][j]);
            dp[0][i][j]=min(dp[0][i][j],dp[0][i][j-1]);//从左格子与上格子中取最小值
            if(i==1&&j==1) dp[0][i][j]=0;
            dp[0][i][j]+=f[0][i][j];
        }
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n;j++){
            dp[1][i][j]=min(dp[1][i][j],dp[1][i-1][j]);
            dp[1][i][j]=min(dp[1][i][j],dp[1][i][j-1]);//从左格子与上格子中取最小值
            if(i==1&&j==1) dp[1][i][j]=0;
            dp[1][i][j]+=f[1][i][j];
        }
    ans=min(dp[0][n][n],dp[1][n][n]);//初步ans
    if(ans>1&&ff==1){ //特判有0的情况,如果有0,那么答案只有0或1.
        putchar('1');
        putchar('\n');
        for(register int i=1;i<qx;i++) putchar('D');
        for(register int i=1;i<qy;i++) putchar('R');
        for(register int i=qx;i<n;i++) putchar('D');
        for(register int i=qy;i<n;i++) putchar('R');
        putchar('\n');
    }else{
        cout<<ans;
        putchar('\n');
        if(dp[0][n][n]<dp[1][n][n]) print(0,n,n,6666); //分2、5讨论
        else print(1,n,n,6666);
        putchar('\n');
    }
    return 0;
}
/*
3
0 1 1 
1 1 1
1 1 1
*/ 
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇