您现在的位置是：首页 >技术教程 >2023 年第五届河南省 CCPC 大学生程序设计竞赛网站首页技术教程

2023 年第五届河南省 CCPC 大学生程序设计竞赛

WA_自动机 2024-06-14 17:18:27
简介2023 年第五届河南省 CCPC 大学生程序设计竞赛

题目地址

题目PDF地址

题解地址

Problem A. 小水獭游河南

∣ a ∣ ≤ ∣ Σ ∣ = 26 ，暴力枚举 a 判断 b 是否为是回文串即可，时间复杂度 O ( ∣ Σ ∣ ∣ s ∣ ) 。 |a| ≤ |Σ| = 26，暴力枚举 a 判断 b 是否为是回文串即可，时间复杂度 O(|Σ||s|)。 ∣a∣≤∣Σ∣=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
";
			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
";
				ok=true;
				break;
			} 
			b[s[i]]++;
		}
		if(!ok) cout<<"NaN
";
	}
    
	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]<<"
";
	}

	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()
{
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
	
    int T;cin>>T;
    while(T--)
    {
    	string s;cin>>s;
    	LL x=0,y=0;
    	int pos=0;
    	for(int i=0;i<s.size();i++)
    	{
    		if(s[i]=='^') 
    		{
    			pos=i+2;
    			break;
			}
    		x=x*10+s[i]-'0';
		}
		for(int i=pos;i<s.size();i++)
		{
			if(s[i]=='}') break;
			y=y*10+s[i]-'0';
		}
		
		__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)
		{
			for(auto c:line)
				cout<<c;
			cout<<"
";
		}
	}
    
	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 √ n ) O(n√n) O(n√n) 已经足以通过此题。

#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;
}
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐