比赛链接: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; }