Codeforces Round #756 (Div. 3)
C. Polycarp Recovers the Permutation
有一个元素个数为 \(n\) 的数组 \(p\)，我们每次执行以下操作：
取 \(p\) 最左边和最右边的数中较小的一个，如果选的是最左边，就加入新数组 \(a\) 的左边，否则加入 \(a\)的右边。
现在给出 \(a\)，求 \(p\)。如果无解，输出 \(-1\) ；如果多组解，输出任意一组即可。
多测，有 \(t\) 组数据 .
\(1\leq t\leq 10^4,1\leq n\leq 2\cdot 10^5,1\leq a_i\leq n,\sum n\leq 2\cdot 10^5\)
sol1
考虑，最后剩下的两个/一个一定在开头/结尾 . 所以，直接一层一层的拨下来 . 但是期间遇到了很多问题 .
比如说奇数序列我分情况讨论了 \(4\) 钟 . div3c 一个 difficulty 1000 的题目我写了 20 min . 相当自闭 .
时间复杂度 : \(O(n)\)
空间复杂度 : \(O(n)\)
code
#include
using namespace std;
int t;
int n;
dequea,na,p,b,ans;
inline void init(){
a.clear();b.clear();p.clear();ans.clear();
}
bool ok(){
for(int i=0;i>n;
for(int i=0;i>x;
a.push_back(x);
}
na=a;
while(!a.empty()){
p.push_front(a.front());a.pop_front();
if(!a.empty())p.push_back(a.back()),a.pop_back();
}
a=na;
ans=p;b.clear();
while(!p.empty()){
if((int)p.size()==1){
b.push_back(p.back());
if(ok()){
for(int i=0;i<(int)ans.size();i++)cout<>t;
while(t--){
solve();
}
return 0;
}
/*inline? ll or int? size? min max?*/
sol2
但是这个做法非常复杂，有更简便的做法吗？分析一下，发现，\(n\) 必然在队首或者队尾 .
因为，在操作过程中 ，\(n\) 如果为现在队列的队首或者队尾，与其他元素比较，其他元素必然会被比到前面去，那么，\(n\) 就会到了最后才被放到最终队列的对头/队尾 . 所以，\(n\) 必然是队头/队尾 . 否则无解 .
因此，考虑一个比较极端的情况，在原来的序列里，\(n\) 就是队头 / 队尾，那么剩下的元素则是依次放入现在得到的序列，相当于 reverse 一下了序列 . 感觉十分巧妙，果真我是智障 .
时间复杂度 : \(O(n)\)
空间复杂度 : \(O(n)\)
code
#include
using namespace std;
int t;
int n;
int a[200010];
void solve(){
cin>>n;
for(int i=0;i>a[i];
if(a[0]!=n&&a[n-1]!=n)cout<<"-1\n";
else{
for(int i=n-1;i>=0;i--)cout<>t;
while(t--){
solve();
}
return 0;
}
/*inline? ll or int? size? min max?*/
D. Weights Assignment For Tree Edges
给定一个含有 \(n\) 个点的有根树和一个长度为 \(n\) 的排列 \(p\)，你需要给这棵树的每一条边赋权，使得对于所有的 \(1 \leq i
，点 \(p_{i}\) 到根的距离小于点 \(p_{j}\) 到根的距离。 你需要保证每条边的边权都是 \([1,1 \times 10^{9}]\) 内的整数。
多测，有 \(t\) 组数据。
若无解，输出 \(-1\)。否则输出 \(n\) 个整数，第 \(i\) 个整数 \(w_{i}\) 表示点 \(i\) 到其父亲的边权为 \(w_{i}\) ，特别地，默认根到其父亲的边权为 \(0\) 。
\(1\leq t\leq 10^4,1\leq n\leq 2\cdot 10^5,1\leq b_i\leq n,1\leq p_i\leq n\)
第一眼看上去会有点懵，冷静一下，发现，考虑从 \(p_0\) 到 \(p_{n-1}\) 依次考虑，首先，这棵树不能有赋值 . 其次，考虑加入第一个点，\(p_0\) 到 \(root\) 上都赋值为 \(1\) 即可 . 现在，再加入 \(p_1\) …… 这样一个过程 .
\(dis(p_i)\) 必须比 \(dis(p_0),dis(p_1),\)$\cdots $$,dis(p_{i-1})$ 都大，其中，得到 \(dis(p_0)
所以，加入 \(p_i\) 上必定有一条边没有被赋值过 . 否则则无解 . 考虑将这条边的边权设为 \(\max(1,dis(p_{i-1})-dis(fa(i))+1)\) . 即可 .
时间复杂度 : \(O(n)\)
空间复杂度 : \(O(n)\)
code
#include
using namespace std;
int t;
int n,rt;
int b[200010],p[200010];
long long sum[200010],ans[200010];
void init(){
for(int i=0;i>n;
for(int i=0;i>b[i];
b[i]--;
if(i==b[i])rt=i;
}
for(int i=0;i>p[i],p[i]--;
long long tmp=-1;
for(int i=0;iv;
int x=p[i];
while(b[x]!=x){
if(ans[x]!=0){
now=sum[x];
break;
}
v.push_back(x);
x=b[x];
}
if((int)v.size()==0&&i!=0){
cout<<"-1\n";
init();
return;
}
if((int)v.size()==0)continue;
reverse(v.begin(),v.end());
tmp-=now;
for(int j=0;j<(int)v.size();j++)ans[v[j]]=1,tmp--;
if(tmp>0)ans[v[0]]+=tmp;
sum[v[0]]=now+ans[v[0]];
for(int j=1;j<(int)v.size();j++)sum[v[j]]=sum[v[j-1]]+ans[v[j]];
tmp=sum[v[(int)v.size()-1]];
}
for(int i=0;i>t;
while(t--){
solve();
}
return 0;
}
/*inline? ll or int? size? min max?*/
E2. Escape The Maze (hard version)
现在有一棵树，其中 \(1\) 号节点是树根，也就是小 v 所在的点，树上边都是双向边。
树上有 \(n\) 个点，您有 \(k\) 位朋友。每个时刻，小 v 和小 v 的朋友都会顺着树上的边走向另一个节点。
小 v 会获胜当且仅当小 v 走到了叶子节点。
小 v 会输当且仅当您被一个朋友在小v 获胜之前在任何房间或走廊遇到。
问：至少在树中保留多少个朋友才能使小 v 在游戏中失败？
多测，有 \(t\) 祖数据 .
\(1\leq t\leq 10^4,1\leq k
考虑每个朋友都向根走都是最优的 .
因此，设计 \(f(i)\) 表示在子树 \(i\) 失败的最少保留节点个数 . \(g(i)\) 表示子树 \(i\) 中距离 \(i\) 距离最小的有朋友所在的节点 .
除了平常的转意外，还要考虑 \(g(i)\) 中保存的节点是否可以使得 \(i\) 不能到达 .
如果 \(dep(i)+1\geq dep(g(i))-dep(i)+1\) 即是会在 \(i\) 或 \(i\) 的祖先上相遇，那么节点 \(i\) 就不可被到达 .
时间复杂度 : \(O(n)\)
空间复杂度 : \(O(n)\)
code
#include
using namespace std;
const int inf=1e9+10;
int t;
int k,n;
bool vis[200010];
vectornei[200010];
int dep[200010];
int f[200010],g[200010];
void init(){
for(int i=0;idep[g[to]]){
g[x]=g[to];
}
}
}
if(legal==1)f[x]=min(f[x],sum);
if(vis[x])g[x]=x,f[x]=1;
if(g[x]!=-1&&dep[x]+1>=dep[g[x]]-dep[x]+1)f[x]=1;
}
void solve(){
cin>>n>>k;
for(int i=0;i>x;
x--;
vis[x]=true;
}
for(int i=0;i>u>>v;
u--;v--;
nei[u].push_back(v);
nei[v].push_back(u);
}
get_dep(0,-1);
for(int i=0;i>t;
while(t--){
solve();
}
return 0;
}
/*inline? ll or int? size? min max?*/
F. ATM and Students
给定一个长度为 \(n\) 的序列 \(a\) 和一个整数 \(s\)，求一段最长的区间 \([l,r]\) 满足
\[\forall i\in[l,r],s+\sum\limits_{j=l}^i a_j\geq 0 \]多测，有 \(t\) 组数据 .
\(1\leq t\leq 10^4,1\leq n\leq 2\cdot 10^5,0\leq s\leq 10^9,-10^9\leq a_i\leq 10^9\)
用一个线段树维护前缀和 .
考虑从后往前加入 \(a_i\) ，相当于区间加 \(a_i\) . 在线段树上二分第一个前缀和 \(<0\) 的位置即可 .
时间复杂度 : \(O(n\log n)\)
空间复杂度 : \(O(n)\)
code
#include
using namespace std;
int t;
int n,s;
int a[200010];
long long ts[200010<<2],tag[200010<<2];
void build(int x,int l,int r){
if(l==r){
ts[x]=tag[x]=0;
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
ts[x]=tag[x]=0;
}
inline void pd(int x){
if(!tag[x])return;
ts[x<<1]+=tag[x];
tag[x<<1]+=tag[x];
ts[x<<1|1]+=tag[x];
tag[x<<1|1]+=tag[x];
tag[x]=0;
}
void upd(int x,int l,int r,int cl,int cr,int val){
if(l==cl&&r==cr){
if(l!=r)pd(x);
ts[x]+=val;
tag[x]+=val;
return;
}
pd(x);
int mid=(l+r)>>1;
if(cr<=mid)upd(x<<1,l,mid,cl,cr,val);
else if(mid+1<=cl)upd(x<<1|1,mid+1,r,cl,cr,val);
else{
upd(x<<1,l,mid,cl,mid,val);
upd(x<<1|1,mid+1,r,mid+1,cr,val);
}
ts[x]=min(ts[x<<1],ts[x<<1|1]);
}
int qry(int x,int l,int r,int cl,int cr){
if(l==cl&&r==cr){
if(l!=r)pd(x);
if(s+ts[x]>=0)return r;
if(l==r)return -1;
int mid=(l+r)>>1;
if(s+ts[x<<1]<0)return qry(x<<1,l,mid,cl,mid);
int res=qry(x<<1|1,mid+1,r,mid+1,cr);
if(res!=-1)return res;
return mid;
}
pd(x);
int mid=(l+r)>>1;
if(cr<=mid)return qry(x<<1,l,mid,cl,cr);
else if(mid+1<=cl)return qry(x<<1|1,mid+1,r,cl,cr);
else{
int r1=qry(x<<1,l,mid,cl,mid);
if(r1!=mid)return r1;
int r2=qry(x<<1|1,mid+1,r,mid+1,cr);
return max(r2,mid);
}
}
int qry(int x,int l,int r,int pos){
if(l==r)return ts[x];
pd(x);
int mid=(l+r)>>1;
if(pos<=mid)return qry(x<<1,l,mid,pos);
else return qry(x<<1|1,mid+1,r,pos);
}
void solve(){
cin>>n>>s;
for(int i=0;i>a[i];
build(1,0,n-1);
int ans=0,l=0,r=0;
for(int i=n-1;i>=0;i--){
upd(1,0,n-1,i,n-1,a[i]);
int pos=qry(1,0,n-1,i,n-1);
if(pos!=-1){
if(ans>t;
while(t--){
solve();
}
return 0;
}
/*inline? ll or int? size? min max?*/
G. Robot and Candies
给定一张 \(n \times m\) 的 \(01\) 网格图，每次选一个点 \((1,x)\) 出发，可以从 \((x,y)\) 到 \((x+1,y+1)\) 或者 \((x+1,y-1)\) ，问至少出发多少次才能经过每个 \(1\) 至少一次。
多测，有 \(t\) 组数据 .
\(1\leq t\leq 10^4,nm\leq 10^6,\sum nm\leq 10^6\)
如果是恰好一次，应该就是网络流了，但是不是 .
一开始有个错误的贪心思路 .
首先，将网格黑白染色 . 观察到道路最多有 \(m+1\) 个 . 所以，考虑维护从开头到上一行的道路最后节点 . 能到达的范围对应着一个区间，考虑当前点选择包含它的右端点最小的区间 .
但是这个做法是错误的 . 题目中的第 3 个样例 . 当前这行的结果会对下一行造成影响 . 这样选不一定是最优的 .
此时，考虑每一条路径从上到下依次选择的是什么 .
考虑保存每一行最小的 \(1\) 节点 . 从小到大排序，依次加入当前路径，如果可以加入则加入，不可以则不加入 . 即为最优 .
时间复杂度 : \(O(nm\log n)\)
空间复杂度 : \(O(nm)\)
code
#include
using namespace std;
int t;
int n,m;
vectorboard;
set::iterator it;
vectorv[1000010];
int ans=0;
void solv(int val){
for(int i=0;i=0;j--)if((i+j)%2==val){
if(board[i][j]=='1')v[i].push_back(j);
}
for(int T=0;Ts;
vector >vec;
for(int i=0;i0){
vec.push_back(make_pair(v[i].back(),i));
}
if((int)vec.size()==0)break;
++ans;
sort(vec.begin(),vec.end());
s.insert(vec[0].second);
for(int i=0;i<(int)vec.size();i++){
bool ok=true;
it=s.lower_bound(vec[i].second);
if(it!=s.end()){
if(abs(v[*it].back()-vec[i].first)>abs(*it-vec[i].second))
ok=false;
}
if(it!=s.begin()){
it--;
if(abs(v[*it].back()-vec[i].first)>abs(*it-vec[i].second))
ok=false;
}
if(ok)s.insert(vec[i].second);
}
for(set::iterator it=s.begin();it!=s.end();it++)v[*it].pop_back();
}
}
void solve(){
board.clear();ans=0;
cin>>n>>m;
for(int i=0;i>s;
board.push_back(s);
}
solv(0);
solv(1);
cout<>t;
while(t--){
solve();
}
return 0;
}
/*inline? ll or int? size? min max?*/