daily 2

2023/3/28 daily

CF 455A

常规DP，首先不要从n来想，一般针对于这个值的大小的转移方程多去值来想，因为这里是1e5，肯定可以去从值来想的

转移方程很简单

$dp[i]=max(dp[i-1],dp[i-2]+cnt[i]*i)$

void solve(){
  int n;
  cin>>n;
  vector<int>cnt(MAXN);
  vector<int>dp(cnt);
  for(int i=0;i<n;++i){
    int x;cin>>x;
    cnt[x]++;
  }
  dp[1]=cnt[1];
  dp[0]=0;
  for(int i=2;i<MAXN;++i){
    dp[i]=max(dp[i-1],dp[i-2]+cnt[i]*i);
  }
  cout<<dp[MAXN-1]<<'\n';
  return;
}

CF 455B

博弈+dp

先计算出当前有必败策略和必胜策略的节点，然后我们对于同时拥有必败和必胜策略的根节点，那么肯定是先手赢（随意控制）

如果根节点只有必胜策略，那么就是交替赢，算k的奇偶性就好了

如果根节点只有必败策略，那么一定输

int tree[MAXN<<2][26];
int is_leaf[MAXN<<2];
int cnt;
int win[MAXN<<2],lose[MAXN<<2];
void add(string s){
    int cur=0;
    for(int i=0;i<s.size();++i){
        is_leaf[cur]=0;
        int x=s[i]-'a';
        if(!tree[cur][x]){
            tree[cur][x]=++cnt;
        }
        cur=tree[cur][x];
    }
}
int dfs_win(int x){
    if(is_leaf[x]){
        return win[x]=0;
    }
    for(int i=0;i<26;++i){
        if(tree[x][i]&&!dfs_win(tree[x][i])){//有一个后继节点是没有必胜策略的，那么可以走到这个节点导致必胜
            return win[x]=1;
        }
    }
    return win[x]=0;
}
int dfs_lose(int x){
    if(is_leaf[x]){
        return lose[x]=1;
    }
    for(int i=0;i<26;++i){
        if(tree[x][i]&&!dfs_lose(tree[x][i])){//有一个节点没有必败策略，那么我们可以走到这个节点导致当前必败
            return lose[x]=1;
        }
    }
    return lose[x]=0;
}
void solve(){
  ll n,k;
  cin>>n>>k;
  memset(is_leaf,1,sizeof(is_leaf));
  for(int i=0;i<n;++i){
    string s;
    cin>>s;
    add(s);
  }
  dfs_win(0);
  dfs_lose(0);
  if(win[0]){
    if(lose[0]){
        cout<<"First\n";
    }else{
        cout<<(k&1?"First":"Second")<<'\n';
    }
  }else{
    cout<<"Second\n";
  }
  return;
}

写lc去了，这几天面试太鸡吧多了

LOADING

daily 2