ACM-ICPC 2018 徐州赛区网络预赛

ACM-ICPC 2018 徐州赛区网络预赛

A. Hard to prepare

题意

$n$个人围成环,每个人可以选择$[0,2^k-1]$中的一个数字,要求相邻两人不能同或为0。

题解

递归。

可以YY出,第一个人有$2^k$种选择,之后第2到第$n-1$个人有$2^k-1$种选择,最后一个人可能可以选$2^k-2$,也可能可以选$2^k-1$。这取决于倒数第二个人是否跟第一个人选一样的。这时候我们就可以加上如果第一个人和倒数第二个人选择相同,并且,最后一个人多选了那$2^k-1-(2^k-2)$种,那么他们三个点变成一个点来选择了。

AC代码

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
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,k;
const ll mod = 1e9+7;
ll pow3(ll a,ll b){
ll ans = 1;
while(b){
if(b&1) ans = ans*a%mod;
a = a*a%mod;
b>>=1;
}
return ans;
}
ll k2,kk2,kk1;
ll solve(int n,int k){
if(k==1) return 2;
if(n==1) return k2;
if(n==2) return k2*kk1%mod;
ll res = (k2*kk2%mod)*pow3(kk1,n-2)%mod;
res = (res+solve(n-2,k))%mod;
return res;
}
int main(){
#ifdef LOCAL
freopen("4.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
k2 = pow3(2,k);
kk1 = (k2-1+mod)%mod;
kk2 = (k2-2+mod)%mod;
printf("%lld\n",solve(n,k));
}

return 0;
}

B.BE,GE or NE

题意

两个人玩游戏,给出$[0,3]$个选项和一个$m$初始值,两个人依次选择,有以下三种选择

  • 选择将值$+a$
  • 选择将值$-b$
  • 选择将值倒过来 $m=-m$

两个人一个想将值变大,一个想让值变小,两个人都知晓所有情况和选项,在最优情况下,问谁赢。

题解

博弈论dp+记忆化搜索

因为数据量很小,范围也在200之间,所以记忆化状态回复的很多。

$dp[pos][val]$表示在pos位置数值是val,之后dp代表的是最优可以赢还是输还是平,分别用2,1,0代表。

之后对于边界值要处理一下。数组存不了负值,我们统一加100处理。


妈的。我看到这个以为是纯博弈论直接人傻了。之后想着能不能记忆化搜索,但是看到$n=1000$还以为他喵的会爆,但是这道题的情况限制在范围$-100到100$,所以情况很少。所以可以直接记忆化,不过对于答案的选择和状态转移我可能还是不会太轻松地做出来,带int的dfs我还是不怎么熟悉,这按道理应该是算是博弈论dp了。从最优状态转移到最优状态。

AC代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
int n,m,k,l;
const int maxn = 1e3 + 10;
int a[maxn],b[maxn],c[maxn];
int dp[maxn][220];
// op
int dfs(int pos,int val){
if(pos == n){
if(val >= k){
return 2;
}else if(val > l){
return 1;
}else{
return 0;
}
}
if(dp[pos][val] != -1) return dp[pos][val];
if(pos%2==0){
int res = 0;
int mmin = min(200,val+a[pos]);
int mmax = max(0,val-b[pos]);
if(a[pos]) res = max(res,dfs(pos+1,mmin));
if(b[pos]) res = max(res,dfs(pos+1,mmax));
if(c[pos]) res = max(res,dfs(pos+1,200-val));
return dp[pos][val] = res;
}else{
int res = 2;
int mmin = min(200,val+a[pos]);
int mmax = max(0,val-b[pos]);
if(a[pos]) res = min(res,dfs(pos+1,mmin));
if(b[pos]) res = min(res,dfs(pos+1,mmax));
if(c[pos]) res = min(res,dfs(pos+1,200-val));
return dp[pos][val] = res;
}
}
int main(){
#ifdef LOCAL
freopen("b.in","r",stdin);
#endif // LOCAL
rep(i,0,maxn) rep(j,0,220) dp[i][j] = -1;
scanf("%d%d%d%d",&n,&m,&k,&l);
l += 100; k += 100; m += 100;
rep(i,0,n){
scanf("%d%d%d",a+i,b+i,c+i);
}
int op = dfs(0,m);
if(op==2) puts("Good Ending");
else if(op==1) puts("Normal Ending");
else puts("Bad Ending");
return 0;
}