\(\text{G - 01Sequence}\)
解法
设 \(x_i\) 为序列中 \([1,i]\) 之间 \(1\) 的个数。那么 \((l,r,x)\) 就可以转化成 \(x_r-x_{l-1}\ge x\)。
由于我们需要求 \(x_n\) 的最小值，可以从 \(l-1\) 向 \(r\) 连一条权值为 \(x\) 的边，求最长路。由于边权为正，所以不能用 \(\mathtt{Dijkstra}\)。但这题用 \(\mathtt{SPFA}\) 会被卡，那咋办捏？
不妨换一个角度：设 \(x_i\) 为序列中 \([1,i]\) 之间 \(0\) 的个数。那么 \((l,r,x)\) 就可以转化成 \(x_r-x_{l-1}\le r-l+1-x\)。此时正好要求 \(x_n\) 的最大值，就转化成了从 \(l-1\) 向 \(r\) 连一条权值为 \(r-l+1-x\) 的边，求最短路。
另外还要注意一个条件：\(0\le x_{i+1}-x_i\le 1\)。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>‘9‘ or s<‘0‘)
f|=(s==‘-‘);
while(s>=‘0‘ and s<=‘9‘)
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar(‘-‘),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <queue>
#include <cstring>
using namespace std;
const int maxn=2e5+5;
struct node {
int nxt,to,val;
} e[maxn*3];
struct Node {
int x,v;
bool operator < (const Node &t) const {
return v>t.v;
}
};
int n,m,cnt,head[maxn];
int d[maxn];
bool vis[maxn];
priority_queue <Node> q;
void addEdge(int u,int v,int w) {
e[++cnt].to=v;
e[cnt].nxt=head[u];
e[cnt].val=w;
head[u]=cnt;
}
void Dijkstra() {
q.push((Node){0,0});
memset(d,0x3f,sizeof d);
d[0]=0;
while(!q.empty()) {
Node t=q.top(); q.pop();
if(vis[t.x] or (t.v^d[t.x]))
continue;
vis[t.x]=1;
for(int i=head[t.x];i;i=e[i].nxt) {
int v=e[i].to;
if(d[v]>d[t.x]+e[i].val) {
d[v]=d[t.x]+e[i].val;
q.push((Node){v,d[v]});
}
}
}
}
int main() {
n=read(9),m=read(9);
int l,r,x;
for(int i=1;i<=m;++i) {
l=read(9),r=read(9);
x=r-l+1-read(9);
addEdge(l-1,r,x);
}
for(int i=0;i<n;++i)
addEdge(i+1,i,0),
addEdge(i,i+1,1);
Dijkstra();
for(int i=1;i<=n;++i)
putchar(d[i]-d[i-1]^‘1‘),putchar(‘ ‘);
puts("");
return 0;
}