牛客小白月赛13

Problem A  小A的签到题

https://ac.nowcoder.com/acm/contest/549/A

C++版本一

题解：

C++版本二

题解：矩阵快速幂+斐波那契数列

参考文章：矩阵快速幂 斐波那契数列 斐波那契数列矩阵快速幂法

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
char str;
ll b[2][2];
ll a[2][2];
void Matrix(ll a[2][2],ll b[2][2]){
    ll c[2][2];
    memset(c,0,sizeof(c));
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                c[i][j]=c[i][j]+a[i][k]*b[k][j];
            }
        }
    }
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            a[i][j]=c[i][j];
        }
    }
}
void power(ll k){
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            a[i][j]=1;
            b[i][j]=1;
        }
    }
    a[0][0]=b[0][0]=0;
    while(k){
        if(k&1)Matrix(a,b);
        Matrix(b,b);
        k>>=1;
    }
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%lld",&n);
    power(n-1);
    printf("%lld\n",a[0][1]*a[0][1]-a[0][0]*a[0][0]-a[0][0]*a[0][1]);
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem B 小A的回文串

https://ac.nowcoder.com/acm/contest/549/B

题解：字符串 朴素 回文字符串

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str[N];
struct node{};
int check(int n,int pos){
    int len1=1;
    int x=pos-1,y=pos+1;
    while(x>=0&&y<2*n&&len1+2<=n&&str[x]==str[y]){
        x--;
        y++;
        len1+=2;
    }
    int len2=0;
    x=pos,y=pos+1;
    while(x>=0&&y<2*n&&len2+2<=n&&str[x]==str[y]){
        x--;
        y++;
        len2+=2;
    }
    return max(len1,len2);
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //scanf("%d",&n);
    cin>>str;
    int len=strlen(str);
    for(int i=0;i<len;i++){
        str[i+len]=str[i];
        ans=max(ans,check(len,i));
    }
    for(int i=len;i<2*len;i++){
        ans=max(ans,check(len,i));
    }
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem C 小A买彩票

https://ac.nowcoder.com/acm/contest/549/C

题解：背包问题 分数

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
ll dp[N][N];
char str;
ll gcd(ll a,ll b){
    //cout<<a<<" "<<b<<endl;
    if(b==0)
        return a;
    return gcd(b,a%b);
}
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    dp[1][1]=dp[1][2]=dp[1][3]=dp[1][4]=1;
    for(int i=2;i<=30;i++){
        for(int k=1;k<=4;k++){
            for(int j=i*4;j>=max(i,k);j--){
                dp[i][j]=dp[i][j]+dp[i-1][j-k];
            }
        }
    }
    while(~scanf("%d",&n)){
        if(n==0){
            cout<<"1/1"<<endl;
            continue;
        }
        sum=1;
        for(int i=1;i<=n;i++)sum*=4;
        ans=0;
        for(int i=3*n;i<=4*n;i++)
            ans+=dp[n][i];
        ll GCD=gcd(sum,ans);
        cout<<ans/GCD<<"/"<<sum/GCD<<endl;
    }

    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem D 小A的位运算

https://ac.nowcoder.com/acm/contest/549/D

题解：预处理了一下前缀和后缀，然后枚举那个不选的数就可以了。

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=5000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum|=a[i];
    }
    for(int i=n;i>=1;i--){
        sum|=a[i];
        if(ans<(sum|temp))
            ans=sum|temp;
        temp|=a[i];
    }
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem E 小A的路径

https://ac.nowcoder.com/acm/contest/549/E

题解：矩阵快速幂+最短路（Floyd算法）

参考文章：矩阵快速幂 Floyd算法 

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
char str;
ll b[N][N];
ll a[N][N];
void Matrix(ll a[N][N],ll b[N][N]){
    ll c[N][N];
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=c[i][j];
        }
    }
}
void power(ll k){
    for(int i=1;i<=n;i++){
        a[i][i]=1;
    }
    while(k){
        if(k&1)Matrix(a,b);
        Matrix(b,b);
        k>>=1;
    }
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d%d%d",&n,&m,&k,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        b[u][v]++;
    }
    power(k);
    for(int i=1;i<=n;i++)
        if(t!=i)ans=(ans+a[t][i])%MOD;
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem F 小A的最短路

https://ac.nowcoder.com/acm/contest/549/F

C++版本一

题解：最近公共祖先+最短路（SPFA算法）

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define pb push_back
#define Rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf=0x3f3f3f3f;
const ll INF=9e18;
const int N=3e5+50;
struct edge{ int v,w; };
vector<edge> G[N];
int n,U,V,dep[N],Fa[N][22];
 
void dfs(int u,int fa) {
    dep[u]=dep[fa]+1;
    Fa[u][0]=fa;
    for(int i=1;(1<<i)<=dep[u];i++) Fa[u][i]=Fa[Fa[u][i-1]][i-1];
    for(auto &e:G[u]) {
        int v=e.v;
        if(v==fa) continue;
        dfs(v,u);
    }
}
int lca(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=20;i>=0;i--) if((1<<i)<=dep[x]-dep[y]) x=Fa[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--) if(Fa[x][i]!=Fa[y][i]) x=Fa[x][i],y=Fa[y][i];
    return Fa[x][0];
}
int solve(int x,int y) { return dep[x]+dep[y]-2*dep[lca(x,y)]; }
 
struct node{
    int u,dis;
    node() {}
    node(int u,int dis):u(u),dis(dis) {}
    bool operator <(const node &rhs) const {
        return dis>rhs.dis;
    }
};
int dis[N];
priority_queue<node> q;
void spfa() {
    for(int i=1;i<=n;i++) dis[i]=inf;
    dis[U]=0;
    q.push({U,0});
    while(!q.empty()) {
        int u=q.top().u,d=q.top().dis;q.pop();
        if(dis[u]<d) continue;
        for(auto &e:G[u]) {
            int v=e.v,w=e.w;
            if(dis[v]>dis[u]+w) {
                dis[v]=dis[u]+w;
                q.push({v,dis[v]});
            }
        }
    }
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back({v,1});
        G[v].push_back({u,1});
    }
    dfs(1,0);
    scanf("%d%d",&U,&V);
    G[U].push_back({V,0});
    G[V].push_back({U,0});
    spfa();
    int q;
    scanf("%d",&q);
    while(q--) {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",min(solve(x,y),dis[x]+dis[y]));
    }
    return 0;
}

C++版本二 

题解：最近公共祖先+最短路（dijkstra算法）

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=300000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int dep[N];
int dp[N][23];
int dis[N];
bool vis[N];
bool VIS[N];
char str;
struct node{
    int e,w;
    bool operator <(const node &S)const{
        return w>S.w;
    }
}x,tmp;
vector<node>G[N];
void dfs(int u){
    vis[u]=1;
    for(int i=0,j=G[u].size();i<j;i++){
        int v=G[u][i].e;
        if(vis[v])
            continue;
        dep[v]=dep[u]+1;
        dp[v][0]=u;
        dfs(v);
    }
}
void RMQ(){
    for(int i=0;i<22;i++){
        for(int j=1;j<=n;j++){
            dp[j][i+1]=dp[dp[j][i]][i];
        }
    }
}
int LCA(int x,int y){
    if(dep[x]<dep[y])
        swap(x,y);//
    while(dep[x]>dep[y])
        x=dp[x][(int)log2(dep[x]-dep[y])];
    if(x==y)
        return x;

    for(int i=log2(dep[x]);i>=0;i--){
        if(dp[x][i]!=dp[y][i])
            x=dp[x][i],y=dp[y][i];
    }
    return dp[x][0];
}
void init(){
    for(int i=1;i<=n;i++){
        G[i].clear();
    }
    memset(vis,0,sizeof(vis));
    memset(dep,0,sizeof(dep));
    memset(dp,0,sizeof(dp));
    memset(dis,0,sizeof(dis));
    memset(VIS,0,sizeof(VIS));
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    init();
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        x.e=v;
        x.w=1;
        G[u].push_back(x);
        x.e=u;
        G[v].push_back(x);
    }
    dfs(1);
    scanf("%d%d",&u,&v);
    RMQ();
    priority_queue<node>q;
    x.e=u;
    x.w=0;
    q.push(x);
    x.e=v;
    q.push(x);
    while(!q.empty()){
        x=q.top();
        q.pop();
        if(VIS[x.e])
            continue;
        VIS[x.e]=1;
        dis[x.e]=x.w;
        for(int i=0,j=G[x.e].size();i<j;i++){
            tmp=G[x.e][i];
            if(VIS[tmp.e])
                continue;
            tmp.w=x.w+tmp.w;
            q.push(tmp);
        }
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        cout<<min(dep[u]+dep[v]-2*dep[LCA(u,v)],dis[u]+dis[v])<<endl;
    }
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem G 小A与小B

https://ac.nowcoder.com/acm/contest/549/G

题解：DFS

1、时间不一定相同；

2、小B最后相遇时刻可以走一步；

3、小B两步都不能在障碍物上；

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=2000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp,sum;
int a[N],b[N];
bool vis1[N][N],vis2[N][N];
int dis[N][N];
char str[N][N];
int ax,ay,bx,by;
struct node{
    int x,y,time;
}s,f,tmp;
int dir2[4][2]={1,0,0,1,-1,0,0,-1};
int dir1[8][2]={1,0,0,1,-1,0,0,-1,1,1,-1,-1,1,-1,-1,1};

int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>str[i][j];
            if(str[i][j]=='C'){
                ax=i;
                ay=j;
            }
            if(str[i][j]=='D'){
                bx=i;
                by=j;
            }
        }
    }
    queue<node>q;
    s.x=ax;
    s.y=ay;
    s.time=0;
    q.push(s);
    vis1[ax][ay]=1;
    while(!q.empty()){
        f=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            tmp.x=f.x+dir1[i][0];
            tmp.y=f.y+dir1[i][1];
            tmp.time=f.time+1;
            if(tmp.x<1||tmp.x>n||tmp.y<1||tmp.y>m)
                continue;
            if(vis1[tmp.x][tmp.y])
                continue;
            if(str[tmp.x][tmp.y]=='#')
                continue;
            vis1[tmp.x][tmp.y]=1;
            dis[tmp.x][tmp.y]=tmp.time;
            q.push(tmp);

        }
    }
    //for(int i=1;i<=n;i++){
        //for(int j=1;j<=m;j++){
            //printf("%d%c",dis[i][j]," \n"[j==m]);
        //}
    //}
    while(!q.empty())
        q.empty();
    s.x=bx;
    s.y=by;
    s.time=0;
    q.push(s);
    vis2[bx][by]=1;
    ans=INF;
    while(!q.empty()){
        f=q.front();
        q.pop();
        //cout<<f.x<<" "<<f.y<<endl;
        if(vis1[f.x][f.y]){
            ans=min(max(dis[f.x][f.y],f.time),ans);
            flag=1;
            //cout<<ans<<endl;
        }
        for(int i=0;i<4;i++){
            tmp.x=f.x+dir2[i][0];
            tmp.y=f.y+dir2[i][1];
            tmp.time=f.time+1;
            if(tmp.x<1||tmp.x>n||tmp.y<1||tmp.y>m)
                continue;
            if(vis2[tmp.x][tmp.y])
                continue;
            if(str[tmp.x][tmp.y]=='#')
                continue;
            if(vis1[tmp.x][tmp.y]){
                ans=min(max(dis[tmp.x][tmp.y],tmp.time),ans);
                flag=1;
                //cout<<ans<<endl;
            }
            for(int j=0;j<4;j++){
                tmp.x=f.x+dir2[i][0]+dir2[j][0];
                tmp.y=f.y+dir2[i][1]+dir2[j][1];
                if(tmp.x<1||tmp.x>n||tmp.y<1||tmp.y>m)
                    continue;
                if(vis2[tmp.x][tmp.y])
                    continue;
                if(str[tmp.x][tmp.y]=='#')
                    continue;
                if(vis1[tmp.x][tmp.y]){
                    ans=min(max(dis[tmp.x][tmp.y],tmp.time),ans);
                    flag=1;
                    //cout<<ans<<endl;
                }
                vis2[tmp.x][tmp.y]=1;
                q.push(tmp);
            }
        }
    }
    if(flag){
        cout<<"YES"<<endl;
        cout<<ans<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem H 小A的柱状图

https://ac.nowcoder.com/acm/contest/549/H

题解：单调栈

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
int a[N];
int b[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    stack<int>s,t;
    s.push(0);
    t.push(0);
    for(int i=1;i<=n;i++){
        ll w=0;
        while(s.top()>b[i]){
            w+=t.top();
            ans=max(ans,(ll)w*s.top());
            s.pop();
            t.pop();
        }
        s.push(b[i]);
        t.push(w+a[i]);
    }
    cout<<ans<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem I 小A取石子

https://ac.nowcoder.com/acm/contest/549/I

题解：NIM游戏 博弈论

判断一下小A是否能够取石子，当且仅当小A原本就是必败态并且不能取出任何石子的情形下，小A会输否则小A都会赢。

参考文章：SG函数    NIM游戏

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum^=a[i];
    }
    if(sum)
        ans=1;
    for(int i=1;i<=n;i++){
        if(a[i]>=k){
            temp=sum^a[i]^(a[i]-k);
            if(temp){
                ans=1;
                break;
            }
        }
    }
    cout<<(ans?"YES":"NO")<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem J 小A的数学题

https://ac.nowcoder.com/acm/contest/549/J

题解：

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define pb push_back
#define Rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf=0x3f3f3f3f;
const ll INF=9e18;
const int N=1e6+50;
const int maxn=1e6+50;
const ll mod=1e9+7;
bool vis[maxn];
int cnt=0,pri[maxn],mu[maxn];
inline void init(){
    mu[1]=1;
    for(int i=2;i<=(int)1e6+1;i++){
        if(!vis[i]) pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&pri[j]*i<=(int)1e6+1;j++){
            vis[i*pri[j]]=true;
            if(i%pri[j]==0){ mu[i*pri[j]]=0;break; }
            else mu[i*pri[j]]=-mu[i];
        }
    }
}
int main() {
    init();
    ll n,m,ans=0;
    scanf("%lld%lld",&n,&m);
    ll k=min(m,n);
    for(ll i=1;i<=k;i++) {
        for(ll j=i;j<=k;j+=i) {
            ans+=i*i*(ll)mu[j/i]*(n/j)*(m/j);
            ans%=mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}