Codeforces Round #590 (Div. 3) 训练总结及A-F题解
总结：A5mins ac，B过的慢22mins ac，接着就被c卡了一小时1小时ac，写到了d题，因为打星练了下手速，无板子17mins ac还算不错，e是个差分，f思维题。
总结:
- C题想多一点，就节省了很多代码量。
- E题要静下心写。
题解：
A.
题意：00个货物，价格不一。使所有货物价格变为一个价格，且新总价格>=原sum且要求变动最小。
思路：-1找到平均值+1
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0)
const int inf = 2e9+5;
const ll INF = 2e18+5;
int main(){
IO;cout.precision(10);cout<<fixed;
int t;cin>>t;
while(t--){
int n;cin>>n;
int sum = 0;
forn(i,n){
int x;cin>>x;
sum+=x;
}
sum--;
sum/=n;
sum++;
sum;
cout<<sum<<'
';
}
return 0;
}
B.
题意：2e5个数，你的显示器每次只能显示k个数，按顺序来如果新来的数字在显示器上，则不更新显示器，如果超过k个数，挤掉显示器进入最早的数。
思路：维护一个set来确定进不进，维护一个deque来确定删哪个。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0)
const int inf = 2e9+5;
const ll INF = 2e18+5;
int main(){
IO;cout.precision(10);cout<<fixed;
set<int>s;
deque<int>ans;
int n,k;cin>>n>>k;
forn(i,n){
int x;cin>>x;
if(s.find(x)!=s.end()) continue;
if(ans.size()<k){
s.insert(x);
ans.push_back(x);
continue;
}
int y = ans.front();ans.pop_front();
s.erase(s.find(y));
s.insert(x);ans.push_back(x);
}
cout<< ans.size() <<'
';
while(!ans.empty()){
cout<<ans.back()<<' ';
ans.pop_back();
}
return 0;
}
C
题意：如图从左上走到右下，地图大小2*n(n2e5)，每个管道可以旋转。问能否走出去。
思路：bfs或者按顺序走就可以。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0)
const int inf = 2e9+5;
const ll INF = 2e18+5;
struct node{
int x,y,p;
};
const int maxn = 2e5+5;
bool vis[2][maxn];
int dy[] = {0,0,1},dx[] = {1,-1,0};
int main(){
IO;cout.precision(10);cout<<fixed;
int t;cin>>t;
while(t--){
int n;cin>>n;
string s[2];cin>>s[0]>>s[1];
queue<node>q;
node now = {0,0,2};
bool ok = 0;
q.push(now);
while(!q.empty()){
now = q.front();q.pop();
int x = now.x,y = now.y,p = now.p;
//cerr<<"@!#!@# "<<x<<' '<<y<<'
';
if(x==1&&y==n-1){
//cerr<<"@!@!#@!#@! "<<s[x][y]<<' '<<p<<'
';
if(s[x][y]>='1'&&s[x][y]<='2'){
if(p==2) ok = 1;
}else{
if(p==0) ok = 1;
}
}
if(s[x][y]>='1'&&s[x][y]<='2'){
if(p!=2) continue;
int nx = x+dx[2],ny = y+dy[2];
if(nx<0||nx>1||ny<0||ny==n)continue;
if(vis[nx][ny]) continue;
vis[nx][ny] = 1;
q.push({nx,ny,2});
}else{
if(p!=2){
int nx = x+dx[2],ny = y+dy[2];
if(nx<0||nx>1||ny<0||ny==n)continue;
if(vis[nx][ny]) continue;
vis[nx][ny] = 1;
q.push({nx,ny,2});
}else{
forn(i,2){
int nx = x+dx[i],ny = y+dy[i];
if(nx<0||nx>1||ny<0||ny==n)continue;
if(vis[nx][ny]) continue;
vis[nx][ny] = 1;
q.push({nx,ny,i});
}
}
}
}
if(!ok) cout<<"NO"<<'
';
else cout<<"YES"<<'
';
forn(i,2) forn(j,n) vis[i][j] = 0;
}
return 0;
}
D.
题意：1e5的字符串，两种操作：1.修改某位置字符 2.查询区间字符不相同数。
思路：线段树，字母表对应二进制的位数，用或操作。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0)
const int inf = 2e9+5;
const ll INF = 2e18+5;
const int maxn = 1e5+5;
int a[maxn],n,now;
class segment_tree{
public:
#define nd node[now]
#define ndl node[now<<1]
#define ndr node[now<<1|1]
struct segement_node{
int l,r,v;
}node[maxn<<2];
void pushup(int now){
nd.v = ndl.v|ndr.v;
}
void maketree(int l,int r,int now = 1){
nd = {l,r,0};
if(l==r){
nd.v = (1<<a[l]);
return;
}
maketree(l,l+r>>1,now<<1);
maketree((l+r>>1)+1,r,now<<1|1);
pushup(now);
}
void update(int pos,int v,int now = 1){
if(nd.l==nd.r){
nd.v = (1<<v);
return;
}
if(pos<=ndl.r) update(pos,v,now<<1);
else update(pos,v,now<<1|1);
pushup(now);
}
int query(int l,int r,int now = 1){
if(l<=nd.l&&r>=nd.r) return nd.v;
int res = 0;
if(l<=ndl.r) res|=query(l,r,now<<1);
if(r>=ndr.l) res|=query(l,r,now<<1|1);
return res;
}
}tree;
int main(){
IO;cout.precision(10);cout<<fixed;
string s;cin>>s;
n = s.size();
for1(i,n) a[i] = s[i-1]-'a';
tree.maketree(1,n);
int q;cin>>q;
while(q--){
int op;cin>>op;
if(op==1){
int pos;char c;cin>>pos>>c;
int v = c-'a';
tree.update(pos,v);
}else{
int l,r;cin>>l>>r;
int x = tree.query(l,r),res = 0;
forn(i,26){
int y = 1<<i;
if(x&y) res++;
}
cout<<res<<'
';
}
}
return 0;
}
E
题意：从1-n的序列，pi（n)函数会把序列中第i个值提出来放到序列第一位。然后告诉你一个pos(pi,xi)函数，会找到pi序列的第xi个值，xi是给定的数组，再告诉你一个F函数，求1-n每个f函数的值。具体函数看题目。
思路：分类讨论，然后差分
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0)
const int inf = 2e9+5;
const ll INF = 2e18+5;
const int maxn = 2e5+5;
int a[maxn];
ll sum[maxn];
int main(){
IO;cout.precision(10);cout<<fixed;
int n,m;cin>>n>>m;
for1(i,m) cin>>a[i];
for1(i,m-1){
int x = min(a[i],a[i+1]),y = max(a[i],a[i+1]);
if(x==y) continue;
sum[1]+=y-x;
sum[x]-=y-x;
sum[x]+=y-1;
sum[x+1]-=y-1;
sum[x+1]+=y-x-1;
sum[y]-=y-x-1;
sum[y]+=x;
sum[y+1]-=x;
sum[y+1]+=y-x;
}
for1(i,n){
sum[i] = sum[i]+sum[i-1];
cout<<sum[i]<<' ';
}
return 0;
}
F.
题意：
F题意是1e6长度的字符串，你可以进行一次操作，操作可以选择一段区间反转字符串。你的目的是尽可能找到一段最长区间，使得区间内每一个字母都只出现一次。输出这个区间的最大长度。
思路：
问题等价于找到两个完美区间，且这两个区间任取字符不同，且总字符数最大。
转换成这个问题之后就可以dp+二进制了。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0)
const int inf = 2e9+5;
const ll INF = 2e18+5;
int a[1<<20];
int main(){
IO;cout.precision(10);cout<<fixed;
string s;cin>>s;
int n = s.size();
forn(i,n) s[i]-='a';
forn(i,n){
int num = 0;
for(int j = i;j<n;j++){
if(num&(1<<s[j])) break;
num|=(1<<s[j]);
a[num] = __builtin_popcount(num);
}
}
forn(j,1<<20){
forn(i,20)if(j&(1<<i)){
a[j] = max(a[j],a[j^(1<<i)]);
}
}
int ans = 0;
forn(i,1<<20) ans = max(ans,a[i]+a[(1<<20)-1-i]);
cout << ans <<'
';
return 0;
}