LPC 计算机学会第五届“鸭王争霸赛”

A.虫洞(wormhole)

• 动态规划
  pd[i]=((pd[i-1]+1+pd[i-1]+M)-pd[p[i-1]]+1)mod M ;

1. 有钥匙 ： dp[i]=(dp[i-1]+1)modM ;
2. 没钥匙： dp[i]=((dp[i-1]+1+pd[i-1]+M)-pd[p[i-1]]+1)modM ;

• 附代码：

#include
using namespace std;
int n;
const long long M=1710833;
bool a[1000001];
long long p[1000001];
long long dp[1000001],pd[1000001];
int main() {
    freopen("wormhole.in","r",stdin);
    freopen("wormhole.out","w",stdout);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1; i>a[i];
    for(int i=1; i>p[i];
    dp[1]=0;
    for(int i=1; i<=n; i++)
        pd[i]=((pd[i-1]+1+pd[i-1]+M)-pd[p[i-1]]+1)%M;
    for(int i=2; i<=n; i++) {
        if(a[i-1] == 1)
            dp[i]=(dp[i-1]+1)%M;
        else
            dp[i]=((dp[i-1]+1+pd[i-1]+M)-pd[p[i-1]]+1)%M;
    }

    cout<<dp[n]%M;
    return 0;
}

B.剪发(haircut)

• 倒序并查集

C.吃人(eatman)

• 莫队

D.鸭子(duck)

• 环形差分约束的模板题