URAL--1007 codewords-蒲公英云

URAL--1007 codewords

三种信息传递过程中可能出错的方式，让你恢复原来正确的信息。

我用的是分类暴搜，用字符串模拟的，这里还是是可行的，不过debug快坑死了o(╯□╰)o……

后面还有一个别人的用string写的，感觉挺不错的……

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
int n;
int main()
{
    scanf("%d",&n);
    char word[1005],tmp[1005];
    memset(word,0,sizeof(word));
    while (scanf("%s",word)!=EOF)
    {
        int len=strlen(word),i,sum=0,j;
        if (len==n)
        {
            for (i=len-1;i>=0;i--)
                if (word[i]=='1')sum+=len-i;
            if (sum%(n+1)==0)printf("%s\n",word);
            else
            {
                for (j=len-1;j>=0;j--)
                    if (word[j]=='1')
                    {
                        sum=0;
                        word[j]='0';
                        for (i=len-1;i>=0;i--)
                            if (word[i]=='1')sum+=len-i;
                        if (sum%(n+1)==0)
                        {
                            printf("%s\n",word);
                            break;
                        }
                        else word[j]='1';
                    }
            }
        }
        else if (len<n)
        {
            for (j=n-1;j>=0;j--)
            {
                memset(tmp,0,sizeof(tmp));
                for (i=0;i<j;i++)
                    tmp[i]=word[i];
                for (i=j;i<len;i++)
                    tmp[i+1]=word[i];
                tmp[j]='1';
                sum=0;
                for (i=len;i>=0;i--)
                    if (tmp[i]=='1')sum+=n-i;
                if (sum%(n+1)==0)
                {
                    printf("%s\n",tmp);
                    break;
                }
                tmp[j]='0';
                sum=0;
                for (i=len;i>=0;i--)
                    if (tmp[i]=='1')sum+=n-i;
                if (sum%(n+1)==0)
                {
                    printf("%s\n",tmp);
                    break;
                }
            }
        }
        else
        {
            for (j=len-1;j>=0;j--)
            {
                for (i=0;i<j;i++)
                    tmp[i]=word[i];
                for (i=j;i<len;i++)
                    tmp[i]=word[i+1];
                sum=0;
                for (i=len-1;i>=0;i--)
                    if (tmp[i]=='1')sum+=n-i;
                if (sum%(n+1)==0)
                {
                    printf("%s\n",tmp);
                    break;
                }
            }
        }
        memset(word,0,sizeof(word));
    }
    return 0;
}

测试数据：

input	output
4 0000 011 1011 11011	0000 0110 1001 1111

看到了别人用string写的，感觉代码短小精悍就拿了过来，不过时间稍长，但不会超时…

#include <iostream>
#include <string>
using namespace std;
int n;
bool count(string &s)
{
    int k = 0;
    for(int i = 1 ; i <= n ; i++)
        if(s[i - 1] == '1') k += i;
    return k % (n + 1) == 0;
}
void work()
{
    string s;
    cin >> n;
    while(cin >> s)
    {
        if(s.length() == n && count(s)) goto end;
        if(s.length() == n)
        for(int i = 1 ; i <= n ; i++)
        if(s[i - 1] == '1')
        {
            s[i - 1] = '0';
            if(count(s)) goto end;
            s[i - 1] = '1';
        }
        if(s.length() < n)
        for(int i = 1 ; i <= n ; i++)
        {
            s.insert(i - 1, "1");
            if(count(s)) goto end;
            s.erase(i - 1, 1);
            s.insert(i - 1, "0");
            if(count(s)) goto end;
            s.erase(i - 1, 1);
        }
        if(s.length() > n)
        for(int i = 1 ; i <= n ; i++)
        {
            string tmp = s.substr(i - 1, 1);
            s.erase(i - 1, 1);
            if(count(s)) goto end;
            s.insert(i - 1, tmp);
        }
        end:
            cout << s << endl;
    }
}
int main()
{
    work();
    return 0;
}