【题解】第六届传智杯决赛题解

作为决赛，整体难度相对高于初赛和复赛。决赛一共8题，其中A组使用6题：BCDEFH；B组使用6题：ACDEFG

补题链接：https://ac.nowcoder.com/acm/contest/78721

A 丰川睦子的质数合数

知识点：模拟

签到题。只需要将除了1以外其余的数加起来即可。

参考代码：

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    long long sum = 0;
    while (n--) {
        int x;
        cin >> x;
        if (x != 1) sum += x;
    }
    cout << sum << endl;
}

B 转纸杯游戏

知识点：模拟

签到题。按题意模拟交换过程即可。

参考代码：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n,k;
    cin>>n>>k;
    vector<int> a(4);
    a[k] = 1;
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        swap(a[u] , a[v]);
    }
    cout<<max_element(a.begin(), a.end())-a.begin();
}

C 千早素世的互斥数组

知识点：前缀和

我们首先预处理出有哪些位置是不同的，然后将不同的标记为0，相同的标记为1，这样就相当于查询区间和是否为0，使用前缀和即可。

参考代码：

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> a(n), b(n);
    for (auto &i : a) {
        std::cin >> i;
    }
    for (auto &i : b) {
        std::cin >> i;
    }

    std::vector<int> s(n + 1);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + (a[i] == b[i]);
    }

    int q;
    std::cin >> q;

    while (q--) {
        int l, r;
        std::cin >> l >> r;
        l--;

        std::cout << (s[r] - s[l] ? "NO" : "YES") << "\n";
    }

    return 0;
}

D. 长崎爱音的ansy++

知识点：构造

本题本质上即为：构造一组算法可以在给定的规约条件下，判断输入的字符串为奇数还是偶数。

一个很明显的思路是，由于指判断奇数还是偶数，所以不需要管每个字母是什么。因此我们可以先用两个语句将所有字母都变成'a'。

然后使用change("aaa","a")即可将字符串长度变成不小于2。

请注意，不能用change("aa","")，因为它会将长度为偶数的字符串变成空串，而change("","even")是不合理的，因为空串是任意字符串的子串，按题目约束会导致直接死循环。

参考代码：

#include<bits/stdc++.h>
using namespace std;
void solve(int _){
	cout<<"change(\"b\",\"a\");"<<endl;
	cout<<"change(\"c\",\"a\");"<<endl;
	cout<<"change(\"aaa\",\"a\");"<<endl;
	cout<<"change(\"aa\",\"even\");"<<endl;
	cout<<"change(\"a\",\"odd\");"<<endl;
}

int main(int argc,char *argv[]){
	int t = 0;
	
	solve(t);
	return 0;
}

E. 小苯的矩阵染色

题意：给定面积不超过 20 的矩阵，给定起点和终点问是否能不经过同一个点的情况下将矩阵的空地位置全部恰好经过一次。

本题数据范围较小，DFS剪枝和存矩阵形态的BFS均可通过，同时本题也是经典哈密顿路径问题，于是自然想到可以使用状压 。

首先将矩阵的所有空地按照任意顺序标上正整数编号作为图的节点编号，问题就转为了求这张节点不超过20个的无向图是否存在一个合法的哈密顿路径。

我们可以定义 表示考虑以 号点结尾的，当前已经经过的点的状态数为 ，这个状态是否可以做到。（其中 是一个二进制数表示当前已经经过的点的状态，）

状态转移，首先我们枚举所有的 状态，那么 的二进制为 1 的位都有可能是这个状态最后一个经过的点，因此我们枚举所有 二进制中的 1，由于转移是考虑上一步的，那上一步一定是能转移到 这个状态的，因此上一步的结尾点 也是 的二进制中的某位 1，因此再枚举 作为上一步的结尾点，执行： 能否到达 。 （其中 表示按位异或， 表示按位或， 表示按位与）

最终如果某个 为 ，则说明存在合法哈密顿路径，即以 结尾，可以经过所有 个点。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define inf 1e18
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<ll, ll> P;
#define x first
#define y second
#define pi acos(-1)
#define int long long

const int p = 1e9 + 7;
const int pp = 998244353;

int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};

ll ksm(ll a, ll b, ll p) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = (ans * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return ans % p;
}

std::mt19937 rng;  // 随机数生成器  
int rand(int l, int r) {
    std::uniform_int_distribution<int> distribution(l, r);
    return distribution(rng);
}

void add(int & x, int y, int p) {
	x %= p;
	y %= p;
	x = ((x + y) % p + p) % p;
}

int inv(int x, int p) {
	x %= p;
	return ksm(x, p - 2, p);
}

const int N = 20, M = 1 << N;
int n, m, c, sx, sy;
int dp[M][N], a[N][N];
string mp[N];
int g[N][N];

void solve() {
    memset(a, -1, sizeof a);
    cin >> n >> m >> sx >> sy;
    sx -- ;
    sy -- ;
    for(int i = 0; i < n; i++) {
        cin >> mp[i];
        for(int j = 0; j < m; j++) {
            if(mp[i][j] == '.') {
                a[i][j] = c ++ ;
//                 cout << "i : " << i << ", j : " << j << ", c : " << c << endl;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(mp[i][j] == '.') {
                for(int d = 0; d < 4; d++) {
                    int xx = i + dx[d], yy = j + dy[d];
                    if(xx < 0 || xx >= n || yy < 0 || yy >= m || a[xx][yy] == -1) continue;
                    int u = a[i][j], v = a[xx][yy];
                    g[u][v] = g[v][u] = 1;
                }
            }
        }
    }
    int s = a[sx][sy];
    dp[1 << s][s] = 1;
    for(int i = 1; i < 1 << c; i++) {
        for(int j = 0; j < c; j++) {
            if(i >> j & 1) {
                for(int k = 0; k < c; k++) {
                    if(i >> k & 1) {
                        dp[i][j] |= dp[i ^ (1 << j)][k] & g[k][j];
                    }
                }
            }
        }
    }
    for(int j = 0; j < c; j++) {
        if(dp[(1 << c) - 1][j]) {
            cout << "YES" << endl;
            return ;
        }
    }
    cout << "NO" << endl;
}



signed main () {
//     init(minp, primes, m); // primes
//     init();
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int _ = 1;
//   cin >> _;
    while(_ -- ) {
        solve();
    }
    return 0;
}

F. 小红的01矩阵

知识点：dfs，组合数学

对于的情况，我们只需要dfs即可找到最终的答案数量。dfs最多的搜索次数为，不会超过2e6次。

对于的情况，显然最终的异或只能是0。我们根据的值分类讨论：

若，则只有1种方案。

若，方案数为，因为时，必然会有4个1为这种形式：

11

11

然后行中任选2行，列中任选2列放置这4个1。

若，方案数为，因为时，必然会有6个1为这种形式：

011

110

101

类似的形式共有6组。行中任选3行，列中任选3列按以上形式放置这6个1即可。

参考代码：

#include <bits/stdc++.h>

template <typename T>
constexpr static T power(T a, int64_t b) {
    assert(b >= 0);
    T res = 1;
    while (b) {
        if (b & 1) {
            res *= a;
        }
        b >>= 1;
        a *= a;
    }
    return res;
}

template <typename T, T MOD>
struct ModInt {
    using prod_type = std::conditional_t<std::is_same_v<T, int>, int64_t, __int128>;
    T val;
    constexpr ModInt(const int64_t v = 0) : val(v % MOD) { if (val < 0) val += MOD; }
    constexpr ModInt operator+() const { return ModInt(val); }
    constexpr ModInt operator-() const { return ModInt(MOD - val); }
    constexpr ModInt inv() const { return power(*this, MOD - 2); }
    constexpr friend ModInt operator+(ModInt lhs, const ModInt rhs) { return lhs += rhs; }
    constexpr friend ModInt operator-(ModInt lhs, const ModInt rhs) { return lhs -= rhs; }
    constexpr friend ModInt operator*(ModInt lhs, const ModInt rhs) { return lhs *= rhs; }
    constexpr friend ModInt operator/(ModInt lhs, const ModInt rhs) { return lhs /= rhs; }
    constexpr ModInt &operator+=(const ModInt x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    constexpr ModInt &operator-=(const ModInt x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    constexpr ModInt &operator*=(const ModInt x) {
        val = prod_type(val) * x.val % MOD;
        return *this;
    }
    constexpr ModInt &operator/=(const ModInt x) { return *this *= x.inv(); }
    bool operator==(const ModInt b) const { return val == b.val; }
    bool operator!=(const ModInt b) const { return val != b.val; }
    friend std::istream &operator>>(std::istream &is, ModInt &x) noexcept { return is >> x.val; }
    friend std::ostream &operator<<(std::ostream &os, const ModInt x) noexcept { return os << x.val; }
    constexpr static ModInt identity() { return 1; }
    constexpr ModInt pow(int64_t p) { return power(*this, p); }
};
using Z = ModInt<int, 1'000'000'007>;

struct Comb {
    int n;
    std::vector<Z> _fac, _invfac, _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

Z solve(int n, int k) {
    auto check = [&](const std::vector<std::vector<int>>& a) {
        std::vector<int> row(n), col(n);
        for (int i = 0; i < n; i++) {
            row[i] = std::accumulate(a[i].begin(), a[i].end(), 0, std::bit_xor<>());
            col[i] = std::accumulate(a.begin(), a.end(), 0, [&](int x, const auto &y) { return x ^ y[i]; });
        }
        int x = row[0];
        return row == std::vector(n, x) && col == std::vector(n, x);
    };

    Z ans = 0;
    std::vector a(n, std::vector(n, 0));
    auto dfs = [&](auto &&self, int x, int y, int m) -> void {
        if (m > k) return;
        if (x == n) {
            if (m == k && check(a)) {
                ans += 1;
            }
            return;
        }

        for (int i = 0; i < 2; i++) {
            a[x][y] = i;
            self(self, x + (y + 1) / n, (y + 1) % n, m + i);
        }
    };

    dfs(dfs, 0, 0, 0);
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;

    if (n <= 6) {
        std::cout << solve(n, k) << "\n";
    } else {
        if (k == 0) {
            std::cout << "1\n";
        } else if (k == 4) {
            std::cout << comb.binom(n, 2) * comb.binom(n, 2) << '\n';
        } else if (k == 6) {
            std::cout << comb.binom(n, 3) * comb.binom(n, 3) * 6 << '\n';
        } else {
            std::cout << "0\n";
        }
    }

    return 0;
}

G 智乃画树状数组

根据题意模拟，树状数组上每个节点的管辖区间为，节点高度为。

画图可以使用一些小技巧，例如按照如下的过程会比较容易：

1、先画出边框，以及每个矩形区域（不包含数字标号）

2、使用位运算或，1表示横线，2表示竖线，3表示交叉

3、最后在定位每个数字标号的坐标，填入数字。

参考代码：

#include <bits/stdc++.h>

const int MAXN = 2010;
using namespace std;

int lowbit(int x)
{
    return x & -x;
}

int get_deeep(int x)
{
    int ret = 0;
    while (x)
    {
        ret++;
        x >>= 1;
    }
    return ret;
}


struct fame
{
    vector<vector<char>> a;
    int h_, w_;
    int H, W;

    fame(int h, int w) : h_(h), w_(w)
    {
        H = 2 * h + 3;
        W = 4 * w + 3;
        a = vector<vector<char>>(H + 5, vector<char>(W + 5));
        for (int i = 1; i < H - 1; ++i)
        {
            for (int j = 1; j < W - 1; ++j)
            {
                a[i][j] = ' ';
            }
        }
        for (int i = 0; i < H; ++i)
        {
            a[i][0] = a[i][W - 1] = '*';
            a[i][W] = '\0';
        }
        for (int i = 0; i < W; ++i)
        {
            a[0][i] = a[H - 1][i] = '*';
        }
    }

    void print()
    {
        for (int i = 0; i < H; ++i)
        {
            printf("%s\n", a[i].data());
        }
    }

    void draw_number(int x, int y, int val)
    {
        stack<int> stk;
        while (val)
        {
            stk.push(val % 10);
            val /= 10;
        }
        while (!stk.empty())
        {
            auto num = stk.top() + '0';
            stk.pop();
            a[x][y++] = num;
        }
    }

    void draw_line(int x, int y)
    {
        while (a[x][y] == ' ')
        {
            a[x++][y] = '|';
        }
    }

    void drwa_block_fame(int lx, int rx, int ly, int ry)
    {
        a[lx][ly] = a[rx][ly] = a[lx][ry] = a[rx][ry] = '+';
        for (auto i = lx + 1; i < rx; ++i)
        {
            if(a[i][ly]==' ')
            {
                a[i][ly] = '|';
            }
            if(a[i][ry] ==' ')
            {
                a[i][ry] = '|';
            }
        }
        for (auto i = ly + 1; i < ry; ++i)
        {
            if(a[lx][i]==' ')
            {
                a[lx][i] = '-';
            }
            if(a[rx][i] ==' ')
            {
                a[rx][i] = '-';
            }
        }
    }

    void draw_block(int val, int h, int l, int r)
    {
        h++;
        auto X = (h_ - h) * 2 + 1;
        auto Y = l * 4 + 1;
        auto rX = (h_ - h + 1) * 2 + 1;
        auto rY = (r + 1) * 4 + 1;
        if (val > 0)
        {
            draw_number(X + 1, rY - 3, val);
        }
        if (l != r)
        {
            drwa_block_fame(X, rX, Y, rY - 4);
        }
        drwa_block_fame(X, rX, rY - 4, rY);
    }

    void draw()
    {
        for (int i = 0; i < w_; ++i)
        {
            draw_block(i + 1, 0, i, i);
        }
        for (int i = 0; i < w_; ++i)
        {
            draw_block(i + 1, get_deeep(lowbit(i + 1)), i - lowbit(i + 1) + 1, i);
        }
    }
};


int main()
{
    int n, h, w;
    scanf("%d", &n);
    w = n;
    h = get_deeep(n) + 1;
    fame f(h, w);
    f.draw();
    f.print();
    return 0;
}

H 白浅模大佬

首先注意到的取值只有种，则是一个等差数列，想到暴力维护区间等差数列。

即每个数最多暴力次，总共暴力，完全能接受。

接下来需要一种数据结构能够，快速定位到需要暴力的位置，快速区间求和。

接下来随便使用一种数据结构维护即可。

1、考虑分块，块内维护堆piar<next,pos>，next表示距离下一次暴力的值，pos表示坐标，如果操作覆盖整块就只暴力触发修改的位置，如果不满整块就全暴力了，全局总的暴力次数是固定的，所以无所谓。

2、考虑线段树暴力，如果需要更新，就一路更新到叶子结点。

复杂度，看上去复杂度很高，但是由于实际上很难让不同的值每次同时触发暴力，所以实际上跑起来蛮快的。

参考代码：

#include <bits/stdc++.h>
using namespace std;

template <typename T, std::size_t N>
struct _vec : public _vec<std::vector<T>, N - 1>
{
};

template <typename T>
struct _vec<T, 0>
{
    using type = T;
};
template <typename T, std::size_t N>
using vec_t = typename _vec<T, N>::type;

template <typename T>
vec_t<T, 0> vec_t_create(const T &data)
{
    return data;
}

template <typename T, size_t arg0, size_t... args>
vec_t<T, sizeof...(args) + 1> vec_t_create(const T &data)
{
    return vec_t<T, sizeof...(args) + 1>(arg0, vec_t_create<T, args...>(data));
}

void read(int &x)
{
    scanf("%d", &x);
}

void read(long long &x)
{
    scanf("%lld", &x);
}

void print(int x)
{
    printf("%d", x);
}

void print(long long x)
{
    printf("%lld", x);
}

template <typename T, typename... Args>
void read(T &arg0, Args &...args)
{
    read(arg0);
    read(args...);
}
template <typename T>
void println(T x)
{
    print(x);
    printf("\n");
}

template <typename T, typename... Args>
void println(T arg0, Args... args)
{
    print(arg0);
    printf(" ");
    println(args...);
}

template <typename T>
void vread(T *begin, T *end)
{
    for (T *i = begin; i != end; ++i)
    {
        read(*i);
    }
}
const int MAXN = 200005;

namespace chino
{
    class divBlock
    {

    private:
        long long n_;
        long long sn_;
        bool f_;

    public:
        divBlock(long long n)
        {
            n_ = n;
            sn_ = std::sqrt(n_ + 0.5);
            f_ = sn_ != (n_ / sn_);
        }

        long long belone(long long x)
        {
            return (x <= sn_ ? x : (sn_ << 1) - n_ / x + f_) - 1;
        }

        long long l(long long id)
        {
            if (id < 0 || id > belone(n_))
            {
                return -1;
            }
            return id + 1 <= sn_ ? id + 1 : n_ / (belone(n_) - id + 2) + 1;
        }

        long long r(long long id)
        {
            if (id < 0 || id > belone(n_))
            {
                return -1;
            }
            return n_ / (n_ / l(id));
        }
    };

    void divBlockSegments(long long n, std::function<void(long long id, long long l, long long r)> cb)
    {
        for (long long l = 1, r, id = 0; l <= n; id++, l = r + 1)
        {
            r = n / (n / l);
            cb(id, l, r);
        }
    }
}
long long n, m, c;

struct node
{
    long long sum;
    long long scdx;
    long long less;
    long long x;
    long long lazy;
};

struct segmentTree
{

    int N_;
    int n_;
    std::vector<node> td_; // tree data
    chino::divBlock block;

    void pushdown_(int root, int L, int R)
    {
        if (td_[root].lazy)
        {
            td_[root].less -= td_[root].lazy;
            td_[root].sum -= td_[root].scdx * td_[root].lazy;
            if (L != R)
            {
                td_[root << 1].lazy += td_[root].lazy;
                td_[root << 1 | 1].lazy += td_[root].lazy;
            }
            else
            {
                td_[root].x += td_[root].lazy;
            }
            td_[root].lazy = 0;
        }
    }

    void update_(int root, int L, int R)
    {
        auto mid = (L + R) >> 1;
        pushdown_(root << 1, L, mid);
        pushdown_(root << 1 | 1, mid + 1, R);
        td_[root].less = min(td_[root << 1].less, td_[root << 1 | 1].less);
        td_[root].scdx = td_[root << 1].scdx + td_[root << 1 | 1].scdx;
        td_[root].sum = td_[root << 1].sum + td_[root << 1 | 1].sum;
    }

    void build_(int l, int r, int root, int a[])
    {
        td_[root] = {};
        if (l == r)
        {
            td_[root].x = a[l];
            if (td_[root].x <= c)
            {
                td_[root].less = block.r(block.belone(td_[root].x)) - td_[root].x;
                td_[root].scdx = c / td_[root].x;
                td_[root].sum = c - td_[root].scdx * td_[root].x;
            }
            else
            {
                td_[root].less = (1 << 30);
                td_[root].scdx = 0;
                td_[root].sum = c;
            }
            return;
        }
        auto mid = (l + r) >> 1;
        build_(l, mid, root << 1, a);
        build_(mid + 1, r, root << 1 | 1, a);
        update_(root, l, r);
    }

    void modify_(int l, int r, int L, int R, int root, const long long &val)
    {
        pushdown_(root, L, R);
        if (l <= L && R <= r)
        {
            if (td_[root].less >= val)
            {
                td_[root].lazy += val;
                return;
            }
            if (L == R)
            {
                td_[root].x += val;
                if (td_[root].x <= c)
                {
                    td_[root].less = block.r(block.belone(td_[root].x)) - td_[root].x;
                    td_[root].scdx = c / td_[root].x;
                    td_[root].sum = c - td_[root].scdx * td_[root].x;
                }
                else
                {
                    td_[root].less = (1 << 30);
                    td_[root].scdx = 0;
                    td_[root].sum = c;
                }
                return;
            }
            auto mid = (L + R) >> 1;
            if (l <= mid)
                modify_(l, r, L, mid, root << 1, val);
            if (r > mid)
                modify_(l, r, mid + 1, R, root << 1 | 1, val);
            update_(root, L, R);
            return;
        }
        auto mid = (L + R) >> 1;
        if (l <= mid)
            modify_(l, r, L, mid, root << 1, val);
        if (r > mid)
            modify_(l, r, mid + 1, R, root << 1 | 1, val);
        update_(root, L, R);
    }

    long long query_(int l, int r, int L, int R, int root)
    {
        pushdown_(root, L, R);
        if (l <= L && R <= r)
        {
            return td_[root].sum;
        }
        auto mid = (L + R) >> 1;
        if (r <= mid)
            return query_(l, r, L, mid, root << 1);
        else if (l > mid)
            return query_(l, r, mid + 1, R, root << 1 | 1);
        else
            return query_(l, mid, L, mid, root << 1) + query_(mid + 1, r, mid + 1, R, root << 1 | 1);
    }

    segmentTree(int N) : N_(N), block(c)
    {
        td_.resize(4 * (N + 5));
    }

    void build(int n, int a[])
    {
        n_ = n;
        build_(1, n_, 1, a);
    }

    void modify(int l, int r, const long long &val)
    {
        modify_(l, r, 1, n_, 1, val);
    }

    long long query(int l, int r)
    {
        return query_(l, r, 1, n_, 1);
    }
};

int main(int argc, char const *argv[])
{
    auto s = chino::divBlock(100);

    auto a = vec_t_create<int, MAXN>(0);
    int op,l,r,x;
    read(n, m, c);
    segmentTree seg(n);
    vread(a.data() + 1, a.data() + n + 1);

    seg.build(n, a.data());
    
    for (int i = 0; i < m; ++i)
    {
        read(op,l,r);
        if (op == 1)
        {
            read(x);
            seg.modify(l, r, x);
        }
        else
        {
           println(seg.query(l, r));
        }
    }
    return 0;
}