首页 > 代码库 > BestCoder Round #90

BestCoder Round #90

  考完6级(6级GG),回到宿舍就休息了,但脑袋不断回想着(农业咋翻译,听力没听懂,阅读没时间做……),然后突然想起了今晚BC,冲进赛场,嗯……还有10分钟呢,A题好像挺简单,敲一下吧(虽然B也不会做,但是我完成了一波漂亮的卖萌)

  A题套上题目的那个东西,暴力一发就可以

技术分享
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1000005
const int _K=50268147,_B=6082187,_P=100000007;
int _X;
inline int get_rand(int _l,int _r) {
    _X=((long long)_K*_X+_B)%_P;
    return _X%(_r-_l+1)+_l;
}
int n,m,k,seed,x,y;
bool isx[N],isy[N];
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%d%d",&n,&m,&k,&seed);
        _X=seed;
        int tn=n,tm=m;
        memset(isx,0,sizeof(isx));
        memset(isy,0,sizeof(isy));
        for (int i=1; i<=k; ++i) {
            x=get_rand(1,n);
            if(!isx[x]){
                isx[x] = 1;
                tn--;
            }
            y=get_rand(1,m);
            if(!isy[y]){
                isy[y] = 1;
                tm--;
            }
        }
        printf("%d %d\n",tn,tm);
    }
    return 0;
}
View Code

  B题我知道是个博弈,对于博弈我一般就是首先套学过的那几个,发现没套上去,然后想从必败态出发找一下sg函数,打个表出来,发现局面太多,再说以前的打表题我都没找出来规律,GG。

  赛后知道这是阶梯博弈,也是尼姆博弈的变形,某一层上的节点和看做某一个台阶上的石子个数,然后把奇数台阶异或一下就好。

  至于我为什么可以按下面的方式写,因为(a+b)^c = a^b^c,这样可以防止溢出

技术分享
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100005;
vector<int> vt[N];
int a[N],ans;
void dfs(int T,int deep){
    if(deep % 2 == 1){
        ans ^= a[T];
    }
    int len = vt[T].size();
    for(int i=0;i < len;i++){
        dfs(vt[T][i],deep+1);
    }
}
int main()
{
    int T,n,fa;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i = 0;i < n;i++) vt[i].clear();
        for(int i=1; i<n;i++){
            scanf("%d",&fa);
            vt[fa].push_back(i);
        }
        for(int i = 0;i < n;i++) {
            scanf("%d",&a[i]);
        }
        ans = 0;
        dfs(0,0);
        if(ans == 0) printf("lose\n");
        else printf("win\n");
    }
    return 0;
}
View Code

 

BestCoder Round #90