Codeforces #528 Div2 F (1087F) Rock-Paper-Scissors Champion 树状数组+set
2024-08-25 10:02:19
题意:n个人站成一排,初始时刻每个人手中都有一个图案,可能是石头,剪刀,布3个中的1种,之后会随机选取相邻的两个人玩石头剪刀布的游戏,输的人会离开(如果两个人图案相同,则随机选择一个人离开)。执行(n-1)次操作剩下的最后一个人是冠军,问有多少个人可能成为最后的冠军?并且还有m次修改,每次修改会改变某个人的图案,并且要输出修改后可能成为冠军的人数。
思路:为了方便叙述,我们把石头,剪刀,布记为0,1,2,并且0大于2,2小于0。通过观察,我们很容易可以发现如果一个人可能成为冠军必须满足以下两个条件之一:
1:这个人的左右两边没有人的图案比他大(左边或右边没人也看作没人比他大)。
2:这个人的某一边既有比他大的,也有比他小的。
稍微解释一下条件2:这边比他大的图案都有可能被这这比他小的图案吃掉,因为这个比他小的图案比比他大的图案大。比如:0 1 2 。虽然1比0大,但是有比0小的2的存在,2可以把1吃掉。
把条件1和条件2合并一下,只要两边都有小于它的图案,无论什么情况都肯成为冠军。假设该数为x,比他小的数为y,最左端y的位置记为l,最右端的记为r,则[l,r]中所有x都可能成为冠军。
对于剩余的情况,比如左端中没在[l.r]中的数x,可能成为冠军的情况只能是左端没有大于他的数,右端同理。
于是我们可以用树状数组查询区间的个数,set维护每个数的位置。
代码:
#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
const int maxn=200010;
int n,m;
struct BIT{
int c[maxn]; void add(int x,int y){
for(;x<=n;x+=lowbit(x))c[x]+=y;
} int ask(int x){
int ans=0;
for(;x;x-=lowbit(x))ans+=c[x];
return ans;
} int query(int l,int r){
return ask(r)-ask(l-1);
}
};
BIT b[3];
set<int> s[3];
map<char,int> mp;
int a[maxn];
char str[maxn];
int solve(void){
int ans=0;
for(int i=0;i<3;i++){
if(s[(i+1)%3].empty()){
ans+=s[i].size();
continue;
}
if(s[(i+2)%3].empty())continue;
int l1=*(s[(i+2)%3].begin()),r1=*(--s[(i+2)%3].end());
ans+=b[i].query(l1,r1);
int l2=*(s[(i+1)%3].begin()),r2=*(--s[(i+1)%3].end());
ans+=b[i].query(1,min(l1,l2)-1);
ans+=b[i].query(max(r1,r2)+1,n);
}
return ans;
}
int main(){
mp['R']=0,mp['P']=1,mp['S']=2;
scanf("%d%d",&n,&m);
scanf("%s",str+1);
for(int i=1;i<=n;i++){
a[i]=mp[str[i]];
b[a[i]].add(i,1);
s[a[i]].insert(i);
}
printf("%d\n",solve());
for(int i=1;i<=m;i++){
int x;
scanf("%d%s",&x,str+1);
b[a[x]].add(x,-1);
s[a[x]].erase(x);
a[x]=mp[str[1]];
b[a[x]].add(x,1);
s[a[x]].insert(x);
printf("%d\n",solve());
}
}
最新文章
- php 导出对象生成代码并执行var_export和eval
- Android在一个Activity中关闭另一个Activity
- linux内核分析 第八周
- JS设计模式——5.单体模式
- 使用 cloc 统计代码行数
- Java vs Python
- 本人对于JavaScript的一些总结
- Codeforces 353D Queue(构造法)
- 第一个jdbc
- Win10 将slim加入PYTHONPYTH
- bootstrap modal 点击头部移动
- 04-体验一下apache组织封装的BeanUtil工具包
- SNF快速开发平台--规则引擎整体介绍及使用说明书
- 有趣的console.log(console.log输出彩色字,图片等)
- orika实现对象复制
- Link1123:转换到COFF期间失败:文件无效或损坏
- nodejs(一)process模块
- python-day43--单表查询之关键字执行优先级(重点)
- 运行quectel EC20 module example data
- 14 - 函数参数检测-inspect模块
热门文章
- Python爬虫之利用BeautifulSoup爬取豆瓣小说(三)——将小说信息写入文件
- Unity3D重要知识点(转)
- fasttext和cnn的比较,使用keras imdb看效果——cnn要慢10倍。
- axios 拦截 , 页面跳转, token 验证(自己摸索了一天搞出来的)
- Spring与RMI集成实现远程访问
- JDK自动安装脚本
- ugui Event.current.mousePosition获取的坐标原点在左上角
- Android UI--提高Android UI体验
- Windbg内核调试之三: 调试驱动
- Linux基础命令-文本文件查看工具