2020 Multi-University Training Contest 10

8.20 并不是一个好收尾的杭电10

1004-Permutation Counting

题意

给定 $n-1$ 长度的 $01$ 关系数组,$0$ 和 $1$ 代表原数组中当前位和前一位的大小关系。问有多少种符合条件的原数组方案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
using namespace std;
const int mod = 1e9 + 7;
int dp[2][5005];
int solve(){
mst(dp,0); dp[0][1]=1;
int n,ff(0); sc(n); rep(i,1,n){
int x,res(0); sc(x); ff^=1; if(x){
dp[ff][1]=0; rep(j,1,i+1){
res+=dp[ff^1][j];
if(res>=mod) res-=mod;
dp[ff][j+1]=res;
}
} else{
dp[ff][i+1]=0; dep(j,i,1){
res+=dp[ff^1][j];
if(res>=mod) res-=mod;
dp[ff][j]=res;
}
}
} int ans(0); rep(i,1,n+1){
ans+=dp[ff][i];
if(ans>=mod) ans-=mod;
} return pf("%d\n",ans);
}
int main(){
int _; sc(_); while(_--) solve();
}

1010-Tic-Tac-Toe-Nim

题意

给定 $3*3$ 的石子堆,$a$ 、$b$ 两人轮流拿石子,每人的第一轮必须整堆拿走,其余任意。问先手有几种取法能保证必胜。

思路

枚举 $a$ 第一步取的点,再枚举 $b$ 第一步能取的剩下 $4$ 个点。如果有 $b$ 能赢的状态就不计数。

最优局势到最后一定是除了三个横纵坐标各不相同的点为 $0$ 外其他全是 $1$ 。这时候再两步就一定走到结局。所以枚举 $a$ 、$b$ 初始点后,异或第三个能取到 $0$ 的点的值和其他点的值 $-1$ 。为 $0$ 的话 $b$ 胜利。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
using namespace std;
int p[5][5],q[5][5];
int cal(int a,int b,int c,int d){
int cnt(0); rep(i,1,4) rep(j,1,4){
if(i==a&&j==b||i==c&&j==d) continue;
if(i!=a&&i!=c&&j!=b&&j!=d){ cnt^=q[i][j]; continue; }
cnt^=q[i][j]-1;
} return cnt;
}
int solve(){
rep(i,1,4) rep(j,1,4) sc(p[i][j]),q[i][j]=p[i][j];
int ans(0); rep(i,1,4) rep(j,1,4){
q[i][j]=0; int ff(0);
rep(k,1,4) rep(l,1,4){
if(k==i||l==j) continue;
q[k][l]=0;
int t=cal(i,j,k,l);
ff+=(t>0);
q[k][l]=p[k][l];
} if(ff==4) ans++;
q[i][j]=p[i][j];
} return pf("%d\n",ans);
}
int main(){
int _; sc(_); while(_--) solve();
}

1011-Task Scheduler

题意

有 $n$ 个任务,每个任务需要 $t_i$ 个人完成。公司一共有 $m$ 个员工,其中有 $k$ 个掉线。随机安排在当前没任务的员工分配任务,随机到掉线的员工就重新分配直到分配完成。问如何安排任务顺序可以使分配次数的期望最少,如果有多个方案输出其中字典序最小的。

思路

特判 + $sort$ ,就这是第三简单???

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
using namespace std;
typedef pair<int,int> pii;
pii p[105];
int cmp(pii a,pii b){
return (a.first==b.first&&a.second<b.second)||a.first>b.first;
}
int solve(){
int n,m,k; sc(n); sc(m); sc(k);
rep(i,1,n+1) sc(p[i].first),p[i].second=i; sort(p+1,p+n+1,cmp);
if(!k){ rep(i,1,n+1) pf("%d%c",i," \n"[i==n]); return 0; }
rep(i,1,n+1) pf("%d%c",p[i].second," \n"[i==n]); return 0;
}
int main(){
int _; sc(_); while(_--) solve();
}