Day9复盘

yanjiadong · 2023-07-26 20:45:02 · 个人记录

T1

#include<bits/stdc++.h>
using namespace std;
int main() {
    for(int i=0;i<=1000;i++) {
        for(int j=i;j<=1000;j++) {
            if((i|j)+(i&j)>j*2)cout<<"XbbChidaji";
        }
    }
    return 0;
}

用这玩意可以证明数列增加数字不能让它变大，所以直接找最大乘2然后就没了，简直和树上的链1有的一拼，最后记住取模！

T2

爆搜，分成两半爆搜，复杂度log(sqrt(2^n)) sqrt(2^n)，就没了

T3

三角形除了同色三角形还有什么三角形呢？

原来是异色三角形！

每个异色三角形都有两个异色角，找到所有异色角然后除以2再用三角形总数减去就是同色三角形

T4

死因：max 打成 min了

强联通块打个模板就过了

那么

怎么算额外连的边数呢？

入度或出度为0的点显然就是这个图的害群之马，所以要用额外的边把他们处理掉就行，只要给每个出度为0的点多连一条出边，入度为0的点多连一条入边，连得边数就是他俩的max