MNNU acm第一场网络赛 vv's kindle 题解

mac2024-11-25  99

题目: vv的大哥bluejoy是一个很nb的人,同时她也非常的善良且乐于助人。今年bluejoy拿到了一等奖学金,她得知vv非常穷困潦倒,于是决定给她的好朋友vv买一个全新的kindle,但bluejoy是一个热爱打代码的girl,于是她想考考vv,如果vv能通过她的考验,她就奖励vv一个kindle,如果不能,她就会无情的用她所有的奖学金去买滑板,一毛钱都不留给vv!

vv非常想要这个kindle,你能帮她拿到这个kindle吗!真是太感谢你了!

bluejoy的考验是:她的奖学金有n元,kindle需要m元,是否有可能通过数次删去n中的一位(次数可为0),使得n=m?如果可以,输出删除的次数,如果不可以,则输出impossible!

例如:

1.n=13,m=3,则删除n中的第一位的数字1,此时答案为1。

2.n=2342,m=32,则删除n中的第一位2与第三位4,此时答案为2。

3.n=222,m=32;则不可能删除n中的任何一位或几位使m=n,此时答案为Impossible。

Input: 输入数据包含多组测试实例,输入的第一行包含两个正整数n,m(1<=n<=1018)(1≤m≤1018)

Output: 对于每组数据,如果可以删除,则输出删除的次数,否则输出“Impossible”。

思路: 首先明确一点,答案只会有两个,一个是impossible,一个是n的长度-m的长度。 先用字符数组存n,m,循环读入

char a[20],b[20]; while(~scanf("%s%s",a,b)){

接下来我们定义一个head变量,用来指向b数组的下标(不懂为什么要定义head的先往下看)

int head=0;

我们先举个例子: N=12365478 M=158

i01234567a[i]12365478b[i]158

我们开始进行匹配查询: ①查a[0]和b[0]是否匹配?a[0]=1 , b[head]=b[0]=1 可知 a[0]=b[head],匹配!head++;

②查a[1]和b[1]是否匹配?(为什么不查a[1]和b[0]是否匹配?因为head=1,这说明b[0]已经被匹配过了,head指向的是我当前需要匹配的字符.)a[1]=2 , b[head]=b[1]=5, a[1]!=a[head],不匹配!

③查a[2]和b[1]是否匹配?(同上,b[1]都没匹配完你还想匹配个啥?) a[2]=3 , b[1]=5,不匹配!

④查a[3]和b[1]是否匹配?a[3]=6 , b[1]=5,不匹配!

⑤查a[4]和b[1]是否匹配?a[4]=5,b[1]=5,匹配!head++.

⑥查a[5]和b[2]是否匹配?(看上面哦,b[1]匹配完了,要匹配b[2]了,所以此时head=2) … 一直匹配到最后一位 a[7]=8 , b[3]=8,匹配!head++,此时head=3;

好啦已经全部匹配完了! 那么要怎么看b是否全部成功匹配呢? 代码如下:

if(head==strlen(b)) printf("%d",strlen(a)-head); else printf("Impossible");

为什么是这样的呢? 因为:一旦b中的数全部匹配完了,那么head一定走到了最后一个数的后面一个位置。 全部代码如下:

char a[20],b[20]; while(~scanf("%s%s",a,b)){ int head=0; for(int i=0;i<strlen(a);i++){ if(a[i]==b[head]){ head++; } } if(head==strlen(b)) printf("%d",strlen(a)-head); else printf("Impossible");
最新回复(0)