首页 > 其他分享 >Codeforces 1971H ±1

Codeforces 1971H ±1

时间:2024-05-11 15:09:17浏览次数:17  
标签:int Codeforces ins 1971H maxn low dfn operatorname

考虑到因为只有 \(3\) 行,所以第 \(2\) 行为 \(1\) 的条件就是 \(1\) 的个数 \(\ge 2\)。

对于这种只能去正负且有无解的问题,可以想到用个 \(\text{2-SAT}\)。
于是接下来考虑用 \(\operatorname{AND}, \operatorname{OR}, \operatorname{XOR}\) 来表示至少有 \(2\) 个 \(1\)。
考虑到如果存在 \(2\) 个 \(0\),那么这两个数 \(\operatorname{OR}\) 肯定为 \(0\)。
否则如果存在 \(2\) 个 \(1\),任意选出 \(2\) 个肯定都存在 \(1\),\(\operatorname{OR}\) 为 \(1\)。
于是可以得到限制 \(p_1\operatorname{OR} p_2 = p_1\operatorname{OR} p_3 = p_2\operatorname{OR} p_3 = 1\)。
于是建图缩点就可以了。

时间复杂度 \(\mathcal{O}(n)\)。

#include<bits/stdc++.h>
const int maxn = 1e3 + 10;
std::vector<int> to[maxn];
int a[3][maxn];
int dfn[maxn], low[maxn], fa[maxn], dt, ft, stk[maxn], top, ins[maxn];
void dfs(int u) {
   dfn[u] = low[u] = ++dt, stk[++top] = u, ins[u] = 1;
   for (int v : to[u]) {
      if (! dfn[v])
         dfs(v), low[u] = std::min(low[v], low[u]);
      else if (ins[v])
         low[u] = std::min(low[u], dfn[v]);
   }
   if (low[u] < dfn[u])
      return ;
   ft++;
   int t;
   do {
      t = stk[top--];
      ins[t] = 0, fa[t] = ft;
   } while (t != u);
}
inline void Main() {
   int n;
   scanf("%d", &n);
   for (int i : {0, 1, 2})
      for (int j = 1; j <= n; j++)
         scanf("%d", &a[i][j]);
   for (int i = 1; i <= n * 2; i++)
      to[i].clear();
   auto id = [&](int x) {return x < 0 ? -x : (x + n);};
   auto oth = [&](int x) {return x > n ? (x - n) : (x + n);};
   auto add = [&](int x, int y) {to[x].push_back(y);};
   for (int i = 1; i <= n; i++) {
      for (int j : {0, 1, 2}) for (int k : {0, 1, 2})
         if (j != k) 
            add(oth(id(a[j][i])), id(a[k][i]));
   }
   memset(dfn, 0, sizeof(int) * (n * 2 + 1));
   memset(low, 0, sizeof(int) * (n * 2 + 1));
   dt = ft = 0;
   for (int i = 1; i <= n * 2; i++)
      ! dfn[i] && (dfs(i), 1);
   for (int i = 1; i <= n; i++)
      if (fa[i] == fa[n + i])
         return puts("NO"), void();
   puts("YES");
}
int main() {
   int T;
   scanf("%d", &T);
   while (T--) Main();
   return 0;
}

标签:int,Codeforces,ins,1971H,maxn,low,dfn,operatorname
From: https://www.cnblogs.com/rizynvu/p/18186531

相关文章

  • Codeforces 1761D Carry Bit
    令\(c_i\)为第\(i\)位带来的进位的值,令\(c_{-1}=0\)。考虑如果知道了\(c_{i-1},c_i\)的值,\(a_i,b_i\)有多少种选法:\(c_{i-1}=0,c_i=0\),\((a_i,b_i)=(0,0),(0,1),(1,0)\)。\(c_{i-1}=1,c_i=1\),\((a_i,b_i)=(1,1),(0,1),(1,0)\)。......
  • Codeforces 295D Greg and Caves
    首先可以只考虑有效的行(有黑格的),设有\(h\)行,那么就有\(n-h+1\)种分配方式,最后\(\times(n-h+1)\)即可。对于有效的行,发现如果要考虑中间的部分\([l,r]\)其实可以只用\(len=r-l+1\)来表示。当然肯定会漏掉一些方案的,但考虑知道了\(\max\{len\}\)之后,......
  • Codeforces 1146D Frog Jumping
    首先根据裴蜀定理,能走到的点\(x\)肯定满足\(\gcd(a,b)|x\)。于是令\(g=\gcd(a,b)\),可以考虑求解\(\lfloor\frac{m}{g}\rfloor,\frac{a}{g},\frac{b}{g}\),最后记得去判一下\([g\lfloor\frac{m}{g}\rfloor,m]\)这个区间,因为只有这个区间是不满(区间长度可能\(<g\)......
  • CF1787H Codeforces Scoreboard
    CF1787HCodeforcesScoreboard校内测试的一道题,考试时根本没动。。题面考虑\(k\)比较大的放前面肯定优,然后修门挨着放也肯定优,所以先按\(k\)排个序,然后我们就只考虑每个门修不修。设计状态\(f[i][j]\)表示前\(i\)个点,有\(j\)个门取\(b-kt\),少送回去的最少......
  • CodeForces 1967D Long Way to be Non-decreasing 题解
    题意简述yzh喜欢单调不降序列。她有一个序列\(a\),最初为\(a_1,\ldots,a_n\),其中每个元素都在\([1,m]\)内。她希望使序列变得单调不降,为此,她有一个序列$b_1\ldotsb_m$,每个元素也在\([1,m]\)内。她可以进行若干次操作,一次操作定义为:选择一个集合\(S\subseteq......
  • Codeforces Round 942 (Div. 2) D2
    链接题目要求用数学一点的形式表达出来就是统计有多少a,b满足1.\(1\leqa\leqn,1\leqb\leqm\)2.\(\existsk\inN^*,使得b\timesgcd(a,b)=k\times(a+b)\)首先,把a和b改写,使得\(gcd(a,b)\)消失\(a=q*d,b=p*d\),则,\(gcd(a,b)=d\)条件二变为:\(p\timesd^2=k\times(q\t......
  • Codeforces Round 941 (Div. 2) Div 1 cf941 A-D
     A感觉A比较复杂啊,相比较B简单明了。way1只要有相同的一个数,它的数目大于等于k,那么它就可以进行一次操作,接下来可以再摸k-1个数,那么对于无法凑成k个数的数字来说,无论现在它有多少个数(>=1),加上这k-1个数,都能凑成数目>=k。同时,这个操作可以无限循环下去。所以这道题的出题设......
  • 『Solution』Codeforces 372D Choosing Subtree is Fun
    首先这个\(k\)的限制不是很好入手,考虑先从如果选取了区间\([l,r]\)来入手。那么此时连通块最小的\(siz\)就是把这些点拎出来建虚树对应在原树上的所有点。那么这个有个结论,考虑按\(\operatorname{dfn}\)序排序后的点为\(p_0\simp_{k-1}\),那么对应的最小\(sz\)就......
  • 『Solution』Codeforces 1970B Exact Neighbours
    Easy没什么启发性,直接考虑Medium。考虑到\(a_1=0\),那么\(1\)明显直接和自己配对就行,考虑分配到一个特殊的位置\((1,1)\)。接下来考虑如果还有\(a_i=0\),那么明显\(i\)也是和自己配对,此时因为这是无关紧要的就可以离特殊的\((1,1)\)尽量远一点,也就是让\(x\)坐......
  • Codeforces Round 943 (Div. 3)
    CodeforcesRound943(Div.3)A.Maximize?题意:给定x,求一个范围在[1,x)的数字y,内使得gcd(x,y)+y最大,输出任意的y思路:数据范围很小,暴力枚举即可voidsolve(){intx;cin>>x;inty=1,ma=0;for(inti=1;i<x;i++){intres=__gc......