Codechef January Challenge 2021 Division 3 部分题解

技术文章 6个月前 完美者
2,131 0

标签:目标   red   challenge   答案   产生   cpp   bitset   一个   直接   

January Challenge 2021 Division 3

Chef and Ants

如果只有一根线,两只蚂蚁相撞可以看成沿着原路前进,这和两只蚂蚁都掉头显然等价。答案就是蚂蚁相撞的次数:负半轴蚂蚁数量 \(\times\) 正半轴蚂蚁数量

有了这样的转化,多条轴的问题也容易解决了

如果两只蚂蚁不是在中心相撞,这种情况和一根线的一样处理

如果在中心相撞,要注意两个点:

原本在答案中算多此的现在算一次,减去多余

对于每根轴上的蚂蚁,原本是和另一半还没过界的蚂蚁相撞,现在改为和身后的蚂蚁相撞

也就是在原来的基础上稍作修改即可

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
// #define int long long
void read (int &x) {
    char ch = getchar(); x = 0; int f = 0;
    while (!isdigit(ch)) { if (ch == ‘-‘) f = 1; ch = getchar(); }
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    if (f) x = -x;
} const int N = 2e5 + 5, M = 5e5 + 5;
int n, m, c[N], b[M]; vector<int> a[N]; unordered_map<int, int> mp;
signed main() {
    int T; read (T);
    while (T--) {
        read (n); long long res = 0; mp.clear();
        for (int i = 1; i <= n; ++i) a[i].clear();
        for (int i = 1; i <= n; ++i) {
            read (c[i]); a[i].resize (c[i] + 1); int cnt = 0;
            for (int j = 1; j <= c[i]; ++j)
                read (a[i][j]), cnt += (a[i][j] < 0), ++mp[abs (a[i][j])];
            res += 1ll * cnt * (c[i] - cnt);
        }
        // cout << res << endl;
        for (int i = 1; i <= n; ++i) {
            int cnt = 0;
            for (int j = 1; j <= c[i]; ++j)
                b[j] = a[i][j], cnt += (b[j] < 0);
            for (int j = 1, k = c[i]; j <= cnt; ++j) {
                while (k > cnt && b[k] + b[j] >= 0) --k;
                if (mp[abs (b[j])] > 1) {
                    res += j - 1 - (c[i] - k);
                    // cout << j << ‘ ‘ << j - 1 - (c[i] - k) << endl;
                }
            }
            for (int j = c[i], k = 1; j > cnt; --j) {
                while (k <= cnt && b[k] + b[j] < 0) ++k;
                if (mp[b[j]] > 1) {
                    res += c[i] - j - (k - 1);
                    // cout << j << ‘ ‘ << c[i] - j - (k - 1) << endl;
                }
            }
        } //res /= 2;
        for (auto i : mp) if (i.second > 1) ++res;
        printf ("%lld\n", res);
    }
    return 0;
}

Guess the Tiling

如果想要知道答案,显然要让一个 \(2\times 2\) 的方格内的线处于特殊位置(形成正方形),这样 \(ask\) 后答案会改变,就可以判断了

我们采取“边缘包围中心”的策略,就是先把左上角四个才出来,然后猜最上面一层和最左边一层,中间的都很好判断了。具体怎么判断还是很好想的

主要的难点:平均每个格子只能询问 \(4\) 次,这就要求严格的乱搞能力,也就是说在枚举周围格子状态(用二进制表示)的时候,每次只能改变一个二进制位。对于左上角的四个,以嘴上角的那个为“关键点”(根据操作它后答案是否改变来判断是否形成正方形),要枚举其他三个的状态,\(2^3=8\),给出一种顺序使相邻两个只有一个二进制位不同:\(0, 1, 3, 2, 6, 4, 5, 7\),而对于最左侧和最右侧(两层),每次推进一层,以最左侧为例:以左上的为关键点,右上的已经猜出来,直接转到关键状态,剩下两个的状态要枚举:\(0,1,3,2\)。中间的每次处理一个,其他三个都已知,直接转到目标状态,一次询问即可

代码的四个注释简短的体现了四种情况

#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int n, q, cnt, la, a[N][N]; 
void ask (int x, int y) {
    printf ("1 %d %d\n", x, y);
    fflush (stdout); a[x][y] ^= 1;
    cin >> cnt;
}
int k[8] = {0, 1, 3, 2, 6, 4, 5, 7}, p[3] = {1, 2, 4};
signed main() {
    ios_base::sync_with_stdio (0);
    cin.tie (0); //cout.tie (0);
    int T; cin >> T;
    while (T--) {
        cin >> n >> q >> cnt;
        memset (a, 0, sizeof (a));
/*
左上角
x 0
1 2
*/
        for (int i = 0; i < 8; ++i) {
            for (int j = 0, x, y; j < 3; ++j) {
                if (j == 0) x = 1, y = 2;
                if (j == 1) x = 2, y = 1;
                if (j == 2) x = y = 2;
                if ((k[i] & p[j]) && !a[x][y]) ask (x, y);
                else if (!(k[i] & p[j]) && a[x][y]) ask (x, y);
            }
            la = cnt, ask (1, 1);
                if (cnt == la + 1) {
                a[1][1] = a[2][2] = 0;
                a[1][2] = a[2][1] = 1;
                break;
            }
            if (cnt == la - 1) {
                a[1][1] = a[2][1] = a[1][2] = 1;
                a[2][2] = 0; break;
            }
        }
/*
左边缘
x 定
0 1
*/
        for (int t = 3; t <= n; ++t) {
            if (!a[t - 1][2]) ask (t - 1, 2);
            for (int i = 0; i < 4; ++i) {
                for (int j = 0; j < 2; ++j) {
                    if ((k[i] & p[j]) && !a[t][j + 1]) ask (t, j + 1);
                    else if (!(k[i] & p[j]) && a[t][j + 1]) ask (t, j + 1);
                }
                la = cnt, ask (t - 1, 1);
                if (cnt == la + 1) {
                    a[t - 1][1] = a[t][2] = 0;
                    a[t - 1][2] = a[t][1] = 1; break;
                }
                if (cnt == la - 1) {
                    a[t - 1][1] = a[t - 1][2] = a[t][1] = 1;
                    a[t][2] = 0; break;
                }
            }
        }
/*
右边缘
x 0
定 1
*/
        for (int t = 3; t <= n; ++t) {
            if (!a[2][t - 1]) ask (2, t - 1);
            for (int i = 0; i < 4; ++i) {
                for (int j = 0; j < 2; ++j) {
                    if ((k[i] & p[j]) && !a[j + 1][t]) ask (j + 1, t);
                    else if (!(k[i] & p[j]) && a[j + 1][t]) ask (j + 1, t);
                }
                la = cnt, ask (1, t - 1);
                if (cnt == la + 1) {
                    a[1][t - 1] = a[2][t] = 0;
                    a[2][t - 1] = a[1][t] = 1; break;
                }
                if (cnt == la - 1) {
                    a[1][t - 1] = a[2][t - 1] = a[1][t] = 1;
                    a[2][t] = 0; break;
                }
            }
        }
/*
定 定
定 x
*/
        for (int i = 3; i <= n; ++i)
            for (int j = 3; j <= n; ++j) {
                if (a[i - 1][j - 1]) ask (i - 1, j - 1);
                if (!a[i][j - 1]) ask (i, j - 1);
                if (!a[i - 1][j]) ask (i - 1, j);
                la = cnt, ask (i, j);
                a[i][j] = (cnt < la);
            }
        puts ("2");
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j)
                putchar (‘0‘ + a[i][j]), putchar (‘ ‘); puts ("");
        } fflush (stdout); cin >> cnt;
    }
}

And-Or Game

如果只有一种 \(|\) 运算,显然如果每次操作都发生更改,最多更改 \(20\) 次,做 \(20\)\(fwt\)

同样,可以把一堆 \(|\) 和一堆 \(\&\) 看成一次运算,每次也只能变多,这样也最多更改 \(20\) 次,一共 \(40\)\(fwt\)卡卡常就好了

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void read (int &x) {
    char ch = getchar(); x = 0; while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 1024 * 1024 * 2 + 5, mod = 1e9 + 7;
int n, m, mx, lim; ll f[N], g[N], res[N], la[N];
#define up(x, y) ((x += y) >= mod && (x -= mod))
void fwt_or (ll *a, int opt) {
    for (int i = 1; i < lim; i <<= 1)
        for (int j = 0; j < lim; j += (i << 1))
            for (int k = 0; k < i; ++k)
                if (opt == 1) up (a[i + j + k], a[j + k]);
                else up (a[i + j + k], mod - a[j + k]);
}
void fwt_and (ll *a, int opt) {
    for (int i = 1; i < lim; i <<= 1)
        for (int j = 0; j < lim; j += (i << 1))
            for (int k = 0; k < i; ++k)
                if (opt == 1) up (a[j + k], a[i + j + k]);
                else up (a[j + k], mod - a[i + j + k]);
}
ll qpow (ll x, int y) {
    ll t = 1; while (y) { if (y & 1) t = t * x % mod; x = x * x % mod, y >>= 1; } return t;
}
signed main() {
    int T; read (T);
    while (T--) {
        read (n), read (m); lim = 1, mx = 0;
        for (int i = 1, x; i <= n; ++i)
            read (x), mx = max (mx, x), f[x] = 1;
        for (int i = 1, x; i <= m; ++i)
            read (x), mx = max (mx, x), g[x] = 1;
        while (lim <= mx) lim <<= 1;
        f[0] = res[0] = 1, g[lim - 1]= 1;
        fwt_or (f, 1), fwt_and (g, 1);
        for (int i = 0; i < lim; ++i) f[i] = qpow (f[i], 21);
        for (int i = 0; i < lim; ++i) g[i] = qpow (g[i], 21);
        while (1) {
            memcpy (la, res, sizeof (res));
            int tag = 0;
            fwt_or (res, 1);
            for (int i = 0; i < lim; ++i) res[i] = res[i] * f[i] % mod;
            fwt_or (res, -1);
            fwt_and (res, 1);
            for (int i = 0; i < lim; ++i) res[i] = res[i] * g[i] % mod;
            fwt_and (res, -1);
            for (int i = 0; i < lim; ++i)
                if (!la[i] && res[i]) { tag = 1; break; }
            if (!tag) break;
        }
        int cnt = 0;
        for (int i = 0; i < lim; ++i) if (res[i]) ++cnt;
        printf ("%d\n", cnt);
        for (int i = 0; i < lim; ++i) f[i] = g[i] = res[i] = 0;
    }
    return 0;
}

Blackjack

这题最后还是没想出正解。。。写了个 \(O(\frac{n^3log_n}{w})\) 卡过去了,正解是 \(O(\frac{n^3}{w})\)

题意就是枚举一个边界 \(x\),然后在右侧选 \(y\) 个,左侧选 \(x-y\) 个,和在 \([l,r]\) 内,使 \(y\) 最小

前后缀背包是肯定要做的,\(L_{i,j,k}\) 表示前 \(i\) 个物品,选 \(j\) 个,和为 \(k\) 是否可行,\(R\) 同理。

只有 \(0/1\) 状态显然是可以用 \(bitset\) 优化的,推完一遍是 \(O(\frac{n^3}{w})\)

brute solution:

枚举边界 \(x\),枚举 \(L\) 的个数 \(j\),然后每一个可行的 \(k\)\(R\) 中对应一段区间,这个也是可以 \(bitset\) 优化的(初始一个一段是 \(1\) 的,\(\&\) 一下看一下有没有 \(1\)),应该是\(O(\frac{n^4}{w})\)

my solution:

先把 \(L,R\) 的二 、三两维翻转,变成 \(L_{i,j,k}\) 表示前 \(i\) 个物品,和为 \(j\),选 \(k\) 个是否可行

同样枚举 \(x\),对于 \(L\) 中每一种和,在 \(R\) 中对应一段下标,可以用数据结构维护(st表,线段树...)。然后用 \(\_Find\_first()\) 找第一个 \(1\),即最小的答案

有一个需要注意的地方是由于 \(L\)\(R\) 选的物品要满足数量和是个定值,在推 \(L\) 的时候会发生一些改变,\(L\)\(R\) 的方程式不太一样

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
// using namespace std;
void read (int &x) {
    char ch = getchar(); x = 0; while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 1005;
int n, res, mx, L, R, len, a[N], lg[N];
std::bitset<505> f[N][N], g[N][N], tmp, c[12][N];
void build (int k) {
    for (int i = 0; i<= R; ++i) c[0][i] = g[k][i];
    // for (int i = R + 1; i <= R + (1 << len); ++i) c[0][i].reset();
    for (int i = 1; i <= len; ++i) {
        int lim = R - (1 << i);
        for (int j = 0; j <= lim; ++j)
            c[i][j] = c[i - 1][j] | c[i - 1][j + (1 << (i - 1))];
    }
}
void query (int l, int r) {
    l = std::max (l, 0), r = std::min (r, R); int t = lg[r - l + 1];
    tmp |= c[t][l] | c[t][r - (1 << t) + 1];
}
int get (int x) {
    int ans = 10000; build (x + 1);
    for (int i = 0; i <= R; ++i) {
        // int l = L - i, r = R - i;
        tmp.reset(); query (L - i, R - i); tmp &= f[x][i];
        ans = std::min (ans, (int)tmp._Find_first());
    }
    return ans;
}
signed main() {
    int T; read (T); lg[0] = -1;
    for (int i = 1; i <= 1000; ++i) lg[i] = lg[i >> 1] + 1;
    while (T--) {
        read (n), read (L), read (R);
        int zero = 0, ss = 0; mx = R;
        for (int i = 1; i <= n; ++i) read (a[i]);
        for (int i = 1; i <= n; ++i) {
            ss += a[i]; if (ss >= L && ss <= R) { zero = 1; break; }
        }
        if (zero) { puts ("0"); continue; }
        for (int i = 0; i <= mx; ++i)
            f[0][i].reset(), g[n + 1][i].reset();
        // for (int i = 0; i <= 1000) qwq[i].reset();
        f[0][0][0] = g[n + 1][0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= mx; ++j) f[i][j] = f[i - 1][j] << 1;
            for (int j = mx; j >= a[i]; --j)
                f[i][j] |= f[i - 1][j - a[i]];
        }
        for (int i = n; i >= 1; --i) {
            for (int j = 0; j <= mx; ++j) g[i][j] = g[i + 1][j];
            for (int j = mx; j >= a[i]; --j)
                g[i][j] |= g[i + 1][j - a[i]] << 1;
        }
        len = lg[R - L + 1]; res = 100000;
        for (int i = 1; i < n; ++i)
            res = std::min (res, get (i));
        if (res > n / 2) res = -1;
        printf ("%d\n", res);
    }
    return 0;
}

very good solution:

其实和普通 \(dp\) 优化方法是一样的,记录 \(0/1\) 状态往往产生很多浪费,即使有 \(bitset\) 加持。

这种时候可以想一想转向记录最佳状态。

\(L,R\) 还是按照上面那样翻转二、三维

\(L‘_{i,j}\) 表示选了和为 \(j\),选了 \(i\) 个数,满足 \(L_{x,i,j}=1\) 的最小的 \(x\)

\(R‘_{i,j}\) 表示和为 \(j\),选了 \(i\) 个数,满足 \(R_{x,i,j}=1\) 的最大的 \(x\)

在原来递推求 \(L,R\) 的基础上,每次计算 \(L_x xor L_{x-1}\),多出来的 \(1\) 就是新产生的可行方案,在 \(L‘\) 中修改。找所有的 \(1\) 依然可以用 \(bitset\) 优化遍历,求出 \(L‘,R‘\) 的复杂度依然是 \(O(\frac{n^3}{w})\)

有了 \(L‘,R‘\),枚举 \(R‘\) 的每一个 \(i,j\),此时 \(L‘\) 中的 \(i’\) 在一段区间内,\(j‘\) 随意(所以可以把所有 \(j‘\) 缩到一起变成一维数组),如果存在 \(L‘_{i‘,j‘}<R‘_{i,j}\),则答案可以为 \(j\)。这个过程同样可以数据结构优化,复杂度 \(O(n^2log_n)\)

所以复杂度为 \(O(n^2log_n+\frac{n^3}{w})\),此问题得到完美解决,然而代码还没有写。。。

Codechef January Challenge 2021 Division 3 部分题解

标签:目标   red   challenge   答案   产生   cpp   bitset   一个   直接   

原文地址:https://www.cnblogs.com/whx666/p/14295514.html

版权声明:完美者 发表于 2021-01-19 12:20:04。
转载请注明:Codechef January Challenge 2021 Division 3 部分题解 | 完美导航

暂无评论

暂无评论...