Codeforces Round #773 (Div. 2)
VP
| A | B | C |
|---|---|---|
| 24min | 31min | 48min |
| +2 | +1 |
A
\(\color{Gray}{800}\)
观察题目样例外加手摸可知，只有满足三角形中某条边与 \(x\) 轴平行且在最上面的情况下，有且仅有这条边算作贡献。
稍加模拟即可。
时间复杂度：\(O(1)\)
#define pi pair <int,int>
#define F(i) (i).first
#define S(i) (i).second
pi a[4];
void work(){
for(int i=1;i<=3;i++) cin>>F(a[i])>>S(a[i]);
if(S(a[2])==S(a[1])&&S(a[3])<S(a[1])) return cout<<abs(F(a[2])-F(a[1]))<<'\n',void();
if(S(a[2])==S(a[3])&&S(a[1])<S(a[2])) return cout<<abs(F(a[3])-F(a[2]))<<'\n',void();
if(S(a[3])==S(a[1])&&S(a[2])<S(a[1])) return cout<<abs(F(a[3])-F(a[1]))<<'\n',void();
cout<<0<<'\n';
}
B
\(\color{Gray}{900}\)
从后向前考虑，先分成 \(n\) 组后合并。
不难发现，重复的数字个数 \(x\) 即前 \(x\) 次合并能减小贡献 \(1\) 的情况。
使用 std::sort() 和 std::unique() 模拟过程即可。
时间复杂度：\(O(n \log_2 n)\)
#define L(i,j,k) for(int i=(j);i<=(k);i++)
int n,cnt;
const int N=3e5+10;
int a[N],ans[N];
void work(){
cin>>n;L(i,1,n) cin>>a[i];
sort(a+1,a+1+n);
cnt=unique(a+1,a+1+n)-a-1;
cnt=n-cnt;int x=n;
R(i,n,1){
ans[i]=x;
if(cnt) x--,cnt--;
}L(i,1,n) cout<<ans[i]<<' ';
cout<<'\n';
}
C
\(\color{ForestGreen}{1200}\)
不难想到，每次操作能解决一个没有配对的数。
用 std::map 统计一下就行了。
不知道为啥 std::unordered_map 这回没被针对
时间复杂度：\(O(n \log_2 n)\)
#define L(i,j,k) for(int i=(j);i<=(k);i++)
int n,k,cnt;
map<int,int>mp;
const int N=3e5+10;
int a[N];
void work(){
mp.clear();cnt=0;
cin>>n>>k;L(i,1,n) cin>>a[i],mp[a[i]]++;
sort(a+1,a+1+n);
L(i,1,n) if(mp[a[i]*k]&&mp[a[i]])
mp[a[i]]--,mp[a[i]*k]--;
L(i,1,n) cnt+=mp[a[i]],mp[a[i]]=0;
cout<<cnt<<'\n';
}
D
\(\color{Purple}{2000}\)
这 CD gap 咋这么大
题目把操作次数给的非常充裕，所以考虑比较暴力的想法。
对于某个数 \(a_i\)，找到第一个与之相等的数 \(a_j\)。
然后将 \(a_k \left( k \in \left[ i+1,j-1 \right] \right)\) 的数按顺序加入。
比如：\(12341\)
\(12341 \mapsto 1234122 \mapsto 123412332 \mapsto 1234234432\)
去掉可以作为答案序列的部分，得到 \(432\)。
每次进行操作，相当于去掉头尾的数，将中间序列翻转。
模拟此过程即可，最多进行 \(O(\dfrac{n^2}{2})\) 次，可以通过。
时间复杂度：\(O(n^3)\)
#define F(i) (i).first
#define S(i) (i).second
#define pb push_back
#define pi pair<int,int>
#define L(i,j,k) for(int i=(j);i<=(k);i++)
void work(){
vector<int>a,l;vector<pi>ans;
map<int,int>mp;int x,n,len=0;
cin>>n;L(i,0,n-1)
cin>>x,a.pb(x),mp[x]++;
for(int i:a) if(mp[i]&1)
return cout<<-1<<'\n',void();
while(!a.empty()){
L(j,1,a.size()-1)
if(a[0]==a[j]){
L(k,0,j-2) ans.pb({len+k+1+j,a[k+1]});
l.pb(j*2);len+=j*2;
reverse(a.begin()+1,a.begin()+j);
a.erase(a.begin()+j),a.erase(a.begin());
break;
}
}cout<<ans.size()<<'\n';
for(auto x:ans)
cout<<F(x)<<' '<<S(x)<<'\n';
cout<<l.size()<<'\n';
for(int i:l)
cout<<i<<' ';cout<<'\n';
}
E
\(\color{Orange}{2200}\)
用 \(0\) 区间和 \(1\) 区间描述题目中的区间。
对题意进行分析：
- 如果某人在 \(0\) 区间内，则必定不是。
- 如果某人在 \(1\) 区间内，且此 \(1\) 区间中其余人都被前一条确定否，则必定是，否则不确定。
比如
11000010001111
- ^ -
^ 指向的是当前询问对象，当且仅当其本身和其左右 0 的连续段 中包含这个 \(1\) 区间，才能确定其为病人。
考虑用 std::set 维护这些信息。一开始将所有点丢到 std::set 里，确认不为病人后踢出即可。
询问时先找到中间那一位的前驱 \(l\) 后继 \(r\) 。
如果存在左端点在 \(( l,x ]\)，右端点在 \([ x,r )\) 的 \(1\) 区间，就能确定此人为病人。
- 线段树：
如果用线段树维护，就是单点修改，区间查询，维护区间最小值。
每次输入 \(1\) 区间时将 $\text{seg_tree}_ l $ 赋值为 \(\min(\text{seg_tree}_ l,r)\) 即可。
每次询问判断 \(ask(l+1,x)\) 与 \(r\) 的关系即可。
时间复杂度：\(O(n\log_2 n)\)
#define L(i,j,k) for(int i=(j);i<=(k);i++)
int n,q;set<int>st;
const int N=2e5+100,INF=1e9;
struct tree{int l,r,z;}s[N<<2];
void pushup(int p){s[p].z=min(s[lc].z,s[rc].z);}
void build(int p,int l,int r){
s[p]=(tree){l,r,INF};
if(l==r) return;int m=(l+r)>>1;
build(lc,l,m);build(rc,m+1,r);
}void change(int x,int k,int p=1){
s[p].z=min(s[p].z,k);
if(s[p].l==s[p].r) return ;
int m=(s[p].l+s[p].r)>>1;
change(x,k,(x<=m?lc:rc));
pushup(p);
}int ask(int l,int r,int p=1){
if(s[p].l>=l&&s[p].r<=r) return s[p].z;
int m=(s[p].l+s[p].r)>>1,v=INF;
if(l<=m) v=min(v,ask(l,r,lc));
if(r>m) v=min(v,ask(l,r,rc));
return v;
}void work(){
cin>>n>>q;
build(1,0,n+1);
L(i,0,n+1) st.insert(i);
while(q--){
int o;cin>>o;
if(o){
int j;cin>>j;
auto i=st.lower_bound(j);
if(*i!=j) cout<<"NO"<<'\n';
else{
auto k=i--;k++;
cout<<((*k>(ask(*i+1,j)))?"YES":"N/A")<<'\n';
}
}else{
int l,r,x;
cin>>l>>r>>x;
if(x) change(l,r);
else{
auto a=st.lower_bound(l),b=st.upper_bound(r);
while(a!=b){auto c=a++;st.erase(c);}
}
}
}
}
- 并查集：
考虑使用并查集维护连通块。对于一个 \(0\) 区间 \([l,r]\)，可以在并查集中把 \([l,r+1]\) 合并，同时将 \(r+1\) 作集合代表元素，把编号小者合并到编号大者集合内。
同时维护 \(\forall i \in [l,r+1]\)，若 \(i\) 为一个 \(0\) 区间的左端点，则右端点的最小值，此值在连通块最右端（集合代表元素）处更新。
然后对 \(i\) 是否有病进行判断：
若无病，则其一定非集合代表元素。
若有病，则其一定是集合代表元素，且包括与其同一集合的元素右端点最小值一定小于其右边连通块代表元素。
（也就是有包括他的有病者所在的区间，且区间内此人之前和之后的人全部没有病）。
（若不小于，则证明没有满足上述要求的区间，此人不能明确是否患病）。
时间复杂度：\(O(n\alpha(n))\)
int n,q,a,b;
const int N=2e5+100,INF=1e9;
int f[N],g[N];
int cz(int x){return x==f[x]?x:f[x]=cz(f[x]);}
void work(){
cin>>n>>q;++n;
L(i,1,n) f[i]=i,g[i]=INF;
while(q--){
int o,l,r;
cin>>o>>l;
if(o){
if(cz(l)!=l) cout<<"NO"<<'\n';
else
if(g[l]<cz(l+1)) cout<<"YES"<<'\n';
else cout<<"N/A"<<'\n';
}else{
cin>>r>>o;
if(o)
a=cz(l),g[a]=min(g[a],r);
else
while(l<=r){
a=cz(l);b=cz(l+1);f[a]=b;
g[b]=min(g[a],g[b]);l=b;
}
}
}
}
