Znzryb's Blog
0%

Posted on Edited on

题目大意

题目大意

定义一种自然数下的二元运算「月球异或」（记作 ⊛\circledast）：将两个自然数转换为三进制后，对每一位分别相加并对 33 取模（即三进制下的不进位加法）。例如 8(10)⊛16(10)=022(3)⊛121(3)=110(3)=12(10)8_{(10)} \circledast 16_{(10)} = 022_{(3)} \circledast 121_{(3)} = 110_{(3)} = 12_{(10)}。

现给定一个长度为 NN 的自然数序列 v1,v2,…,vNv_1, v_2, \dots, v_N。你可以对序列中的任意元素 viv_i 执行以下两种操作任意次（包含零次）：

  1. vi←vi⊛viv_i \leftarrow v_i \circledast v_i

  2. vi←0v_i \leftarrow 0

有 QQ 次独立的询问，每次询问给出一个自然数 ss。对于每次询问，你需要判断能否通过若干次上述操作，使得序列全部元素的「月球异或」和等于 ss（即 v1⊛v2⊛⋯⊛vN=sv_1 \circledast v_2 \circledast \dots \circledast v_N = s）。

数据范围

测试组数：1≤T≤1000001 \le T \le 100000
序列长度与询问次数：1≤N,Q≤1061 \le N, Q \le 10^6，且所有测试组的 ∑N,∑Q≤2×106\sum N, \sum Q \le 2 \times 10^6
序列元素与询问值：0≤vi,si≤10180 \le v_i, s_i \le 10^{18}

样例数据

输入：

1
2
3
4
5
6
7
8
9
10
3
1 4
1
0 1 2 3
3 5
0 5 10
4 5 6 7 8
3 6
8 16 32
12 17 57 41 4 44

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Yes
Yes
Yes
No
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
Yes

样例解释

以第一组样例为例：
此时 N=1,Q=4N=1, Q=4，序列只包含一个元素 v1=1v_1 = 1。
四次询问的值分别为 s=0,1,2,3s = 0, 1, 2, 3。

对于 v1=1v_1 = 1（三进制表示为 01(3)01_{(3)}），它可能变化得到的状态有：

  • 执行零次操作：得到原来的值 11。

  • 执行一次第一种操作：1⊛1=1(3)+1(3)(mod3)=2(3)=21 \circledast 1 = 1_{(3)} + 1_{(3)} \pmod 3 = 2_{(3)} = 2。

  • 执行一次第二种操作：直接变为 00。

因为操作本质上是对三进制的每一位独立进行乘法并对 33 取模，或者直接置零，所以原本为 00 的高位（如 313^1 对应的位）永远不可能变成非 00 值。
目标 s=3s=3 在三进制下表示为 10(3)10_{(3)}，其第 11 位（对应数值 33）的值为 11，而 v1v_1 无论怎么操作在第 11 位上永远是 00，因此永远无法得到 33。
最终对于 0,1,2,30, 1, 2, 3 的询问，前三个可以得到，后一个无法得到，分别输出 Yes、Yes、Yes、No。

思路讲解

其实，不难发现，我们其实就是要看一个数字能不能用我们的这个三进制异或线性基表示出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137


// 模 p 意义下的线性基（用于处理 p 进制下的无进位加法，本题中 p = 3）
class modn_XOR_base {  
private:  
    vector<ll> base;                // 记录主元位置对应的原始数值
    vector<vector<ll>> mat;         // mat[i] 存储最高位为 i 且系数已被标准化为 1 的基向量
    ll mod;                         // 模数 p（要求 p 为质数，才能使用费马小定理求逆元）


    // 快速幂计算 (a^b % mod)
    ll power(ll a, ll b) const {
        ll res = 1;
        a %= mod;
        while (b > 0) {
            if (b & 1) res = (res * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return res;
    }

    // 费马小定理求逆元（因为 mod 为质数）
    ll modInverse(ll n) const {
        return power(n, mod - 2);
    }

public:  
    // 构造函数，初始化模数和基数组的大小
    // 64 位数组足以容纳 10^18 在三进制下的最大位数（约为 38 位）
    modn_XOR_base(ll Mod) {  
        mod = Mod; 
        base.assign(64, 0);                      
        mat.assign(64, vector<ll>(64, 0));       
    }  

    // 插入元素 x 到线性基中
    // 如果 x 能被已有的线性基表出，返回 false；否则将其作为新的基插入并返回 true
    bool insert(ll x) {
        ll orig_x = x;
        vector<ll> v(64, 0);
        
        // 将 x 转换为 mod 进制的向量表示（从低位到高位分离）
        for (int i = 0; i < 64; ++i) {
            v[i] = x % mod;
            x /= mod;
        }

        // 从高位到低位进行高斯消元操作
        for (int i = 63; i >= 0; --i) {
            if (v[i] == 0) continue; // 当前位为 0，无需处理

            // 如果当前位没有主元（即线性基在此位为空）
            if (base[i] == 0) {
                ll inv = modInverse(v[i]); // 求当前位系数的逆元
                // 将整个向量乘以逆元，使得最高位（第 i 位）的系数标准化为 1
                for (int j = 0; j <= i; ++j) {
                    mat[i][j] = (v[j] * inv) % mod;
                }
                base[i] = orig_x; // 记录在该位有主元被插入
                return true;      // 成功插入新的基向量，向量空间维数 +1
            }

            // 如果当前位已经有主元了，利用已有的基向量 mat[i] 消去当前位 v[i]
            ll k = v[i]; // 因为 mat[i][i] 已经被标准化为 1，所以要消去 v[i]，需减去 mat[i] 的 k 倍
            for (int j = 0; j <= i; ++j) {
                v[j] = (v[j] - k * mat[i][j]) % mod;
                if (v[j] < 0) v[j] += mod; // 保证结果始终在 [0, mod-1] 的合法范围内
            }
        }
        // 如果循环结束，说明整个向量被彻底消成了 0，即它可以由已有基表出
        return false; 
    }  

    
    // 查询元素 x 能否被当前的线性基表出
    bool query(ll x) const {
        vector<ll> v(64, 0);
        
        // 同样将待查询的 x 转换为 mod 进制的向量表示
        for (int i = 0; i < 64; ++i) {
            v[i] = x % mod;
            x /= mod;
        }

        // 从高位到低位依次尝试被线性基消元
        for (int i = 63; i >= 0; --i) {
            if (v[i] == 0) continue;
            
            // 如果 x 在某一位不为 0，但线性基该位为空，说明无法被表出，直接返回 false
            if (base[i] == 0) return false;

            // 利用线性基消去当前位
            ll k = v[i];
            for (int j = 0; j <= i; ++j) {
                v[j] = (v[j] - k * mat[i][j]) % mod;
                if (v[j] < 0) v[j] += mod;
            }
        }
        
        // 如果所有非零位都被成功消去（最终变为全 0 向量），说明 x 能被完美表出
        return true;
    }  
};

int main() {
    
    // 优化标准 I/O 速度，避免因为读写大规模数据超时
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    

    int T;
    cin >> T;
    while (T--) {
        // 针对题目“月球异或”：三进制下的每一位独立相加后模 3，因此实例化模数为 3 的线性基
        modn_XOR_base base(3);
        ll N, Q;
        cin >> N >> Q;
        
        // 读入序列 v 并将每一个元素构建到线性基中
        // 注意：线性基可以允许重复操作操作对象 v_i <- v_i ⊛ v_i，本质就是该向量的数乘操作
        for(int i = 0; i < N; ++i){
            ll x;
            cin >> x;
            base.insert(x);
        }
        
        // 读入每个询问的数值 t，利用已求得的线性基判断是否能生成 t
        for(int i = 0; i < Q; ++i){
            ll t;
            cin >> t;
            cout << (base.query(t) ? "Yes\n" : "No\n");
        }
    }
    return 0;
}

AC代码

AC

https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=7820&from=rank

心路历程（WA，TLE，MLE……）

Posted on Edited on

注意 dfs 要记得进行回退操作的时候，所有东西都要回退，包括这个 vis 数组。

image

Posted on Edited on

题目大意

题目描述
有一个大小为 3×33 \times 3 的矩形安全箱。
共有 nn 件物品，第 ii 件物品的大小为 ai×bia_i \times b_i（可以水平放置或旋转 90∘90^{\circ}），价值为 viv_i。
你需要选择若干件物品放入安全箱内，物品必须完全在箱子内部且互相之间不能有重叠部分。
求能够放入安全箱内物品的最大总价值。

输入格式
第一行输入一个整数 TT（1≤T≤100001 \le T \le 10000），表示测试数据的组数。
对于每组数据：
第一行输入一个正整数 nn（1≤n≤1061 \le n \le 10^6），表示物品的数量。
接下来 nn 行，每行输入三个整数 ai,bi,via_i, b_i, v_i（1≤ai,bi≤3,1≤vi≤1081 \le a_i, b_i \le 3, 1 \le v_i \le 10^8），分别代表第 ii 件物品的长、宽和价值。
保证所有测试组的 nn 之和不超过 10610^6。

输出格式
对于每组数据，输出一行一个整数，表示最大的总价值。

样例输入

1
2
3
4
5
6
7
8
9
10
2
5
2 3 20
1 3 5
1 2 4
1 1 4
1 3 6
2
1 1 13141314
3 3 6947311

样例输出

1
2
28
13141314

样例解释第一组数据：最优策略是放入第 11 件物品（大小 2×32 \times 3，价值 2020）、第 33 件物品（大小 1×21 \times 2，价值 44）以及第 44 件物品（大小 1×11 \times 1，价值 44）。第 11 件物品占用 2×32 \times 3 的空间后，安全箱还会剩余 1×31 \times 3 的空白区域，恰好可以无重叠地容纳第 33 件和第 44 件物品。总价值为 20+4+4=2820 + 4 + 4 = 28。
第二组数据：虽然第 22 件物品（大小 3×33 \times 3，价值 69473116947311）能正好填满整个安全箱，但只放入第 11 件物品（大小 1×11 \times 1，价值 1314131413141314）可以获得更高的总价值。因此最优选择是仅放置第 11 件物品，最大总价值为 1314131413141314。

思路讲解

不难发现，一共只有 21 种有效状态。

开个玩笑，这个是提前用 dfs 跑出来的，直接打表，跳过这个预处理。

image

那你都预处理出来所有的这个情况了，做起来就很简单了。

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=13515

心路历程（WA，TLE，MLE……）

常见 dfs 错误及原因

Posted on Edited on

题目大意

image

题目背景与目标
有 nn 张牌从上至下组成的牌堆，每张牌上有一个点数 aia_i。共有 mm 名玩家按 1,2,…,m1, 2, \dots, m 的顺序依次循环摸牌。玩家 kk 作为游戏组织者，在所有人开始摸牌之前，可以进行至多一次切牌操作（即将牌堆从任意位置分为上下两部分，并交换这两部分的位置）。目标是求出玩家 kk 通过合理切牌，最终自己摸到的牌的点数总和的最大值。

输入格式
第一行包含一个整数 TT，表示测试用例的数量。
每组数据包含两行：
第一行输入三个正整数 n,m,kn, m, k，分别代表牌的总数、玩家的总数以及目标玩家的顺位。
第二行输入 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n，自顶向下给出牌堆中每张牌的点数。

输出格式
对于每组数据，输出一行一个整数，表示玩家 kk 可以获得的最大点数和。

样例输入

1
2
3
4
5
2
2 2 1
114514 1919810
3 1 1
1 -3 2

样例输出

1
2
1919810
0

样例解释第一组样例：牌堆共 22 张牌，有 22 名玩家，主角是第 11 名玩家。初始牌堆点数为 114514, 1919810。主角可以通过切牌操作，将上面的第一张牌移到最下方，得到新牌堆 1919810, 114514。开始发牌后，主角作为第 11 名玩家摸走第一张牌，获得最大点数 19198101919810。
第二组样例：牌堆共 33 张牌，只有 11 名玩家，主角是第 11 名玩家。无论主角在开始前如何切牌，因为只有他一个人玩，他都会摸走所有的牌。因此他获得的总点数固定为 1−3+2=01 - 3 + 2 = 0。

思路讲解

其实这道题目的思路说起来也很简单，就是在一个环上跑这个滑动窗口。

这个切牌其实可以看作循环位移操作。

image

然后，需要注意到的就是，无论你怎么切牌，第 k 个玩家所能吃到的牌的数量是不变的（也就是代码中的 cnt_k ）

因此，我们是用 2N 技巧，在这个 2N 上模拟环，进行一个滑动窗口，就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for (ll i = K - 1; i < N; i += M) {
    cnt_k++;
    ans += A[i];
}
for (int i = 0; i < M; ++i) {
    ll lans = 0;
    ll cnt_i = 0;
    queue<ll> q;
    for (ll j = i; j < 2 * N; j += M) {
        lans += A[j];
        q.push(A[j]);
        if (SZ(q) == cnt_k) {
            ans = max(ans, lans);
        }
        if (SZ(q) > cnt_k) {
            lans -= q.front();
            q.pop();
            ans = max(ans, lans);
        }
    }
}

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=8833

心路历程（WA，TLE，MLE……）