URAL--1007 codewords

落日映苍穹つ 2022-08-11 00:44 143阅读 0赞

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

我用的是分类暴搜，用字符串模拟的，这里还是是可行的，不过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;
    }

测试数据：

<table style="border-style:solid; border-color:rgb(26,92,200); font-family:Simsun; border-collapse:collapse"> 
 <tbody> 
  <tr> 
   <th style="border-style:solid; border-color:rgb(26,92,200); padding:3px; vertical-align:top; color:rgb(26,92,200)"> input</th> 
   <th style="border-style:solid; border-color:rgb(26,92,200); padding:3px; vertical-align:top; color:rgb(26,92,200)"> output</th> 
  </tr> 
  <tr> 
   <td style="border-style:solid; border-color:rgb(26,92,200); padding:3px; vertical-align:top"> <pre style="margin-top:0px; margin-bottom:0px; font-family:monospace,'monospace for firefox'; font-size:0.81em">4    
0000 
011  
1011 
11011
</pre> </td> 
   <td style="border-style:solid; border-color:rgb(26,92,200); padding:3px; vertical-align:top"> <pre style="margin-top:0px; margin-bottom:0px; font-family:monospace,'monospace for firefox'; font-size:0.81em">0000
0110
1001
1111
</pre> 
    <div> 
     <br> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

看到了别人用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;
    }