第一次深夜打 CF 不回寝室.

A K-th Largest Value

给定 $a_{1,2,\ldots,n}\in\{0,1\}$ 数, 每次给定 $x$ 将 $a_x$ 变为 $1-a_x$ 或者询问第 $k$ 大.

直接记录有几个 $0/1$ 即可.

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int a[100005];

int main() {
    int n,m,s=0,u,v; scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i) {scanf("%d",&a[i]); s+=a[i];}
    while (m--) {
        scanf("%d%d",&u,&v);
        if (u==1) {a[v]?--s:++s; a[v]^=1;}
        else printf("%d\n",v<=s?1:0);
    }
    return 0;
}

B Minimal Cost

给定下图, 第 $i$ 行在第 $1\le a_i\le10^6$ 列处有一个障碍, 纵向移动一个障碍需要 $v$ 的代价, 横向需要 $v$ 的代价, 问最少需要多少代价使 $(1,0)$ 和 $(n,10^6+1)$ 连通.

考虑以下三种情况:

• 如果相邻两行 $a_i$ 之差 $\ge2$, 则能直接从中间穿过去而不需要移动;
• 否则如果之差 $=1$, 则可以将其中一个横向或纵向移动一次实现;
• 否则需要横向移动任意一行, 然后变为第二种情况.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;

int a[100005];

int main() {
    int t,n,u,v,p; scanf("%d",&t); while (t--) {
        scanf("%d%d%d",&n,&u,&v); p=v+min(u,v);
        for (int i=1;i<=n;++i) {
            scanf("%d",&a[i]);
            if (i>1&&a[i]!=a[i-1]) p=min(p,min(u,v));
            if (i>1&&abs(a[i]-a[i-1])>1) p=0;
        }
        printf("%d\n",p);
    }
    return 0;
}

C Pekora and Trampoline

有 $n$ 个排成一列的蹦床, 第 $i$ 个弹力系数为 $S_i$. 每次可以随意挑选一个蹦床 $p$ 出发, 然后跳到 $p+S_p$ 个蹦床, 直到 $p>n$ 为止, 同时跳到过 (没跳到不算) 的每个蹦床 $S_i\gets\max\{S_i-1,1\}$. 问最少几次能使所有 $S_i=1$.

直接暴力跳的过程中加一些优化即可.

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;

int s[5005],r[5005];

int main() {
    int t,n; ll a;
    scanf("%d",&t); while (t--) {
        scanf("%d",&n); a=0;
        for (int i=1;i<=n;++i) {
            scanf("%d",&s[i]);
            r[i]=i+1;
        }
        for (int i=1;i<=n;++i) {
            if (s[i]+i>=max(n,i+1)) {
                a+=s[i]+i-max(n,i+1);
                s[i]=max(n,i+1)-i;
            }
            while (s[i]>1) {
                for (int j=i;j<=n;) {
                    if (s[j]>1) j+=s[j]--;
                    else {
                        while (r[j]<=n&&s[r[j]]==1) r[j]=r[r[j]];
                        j=r[j];
                    }
                }
                ++a;
            }
        }
        printf("%lld\n",a);
    }
    return 0;
}

D Zookeeper and The Infinite Zoo

有一张无限个点的图, 有从 $u$ 到 $u+v$ 的有向边当且仅当 $u~\mathrm{and}~v=v$, 多次询问是否存在两点间道路.

有个结论, 不过直接看代码更好理解.

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;

int s[5005];
vector<int> e[5005];

int main() {
    int t,u,v,c;
    scanf("%d",&t); while (t--) {
        scanf("%d%d",&u,&v); c=0;
        if (u>v) {puts("NO"); goto query_end;}
        for (int i=0;i<30;++i)
            if ((c+=((u>>i)&1)-((v>>i)&1))<0) {
                puts("NO"); goto query_end;
            }
        puts("YES");
query_end:;
    }
    return 0;
}

E Fib-tree

结论是如果能拆分就拆分, 拆不动了说明不合法.

假设有两种拆分方式 $F_{a1}+F_{a2}=F_{b1}+F_{b2}$, 再下一步拆分一定会拆成相同的 $F_{c1}+F_{c2}+F_{c3}$.

F Magnets

G Switch and Flip

H Yuezheng Ling and Dynamic Tree

I Ruler Of The Zoo

不会, 都不会.