【GDOI2018 D1T2】【51nod1357】密码锁

Source and Judge

GDOI2018 D1T2(模数不固定)
51nod1357

Problem

【Description】
有一个密码锁,其有N位,每一位可以是一个0~9的数字,开启密码锁需要将锁上每一位数字转到解锁密码一致。这个类似你旅行用的行李箱上的密码锁,密码锁的每一位其实是一个圆形转盘,上面依次标了0,1,…9,对每一位来说可以正向或者逆向拨动,正向拨动时原有数字x会变成新的数字(x+1 mod 10),例如1->2,2->3,9->0;同理逆向拨动变为(x-1 mod 10)即9->8,5->4,0->9。定义对密码锁的一次操作:选择一个连续的区间[L,R],可以只包含一位即L==R,将这个区间的所有数字正向拨动或逆向拨动一次,注意要么全部正着拨,要么全逆着。例如:12397正向后变成23408,逆向后变成01286。给出密码锁初始和解锁需要的终止状态,问最少多少次操作能解锁。
【Input】
多组测试数据,第一行一个整数T,表示测试数据数量
每组测试数据有相同的结构构成:
每组数据有两行构成,第一行是密码锁的初始状态S,第二行是解锁的终止状态E
【Output】
每组数据一行输出,即最少需要的操作数。
【Limited conditions】
1<=len(S)=len(E)<=2500,且都由0~9构成
【Sample input】
10
607
607
1234
4567
3789656
5159478
92778243285457494629783933521676060327742645358293
73909905995243281321698807518024164499178500552788
4412418167031360587403146933365311425441936961077
8733406822463469353946356056711090437786504862201
123
112
1
7
020
909
4423232218340
6290421476245
0183785
0000000
【Sample output】
0
3
10
66
28
1
4
2
18
11
【Sample explanation】

Record

2h
这个是比赛的题目,但当时没有做出来
然后因为讲课的时候不是那么明确,想做一做(就是想报仇的心态)
在知乎上找到了类似的题目,不过都没人做
wa了很多次……
所以数据特别多,是我买的几组数据

Analysis

请先思考后再展开

首先,gdoi的题目是最后要到0,而这里是指定的
如何处理这一步呢?
其实很好理解,因为每一个位是相对独立互不影响的,那么可以把目标位对其为0,然后把当前串映射过去(其实就是相减一下),那么现在对正确性没有影响的

但是,这道题目有个很迷惑人的地方,在于有模数
刚才我们搞出来的当前串a是有负数的,但是我们先不管它

现在有+1和-1两种区间操作,那么一个不那么显然的套路就是差分一下(没想到啊555)
那么现在,我们的目标就是,对于得到的差分数组cf,我们要把其中每一个元素变成m的倍数(包括0)
而这两个区间操作,现在就变成了对一个数+1,一个数-1

不难发现这道题是一定有解的,因为你可以一个个拧过去
我们要利用这个性质,辅助我们去理解这道题
那一个个拧过去,其实就是这个+1,下一个-1
所以我们的差分数组,长度应该是n+1
而且,我们的+1和-1的个数是要相同的

那么对于每一个差分后的数,它都有一个上下界,因为跨越是没有意义的
那么显然我们可以取个模,然后如果还是负数的话,把它+m后,其实是等效的

现在的问题就在于,如何分配+1和-1呢?
首先明确一个数,只可能增加或减少,而不会重叠,否则答案不会更优(还不理解可以联想一下原问题,对于两个重叠的+1和-1区间,显然可以把中间的去掉,剩下的还是两个)

接下来,我们可以尝试贪心
把差分的数字排个序,然后枚举一个断点(在空隙位置),这个断点左边的,也就是比它小的,全部都是要减小的,右边的都是要增加的
那么线性地扫描一遍,如果左边的花费能否等于右边的花费,显然这个时候是最优的

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
//*******************全局常量*******************
const int MAXN=3100;
const int m=10;
//*******************全局定义*******************
char st[MAXN],ed[MAXN];
//*******************实现*******************
int myabs(int x) {return (x>0)?x:-x;}
int mymin(int x,int y) {return x<y?x:y;}
//*******************主函数*******************
struct Nod
{
int cf;
int a,b;//下、上
}p[MAXN];
bool cmp(Nod a,Nod b) {return a.cf<b.cf;}
int a[MAXN];
int l[MAXN],r[MAXN];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%s%s",st+1,ed+1);
int n=strlen(st+1);
for(int i=1;i<=n+1;i++)
{
a[i]=st[i]-ed[i];
p[i].cf=(a[i]-a[i-1])%m;
if(p[i].cf<0) p[i].cf+=m;//对应位置
p[i].a=p[i].cf,p[i].b=10-p[i].cf;
}
sort(p+1,p+n+1+1,cmp);
l[0]=0;for(int i=1;i<=n+1;i++) l[i]=l[i-1]+p[i].a;
r[n+2]=0;for(int i=n+1;i>=1;i--) r[i]=r[i+1]+p[i].b;
int ans=-1;
for(int i=1;i<=n+2;i++) if(l[i-1]==r[i]) {ans=l[i-1];break;}
printf("%d\n",ans);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-05/密码锁.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%