头像

周赛二题必超时




离线:2小时前


最近来访(46)
用户头像
RyanMoriarty
用户头像
lee_16
用户头像
sanctuary_
用户头像
limie
用户头像
yxc
用户头像
郑若辰
用户头像
万花筒写轮眼2号
用户头像
a睿
用户头像
我要出去乱说
用户头像
bobo2010
用户头像
木棉觉
用户头像
zyl666
用户头像
该用户被封禁
用户头像
风竹斜街
用户头像
用户头像
看不穿的宇宙
用户头像
Acanuva
用户头像
龚子昂
用户头像
撒旦
用户头像
silly_xl


Nim游戏的解法

1. 什么是Nim游戏

Nim游戏一般来说是这样的:有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。

2.如何来解决这个问题

首先这题看看能不能分解或者再简化一下,我们先来看看这样一个问题:有一堆石子,这堆石子的数量是有限的,合法的移动是“拿走若干颗(不能不拿)”,如果轮到某个人时石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。这个题目就简单多了,先手必胜,因为只要先手把所有石子拿走就可以了。如果不这么做,只拿走一部分的石子,那对手只要把剩下的全拿走就胜了。在这里为了后面方便讨论,先定义两种状态:1:胜态:当前回合至少有一个选择可以使游戏结束的状态,或者当前回合至少有一个选择可以使游戏变成败态的状态。2:败态:当前回合没任何选择可以使游戏变成胜态的状态。所以先可以看出败态的下一步必然是胜态,而胜态的下步可能是败态,也可能是胜态。

若拿走的石子数不加限制那很好想,先手拿走就好了,变化简单,用大脑就能算出来。但若拿走的石子有限制(比如只能拿一到四个石子,或只能拿两个或五个石子),而石子数又比较大,那大脑就不好想了,需要用电脑来做,首先,我们设一个SG数来记录每一个状态点(就是当前还剩下的石子数)是胜态还是败态,然后把每一种可能的走法做一个遍历,就可以知道每一个状态点是赢是输了。求SG数的模板如下:

//求SG数的模板
int sg(int x)
{
    if (f[x] != -1) return f[x];//每个点的状态是唯一的,要么赢要求输,所以若之前算过就可以偷懒不用再算一遍了。

    unordered_set<int> S;//定义一个临时用的篮子来暂时装一下下一步走向胜态或败态的各种可能性
    for (int i = 0; i < m; i ++ )
    {
        int sum = s[i];//把s里的每一种操作可能都一一拿出来试一下
        if (x >= sum) S.insert(sg(x - sum));//把每一种操作一路走到底,用递归的方式把每一个节点的胜败态记录一下。
    }

    for (int i = 0; ; i ++ )
        if (!S.count(i))
            return f[x] = i;//从0开始由小到大来数,返回篮子里第一个没出现的数,就是sg数,若sg数等于0那说明要么篮子是空的(也就是败态)或者下一步的各种操作的sg数都不为0(也就是当前回合是没任何选择可以使游戏变成胜态的状态,也就是败态)。若sg不等于0,说明是胜态。
}

3.问题的延申

到了这个时候,游戏可以再复杂一些了,比如有两堆石子,每堆石子的数量是有限的,合法的移动是“拿走若干颗(不能不拿)”,如果轮到某个人时,所有石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。这个时候就不能先手把一堆全拿走了,因为后手把另一堆也全拿走,先手就输了。用之前的胜态败态的定义来分析一下,我们发现有三种情况,1、两个败态的组合。两个败态的组合还是败态。从后手玩家的角度来看,先手玩家的行动只能将两个败态中的一个改变为胜态,于是后手玩家可以再将这个胜态变成败态,从而将两个败态的组合抛回给先手玩家。由于终局状态为败态,最终先手玩家必将面对两个终局状态组成的败态,故后手必胜。2、一胜一败两个状态的组合。胜态与败态的组合还是胜态——先手玩家只要把胜态变成败态,就可以把两个败态组合成的败态抛给后手玩家了。3、两个胜态的组合。这种组合就比较复杂了:先手玩家不应把其中一个胜态变成败态,因为这样会把一胜一败两个状态组合成的胜态留给对方。因此,先手玩家应当把其中一个胜态变成一个新的胜态。后手玩家面对新的胜态+胜态的组合,应当采取相同的策略。前面两种情况都好说,主要的问题在第三种情况,因为这是个有限回合的游戏,胜态+胜态的情况不能一直维持下去,那就有必要研究一下哪一方会撑不下去。

为了方便说明,这时再引入一个胜态级数的概念,所谓胜态级数, 就是指从当前胜态走到败态,若双方都尽可能慢的走到败态,最多还能走多少回合,就称当前状态为几级胜态。还是举一堆石子的例子,假如有两个石子,那先手拿走两个,那就直接给对手一个败态,若只拿一个,那就留给对手一个胜态,对手再拿走一个,场面就走到了败态,所以我们称两个石子时的那个情况为二级胜态。回头一看,我们惊奇的发现胜态级数竟然和SG数一样(SG数本来也就是为了求这个级数–!)。如此,结合之上的讨论,我们可以得每一堆石子的胜态级数也就是SG数,我们想要给对手一个败态,只要把各堆石子之间的异或值变成0就行,即如第一堆石子的SG数为SG~1~$\ldots$,那只要SG~1~$\bigoplus$SG~2~$\bigoplus$$\ldots$$\bigoplus$SG~n~=0即可达到必胜的状态。(下面结论与证明的部分直接抄了qiaoxinwei同学的题解)

结论

假设n堆石子,石子数目分别是a1,a2,…,an,如果a1⊕a2⊕…⊕an≠0,先手必胜;否则先手必败。

证明

操作到最后时,每堆石子数都是0,0⊕0⊕…0=0
在操作过程中,如果 a1⊕a2⊕…⊕an=x≠0。那么玩家必然可以通过拿走某一堆若干个石子将异或结果变为0。
证明:不妨设x的二进制表示中最高一位1在第k位,那么在a1,a2,…,an中,必然有一个数ai,它的第k为时1,且ai⊕x<ai,那么从第i堆石子中拿走(ai−ai⊕x)个石子,第i堆石子还剩ai−(ai−ai⊕x)=ai⊕x,此时 a1⊕a2⊕…⊕ai⊕x⊕…⊕an=x⊕x=0 。
在操作过程中,如果a1⊕a2⊕…⊕an=0,那么无论玩家怎么拿,必然会导致最终异或结果不为0。
反证法:假设玩家从第ii堆石子拿走若干个,结果仍是0。不妨设还剩下a′个,因为不能不拿,所以0≤a′<ai,且a1⊕a2⊕…⊕a′⊕…⊕an=0。那么(a1⊕a2⊕…⊕ai⊕…an)⊕(a1⊕a2⊕…⊕a′⊕…⊕an)=ai⊕a′=0,则 ai=a′,与假设0≤a′<ai矛盾。

4.总结

通过以上的讨论可以发现,Nim问题最终都可以化为求每一堆的SG数,再把各SG数异或运算一下就可以得到结论。其中用记忆化搜索的方式遍历每一种操作选择可得每个状态点是胜态还是败态,用胜态级数(SG数)来表示胜态与胜态之间的操作选择,用各独立问题的SG数异或来取得整个问题是胜态还是败态。
这里级数的运用,是把具体操作抽象到了状态之间的变化操作,更容易发现新的性质。选择异或运算,应该是考虑到异或运算的法则和胜败态之间变化类似的原因。




题目描述

n−皇后问题是指将n个皇后放在n×n的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。

. . . Q . . . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . Q
. Q . . . . . .
. . . . Q . . .
Q . . . . . . .
. . . . . Q . .
现在给定整数 n,请你输出所有的满足条件的棋子摆法。

输入格式

共一行,包含整数n。

输出格式

每个解决方案占n行,每行输出一个长度为n的字符串,用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后,输出一个空行。

注意:行末不能有多余空格。

输出方案的顺序任意,只要不重复且没有遗漏即可。

数据范围

1≤n≤9

样例

输入样例:

4

输出样例:

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

算法1 (骗分) $O(1)$

看到数据范围的我产生了不好的想法。

可是为了写这段c++代码耗了我一整天的时间……

所以破例用了一次python3。代码有2552行,就不写了。

算法2 (dfs)

dfs(深度优先搜索)是对图进行搜索的算法,目的是从起点开始搜索直到到达指定顶点(终点)。dfs会沿着一条路径不断往下搜索直到不能再继续为止,然后再折返,开始搜索下一条候补路径。

此处把棋盘的状态看作是图中的节点。

模拟一下样例。
QQ图片20211126121045.jpg

算法2 c++代码加解释

#include <iostream>
using namespace std;
const int N=10;
int n;
bool col[N],dg[N],udg[N];//列,对角,反对角。
char q[N][N];
void dfs(int u){
    if(u==n){//全填完了,输出。
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)cout<<q[i][j];
            cout<<endl;
        }
        cout<<endl;
        return;
    }
    for(int i=0;i<n;i++)
        if(!col[i]&&!dg[i+u]&&!udg[i-u+n]){
            col[i]=dg[i+u]=udg[i-u+n]=true;
            q[u][i]='Q';//放皇后。
            dfs(u+1);//往下搜
            col[i]=dg[i+u]=udg[i-u+n]=false;
            q[u][i]='.';//还原现场。
        }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)q[i][j]='.';
    dfs(0);/从第一层搜起。
}



#include <iostream>
#include <cstring>
using namespace std;
const int N=1005,M=505,S=105;
int n,m,num,w[S],v[S],f[N][M];
int main()
{
    memset(f,0xcf,sizeof f);
    cin>>n>>m>>num;
    for(int i=1;i<=num;i++)cin>>w[i]>>v[i];
    f[0][0]=0;
    for(int i=1;i<=num;i++)
        for(int j=n;j>=w[i];j--) 
            for(int k=m;k>=v[i];k--)f[j][k]=max(f[j][k],f[j-w[i]][k-v[i]]+1);
    int res=-1,t;
    for(int j=0;j<=n;j++)
        for(int k=0;k<m;k++)
            if(f[j][k]>res||(res==f[j][k]&&k<t)){
                res=f[j][k];
                t=k;
            }
    cout<<res<<" "<<m-t;
    return 0;
}


活动打卡代码 AcWing 1024. 装箱问题

#include <iostream>
using namespace std;
const int N = 20010;
int n,m,f[N];
int main(){
    cin>>m>>n;
    for (int i = 0; i < n; i ++ ){
        int v;
        cin>>v;
        for(int j=m;j>=v;j--)f[j]=max(f[j],f[j-v]+v);
    }
    cout<<m-f[m];
    return 0;
}


活动打卡代码 AcWing 423. 采药

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m,f[N];
int main()
{
    cin>>m>>n;
    for (int i = 0; i < n; i ++ ){
        int v,w;
        cin >>v>>w;
        for(int j=m;j>=v;j--)f[j]=max(f[j],f[j-v]+w);
    }
    cout<<f[m];
    return 0;
}



题目描述

给定一个包含n个点(编号为1∼n)的无向图,初始时图中没有边。

现在要进行m个操作,操作共有三种:

C a b,在点a和点b之间连一条边,a和b可能相等;
Q1 a b,询问点a和点b是否在同一个连通块中,a和b可能相等;
Q2 a,询问点a所在连通块中点的数量;
输入格式

第一行输入整数n和m。

接下来m行,每行包含一个操作指令,指令为 C a b,Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b,如果a和b在同一个连通块中,则输出Yes,否则输出No。

对于每个询问指令 Q2 a,输出一个整数表示点a所在连通块中点的数量

每个结果占一行。

样例

输入样例:

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例:

Yes
2
3

并查集

这题是标准并查集模板(但还是讲一下吧)。

先把并查集看成一个家族,再分析一下三条指令。(我突然发现家族里没有母子关系,计算机世界真奇妙!)

C a b:认爹,直接将a结点的爸爸设为b,再让祖宗算人数。

Q1 a b:找祖宗,只需判断a和b是不是一个祖宗就行了,找祖宗时只需用每个人的爹往上找。

Q2 a:数人,在进行认爹时做完了,所以找到祖宗,问家里有多少人就行了。

C++ 代码加详解

#include<bits/stdc++.h>
using namespace std;
int n,m,father[100010],sum[100010];//sum是人数。
int find(int x){//找祖宗
    if(father[x]==x)return x;//遇到“我是我祖宗”的情况时,说明找到了。
    else return father[x]=find(father[x]);//继续找爸爸的祖宗。
}
void merge(int a,int b){
    int x=find(a),y=find(b);
    fa[x]=y;//把a的祖宗设成b的祖宗的儿子(a他祖宗你不要不服气)。
    sum[y]+=sum[x];//家族人数合并。
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        fa[i]=i;//“我是我祖宗”。
        sum[i]=1;//家族里只有一人。
    }
    while(m--){
        string op;//指令。
        int a;
        cin>>op>>a;
        if(op=="C"){
            int b;
            cin>>b;
            if(find(a)!=find(b))merge(a,b);//不是一个祖宗再认爹(否则你爹肯定扇你)。
        }
        else if(op=="Q1"){
            int b;
            cin>>b;
            cout<<(find(a)==find(b)?"Yes":"No")<<endl;//是一家的输出Yes,否则输出No。
        }
        else cout<<sum[find(a)]<<endl;//去祖宗那儿问人数。
    }   
    return 0;
}



题目描述

在给定的N个整数A1A2……AN中选出两个进行xor(异或)运算,得到的结果最大是多少?

输入格式

第一行输入一个整数N。

第二行输入N个整数A1~AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤10的5次方,
0≤Ai<2的31次方

样例

输入样例:

3
1 2 3

输出样例:

3

(Trie)

emm……总之在讲这个解法之前,我只想说这个算法真的太牛逼了(以至于这绝对不是我创造的)。
异或吗,就是把两个数的二进制进行“同0异1”。所以二进制差的越多,异或值越大。
所以就把所有二进制合并成一个31层的二叉树。最后分别求出每个数进行异或时可得到的最大值,在根据比较求出序列中的最大值。

举个例子:1 2 3。
首先画一棵树(最令人蛋疼的事情)。
(此处省略29层)
/ \
0 1
/ / \
1 0 1
再分别枚举每个数异或得到的最大值:
1:3(与2异或)
2:3(与1异或)
3:2(与1异或)
得到的值最大是3,答案是3。

C++ 代码附详解

#include <iostream>
using namespace std;
int n,idx,ans;//ans记答案。
int a[100010],so[3100010][2];//so表示某节点的分支。数组开那么大是因为int有32位。
void insert(int x){
    int p=0;//根。
    for(int i=30;i>=0;i--){
        int &s=so[p][x>>i&1];//用x>>i&1求二进制的该位(x>>i刨后面,&1刨前面)。
        if(!s)s=++idx;//没有这一个分支就自己开一个。
        p=s;//往下找。
    }
}
int search(int x){
    int p=0,res=0;
    for(int i=30;i>=0;i--){
        int s=x>>i&1;
        if(so[p][!s]){//二进制差越多,异或值越大。
            res+=1<<i;//加上2的i次方,也就是该二进制位表达的值。
            p=so[p][!s];//往二进制位不一样那边遍历。
        }
        else p=so[p][s];//往唯一的一边走(异或运算总不能半途而废吧)。
    }
    return res;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        insert(a[i]);//将这个数的二进制插入到树里。
    }
    for(int i=0;i<n;i++)ans=max(ans,search(a[i]));//求最大值。
    cout<<ans;
    return 0;
}



#include <iostream>
using namespace std;
const int N=3010;
int f[N][N],a[N],b[N],n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    for(int i=1;i<=n;i++){
        int maxn=1;
        for(int j=0;j<n;j++){
            f[i][j]=f[i-1][j];
            if(a[i]==b[j])f[i][j]=max(f[i][j],maxn);
            if(b[j]<a[i])maxn=max(maxn,f[i-1][j]+1);
        }
    }
    int res=0;
    for(int i=0;i<n;i++)res=max(res,f[n][i]);
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 187. 导弹防御系统

#include<iostream>
using namespace std;
const int N=55;
int a[N],ans,up[N],down[N],n;
void dfs(int u,int d,int t){
    if(u+d>=ans)return;
    if(t==n){
        if(u+d<ans)ans=u+d;
        return;
    }
    int i;
    for(i=1;i<=u;i++)
        if(up[i]<a[t])break;
    int temp=up[i];
    up[i]=a[t];
    dfs(max(u,i),d,t+1);
    up[i]=temp;
    for(i=1;i<=d;i++)
        if(down[i]>a[t])break;
    temp=down[i];
    down[i]=a[t];
    dfs(u,max(d,i),t+1);
    down[i]=temp;
}
int main(){
    while(cin>>n&&n!=0){
        ans=N;
        for(int i=0;i<n;i++)cin>>a[i];
        dfs(0,0,0);
        cout<<ans<<endl;
    }
    return 0;
}



题目描述

给定一个长度为n的整数数列,以及一个整数k,请用快速选择算法求出数列从小到大排序后的第k个数。

输入格式

第一行包含两个整数n和k。

第二行包含n个整数(所有整数均在1∼10的9次方范围内),表示整数数列。

输出格式

输出一个整数,表示数列的第k小数。

数据范围

1≤n≤100000,1≤k≤n

样例

输入样例:

5 3
2 4 1 5 3

输出样例:

3

算法1

(干就完了奥利给) $O(nlogn)$

此算法唯一的难点就是你要会写算法(或万能)头文件。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    cout<<a[m-1];
}


算法2

(快排) $O(nlogn)$

快排首先会在序列中选择一个基准值,然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别,再将其排列成以下形式。

【比基准值小的数】基准值【比基准值大的数】

接着,对两个“【】”中的数据进行排序之后,整体的排序便完成了。对“【】”里面的数据进行排序时同样也会使用快速排序。
(以上内容是抄的)

拿数据给大家演示一下:

2 4 1 5 3
基准值选1(中间值)。
1【2 4 5 3】
emm……这种情况是挺尴尬的。接下来,基准值选4。
1【2 3】4 5
右边的区域因为只有5,所以不用继续排序。接下来,基准值选2。
1 2 3 4 5
排序完成。

C++ 代码加详解

#include <iostream>
using namespace std;
const int N=100010;
void qs(int q[],int l,int r){
    if(l>=r)return;//不到两个元素,无需排序。
    int i=l-1,j=r+1,x=q[(l+r)>>1];
    do{
        do i++;while(q[i]<x);//遇到比基准值大的靠前的数,
        do j--;while(q[j]>x);//遇到比基准值小的靠后的数,
        if(i<j)swap(q[i],q[j]);//而且没有遍历过头就交换两个数。
    }while(i<j);
    qs(q,l,j);//【比基准值小的数】排序
    qs(q,j+1,r);//【比基准值大的数】排序
}
int main(){
    int n,k,q[N];
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>q[i];
    qs(q,0,n-1);
    cout<<q[k-1];
    return 0;
}