8.20 并不是一个好收尾的杭电10
题意
给定 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();
}
题意
给定 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();
}
题意
有 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();
}