当前位置:网站首页>【集训DAY10】Silly【模拟】【贪心】
【集训DAY10】Silly【模拟】【贪心】
2022-07-21 07:15:00 【VL——MOESR】
思路:
我们发现它的比值就是原串w和b的个数比。
那我们就直接一段一段去模拟就行了。
c o d e code code
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll MAXN = 1e5 + 10;
ll t, n;
struct node {
char ch;
ll x;
}a[MAXN];
ll gcd(ll x, ll y) {
if(y == 0) return x;
else return gcd(y, x % y);
}
ll ji(ll x, ll y, ll z) {
return x * z / y;
}
ll sum(ll x, ll y) {
// w b
ll w = 0, b = 0, len = 0;
for(ll i = 1; i <= n; i ++) {
if(a[i].ch == 'B') {
if(w * y % x == 0)
if(b < ji(w, x, y) && b + a[i].x >= ji(w, x, y)) len ++;
b += a[i].x;
}
if(a[i].ch == 'W') {
if(b * x % y == 0)
if(w < ji(b, y, x) && w + a[i].x >= ji(b, y, x)) len ++;
w += a[i].x;
}
}
return len;
}
int main() {
freopen("silly.in", "r", stdin);
freopen("silly.out", "w", stdout);
scanf("%lld", &t);
while(t--) {
scanf("%lld", &n);
ll b = 0, w = 0;
for(ll i = 1; i <= n; i ++) {
scanf("%lld %c", &a[i].x, &a[i].ch);
if(a[i].ch == 'W') w += a[i].x;
else b += a[i].x;
}
if(w == 0) {
printf("%lld\n", b);
continue;
}
if(b == 0) {
printf("%lld\n", w);
continue;
}
ll k = gcd(b, w);
b /= k, w /= k;
ll len = sum(w, b);
printf("%lld\n", len);
}
return 0;
}
边栏推荐
- 44: Chapter 4: develop file service: 5: integrate fastdfs in [files] file service to realize the logic of [upload avatar]; (including: integrating fastdfs in the project; cross domain issues; creating
- Cloud foundry 4: application lifecycle
- Problems and principle analysis of audio AGC
- 铜牛机房项目的优势和劣势
- Visualization: you must know these ten data visualization tool software platforms
- Houdini building rigid body area influence breaking notes
- Introduction to common interfaces of vector
- StarkNet如何改变L2格局?
- SSM整合其他组件
- 小程序 奇葩BUG 更新~
猜你喜欢
44: Chapter 4: develop file service: 5: integrate fastdfs in [files] file service to realize the logic of [upload avatar]; (including: integrating fastdfs in the project; cross domain issues; creating
应用层——典型协议解析
44:第四章:开发文件服务:5:在【files】文件服务中,整合FastDFS,实现【上传头像】的逻辑;(包括:项目中整合FastDFS;跨域问题;创建资源文件,并在代码中获取属性;异常处理;)
数据库连接池
LeetCode 1911. 最大子序列交替和
[dongle vulnerability notification] Apache spark command injection vulnerability scheme
Selenium被检测为爬虫,怎么屏蔽和绕过
零基础转行软件测试学习要不要报培训班学习,还是自学好?
LeetCode 1928. 规定时间内到达终点的最小花费
Detailed explanation and typical cases of multi-agent system cluster collaborative control experimental platform
随机推荐
KY novel collection rules (5 collection rules)
Leetcode [sword finger offer II 068. find the insertion position
软件测试面试小技巧 | 如果你没收到offer我倒立洗头
如何理解指针?
uniapp,微信小程序input正则校验只能输入为数字和小数点位数限制
malloc 和 空间配置器
(pytorch advanced road VI) implementation of swing transformer
uniapp 使用 u-view 框架小程序的样式问题集合
Chrome实现自动化测试:录制回放网页动作
vector的常见接口介绍
47:第四章:开发文件服务:8:图片自动审核(阿里云内容安全);(还没写,别看;待写……)
token和session的区别,这个经典面试题值得一个更深入的回答
lua环境配置
Share 50 free cloud disk and online disk Services - with unlimited storage space
Qt:qstring and qstringlist
Installation du gestionnaire de loisirs
Detailed explanation and typical cases of multi-agent system cluster collaborative control experimental platform
Framework - WindowManager (window management service) practice of WMS
Mysql08 (transaction)
The NSLOOKUP command uses