比赛链接:https://codeforces.ml/contest/1739

这样有点难,B使劲WA,C题直接解不出来,思维上要求很高。C题更是赛出了组合数学

A题:水题,棋盘固定走法,求哪个格子没有可走的步子。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,m;
bool check(int i,int j){
	if((i-1<1||j-2<1)&&(i-2<1||j-1<1)&&(i-1<1||j+2>m)&&(i-2<1||j+1>m)
	&&(i+1>n||j-2<1)&&(i+2>n||j-1<1)&&(i+1>n||j+2>m)&&(i+2>n||j+1>m))
		return true;
	return false;
}
void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(check(i,j)){
				cout<<i<<" "<<j<<endl;
				return;
			}
		} 
	}
	cout<<1<<' '<<1<<endl;
	
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

 

B题:动规的前奏,大意是有两个数组d和a,定义d[i] = | a[i]-a[i-1] |,对于i>=2,规定d[1] = a[1]。

给出d数组,如果a数组唯一,那么输出它,否则输出-1.

思路:我们可以很容易的想到,对于任意一个a[i],我们总能通过a[i-1]+d[i]来得到,这并不难。如果这个数存在一种情况,

这个ai比后一个di要大,那么下一次的构造一定能够构造一个比ai大的和比ai小的来解决。(当然,这里的前提是d[i+1]不为0时,且di不是最后构造)
如果和后一个di相等呢,我们总能通过0来构造,但是这个前提是di不为0。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int nn =  110;
int a[nn],b[nn];
void solve()
{
	memset(a,0,sizeof a);
	memset(b,0,sizeof b);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	b[1] = a[1];
	for(int i=1;i<=n;i++){
		b[i] = b[i-1] + a[i];
		if(i!=n&&b[i]>a[i+1]&&a[i+1]!=0||b[i]==a[i+1]&&b[i]!=0){
			cout<<-1<<endl;
			return;
		}
	}
	for(int i=1;i<=n;i++)
		cout<<b[i]<<' ';
	cout<<endl;
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

 

C题:大意是有n张牌,n为偶数,a和b两个人每人n/2张牌,牌大小为1-n。游戏规则,a先出牌,b必须出一个刚好比a大的现有的牌,然后依次来回。
如果最后压不住了,那么另一方获胜,如果最后两人手里都没有牌,那么平局。

思路:首先可以通过样例发现,平局只有1情况。

然后就是A胜。情况有a手里有最大牌,a手里有最大的四张牌中的三张,a手里有第二和第三大的牌。

由此dp推导

B胜就是总和减去A胜减去1.

官方解法有些复杂,用的三维dp,表示a  b  和三个状态

code:

 

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

int c[N][N];
int f[N];

void solve()
{
    int n;
    cin >> n;

    //从i中选j个
    for (int i = 0; i < N; i++){
        for (int j = 0; j <= i; j++){
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }

    f[2] = 1;
    f[4] = 3;
    for (int i = 6; i <= n; i += 2){
        f[i] = ((c[i - 1][i / 2 - 1] + c[i - 4][i / 2 - 1]) % mod + f[i - 4]) % mod;
    }
	
	//每次都要取模,不然就会溢出
    cout << f[n] << ' ' << (c[n][n / 2] - f[n] - 1 + mod) % mod << ' ' << 1 << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }

    return 0;
}