比赛传送门：。

比赛记录：。

涨了挺多分，希望下次还能涨。

---

题意简述：

问 \(k\) 位 \(b\) 进制数 \(\overline{a_1a_2\cdots a_k}\) 的奇偶性。

题解：

若 \(b\) 是偶数，则答案等于 \(a_k\) 的奇偶性。

若 \(b\) 是奇数，则答案等于 \(\sum_{i=1}^{k}a_i\) 的奇偶性。

#include
    
     using namespace std;#define F(i,a,b) for(int i=a;i<=(b);++i)#define MN 100005int b,k;int a[MN];int main(){    scanf("%d%d",&b,&k);    F(i,1,k)scanf("%d",a+i);    if(b%2==0)puts(a[k]%2==0?"even":"odd");    else{        int s=0;        F(i,1,k)s^=a[i]&1;        puts(s?"odd":"even");    }    return 0;}
    

---

题意简述：

有 \(n\) 个线段，第 \(i\) 个覆盖了数轴上的区间 \([b_i,b_i+1]\)，保证 \(b_1<b_2<\cdots<b_n\le m\)。

你需要用不超过 \(k\) 个区间覆盖所有线段，求使用的区间总长度最小值。

题解：

假设一开始用 \(n\) 个长度为 \(1\) 的区间覆盖了所有线段。

每次可以选择相邻的两个区间，把它们合并，长度增加它们之间的距离，区间个数减少 \(1\)。

那么我们令答案等于 \(n\)，把 \(\{b_2-b_1-1,b_3-b_2-1,\ldots,b_n-b_{n-1}-1\}\) 从小到大排序，将前 \(k\) 小加入答案即可。

#include
    
     using namespace std;#define F(i,a,b) for(int i=a;i<=(b);++i)#define MN 100005int n,m,k;int a[MN],b[MN];int main(){    scanf("%d%d%d",&n,&m,&k);    F(i,1,n)scanf("%d",a+i);    F(i,1,n-1)b[i]=a[i+1]-a[i]-1;    sort(b+1,b+n);    long long s=n;    F(i,1,n-k)s+=b[i];    printf("%lld\n",s);    return 0;}
    

---

题意简述：

定义函数 \(f(a)=\max_{0<b<a}\gcd(a\oplus b,a\>\&\>b)\)。

\(q\) 次询问，每次给定 \(a_i\)，询问 \(f(a_i)\) 的值。

\(1\le q\le 10^3\)，\(2\le a_i\le 2^{25}-1\)。

题解：

如果 \(a\ne 2^i-1\)，假设 \(a\) 有 \(k\) 位，令 \(b=2^k-1-a\)，则 \(a\oplus b=2^k-1\)，\(a\>\&\>b=0\)，\(\gcd(2^k-1,0)=2^k-1\)。

容易证明 \(f(a)\le 2^k-1\)，所以这样是最大的。

如果 \(a=2^i-1\)，此时对于任意的 \(b\)，有 \(a\oplus b=a-b\)，\(a\>\&\>b=b\)，则 \(f(a)=\max_{0<b<a}\gcd(b,a-b)\)。

所以答案一定是 \(a\) 的一个不等于自身的因数。假设 \(a\) 最大不等于自身的因数为 \(d\)，取 \(b=d\) 即可得到最大的答案。

对 \(a\) 用 \(O(\sqrt{a})\) 的时间找到最小的质因子即可。

#include
    
     using namespace std;#define F(i,a,b) for(int i=a;i<=(b);++i)int q,a;int main(){    scanf("%d",&q);    F(i,1,q){        scanf("%d",&a);        if((a+1)&a){            int x=1;            while(x<=a)x<<=1;            printf("%d\n",x-1);        }        else{            int y=0;            for(int x=2;x*x<=a;++x)                if(a%x==0){y=x;break;}            if(!y)puts("1");            else printf("%d\n",a/y);        }    }    return 0;}
    

---

题意简述：

你有 \(n\) 个正整数 \(a_i\le m\)，每次可以消去 \(3\) 个相等的数或者 \(3\) 个连续的数。问最多可以消几次。

题解：

对于消去 \(3\) 个连续的数\((a-1,a,a+1)\)，相同的消除不会超过 \(3\) 次，因为如果超过 \(3\) 次，可以替换为消除 \(3\) 次相等的数。

记录 \(\mathrm{b}[i]\) 为 \(i\) 的出现次数。

考虑 \(\mathrm{dp}\)，记 \(\mathrm{f}[i][j][k]\) 表示对于小于等于 \(i\) 的数，进行了 \(j\) 次 \((i-1,i,i+1)\) 的消除，进行了 \(k\) 次 \((i,i+1,i+2)\) 的消除最多能消除几次。

这里不考虑 \(i+1\) 和 \(i+2\) 出现的次数。

转移比较显然，在保证 \(b[i]\ge j+k+l\) 的情况下，有 \(\mathrm{f}[i][k][l]=\mathrm{f}[i-1][j][k]+l+\lfloor\frac{b[i]-j-k-l}{3}\rfloor\)

#include 
    
     using namespace std;#define MN 1000005int N, M;int b[MN], f[MN][3][3];int main(){    scanf("%d%d", &N, &M);    for (int i = 1, x; i <= N; ++i) scanf("%d", &x), ++b[x];    for (int i = 1; i <= M; ++i)        for (int j = 0; j < 3; ++j)            for (int k = 0; k < 3; ++k)                for (int l = 0; l < 3; ++l)                    if (b[i] < j + k + l) continue ;                    else f[i][k][l] = max(f[i][k][l], f[i - 1][j][k] + (b[i] - j - k - l) / 3 + l);    printf("%d\n", f[M][0][0]);    return 0;}
    

---

题意简述：

一个长度为 \(n\) 的序列 \(a_1,a_2,\ldots,a_n\)。每次可以对第 \(i(1<i<n)\) 位进行操作：\(c_i\leftarrow c_{i+1}+c_{i-1}-c_i\)。

问是否可以变成另一个序列 \(b_1,b_2,\ldots,b_n\)。

题解：

首先必须有 \(a_1=b_1\) 和 \(a_n=b_n\)。

考虑原序列的差分，分析一次操作对其造成的影响：

假设 \(c_i=a_{i+1}-a_i\)，则对第 \(i\) 位的操作会让 \(c_{i-1}\) 与 \(c_i\) 交换。

则显然 \(c_i\) 形成的多重集在操作下是不会改变的，又因为只依靠交换相邻两位就可以把序列任意重排，所以只要判断原序列和最终序列的差分是否本质相同即可。

#include
    
     using namespace std;#define F(i,a,b) for(int i=a;i<=(b);++i)#define MN 100005int n,m,q,k;int a[MN],b[MN],c[MN],d[MN];int main(){    scanf("%d",&n);    F(i,1,n)scanf("%d",a+i);    F(i,1,n)scanf("%d",b+i);    if(a[1]!=b[1]||a[n]!=b[n])return puts("No"),0;    F(i,1,n-1)c[i]=a[i+1]-a[i];    F(i,1,n-1)d[i]=b[i+1]-b[i];    sort(c+1,c+n);sort(d+1,d+n);    F(i,1,n-1)if(c[i]!=d[i])return puts("No"),0;    puts("Yes");    return 0;}
    

---

题意简述：

给定一棵 \(n\) 个点的以 \(1\) 号点为根的树，有边权，保证 \(1\) 号点不是叶子。

一个性质：这棵树从 \(1\) 开始 \(\mathrm{DFS}\)，遍历到一个点之后按照编号递增的顺序遍历它的儿子，得到的 \(\mathrm{DFS}\) 序恰好是 \(1\) 到 \(n\)。

\(q\) 次询问，每次问 \(v_i\) 号点到编号在 \([l_i,r_i]\) 中的叶子的最小距离。

题解：

输入的树只有给定每个节点的父亲，这时可以通过一个栈求出每个点的子树中的最大 \(\mathrm{DFS}\) 序。

考虑对于结点 \(u\)，用支持区间加，区间查 \(\min\) 的线段树维护 \(u\) 到每个叶子的距离，则对于 \(v_i=u\) 的询问可以直接查询。

发现可以离线，我们把询问按照 \(v_i\) 排序，模拟一个 \(\mathrm{DFS}\) 的过程。

当前遍历到的结点沿着一条边改变时，就在线段树上修改全局权值加上 \(w_i\)，子树权值减去 \(-2w_i\)。

#include 
    
     #include 
     
      #include 
      
       typedef long long LL;typedef std::pair
       
         pii;const LL INF = 0x3f3f3f3f3f3f3f3f;const int MN = 500005;int N, Q;int faz[MN], d[MN], rdf[MN], stk[MN], t;LL w[MN], dis[MN];std::vector
        
          c[MN], q[MN];int l[MN], r[MN];LL Ans[MN];const int MS = 1 << 20;#define li (i << 1)#define ri (i << 1 | 1)#define mid ((l + r) >> 1)#define ls li, l, mid#define rs ri, mid + 1, rLL mn[MS], tg[MS];inline void P(int i, LL v) { mn[i] += v; tg[i] += v; }inline void pd(int i) { if (tg[i]) P(li, tg[i]), P(ri, tg[i]), tg[i] = 0; }void Mdf(int i, int l, int r, int a, int b, LL v) {    if (r < a || b < l) return ;    if (a <= l && r <= b) return P(i, v);    pd(i), Mdf(ls, a, b, v), Mdf(rs, a, b, v);    mn[i] = std::min(mn[li], mn[ri]);}LL Qur(int i, int l, int r, int a, int b) {    if (r < a || b < l) return INF;    if (a <= l && r <= b) return mn[i];    pd(i); return std::min(Qur(ls, a, b), Qur(rs, a, b));}void DFS(int u) {    Mdf(1, 1, N, 1, N, w[u]);    Mdf(1, 1, N, u, rdf[u], -2 * w[u]);    for (int i : q[u]) Ans[i] = Qur(1, 1, N, l[i], r[i]);    for (int i : c[u]) DFS(i);    Mdf(1, 1, N, 1, N, -w[u]);    Mdf(1, 1, N, u, rdf[u], 2 * w[u]);}int main() {    scanf("%d%d", &N, &Q);    stk[t = 1] = 1;    for (int i = 2; i <= N; ++i) {        scanf("%d%lld", &faz[i], &w[i]);        c[faz[i]].push_back(i);        ++d[faz[i]], ++d[i];        dis[i] = dis[faz[i]] + w[i];        while (faz[i] != stk[t]) rdf[stk[t--]] = i - 1;        stk[++t] = i;    }    while (t) rdf[stk[t--]] = N;    for (int i = 1; i <= N; ++i) {        if (d[i] == 1) Mdf(1, 1, N, i, i, dis[i]);        else Mdf(1, 1, N, i, i, INF);    }    for (int i = 1, u; i <= Q; ++i) {        scanf("%d%d%d", &u, &l[i], &r[i]);        q[u].push_back(i);    }    DFS(1);    for (int i = 1; i <= Q; ++i) printf("%lld\n", Ans[i]);    return 0;}