武汉工程大学第八届ACM新生赛 题解

武汉工程大学第八届ACM新生赛 题解

A. world.search(you);

题意

本题要求判断一个字符串是否为另一个字符串的连续子串。

  • 输入两个字符串 s1 和 s2，长度分别为 l1 和 l2。
  • 如果 s2 在 s1 中出现过（且是连续的），输出 Yes；否则输出 No。

解法

  • 暴力枚举：从 s1 的每个位置开始尝试匹配 s2。
  • 如果在某个位置能完整匹配 s2，则输出 Yes；否则最终输出 No。
  • 时间复杂度最坏 ，在 范围内可行。

使用库函数 strstr(s1, s2) 能够简便实现。

参考代码

#include <stdio.h>
#define N 1000
char s1[N], s2[N];

int main() {
    int l1, l2;
    scanf("%d%d", &l1, &l2);
    scanf("%s%s", s1, s2);

    for (int i = 0; i <= l1 - l2; i++) {
        int flag = 0;
        for (int j = 0; j < l2; j++) {
            if (s1[i + j] != s2[j]) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            printf("Yes");
            return 0;
        }
    }
    printf("No");
    return 0;
}

B. 邪恶小 H 的客运公司

题意

有向图，从 到 ，费用是经过的边的权值异或能得到的最大值的最高位 1。

解法

抹掉“零头”意味着只需看最高位 1，异或和能得到的最高位 1，就是原来数中最高位的 1，不需要考虑异或和的最大值。

  • 所以直接求最大值的最短路。
  • 或枚举最高位 1，只走小于它的边，看能否到达。

参考代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;

const int N = 1e5 + 100, M = 2e6 + 100;

int n, m, s, t;
struct EDGE {
	int v, w, nxt;
} e[M];
int lst[N], ep;
void AE(int u, int v, int w) {
	e[++ep].v = v;
	e[ep].w = w;
	e[ep].nxt = lst[u];
	lst[u] = ep;
}

priority_queue<pair<int, int>, vector<pair<int, int > >, greater<pair<int, int> > > q;
int d[N];

int main() {
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for(int i = 1; i <= m; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		int ww = 0;
		while(w) ++ww, w >>= 1;
		AE(u, v, ww);
	}
	
	memset(d, 0x3f, sizeof d);
	q.push({0, s});
	d[s] = 0;
	while(!q.empty()) {
		auto [ud, u] = q.top();
		q.pop();
		if(d[u] < ud) continue;
		for(int i = lst[u]; i; i = e[i].nxt) {
			int v = e[i].v, w = e[i].w;
			int vd = max(ud, w);
			if(vd < d[v]) {
				q.push({vd, v});
				d[v] = vd;
			}
		}
	}
	
	if(d[t] == 0) printf("0\n");
	else if(d[t] == d[0]) printf("-1\n");
	else printf("%d\n", 1 << (d[t] - 1));
	
	return 0;
}

CD. 保卫数字王国

题意

个数字，给定每个数字的下一个数字可以是哪些，求可以形成的长为 的串的数量。对 取模。

解法

简单版可以直接暴搜。

也可以 DP。明显在末尾添加数字时可用的字符只与结尾字符有关，故设 表示长为 、以 结尾的串有多少个。设 表示 的下一个数字能否是 ，能则为 ，不能则为 。则转移方程为 。

困难版的 更大，可以到 。这种情况就可以考虑 或 的时间复杂度。

观察 DP 的转移方程，发现长度为 时，以各数字为结尾的状态可以看作一个列向量
，
可以看作矩阵，转态转移就是矩阵乘法。而矩阵乘法满足交换律，所以

可以像普通数字的幂一样用快速幂计算；只需要把底数换成矩阵，整数乘法换成矩阵乘法。复杂度 。

大一的同学可以看一下矩阵乘法的运算法则，并不需要学过线性代数。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int128 __int128 
#define pb push_back
typedef pair <int,int> PII;
const int N = 5e5 + 5;
const int M = 505;
const ll INF = 1e18;
const int mod = 998244353;


vector <vector<ll>> d(6,vector<ll>(6));
vector<vector<ll>> mtxqmi(ll k)
{
    vector <vector<ll>> ans(6,vector<ll>(6));
    for (int i = 1; i <= 5; i++)
    {
        ans[i][i] = 1;
    }
    while (k)
    {
        vector <vector<ll>> tem(6,vector<ll>(6));
        if (k&1)
        {
            for (int i = 1; i <= 5; i++)
            {
                for (int j = 1; j <= 5; j++)
                {
                    tem[i][j] = ans[i][j];
                    ans[i][j] = 0;
                }
            }
            for (int i = 1; i <= 5; i++)
            {
                for (int j = 1; j <= 5; j++)
                {
                    for (int k = 1; k <= 5; k++)
                    {
                        ans[i][j] = (ans[i][j] + (tem[i][k] * d[k][j])%mod)%mod;
                    }
                }
            }
        }
        k >>= 1;
        for (int i = 1; i <= 5; i++)
        {
            for (int j = 1; j <= 5; j++)
            {
                tem[i][j] = d[i][j];
                d[i][j] = 0;
            }
        }
        for (int i = 1; i <= 5; i++)
        {
            for (int j = 1; j <= 5; j++)
            {
                for (int k = 1; k <= 5; k++)
                {
                    d[i][j] = (d[i][j] + (tem[i][k] * tem[k][j])%mod)%mod;
                }
            }
        }
    }
    return ans;
}
void solve()
{
    ll n;
    cin >> n;
    for (int i = 1; i <= 5; i++)
    {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++)
        {
            int a;
            cin >> a;
            d[a][i] = 1;
        }
    }
    vector <vector<ll>> res(6,vector<ll>(6));
    res = mtxqmi(n - 1);
    ll out = 0;
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= 5; j++)
        {
            out = (out + res[i][j])%mod;
        }
    }
    cout << out << '\n';
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
	// cin >> T;
    while (T--) 
	{
        solve();
    }
    return 0;
}

E. 火速生成题面中

题意

本题要求计算一组整数的总和，并根据结果输出不同的字符串。

  • 输入一个长度为 的整数序列，每个数表示一道题的“抽象度”。
  • 计算所有抽象度的总和。
  • 如果 ，输出 Good job；否则输出 Statement made by gzd。

解法

  1. 使用 64 位整数类型long long(C/C++)存储总和，避免溢出。
  2. 遍历数组，累加所有元素。
  3. 并根据大小输出对应的字符串。

时间复杂度：，只需遍历一次数组。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    cout << sum << "\n";
    if (sum <= 100) {
        cout << "Good job\n";
    } else {
        cout << "Statement made by gzd\n";
    }
    return 0;
}

F. 小白的区间查询 I

题意

给定一个长度为 的数组和一个整数 ，有 次询问，每次会询问一个区间 ，询问在这个区间内有多少个连续的子区间的和不小于 。

解法

计算前缀和数组 pre[i] = pre[i-1] + a[i]。

对每个起点 ，用二分查找第一个位置 （在 pre 上）使得 pre[x] - pre[i-1] >= k，将 sp[i] = x（若找不到则 x = n+1）。

代码中：

int x = lower_bound(pre+1, pre+n+1, pre[i-1] + k) - pre;
sp[i] = x;

预处理 pre1[i] 为 sp 的前缀和：pre1[i] = sum_{t=1..i} sp[t]，这样可以在 O(1) 时间得到任意区间 sp 的和。

对于每个查询 ：

  1. 找到区间 中最后一个满足 sp[idx] <= r 的位置 cp，可以用 upper_bound(sp+l, sp+r+1, r) - sp - 1 获得。
  2. 满足条件的起点个数为 cnt = cp - l + 1（若 cp < l 则为 0）。
  3. 答案为 (r+1) * cnt - (pre1[cp] - pre1[l-1])（当 时直接输出 0）。
  4. 代码里直接按这个公式输出。

参考代码

#include<bits/stdc++.h>
#define int long long
#define double long double
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef long long ll;
typedef pair<int,int> PII;
const int N=3e5+10;
const int M=1e3+10;
int mod=1e9+7;
int a[N],pre[N],pre1[N],sp[N];

void solve(){
    int n,q,k;
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
    for(int i=1;i<=n;i++){
        int x=lower_bound(pre+1,pre+n+1,pre[i-1]+k)-pre;
        sp[i]=x;
        pre1[i]=pre1[i-1]+x;
    }
    while(q--){
        int l,r;cin>>l>>r;
        int cp=upper_bound(sp+l,sp+r+1,r)-sp-1;
        int cnt=cp-l+1;
        cout<<(r+1)*cnt-(pre1[cp]-pre1[l-1])<<"\n";
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int _;
    _=1;
    while(_--){
        solve();
    }
}

G. 小白的区间查询 II

题意

给定一个长度为 的数组，有 次询问，每次会询问一个区间 和一个 ，询问在这个区间内有多少个连续的子区间的长度不小于 。

解法

对于每次询问可以用总的子区间的个数减去没有出现过 的子区间个数即可，对于没有出现过 的子区间个数可以对 的出现位置进行预处理，二分出最接近 和 的两个位置，中间的每个间隔都可以预处理出来(使用前缀和即可)。

参考代码

#include<bits/stdc++.h>
#define int long long
#define double long double
#define x first
#define y second
using namespace std;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    unordered_map<int, vector<int>> pos;
    pos.reserve(n * 2);
    for (int i = 1; i <= n; i++) pos[a[i]].push_back(i);
    unordered_map<int, vector<int>> pref;
    pref.reserve(pos.size() * 2);
    for (auto& pr : pos) {
        auto& v = pr.second;
        int m = v.size();
        vector<int> pf(m);
        pf[0] = 0;
        for (int i = 1; i < m; i++) {
            int gap = v[i] - v[i - 1] - 1;
            pf[i] = pf[i - 1] + gap * (gap + 1) / 2;
        }
        pref[pr.first] = move(pf);
    }
    while (q--) {
        int l, r, xv;
        cin >> l >> r >> xv;
        auto it = pos.find(xv);
        if (it == pos.end()) {
            cout << 0 << "\n";
            continue;
        }
        auto& v = it->second;
        auto& pf = pref[xv];
        int L = lower_bound(v.begin(), v.end(), l) - v.begin();
        int R = upper_bound(v.begin(), v.end(), r) - v.begin() - 1;
        if (L > R) {
            cout << 0 << "\n";
            continue;
        }
        int len = r - l + 1;
        int total = len * (len + 1) / 2;
        int t0 = v[L] - l;
        int tlast = r - v[R];
        int bad = t0 * (t0 + 1) / 2 + tlast * (tlast + 1) / 2 + (pf[R] - pf[L]);
        cout << total - bad << "\n";
    }
    return 0;
}

H. 梵墨的 Clash Royale

题意

个一位数字，把全排列构成的 个数分成两组，使两组的平方和相同。

解法

根据样例可知对于三个数 1 2 3， 分为一组是对的，看起来就像循环移位。不难发现，对于任意三个数字这样分组都是正确的，证明详在最后。

正常做一遍全排列，在只剩三个数时，有 种可能，把这三个数放最后得到一个数，做循环左移两次分别得到两个数，把这三个数分到一组，可以得到 个数，即为答案。

  • 或按字典序构造这 个数，选第一个数，然后隔两个选两个。
  • 或按字典序构造这 个数，每 个里选第 个。
  • ……

证明

对于三个数 ， 的轮换求和是对称的。即：

任意交换 的位置值不变。所以：

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e6 + 6e5 + 3e4;
int a[20],b[20],c[20][20],st[20];
int n,op;
string s1="";
vector<string>s;
int h[3];
void dfs(int id){
    if(op==1&&id==n-3){
        int it=-1;
        for(int i=1;i<=n;i++){
            if(!st[i])h[++it]=i;
        }
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                b[id+j+1]=a[h[(j+i)%3]];
            }
            s.push_back(s1);
            for(int i=1;i<=n;i++){
                char c='0'+b[i];
                s[s.size()-1]+=c;
            }
        }
        return;
    }
    if(op==0&&id==n){
        s.push_back(s1);
        for(int i=1;i<=n;i++){
            char c='0'+b[i];
            s[s.size()-1]+=c;
        }
        return;
    }
    for(int i=1;i<=n;i++){
        if(st[i])continue;
        st[i]++;
        b[id+1]=a[i];
        dfs(id+1);
        st[i]--;
    }
}
void f(string s,int &ans){
    int t=0;
    for(int i=0;i<n;i++){
        t*=10;
        t+=s[i]-'0';
    }
    ans+=t*t;
}
signed main() {
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    int ans1=0,ans2=0;
    op=1;
    dfs(0);
    
    for(int i=0;i<s.size();i++){
        f(s[i],ans1);
        cout<<s[i]<<"\n";
    }
}

I. 冰箱

题意

本题要求模拟冰箱和记忆系统的交互过程。

  • 冰箱最多存放 件零食。
  • 小O只记住最近 次“想吃零食”的记录。
  • 操作包括：
    • 1 x：小O想吃零食，可能导致冰箱移除最不受欢迎的零食或记忆过期删除。
    • 2 y：gzd 偷吃零食，若存在则移除并删除记忆。
  • 输出：
    1. 每次操作是否有零食被移除（编号或 -1）。
    2. 操作完成后冰箱剩余零食，按出现次数排序。

解法

  • 使用链表 list<int> 存储最近 条记录（前端最新，后端最旧）。
  • 使用 unordered_map<int, deque<list<int>::iterator>> 保存每个零食在记忆中的位置，方便删除（使用map亦可）。
  • 使用 set<node> 存储冰箱零食，比较规则：
    • 出现次数多的优先；
    • 次数相同编号大的优先。
  • 操作流程：
    • 操作 1：若冰箱满则移除最不受欢迎零食；插入新记录；若记忆超出 ，弹出最旧记录并更新计数。
    • 操作 2：若零食存在则移除并删除记忆，否则输出 -1。

参考代码

#include<bits/stdc++.h>
using namespace std;
struct meta{
    unordered_map<int,deque<list<int>::iterator>> mp;
    list<int> ls;
};
struct node{
    int v;
    meta *m;
    bool operator<(const node & n)const{
        if(m->mp[v].size()==m->mp[n.v].size())return v > n.v;
        return m->mp[v].size() > m->mp[n.v].size();
    }
};

void solve(){
    int n,k,q;
    cin>>n>>k>>q;

    meta m;
    //st用于保持顺序
    set<node> st;

    for(int i=0;i<q;i++){
        int op,v;
        cin>>op>>v;
        if(op==1){
            //是否删除过
            bool flag = false;
            //如果不存在这个对象需要为插入预留位置，删除时会减小m.ls的size，所以这里删除了下面就不会删除
            if(!st.count(node{v,&m})){
                while(st.size()>=n){
                    //删除最不常用的最小元素
                    auto item = *st.rbegin();
                    st.erase(item);
                    //本轮删除过
                    flag = true;
                    //输出
                    cout<<item.v<<' ';
                    //删除这个元素的记忆
                    for(auto it: m.mp[item.v]){
                        m.ls.erase(it);
                    }
                    m.mp.erase(item.v);
                }
            }
            //删除对象（若有）要在修改之前从set删除对象
            st.erase(node{v,&m});
            //插入记录
            m.ls.emplace_front(v);
            m.mp[v].emplace_front(m.ls.begin());
            //重新加入set
            st.emplace(node{v,&m});
            //记忆过期
            while(m.ls.size()>k){
                //删除set中对象后删除最后的记录
                auto d = m.ls.back();
                st.erase(node{d,&m});
                m.ls.pop_back();
                m.mp[d].pop_back();
                //如果记忆变为0也要删除
                if(m.mp[d].empty()){
                    m.mp.erase(d);
                    cout<<d<<' ';
                    flag = true;
                    continue;
                }
                //重新插入对象
                st.emplace(node{d,&m});
            }
            //没有任何对象被删除输出-1
            if(!flag){
                cout<<-1<<' ';
            }
        }else if(op == 2){
            //删除的数不存在
            if(!st.count(node{v,&m})){
                cout<<-1<<' ';
                continue;
            }
            cout<<v<<' ';
            //存在的话先删除set
            st.erase(node{v,&m});
            //删除记录
            for(auto item: m.mp[v]){
                m.ls.erase(item);
            }
            m.mp.erase(v);
        }
    }
    cout<<endl;
    //如空，直接输出-1;
    if(st.empty()){
        cout<<-1<<endl;
        return;
    }
    //非空，按排序输出
    for(auto item: st){
        cout<<item.v<<' ';
    }
    cout<<endl;
}
signed main(){
    int t=1;
    // cin>>t;
    while(t--)solve();
}

J. 美妙的旋律

题意

树上所有从上到下的子串与模式串的前缀进行匹配。

解法

与模式串的前缀匹配，我们很容易想到 KMP。KMP 能 求出主串以每个位置为结尾的、与模式串前缀匹配的最长的串。再由 border 数组的性质，不断跳 border 就能找到以该位置为结尾的、与模式串前缀匹配的所有的串。可以通过 cnt[i] = cnt[nxt[i]] + i} 预处理出这些串的总长度。

把 KMP 的循环改成 dfs 就能把 KMP 放到树上。从不断求主串中后一个字符的答案，变成了不断求子节点的答案。

但是，TLE！

KMP 有两层循环，保证它线性复杂度的是：模式串的指针j最多增长 ，在内层循环中每次要减小 ，而j不会小于 ，所以内层循环总复杂度只有 。

而在树上，一个节点的j值可被多个子节点继承，因而总减小次数可以远超 ，故树上 KMP 的复杂度变成了 。

解决方法是，把指针为 、下一个要匹配的字符是 时，j通过 border 数组最终会跳到的位置jmp[j][c]预处理出来；因为值域很小，，空间可以接受。这样就不需要内层循环，复杂度 。

也可以从 DP 或自动机的角度理解。

参考代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
const int N = 1e6 + 100, M = 1e5 + 10, A = 21 + 10;

int n, m;
struct EDEG {
	int v, nxt;
} e[N];
int lst[N], ep;
void AE(int u, int v) {
	e[++ep].v = v;
	e[ep].nxt = lst[u];
	lst[u] = ep;
}

int w[N], a[N];
int nxt[M], jmp[M][A];
LL pre[M];

LL ans;
void dfs(int u, int j) {
	while(j > 0 && w[u] != a[j + 1]) j = jmp[j][w[u]];
	if(w[u] == a[j + 1]) ++j;
	ans += pre[j];
	
	if(j >= m) j = nxt[j];
	for(int i = lst[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		dfs(v, j);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 2; i <= n; ++i) {
		int fa;
		scanf("%d", &fa);
		AE(fa, i);
	}
	for(int i = 1; i <= n; ++i) scanf("%d", &w[i]);
	for(int i = 1; i <= m; ++i) scanf("%d", &a[i]);
	
	for(int i = 2, j = 0; i <= m; ++i) {
		while(j > 0 && a[i] != a[j + 1]) j = nxt[j];
		if(a[i] == a[j + 1]) ++j;
		nxt[i] = j;
	}
	for(int i = 1; i <= m; ++i) {
		for(int c = 1; c <= 21; ++c) {
			if(a[nxt[i] + 1] == c) jmp[i][c] = nxt[i];
			else jmp[i][c] = jmp[nxt[i]][c];
		}
	}
	for(int i = 1; i <= m; ++i)
		pre[i] = pre[nxt[i]] + i;
	
	dfs(1, 0);
	
	printf("%lld", ans);
	return 0;
}

K. 真的很简单

题意

若干盏灯，两种状态，第 轮切换编号是 的倍数的灯的状态。 组询问，每次询问第 轮后灯 的状态。

解法

灯 被切换的次数等于 的约数中不超过 的个数。因为只有在第 轮（）且 是 的约数时，灯 才会被切换。

预先计算每个数 （从 到 ）的所有约数，并存储在 vector 中。这样可以在查询时快速访问。

对于每个测试用例，二分计算 的约数中不超过 的个数。如果这个数是奇数，输出 Yes；否则输出 No。

也可以暴力模拟。将所有询问离线下来，按 从小到大处理。

用 个变量表示 盏灯，第 轮枚举所有 的倍数并切换灯的状态。注意枚举时只能枚举 的倍数，复杂度才有保证。

for(int j = i; j <= m; j += i)

由于 的倍数只有 个，调和级数 和 在 时是等价无穷大，即 很大时 和 趋于相等，所以复杂度为 。这是一种常见技巧。

参考代码

#include <iostream>
#include <vector>
using namespace std;

const int maxM = 1000000;
vector<vector<int>> divisors(maxM + 1);

void precompute() {
    for (int i = 1; i <= maxM; i++) {
        for (int j = i; j <= maxM; j += i) {
            divisors[j].push_back(i);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    precompute();
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        int count = 0;
        for (int d : divisors[m]) {
            if (d <= n) {
                count++;
            } else {
                break;
            }
        }
        if (count % 2 == 1) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    return 0;
}
  1. 预计算：precompute 函数通过遍历每个数 及其倍数，将 添加到对应倍数的约数列表中。这样，每个数 的约数列表在查询时可以直接使用。
  2. 查询处理：对于每个测试用例，读取 和 ，遍历 的约数列表，统计不超过 的约数个数。根据个数的奇偶性输出结果。
  3. 效率优化：预计算阶段的时间复杂度为 ，其中 。每个查询的处理时间为 ，其中 是 的约数个数，平均情况下很小，因此整体效率很高。

L. 小 H 的三角形

题意

给上平面上三个点，判断它们能否构成三角形。

解法

也可以用斜率或边长等方法判断。但向量是计算几何中重要的方法，涉及小数的方法可能在数据范围很大或计算复杂时出现误差过大的问题。

参考代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
	int x1, x2, x3, y1, y2, y3;
	scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);
	x2 -= x1, y2 -= y1;
	x3 -= x1, y3 -= y1;
	if(x2 * y3 - x3 * y2 == 0)
		printf("collinear\n");
	else printf("triangle\n");
	
	return 0;
}

M. 石头博弈

题意

博弈论。一堆石子，每回合每人可把它分成两堆，但最多只能存在两堆；或从一堆中取一个。求必胜状态。

解法

由于石头最多只能有两堆，所以当石头已经有两堆的时候，就只能拿一个石头了。什么时候必赢呢？假设先操作的为 A，后手为 B，假设现在有两堆石头，石头数量都为 ，那么 A 很明显只能选择一堆来拿，那么其中一堆就变成了 ，另一堆为 ，那 B 想赢的话该怎么操作？绝顶聪明的他决定镜像操作！当 A 从一堆中拿一个时，那他就从相反堆中拿走一个，维持两堆数量相同，那么他一定是拿走最后一个石头的人，A 就无法操作了，B 就必胜了！

所以想要必胜的话，就需要在自己回合内把石头变成相同的两堆，那么下一个人拿的时候就会破坏这两堆的平衡，你只需要做他的镜像操作就可以获胜！

答案就显而易见了，当 为偶数的时候，A 可以将石头分为相同的两堆，然后模仿 B 做镜像操作 A 就可以必胜了。 为奇数的时候，若 A 拿走一个，则 B 下一步将石头分为相同的两堆，那么 B 就胜利了，若 A 将石头分为两堆，那 B 拿走多的那堆中的一个，那同样会变成相同的两堆，B 一样会必胜！

但是！！！n 为 的时候 A 拿走这一个就赢了， 为 的时候 A 什么都做不了，那么 B 就胜利了。所以需要单独判断 和 。

最后！！！因为数据范围为 所以一定要开long long ！！！

参考代码

#include <iostream>
#define int long long
using namespace std;

signed main() {
    int n;
    cin >> n;
    if(n == 0) cout << "Wang Win!" << endl;
    else if(n <= 2) cout << "Zhang Win!" << endl;
    else if((n - 2) & 1) cout << "Wang Win!" << endl;
    else cout << "Zhang Win!" << endl;
}
全部评论

相关推荐

01-14 14:34
已编辑
华北电力大学 客户端开发
应届生入职半年，分享7个让我不再内耗的职场经验！
刚进职场那会儿，我每天都在反思：是不是我太菜了？是不是领导不喜欢我？是不是我不适合工作？后来慢慢发现，很多内耗其实是没必要的。下面这6点，是我踩坑后总结出来的，可能对26届即将入职的朋友有点用。1.别只看领导做了什么，要想他为什么这么做&nbsp;被领导批评≠你不行。有一句话说的好，不扣钱的批评你别信，不加钱的夸奖你别听。很多时候领导的批评也是他管理的手段，他要给他上面的领导交差罢了👉&nbsp;职场里很多行为，本质是向上交差，不一定和你本人有关。2.不接住别人的情绪只解决事情有次客户找我私下帮忙，但公司明确不允许，对方急得在电话里喷我。我等他说完，只说了一句：“我理解你着急，但这件事我确实无能为力。”后来他反...
工作压力大，你会干什么？
点赞 评论 收藏
分享
01-12 17:59
西安电子科技大学 Java
美团面试：接口被恶意狂刷，怎么办？
下面是原本面试现场：面试官：接口被恶意狂刷，怎么办？我：这个没搞过（每天CRUD，真的没搞过）面试官：如果现在让你来设计，你会怎么设计？我：巴拉巴拉...胡扯一通面试官：（带着不耐烦的表情）我们还是换个话题吧.....为了不让大家也和我有同样的遭遇，今天，咱们就用一个非常简单的方式实现防刷：一个注解搞定防刷技术点涉及到的技术点有如下几个：自定义注解拦截器Redis的基本操作Spring&nbsp;Boot项目其实，非常简单，主要的还是看业务。机-会技术大厂，前端-后端-测试，全国均有机会，感兴趣可以试试。待遇和稳定性都还不错~自定义注解自定义一注解AccessLimit**。&nbsp;import&nbsp;java.l...
哞客37422655...：遇到刷接口的 就私聊他 告诉他求求你不要刷了
面试时最害怕被问到的问题
点赞 评论 收藏
分享
头像
2025-12-11 11:13
已编辑
湖南大学 安卓
点赞 评论 收藏
分享
头像
2025-12-16 16:24
已编辑
河南大学 Java
点赞 评论 收藏
分享
01-12 13:26
新国都_Java研发工程师(准入职员工)
图拉斯内推，图拉斯内推码
ai面总结：AI调教的很好，问的问题很有意思，整场面试不会有很大的压迫感，追问大多是根据你的回答提问。总时长：35分钟Q1:自我介绍，重点介绍一下个人背景和大学期间的主要经历。Q2：你对于在一家公司长期发展有什么看法？你认为哪几点因素会让你在一家公司长期工作？（有追问）Q3：你取得过的最大成就是什么？过程中最大的难点是什么？你是如何突破的？最终的结果怎么样？（有追问2个）Q4：请描述一个过往遇到的最有压力困难或最具挑战的一个场景，你是如何解决的？对你有什么影响？（有追问）Q5：依你的看法，请描述一个你近期完成的项目任务，如果重来一次，你会做哪些不同的事情来提升结果？（有追问2个）Q6：电商运营...
点赞 评论 收藏
分享
评论
1
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 为了入行xx岗，我学了__ #
7533次浏览 116人参与
# 26届校招投递进展 #
586617次浏览 3775人参与
# 简历第一个项目做什么 #
8637次浏览 126人参与
# 被说“做题家”，你的反应是_____？ #
3282次浏览 106人参与
# 参加哪些竞赛对找工作有帮助？ #
9689次浏览 150人参与
# 你都见过什么样的草台班子？ #
10997次浏览 86人参与
# Prompt分享 #
3619次浏览 98人参与
# 找实习记录 #
41844次浏览 598人参与
# 工作压力大，你会干什么？ #
15644次浏览 336人参与
# 从哪些方向判断这个offer值不值得去？ #
48782次浏览 342人参与
# 找工作前vs找工作后的心路变化 #
37335次浏览 301人参与
# AI让你的思考变深了还是变浅了？ #
6139次浏览 149人参与
# 多益网络求职进展汇总 #
62311次浏览 281人参与
# 如果不上班，你会去做什么 #
8679次浏览 298人参与
# 入职以后才知道的校招谎言 #
117315次浏览 747人参与
# 去年你投递实习了吗？ #
28244次浏览 335人参与
# 大家每天通勤多久？ #
75518次浏览 537人参与
# 今年秋招还有金九银十吗 #
71483次浏览 502人参与
# 邪修省钱套路 #
8707次浏览 268人参与
# 校招入职后的感受 #
466762次浏览 3629人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务