第三届西南石油大学程序设计竞赛题解

第三届西南石油大学程序设计竞赛题解 1.孪生素数

就判断素数就行，但是数据范围是1e9所以需要O(√N)的判断

考察点：循环

#include
using namespace std;
typedef long long ll;
bool check(int x){
    if(x<2)return false;
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0)return false;
    }
    return true;
}
int main(){
    int x;
    cin>>x;
    for(int i=x;;i++){
        if(check(i)&&check(i+2)){
            cout<<i<<' '<<i+2;
            break;
        }
    }
    return 0;
}

2.天造地设

考察点：搜索，剪枝

为了考虑降低难度特意把时间放宽，空间开大，数据缩小，原题的话数据是很大的这里的每个笔画数不超过20

我这里说的是我写的版本，不过也有过了的人的解法也很不错不过就是过不了大数据，就n个数，相邻两个数通过加减运算生成第三个数，n个数就会生成n-1个数，搜索出着n-1个数的所有情况(顺便去个重),然后再对这n-1个数重复上述步骤直到剩下一个数判断是否为0，

这是最基础的搜索，肯定会超时或者爆内存，第一个剪枝就是当你剩下两个数的时候不需要在搜索了只需要判断他俩和或者差是否为0就行减少一重搜索，第二个剪枝也是最重要的就是你去搜索的时候比如两个数a,b生成第三个数的时候有a+b,a-b,b+a,b-a这四种情况，大家肯定都能想到a+b相当于就是b+a,可以减少一次搜索，但是既然能想到这个那为什么不去考虑一下a-b是否就相当于是b-a呢，有一个很简单的理解但是怕你们不理解，就比如三个数x,a,b,x和a生成x-a,a和b生成b-a,那这三个数就生成了两个数x-a,b-a,在下一轮这两个数继续生成比如(x-a)-(b-a)就相当于是(x-a)+(a-b),而(x-a)+(b-a)就相当于是(x-a)-(a-b),如果是(b-a)-(x-a)那么在下一轮同样可以这样 *** 作,意思就是 a和b生成的b-a其实就相当于是下一轮的-(a-b)，而在最后两个数判断的时候我们是通过这俩数的和与差判断是否为0，也就是说两个数生成第三个数只需要生成a+b和a-b两个就行，不影响他最后是否为0。

那个简单的理解就是，所有后面的数减去前面的数都可以转换成 -(前面的数减去后面的数)，然而这个需要这个数不是第一个数才行，那假如是第二个数减第一个数该怎么办呢，其实就给他整体加个负号那就变成了第一个数减去第二个数，而后面的就算加了负号也不影响因为可以通过上面说的转换出来,并且-0=0(数值上来说)

#include
using namespace std;
int vis[25],n,cou,m;
int a[25];
vector < vector<int> > ans;
vector <int> res;
map < vector<int> , int > ma;
set <vector<int> > se; 
void dfs(int x){
    if(x>=n){
		ans.push_back(res);
        return ;
    }
    for(int i=x;i<n;i++) 
        if(vis[i]){
            vis[i]=false;
            res.push_back(a[i]+a[i+1]);
            dfs(x+1);
            res.pop_back();
            
            res.push_back(a[i]-a[i+1]);
            dfs(x+1);
            res.pop_back();
            vis[i]=true;
        }
    return ;
    
}
int main()
{   
	ios::sync_with_stdio(false);
	memset(vis,true,sizeof(vis));
    cin>>n>>m;
	n+=m;
    vector <int> x;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	x.push_back(a[i]);
	}
	ans.push_back(x);
	int i=0;
    for(i=0;;i++){
    	x=ans[i];
    	n=x.size();
    	if(n==2)break;
		for(int j=1;j<=n;j++){
    		a[j]=x[j-1];
		}
		dfs(1);
	}
    for(;i<ans.size();i++){
    	if(ans[i][0]-ans[i][1]==0||ans[i][0]+ans[i][1]==0){
    		cout<<"Yes";
    		return 0;
		}
	}
	cout<<"No"; 
    return 0;
}

3.简单的A+B

考察点:模拟

这题不是我出的，就一看数据就知道是大数模拟，Python和Java都好写C的话就模拟小学加法运算就行

#include
#include
#include
#include
using namespace std;
int compare(string str1,string str2)
{
    if(str1.length()>str2.length()) return 1;
    else if(str1.length()<str2.length())  return -1;
    else return str1.compare(str2);
}
string add(string str1,string str2)
{
    string str;
    int len1=str1.length();
    int len2=str2.length();
    //前面补0，弄成长度相同
    if(len1<len2)
    {
        for(int i=1;i<=len2-len1;i++)
           str1="0"+str1;
    }
    else
    {
        for(int i=1;i<=len1-len2;i++)
           str2="0"+str2;
    }
    len1=str1.length();
    int cf=0;
    int temp;
    for(int i=len1-1;i>=0;i--)
    {
        temp=str1[i]-'0'+str2[i]-'0'+cf;
        cf=temp/10;
        temp%=10;
        str=char(temp+'0')+str;
    }
    if(cf!=0)  str=char(cf+'0')+str;
    return str;
}
int main(){
    int t;
    cin>>t;
    string a,b;
    while(t--){
        cin>>a>>b;
        cout<<add(a,b)<<endl;
    }



    return 0;
}

4.配平方程式

考察点:最小公倍数

就对给定的两个数转换成正数后求最小公倍数就行

#include
using namespace std;
typedef long long ll;
int gcd(int a,int b){
    if(!b)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a*b/gcd(a,b);
}
int main(){
    int t;
    cin>>t;
    int x,y;
    while(t--){
        cin>>x>>y;
        x=abs(x);
        y=abs(y);
        cout<<lcm(x,y)/x<<":"<<lcm(x,y)/y<<endl;
    }


    return 0;
}

5.寻找卷王

考察点：递归
这个题考察的点主要是递归，天梯赛经常出现类似的题目（有没有觉得这个题目很“天梯”呢，就连输出的风格也挺像天梯赛的，主要是出题的时候刚刚打完天梯赛~）。 当给出的学生并不是题目中所定义的大卷王时，就需要一层一层的去搜索，直到寻找到大卷王为止。由于这个题的数据范围较小（为了降低难度）可以不使用并查集的方法来完成这个题目。如果数据范围较大的话，就需要每一次进行一次集合的合并，来减少搜索的时间。 至于题目的背景是根据一些极端的例子改编的，当然有些夸张，是不是感觉真的很“卷”。还好，通过的人数比去年招新赛卷王那道题多多了~

附代码：

#include
int pov[10010];
int find(int x) //不断的递归搜索，直到找到卷的源头为止 
{
	if (pov[x]==0)
	{
		return x;
	}
	return find(pov[x]); 
}
int main()
{
	int n,i;
	for (i=0;i<10001;i++)//预处理每个同学的信息 
	{
		pov[i]=-2;
	}
	scanf("%d",&n);
	for (i=0;i<n;i++)//录入每个同学的信息 
	{
		int s,t;
		scanf("%d %d",&s,&t);
		pov[s]=t;
	}
	int k;
	scanf("%d",&k);
	for (i=0;i<k;i++)
	{
		int s;
		scanf("%d",&s);  
		if (pov[s]==-1)//判断，如果是-1输出“躺平” 
		{
			printf("%d zai tang ping\n",s); 
		} 
		else if(pov[s]==0)//如果是0，则表明该同学就是卷的源头，输出“是大卷王” 
		{
			printf("%d shi da juan wang\n",s);
		 }
		 else //如果不是上述的特殊情况，则就要递归查找卷的源头 
		 {
		 	int Z;
		 	Z=find(s);
		 	printf("%d bei %d dai juan le\n",s,Z);
		  } 
	}
	return 0;
 } 

6. Vigenère cipher 分析

Vigenere密码

百科

核心思想：可以理解为密钥在滚动加密明文。

Vigengere密码使用一个词组作为密钥，第一个密钥字母加密明文的第一个字母，第二个密钥字母加密明文的第二个字母，等所有密钥字母使用完后，密钥又再循环使用（即，后文中未加密明文的第一个对应密钥的第一个，后面一一对应）。

# 可行代码

#include 
#include 
using namespace std;
const int MAX = 10000;
int main() {
  char key[100];
  char plaintext[MAX];
  cin >> plaintext >> key;
  int len = strlen(plaintext);
  int keyLen = strlen(key);
  for (int i = 0; i < len;)
    for (int j = 0; j < keyLen && i < len; j++) 
      plaintext[i++] = 'a' + 
        (plaintext[i] + key[j] - 2 * 'a') % 26;
  puts(plaintext);
  return 0;
}

7.我all两次

经典的取石子游戏（巴什博弈），题面基本上都是废话，总结一下就是一共n张卡，a，b两人轮流抽，每人每次最多抽k张，a先抽，问谁抽到最后一张。

如果我们把两人各抽一次作为一轮，那么我们不难发现这一轮一共抽了多少张卡是由后抽卡的人决定的。比如一共8张卡，每次最多抽3张，那么a无论是抽1张、2张还是三张，b都可以把这一轮抽的总张数控制为4张。按照这样抽卡的话，一共8张卡，两轮后刚好抽完，那么b就一定抽到最后一张也就是说，当总张数n能够被（k+1）整除时，b抽到最后一张，反之a抽到最后一张。

详解：https://www.cnblogs.com/Untergehen/p/16298681.html

代码如下：

#include
#include
using namespace std;
int main(){
    int t;
    int a[1000];
    int k,n;
    scanf("%d",&t);
    for(int i=0;i<t;i++){
    	scanf("%d %d",&k,&n);
    	if(n%(k+1))
            printf("I'll all twice.\n");
    	else
            printf("I'll all once.\n");
    }
    return 0;
}

8.要强的dumpline

这肯定能看明白是啥意思就直接输出就行了

#include
using namespace std;
typedef long long ll;
int main(){

    puts("English is a bad thing");

    return 0;
}