2023 年第五届河南省 CCPC 大学生程序设计竞赛-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023 年第五届河南省 CCPC 大学生程序设计竞赛。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目地址

题目PDF地址

题解地址

Problem A. 小水獭游河南

$∣ a ∣ \leq ∣Σ∣ = 26 ，暴力枚举 a 判断 b 是否为是回文串即可，时间复杂度 O (∣Σ∣∣ s ∣) 。$

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;cin>>T;
    while(T--)
    {
    	string s;cin>>s;
    	if(s.size()==1) 
		{
			cout<<"NaN\n";
			continue;
		} 
    	
    	map<char,int> b;
    	bool ok=false;
		for(int i=0;i<s.size();i++)
    	{
    		if(b[s[i]]) break;
    		string str=s.substr(i+1);
    		string ss=str;
    		reverse(str.begin(),str.end());
    		if(str==ss)
			{
				cout<<"HE\n";
				ok=true;
				break;
			} 
			b[s[i]]++;
		}
		if(!ok) cout<<"NaN\n";
	}
    
	return 0;
}

Problem B. Art for Rest

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

const int N = 1000001, M = 21;
int f[N][M],g[N][M];
int lg[N],a[N];
int n;

bool st[N];

inline int max(int A,int B)
{
    return A>B?A:B;
}

inline int min(int A,int B)
{
    return A<B?A:B;
}

void init()
{
    lg[1]=0;
    for(int i=2;i<=1000000;i++) lg[i]=lg[i>>1]+1;
    for(int j=0;j<20;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            if(!j) f[i][j]=g[i][j]=a[i];
            else
            {
                f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
                g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
            }
}

inline int query_max(int l,int r)
{
    int k=lg[r-l+1];
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

inline int query_min(int l,int r)
{
    int k=lg[r-l+1];
    return min(g[l][k],g[r-(1<<k)+1][k]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    if(is_sorted(a+1,a+n+1))
    {
        cout<<n;
        return 0;
    }

    init();

    int res=1;
    for(int k=2;k<=n-1;k++)
    {
        if(st[k])
        {
            res++;
            continue;
        }
        bool ok=true;
        int l=1,r=k;
        while(r<n)
        {
            int mx=query_max(l,r);
            int mn=query_min(l+k,min(r+k,n));
            if(mx>mn)
            {
                ok=false;
                break;
            }
            l+=k,r+=k;
        }
        if(ok)
        {
            for(int j=k;j<=n-1;j+=k)
                st[j]=true;
            res++;
        }
    }
    cout<<res;

	return 0;
}

Problem E. 矩阵游戏

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

const int N = 510, M = 1010;
char s[N][N];
int dp[3][N][M];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;cin>>T;
	while(T--)
	{
		int n,m,x;cin>>n>>m>>x;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>s[i][j];

        for(int k=0;k<2;k++)
            for(int i=0;i<=m;i++)
                for(int j=0;j<=x;j++)
                    dp[k][i][j]=0;

		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				for(int k=0;k<=x;k++)
					if(s[i][j]=='0') dp[i&1][j][k]=max(dp[i&1][j-1][k],dp[(i-1)&1][j][k]);
					else if(s[i][j]=='1') dp[i&1][j][k]=max(dp[i&1][j-1][k],dp[(i-1)&1][j][k])+1;
					else
					{
						if(k>=1) dp[i&1][j][k]=max(dp[i&1][j-1][k-1],dp[(i-1)&1][j][k-1])+1;
						else dp[i&1][j][k]=max(dp[i&1][j-1][k],dp[(i-1)&1][j][k]);
					}
		cout<<dp[n&1][m][x]<<"\n";
	}

	return 0;
}

Problem F. Art for Last

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

typedef long long LL;
const int N = 500010;
int a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);

    multiset<int> b;
    for(int i=2;i<=k-1;i++)
        b.insert(a[i]-a[i-1]);

    LL res=1e18;
    for(int i=k;i<=n;i++)
    {
        b.insert(a[i]-a[i-1]);
        res=min(res,(LL)*b.begin()*(a[i]-a[i-k+1]));
        b.erase(b.lower_bound(a[i-k+2]-a[i-k+1]));
    }
    cout<<res;

	return 0;
}

Problem G. Toxel 与字符画

按照题意模拟即可。例如，一种实现方式是，将题面提供的各种字符画在程序中存入一个二维字符矩阵中。随后计算表达式的值，并求出该表达式所需使用的各个字符。最后根据这些字符，找到相对应的字符画，拼接在答案后即可。

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

typedef long long LL;

string a[]=
{
	".................................................................................",
	".................................................................................",
	".0000000.......1.2222222.3333333.4.....4.5555555.6666666.7777777.8888888.9999999.",
	".0.....0.......1.......2.......3.4.....4.5.......6.............7.8.....8.9.....9.",
	".0.....0.......1.......2.......3.4.....4.5.......6.............7.8.....8.9.....9.",
	".0.....0.......1.2222222.3333333.4444444.5555555.6666666.......7.8888888.9999999.",
	".0.....0.......1.2.............3.......4.......5.6.....6.......7.8.....8.......9.",
	".0.....0.......1.2.............3.......4.......5.6.....6.......7.8.....8.......9.",
	".0000000.......1.2222222.3333333.......4.5555555.6666666.......7.8888888.9999999.",
	"................................................................................."
};
string b[]=
{
	".............................................................",
	".00000.....1.22222.33333.4...4.55555.66666.77777.88888.99999.",
	".0...0.....1.....2.....3.4...4.5.....6.........7.8...8.9...9.",
	".0...0.....1.22222.33333.44444.55555.66666.....7.88888.99999.",
	".0...0.....1.2.........3.....4.....5.6...6.....7.8...8.....9.",
	".00000.....1.22222.33333.....4.55555.66666.....7.88888.99999.",
	".............................................................",
	".............................................................",
	".............................................................",
	"............................................................."
};
string c[]=
{
	".................................",
	".................................",
	".........IIIIIII.N.....N.FFFFFFF.",
	"............I....NN....N.F.......",
	".=======....I....N.N...N.F.......",
	"............I....N..N..N.FFFFFFF.",
	".=======....I....N...N.N.F.......",
	"............I....N....NN.F.......",
	".........IIIIIII.N.....N.F.......",
	"................................."
};

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		LL x,y;
		scanf("%lld^{%lld}",&x,&y);

		__int128 sum=1;
		bool ok=false;
		if(x!=1)
		{
			for(LL i=1; i<=y; i++)
			{
				sum*=x;
				if(sum>1000000000000000000ll)
				{
					ok=true;
					break;
				}
			}
		}

		vector<string> res(10);

		string xx=to_string(x);
		string yy=to_string(y);

		for(int i=0; i<xx.size(); i++)
		{
			int number=xx[i]-'0';
			for(int k=0; k<8; k++)
				for(int j=0; j<10; j++)
					res[j].push_back(a[j][number*8+k]);
		}

		for(int i=0; i<yy.size(); i++)
		{
			int number=yy[i]-'0';
			for(int k=0; k<6; k++)
				for(int j=0; j<10; j++)
					res[j].push_back(b[j][number*6+k]);
		}

		for(int k=0; k<8; k++)
			for(int j=0; j<10; j++)
				res[j].push_back(c[j][k]);

		if(ok)
		{
			for(int k=8; k<33; k++)
				for(int j=0; j<10; j++)
					res[j].push_back(c[j][k]);
		}
		else
		{
			string zz=to_string((LL)sum);
			for(int i=0; i<zz.size(); i++)
			{
				int number=zz[i]-'0';
				for(int k=0; k<8; k++)
					for(int j=0; j<10; j++)
						res[j].push_back(a[j][number*8+k]);
			}
			for(int j=0; j<10; j++)
				res[j].push_back('.');
		}

		for(auto line:res)
			printf("%s\n",line.c_str());
	}

	return 0;
}

Problem H. Travel Begins

Problem K. 排列与质数

对于 n ≤ 11，可以暴力枚举排列求解；
对于 n > 11 的奇数，先将数按照 1, 3, 5, . . . , n − 2, n, n −3, n − 5, . . . , 8, 6, 4 排列；
对于 n > 11 的偶数，先将数按照 1, 3, 5, . . . , n − 3, n, n −2, n − 4, . . . , 8, 6, 4 排列；
即先将奇数升序排列，再将偶数降序排列。

可以发现，现在除了 2 和 n − 1 以外，所有数均已出现，且满足题目的限制。那么我们只需要将这两个数插进合适的位置即可。容易发现一定有解，因为可以将 2 插在 5 和 7 之间，将n − 1 插在 n − 4 和 n − 6 之间。
复杂度取决于判断质数的速度， $O (n \sqrt n)$ 已经足以通过此题。文章来源地址https://www.toymoban.com/news/detail-438106.html

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

bool p(int n)
{
	if(n<=1) return false;
	for(int i=2;i<=n/i;i++)
		if(n%i==0)
			return false;
	return true;
}

int main()
{
	int n;cin>>n;
	
	if(n<=4) cout<<"-1";
	else if(n<=11)
	{
		vector<int> pos(n);
		for(int i=0;i<n;i++) pos[i]=i+1;
		do{
			bool ok=false;
			for(int i=1;i<n;i++)
				if(!p(abs(pos[i]-pos[i-1])))
				{
					ok=true;
					break;
				}
			if(!p(abs(pos[0]-pos[n-1]))) ok=true;
			if(!ok)
			{
				for(auto c:pos)
					cout<<c<<" ";
				break;
			}
		}while(next_permutation(pos.begin(),pos.end()));
	}
	else
	{
		vector<int> res;
		if(n&1)
		{
			for(int i=1;i<=n;i+=2)
				res.push_back(i);
			for(int i=n-3;i>=4;i-=2)
				res.push_back(i);
			
			for(int i=0;i<res.size();i++)
			{
				cout<<res[i]<<" ";
				if(res[i]==5) cout<<"2 ";
				if(res[i]==n-6) cout<<n-1<<" ";
			}
		}
		else
		{
			for(int i=1;i<=n-3;i+=2)
				res.push_back(i);
			for(int i=n;i>=4;i-=2)
				res.push_back(i);
			
			for(int i=0;i<res.size();i++)
			{
				cout<<res[i]<<" ";
				if(res[i]==5) cout<<"2 ";
				if(res[i]==n-4) cout<<n-1<<" ";
			}
		} 
	}
	
	return 0;
}