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();
}