[Codeforces] games (R1600) Part.1

[] games (R1600) Part.1

题单:,1201-1600

74B. Train

原题指路:

题意 ( 2 s 2\ \{s} 2s)

偷渡者()和管理员()在火车上玩游戏.火车有编号 1 ∼ n 1\sim n 1∼n的 n n n节车厢,其中 1 1 1号车厢是头, n n n号车厢是尾.火车每分钟处于运行或停靠状态.每分钟两个玩家都会移动,且偷渡者先移动.任意时刻两玩家都知道对方的位置.

管理员有一个移动方向——朝着火车头或火车尾.每分钟他会移动到他的移动方向的下一节车厢,当他在 1 1 1号或 n n n号车厢时转向.

偷渡者的移动与火车的状态有关.若火车该分钟处于运行状态,则偷渡者可移动到相邻的一节车厢或留在所处车厢;若火车处于停靠状态且不是终点站,他会下车并从任一节车厢上车.若火车停靠若干分钟,则每分钟他都会下车再重新上车.

若某一分钟偷渡者和管理员处于同一节车厢,则管理员胜.若到终点站后偷渡者仍未负,则偷渡者胜.若偷渡者负,则希望他尽量晚负.两人都采取最优策略,问最后的胜者.若管理员胜,需他抓到偷渡者的分钟数(从 1 1 1开始).

第一行输入三个整数 n , m , k ( 2 ≤ n ≤ 50 , 1 ≤ m , k ≤ n , m ≠ k ) n,m,k\ \ (2\leq n\leq 50,1\leq m,k\leq n,m\neq k) n,m,k(2≤n≤50,1≤m,k≤n,m=k),分别表示火车的车厢数、偷渡者的初始位置、管理员的初始位置.第二行输入一个字符串表示管理员初始时的移动方向,其中"to head"表示他向火车头移动,"to tail"表示他向火车尾移动.数据保证他移动的方向至少还有一节车厢.第三行输入一个长度不超过 200 200 200的 0 − 1 0-1 0−1串表示每分钟火车的状态,其中 0 0 0表示火车处于运行状态, 1 1 1表示火车处于停靠状态.

思路

偷渡者的最优策略:①在火车运行时与管理员同向移动;②在火车停靠时在与管理员移动方向相反的最远的车厢上车.

模拟该过程即可.

代码

void solve() {int n, m, k; cin >> n >> m >> k;  // m表示偷渡者的位置,k表示管理员的位置int face = 0;  // 管理者的移动方向,0表示向火车尾,1表示向火车头string s; cin >> s >> s;if (s[0] == 'h') face = 1;cin >> s;s = " " + s;for (int i = 1; s[i]; i++) {if (s[i] == '0') {  // 火车处于运行状态if (face) {  // 管理员向火车头走m = max(1, m - 1);  // 若偷渡者在1号车厢,则他留在原地比走到2号车厢更优k--;if (m == k) {cout << "Controller " << i;return;}if (k == 1) face = 0;  // 管理员转向}else {  // 管理员向火车尾走m = min(n, m + 1);  // 若偷渡者在n号车厢,则他留在原地比走到(n-1)号车厢更优k++;if (m == k) {cout << "Controller " << i;return;}if (k == n) face = 1;  // 管理员转向}}else {  // 火车处于停靠状态if (face) {  // 管理员向火车头走if (--k == 1) face = 0;  // 管理员转向m = n;  // 偷渡者在与管理员移动方向相反的最远的车厢上车}else {if (++k == n) face = 1;  // 管理员转向m = 1;  // 偷渡者在与管理员移动方向相反的最远的车厢上车}}}cout << "Stowaway";
}int main() {solve();
}

120E. Put !

原题指路:

题意

一个位于红色格子的骑士能攻击到所有蓝色格子.A和B轮流在在一个 n × n n\times n n×n棋盘上放置一个骑士,使得任意两骑士间不能互相攻击,A先手.两人都采取最优策略,若最后A胜,输出 0 0 0;否则输出 1 1 1.

有 t ( 1 ≤ t ≤ 100 ) t\ \ (1\leq t\leq 100) t(1≤t≤100)组测试数据.每组测试数据输入一个整数 n ( 1 ≤ n ≤ 1 e 4 ) n\ \ (1\leq n\leq 1\{e}4) n(1≤n≤1e4).

思路

最优策略:先手占中心位置,然后先手放置在后手放置的位置关于中心对称的位置.

① n n n为奇数时,先手能占中心位置,先手必胜.

② n n n为偶数时,不存在中心位置,后手必胜.

代码

void solve() {int n; cin >> n;cout << (!(n & 1)) << endl;
}int main() {CaseT  // 单测时注释掉该行solve();
}

150A. Win or

原题指路:

题意 ( 2 s 2\ \{s} 2s)

A和B两人玩游戏,A先手.初始时纸上有一个整数 n n n,每轮每人写出一个上一个写的数的非平凡因子(非 1 1 1和它本身的因子),不能操作者胜.给定 n ( 1 ≤ n ≤ 1 e 13 ) n\ \ (1\leq n\leq 1\{e}13) n(1≤n≤1e13),问最后谁胜利.若A胜,第一行输出 1 1 1,第二行输出他的第一步操作,若他无法进行第一次操作,输出 0 0 0;若B胜,输出 2 2 2.

思路

只有当 n n n形如 p q pq pq或 p 2 p^2 p2时B胜,其中 p , q p,q p,q为素因子.

对其余情况,先预处理出 n n n的素因子后,若素因子个数为 1 1 1(含重复的素因子),则 n n n为素数,进而A无法进行第一次操作,输出 1 1 1;否则A至少有两个素因子,输出前两个素因子之积即可.

代码

void solve() {ll n; cin >> n;if (n == 1) {cout << 1 << endl << 0;return;}vl divisors;for (ll i = 2; i <= sqrt(n); i++) {if (n % i == 0) {while (n % i == 0) {n /= i;divisors.push_back(i);}}}if(n > 1) divisors.push_back(n);if (divisors.size() == 2) cout << 2;else {cout << 1 << endl;cout << (divisors.size() == 1 ? 0 : divisors[0] * divisors[1]);}
}int main() {solve();
}

197A. Plate Game

原题指路:

题意 ( 2 s 2\ \{s} 2s)

A和B轮流在一个 a × b a\times b a×b的矩形桌子上放置半径为 r r r的圆盘,A先手,要求圆盘间不能重叠,圆盘不能超出桌子区域,无法放置者负.两人都采取最优策略,问谁胜.

第一行输入三个整数 a , b , r ( 1 ≤ a , b , r ≤ 100 ) a,b,r\ \ (1\leq a,b,r\leq 100) a,b,r(1≤a,b,r≤100).

思路

最优策略:先手先在桌子中心放圆盘,随后放在与后手中心对称的位置.

故先手负当且仅当第一步无法放置圆盘.

代码

void solve() {int a, b, r; cin >> a >> b >> r;cout << (a >= 2 * r && b >= 2 * r ? "First" : "Second");
}int main() {solve();
}

257B. Cubes

原题指路:

题意 ( 2 s 2\ \{s} 2s)

有 n n n个红方块和 m ( 1 ≤ n , m ≤ 1 e 5 ) m\ \ (1\leq n,m\leq 1\{e}5) m(1≤n,m≤1e5)个蓝方块.A和B轮流将方块排成一条线,A先手.每轮每人选一个剩下的方块,接在已经排好的线最后.所有方块排完后,A的得分是相邻两个方块颜色相同的对数,B的得分是相邻两个方块颜色不同的对数.两人都想最大化自己的得分并都采取最优策略,问他们两人最后的得分.

思路

最优策略:A每次放置与上一个位置同色的方块,B每次放置与上一个位置异色的方块.

①对A,前 2 min ⁡ { n , m } 2\min\{n,m\} 2min{n,m}轮中只有A自己放置的操作才能得分.

​ 之后的 ( n + m − 2 min ⁡ { n , m } ) (n+m-2\min\{n,m\}) (n+m−2min{n,m})轮只剩下一种颜色,不管谁放置都是A得分.

​ 故A得分 min ⁡ { n , m } + ( n + m − 2 min ⁡ { n , m } ) − 1 = max ⁡ { n , m } − 1 \min\{n,m\}+(n+m-2\min\{n,m\})-1=\max\{n,m\}-1 min{n,m}+(n+m−2min{n,m})−1=max{n,m}−1,其中 − 1 -1 −1是因为A第一轮不得分.

②对B,因两人得分之和为 ( n + m − 1 ) (n+m-1) (n+m−1),故B的得分为 min ⁡ { n , m } \min\{n,m\} min{n,m}.

​ n n n个红方块和 m m m个蓝方块的排列中至多有 min ⁡ { n , m } \min\{n,m\} min{n,m}对相邻相异的颜色,

​ 该最大值可以达到,只需每次都放上一个位置异色的方块即可.

代码

void solve() {int n, m; cin >> n >> m;cout << max(n, m) - 1 << ' ' << min(n, m);
}int main() {solve();
}

276B. Girl and Game

原题指路:

题意 ( 2 s ) (2\ \{s}) (2s)

First和玩游戏,First先手.初始时给定一个只包含小写英文字母的字符串 s ( 1 ≤ ∣ s ∣ ≤ 1000 ) s\ \ (1\leq |s|\leq 1000) s(1≤∣s∣≤1000).每轮每人有操作:移除 s s s中的任一个字符.若玩家在操作前可通过重排 s s s使其变为一个回文串,则他获胜.两人都采取最优策略,问最后谁获胜.

思路

可重排 s s s使其变为一个回文串的充要条件是:至多有一个出现次数为奇数的字符.

显然胜当且仅当初始时 s s s有偶数个出现次数为奇数的字符.

代码

void solve() {string s; cin >> s;map cnt;  // 每个字符出现的次数for (auto ch : s) cnt[ch]++;int odd = 0;  // 出现次数为奇数的字符的个数for (auto [u, v] : cnt) odd += v & 1;cout << ((odd && odd % 2 == 0) ? "Second" : "First");
}int main() {solve();
}

293A. Weird Game

原题指路:

题意 ( 2 s ) (2\ \{s}) (2s)

A和B玩游戏,A先手.初始时A有一个长度为 2 n 2n 2n的 0 − 1 0-1 0−1串 s = s 1 ⋯ s 2 n s=s_1\cdots s_{2n} s=s1​⋯s2n​,B有一个长度为 2 n 2n 2n的 0 − 1 0-1 0−1串 t = t 1 ⋯ t 2 n t=t_1\cdots t_{2n} t=t1​⋯t2n​.每人每轮选择一个未被禁止的下标 i ∈ [ 1 , n ] i\in[1,n] i∈[1,n],将自己的串中下标 i i i的字符写在自己的纸上,并禁止下标 i i i.两人都无法操作时游戏结束,此时两人重排自己纸上写的数字分别得到一个二进制数,数较大者获胜,若二进制数相等则平局.问最后谁胜.

第一行输入一个整数 n ( 1 ≤ n ≤ 1 e 6 ) n\ \ (1\leq n\leq 1\{e}6) n(1≤n≤1e6).第二行输入一个长度为 2 n 2n 2n的 0 − 1 0-1 0−1串 s s s.第三行输入一个长度为 2 n 2n 2n的 0 − 1 0-1 0−1串 t t t.

思路

显然获得尽量多的 1 1 1的人胜,故最优策略是贪心地选未被禁止的 1 1 1,若无未被禁止的 1 1 1可选,则选对手的串有 1 1 1的位置.模拟该过程即可.

代码

void solve() {int n; string s, t; cin >> n >> s >> t;n <<= 1;int ans1 = 0, ans2 = 0;  // A和B拿到的1的个数int cnt = 0;  // s[i] = t[i] = 1的下标i的个数for (int i = 0; i < n; i++) {if (s[i] == '1' && t[i] == '1') cnt++;else if (s[i] == '1' && t[i] == '0') ans1++;else if (s[i] == '0' && t[i] == '1') ans2++;}if (cnt & 1) ans2--;  // B少拿一个s[i] = t[i] = 1的下标if (ans1 > ans2) cout << "First";else cout << (ans2 > ans1 + 1 ? "Second" : "Draw");
}int main() {solve();
}

346A. Alice and Bob

原题指路:

题意 ( 2 s ) (2\ \{s}) (2s)

Alice和Bob两人玩游戏,Alice先手.初始时给定一个整数集合 S S S.每轮玩家选两个相异的整数 x , y ∈ S x,y\in S x,y∈S,使得 ∣ x − y ∣ ∉ S |x-y|\not\in S ∣x−y∣∈S,并将 ∣ x − y ∣ |x-y| ∣x−y∣加入 S S S中,不能操作者负.问最后谁赢.

第一行输入一个整数 n ( 2 ≤ n ≤ 100 ) n\ \ (2\leq n\leq 100) n(2≤n≤100).第二行输入 n n n个相异的整数 a 1 , ⋯ , a n ( 1 ≤ a i ≤ 1 e 9 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 1\{e}9) a1​,⋯,an​(1≤ai​≤1e9).

思路

类似于闭包,无论中间过程,最后得到的集合都相同.设 g = gcd ⁡ 1 ≤ i ≤ n a i \ g=\gcd_{1\leq i\leq n}a_i g=1≤i≤ngcd​ai​,则最终集合为 { d , 2 d , 3 d , ⋯ , max ⁡ { x i } } \{d,2d,3d,\cdots,\max\{x_i\}\} {d,2d,3d,⋯,max{xi​}},故轮数为 max ⁡ { x i } d \dfrac{\max\{x_i\}}{d} dmax{xi​}​,判断其奇偶性即可.

代码

void solve() {int n; cin >> n;valarray a(n);int g = 0;  // gcdfor (auto& ai : a) {cin >> ai;g = gcd(g, ai);}int ans = a.max() / g - n;cout << (ans & 1 ? "Alice" : "Bob");
}int main() {solve();
}

546C. and Cards

原题指路:

题意 ( 2 s ) (2\ \{s}) (2s)

有 n n n张牌,分别写着 1 ∼ n 1\sim n 1∼n的 n n n个整数.A和B玩游戏,A先手.初始时将 n n n张牌以某种方式分配给A和B,每人拿到一叠牌.每轮每人从自己的牌堆中拿出顶上的牌比大小,点数较大者拿走对手的牌和自己的牌,先将对手的牌放在牌堆顶部,再将自己的牌放在牌堆顶部.手中无牌者负.若游戏能一直进行下去,输出 − 1 -1 −1;否则先输出游戏轮数,再输出胜者(A为 1 1 1,B为 2 2 2).

第一行输入一个整数 n ( 2 ≤ n ≤ 10 ) n\ \ (2\leq n\leq 10) n(2≤n≤10).第二行先输入一个整数 k 1 ( 1 ≤ k 1 ≤ n − 1 ) k_1\ \ (1\leq k_1\leq n-1) k1​(1≤k1​≤n−1),表示A手中的牌数.接下来输入 k 1 k_1 k1​个范围为 [ 1 , n ] [1,n] [1,n]的整数,从左往右依次表示A的牌堆从上到下的牌.第三行先输入一个整数 k 2 ( k 1 + k 2 = n ) k_2\ \ (k_1+k_2=n) k2​(k1​+k2​=n),表示B手中的牌数.接下来输入 k 2 k_2 k2​个范围为 [ 1 , n ] [1,n] [1,n]的整数,从左往右依次表示B的牌堆从上到下的牌.数据保证所有牌相异.

思路

n n n张牌有 n ! n! n!种排列,在 n n n张牌的任一排列的间隙中插隔板,左边为A的牌,右边为B的牌,有 ( n − 1 ) (n-1) (n−1)种方案,故总方案数为 n ! ⋅ ( n − 1 ) n!\cdot (n-1) n!⋅(n−1). n = 10 n=10 n=10时,方案数为 M A X _ R O U N D = MAX\= =.模拟游戏过程,若轮数超过 M A X _ R O U N D MAX\ 则游戏状态出现环,可一直进行下去.

代码

const int MAX_ROUND = 32659200;void solve() {int n; cin >> n;qi que1, que2;int k; cin >> k;while (k--) {int x; cin >> x;que1.push(x);}cin >> k;while (k--) {int x; cin >> x;que2.push(x);}int round;for (round = 0; round <= MAX_ROUND && que1.size () && que2.size(); round++) {int a = que1.front(); que1.pop();int b = que2.front(); que2.pop();if (a > b) que1.push(b), que1.push(a);else que2.push(a), que2.push(b);}if (que1.size() && que2.size()) cout << -1;else if (que1.size()) cout << round << " 1";else cout << round << " 2";
}int main() {solve();
}

570B. Game

原题指路:

题意

给定两个整数 n , m ( 1 ≤ n , m ≤ 1 e 9 ) n,m\ \ (1\leq n,m\leq 1\{e}9) n,m(1≤n,m≤1e9).选一个整数 a ∈ [ 1 , n ] s . t . ∣ c − a ∣ < ∣ c − m ∣ a\in[1,n]\ s.t.\ |c-a| 2 m − 1 n>2m-1 n>2m−1,亦即 n ≥ 2 m n\geq 2m n≥2m时,取 a = m + 1 a=m+1 a=m+1;否则取 a = m − 1 a=m-1 a=m−1.

注意 a = m − 1 a=m-1 a=m−1当 m = 1 m=1 m=1时 a = 0 ∉ [ 1 , n ] a=0\notin[1,n] a=0∈/[1,n],故需特判 n = m = 1 n=m=1 n=m=1的情况或 ( m − 1 ) (m-1) (m−1)与 1 1 1取 max ⁡ \max max.

代码

void solve() {int n, m; cin >> n >> m;if (n == 1 && m == 1) cout << 1;else cout << (n >= 2 * m ? m + 1 : m - 1);
}int main() {solve();
}