免费做网站刮刮卡,wordpress伪静态卡死,免费公司网站怎么做,自己做网站美工传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
你现在有ppp种电台#xff0c;有nnn对关系(x,y)(x,y)(x,y)代表xxx电台或yyy电台中至少有一个#xff0c;mmm对关系(x,y)(x,y)(x,y)代表xxx电台或yyy电台中最多有一个#xff0c;每个电台有两个参数li,ril…传送门 文章目录题意思路题意
你现在有ppp种电台有nnn对关系(x,y)(x,y)(x,y)代表xxx电台或yyy电台中至少有一个mmm对关系(x,y)(x,y)(x,y)代表xxx电台或yyy电台中最多有一个每个电台有两个参数li,ril_i,r_ili,ri你需要在[1,M][1,M][1,M]中选择一个主频fff如果f∈[li,ri]f\in [l_i,r_i]f∈[li,ri]那么第iii个电台你可以选择是否启用否则无法启用。
请给出fff并构造电台启用方案无解输出−1-1−1。
2≤n,p,m,M≤4e52\le n,p,m,M\le 4e52≤n,p,m,M≤4e5
思路
对于n,mn,mn,m这几个条件显然是2−sat2-sat2−sat板子了以下设uuu代表选uuu这个点u′uu′代表不选uuu这个点。
对于nnn对关系我们建x′−y,y′−xx-y,y-xx′−y,y′−x。
对于mmm对关系我们建x−y′,y−x′x-y,y-xx−y′,y−x′。
热身完毕现在开始正菜。
考虑如何制定fff呢我们运用前缀和的思想尝试将[l,r][l,r][l,r]拆成[1,l−1],[1,r][1,l-1],[1,r][1,l−1],[1,r]。
我们把f∈[1,li−1],f∈[1,ri]f\in [1,l_i-1],f\in [1,r_i]f∈[1,li−1],f∈[1,ri]的真值表写出来。
f∈[1,li−1]f∈[1,ri]i能否启用00001110不存在110\begin{array}{ccc} f\in [1,l_i-1] f\in [1,r_i] i能否启用 \\ \hline \ 000\\ \ 011\\ \ 10不存在\\ \ 110\\\\\end{array}f∈[1,li−1] 0 0 1 1f∈[1,ri]0101i能否启用01不存在0
我们可以发现总结一下就是以下三个限制
(1)(1)(1)若f∈[1,li−1]f\in [1,l_i-1]f∈[1,li−1]则iii不能启用。
(2)(2)(2)若f∈[1,ri]f\in [1,r_i]f∈[1,ri]不满足则iii不能启用。
(3)(3)(3) 若iii启用则f∈[li,ri]f\in [l_i,r_i]f∈[li,ri]。
所以我们拿出来[n1,nM1][n1,nM1][n1,nM1]来代表[0,M][0,M][0,M]我们用这个来继续限制。
我们设满足ni1ni1ni1的时候就是f≤if\le if≤i否则fififi。
首先就是ni1−ni2,(ni2)′−(ni1)′ni1-ni2,(ni2)-(ni1)ni1−ni2,(ni2)′−(ni1)′这个比较显然因为f≤if\le if≤i那么f≤i1f\le i1f≤i1如果fi1fi1fi1那么fififi。
让后就是限制一下上面的条件
(1)(1)(1) nli−i′,i−(nli)′nl_i-i,i-(nl_i)nli−i′,i−(nli)′。
(2)(2)(2)(nri1)′−i′,i−nri1(nr_i1)-i,i-nr_i1(nri1)′−i′,i−nri1。
还有就是fff不能为000这个用n1−(n1)′n1-(n1)n1−(n1)′限制一下即可算是2−sat2-sat2−sat的小技巧了。
跑完之后nf1nf1nf1成立而nfnfnf不成立的时候的分界点就是fff。
// Problem: F. Radio Stations
// Contest: Codeforces - Codeforces Round #585 (Div. 2)
// URL: https://codeforces.com/contest/1215/problem/F
// Memory Limit: 256 MB
// Time Limit: 7000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N2000010,MN*10,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int p,n,q,m;
int e[M],ne[M],h[N],idx;
int dfn[N],low[N],id[N],tot,cnt;
int stk[N],top;
bool in[N];void add(int a,int b)
{e[idx]b,ne[idx]h[a],h[a]idx;
}void tarjan(int u)
{dfn[u]low[u]tot;stk[top]u; in[u]true;for(int ih[u];~i;ine[i]){int vere[i];if(!dfn[ver]){tarjan(ver);low[u]min(low[u],low[ver]);}else if(in[ver]) low[u]min(low[u],dfn[ver]);}if(dfn[u]low[u]){int y; cnt;do{ystk[top--];in[y]false; id[y]cnt;}while(y!u);}
}int yes(int x) { return x1; }int no(int x) { return x1|1; }void link(int x,int y) {add(x,y); add(y^1,x^1);
}bool check()
{for(int i0;inm;i) if(id[yes(i)]id[no(i)]) return false;return true;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d%d%d,p,n,m,q);idx0;memset(h,-1,sizeof(h));for(int i1;ip;i) {int a,b; scanf(%d%d,a,b);a--; b--;// add(2*a,2*b1); // add(2*b,2*a1);link(no(a),yes(b));}for(int i0;im;i) {// add(n*2i*21,n*2(i1)*21),add(n*2(i1)*2,n*2i*2);link(yes(ni),yes(ni1));}// link(yes(n),no(n));// add(n*2,n*21);// add(n*21,n*2);for(int i0;in;i) {int l,r; scanf(%d%d,l,r);l--; link(yes(i),no(nl));link(yes(i),yes(nr));// add(n*2l*21,i*2); add(i*21,n*2l*2);// add(n*2r*2,i*2); add(i*21,n*2r*21);}for(int i1;iq;i) {int a,b; scanf(%d%d,a,b);a--; b--;link(yes(a),no(b));// add(a*21,b*2);// add(b*21,a*2);}//n*2(m1)*2for(int i0;i2*n(m1)*2;i) if(!dfn[i]) tarjan(i);if(check()) {vectorintans;for(int i0;in;i) if(id[yes(i)]id[no(i)]) ans.pb(i1);for(int i1;im;i) if(id[yes(ni)]id[no(ni)]) {printf(%d %d\n,ans.size(),i);break;}for(auto x:ans) printf(%d ,x); puts();} else puts(-1);return 0;
}
