![[Codeforces] games (R1600) Part.1](/uploads/image/0932.jpg)
题单:=games,1201-1600
原题指路:
偷渡者(Stowaway)和管理员(Controller)在火车上玩游戏.火车有编号 1 ∼ n 1sim 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 (2leq nleq 50,1leq m,kleq n,mneq 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();
}
原题指路:
一个位于红色格子的骑士能攻击到所有蓝色格子.A和B轮流在在一个 n × n ntimes n n×n棋盘上放置一个骑士,使得任意两骑士间不能互相攻击,A先手.两人都采取最优策略,若最后A胜,输出 0 0 0;否则输出 1 1 1.
有 t ( 1 ≤ t ≤ 100 ) t (1leq tleq 100) t (1≤t≤100)组测试数据.每组测试数据输入一个整数 n ( 1 ≤ n ≤ 1 e 4 ) n (1leq nleq 1mathrm{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();
}
原题指路:
A和B两人玩游戏,A先手.初始时纸上有一个整数 n n n,每轮每人写出一个上一个写的数的非平凡因子(非 1 1 1和它本身的因子),不能操作者胜.给定 n ( 1 ≤ n ≤ 1 e 13 ) n (1leq nleq 1mathrm{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();
}
原题指路:
A和B轮流在一个 a × b atimes b a×b的矩形桌子上放置半径为 r r r的圆盘,A先手,要求圆盘间不能重叠,圆盘不能超出桌子区域,无法放置者负.两人都采取最优策略,问谁胜.
第一行输入三个整数 a , b , r ( 1 ≤ a , b , r ≤ 100 ) a,b,r (1leq a,b,rleq 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();
}
原题指路:
有 n n n个红方块和 m ( 1 ≤ n , m ≤ 1 e 5 ) m (1leq n,mleq 1mathrm{e}5) m (1≤n,m≤1e5)个蓝方块.A和B轮流将方块排成一条线,A先手.每轮每人选一个剩下的方块,接在已经排好的线最后.所有方块排完后,A的得分是相邻两个方块颜色相同的对数,B的得分是相邻两个方块颜色不同的对数.两人都想最大化自己的得分并都采取最优策略,问他们两人最后的得分.
最优策略:A每次放置与上一个位置同色的方块,B每次放置与上一个位置异色的方块.
①对A,前 2 min { n , m } 2min{n,m} 2min{n,m}轮中只有A自己放置的操作才能得分.
之后的 ( n + m − 2 min { n , m } ) (n+m-2min{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-2min{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();
}
原题指路:
First和Second玩游戏,First先手.初始时给定一个只包含小写英文字母的字符串 s ( 1 ≤ ∣ s ∣ ≤ 1000 ) s (1leq |s|leq 1000) s (1≤∣s∣≤1000).每轮每人有操作:移除 s s s中的任一个字符.若玩家在操作前可通过重排 s s s使其变为一个回文串,则他获胜.两人都采取最优策略,问最后谁获胜.
可重排 s s s使其变为一个回文串的充要条件是:至多有一个出现次数为奇数的字符.
显然Second胜当且仅当初始时 s s s有偶数个出现次数为奇数的字符.
void solve() {string s; cin >> s;map<char, int> 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();
}
原题指路:
A和B玩游戏,A先手.初始时A有一个长度为 2 n 2n 2n的 0 − 1 0-1 0−1串 s = s 1 ⋯ s 2 n s=s_1cdots s_{2n} s=s1⋯s2n,B有一个长度为 2 n 2n 2n的 0 − 1 0-1 0−1串 t = t 1 ⋯ t 2 n t=t_1cdots t_{2n} t=t1⋯t2n.每人每轮选择一个未被禁止的下标 i ∈ [ 1 , n ] iin[1,n] i∈[1,n],将自己的串中下标 i i i的字符写在自己的纸上,并禁止下标 i i i.两人都无法操作时游戏结束,此时两人重排自己纸上写的数字分别得到一个二进制数,数较大者获胜,若二进制数相等则平局.问最后谁胜.
第一行输入一个整数 n ( 1 ≤ n ≤ 1 e 6 ) n (1leq nleq 1mathrm{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();
}
原题指路:
Alice和Bob两人玩游戏,Alice先手.初始时给定一个整数集合 S S S.每轮玩家选两个相异的整数 x , y ∈ S x,yin S x,y∈S,使得 ∣ x − y ∣ ∉ S |x-y|notin S ∣x−y∣∈S,并将 ∣ x − y ∣ |x-y| ∣x−y∣加入 S S S中,不能操作者负.问最后谁赢.
第一行输入一个整数 n ( 2 ≤ n ≤ 100 ) n (2leq nleq 100) n (2≤n≤100).第二行输入 n n n个相异的整数 a 1 , ⋯ , a n ( 1 ≤ a i ≤ 1 e 9 ) a_1,cdots,a_n (1leq a_ileq 1mathrm{e}9) a1,⋯,an (1≤ai≤1e9).
类似于闭包,无论中间过程,最后得到的集合都相同.设 g = gcd 1 ≤ i ≤ n a i displaystyle g=gcd_{1leq ileq n}a_i g=1≤i≤ngcdai,则最终集合为 { 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<int> 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();
}
原题指路:
有 n n n张牌,分别写着 1 ∼ n 1sim 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 (2leq nleq 10) n (2≤n≤10).第二行先输入一个整数 k 1 ( 1 ≤ k 1 ≤ n − 1 ) k_1 (1leq k_1leq 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 = 32659200 MAX_ROUND=32659200 MAX_ROUND=32659200.模拟游戏过程,若轮数超过 M A X _ R O U N D MAX_ROUND MAX_ROUND则游戏状态出现环,可一直进行下去.
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();
}
原题指路:
给定两个整数 n , m ( 1 ≤ n , m ≤ 1 e 9 ) n,m (1leq n,mleq 1mathrm{e}9) n,m (1≤n,m≤1e9).选一个整数 a ∈ [ 1 , n ] s . t . ∣ c − a ∣ < ∣ c − m ∣ ain[1,n] s.t. |c-a|<|c-m| a∈[1,n] s.t. ∣c−a∣<∣c−m∣的概率最大,其中 c c c等概率地取 1 ∼ n 1sim n 1∼n内的整数.
∣ c − a ∣ < ∣ c − m ∣ |c-a|<|c-m| ∣c−a∣<∣c−m∣即随机出的 c c c距 a a a比距 m m m近.
最优策略取 a = m ± 1 a=mpm 1 a=m±1,否则 a a a与 m m m间的整数中离 m m m更近的数更多,这是不优的.
① a = m − 1 a=m-1 a=m−1时,符合条件的 c ∈ [ 1 , m − 1 ] cin [1,m-1] c∈[1,m−1],有 ( m − 1 ) (m-1) (m−1)个.
② a = m + 1 a=m+1 a=m+1时,符合条件的 c ∈ [ m + 1 , n ] cin[m+1,n] c∈[m+1,n],有 ( n − m ) (n-m) (n−m)个.
故 n − m > m − 1 n-m>m-1 n−m>m−1,即 n > 2 m − 1 n>2m-1 n>2m−1,亦即 n ≥ 2 m ngeq 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=0notin[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();
}
本文发布于:2024-01-31 05:55:59，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170665176226029.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
