看大家都要写我就来写了
今日44（0+10+15+19），改题没有一题ACqaq

T1

第一题考虑把n进行二进制拆分,再构造一条含有2q+1个节点的链,将k二进制拆分后,记最低位为第0位。若第i位二进制位为1,连接图对应的两个点。不难发现图符合要求，使用节点数为5q+2，极限情况时大约需要使用150个节点。
预计得分100分(然而我爆零)

T2 区区黑题

这道题在洛谷上面是NOI/NOI+/CTSC我是没想到的
冒泡排序暴力打了10分，复杂度(Q*N²)，但是题解说30
稍做优化，先只是暴力算结果，在修改时用O(n)算答案更新结果即可，复杂度(N²+QN)，55左右
后面的看不懂了，直接摘题解
KD Tree或者树套树维护，85+ (不会)
推公式（ans=max(i从1至n){i-<=a的数的个数}+1，然后离线用权值线段树维护（不会，too）

T3紫题

快速幂炸了（不是TLE！！！），用题解的公式也只有20-分，跳过

T4紫题，DP+优化

考试时以为是背包，打了2h+发现不对啊，这背包怕不是成精了
最后样例没过的代码交上去19分（其实就是子任务3数据弱被我混过去了）
DP转移方程f(i,l,r)=min(f(i-1,l,r),f(i-1,l-ri,r-pi)+hi)，复杂度（nP²），会挂
后来才发现需要单调队列优化

·总结

你永远也到达不了「AC」的真实
今天的Hash听懂了一点，字典树听懂概念但是不会实现……
学了一下乘法逆元，顺便补了一下贝祖定理和拓展欧几里得算法，模板如下

//求取模运算的乘法逆元
#define ll long long
ll ex_gcd(ll a,ll b,ll &x,ll &y) {
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int d=ex_gcd(b,a%b,x,y);
    int z=x;
    x=y;
    y=z-y*(a/b);
    return d;
}
ll inv(ll a, ll p) {
    ll x,y;
    ll d=ex_gcd(a,p,x,y);
    return d==1?(x+p)%p:-1;
}   

学了一点点优先队列
好了，各位再见！！！