测训815省Ca1-方程整数解20省3-1- 数青蛙，20省3-2- 互质，15校4-7对数字，15省Ca7-手链样式，全排列去重,15国2-完美正方形dfs剪枝

妖狐艹你老母 2022-11-09 14:24 6阅读 0赞

### 15省Ca1-方程整数解 ###

[题目link][link].  
方程: a^2 + b^2 + c^2 = 1000  
　　 a^2 + b^2 + c^2 = 1000a  
2  
\+b  
2  
\+c  
2  
=1000  
　　这个方程有正整数解吗？有：a,b,c=6,8,30 就是一组解。  
　　你能算出另一组合适的解吗？  
　注意是另一组解

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
           int i,j,k;
        for(i=0;i<34;i++){
        
            for(j=i;j<34;j++){
        
                if(i*i+j*j>1000) break;
                for(k=j;k<34;k++){
        
                    int sum=i*i+j*j+k*k;
                    if(sum>1000) break;
                    if(sum==1000) printf("%d %d %d\n",i,j,k);
                }
            }
        }
    
        return 0;
    }

### 20省3-1- 数青蛙 ###

[link][link 1].

算出来的

### 20省3-2- 互质 ###

[link][link 2].  
【注意】1和其他数也是互质，比如1和6互质

#include <bits/stdc++.h>
    
    using namespace std;
    int main(){
        
         int i,sum=0;//1018
        for(i=1;i<2020;i++){
        //1和1018是互质数
            if(i%2==0||i%509==0) continue;
            else {
        sum++;
            printf("%d\n",i);}
        }
        printf("中暑%d\n",sum);//1008
        return 0;
    }

### 15校4-7对数字 ###

[link][link 3].  
【思路】  
问题中要求以74开头,那么可以建立一个数组a,数组中的0代表该位置还没确定数字：

int a[] = {
         0, 7, 4, 0, 0, 0, 0, 4, 0, 7, 0, 0, 0, 0, 0 };

答案要求是14位数,且前两位和第7,9位均已有值。  
从第三位开始,判断该位是否为0,如果为0则说明该位还没有值,则选择1~9以内除了4,7的其它数进行赋值,要注意的是不只是第三位,3+index+1位也要赋值,这是题目所要求的。就这样到下一位,进行同样的操作,在对某位置赋值的时候,如果出现(该位置+要插入的数字+1)大于14等情况,则进行回退,这是典型的回溯法。

#include <stdio.h>
    int a[] = {
         0, 7, 4, 0, 0, 0, 0, 4, 0, 7, 0, 0, 0, 0, 0 };
    void getResult(int index) {
        
    	if (index == 4) {
        //跳过数字4
    		index++;
    	}
    	if (index >= 7) {
        //此时说明1-7数字都被取完,输出答案即可
    		for (int i = 1; i < 15; i++) {
        
    			printf("%d",a[i]);
    		}
    	}
    	//i--->位数
    	for (int i = 3; i < 14; i++) {
        
    		if ((i + index + 1) <= 14 && a[i] == 0 && a[i + index + 1] == 0) {
        
    			a[i] = a[i + index + 1] = index;
    			getResult(index + 1);
    			       //执行到这一步说明此时的数字index不适合于位置i,撤回赋值
    			a[i] = a[i + index + 1] = 0;
    		}
    	}
    }
    int main () {
        
    	getResult(1);//从数字1开始
    	return 0;
    }

### 15省Ca7-手链样式，全排列去重 ###

[link][link 4].

if((*it).find(str, 0) != string::npos)是什么意思

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70]  
【思路】  
【识记】vector v; 用于存储结果，string str=“aaabbbbccccc”; 将str加入到什么地方便于后面去重，vector ::iterator i;用于遍历string  
这个题是全排列加特殊去重

#include<bits/stdc++.h>
    using namespace std;
    vector <string> v;
    int sum=0;
    int main(){
        
        string S="aaabbbbccccc";
        vector<string> v1;
        do{
        
    
         //vector中有该S，则跳过这个S
         //排出重复，如果队列中存在旋转，翻转则跳过
         int  i;
         for(i=0;i<v1.size();i++){
        
            if(v1[i].find(S)!=string :: npos){
        break;}
         }
         //s不可用的情况,也就是前面的循环提前退出了
         if(i!=v1.size()) continue;
         string S2=S+S;
         v1.push_back(S2);//将S旋转放入vector中
         reverse(S2.begin(),S2.end());//翻转
         v1.push_back(S2);//将S翻转放入vector中
         sum++;
        }while( next_permutation(S.begin(),S.end()));
        cout<<sum;
    return 0;}

#include<bits/stdc++.h>
    using namespace std;
    int sum=0;
    int main(){
        
        string str="aaabbbbccccc";
        do{
        
          vector <string>::iterator i;
          for(i=v.begin();i!=v.end();i++){
        
            if((*i).find(str,0)!=string :: npos) {
        
               break;
            }
          }
          if(i!=v.end()) continue;
          string str2=str+str;
          v.push_back(str2);
          reverse(str2.begin(),str2.end());
          v.push_back(str2);
          sum++;
        }while( next_permutation(str.begin(),str.end()));
        cout<<sum;
    return 0;}

### 15国2-完美正方形 ###

[link][link 5].  
由题可知要求的正方形的边长是47+46+61=154

把所给正方形看作154\*154的格点正方形，在每个格点依次尝试填入所给的数字(dfs)，如上图转换成格点正方形后：\[0,0\]到\[59,59\]的格点填入数字60,\[60,0\]到\[109,49\]的格点填入数字50…  
【重点】dfs

#include<bits/stdc++.h>
    using namespace std;
    
    int a[19]={
        2,5,9,11,16,17,19,21,22,24,26,30,31,33,35,36,41,50,52};
    int mp[154][154];
    int book[100];
    
    void fill(int x,int y,int n,int num)//填数操作,在相应的格子区间里填入num
    {
        
    	for(int i=x;i<x+n;i++)
    	{
        
    		for(int j=y;j<y+n;j++)
    		{
        
    			mp[i][j]=num;
    		}
    	}
    }
    
    int solve()//是否已经填完
    {
        
    	for(int i=0;i<154;i++)
    	{
        
    		for(int j=0;j<154;j++)
    		{
        
    			if(mp[i][j]==0) return 0;
    		}
    	}
    	return 1;
    }
    
    int judge(int x,int y,int n)//判断当前数字能不能填进去
    {
        
    	if(x+n>154||y+n>154) return 0;
    	for(int i=x;i<x+n;i++)
    	{
        
    		for(int j=y;j<y+n;j++)
    		{
        
    			if(mp[i][j]) return 0;
    		}
    	}
    	return 1;
    }
    
    int dfs(int x,int y)
    {
        
    	if(solve()) return 1;
    	else
    	{
        
    		int flag=0;
    		for(int i=0;i<154;i++)//找到能填数字的位置
    		{
        
    			for(int j=0;j<154;j++)
    			{
        
    				if(mp[i][j]==0)
    				{
        
    					x=i;
    					y=j;
    					flag=1;
    					break;
    				}
    			}
    			if(flag) break;
    		}
    
    		for(int i=0;i<19;i++)
    		{
        
    			if(judge(x,y,a[i]))
    			{
        
    				if(book[i]==0)
    				{
        
    					fill(x,y,a[i],a[i]);
    					book[i]=1;
    					if(dfs(x,y+a[i])) return 1;//在(x,y)填好的基础上继续填下一个数字
    					fill(x,y,a[i],0);//取消标记,将填的数字清零
    					book[i]=0;//取消标记
    				}
    			}
    			else break;
    		}
    	}
    	return 0;
    }
    
    int main()
    {
        
    	memset(mp,0,sizeof(mp));
    	memset(book,0,sizeof(book));
    	fill(0,0,47,47);//初始填入的数字
    	fill(0,47,46,46);
    	fill(0,93,61,61);
    	dfs(0,0);
    	int ans=0;
    	for(int i=0;i<154;i++)//找最后一行不同的数字即是答案
    	{
        
    		if(mp[153][i]!=ans)
    		{
        
    			printf("%d ",mp[153][i]);
    			ans=mp[153][i];
    		}
    	}
    	return 0;
    }

[link]: https://vijos.org/d/gadflycq/contest/604b0975f41362fb2c97c3b7/5ab52dfed3d8a137122433bb
[link 1]: https://vijos.org/d/gadflycq/contest/604b0975f41362fb2c97c3b7/1054
[link 2]: https://vijos.org/d/gadflycq/contest/604b0975f41362fb2c97c3b7/1055
[link 3]: https://vijos.org/d/gadflycq/contest/604b0975f41362fb2c97c3b7/5a795a8fd3d8a103be7e2a02
[link 4]: https://vijos.org/d/gadflycq/contest/605471a9f41362fb2c97cc26/1057
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1OTc0Mw_size_16_color_FFFFFF_t_70]: /images/20221023/00253e17be8d4d87a7ca2fc34c60e6e1.png
[link 5]: https://vijos.org/d/gadflycq/contest/605471a9f41362fb2c97cc26/5a685140d3d8a103be7e0303