Codeforces Round 927 (Div. 3)（A~E)

2024-02-19 15:04
文章标签 codeforces round div 927

本文主要是介绍Codeforces Round 927 (Div. 3)（A~E)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Codeforces Round 927 (Div. 3) (A~E)

目录：A B C D E

A题：Thorns and Coins

标签: 动态规划（dp）贪心（greedy）实现问题，编程技巧，模拟（implementation）

题目大意

  • 由 n个连续单元组成的路径，每个单元可以是空的，含有荆棘，或者含有一枚硬币，在一次移动中，你可以沿着路径移动一个或两个单元，前提是目标单元不含有荆棘（并且属于路径）如果你移动到含有硬币的单元，你就会捡起它。
  • 问：找出你从路径的最左端开始能够收集到的最大硬币数量。

思路

  • 可以一直走下去直到遇见连续两个荆棘地导致跨不过去

AC代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{int n;string s;cin >> n >> s;int i = s.find("**");if (i == -1) i = s.size();int ans = count(s.begin(), s.begin() + i, '@');cout << ans << "\n";
}  
int main()
{int T; cin >> T;while(T--)solve();return 0; 
}

B题：Chaya Calendar

标签: 数论（number theory）

题目大意

  • 有 n个迹象。给定数组a代表每个迹象出现的周期。
  • 第一个迹象出现，第二个迹象才会出现，然后严格按照这个顺序。
  • 问：第 n 个迹象将在哪一年发生

思路

  • 对于每个迹象 ai，观测到它的时间都是从观测前 i−1 个启示的时间以后，第一个 ai的倍数

AC代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{int n, x = 0; cin >> n;for (int i = 0; i < n; i++) {int a; cin >> a;// 上一个迹象在x年发生，找到大于x的第一个a的倍数// x - x % a 去除尾数，在往后一个即可 x = x - x % a + a;}cout << x << "\n";
}  
int main()
{int T; cin >> T;while(T--)solve();return 0; }

C题：LR-remainders

标签: 暴力枚举（brute force）数据结构（data structures）实现问题，编程技巧，模拟（implementation）数学（math）

题目大意

  • 给你一个长度为 n 的数组 a、一个正整数 m 和一串长度为 n的命令串s。每条命令要么是字符 “L”，要么是字符 “R”
  • 按照字符串 s中的顺序处理所有n条命令。处理一条命令的步骤如下：
    1. 首先，输出数组 a 中所有元素乘积最后对 m 取模后的结果。
    1. 然后，如果命令是 “L”，则从数组 a 中删除最左边的元素；如果命令是 “R”，则从数组 a 中删除最右边的元素。
  • 注意，每次移动后，数组 a的长度都会减少1 ，处理完所有命令后，数组 a将为空。

思路

  • 要求每个操作前所有元素乘积对m的模数，正着求数字相乘会很大，并且左右都会变化无法用前缀和，但是倒着求，每次添加一个元素，就有一个固定的顺序
  • 总结：倒着求即可，具体看代码

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int p[N], a[N], ans[N];
void solve()
{int n, m;cin >> n >> m;for(int i = 1;i <= n; i++)cin >> a[i];string s; cin >> s;int l = 1, r = n;// 将每次要删除的数下标储存到p数组 for(int i = 0; i < n; i++)if(s[i] == 'L') p[i+1] = l++;else p[i+1] = r--;int mul = 1; // 倒序遍历p数组累求积 并对m取模 for(int i = n; i >= 1; i--){mul = mul * a[p[i]] % m;ans[i] = mul;}for(int i = 1; i <= n; i++)cout << ans[i] <<" \n"[i == n];
}  
int main()
{int T; cin >> T;while(T--)solve();return 0; }

D题：Card Game

标签: 贪心策略（greedy）实现问题，编程技巧，模拟（implementation）

题目大意

  • 两名玩家正在玩一款在线纸牌游戏。游戏使用一副 32 张牌。每张牌都有花色和等级。共有四种花色：梅花、方块、红心和黑桃。我们将分别用字符 “C”、“D”、"H "和 "S "对它们进行编码。共有 8 个等级，依次递增：‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’.
  • 游戏开始时，选择一种花色作为王牌花色。
  • 在每一轮游戏中，玩家都要这样出牌：第一位玩家将自己的一张牌放在桌上，第二位玩家必须用自己的一张牌击败这张牌。之后，两张牌都被移至弃牌堆。
  • 如果两张牌的花色相同，且第一张牌的等级高于第二张牌，那么这张牌就能打败另一张牌。例如，8S 可以打败 4S。例如，如果王牌花色是梅花(“C”)，那么 3C 可以击败 9D。请注意，王牌只能被等级更高的王牌击败。
  • 游戏中一共进行了 n轮，请找出游戏中可能出现的 n 个回合，如果有多个解法，则打印其中任何一个，如果无解，则打印一行 “IMPOSSIBLE”。

思路

  • 先看除了王牌以外的三种花色，给他们两两配对，如果存在单出来的一张牌，就用一张王牌管住他。最后再给王牌两两配对。

AC代码

#include<bits/stdc++.h>
using namespace std;
int th[128];
void solve(){int n; char t;cin >> n >> t;vector<string> o[4];for(int i = 0; i < 2 * n; i++){string s; cin >> s;o[th[s[1]]].push_back(s);}for(int i = 0; i < 4; i++) sort(o[i].begin(), o[i].end());vector<string> k;for(int i = 0;i < 4; i++){if(i == th[t] || o[i].size()%2 == 0) continue;k.push_back(o[i].back());o[i].pop_back();}if(o[th[t]].size() < k.size()){cout << "IMPOSSIBLE\n";return;}for(int i = 0; i < k.size(); i++){cout << k[i] << ' ' << o[th[t]].back() << '\n';o[th[t]].pop_back();}for(int i = 0; i < 4; i++)for(int j = 0;j < o[i].size(); j += 2)cout << o[i][j] << ' ' << o[i][j+1] << '\n';
}
int main(){th['C'] = 0;th['D'] = 1;th['H'] = 2;th['S'] = 3;int T; cin >> T;while(T--) solve();
}

E题：Final Countdown

标签: 实现问题，编程技巧，模拟（implementation）数学（math）数论（number theory）

题目大意

  • 倒计时由 n ( 1≤n≤ 4⋅105) 个机械指示器组成，每个指示器显示一位小数。当倒计时的状态从 x 变为 x−1 时，并不每个数字的变化都需要一秒钟。
  • 因此，举例来说，如果倒计时显示 42，那么它将在一秒钟内变为 41，因为只有一位数发生了变化；但如果倒计时显示 2300，那么它将在三秒钟内变为 2299，因为最后三位数发生了变化。
  • 找出倒计时归零前还剩多少时间。

思路

  • 要求归零需要多少时间，即求x的所有位需要改变多少次
  • 各位上的数字每1秒变化一次，十位上的数字每10秒变化一次，百位上的数字每100秒变化一次…
  • 所以答案为：x + x / 10 + x / 100 + x / 1000…
  • 用前缀和求出每一位要加的数然后加上进位即可
  • 例如12345，答案为12345 + 1234 + 123 + 12 + 1 = 13715
    在这里插入图片描述

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 400010;
int f[N];
void solve(){int n;string s;cin >> n >> s;for(int i = 0; i < n; i++){f[i+1] = s[i] - '0';f[i+1] += f[i];}vector<int> res;int t = 0;for(int i = n; i >= 1; i--){res.push_back((f[i] + t) % 10);t = (f[i] + t)/ 10;}if(t != 0) res.push_back(t);while(res.back() == 0)res.pop_back();for(int i = res.size() - 1; i >= 0; i--)cout << res[i]; cout << "\n";
} 
int main(){int T; cin >> T;while(T--) solve();
}

logo

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　⊂⊃〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//

/*__   _,--="=--,_   __/  \."    .-.    "./  \/  ,/  _   : :   _  \/` \\  `| /o\  :_:  /o\ |\__/`-'| :="~` _ `~"=: |\`     (_)     `/.-"-.   \      |      /   .-"-.
.---{     }--|  /,.-'-.,\  |--{     }---.)  (_)_)_)  \_/`~-===-~`\_/  (_(_(_)  (
(                         				))                                     (
'---------------------------------------'
*/

这篇关于Codeforces Round 927 (Div. 3)（A~E)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/725034。

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...
Codeforces Round #261 (Div. 2)小记

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件，我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m
阅读更多...
Codeforces Beta Round #47 C凸包 （最终写法）

Codeforces Beta Round #47 C凸包 （最终写法）

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op
阅读更多...
Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A， 多边形B， 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包，如果凸包上的点是B的某个点，则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法，只需在求凸包的时候， <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int
阅读更多...
Codeforces 482B 线段树

Codeforces 482B 线段树

求是否存在这样的n个数； m次操作，每次操作就是三个数 l ，r，val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja
阅读更多...
CSS实现DIV三角形

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor
阅读更多...
创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动

创建一个大的DIV，里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;
阅读更多...
Codeforces Round 971 (Div. 4) (A~G1)

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单，不做解释 C 对于 x y 两个方向，每一个方向至少需要 x / k 向上取整的步数，取最大值。 由于 x 方向先移动，假如 x 方向需要的步数多于 y 方向的步数，那么最后 y 方向的那一步就不需要了，答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>
阅读更多...
CF#271 (Div. 2) D.（dp）

CF#271 (Div. 2) D.（dp）

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/474/problem/D We s
阅读更多...
CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

CF #278 (Div. 2) B.（暴力枚举+推导公式+数学构造）

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接： http://codeforces.com/contest/488/problem/B There
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2