Codeforces Round #590 (Div. 3)：点击进入新世界

总结：

第二次实时打cf,刚开始四分钟就且切了A题，后面看了B1 B2 难度改变对思路没有影响，一开始思路是对的，但是用hash数组没考虑数组下标爆1e9，两题提交都出现RE，还以为是数组开小了，改了数组大小再次提交依旧RE后，才发现hash数组的毛病，后面改用map直接切了B1 B2, 开局半小时切三题（没有失误的话应该是十五分钟）以为这一次能够破四题，没想到后面的CDEF一直做不出来。 没失误的理想排名2000+ 实际排名3000+ （B1 2发RE B2 1发RE） 估计掉了100左右分

文章目录

总结：A. Equalize Prices Again（思维）B1. Social Network (easy version)（模拟）B2. Social Network (hard version)（模拟同上）C. Pipes（模拟 or 思维）D. Distinct Characters Queries（set的运用）

A. Equalize Prices Again（思维）

原题链接：传送门

思路：

题目给出n个货物的价格，让你求出一个所有货物的共同价格保证全部货物卖不出商家不亏本。很简单直接求平均数，如果平均数带小数点就加一否则商家亏死。 代码如下： #include<bits/stdc++.h> using namespace std; const int manx=1e3; int a[manx]; int main() { int q; cin>>q; while(q--) { long long n; long long ans=0; cin>>n; for(int i=1;i<=n;i++) cin>>a[i],ans+=a[i]; if(ans%n==0) cout<<ans/n<<endl; else cout<<ans/n+1<<endl; } return 0; }

B1. Social Network (easy version)（模拟）

原题链接：传送门

思路：

题目给出n个数字和容量k，让你求出最后容器中剩下的数字。用map标记是否还在容器中，用双端队列进行模拟即可。

AC代码如下：

#include<bits/stdc++.h> using namespace std; const int manx=2e5+5; typedef long long ll; map<int,int>vis; int main() { int n,k,ans=0; scanf("%d%d",&n,&k); deque<int>q; while(q.size()) q.pop_back(); for(int i=1;i<=n;i++) { int a; scanf("%d",&a); if(!vis[a]){ if(ans==k){ int b=q.back(); q.pop_back(); ans--,vis[b]=0; } q.push_front(a),ans++,vis[a]=1; } } cout<<q.size()<<endl; while(q.size()) { cout<<q.front()<<" "; q.pop_front(); } return 0; }

B2. Social Network (hard version)（模拟同上）

原题链接：传送门

思路：

题目给出n个数字和容量k，让你求出最后容器中剩下的数字。用map标记是否还在容器中，用双端队列进行模拟即可。这道题不过是n,k范围变大，我模拟的思路时间复杂度为O(n)，边输入边操作，所以莫得问题。

AC代码如下：

#include<bits/stdc++.h> using namespace std; const int manx=2e5+5; typedef long long ll; map<int,int>vis; int main() { int n,k,ans=0; scanf("%d%d",&n,&k); deque<int>q; while(q.size()) q.pop_back(); for(int i=1;i<=n;i++) { int a; scanf("%d",&a); if(!vis[a]){ if(ans==k){ int b=q.back(); q.pop_back(); ans--,vis[b]=0; } q.push_front(a),ans++,vis[a]=1; } } cout<<q.size()<<endl; while(q.size()) { cout<<q.front()<<" "; q.pop_front(); } return 0; }

明天起来再补题

C. Pipes（模拟 or 思维）

原题链接：传送门

思路：

给出两种类型的水管，判断水流是否能够从（1，0）到（2，n+1）。比赛的时候想过bfs，又不够坚定，一直想找出规律，后来比赛结束了也没时间做。官方题解是很不错的模拟，用异或来决定水流位于那一行，判断是否能够流到最后。

AC代码如下：

#include<bits/stdc++.h> using namespace std; int main() { int q; cin>>q; while(q--) { int n; string s[2]; cin>>n>>s[0]>>s[1]; int l=0,r=0; for(l=0;l<n;l++) { if(s[r][l]>='3'){ if(s[r^1][l]<'3') break; else r^=1; } } if(l==n&&r==1) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }

D. Distinct Characters Queries（set的运用）

原题链接：传送门

思路：

在线修改字符，查询区间不同字符数目。一开始想用线段树，但是不怎么会线段树，只会简单的区间求和操作，后面改用set，做法和答案有点差距，但是真的没想到还可以这么操作。统计每个字母的下标。用set来快速删除加入元素。

AC代码如下：

#include<bits/stdc++.h> using namespace std; const int manx=2e5+50; char a[manx]; set<int>s[50]; int x,l,r,q,n; char c; int main() { scanf("%s%d",a+1,&q); n=strlen(a+1); for(int i=1;i<=n;i++) s[a[i]-'a'].insert(i); while(q--) { scanf("%d",&x); if(x==2){ scanf("%d%d",&l,&r); int ans=0; for(int i=0;i<26;i++) { auto it=s[i].lower_bound(l); if(it!=s[i].end()&&*it<=r) ans++; } printf("%d\n",ans); } else if(x==1){ cin>>l>>c; s[a[l]-'a'].erase(l); s[c-'a'].insert(l); a[l]=c; } } return 0; }