• 欢迎光临~

2022“杭电杯”中国大学生算法设计超级联赛(1)

开发技术 开发技术 2022-07-19 次浏览

比赛链接

2022“杭电杯”中国大学生算法设计超级联赛(1)

7149. Alice and Bob

(a_i)(i)((0leq ileq n)),(Alice) 每次可以将这些数划分为两个集合,(Bob) 每次可以删除一个集合,同时另外一个集合所有数减一。如果任何时候存在 (0)(Alice) 胜,否则 (Bob)

解题思路

博弈论

需要对 (Alice) 构造一种必胜策略,考虑将 (a_i)(i) 平分,即每次平分进两个集合,无论 (Bob) 如何选择,而由于每次平分后另外一个集合所有数减一,相当于将 (i) 减一,逆序处理所有的 (a_i),累计所有贡献,只要判断最后轮次的时候是否还存在数即可,因为划分集合后选择权在 (Bob) 手上,如果 (Alice) 不采取平分的策略,(Bob) 一定会删除对自己最有利的集合,而如果采取平分策略,即主动权掌握在 (Alice) 手上,无论 (Bob) 如何操作,其结果都是一定的。另一种理解:平分策略的任一子集是非平分策略的两个子集的中和,如果采取非平分策略,(Bob) 可以删除使对 (Alice) 平分策略更差的子集,这样可能平分策略能获胜但有一步采取非平分策略结果却败了,故平分策略是最优策略

  • 时间复杂度:(O(n))

代码

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e6+5;
int a[N],n,t;
int main()
{
    help;
    for(read(t);t;t--)
    {
    	cin>>n;
	    for(int i=0;i<=n;i++)cin>>a[i];
	    for(int i=n;i>=1;i--)a[i-1]+=a[i]/2;
	    puts(a[0]?"Alice":"Bob");
    }
    return 0;
}
程序员灯塔
转载请注明原文链接:2022“杭电杯”中国大学生算法设计超级联赛(1)
喜欢 (0)