CF Pinely Round 4

https://codeforces.com/contest/1991

\(-122=2019\)

D

\(1,3,4,6\) 构成团，所以答案下界为 \(4\)

按模 \(4\) 染色。同色的二进制后两位相同，异或和有约数 \(4\)

E

判二分图写了

bool dfs(int u,int x) {
    vis[u] = x;
    for(int v : e[u])
        if( vis[v] ) {
            if( vis[v] == x ) return 0;
        } else dfs(v,x^1); // ???
    return 1;
}

F

先排序

如果构不成三角形，满足 \(b[i]+b[i+1]\le b[i+2]\)，值域内最多只有 \(44\) 项。因此 \(48\) 个数一定能构成两个三角形

注意到如果三边能构成三角形，增大最短边（不超过次短边）仍能构成三角形。最终只需要 check 两种情况：六条边下标连续；每个三角形的三边下标连续

时间复杂度 \(O(43{5\choose 2}q)\)

G