- 题解
拓扑排序讲评
-
xuanxuan1688
LV 2
@
2024-2-17 1:55:15
A题 从来没有遗忘过，可迟到的真相，如今记起来真的还有意义吗？意义又是什么呢？记起来难道不是徒增烦恼吗？
形式化题意:给定个按照原始字符串字典序排列的字符串,再给定一个加密串,输出解密的加密串。
众所周知，字典序的排列便是比较第一位不相同的字符，我们将第i个字符串与第1~i - 1的字符串进行比较，找到第一位不相同的字符，便可得到许多等量关系。
之后对等量关系进行拓扑排序，之后解密便可得到原文。
#include <bits/stdc++.h>
using namespace std;
char *p1,*p2,buf[100000];
int head[26],tot,r[26],n,m,num,u,v,ans[26],tf,length;
bool visited[26];
string s[8005];
struct edge{
int v,nxt;
}edges[64000005];
inline void addedge(int u,int v){
++r[v],edges[++tot] = {v,head[u]},head[u] = tot;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(ans,-1,sizeof(ans));
cin >> n;
for (int i = 1;i <= n;++i){
cin >> s[i];
for (int j = 0;j < s[i].size();++j) visited[s[i][j] - 'a'] = true;
}
for (int i = 1;i <= n;++i){
for (int j = i + 1;j <= n;++j){
length = min(s[i].size(),s[j].size());
for (int k = 0;k < length;++k){
if (s[i][k] != s[j][k]){
addedge(s[j][k] - 'a',s[i][k] - 'a');
break;
}
}
}
}
queue <int> q;
for (int i = 0;i < 26;++i)
if (!r[i] && visited[i])
q.push(i);
while (!q.empty()){
int tmp = q.front();
q.pop();
if (ans[tmp] != -1){
cout << 0;
return 0;
}
ans[tmp] = tf++;
for (int i = head[tmp];i;i = edges[i].nxt)
if (!(--r[edges[i].v]))
q.push(edges[i].v);
}
cin >> s[n + 1];
for (int i = 0;i < s[n + 1].size();++i)
if (ans[s[n + 1][i] - 'a'] == -1){
cout << 0;
return 0;
}
for (int i = 0;i < s[n + 1].size();++i)
cout << char(ans[s[n + 1][i] - 'a'] + 'a');
}
B题 难道就真的就只是他们的一厢情愿吗?他们的人生价值又是什么呢？他们的一厢情愿又能换来什么改变呢？
形式化题意:给定一张图,输出它的拓扑排序序列。
在本题中,由于有生成的序列字典序最小这一限制条件,所以请将你的队列(queue)换成堆(priority_queue),按照编号排序。
#include <bits/stdc++.h>
using namespace std;
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
const int N = 100005,M = 100005;
char *p1,*p2,buf[100000];
int head[N],tot,r[N],n,m,num,u,v,ans[N];
struct edge{
int v,nxt;
}edges[M];
char ch;
inline int read(){
int x = 0;
char ch = nc();
while (ch < '0' || ch > '9') ch = nc();
while (ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = nc();
}
return x;
}
int main(){
n = read(),m = read();
for (int i = 1;i <= m;++i){
u = read(),v = read();
++r[v],edges[++tot] = {v,head[u]},head[u] = tot;
}
priority_queue <int,vector<int>,greater<int> > q;
for (int i = 1;i <= n;++i) if (!r[i]) q.push(i);
while (!q.empty()){
int tmp = q.top();
q.pop();
ans[++num] = tmp;
for (int i = head[tmp];i;i = edges[i].nxt)
if (!(--r[edges[i].v])) q.push(edges[i].v);
}
if (num != n){
cout << -1;
return 0;
}
for (int i = 1;i <= n;++i) cout << ans[i] << " ";
}
C题 这样做真的对吗？是不是再早一点便不会这样了？未来的世界又是怎样的呢？那命运的撞击是否能被阻止？
在本题中，我不断强调了秦始皇给你的是一张DAG。
做法便是写个循环在到达时间点时将该事件加入至堆(priority_queue)中(按照排序),之后按照正常的思路拓扑排序即可。
同时，入度数组你需要开到二维，两个维度分别是[任务编号]与[点编号]。
#include <bits/stdc++.h>
using namespace std;
const int N = 5005,M = 5005,K = 10005;
short ftot = 1,tot,r[K][N],head[N],n,m,u,v,k;
int tnow,ansk[K],t,to,s;
long long ansn[N],byte;
struct thing{
short num,to;
int t,s;
long long byte;
bool operator < (const thing &p) const{
return p.t > t;
}
}something[K];
struct edge{
short v,nxt;
}edges[M];
struct node{
short num,in;
int s,t;
long long byte;
bool operator < (const node &p) const{
if (p.s != s) return p.s > s;
return p.t < t;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
for (int i = 1;i <= m;++i){
cin >> u >> v;
for (int j = 1;j <= k;++j) ++r[j][v];
edges[++tot] = {v,head[u]},head[u] = tot;
}
for (int i = 1;i <= k;++i){
cin >> t >> to >> s >> byte;
something[i] = {i,to,t,s,byte};
}
sort(something + 1,something + 1 + k);
priority_queue <node> q;
while (ftot <= k || !q.empty()){
if (ftot <= k && tnow >= something[ftot].t){
q.push({something[ftot].num,something[ftot].to,something[ftot].s,something[ftot].t,something[ftot].byte});
ansk[something[ftot++].num] = -~tnow;
}
if (!q.empty()){
node tmp = q.top();
q.pop();
if (head[tmp.in]) ansk[tmp.num] = -~tnow;
ansn[tmp.in] += tmp.byte;
for (int i = head[tmp.in];i;i = edges[i].nxt)
if (!(--r[tmp.num][edges[i].v])) q.push({tmp.num,edges[i].v,tmp.s,tmp.t,tmp.byte});
}
++tnow;
}
for (int i = 1;i <= k;++i) cout << ansk[i] << "\n";
for (int i = 1;i <= n;++i) cout << ansn[i] << "\n";
}
D题 回望时，皆是你与光芒。一切如同那点点繁星般璀璨闪耀，命运的脚步不断前进，身后的脚印，是那点点星光
TLE做法
在本题中，一辆车会有4个方向，相信有的人想到了将冲时会被碰撞的车设为父亲(面向4个方向4个循环查找车)，从而制作出一张DAG(有向无环)图(如果制作出的不是DAG直接输出-1)。
之后对该图进行拓扑排序，便可以得到答案序列。
AC做法
我们考虑在查找4个方向的车上进行优化 首先我们先正向对地图遍历一遍，同时开一个数组，这里称之为
代表第列目前行最大的车子(排除目前遍历的车子)，于是，对于一个点，当前的即为它的N，上一个不为.的车即为它的W
同理，我们反向对地图遍历一遍，此时，对于一个点，当前的即为它的S，上一个不为.的车即为它的E
#include <bits/stdc++.h>
using namespace std;
const int N = 5505,M = 5505;
int ptot,head[N * M],tot,r[N * M],ans[N * M],n,m,num,u,v,t[N * M],totf;
bool flag;
struct node{
int x,y;
}nodes[N * M];
struct edge{
int v,nxt;
}edges[N * M];
struct car{
int nums;
bool operator < (const car &s) const{
return nodes[s.nums].x * nodes[s.nums].x + nodes[s.nums].y * nodes[s.nums].y < nodes[nums].x * nodes[nums].x + nodes[nums].y * nodes[nums].y;
}
};
char f[N][M];
inline void addedge(int u,int v){
++r[v],edges[++tot] = {v,head[u]},head[u] = tot;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1;i <= n;++i){
flag = false;
for (int j = 1;j <= m;++j){
cin >> f[i][j];
if (f[i][j] != '.') nodes[++totf] = {i,j};
if (f[i][j] == 'N' && t[j]) addedge(t[j],totf);
if (f[i][j] == 'W' && flag) addedge(totf - 1,totf);
if (f[i][j] != '.') t[j] = totf,flag = true;
}
}
ptot = totf;
memset(t,0,sizeof(t));
for (int i = n;i >= 1;--i){
flag = false;
for (int j = m;j >= 1;--j){
if (f[i][j] == 'S' && t[j]) addedge(t[j],totf);
if (f[i][j] == 'E' && flag) addedge(totf + 1,totf);
if (f[i][j] != '.') t[j] = totf,--totf,flag = true;
}
}
priority_queue <car> q;
for (int i = 1;i <= ptot;++i) if (!r[i]) q.push({i});
while (!q.empty()){
car tmp = q.top();
q.pop();
ans[++num] = tmp.nums;
for (int i = head[tmp.nums];i;i = edges[i].nxt)
if (!(--r[edges[i].v])) q.push({edges[i].v});
}
if (num != ptot){
cout << -1;
return 0;
}
for (int i = 1;i <= ptot;++i)
cout << nodes[ans[i]].x - 1 << " " << nodes[ans[i]].y - 1 << "\n";
}
0 条评论
目前还没有评论...