[CCPC 2019 秦皇岛站] 题解

liuzhenhao09 · 2023-01-13 23:02:02 · 个人记录

q汝母呢

比赛链接

想了很久不知道写什么就写这个吧

A Angle Beats

这题还是很套路的吧

分类讨论一下询问的点是不是直角的那个点

• 如果是的话其余点直接按极角排序即可

• 这部分复杂度O(qnlogn)

• 如果不是直角的那个点，明显不能每次都对于本来的点重新排序，复杂度会爆炸

• 解决方法也不难，直接离线下来然后对于每个本来的点处理一下询问就行，详情可以见代码

然后就是一些代码实现上的细节

• 一就是先按象限排序再按叉积排序

• 二就是如何构造一个直角的问题

• 大概就是将左边的三角形旋转一个角度得到右边的

• 为什么是九十度容易用三垂直模型相关的定理推出，不展开说了

• 另一边的垂直也是类似的

• 这样的话C点坐标就很好求了

• 直接用二分找到所有在这条线上的点即可，非常方便

代码：（码起来应该不难吧）

#include<bits/stdc++.h>
using namespace std;
struct Point{
    int x,y,id;
}p[5010],pcop[5010],tmp;
Point operator - (const Point& A,const Point& B){
    return (Point){A.x - B.x,A.y - B.y};
}
bool CMP(const Point& A,const Point& B){
    return (1LL * A.x * B.y - 1LL * A.y * B.x) > 0;
}
int Q(const Point &A){ //象限，细节挺多的，没有重复的两个点还挺好的，容易风车形划分 
    if(A.x > 0 && A.y >= 0) return 1;
    else if(A.x <= 0 && A.y > 0) return 2;
    else if(A.x < 0 && A.y <= 0) return 3;
    else return 4;
}
bool operator <(const Point& A,const Point& B){ //排序 
    Point AA = A - tmp,BB = B - tmp;
    int QA = Q(AA),QB = Q(BB);
    if(QA != QB) return QA < QB;
    return CMP(AA,BB);
}
int n,m; 
int ans[5010];
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n + m; i++) scanf("%d %d",&p[i].x,&p[i].y),pcop[i] = p[i];
    for(int i = n + 1; i <= n + m; i++){
        tmp = p[i];
        sort(p + 1,p + n + 1);
        for(int j = 1; j <= n; j++){
            Point C = (Point){tmp.x - p[j].y + tmp.y,tmp.y + p[j].x - tmp.x}; //求C点 
            ans[i] += upper_bound(p + 1,p + n + 1,C) - lower_bound(p + 1,p + n + 1,C);
        }
    }
    for(int i = 1; i <= n; i++){
        memcpy(p + 1,pcop + 1,sizeof(Point) * n); //记得清空 
        tmp = p[i];
        swap(p[i],p[n]);
        sort(p + 1,p + n);
        for(int j = n + 1; j <= n + m; j++){
            Point C = (Point){tmp.x - p[j].y + tmp.y,tmp.y + p[j].x - tmp.x};
            Point D = (Point){tmp.x + p[j].y - tmp.y,tmp.y - p[j].x + tmp.x};
            ans[j] += upper_bound(p + 1,p + n,C) - lower_bound(p + 1,p + n,C);
            ans[j] += upper_bound(p + 1,p + n,D) - lower_bound(p + 1,p + n,D);
        }
    }
    for(int i = n + 1; i <= n + m; i++) printf("%d\n",ans[i]);
    return 0;
}

(two-pointers由于有排序的存在显得麻烦了些，虽然常数小了点，但是复杂度不变）

开long long时间会炸

B The Tree of Haruhi Suzumiya

神题

首先考虑一个容斥，把 D(A) 容斥一下。

具体地，D(A)=\tbinom{|A|}{2} - i 是 j 祖先且 w_i≤w_j 的点对数 +A 中所有点的深度和。

如果没有权值相等的点的话则"i 是 j 祖先且 w_i≤w_j 的点对数"等于 D(B)。

问题就转换的简单了些。

首先考虑求出 |V(B)|=n 的情况的答案。

直接树状数组维护即可，顺便求出了每个点有多少个祖先权值比它小的，设这个值为 a_i。

先考虑没有权值相等的点的情况。

考虑把 B 中的点放到 A 中的过程，设从 B 拿出来的点为 x。

则对于 D(B) 来说贡献减少了"i 是 x 祖先且 w_i<w_x 或 x 是 i 祖先且 w_x<w_i(i\in B) 的点对数"。

对于 D(A) 来说 \tbinom{|A|}{2} 这部分可以暂时不考虑，因为贡献增量是一个定值，然后贡献增加了"d_x-i 是 x 祖先且 w_i<w_x 或 x 是 i 祖先且 w_x<w_i(i\in A) 的点对数"。

两边拼起来也就是"d_x-i 是 x 祖先且 w_i<w_x 或 x 是 i 祖先且 w_x<w_i 的点对数"。

后面这个是个常数可以直接预处理。

然后这个步骤的贡献就算出来了，直接每次找贡献最小的值从小到大扔到 A 就可以了。

接下来考虑有权值相等的点的情况。

设 b_i 为每个点有多少个子孙权值比它大的，这个也不难求。

则刚才说的每个步骤的贡献变成了 d_x-a_x-b_x。

然后问题就是对于两个权值相等的点 u,v，若 u 为 v 祖先则应该选谁。

因为 a_v-a_u≤d_v-d_u (根据定义易知)。

也就是 d_u-a_u≤d_v-a_v。

同时 b_u≥b_v。

则 d_u-a_u-b_u≤d_v-a_v-b_v。

也就是即使有权值相等还是选祖先更优，下述算法的正确性得到保证。

这里只需要预处理每个点有多少个祖先权值和它一样的，设为 c_i。

则直接按 d_i-a_i-b_i-c_i 排序即可。

时间复杂度 O(n\log n)。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
    int to,nxt;
}e[1000010];
int n,nE = 0;
int hd[500010],w[500010],a[500010],b[500010],c[500010],d[500010],bit[500010],ans[500010],now[500010];
int LSB(int i){
    return i & (-i);
}
void upd(int i,int k){
    while(i <= 500000){
        bit[i] += k;
        i += LSB(i);
    }
}
int query(int i){
    int s = 0;
    while(i){
        s += bit[i];
        i -= LSB(i);
    }
    return s;
}
void add(int u,int v){
    e[++nE] = (edge){v,hd[u]};
    hd[u] = nE;
}
void dfs_a(int u,int fa){
    a[u] = query(w[u] - 1);
    upd(w[u],1);
    for(int i = hd[u]; i; i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        dfs_a(v,u);
    }
    upd(w[u],-1);
}
void dfs_b(int u,int fa){
    upd(w[u],1);
    b[u] = query(w[u]) - query(500000);
    for(int i = hd[u]; i; i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        dfs_b(v,u);
    }
    b[u] += query(500000) - query(w[u]);
}
void dfs_c(int u,int fa){
    c[u] = query(w[u]) - query(w[u] - 1);
    upd(w[u],1);
    for(int i = hd[u]; i; i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        dfs_c(v,u);
    }
    upd(w[u],-1);
}
void dfs_d(int u,int fa){
    d[u] = d[fa] + 1;
    for(int i = hd[u]; i; i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        dfs_d(v,u);
    }
}
bool cmp(int x,int y){
    return d[x] - a[x] - b[x] - c[x] < d[y] - a[y] - b[y] - c[y];
}
signed main(){
    scanf("%lld",&n);
    for(int i = 1; i <= n; i++) scanf("%lld",&w[i]);
    for(int i = 1,u,v; i < n; i++){
        scanf("%lld %lld",&u,&v);
        add(u,v);
        add(v,u);
    }
    d[0] = -1;
    dfs_a(1,0);
    dfs_c(1,0);
    dfs_b(1,0);
    dfs_d(1,0);
    for(int i = 1; i <= n; i++) ans[n] += a[i],now[i] = i;
    sort(now + 1,now + n + 1,cmp);
    for(int i = n - 1; i >= 0; i--){
        int tmp = ans[i + 1] + (n - i - 1); //组合数的贡献 
        int nowtmp = now[n - i];
        tmp = tmp + (d[nowtmp] - a[nowtmp] - b[nowtmp] - c[nowtmp]);
        ans[i] = tmp;
    }
    for(int i = 0; i <= n; i++) printf("%lld\n",ans[i]);
    return 0;
}

C Sakurada Reset

题目应该是很套路的可以看官方题解

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
int n,m;
int a[5010],b[5010],prea[5010],preb[5010],fa[5010][5010],facop[5010],fb[5010][5010],fbcop[5010];
int cnt[5010],sumcnt[5010],f[5010][5010],s[5010][5010],sg[5010][5010];
signed main(){
    scanf("%lld %lld",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%lld",&a[i]);
    for(int i = 1; i <= m; i++) scanf("%lld",&b[i]);
    for(int i = 1; i <= n; i++){
        prea[i] = cnt[a[i]];
        cnt[a[i]] = i;
    }
    memset(cnt,0,sizeof(cnt));
    for(int i = 1; i <= m; i++){
        preb[i] = cnt[b[i]];
        cnt[b[i]] = i;
    }
    for(int i = 0; i <= max(n,m); i++){
        fa[i][0] = 1,fb[i][0] = 1;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            if(!prea[i]) fa[i][j] = (fa[i][j] + fa[i - 1][j - 1]) % MOD;
            else fa[i][j] = (fa[i][j] + fa[i - 1][j - 1] - fa[prea[i] - 1][j - 1] + MOD) % MOD;
            facop[j] = (facop[j] + fa[i][j]) % MOD;
            fa[i][j] = (fa[i - 1][j] + fa[i][j]) % MOD;
        }
    }
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= i; j++){
            if(!preb[i]) fb[i][j] = (fb[i][j] + fb[i - 1][j - 1]) % MOD;
            else fb[i][j] = (fb[i][j] + fb[i - 1][j - 1] - fb[preb[i] - 1][j - 1] + MOD) % MOD;
            fbcop[j] = (fbcop[j] + fb[i][j]) % MOD;
            fb[i][j] = (fb[i - 1][j] + fb[i][j]) % MOD;
        }
    }
    for(int i = 1; i <= n; i++) fbcop[i] = (fbcop[i] + fbcop[i - 1]) % MOD;
    int ans = 0;
    for(int i = 2; i <= n; i++){
        (ans += facop[i] * fbcop[i - 1] % MOD) %= MOD;
    }
    f[0][0] = 1;
    for(int i = 0; i <= n; i++) f[i][0] = 1;
    for(int i = 0; i <= m; i++) f[0][i] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i] == b[j]){
                if(!prea[i] && !preb[j]) f[i][j] = (f[i][j] + f[i - 1][j - 1]) % MOD;
                else if(!prea[i]) f[i][j] = (f[i][j] + f[i - 1][j - 1] - f[i - 1][preb[j] - 1] + MOD) % MOD;
                else if(!preb[j]) f[i][j] = (f[i][j] + f[i - 1][j - 1] - f[prea[i] - 1][j - 1] + MOD) % MOD;
                else f[i][j] = (f[i][j] + f[i - 1][j - 1] - f[prea[i] - 1][j - 1] - f[i - 1][preb[j] - 1] + f[prea[i] - 1][preb[j] - 1] + MOD + MOD) % MOD;
            }
            f[i][j] = (f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j] + MOD) % MOD;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i] > b[j]){
                if(!prea[i] && !preb[j]) s[i][j] = (s[i][j] + f[i - 1][j - 1]) % MOD;
                else if(!prea[i]) s[i][j] = (s[i][j] + f[i - 1][j - 1] - f[i - 1][preb[j] - 1] + MOD) % MOD;
                else if(!preb[j]) s[i][j] = (s[i][j] + f[i - 1][j - 1] - f[prea[i] - 1][j - 1] + MOD) % MOD;
                else s[i][j] = (s[i][j] + f[i - 1][j - 1] - f[prea[i] - 1][j - 1] - f[i - 1][preb[j] - 1] + f[prea[i] - 1][preb[j] - 1] + MOD + MOD) % MOD;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(!prea[i] && !preb[j]) s[i][j] = (s[i][j] + s[i - 1][j - 1]) % MOD;
            else if(!prea[i]) s[i][j] = (s[i][j] + s[i - 1][j - 1] - s[i - 1][preb[j] - 1] + MOD) % MOD;
            else if(!preb[j]) s[i][j] = (s[i][j] + s[i - 1][j - 1] - s[prea[i] - 1][j - 1] + MOD) % MOD;
            else s[i][j] = (s[i][j] + s[i - 1][j - 1] - s[prea[i] - 1][j - 1] - s[i - 1][preb[j] - 1] + s[prea[i] - 1][preb[j] - 1] + MOD + MOD) % MOD;
            (ans += s[i][j]) %= MOD;
            s[i][j] = (s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + s[i][j] + MOD) % MOD;
        }
    }
    printf("%lld",ans % MOD);
    return 0;
}

D Demical

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
signed main(){
    scanf("%lld",&T);
    while(T--){
        int n;
        scanf("%lld",&n);
        while(n % 2 == 0) n /= 2;
        while(n % 5 == 0) n /= 5;
        if(n == 1) puts("No");
        else puts("Yes");
    }
    return 0;
}

E Escape

一眼网络流

考虑如何建图

首先化简题目条件容易发现

• 如果一个点没有放转弯装置，则该点可以纵向横向各通过一次

• 如果一个点放了转弯装置，则该点只能被通过一次

一次也就是流量的限制

每个点拆成横向来的和纵向来的两个点

这两个点之间连一条流量为1的边代表只能转弯一次

然后横纵向正常连边即可

时间复杂度O((n*m)\sqrt{n*m})

代码太丑了就不放了

F Forest Program

智障计数题

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
struct edge{
    int to,nxt;
}e[1000010];
int n,m,nE = 0,ans = 1;
int fac[1000010],dep[1000010],hd[1000010];
bool vis[1000010];
void add(int u,int v){
    e[++nE] = (edge){v,hd[u]};
    hd[u] = nE;
}
void dfs(int u,int fa){
    vis[u] = 1;
    for(int i = hd[u]; i; i = e[i].nxt){
        int v = e[i].to;
        if(v == fa) continue;
        if(!vis[v]){
            dep[v] = dep[u] + 1;
            dfs(v,u);
            continue;
        }
        if(dep[v] > dep[u]) continue;
        int len = dep[u] - dep[v] + 1;
        ans = (ans * (fac[len] - 1)) % MOD;
        m = m - len;
    }
}
signed main(){
    fac[0] = 1;
    for(int i = 1; i <= 1000000; i++) fac[i] = (fac[i - 1] * 2) % MOD;
    scanf("%lld %lld",&n,&m);
    for(int i = 1,u,v; i <= m; i++){
        scanf("%lld %lld",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            dep[i] = 1;
            dfs(i,0);
        }
    }
    ans = (ans * fac[m]) % MOD;
    printf("%lld",ans);
    return 0;
}

G Game on Chessboard

看一眼数据范围就能想到状压

然后发现合法的状态应该是从左上到右下的一条轮廓线

直接轮廓线DP就行了

具体地就是轮廓线从右上角扫到左下角的过程

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
int w[20][20];
char a[20][20];
int dp[17000000];
int n;
int main(){
    scanf("%d",&n);
    for(int i = 0; i < n; i++) scanf("%s",a[i]);
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d",&w[i][j]);
    int S = (1 << n) - 1;
    int T = S << n;
    for(int i = 0; i < 16999996; i++) dp[i] = INF;
    dp[T] = 0;
    for(int s = T; s >= S; s--){ //0下 1右 
        if(dp[s] == INF) continue;
        int cnt = 0;
        for(int i = 0; i <= 2 * n; i++){
            if((s >> i) & 1) cnt++;
        }
        if(cnt != n) continue;
        int x = -1,y = 0;
        for(int i = 2 * n - 1; i > 0; i--){
            if((s >> i) & 1) x++;
            else y++;
            if((s >> i) & 1 && !((s >> (i - 1)) & 1)){
                if(a[x][y] == '.') dp[s - (1 << (i - 1))] = min(dp[s - (1 << (i - 1))],dp[s]);
                else dp[s - (1 << (i - 1))] = min(dp[s - (1 << (i - 1))],dp[s] + w[x][y]);
                int nx = -1,ny = 0;
                for(int j = 2 * n - 1; j > i + 1; j--){
                    if((s >> j) & 1) nx++;
                    else ny++;
                    if((s >> j) & 1 && !((s >> (j - 1)) & 1)){
                        if((a[x][y] == 'B' && a[nx][ny] == 'W') || (a[x][y] == 'W' && a[nx][ny] == 'B')){
                            dp[s - (1 << (i - 1)) - (1 << (j - 1))] = min(dp[s - (1 << (i - 1)) - (1 << (j - 1))],dp[s] + abs(w[x][y] - w[nx][ny]));
                        }
                    }
                }
            }
        }
    }
    printf("%d",dp[S]);
    return 0;
}

H Houraisan Kaguya

预处理阶+FWT

官方题解写的很好

自己的代码T了，求调qwq

(Pollard-Rho抄的板子)

#include<bits/stdc++.h>
#define I __int128
#define ll long long
using namespace std;
int n;
int pr[12]={2,3,5,7,11,13,17,19,23,29,31,37};
ll p,a[1000010],o[1000100];
vector<ll> pw;
int tot,u[35];
long long q[35];
ll gcd(ll a,ll b) {if(b==0) return a; return gcd(b,a%b);}
long long mul(long long a,long long b,long long c){
    long long r=a*b-(long long)((long double)a*b/c+0.5)*c;
    return r<0?r+c:r;
}
inline long long poww(long long a,long long k,long long p)
{
    long long ans=1;
    a=a%p;
    while(k)
    {
        if(k&(1ll)) ans=mul(ans,a,p);
        a=mul(a,a,p); k=k>>1;
    }
    return ans;
}
bool ml(long long x)
{
    if(x<3||x%2==0) return (x==2);
    if(x>40) {
        long long t=x-1; int cnt=0;
        while(t%2==0) t=t/2,cnt++;
        for(auto pri:pr) {
            long long g=poww(pri,t,x);
            if(g==1) continue;
            for(int i=0;i<cnt;++i)
            {
                if(g==x-1) break;
                g=(I)g*g%x;
                if(g==1||i==cnt-1) return 0;
            }
        }
        return 1;
    }
    for(auto i:pr) {
        if(x==i) return 1;
    }
    return 0;
}
long long h[1000005];
void work(long long x)
{
    int e=0;
    long long ans=p-1;
    for(int i=1;i<=tot;++i)
    {
        e=e*(u[i]+1)+u[i];
        for(int j=1;j<=u[i];++j)
        {
            if(poww(x,ans/q[i],p)==1) ans/=q[i],e--;
            else break;
        }
    }
    (h[e]+=ans)%=p;
}
long long get(long long x,long long c,long long p) {
    return ((I)x*x+c)%p;
}
long long P_Rho(long long x)
{
    long long c=(long long)rand()%(x-1)+1;
    long long t=0;
    long long r=c;
    while(t!=r) {
        long long d=gcd(abs(t-r),x);
        if(d>1) return d;
        t=get(t,c,x);
        r=get(get(r,c,x),c,x);
    }
    return x;
}
int pre[55];
void fac(long long x)
{
    if(x==1) return;
    if(ml(x)) {
        pw.push_back(x);
        return;
    }
    long long p=x;
    while(p>=x) p=P_Rho(x);
    while(x%p==0) x/=p;
    fac(x); fac(p);
}
long long ans[1000005];
int main()
{
    cin>>n>>p; 
    if(p==2) {
        cout<<1ll*n*n%p;
        return 0;
    }
    fac(p-1); long long d=p-1;
    long long uu=1;
    for(auto i:pw) {
        if(d%i==0) {
            int cnt=0;
            q[++tot]=i;
            while(d%i==0) d/=i,cnt++;
            u[tot]=cnt;
            uu=uu*poww(i,cnt,p);
        }
    }
    int r=1;
    for(int i=tot;i>=1;--i) {
        pre[i]=r;
        r=r*(u[i]+1);
    }
    for(int i=1;i<=n;++i) {
        scanf("%lld",&a[i]);
        if(a[i]==1) h[0]++; 
        else work(a[i]);
    }
    for(int i=1;i<=tot;++i)
    {
        for(int j=r-1;j>=0;--j)
        {
            if(((j/pre[i])%(u[i]+1))+1<=u[i]) {
                (h[j]+=h[j+pre[i]])%=p;
            }
        }       
    }
    for(int i=0;i<r;++i) h[i]=(I)h[i]*h[i]%p;
    for(int i=1;i<=tot;++i)
        for(int j=0;j<=r-1;++j)
        {
            if(((j/pre[i])%(u[i]+1))+1<=u[i]) {
                h[j]=(h[j]-h[j+pre[i]]+p)%p;
            }
        }
    long long sum=0;
    for(int j=0;j<=r-1;++j)
    {
        ans[j]=1;
        for(int i=1;i<=tot;++i)
        {
            if(j/pre[i]>0) 
            {
                ans[j]=ans[j-pre[i]]*q[i];
                break;
            }
        }
        sum=(sum+(I)h[j]*poww(poww(ans[j],p-2,p),2,p))%p;
    }
    cout<<sum;
    return 0;
}

I Invoker

智障题

#include<bits/stdc++.h>
using namespace std;
char c[10][6][4] = {
    "QQQ","QQQ","QQQ","QQQ","QQQ","QQQ",
    "QQW","QWQ","WQQ","WQQ","WQQ","WQQ",
    "QQE","QEQ","EQQ","EQQ","EQQ","EQQ",
    "WWW","WWW","WWW","WWW","WWW","WWW",
    "QWW","WQW","WWQ","WWQ","WWQ","WWQ",
    "WWE","WEW","EWW","EWW","EWW","EWW",
    "EEE","EEE","EEE","EEE","EEE","EEE",
    "QEE","EQE","EEQ","EEQ","EEQ","EEQ",
    "WEE","EWE","EEW","EEW","EEW","EEW",
    "QWE","QEW","EQW","EWQ","WEQ","WQE",
};
map<char,int>mp;
int dp[100010][10];
char a[100010];
int dis(char a[],char b[]){
    if(a[0] == b[0] && a[1] == b[1] && a[2] == b[2]){
        return 0;
    }
    else if(a[0] == b[1] && a[1] == b[2]){
        return 1;
    }
    else if(a[0] == b[2]){
        return 2;
    }
    return 3;
}
int main(){
    scanf("%s",a);
    mp['Y'] = 0;
    mp['V'] = 1;
    mp['G'] = 2;
    mp['C'] = 3;
    mp['X'] = 4;
    mp['Z'] = 5;
    mp['T'] = 6;
    mp['F'] = 7;
    mp['D'] = 8;
    mp['B'] = 9;
    memset(dp,0x3f3f3f3f,sizeof(dp));
    for(int i = 0; i < 6; i++) dp[0][i] = 3;
    int len = strlen(a);
    for(int i = 1; i < len; i++){ 
        for(int j = 0; j < 6; j++){ 
            for(int x = 0; x < 6; x++){ 
                dp[i][j] = min(dp[i][j],dp[i - 1][x] + dis(c[mp[a[i - 1]]][x],c[mp[a[i]]][j]));
            } 
        }
    }
    int ans = 0x3f3f3f3f;
    for(int i = 0; i < 6; i++){
        ans = min(ans,dp[len - 1][i]);
    }
    ans += len;
    printf("%d",ans);
    return 0;
}

J MUV LUV EXTRA

智障题

(其实也不算智障但是想到KMP就能秒切了）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e15 + 7;
int a,b,len = 0;
char s[10000010],t[10000010];
int nxt[10000010];
signed main(){
    scanf("%lld %lld",&a,&b);
    scanf("%s",s);
    for(int i = strlen(s) - 1; i >= 0; i--){
        if(s[i] == '.') break;
        else{
            t[++len] = s[i];
        }
    }
    nxt[0] = nxt[1] = 0;
    for(int i = 2,j = 0; i <= len; i++){
        while(j > 0 && t[i] != t[j + 1]) j = nxt[j];
        if(t[i] == t[j + 1]) j++;
        nxt[i] = j;
    }
    int ans = -INF;
    for(int i = 1; i <= len; i++){
        ans = max(ans,a * i - b * (i - nxt[i]));
    }
    printf("%lld",ans);
    return 0;
}

K MUV LUV UNLIMITED

能猜到是结论题

口胡了一下就直接切了

大概就是每个叶节点一直往上走走到第一个分叉点

经过的距离只要有一个是奇数就是先手必胜了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,T;
vector<int>to[1000010];
int cnt[1000010];
bool ans = 0;
void dfs(int u,int tot){
    if(cnt[u] == 0){
        if(tot % 2) ans = 1;
        return;
    }
    if(cnt[u] == 1){
        dfs(to[u][0],tot + 1);
        return;
    }
    for(int i = 0; i < to[u].size(); i++){
        int v = to[u][i];
        dfs(v,1);
    }
}
signed main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        ans = 0;
        for(int i = 1; i <= n; i++) cnt[i] = 0,to[i].clear();
        for(int i = 2,x; i <= n; i++){
            scanf("%lld",&x);
            to[x].push_back(i);
            cnt[x]++;
        }
        dfs(1,1);
        if(ans) puts("Takeru");
        else puts("Meiya");
    }
    return 0;
}

L MUV LUV ALTERNATIVE

大贪心

最左最右先走然后走中间

因为主要的影响都是在走廊里的

考虑处理相撞的问题

假设目前只有两个人

这里有一个很妙的方法就是先走离出口远的那个

然后再走离出口近的

• 如果两人离出口距离相等，则这样一次先后走可以正好避开，也就是now++在程序中的作用

• 如果两人离出口距离不等，则可以假装没有先后走正好避开，now++并不会造成影响

可以感性理解一下\kk

用set的单调性优化

复杂度O(能过)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF =  1e18 + 7;
int n,L1,L2,L3,K;
multiset<pair<int,int> >s1,s2;
multiset<int>t1,t2;
signed main(){
    scanf("%lld %lld %lld %lld %lld",&n,&L1,&L2,&L3,&K);
    int cnt = 0;
    for(int i = 1,a,x,y; i <= K; i++){
        scanf("%lld %lld %lld",&a,&x,&y);
        int dis1 = abs(L1 + 1 - y) + x;
        int dis2 = abs(L1 + L2 + 2 - y) + x;
        if(a == 1) dis2 = INF;
        else if(a == 3) dis1 = INF;
        s1.insert(make_pair(dis1,dis2));
        s2.insert(make_pair(dis2,dis1));
    }
    int now = 1;
    while(1){
        while(!s1.empty()){
            int x = s1.begin()->first;
            int y = s1.begin()->second;
            if(x <= now){
                t1.insert(y);
                s1.erase(s1.begin());
                s2.erase(s2.find(make_pair(y,x)));
            }
            else break;
        }
        while(!s2.empty()) {
            int x = s2.begin()->first;
            int y = s2.begin()->second;
            if(x <= now) {
                t2.insert(y);
                s2.erase(s2.begin());
                s1.erase(s1.find(make_pair(y,x)));
            }
            else break;
        }
        while(!t1.empty()){
            if(*t1.begin() <= now){
                t1.erase(t1.begin());
                cnt++;
            }
            else break;
        }
        while(!t2.empty()){
            if(*t2.begin() <= now){
                t2.erase(t2.begin());
                cnt++;
            }
            else break;
        }
        bool flag = 0;
        if(!t1.empty()){
            t1.erase(--t1.end()); //贪心选离二号口最远的 
            flag = 1;
        }
        else if(cnt){
            cnt--;
            flag = 1;
        }
        if(!t2.empty()) {
            t2.erase(--t2.end());
            flag = 1;
        }
        else if(cnt){
            cnt--;
            flag = 1;
        }
        if(flag) now++;
        else if(s1.empty()) break;
        else now = min(s1.begin()->first,s2.begin()->first);
    }
    printf("%lld",now - 1);
    return 0;
}

（这个和官方题解稍有出入，正确性有待证明）

目前状态：