学到好多

夕景昨日

题目描述

Shintaro 制作了 $n$ 个开关，每个开关的状态可被设置为 $+$ 或 $−$。

现在你有一个数列 $A=(a_1,⋯,a_n)$，和一个初始值为 $0$ 的变量 $v$ 。你可以自由地操纵开关，当第 $i$ 个开关被设置为 $+$ 状态时， $v$ 会加上 $a_i$ ，被设置为 $−$ 状态时， $v$ 会减去$ a_i$。

请你判断是否有两种及以上不同的方式操纵开关，使得最后得到的 $v$值相等。

数据范围

$ 20 \% :n≤10$

$ 100 \% :1≤n≤100000 \ , 0≤a_i≤500000$

解题思路

这题题意转化一下就是能否从$n$个数中随意挑出任意两个集合，使得集合中的数的和相同。

这题是死活都想不到，首先当$n$ 小于20（大概时20左右）时可以暴搜，大于时可以直接输出Yes。

那么为什么可以这么做呢？别急，我来说。

首先假设有$n$个值域大小为$W$ 的数，显然这$n$个数最多能构成$2^n$ 个互不相同的数，同时，这些数的范围为$[0,n \times W]$，那么当$ n \times W < 2^n $时，一定满足不了构成$2^n$ 个不同的数这个条件，因为最大的数为$n \times W$ 而每个数都不相等的话最大的数至少为$2^n$（不怎么准确，意会一下）。所以可以这么判断。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e5+10;
int n,a[N];
bool v1[N];
bool fl;;
map<long long,long long>v;

void dfs(int x,int res){
    if(x==n+1){
//        cout<<res<<'\n';
        if(v.count(res)){
            fl=1;
        }
        v[res]=1;
        return;
    }
    dfs(x+1,res+a[x]);
    if(fl) return;
    dfs(x+1,res-a[x]);
    if(fl) return;
}

signed main(){
     srand(time(0));
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    if(n<=20){
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        dfs(1,0);
        cout<<(fl?"Yes\n":"No\n");
        return 0;
    }
    else{
        cout<<"Yes\n";
    }
}

透明答案

题目描述

Ayano 和 Bob 在玩简单的取石子游戏。最初有 $n$ 堆石子，每堆有 $2$ 块。

Ayano 和 Bob 轮流取石子（从 Ayano 开始）。每一次取石子时当前玩家可以
任选一堆，如果还剩下 $k$ 块石子，则可以从这堆中取出 $1$ 到 $k$ 之间的任意数量的
石子。

此外，每 $3$ 回合他们会添加一堆石子（含 $2$ 块石子）。换句话说，在第 $t$ 次
操作（两个人操作的总次数）之后，如果 $t$ 可以被 $3$ 整除，则添加一堆 $2$ 块石子
的石子堆。
（即使在第 $t$ 次操作中取完了所有石子，如果 $t$ 可被 $3$ 整除，也会添加新石
子堆并继续游戏。）

双方都采取最优策略，无法操作的玩家输掉游戏。请你判断哪个玩家获胜。

解题思路

显然的博弈论，不是很会系统性的什么SG函数，在我的印象里博弈论就是打表找规律，这一题由于数据范围比较小，$n \leq 1000$ ，所以直接dfs也可以，规律为当且仅当$n \% 3 =2$ 时Bob获胜。规律较为简单，这里只放dfs的代码。

dfs的大致思路，设x为剩下x堆个数为$2$的石子，y为剩下y堆个数为$3$的石子，$t$为目前进行到第几回合（$\% 3$之后，用来进行石子的添加）。

#include <bits/stdc++.h>

using namespace std;

const int N=2e3+10;

int dp[N][N][3];

bool dfs(int x,int y,int t){
    // cout<<x<<' '<<y<<' '<<t<<' '<<'\n';
    // h%=2;
    if(t==3){
        x+=1;
        t=0;
    }
    if(~dp[x][y][t]) return dp[x][y][t];
    if(!x&&!y){
        return 1;
    }
    if(~dp[x][y][t]) return dp[x][y][t];
    if(x&&dfs(x-1,y,t+1)) dp[x][y][t]=0;
    if(x&&dfs(x-1,y+1,t+1)) dp[x][y][t]=0;
    if(y&&dfs(x,y-1,t+1)) dp[x][y][t]=0;
    if(dp[x][y][t]==-1)dp[x][y][t]=1;
    return dp[x][y][t];
}
int n;
int main(){
    memset(dp,-1,sizeof dp);
    // freopen("2.out","w",stdout);
    dp[1][0][0]=0;
    cin>>n;
    if(!dfs(n,0,0)){
        cout<<"Ayano\n";
    }
    else cout<<"Bob\n";
}

界外科学

题目描述

ENE 是一位电脑少女，这天她在帮 Shintaro 网上购物。网店一共有 $n$ 件物品，第 $i$ 件物品有 $a_i$ 的价格，并且购买这件物品会给 Shintaro 带来 $b_i$ 的满足度，不同的物品获得的满足度会累加。

Shintaro 最多只能支付 $m$ 元。由于他资金有限，ENE 黑入了网店的支付系统。在她操作之后，总价格的计算方式是将所有物品的价格给 xor（异或运算）起来。

如 Shintaro 现在买了价格为 $1$、$2$、$4$、$7$ 的四件物品，总价格为 $1$⊕$2$⊕$4$⊕$7$=$0$。

Shintaro 现在想知道在足够支付所买的物品的前提下，他最多能获得多少满足度。

数据范围

$30 \% :n≤5$
$50 \% :n≤20$
另外 $20 \% :1≤m,a_i≤100$
$100 \% :1≤n≤36,1≤m,a_i,|b_i|≤10^9$

解题思路

这题看到数据范围自然而然的想到折半搜索，再国庆集训的时候复习过，那么就按照折半搜索的思想先dfs一下，唯一困难的是如何快速的求出满足体积的最大值，思路大致是用$01$字典树。不过看别人的代码的时候，看到的更多的是剪枝，只能说人类的智慧是无穷的，这里只放一下剪枝的代码。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N=40;

int a[N];
int n,m;
int b[N];
int sum[N];
int ans;

void dfs(int x,int v,int w){
    if(x==n+1){
        if(v<=m)ans=max(ans,w);
        return;
    }
    if(w+sum[x]<=ans){
        return;
    }
    dfs(x+1,v^a[x],w+b[x]);
    dfs(x+1,v,w);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=n;i;i--){
        sum[i]=max(sum[i+1],sum[i+1]+b[i]);
    }
    dfs(1,0,0);
    cout<<ans<<'\n';
}

第四道还是不会捏。