题解 P1532 【卡布列克圆舞曲　】

· · 题解

P1532 卡布列克圆舞曲 解题报告

蒟蒻的第三篇题解~

反比例函数的思路与大多数人不同，主要原因是在本人刚学OI时懒得打数位分离，每次遇到数位重排的题就直接上字符串。本题的思路正是由此而生。

虽然反比例函数是C++选手，但题解中使用的是C风格字符串，某些C++选手可能阅读起来有轻微困难，因此讲解较详细，请耐心阅读。

算法：

没什么好说的，就是大模拟，属于比较复杂的那种。

思路：

输入、数位重排使用C风格字符串（暴力sort），计算两数之差时将其转换为long long型整数（注意一定是longlong，否则见祖宗只有10分），将每次计算出的数存储在a数组中，发现a数组有两相同数时输出。

技术：

将C字符串转换为（长）整形可用atoi()函数，该函数会自动将遇到的连续数字转换为整型数，遇到非数字字符则停止。

atoi()函数返回的是转换后的数，因此你应该这样写：

char s[]="998244353";//不用管这是什么数字
int n;
n=atoi(s);

事实证明atoi()函数有时会出现玄学错误（比如我们在这道题中要用到longlong，由于本人一开始用atoi()一直爆零，改成了sprintf()才好）

对了，刚才提到了sprintf()函数，它的定义如下：

int sprintf(char *string, char *format [,argument,...])

看，多像我们几乎天天用的printf，只是前面多了一个char *string。因此你应该这样写：

char s[]="998244353";
int n;
sprintf(s,"%d",n);

但在这个程序中还涉及数字转字符串，于是你会想：有没有itoa()函数？

答案是：有。但对不起，你没法用，因为那不是标准函数，Linux下不能用。

怎么办？

这时候该请出伟大的sscanf()了！

类比前面的sprintf，sscanf()比起scanf只多前面的一个char *string，它的功能是将一些数据（来自其他变量）输入字符串。你可以这样写：

char s[100];
int n=998244353;
sscanf(s,"%d",&n);//不要漏掉n前的&，就像使用scanf一样！

代码实现

//为了保险，我在做题时几乎将所有的int全改了longlong
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long a[10005],m,n,cnt=0;
bool cmp(char x,char y)
{   return x>y;}
bool inarray(long long c[],long long x)//判断数组中是否有相同数据
{   for(int i=1;i<cnt;i++)
      if(c[i]==x) return true; 
    return false;}
long long ffind(long long c[],long long x)//寻找数组中相同数据的位置
{   for(int i=1;i<cnt;i++)
      if(c[i]==x) return i;
    return -1;}
int main()
{
    char s[100];
    long long i,len;
    memset(a,0,sizeof(a));//以防万一
    while(scanf("%s",&s)!=EOF)
    //由于题面没说多少组，我们应用while输入；同时为了省时间使了用scanf。
    //不能像写cin那样，直接写while(scanf("%s",s))，这样会死循环
    //EOF的意思是end of file，也就是输入结束
    //在本地操作时可以在控制台里输入Ctrl+Z停止输入
    {   a[++cnt]=atoi(s);//这一步就是90分到100分的关键！你输入的数可能就是循环节的一部分！
A:      len=strlen(s);
        sort(s,s+len);//排序，s是最小
        char t[100];
        strcpy(t,s);//把s的值赋给t，t是最小
        sort(s,s+len,cmp);又排了一次，s变成最大
        //m=atoi(s),n=atoi(t);  你也可以这样写，但atoi()有危险，不要随便用于longlong
        sscanf(s,"%lld",&m);sscanf(t,"%lld",&n);//字符串变整型
        m-=n;//减
        char tmp[100];
        sprintf(tmp,"%lld",m);
        if(strlen(tmp)<len) m*=10;
        //这是对类似4333-3444=999的特判，位数不够就补0的一步。所幸数据并没有那么毒瘤，不写也不要紧
        a[++cnt]=m;
        if(inarray(a,m))
        {   for(i=ffind(a,m);i<cnt;i++) cout<<a[i]<<' ';
            cout<<endl;
            memset(a,0,sizeof(a));cnt=0;
            continue;}//找到了，输出，清空，再等输入
        memset(s,0,sizeof(s));
        sprintf(s,"%lld",m);//整数变字符串
        goto A;}//此处我最终还是选择了容易出错的goto，因为简洁；
        //但不建议大量使用goto，会出玄学错误。
    return 0;
}