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代码

#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代码

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