https://ac.nowcoder.com/acm/contest/37160#question

anti-Nim游戏（反Nim游戏/反尼姆博弈问题）

定义
游戏规则与Nim类似，只是最后把石子取完的人输。

结论
先手必胜的条件为
①：所有堆的石子数均=1，且有偶数堆。
②：至少有一个堆的石子数>1，且石子堆的异或和≠0。

A-Alice and Bob（反尼姆博弈+分解质因数）

题目大意：Alice和Bob正在玩一个游戏，就是给定一个n，每次都需要整除以a^k(a为质数，k为正整数)
Alice先手，最先变成1的人输
问谁赢了？

示例1
输入
2
输出
Bob win

示例2
输入
12
输出
Alice win

这道题目的思考方向是分解质因数+反尼姆博弈。一个数每次都可以整除质数的倍数，那么我们就可以把它分成众多质因数，每一个相同的质因数划在同一堆，这样就可以看作是每一对的个数.
比如12=2^2 * 3^1。我们就可以分解出这样的一些石子 2 1，每次都从这里面去至少1表示除以某个质数的倍数。
谁最后取完，那个人就输了。

尼姆博弈：

只有一堆石子的时候，必然输；
a1 ^ a2 …… ^ an=0先手必败，否则先手必胜
https://www.cnblogs.com/Vivian-0918/p/16585990.html

A题正解：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const LL N=200200,M=2002;
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        LL sum=0,flag=0;
        //分解质因数
        for(LL i=2;i<=n/i;i++)
        {
            if(n%i==0)
            {
                int s=0;//记录个数
                while(n%i==0) s++,n/=i;
                if(s>1) flag=1;
                sum^=s;
            }
        }
        if(n>1) sum^=1;
        //反尼姆博弈的先手必胜条件有两个
        //异或和为0, 所有数等于 1
        //异或和不为0 ，至少一个数大于1
        if((!flag&&!sum)||(flag&&sum)) cout<<"Alice win"<<endl;
        else cout<<"Bob win"<<endl;
    }
    return 0;
}

B-打对子（签到/思维）

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<deque>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=200200;
const int M=5002;
const int mod=998244353;
struct node
{
    int x;
    int y;
}a[N];
int f[M][M];
LL mp[N];
int b[N];
bool vis[N];
int dx[]={-1,0,0,1},dy[]={0,1,-1,0};
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        map<char,int> mp;
        int sums=0;
        for(int i=0;i<s.size();i++)
        {
            mp[s[i]]++;
            if(mp[s[i]]==2)
            {
                sums++;
                mp[s[i]]=0;
            }
        }
        sums=n-sums*2;
        string c;
        cin>>c;
        map<char,int> pm;
        int sumc=0;
        for(int i=0;i<c.size();i++)
        {
            pm[c[i]]++;
            if(pm[c[i]]==2)
            {
                sumc++;
                pm[c[i]]=0;
            }
        }
        sumc=n-sumc*2;
        cout<<sums<<endl;
        if(sums<sumc) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

D-纪念品领取（签到/思维）

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<deque>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=200200;
const int M=5002;
const int mod=998244353;
struct node
{
    int x;
    int y;
}a[N];
int f[M][M];
LL mp[N];
int b[N];
bool vis[N];
int dx[]={-1,0,0,1},dy[]={0,1,-1,0};
bool cmp(node l,node r)
{
    return l.y<r.y;
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            a[i].x=i;
            a[i].y=i;
        }
        for(int i=n+1;i<=n+m;i++)
        {
            int t;
            cin>>t;
            a[t].y=i;
        }
        sort(a+1,a+1+n,cmp);
        vector<int> v;
        for(int i=1;i<=5;i++)
        {
            //cout<<a[i].x<<" "; 
            v.push_back(a[i].x);
        }
        sort(v.begin(),v.end());
        for(int i=0;i<v.size();i++)
            cout<<v[i]<<" ";
        cout<<endl;
    }
    return 0;
}

E-聚会（思维）

题目大意：
有一场聚会，每个人都有一个活跃度。
一个聚会的活跃度定义为这些人的活跃度组成的可重复数字集合的子集和组成的集合中未出现的最小正整数。
现在需要你求出这个聚会的活跃度的值。

输入
3
1 2 3
输出
7

根据代码内的解释模拟一下就能知道能跑到哪里了

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const LL N=200200,M=2002;
int a[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+1+n);
        //先进行排序，最大的能够排到总和＋1
        LL maxn=1;//默认达不到的最小值是1（空集的时候0是一定可以达到的）
        for(int i=1;i<=n;i++)
        {
            //如果这个数字都比最大的都还小的话，那么就可以用它加上前面的所有数，达成下一个最大的
            if(a[i]<=maxn) maxn+=a[i];
            else break;//不然的话就是只能停留在这个地方了
        }
        cout<<maxn<<endl;
    }
    return 0;
}

F-买车

Alice 在赶去和 Bob 玩游戏的路上遇到了一个问题，她开的车电不够了，然后她准备去再买一辆车。
不同的车电量也不一样，每换一辆车可以让她多走一段距离。
问她最少买多少辆车就可以开到目的地。Alice初始位置为0。
到达不了目的地的话就输出-1。

输入
10 3 1
1 3
3 7
6 2
输出
2

该题代码有待商榷

hack数据
10 7 1
1 2
1 3
3 1
4 2
6 2
7 1
8 2

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const LL N=2002000;
#define x first
#define y second
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
   // cin>>T;
    while(T--)
    {
        map<LL,LL> mp;
        LL n,m,t;
        cin>>n>>m>>t;
        for(int i=1;i<=m;i++)
        {
            LL a,b;
            cin>>a>>b;
            mp[a]=max(mp[a],a+b);//mp表示的是a能够到达a+b这个地方
        }
        //直接用mp，还省得去排序了
        //默认是从t出发的
        LL sum=0,ans=0;
        for(auto i:mp)
        {
            //cout<<i.x<<" "<<i.y<<endl;
            if(t>=n) break;//到达目的地了哦
            if(t<i.x)//开不到这里，需要买一辆车
            {
                sum++;
                t=ans;
                ans=0;
                //cout<<t<<" ";//4 10 2
            }
            if(t>=i.x)//开车都可以超过这个地方
            {
                ans=max(ans,i.y);
                //cout<<ans<<" "; 4 10 8
            }
        }
        if(t>=n) cout<<sum<<endl;
        else cout<<"-1"<<endl;
        mp.clear();
    }
    return 0;
}

K-糟糕的一天(签到)

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<deque>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=200200;
const int M=5002;
const int mod=998244353;
int a[N];
int f[M][M];
LL mp[N];
int b[N];
bool vis[N];
int dx[]={-1,0,0,1},dy[]={0,1,-1,0};
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int maxn=a[n];
        int sum=0;
        for(int i=n-1;i>=1;i--)
        {
            if(a[i]>=maxn) sum++;
            maxn=max(maxn,a[i]);
        }
        cout<<n-1-sum<<endl;
    }
    return 0;
}

原文地址：http://www.cnblogs.com/Vivian-0918/p/16630999.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性