一.闲话

这次比赛挺简单的,我就来写下其中有意思的题目的题解吧。。。(罚时太高,排名直降,我太菜了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,本来以为是个数据结构题,然后码了一部分后,读到一句话。。。

保证数据随机

我:嘿嘿。。。

随手算了一下期望,每次操作区间的长度大概是在左右(不知道算对没qwq)

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

我是暴力做的修改,如果修改差分,询问暴力的话,期望操作次数会小一倍,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;
 }