Nhk R1 Editorial

cirnovsky · 2021-12-30 22:14:15 · 个人记录

前言

这场比赛的锅貌似有点多…在准备的时候就已经推迟过三次，在这里为对各位比赛时造成的困扰抱歉。这是出题组第一次放比赛，欢迎批评指正。

主要问题在于 C 的数据造水了，hack 数据造反了于是没有 hack 到。D 的数据也不强。再次感到抱歉，并且努力做出改正。

最后重拾一下出比赛的初心以及发表一些 mozheng & Chuni 言论：罚金一百万元（不是），以及为自己的 Welcome to NHK 做一个 Sunny Side 式的收尾，或者称之为小结。总之都没差啦……虽然只是举个例子，但我们要告诉你的，就是这样的故事。

A

给出两种构造方式：

• 考虑 d 的每一位，如果当前位为 0，则不对答案产生影响；如果当前位为 1，又因为 1\text{ xor }1\text{ xor }0=0,1\text{ or }1\text{ or }0=1，所以把 a,b,c 其中两个按位或上 2^i 即可。
• \begin{cases}a=d\\b=\text{lowbit}(d)\\c=d\text{ xor }\text{lowbit}(d)\end{cases}

当然这两种方式并无什么不同。无解的情况是 d=2^n。

#include<bits/stdc++.h>
int ans[3],d;
signed main() {
    scanf("%d",&d);
    if((d&-d)==d)   return puts("-1"),0;
    for(int now=0; d; d^=d&-d)  ans[now]|=d&-d,ans[(now+=1)%=3]|=d&-d;
    printf("%d %d %d\n",ans[0],ans[1],ans[2]);
    return 0;
}

#include<bits/stdc++.h>
int d;
signed main() {
    scanf("%d",&d);
    if((d&-d)==d)   return puts("-1"),0;
    printf("%d %d %d\n",d,(d&-d),d-(d&-d));
    return 0;
}

B

首先 a_1=x_1，考虑第二位，因为保证有解，所以 x_2\mid x_1，同理可得 \forall i\in(1,n],x_i\mid x_{i-1}，可以预见数据中最多有 \log 个非 1 数，于是不断往上推即可。

#include<bits/stdc++.h>
int n,x,pre,now,vis[2000100];
signed main() {
    scanf("%d\n%d",&n,&x);
    vis[pre=now=x]=1;
    printf("%d ",x);
    for(int i=1; i<n; ++i) {
        scanf("%d",&x);
        if(pre!=x)  pre=now=x;
        else    while(vis[now]) now+=pre;
        vis[now]=1;
        printf("%d ",now);
    }
    return 0;
}

C

首先我们有个 \mathcal {O}(nm) 的暴力遍历做法，读者很容易想到这样遍历了太多冗余的点。

于是很自然地想到将一个块缩成一个点。具体的，对于每一列，我们将障碍物隔开的一列点看成一个点，这样的店最多有 2k 个。

然后 dp 即可，dp_i=[(\sum_{j=1}^idp_j)>0]。

然后要注意一个块能否转移到另一个块的判断条件有细节：并不是看两个块是联通，而是定义 mx_i 为能到达第 i 个块的最低点（贪心），看从 mx_j 起是否能到达 mx_i，再更新 mx_i。

当然好像有更简便的做法，余不会。

同时存在更优的做法，为了代码的简便起见并没有作为 std，欢迎分享。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#define LL long long
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
const int MAXN = 5005, MAXM = 1e7 + 5;
vector <int> v[MAXM], cx;
map <int, bool> vis;
map <int, int> lst;
struct Point {
    int X, Y, Y_;
}arr[MAXN];
int n, m, k, tot, mx, mn[MAXN];
int pre[MAXM];
bool dp[MAXN];
bool check(int x, int y) {
    if(arr[x].X == arr[y].X - 1) {
        if(arr[x].Y_ < arr[y].Y) return 0;
        if(arr[x].Y > arr[y].Y_) return 0;
        if(max(arr[y].Y, mn[x]) >= arr[y].Y && max(arr[y].Y, mn[x]) <= arr[y].Y_) {
            mn[y] = min(mn[y], max(arr[y].Y, mn[x])); return 1;
        }
        return 0;
    }
    if(arr[x].Y > arr[y].Y_) return 0;
    if(max(arr[y].Y, mn[x]) >= arr[y].Y && max(arr[y].Y, mn[x]) <= arr[y].Y_) {
        mn[y] = min(mn[y], max(arr[y].Y, mn[x])); return 1;
    }
    return  0;
}
int main() {
    int x, y;
    scanf("%d%d%d", &n, &m, &k); memset(mn, 0x3f, sizeof(mn));
    for(int i = 1; i <= k; i ++) {
        scanf("%d%d", &x, &y); v[x].push_back(y); cx.push_back(x); mx = max(mx, x);
    }
    sort(cx.begin(), cx.end());
    int Lst = 0;
    for(auto i : cx) {
        if(vis[i]) continue;
        pre[i] = 1;
        lst[i] = Lst; Lst = i; sort(v[i].begin(), v[i].end()); vis[i] = 1;
        int las = 0;
        for(auto j : v[i]) {
            if(j == las) { las ++; continue; }
            tot ++; arr[tot].X = i; arr[tot].Y = las; arr[tot].Y_ = j - 1; las = j + 1;
        }
        if(las <= m) tot ++, arr[tot].X = i, arr[tot].Y = las, arr[tot].Y_ = m;
    }
    for(int i = 1; i <= 10000000; i ++) pre[i] += pre[i - 1];
//  for(int i = 1; i <= tot; i ++) {
//      printf("%d %d %d\n", arr[i].X, arr[i].Y, arr[i].Y_);
//  }
    if(!tot) { printf("Yes"); return 0; }
    if(vis[0]) {
        if(arr[1].Y != 0) { printf("No"); return 0; }
        dp[1] = 1; mn[1] = 0;
    }
    else {
        for(int i = 1; i <= tot; i ++) if(arr[i].X == arr[1].X) dp[i] = 1, mn[i] = arr[i].Y, dp[i] = 1;
    }
    for(int i = 1; i <= tot; i ++) {
        for(int j = 1; j < i; j ++) {
            if(arr[j].X == arr[i].X) continue;
            if(((arr[j].X + 1 < arr[i].X && pre[arr[i].X - 1] - pre[arr[j].X] == 0) || arr[j].X + 1 == arr[i].X) && arr[j].X == lst[arr[i].X] && check(j, i)) {
                dp[i] |= dp[j];
            }
        }
    }
    if(vis[n]) {
        if(arr[tot].Y_ != m) { printf("No"); return 0; }
        if(dp[tot]) printf("Yes");
        else printf("No");
    }
    else {
        bool ans = 0;
        for(int i = 1; i <= tot; i ++) if(arr[i].X == mx) ans |= dp[i];
        if(ans) printf("Yes");
        else printf("No");
    }
    return 0;
}

D

你考虑维护 n 个单调队列。第 i 个单调队列的数满足：\sum_{d=1}^ia_dc_d，其中 c_i 一定为正数。

每次我们取 n 个单调队列的队头最小值 r，设其在第 i 个队列，那么我们将 a_d+r 放入第 d 个队列中。（i<d\le n）

可以证明，由于 a 数组为正数，这样队列一定是单调的。

一直这样做 k 次，取 r_k 即可。时间复杂度：\mathcal {O}(nk)。数据可以（？）把带 \mathrm {log} 做法卡掉。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <ctime>
#include <queue>
#define LL long long
using namespace std;
const int MAXN = 85;
queue <LL> que[MAXN];
int n, k, a[MAXN], num;
LL minn;
int main() {
    scanf("%d%d", &n, &k); k --;
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    que[0].push(0);
    for(int i = 1; i <= k + 1; i ++) {
        minn = 9e18;
        for(int j = 0; j <= n; j ++) if(!que[j].empty() && que[j].front() < minn) minn = que[j].front(), num = j;
        while(que[0].size()) que[0].pop();
        que[num].pop();
        for(int j = num; j <= n; j ++) que[j].push(minn + a[j]);
    }
    printf("%lld", minn);
    return 0;
}

E