因为大家都要写所以我也要
今日10分（nyy还跟我说考得不错），0+10+0+0，改后110

T1 DP，不需要过多的优化

·题面描述

题目链接
给定n,Ai,Pi(Ai表示i处有几把钥匙)
初始位置在1，如果i处有钥匙就到i+1，否则制造钥匙后就通过虫洞到Pi，钥匙均为一次性物品，问最少几步能到n处，答案对1710833取模，n<=10^6，1<=Pi<=i<=n，0<=Ai<=1

考试的时候直接模拟，爆零（模拟过不去，复杂度O(n²)）
正解应该开两个DP数组，一个用来存储答案，另一个用来存储没有钥匙的情况（有钥匙的直接比较后加入即可），最后在运算时取模就结束哩
正解有一个引理：无论在哪个地方，都不存在比它小的地方有钥匙
讨论，若在1处，不存在更小的地方，故不存在
若不在1处，用第一数学归纳法证明：
由于虫洞只能传送到本身以及之前的地方(Pi=2)时，结论成立
那么当在(k+1)处时，由于没有任何一个在<=k处的虫洞可以传送到(k+1)处，故只能是由k处通过钥匙来到(k+1)处，而当在(k+1)处时，k处及其之前的钥匙均不存在或被消耗，故结论对于(k+1)成立
综上所述，结论成立

由这个引理就可以推出DP转移方程
小Tips:由于DP转移方程中出现减法，可能出现负数的情况，而又因为结果取模即可，所以可以先加上一个1710833再取模，这样会避免掉负数的情况从而拿到满分，否则只有70+

还有，洛谷的评测似乎有点问题，开不开O2都是所有点超时（而且时间出人意料地相等，均为5.20s），然而在本地评测或者2501提交就可以AC而且完全不会TLE

贴一个AC代码

#include
using namespace std;
#define ull unsigned long long
#define rep(i,x,y) for(ull i=x;i<=y;i++)
ull a[1000002],p[1000002],dp[1000002],pd[1000002],n;
const int mod=1710833;
inline void read(ull& a){
    ull s=0,w=1;
    char ch=getchar();
    while(ch'9'){
        if(ch=='-'){
            w=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    a=s*w;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("wormhole.in","r",stdin);
    freopen("wormhole.out","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(dp,0,sizeof(dp));
    read(n);
    rep(i,1,n){
        read(a[i]);
    }
    rep(i,1,n){
        read(p[i]);
    }
    dp[1]=pd[1]=0;
    rep(i,2,n){
        pd[i]=((pd[i-1]*2+2+mod)-pd[p[i-1]])%mod;
        if(a[i-1]!=0){
            dp[i]=(dp[i-1]+1)%mod;
        }
        else{
            dp[i]=((dp[i-1]+2+pd[i-1]+mod)-pd[p[i-1]])%mod;
        }
    }
    cout<<dp[n]%mod;
    return 0;
}

T2倒叙并查集

考试直接一遍数池塘，喜提10分，复杂度太高
正解不会，也没有改出来，不做过多评价
并查集

T3莫队算法+区间扩张/收缩

最近莫队出现有点频繁
考试的时候打的代码莫名其妙RE+TLE了，到现在也没有发现问题
莫队不会，正在学

T4环形差分约束

不会，正在学差分约束
主要是用SPFA算法，像我这种图论和搜索稀巴烂的还是continue吧

·总结

今天没学什么，倍增听不懂（听不懂干脆就没听，在改题）
洛谷切到一道题求在网格里有障碍物的最长路，题解说要插头DP，去看了插头DP的模板发现是黑题，然后一位大佬跟我说先去学数位DP……

$今日博客结束，大家再见$