思维构造,建图——cf1159E
2024-10-07 23:23:59
很好的题
/*
nexti:pi右边第一个比pi大的数的下标
把每个[i,a[i]]都看成一段区间,区间只能在端点处交叉,以此来判断是否有解
特别的,如果a[i]=-1,那么把a[i]=i+1,不对其他区间造成任何影响
如何判区间合法性:用一个set记录区间右边界,每次遍历到左端点i时将set里的i删去,然后放入右边界a[i],同时进行判断
如何输出解 :从n+1开始,右端点向左端点连边,然后拓扑排序(bfs)即可
*/
#include<bits/stdc++.h>
#include<queue>
using namespace std;
#define maxn 500005
int n,a[maxn],t,ans[maxn];
vector<int>G[maxn]; int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=;i<=n+;i++)G[i].clear();
set<int>s;
int flag=; for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=n;i++){
if(a[i]==-)a[i]=i+;
while(s.find(i)!=s.end())
s.erase(i);
if(!s.empty() && *s.begin()<a[i])flag=;
s.insert(a[i]);
G[a[i]].push_back(i);
} if(flag){puts("-1");continue;}
int id=n;
queue<int>q;q.push(n+); while(!q.empty()){
int u=q.front();q.pop();
for(int i=;i<G[u].size();i++){
int v=G[u][i];
ans[v]=id--;
q.push(v);
}
}
for(int i=;i<=n;i++)cout<<ans[i]<<" ";
puts("");
}
}
最新文章
- Struts2中的ModelDriven机制及其运用
- plsql11.06注册码
- JS-字符串操作-替换
- 搜索栏会消失 uisearchbar 狂点消失的问题解决
- EasyUI 后台接受DataGrid传来的参数
- 详解Spring事件驱动模型
- 【jmeter】元件的作用域与执行顺序
- centos下 rpm包sphinx安装成功提示
- AIX性能监控topas命令的详细解析
- BootStrap2学习日记13----关于按钮
- 原生JS研究:学习jquery源码,收集整理常用JS函数
- ASF(传感器)
- RNN的介绍
- ConvertUtils.register注册转换器
- 3200 [HNOI2009]有趣的数列
- contos mysql 删除
- Struts学习资料
- 2018.11.04 NOIP训练 小水塘(并查集)
- python测试开发django-25.表单提交之post注册案例
- WPF中的命令与命令绑定导航
热门文章
- Pathfinding 模板题 /// BFS oj21413
- 【python】collections的使用
- websokect的原理
- Linux-iptables-route-rule
- XSS攻击原理
- CSIC_716_20191113【装饰器进阶以及迭代器】
- sublime text-----查看当前文件的编码格式
- 概率dp的迭代方式小结——zoj3329,hdu4089,hdu4035
- python 毫秒时间戳转日期
- error C2712: Cannot use __try in functions that require object unwinding