华北水利水电大学第十届ACM/ICPC程序设计新生赛题解

目录

1.Y=kx+b

 2.佩奇的数学问题

3.Seven Pass

4.Maximum Numbers

5. Transformation (Easy Version) 

6.Transformation (Hard Version) 

7.. F(x, y)的秘密 

8.彩虹音爆

9.冰与火之舞

​编辑

10.Fantastic

11.两级反转 

语言使用的C++;题目总体来说考察的是思维,和基础的编码能力,并没有使用到什么算法,只要认真写应该问题不大;

1.Y=kx+b

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int a,b,c;cin>>a>>b>>c;
    cout<<a*b+c;
    return 0;
}

 2.佩奇的数学问题

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int a;string b;cin>>a>>b;
    string ret;
    for(auto x:b)
    {
        ret+=to_string((x-'0')*a);
    }
    cout<<ret<<endl; 
    return 0;
}

3.Seven Pass

#include<bits/stdc++.h>
using namespace std;

bool check(const int &n)
{
    int ret=n;
    if(ret%7==0)return true;
    while(ret)
    {
        if(ret%10==7)return true;
        ret/=10;
    }
    return false;
}

int main()
{
    int t=0;
    cin>>t;
    while(t--)
    {
        int x;cin>>x;
        if(check(x))cout<<"Pass"<<endl;
        else
            cout<<x<<endl;
    }
    return 0;
}

4.Maximum Numbers

#include<bits/stdc++.h>

using namespace std;


int main()
{
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    int max_sum=0;
    int min_sum=0;
    for(int i=0;i<k;i++)
        min_sum+=a[i];
    for(int i=n-1;i>=n-k;i--)
        max_sum+=a[i];
    cout<<max_sum<<" "<<min_sum<<endl;
    return 0;
}

5. Transformation (Easy Version) 

#include<bits/stdc++.h>
using namespace std;


int main()
{
    int n,t;cin>>n>>t;
    int a[n+1];
    for(int i=1;i<=n;i++)cin>>a[i];
    while(t--)
    {
        int option=0;
        cin>>option;
        if(option==1)
        {
            int l,r,w;cin>>l>>r>>w;
            for(int i=l;i<=r;i++)a[i]+=w;
        }
        else if (option==2)
        {
            int tmp=0;cin>>tmp;
            int sum=0;
            if(tmp==1)
            {    
                for(int i=1;i<=n;i+=2)sum+=a[i];
            }
            else if (tmp==2)
            {
                for(int i=2;i<=n;i+=2)sum+=a[i];
            }
            cout<<sum<<endl; 
        }
    }
    return 0;
}

6.Transformation (Hard Version) 

这道题相对于上一道题不仅仅是数据范围的变化,效率也要求更高,如果每次都现场求和的话,就会TL;所以我们可以统计每次操作区间的偶数位和奇数位的增量;打印的和时候只需要减下去就可以了,

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll n,t;
    cin>>n>>t;
    ll a[n+1];
    ll sumji=0;
    ll sumou=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i%2==0)sumou+=a[i];
        else sumji+=a[i];
    }

    ll valji=0;
    ll valou=0;
    while(t--)
    {
        int option=0;
        cin>>option;
        if(option==1)
        {
            ll l,r,w;
            int countji=0;int countou=0;
           cin>>l>>r>>w;
            int n=r-l+1;
            //统计偶数和技术的个数
            if(n==1)
            {
                if(l%2!=0)countji++;
                else countou++;
            }
            else if(n%2==0)
            {
                countji+=n/2;countou+=n/2;
            }
            else 
            {
                if(l%2!=0)
                {
                    countji+=n/2+1;
                    countou+=n/2;
                }
                else 
                {
                    countji+=n/2;
                    countou+=n/2+1;
                }
            }
            valji+=countji*w;
            valou+=countou*w;
        }
        else if (option==2)
        {
            ll tmp=0;cin>>tmp;
            if(tmp==1)
            {    
                cout<<sumji+valji;
            }
            else if (tmp==2)
            {
                cout<<sumou+valou;
            }
            
            if(t)cout<<endl;
        }
    }
    return 0;
}

7.. F(x, y)的秘密 

这道题因为数据范围并不大,就那么几个,也没有更好的方法,只能枚举了; 

#include<bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
int main()
{
	int n, lx, rx, ly, ry;   
	cin >> n >> lx >> rx >> ly >> ry;     
	vector<int>a(n);
	vector<int>b(n);
	vector<int>c(n);     

	for (int i = 0; i < n; i++)cin >> c[i];
	for (int i = 0; i < n; i++)cin >> a[i];
	for (int i = 0; i < n; i++)cin >> b[i];

	int ret_max = -inf;
	int ret_min = inf;
	
		//枚举所有取值
		for (int x = lx; x <= rx; x++)
		{
			for (int y = ly; y <= ry; y++)
			{
				int sum = 0;
				for (int i = 0; i < n; i++) {
					int tmp = c[i] * pow(x, a[i]) * pow(y, b[i]);    
					sum += tmp;    
				}
				ret_max = max(ret_max, sum);    
				ret_min = min(ret_min, sum);  
			}
		}
		

	cout << ret_max << " " << ret_min << endl;    
	return 0;
}

8.彩虹音爆

这道题应该是最难的一道题,这道题的目的就是让我们判断二维矩阵中的只有三个因子的数,就是完全平方数,但并不是所有的完全平方数都只有3个因子;

举个例子,81是一个完全平方数,除了1和81之外,因子就是平方根9,但是9的因子除了1和9之外,9还可以再拆3*3,那么这个时候81的因子就超过3个了,所以还要有一个条件就是该平方数的平方根是素数;

#include<bits/stdc++.h>
using namespace std;
#define ll long long


set<ll>s;

bool is_prime(ll n)
{
    if(n<2)return false;
    for (int i = 2; i * i <= n; i ++)
        if (n % i == 0)return false;
    return true;
}


bool check(ll x)//检查是否是完美银块
{
    ll tmp = (ll)sqrt(x);
    if (tmp * tmp != x)return  false;
    else  return is_prime(tmp);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    vector<vector<ll>>a(n, vector<ll>(n));
    ll ret = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
            if (s.count(a[i][j]))ret += a[i][j];
            else
                if (check(a[i][j]))
                {
                    ret += a[i][j];
                    s.insert(a[i][j]);
                }
        }

    }
    cout << ret<<"\n";
    return 0;
}

9.冰与火之舞

 这道题算是一道简单的贪心问题,偶数位值之和大于奇数位值之和,我们使用双指针,依次将奇数位的最大值和偶数位的最小值进行swap,最后判断一下,满足条件按需求打印即可;

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t = 0; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        vector<int>arr(n + 1);
        int s1 = 0, s2 = 0;
        for (int i = 1; i <= n; i++)
        {
            arr[i] = i;
            if (i % 2 == 0)s2 += i;
            else s1 += i;
        }

        if (n == 1 || n == 3) {
            cout << -1;
            if (t)cout << "\n";
        }
        else if (n % 2 == 0)
        {
            for (int i = 1; i <= n; i++)
            {
                if (i == 1)cout << arr[i];
                else
                    cout << " " << arr[i];
            }
            if(t)cout << "\n"; 
        }
        else
        {
            int left = 2; int right = n;
            while (left < right && s1>s2)
            {

                s1 += arr[left] - arr[right];
                s2 += arr[right] - arr[left];
                swap(arr[left], arr[right]);
                left += 2; right -= 2;
            }
            //cout << (s2 > s1) << "ascascac";
            if (s2 > s1)
            {
                for (int i = 1; i <= n; i++)
                {
                    if (i == 1)cout << arr[i];
                    else
                        cout << " " << arr[i];
                }
            }
            else cout << -1;
            if (t)cout << "\n";

        }

    }




    return 0;
}

10.Fantastic

 这道题是一道数学组合排列的问题;题意是任意相邻的两个数的成绩不能是素数;

1和任何素数的乘积都是素数;除1外的任何素数乘上无论是素数还是非素数结果都不是素数;

这道题就是要求我们排1;1不能和素数挨着;然后就是组合问题了;

1可以在数组的头部和尾部如果在头部,则数组的第二位,不许是非素数;后面的位置全排列即可;

1在尾部跟头部是对称的;

1在中间:左边一位和右边一位必须是非素数;其他的全排列即可;

#include<bits/stdc++.h>
#define ll long long 
const int mod = 998244353;
using namespace std;

//判断是否是素数
bool is_prime(int n)
{
	if (n < 2)return false;
	for (int i = 2; i * i <= n; i++)
		if (n % i == 0)return false;

	return true;
}

//求阶乘
ll fact(ll x)
{
	ll ret = 1;   
	for (int i = 1; i <= x; i++)
	{
		ret = ret % mod * i % mod;
		ret%=mod;   
	}
	return ret;
}

int prime_num(int n)
{
	int cnt = 0;
	for (int i = 2; i <= n; i++)
		if (is_prime(i))cnt++;
	return cnt;
}

int main()
{
	int t = 0; cin >> t;
	while (t--)
	{
		ll n; cin >> n;
		ll cnt = prime_num(n);//统计2-n素数的个数  
		ll nocnt = n - cnt - 1;//不是素数的个数n-1-cnt       
		//第一种情况
		ll ret1 = 2 % mod * nocnt % mod * fact(n - 2) % mod;
		ret1 %= mod;
		//cout << ret1 << endl; 
		ll ret2 = 0;

		if (nocnt > 1)
		{
			ret2 = nocnt % mod * (nocnt - 1) % mod * fact(n - 2) % mod;
			ret2 %= mod;
		}
		//第二种情况
		ll ret = ret1 % mod + ret2 % mod;
		ret %= mod;
		cout << ret ;
        if(t)cout<<endl; 
	}
    return 0;
}

11.两级反转 

数组都给出来了,直接无脑按需求判断即可;

#include<bits/stdc++.h>

using namespace std;


int main()
{
    int a[4][4];
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
            cin>>a[i][j];
    }

    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            int cnt=0;
            int _a=a[i][j];
            int b=a[i][j+1];int c=a[i+1][j];
            int d=a[i+1][j+1];
            cnt=_a+b+c+d;
          //  cout<<cnt<<endl;
            if(cnt==4||cnt==3||cnt==1||cnt==0){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}