• 公告

  • 南阳理工学院第二届省内高校新生程序设计大赛（网络）邀请赛 题解

  • @ 2021-12-14 15:28:10

写在前面：

​ 首先，我代表出题组，组题组，先对大家致以最真诚的歉意。本来题目要求是8-10道，最后我们一共出题、整理了11道题。验题之后，我们一直在商量删去哪一题，但是经过多方商议，都不想删去自己的题。最后我一想，干脆放11题算了，题多，不至于让那么多人坐牢。

​ 签到题是我出的，我对那些爆零的同学先道个歉，我出的签到好像并没有签上到，以后如果再有机会，肯定会有一个真正的签到题！

​ 这场是属于榜歪的一场，B题我们验题的时候，是认为他是个签到题的，直接暴力即可。但是赛场上好像只有用bfs过的，并没有人写暴力

题目链接

A、天理的维系者的进制魔法

本题是一道签到题，主要考察是否能熟练掌握十进制与二进制之间的转化，题目上二进制数的范围最大是2352^{35}

，也就是说他的二进制数最多有35位数，必须要用字符串去存，然后再一个一个拆解字符串，就得到了十进制数字

时间复杂度：O(n)O(n)

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#define ll long long
using namespace std;
ll matrix[510][510];
ll a(char str[])
{
    ll sum = 0;
    ll j = 1;
    ll pos = strlen(str) - 1;
    for(; pos >= 0; pos--) 
    {
        sum += (str[pos] - '0') * j;
        j *= 2;
    }
    return sum;
}
int main()
{

    char num[50];
    int n;
    scanf("%d",&n);
    while(n--)
    {
        memset(num,0,sizeof(num));
        scanf("%s",num);
        ll ans=a(num);
        printf("%lld\n",ans);
    }
    return 0;
}

B、好耶！是大冒险！

本题由于数据范围极小，解法多样，是个签到题

容易发现，其实本题也就 3∗3∗3∗3=813*3*3*3=81 种可能出现的情况

所以可以直接使用forfor循环暴力枚举对四颗石头的敲击次数，再找到步数最小的情况是多少即可

时间复杂度：O(1)O(1)

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a[5],ans=100;
	for(int i=1;i<=4;i++)
		cin>>a[i];
	for(int i=0;i<=2;i++)
	{
		for(int j=0;j<=2;j++)
		{
			for(int k=0;k<=2;k++)
			{
				for(int l=0;l<=2;l++)
				{
					int s1,s2,s3,s4;
					s1=(a[1]+i+j-1)%3+1;
					s2=(a[2]+i+j+k-1)%3+1;
					s3=(a[3]+j+k+l-1)%3+1;
					s4=(a[4]+k+l-1)%3+1;
					if(s1==s2&&s2==s3&&s3==s4)
					{
						ans=min(ans,i+j+k+l);
					}
				}
			}
		}
	}
	cout<<ans<<endl;
}

当然，使用BFSBFS 、DFSDFS 搜索也能轻松解决

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct stone
{
	int a[6],step;
}s;
queue<stone>q;
bool vis[5][5][5][5];
bool check(stone k)
{
	for(int i=2;i<=4;i++)
		if(k.a[i]!=k.a[i-1])
			return false;
	return true;
}
int bfs()
{
	while(!q.empty())
	{
		stone k=q.front();
		q.pop();
		if(check(k))
			return k.step;
		for(int i=1;i<=4;i++)
		{
			for(int j=1;j<=4;j++)
			{
				if(abs(i-j)<=1)
				{
					s.a[j]=k.a[j]+1;
					if(s.a[j]==4)
					s.a[j]=1;
				}
				else
					s.a[j]=k.a[j];
			}
			s.step=k.step+1;
			if(vis[s.a[1]][s.a[2]][s.a[3]][s.a[4]]) continue;
			vis[s.a[1]][s.a[2]][s.a[3]][s.a[4]]=1;
			q.push(s);
		}
	}
    return -1;
}
int main()
{
	for(int i=1;i<=4;i++)
	{
		scanf("%d",&s.a[i]);
	}
	s.step=0;
	q.push(s);
	int ans=bfs();
	printf("%d\n",ans);
}

C、质数区间

题目大意：给出nn个区间，求区间并的质数数量。

方法一：对于每个区间枚举数进行判断，使用n\sqrt{n}的方法判断质数。时间复杂度为O(nmm))O(nm\sqrt{m}))，不能通过此题。

优化1：将判断过的数打上标记，这样每个数只会判断一次，时间复杂度为O(nm+mm)O(nm+m\sqrt{m})，可以通过此题。

优化2：用埃氏筛/欧拉筛等方法预处理出质数，这样可以O(1)O(1)判断质数，时间复杂度为O(nm)O(nm)，可以通过此题。

优化3：用埃氏筛/欧拉筛等方法预处理出质数，然后用差分数组预处理区间并，时间复杂度为O(m)O(m)，可以通过此题。

参考代码：

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

const long long N = 1e5 + 5;

int prime[N];
int vis[N];
int delta[N];

void Prime()
{
    vis[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        if (!vis[i])
            prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0] && i * prime[j] <= N; j++)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}

int main()
{
    Prime();
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        delta[l]++;
        delta[r + 1]--;
    }
    for (int i = 1; i <= (int)1e5; i++)
        delta[i] += delta[i - 1];
    int ans = 0;
    for (int i = 1; i <= (int)1e5; i++)
        ans += (delta[i] > 0) && (!vis[i]);
    printf("%d\n", ans);
    return 0;
}

D、艾琳的困难

动态规划

定义 dp[j][i]dp[ j ] [ i ]

表示形成总和为 jj 时 用了 ii 个 数字的方案数

对于总和为 jj 数字个数为 ii 时， 如果新来一个数为l时，那么他能形成的状态应该是dp[j−l∗l][i−1]d p [ j - l * l ] [ i - 1]；

那么枚举j,i,lj,i,l即可

动态转移方程是dp[j][i]=(dp[j][i]+dp[j−l∗l][i−1])dp[j][i]=(dp[j][i]+dp[j-l*l][i-1])% P;

时间复杂度：O(nn)O(n\sqrt{n})

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int P = 998244353;
int dp[N][33];
int n[N];
int fun(int n, int k) {
    for (int i = 0; i <= k; i++) dp[0][i] = 1;
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            for (int l = 0; l*l<= j ; l++) {
                dp[j][i] = (dp[j][i] + dp[j - l * l][i - 1]) % P;
            }
        }
    }
    return dp[n][k] % P;
}
signed main(){
    int t, k, ls = 0;
    scanf("%d%d",&t,&k);
    for (int i = 1; i <= t; i++) {
        scanf("%d",&n[i]);
    }
    fun(t, k);
    for (int i = 1; i <= t; i++) {
        printf("%d\n",dp[n[i]][k]);
    }
}

E、迪卢克玩扑克牌

这题暴力解法即可，坑点是需要将三张牌，按照规则大小进行排序，之后暴力解即可；

时间复杂度：O(n∗n∗T)O(n*n*T)

标程1：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct qw{
	string a,b,c;
}s[N];
int ans[N];
map<string ,int>mp;
bool find(int i,int j)
{
	if(s[i].a==s[i].b&&s[i].a==s[i].c)
	{
		if(s[j].a==s[j].b&&s[j].a==s[j].c)
		{
			return mp[s[i].a]>mp[s[j].b];
		}
		if(s[j].a=="2"&&s[j].b=="3"&&s[j].c=="5")
		{
			return 0;
		}
		return 1;
	}
	if(mp[s[i].a]+1==mp[s[i].b]&&mp[s[i].b]+1==mp[s[i].c])
	{
		if(s[j].a==s[j].b&&s[j].a==s[j].c)
		{
			return 0;
		}
		if(mp[s[j].a]+1==mp[s[j].b]&&mp[s[j].b]+1==mp[s[j].c])
		{
			return mp[s[i].a]>mp[s[j].a];
		}
		return 1;
	}
	if(s[i].a==s[i].b||s[i].b==s[i].c)
	{
		int ls;
		if(s[i].a==s[i].b)
		{
			ls=1;
		}
		if(s[i].b==s[i].c)
		{
			ls=2;
		}
		if(s[j].a==s[j].b&&s[j].a==s[j].c)
		{
			return 0;
		}
		if(mp[s[j].a]+1==mp[s[j].b]&&mp[s[j].b]+1==mp[s[j].c])
		{
			return 0;
		}
		if(s[j].a==s[j].b||s[j].b==s[j].c)
		{
			int ls2;
			if(s[j].a==s[j].b)
			{
				ls2=1;
			}
			if(s[j].b==s[j].c)
			{
				ls2=2;
			}
			if(ls==1)
			{
				if(ls2==1)
				{
					if(s[i].a==s[j].a)
					{
						return mp[s[i].c]>mp[s[j].c];
					}
					return mp[s[i].a]>mp[s[j].a];
				}
				if(ls2==2)
				{
					if(s[i].a==s[j].c)
					{
						return mp[s[i].c]>mp[s[j].a];
					}
					return mp[s[i].a]>mp[s[j].c];
				}	
			}
			if(ls==2)
			{
				if(ls2==1)
				{
					if(s[i].c==s[j].a)
					{
						return mp[s[i].a]>mp[s[j].c];
					}
					return mp[s[i].c]>mp[s[j].a];
				}
				if(ls2==2)
				{
					if(s[i].c==s[j].c)
					{
						return mp[s[i].a]>mp[s[j].a];
					}
					return mp[s[i].c]>mp[s[j].c];
				}	
			}
		}
		return 1;
	}
	if(s[j].a==s[j].b&&s[j].a==s[j].c)
	{
		if(s[i].a=="2"&&s[i].b=="3"&&s[i].c=="5")
		{
			return 1; 
		}
		return 0;
	}
	if(mp[s[j].a]+1==mp[s[j].b]&&mp[s[j].b]+1==mp[s[j].c])
	{
		return 0;
	}
	if(s[j].a==s[j].b||s[j].a==s[j].c||s[j].b==s[j].c)
	{
		return 0;
	}
	if(mp[s[i].c]==mp[s[j].c])
	{
		if(mp[s[i].b]==mp[s[j].b])
		{
			return mp[s[i].a]>mp[s[j].a];
		}
		else
		{
			return mp[s[i].b]>mp[s[j].b];
		}
	}
	else
	{
		return mp[s[i].c]>mp[s[j].c];
	}
}
int main(){
	int t;
	cin>>t;
	mp["2"]=2;
	mp["3"]=3;
	mp["4"]=4;
	mp["5"]=5;
	mp["6"]=6;
	mp["7"]=7;
	mp["8"]=8;
	mp["9"]=9;
	mp["10"]=10;
	mp["J"]=11;
	mp["Q"]=12;
	mp["K"]=13;
	mp["A"]=14;
	while(t--)
	{
		int n;
		cin>>n;
		memset(ans,0,sizeof(int)*(n+5));
		for(int i=1;i<=n;i++)
		{
			cin>>s[i].a>>s[i].b>>s[i].c;
			if(mp[s[i].a]>mp[s[i].b])
				swap(s[i].a,s[i].b);
			if(mp[s[i].a]>mp[s[i].c])
				swap(s[i].a,s[i].c);
			if(mp[s[i].b]>mp[s[i].c])
				swap(s[i].b,s[i].c);
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i!=j&&find(i,j))
				{
					ans[i]++;
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			cout<<ans[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

标程2；

由于标程1写的太丑了，一位牛皮网友写了个更好的代码，具体实现能看懂的可以自己学习一下

#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
int a[20][5],ans[20];
string s[]={"","","2","3","4","5","6","7","8","9","10","J","Q","K","A"};
struct uvw{
	int a,b,c,d;
}e[20];
void make(int x){
	if(a[x][1]==a[x][3]){
		e[x].a=3,e[x].b=a[x][1];
	}else if(a[x][1]+1==a[x][2]&&a[x][2]+1==a[x][3]){
		e[x].a=2,e[x].b=a[x][3];
	}else if(a[x][1]==a[x][2]||a[x][2]==a[x][3]){
		e[x].a = 1;
		e[x].b = a[x][1]==a[x][2] ? a[x][1] : a[x][2];
		e[x].c = a[x][1]==a[x][2] ? a[x][3] : a[x][1];
	}else{
		e[x].b=a[x][3],e[x].c=a[x][2],e[x].d=a[x][1];
	}
}
bool cmp(int x,int y){
	if(e[x].a==3&&e[y].a==0){
		if(e[y].b==5&&e[y].c==3&&e[y].d==2) return false;
		else return true;
	}
	if(e[x].a==0&&e[y].a==3){
		if(e[x].b==5&&e[x].c==3&&e[x].d==2) return true;
		else return false;
	}
	return e[x].a*1000000+e[x].b*10000+e[x].c*100+e[x].d>e[y].a*1000000+e[y].b*10000+e[y].c*100+e[y].d;
}
signed main(){
	for(int i=2;i<=14;i++) mp[s[i]]=i;
	int t,n;
	string s1,s2,s3;
	cin>>t;
	while(t--){
		cin>>n;
		memset(ans,0,sizeof(ans));
		memset(e,0,sizeof(e));
		for(int i=1;i<=n;i++){
			cin>>s1>>s2>>s3;
			a[i][1]=mp[s1];
			a[i][2]=mp[s2];
			a[i][3]=mp[s3];
			sort(a[i]+1,a[i]+4);
			make(i);
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i!=j&&cmp(i,j)){
					ans[i]++;
				} 
			}
		}
		for(int i=1;i<=n;i++){
			cout<<ans[i]<<" \n"[i==n];
		}
	}
}

F、 CY 的 ddl

题目大意：nn个人构成一个排列，第ii个人有两个属性SiSi、TiTi。

记第ii个人的贡献为：f(m)=Sm+∑1m−1(Si+Ti)f(m)=Sm+\sum_1^{m-1}(Si+Ti)

排列贡献为：∑1nf(i)\sum_1^{n}f(i)

可以对所有人重排列，要求排列贡献最小值。

可以用贪心的邻项交换法证明，按照每个人S+T的值进行排序最优。

时间复杂度：O(nlogn)O(nlogn)

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
struct node
{
    int a, b;
} s[N];
int cmp(node q, node p) { return q.a + q.b < p.a + p.b; }
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &s[i].a, &s[i].b);
    sort(s, s + n, cmp);
    int ans = 0, sum = 0;
    for (int i = 0; i < n; i++)
    {
        ans += sum + s[i].a;
        sum += s[i].a + s[i].b;
    }
    printf("%d\n", ans);
    return 0;
}

G、hxx 的美食生活

贪心，更晚的时间能做的美食只会更多，因此对于同一份美食，肯定优先更早制作。同时，对于一个时间，制作在此之前愉悦值最高的美食是最优的，若存在多个，则选择时间最早的。

时间复杂度：O(nlogn)O(nlogn)

参考代码：

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

const long long N = 2e5 + 5;

struct node
{
    long long l, m;
    bool operator<(const node &temp) const { return l > temp.l; }
} s[N];
int main()
{
    long long n, x;
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
        scanf("%lld %lld", &s[i].l, &s[i].m);
    sort(s + 1, s + 1 + n);
    long long ans = 0;
    for (int j = 8; j <= 22; j++)//贪心先使用更早的时间
    {
        int p = 0, res = 0;
        for (int i = 1; i <= n; i++)//找愉悦值最高的美食
        {
            if (s[i].l >= 23)
                continue;
            if (s[i].l <= j && s[i].m - (j >= 19 ? x : 0) > res)
            {
                res = s[i].m - (j >= 19 ? x : 0);
                p = i;
            }
        }
        ans += res;
        s[p].m = -1;//将制作过的美食愉悦值置为-1，这样下次必然不会使用。
    }
    if (ans == 0)
        puts("zxnbbjtqsl");
    else
        printf("%lld\n", ans);

    return 0;
}

H、 小 W 的花园

n∗nn*n的方格中 有若干个#点，每天#\#点会把周围上下左右四个点变成#,问全部变成#所需要的时间。

简单的bfsbfs题，将初始为#的点的坐标一次性全部放入队列，时间设定为00。当队列为空时，代表所有格子都变成了00，队列中最后一个点的时间即答案。

时间复杂度：O(n2)O(n^2)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m;
ll mv[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

ll mp[1005][1005];
bool vis[1005][1005];
struct node
{
    ll x, y, t;
} x1, e;
queue<node> q;
ll bfs()
{
    ll i, j;
    ll ans = 0;
    while (!q.empty())
    {
        x1 = q.front();
        q.pop();
        ans = x1.t;
        for (i = 0; i < 4; i++)
        {
            e.x = x1.x + mv[i][0];
            e.y = x1.y + mv[i][1];
            if (e.x < 0 || e.y < 0 || e.x >= n || e.y >= n)
                continue;
            if (vis[e.x][e.y] == 1)
                continue;
            vis[e.x][e.y] = 1;
            e.t = x1.t + 1;
            q.push(e);
        }
    }
    return ans;
}
int main()
{
    cin >> n;
    string s;

    ll i, j;
    for (i = 0; i < n; i++)
    {
        cin >> s;
        for (j = 0; j < n; j++)
        {
            if (s[j] == '#')
            {
                q.push({i, j, 0});
                vis[i][j] = 1;
            }
        }
    }
    cout << bfs() << endl;
    return 0;
}

I、 原来，你也玩原神

题面全是废话，只有输入和输出两句话有用，根据这两句话，我们很容易就能明白直接找字符串“ylnywys”“ylnywys”出现了多少次即可，而且没有循环，没有任何卡点，就是一个最简单的计数输出的签到题。

时间复杂度：O(n)O(n)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;
char a[200006];
int main(){
	int n, ans = 0;
	scanf("%s", a);
	int l = strlen(a);
	for(int i = 0; i < l; i++){
		if(a[i] =='y'&&a[i+1]=='l'&&a[i+2]=='n' && a[i+3]=='y' && a[i+4]=='w'&&a[i+5]=='y'&&a[i+6]=='s'){
			ans++;
		}
	}
	printf("%d", ans);
	return 0;
}

J、 石子游戏 2020

这个题是根据文件上所说，是我们oj：oj.fuquan.moe的原题，甚至连题面都没有改。

读完题目后会发现，把全部石子加起来，判断一下奇偶即可。

在oj中查找题目名就能找到。

时间复杂度：O(n)O(n)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
int a[100005];
int main(){
	int n;
	ll sum = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
		sum += a[i];
	}
	if(sum & 1){
		printf("ddd\n");
	}
	else{
		printf("bqp\n");
	}
	return 0;
}

K、 小 w 的数学题

题目意思是求同时满足下面三个式子整数三元组的个数：

(1)1≤a≤b≤c≤n(1) 1 \leq a \leq b \leq c \leq n

(2)c2=a2+b2(2)c^2=a^2+b^2

(3)c=a2−b(3)c=a^2-b

由式2与式3可以得到：

b=c−1b=c-1

将其代入式2可以得到

a2=2∗c−1a^2=2*c-1

又已知c≤nc \leq n，因为b=c−1b=c-1，所以满足条件的情况下bb一定小于cc，再因为2∗c−12*c-1一定为一个奇数，那么aa也一定为一个奇数，接下来我们要讨论的就是a≤ba \leq b这个条件。把bb转换为aa带入其中。

a≤(a2+1)/2−1a \leq (a^2+1)/2-1

解得当a>=2a>=2时有解，那么当a=1a=1时候，不满足a≤ba \leq b。

已知cc的范围，可以求到最大的aa为多少，又因为aa一定为奇数，且a!=1a!=1，最后得到aa能取的值的个数为(sqrt(2∗c−1)−1)/2(sqrt(2*c-1)-1)/2

注意题目数据范围，需要开long longlong\ long。

时间复杂度：O(1)O(1)

参考代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long t, p;
    cin >> t;
    while (t--)
    {
        cin >> p;
        cout << ((long long)sqrt(2 * p - 1) - 1) / 2 << endl;
    }
    return 0;
}

3 comments

  • 1
54
Accepted
0
Solutions Liked
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Theme
  3. Worker 0 in 48ms
  4. Powered by Hydro v4.4.4 Community