2020 Multi-University Training Contest 10

wenzhuan

发布于 2022-08-15 12:46:48

2660

发布于 2022-08-15 12:46:48

文章被收录于专栏：你会烧尽还是结冰你会烧尽还是结冰

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

1004-Permutation Counting

题意

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

代码

#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 胜利。

代码

#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 ，就这是第三简单？？？

代码

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度