牛客算法周周练6 部分题解

一.闲话

这次比赛挺简单的，我就来写下其中有意思的题目的题解吧。。。（罚时太高，排名直降，我太菜了qwq）

二.题解

C.Game

这道题明显是一道博弈论问题，那么，就需要搞sg函数之类的。。。

算了吧！/xk

我们直接暴力dp吧。。。

我们设dp[i]=0/1表示有i个石块的情况是必输/胜

那么，考虑转移。

我们每次选i的一个非1约数j,那么，就被分成了j和i/j两部分

考虑两部分的状态的值，有：

1.dp[j]=0,dp[i/j]=0

那么，我们模拟下，我们取拿j的话，就必输，然后再作为先手拿i/j，也必输，所以，先做j和i/j的必输，不过，先手已经将i分成了j和i/j，那么，就轮到后手作为先手拿了，于是先手必胜

2.dp[j]=0,dp[i/j]=1 or dp[j]=1,dp[i/j]=0

同理分析，即可得到，这个状态下先手必输

3.dp[j]=1,dp[i/j]=1

这个就是先手必胜

那么，我们就有如下结论：

如果dp[j]==dp[i/j],那么先手必胜，否则先手必输

因为，先手肯定要让自己胜利，所以先手如果存在一种转移可以使得先手必胜，那么先手就会如此转移，否则先手就必输了

故而，转移方程为：

dp[i]|=(dp[j]^dp[i/j]^1)【j|i】

那么，我们对于每个i，枚举其约数即可~

代码：

#include<bits/stdc++.h>
using namespace std;
bool dp[100000];
int main(){
    int n;
    scanf("%d",&n);
    dp[1]=dp[2]=dp[3]=0;
    for(int i=4;i<=n;++i){
        for(int j=2;j<=sqrt(i);++j){
            if(i%j)continue;
            dp[i]|=((dp[j]^dp[i/j])^1);
        }
    }
    if(!dp[n]){
        puts("Nancy");
    }else{
        puts("Johnson");
    }
    return 0;
}

update:

好吧，没仔细想直接上dp去了qwq，我们每次把一个数拆成它两个约数相乘，那么，不难证明，总的拆分次数即为分解质因数后所有质因子的指数之和-1（相当于把一个集合分成两个小集合，直到所有集合都只有一个元素位置（每个集合的元素都是质数，该集合代表的数即为所有元素之积））

总的操作次数确定后，谁胜谁负就可以根据操作次数的奇偶性判断了qwq

update2:

sg函数版本：
代码：

#include<bits/stdc++.h>
using namespace std;
int sg[100000];
int vis[100000];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=4;i<=n;++i){
        for(int j=2;j<=sqrt(i);++j){
            if(i%j==0){
                vis[(sg[j]^sg[i/j])]=i;//后继是两个状态，总局面即为两状态的异或值
            }
        }
        int now=0;
        while(vis[now]==i){//找mex的值
            ++now;
        }
        sg[i]=now;
    }
    if(sg[n]){//先手必胜
        puts("Johnson");
    }else{//先手必输
        puts("Nancy");
    }
    return 0;
}

E.签到题

读完题，看程序，大概内容是：

给你若干个操作，有三种

一个是给区间加上1，一个是给区间减去1，一个是查询整个数列中不为1的点的个数，而且保证，不会同时给一个相同区间加1，不会给没有加过1的区间减1

emmm，理解完后，看数据范围，1e5，本来以为是个数据结构题，然后码了一部分后，读到一句话。。。

保证数据随机

我：嘿嘿。。。

随手算了一下期望，每次操作区间的长度大概是在 $[\frac{n}{4}]$ 左右（不知道算对没qwq）

然后一算，期望操作次数为 $(1.67*10^9)$ 次(假设三个操作出现概率相同)，又因为基本是跑不到上限的，所以打了个暴力，然后过啦，哈哈

我是暴力做的修改，如果修改差分，询问暴力的话，期望操作次数会小一倍，2333

吐槽：出题人给的代码真丑（逃

代码：

 #include <algorithm>
 #include <iostream>
 #include <cstring>
 #include <climits>
 #include <cstdio>
 #include <vector>
 #include <cstdlib>
 #include <ctime>
 #include <cmath>
 #include <queue>
 #include <stack>
 #include <map>
 #include <set>
 #define fi first
 #define lc (x<<1)
 #define se second
 #define U unsigned
 #define rc (x<<1|1)
 #define Re register
 #define LL long long
 #define MP std::make_pair
 #define CLR(i,a) memset(i,a,sizeof(i))
 #define FOR(i,a,b) for(Re int i = a;i <= b;++i)
 #define ROF(i,a,b) for(Re int i = a;i >= b;--i)
 #define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
 #define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
 #define DEBUG(x) std::cerr << #x << '=' << x << std::endl
 const int MAXN = 1000000+5;
 int N,maxL;
 std::set<std::pair<int,int> > L;
int tim[MAXN];
 int main(){
     scanf("%d%d",&N,&maxL);
     ++maxL;
     int res=0;
     while(N--){
         int opt,x,y;
         scanf("%d%d%d",&opt,&x,&y);++x,++y;
         if(opt == 1){
             if(L.find(MP(x,y)) != L.end()) continue;
             L.insert(MP(x,y));
             for(int i=x;i<=y;++i){
                 ++tim[i];res+=(tim[i]==1);
             }
         }
         if(opt == 2){
             if(L.find(MP(x,y)) == L.end()) continue;
             L.erase(MP(x,y));
             for(int i=x;i<=y;++i){
                 --tim[i];res-=(tim[i]==0);
             }
         }
         if(opt == 3){
             printf("%d\n",res);
         }
     }
     return 0;
 }