AtCoder Beginner Contest 310
感觉F又双叒叕写复杂了
A - Order Something Else (abc310 A)
题目大意
点杯咖啡，要\(p\)元，但可以用一个优惠券，使得咖啡只要 \(q\)元，但你需要额外购买\(n\)个商品中（价格为\(a_i\)）的一个。
问点杯咖啡的最小价格。
解题思路
考虑直接买还是使用优惠券，使用优惠券的话就选\(n\)个商品中价格最小的。
两种情况取最小即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, p, q;
cin >> n >> p >> q;
int a = 1e9 + 7;
while(n--){
int x;
cin >> x;
a = min(a, x);
}
cout << min(p, q + a) << '\n';
return 0;
}
B - Strictly Superior (abc310 B)
题目大意
给定\(n\)个商品的价格 \(p_i\)，以及每个商品的 \(k_i\)种功能。
问是否可以找到两个商品\(i, j\)，满足：
- \(p_i \geq p_j\)
- \(i\)商品的 功能\(j\)商品 都有
- \(p_i > p_j\) 或者 \(j\)商品有额外的功能， \(i\)商品没有。
解题思路
范围都不大，直接\(O(n^2)\)枚举商品，然后比较那三个条件是否满足即可。
对于条件二，可以再花 \(O(m)\)的时间比较下功能是否覆盖，也可以用 bitset，直接作与运算。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<bitset<100>> f(n);
vector<int> p(n);
for(int i = 0; i < n; ++ i){
cin >> p[i];
int k;
cin >> k;
while(k--){
int x;
cin >> x;
-- x;
f[i][x] = 1;
}
}
bool ok = false;
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j){
if (i == j)
continue;
if (p[i] < p[j])
continue;
if ((f[i] & f[j]) != f[i])
continue;
if (p[i] > p[j] || f[i] != f[j])
ok = true;
}
if (ok)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
C - Reversible (abc310 C)
题目大意
给定\(n\)个字符串，问字符串的种类数量。
两个字符串\(s, t\)是相同种类的 ，当且仅当\(s == t\)或 \(rev(s) == t\)。其中 \(rev(s)\)表示字符串 \(s\)的反串。
解题思路
去重可以用set。
对于一个字符串\(s\)，可以在 set中看看能否找到\(s\)或 \(rev(s)\)，不能找到说明是一个新的种类，放进 set即可。
答案就是最后的set的元素数量。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
unordered_set<string> qwq;
while(n--){
string s;
cin >> s;
auto t = s;
reverse(t.begin(), t.end());
if (qwq.empty() || (qwq.find(s) == qwq.end() && qwq.find(t) == qwq.end())){
qwq.insert(s);
}
}
cout << qwq.size() << '\n';
return 0;
}
D - Peaceful Teams (abc310 D)
题目大意
\(n\)个人，分成 \(t\)队，但有 \(m\)条限制，指明了 \(x_i\)和 \(y_i\)不能同一队。
问不违反限制的分队方案数。
解题思路
数据范围很小啊，只有\(10\)，然后答案又不用取模，感觉直接搜也能过，最后也过了（。
搜索就依次考虑每个人，是新成一队，还是加入到已有队伍里，每次加入则检查下是否违反。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, t, m;
cin >> n >> t >> m;
vector<vector<int>> rule(n);
for(int i = 0; i < m; ++ i){
int x, y;
cin >> x >> y;
-- x, -- y;
rule[x].push_back(y);
rule[y].push_back(x);
}
LL ans = 0;
vector<int> a(n, -1);
auto ok = [&](int pos, int zu){
for(auto &i : rule[pos]){
if (a[i] == zu)
return false;
}
return true;
};
function<void(int, int)> dfs = [&](int zu, int pos){
if (zu > t)
return;
if (pos == n){
if (zu == t)
ans ++;
return;
}
for(int i = 0; i < zu; ++ i){
if (ok(pos, i)){
a[pos] = i;
dfs(zu, pos + 1);
a[pos] = -1;
}
}
a[pos] = zu;
dfs(zu + 1, pos + 1);
a[pos] = -1;
};
dfs(0, 0);
cout << ans << '\n';
return 0;
}
E - NAND repeatedly (abc310 E)
题目大意
给定一个长度为\(n\)的\(01\)数组 \(a\)，定义函数 \(f(l,r) = a_l \barwedge a_{l+1} \barwedge \cdots \barwedge a_{r}\)，其中\(\barwedge\)是非与运算，即与运算的非。
求 \(\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)\)
解题思路
虽然题意给了\(f(l,r)\)的递归定义式有点吓人，但展开后其实就是上述的表达式。
直接计算是 \(O(n^2)\)， 思考下这\(O(n^2)\)个结果可以发现有压缩的余地。
考虑什么时候 \(f(l,r) == 1\)，可以发现是\(f(l, r - 1) == 0\)或者\(a_r == 0\)，即它只取决于上一位情况和当前位。
我们在迭代计算，即枚举右端点\(r\)时，考虑其对答案的贡献是多少，那就是考虑有多少个左端点\(l\)满足 \(f(l,r) == 1\)。因为每一个\(f\)为\(1\)的左端点都对答案有 \(1\)的贡献。
思考可以发现其数量可以从右端点为\(r-1\)的情况快速得到。
我们设 \(dp[i][0/1]\)表示前 \(i\)个数，满足 \(f(l, i) == 0\)或 \(f(l, i) == 1\)的数量，
根据\(a_i\)的取值和非与的运算结果，可以得到从 \(dp[i-1][0/1]\)转移过来的式子。
假设 \(a_i = 0\)，则
- \(dp[i][0] = 1\)
- \(dp[i][1] = dp[i-1][0] + dp[i-1][1]\)
假设 \(a_i = 1\)，则
- \(dp[i][0] = dp[i-1][1]\)
- \(dp[i][1] = dp[i-1][0] + 1\)，注意这个\(1\)是 \(f(i,i)\)的情况。
那么以\(i\)为右端点的所有区间的贡献就是\(dp[i][1] \times 1 + dp[i][0] \times 0\)。
累计求和就是答案了。
初始情况，貌似就全\(0\)就好了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
string s;
cin >> n >> s;
array<LL, 2> dp{0, 0};
LL sum = 0;
for(auto &i : s){
array<LL, 2> dp2{0, 0};
if (i == '0'){
dp2[0] = 1;
dp2[1] = dp[0] + dp[1];
}else{
dp2[0] = dp[1];
dp2[1] = dp[0] + 1;
}
sum += dp2[1];
dp.swap(dp2);
}
cout << sum << '\n';
return 0;
}
F - Make 10 Again (abc310 F)
题目大意
给定\(n\)个骰子，每个骰子等概率掷出 \(1 \sim a_i\)中的一个数。
问一个局面出现的概率，在这个局面中，可以选择一些骰子的结果，其和为 \(10\)。
解题思路
算概率考虑两个方向，一种是根据定义来算，即一个概率的结果是若干个前序情况概率的累加。
因为本题的所有局面的出现概率都是相同的（所有的\(\frac{1}{a_i}\)累乘），所以还可以是\(\frac{\text{符合条件的局面数}}{\text{全局面数}}\)（其实这个公式是定义式的通分的结果）。而全局面数就是所有的\(a_i\)累乘。因此我们考虑如何计算分子。
但是状态定义非常困难，因为它统计的是这个局面可以选出和为\(10\)，而不是局面选出和为 \(10\)的方案之类的，常规的一些状态比如 \(dp[i][j]\)表示前 \(i\)个骰子掷出后，选择一些骰子，其和为 \(j\)的方案数（或概率），事实上都会算重。
样例给出的掷出情况 1 3 2 7，这个局面会被算多次，在考虑 1 2 7时考虑了一次这个局面， 3 7时也考虑了一次这个局面，因此这类的状态设计都是不行的。
然后考虑将这个状态\(j\)再细分一下，因为和为 \(j\)的情况数很多，上述状态我们把这些状态都揉在一起了，所以我们可以把这些和\(j\)的 所有情况（比如\(10 \times 1\)，或者 \(8 \times 1 + 1 \times 2\)等等）细分出来。
即设 \(dp[i][c_1][c_2][c_3][c_4][c_5][c_6][c_7][c_8][c_9][c_{10}]\)表示前 \(i\)个骰子，其中掷出结果为 \(1,2,3,4,5,6,7,8,9,10\)的骰子数有 \(c_1,c_2,c_3,c_4,c_5,c_6,c_7,c_8,c_9,c_{10}\)的情况数。虽然有\(11\)维，但后续状态比如 \(c_6,c_7\)，我们可以让它们的取值只有 \(0 \sim 1\)，因为再大的取值对我们来讲是没用的了。
最后我们把可以选出和为\(10\)的 \(c_1 \sim c_{10}\)的情况数加起来，就是符合条件的情况数，再除以总情况数，就是答案。
而判断我有\(c_1\)个 \(1\)， \(c_2\)个 \(2\)， \(\cdots\)， \(c_{10}\)个 \(10\)，能否选出一些数和为 \(10\)，就是一个简单的背包\(dp[i][j]\) 表示前\(i\)个数能否组成和为 \(j\)。
分析下它的复杂度，状态数有 \(100 \times 11 \times 6 \times 4 \times 3 \times 3 \times 2 \times 2 \times 2 \times 2 \times 2 = 7e6\)，每个情况要判断是否能选一些数和为 \(10\)的复杂度 \((11+6+4+3+3+2+2+2+2+2) \times 10 = 370\)，总的复杂度有 \(2e9\)，非常的危险。
但我们考虑逆向情况（其实当时以为正向状态也有重，就直接考虑逆向了，写题解时发现貌似没有重，但分析了下复杂度会炸）即统计不能选一些数和为10的情况数。此时我们可以发现状态数会比较少。首先\(dp\)式子少了最后一维 \(c_{10}\)，然后一些维度 比如\(c_1\)的取值范围只有 \(0 \sim 9\)而不是刚才的 \(0 \sim 10\)（因为取 \(10\)的话就一定能选\(10\)个 \(1\)和为 \(10\)，其情况数一定是 \(0\)），同理\(c_2\)和 \(c_5\)也是。
这样状态数就有 \(100 \times 10 \times 5 \times 4 \times 3 \times 2 \times 2 \times 2 \times 2 \times 2 = 2e6\)，判断合法的复杂度是 \((10+5+4+3+2+2+2+2+2) \times 10 = 320\)，总的复杂度是 \(6e8\)，是可以通过的了。
转移就考虑当前骰子的取值（从\(1 \sim \min(9, a_i)\)），更大的取值（除了 \(10\)）对我们所设的状态没有影响，不过记得加上方案数。
当然\(10\)维 \(dp\)非常不好写，我们可以进行状态压缩，但由于不同维度的取值范围不一样，不能单纯的二进制压缩之类的，但其实如果了解进制转换的话，会发现进制数的每个维度数量不一定要相同，即可以自定义一个进制，最低位有\(10\)种取值，即逢 \(10\)进 \(1\) ，次低位有\(5\)种 取值，逢\(5\)进 \(1\)。依次类推，正向转换和逆向转换就跟转十进制和十进制转换成其他进制一样的公式就可以了。
初始情况就是\(dp[0][0] = 1\)
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
long long qpower(long long a, long long b){
long long qwq = 1;
while(b){
if (b & 1)
qwq = qwq * a % mo;
a = a * a % mo;
b >>= 1;
}
return qwq;
}
long long inv(long long x){
return qpower(x, mo - 2);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(auto &i : a)
cin >> i;
constexpr int size = 10 * 5 * 4 * 3 * 2 * 2 * 2 * 2 * 2;
array<int, 9> ji{10, 5, 4, 3, 2, 2, 2, 2, 2};
array<int, 9> upp{9, 4, 3, 2, 1, 1, 1, 1, 1};
array<LL, size> dp{1};
LL tot = 1;
auto craft = [&](int x){
array<int, 9> cnt;
for(int i = 0; i < 9; ++ i){
cnt[i] = x % ji[i];
x /= ji[i];
}
return cnt;
};
auto invcraft = [&](const array<int, 9>& cnt){
int sum = 0;
for(int i = 8; i >= 0; -- i){
sum = sum * ji[i] + cnt[i];
}
return sum;
};
auto do_ok = [](const array<int, 9>& cnt){
array<int, 11> ok{1};
for(int i = 0; i < 9; ++ i){
array<int, 11> ok2{};
for(int j = 0; j <= cnt[i]; ++ j){
for(int k = 0; k <= 10; ++ k){
if (k + (i + 1) * j <= 10)
ok2[k + (i + 1) * j] |= ok[k];
}
}
ok2.swap(ok);
}
return !ok[10];
};
auto fit = [&](int x, int y){
-- y;
auto cnt = craft(x);
cnt[y] ++;
if (y == 0 && cnt[y] == 10)
return false;
if (y == 1 && cnt[y] == 5)
return false;
if (y == 4 && cnt[y] == 2)
return false;
return true;
};
auto ins = [&](int x, int y){
-- y;
auto cnt = craft(x);
cnt[y] = min(cnt[y] + 1, upp[y]);
return invcraft(cnt);
};
for(auto &i : a){
array<LL, size> dp2{};
int up = min(i, 9);
int left = max(0, i - 10);
for(int i = 0; i < size; ++ i){
for(int j = 1; j <= up; ++ j){
if (fit(i, j)){
int nxt = ins(i, j);
dp2[nxt] += dp[i];
if (dp2[nxt] >= mo)
dp2[nxt] -= mo;
}
}
dp2[i] += dp[i] * left % mo;
if (dp2[i] >= mo)
dp2[i] -= mo;
}
dp.swap(dp2);
tot = tot * i % mo;
}
LL ans = 0;
auto ok = [&](int i){
return do_ok(craft(i));
};
int tmp = 0;
for(int i = 0; i < size; ++ i){
if (ok(i)){
if (dp[i]){
++ tmp;
}
ans += dp[i];
if (ans >= mo)
ans -= mo;
}
}
ans = ((tot - ans) % mo + mo) % mo * inv(tot) % mo;
cout << ans << '\n';
return 0;
}
其实感觉写的非常复杂，尤其是那个进制转换，建议看看jls的是如何在4分钟写完这题的qwq。
G - Takahashi And Pass-The-Ball Game (abc310 G)
题目大意
有\(n\)个高桥，每个高桥有\(b_i\)个球， 每一轮，第\(i\)个高桥会把所有球传给第\(a_i\)个高桥。
等概率取值 \(x \in [1, k]\) ，然后进行\(k\)轮传球。注意这\(n\)个高桥的球是同时传递的。
传球结束后，问每个高桥手中的球的期望数。
解题思路
<++>
神奇的代码
Ex - Negative Cost (abc310 Ex)
题目大意
<++>
解题思路
<++>
神奇的代码