题目链接

题意：
给你n个时间段[l,r]，每个时间段里要花d时间做任务，而这个任务只能在[l,l+d]，或者[r-d,r]这时间段里完成，问你有没有解决方法，有的话就输出任意一种。
思路：
先来翻译一下题意，每个时间段选择啥时候做任务只有两个选择，要么左端或右端，然后n个时间段都是这样的选择，然后这题问你存不存在一种满足n个时间段都能做任务的方案。
因为每个时间段就两个选择，就可以联想到2-SAT，判断两个时间段a,b是不是相交，相交的话就a->!b和b->!a连两条单向边。
spj一发ac，舒服列。

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <sstream>
#include <set>
#include <iterator>
#include <list>
#include <cstdio>
#include <iomanip>
#include <climits>
using namespace std;
const int N = 2*(int)2005+100;     //点数*2
int n;
struct node{int l,r,d;node(){}node(int _l,int _r,int _d):l(_l),r(_r),d(_d){}
}nd[N];
int scc, top, tot;
vector<int> G[N];
int low[N], dfn[N], belong[N];
int stk[N], vis[N];
void init(int n) {for (int i = 0; i <= 2*n; ++i) {G[i].clear();low[i] = 0;dfn[i] = 0;stk[i] = 0;vis[i] = 0;}scc = top = tot = 0;
}
void tarjan(int x) {stk[top++] = x;low[x] = dfn[x] = ++tot;vis[x] = 1;for (int i=0; i<int(G[x].size()); ++i) {int to=G[x][i];if (!dfn[to]) {tarjan(to);low[x] = min(low[x], low[to]);} else if (vis[to]) low[x] = min(low[x], dfn[to]);}if (low[x] == dfn[x]) {++scc;int temp;do {temp = stk[--top];belong[temp] = scc;vis[temp] = 0;} while (temp != x);}
}
void out(int x){int h=x/60;int m=x-h*60;if(h<10) putchar('0');printf("%d:",h);if(m<10) putchar('0');printf("%d",m);
}
void twoSat(int n) {for (int i=0; i<2*n; ++i) {if (!dfn[i]) tarjan(i);}for (int i=0; i<2*n; i+=2) {if (belong[i] == belong[i^1]) {puts("NO");return;}}puts("YES");for (int i = 0; i < 2*n; i+=2) {   //因为强连通用了栈，所以强连通编号是反拓扑序if (belong[i] > belong[i^1]) { //false->true 也就是只能为真out(nd[i^1].l); putchar(' '); out(nd[i^1].r); puts("");} else{out(nd[i].l); putchar(' '); out(nd[i].r); puts("");}}
}
void addEdge(int a, int b) {G[a].push_back(b);
}
bool collide(int id1, int id2){if(nd[id1].l>=nd[id2].r) return false;if(nd[id1].r<=nd[id2].l) return false;return true;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed;
#ifdef LOCAL_DEFINEfreopen("input.txt", "r", stdin);
#endifscanf("%d",&n);init(n);bool pre=true;int tot=0;for(int i=0; i<n; ++i){int h1,m1,h2,m2,x;scanf("%d:%d",&h1,&m1);scanf("%d:%d",&h2,&m2);scanf("%d",&x);int t1=h1*60+m1;int t2=h2*60+m2;if(t2-t1<x) pre=false;nd[tot++]=node(t1,t1+x,x);nd[tot++]=node(t2-x,t2,x);}if(!pre){puts("NO");return 0;}for(int i=0; i<tot; ++i){for(int j=i+1; j<tot; ++j){if(collide(i,j)){addEdge(i,j^1);addEdge(j,i^1);}}}twoSat(n);
#ifdef LOCAL_DEFINEcerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endifreturn 0;
}