A. Battle for Wosneth (Hdu 6838)
题目大意
初始(Alice)有无限血，(Bob)有(m)滴血。(Alice)有(p\%)命中(Bob)，并使(Bob)减少一滴血，自身回复一滴血。(Bob)有(q\%)概率命中(Alice)，并使(Alice)减少一滴血，但自身血不变。问当(Bob)血量减少为(0)时，(Alice)的期望血量变化值是多少。结果对(998244353)取模。
解题思路
当(Bob)血量大于(1)时，设(Alice)命中一次(Bob)，自身血量变化的期望值为(x),则（此处(p,q)为小数）
解得
所以Bob从(m)滴血扣到(1)滴血时，Alice的血量变化期望值为
当(Bob)剩下一滴血时，由于如果(Alice)命中他，则Bob不会反击，这是与上方的区别所在，设(Alice)命中Bob，自身血量变化值为(y)，则
解得
所以最终答案
这可以理解为先假设(m)轮，(Bob)都会反击，造成变化期望值为((1 - dfrac{q}{p}) imes m)，再减去最后一次(Bob)实际反击的变化(扣血)期望(-dfrac{p}{1 - (1 - p)} imes q = -q)。
即为
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mo = 998244353;
LL qpower(LL a, LL b)
{
LL qwq = 1;
while (b)
{
if (b & 1)
qwq = qwq * a % mo;
b >>= 1;
a = a * a % mo;
}
return qwq;
}
LL inv(LL x)
{
return qpower(x, mo - 2);
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int kase;
cin >> kase;
for (int ii = 1; ii <= kase; ii++)
{
LL m, q, p;
cin >> m >> p >> q;
p = p * inv(100) % mo;
q = q * inv(100) % mo;
LL ans = ((1 - q * inv(p) % mo + mo) % mo * m % mo + q) % mo;
cout << ans << endl;
}
return 0;
}
B. Binary Addition (Hdu 6839)
题目大意
给你一串无限长的(01)串(S、T)，其中第(n+1)位及以后都是(0)。现你有两种操作作用于(S)串：
- 将某一位与(1)异或
- 将其视为一个数，对它加一。其中最低位在最左边
求最小的操作次数，使得(S)串变成(T)串。
解题思路
这种看似麻烦的题要去想想特别之处。
可以证明猜测操作二要执行则仅可能执行一次。
操作二有什么用？
如果第一位是(0)，操作二与操作一没区别。
如果第一位是(1)，操作二就能够将前面一连串的(1)变成(0)，在这之后的(0)变成(1)
如果我们会执行两次操作二，由于执行了第一次操作二，前面的数变成了(0)，我们要重新变成(1)，才能再执行操作二。而这最终的结果也只是把某一位变成(1)，而这一结局采用操作一可以一步到位。
所以我们就得到了个重要性质：操作二只能执行一次或者不执行
所以，我们就枚举操作二的执行效果，即枚举(i)，把前(i)个数变成(1)，并把第(i+1)个数变成(0)，然后执行一次操作二，剩下的全部执行操作一即可。
设(num_0[i])表示(S)串的前(i)个数中(0)的个数，(num_1[i])表示(T)串的前(i)个数中(1)的个数，(cnt[i])表示(S)和(T)串的([i..n])中不同的数的个数。
则此时的次数就为(num_0[i] + (s[i+1] == 1) + 1 + num_1[i] + (t[i+1] == 0) + cnt[i+2])
对所有(i)以及(cnt[1])取最小值即是答案。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x)
{
int s = 0, c = getchar();
x = 0;
while (isspace(c))
c = getchar();
if (c == 45)
s = 1, c = getchar();
while (isdigit(c))
x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s)
x = -x;
}
template <typename T>
void write(T x, char c = ' ')
{
int b[40], l = 0;
if (x < 0)
putchar(45), x = -x;
while (x > 0)
b[l++] = x % 10, x /= 10;
if (!l)
putchar(48);
while (l)
putchar(b[--l] | 48);
putchar(c);
}
const int N = 1e5 + 8;
char s[N], t[N];
int n;
int cnt[N];
int num0[N];
int num1[N];
int qwq(int pos)
{
return num0[pos] + (s[pos + 1] == 1) + 1 + num1[pos] + (t[pos + 1] == 0) + cnt[pos + 2];
}
int main(void)
{
int kase;
read(kase);
for (int ii = 1; ii <= kase; ii++)
{
read(n);
scanf("%s", s + 1);
scanf("%s", t + 1);
num0[0] = num1[0] = 0;
for (int i = 1; i <= n; ++i)
{
s[i] -= '0';
t[i] -= '0';
num0[i] = num0[i - 1] + (s[i] == 0);
num1[i] = num1[i - 1] + (t[i] == 1);
}
cnt[n + 1] = 0;
cnt[n + 2] = 0;
bool sign = false;
int cur = n;
for (int i = n; i >= 1; --i)
{
cnt[i] = cnt[i + 1] + (s[i] ^ t[i]);
}
int ans = cnt[1];
for (int i = 1; i <= n; ++i)
{
ans = min(ans, qwq(i));
}
write(ans, '
');
}
return 0;
}
C. Range k-th Maximum Query (Hdu 6840)
题目大意
给定一个(n)个数的序列，以及正整数(k,l)，要求对它重新排序，使得所有长度为(l)的子区间的第(k)大的数和和最大和最小。求最大值和最小值。
解题思路
我们将数列从大到小排列。前(k-1)大的数不会对答案有贡献。
要让和最大，我们期望大的数对答案的贡献尽可能多。
于是我们可以构造这样的序列，它是由若干个长度为(l)的区间构成。
每个这样的区间，前(l - k)个位置标记为红，后(k)个位置标记为蓝。
我们将这个排好序的序列，从左到右，按顺序填充蓝的位置，放完蓝的，然后再从右到左，按顺序填充红的位置。
最后一个长度不足(l)的区间（如果有的话），前(l - k)个位置标记为红，后(k)个位置标记为蓝（如果有的话）。
这样就是最大值的构造。
最小值，将数列从小到大排列，前(k)大的数也就是说前(l - k + 1)小的数，再按照上面构造就可以了。
既然构造出来了，答案自然也就能求出来了。
最大值的情况，设(d = lfloor dfrac{n}{l} floor ， r = n \% l)
排好序的数列里，(k 到 d * k - 1)的数都对答案有(1)次的贡献，其中位置是(k)的倍数的还有额外的((l - k))次的贡献。
最后第(d * k)位的贡献次数跟(r)有关
如果(r > (l - k))，则第(d * k + 1)位到第(d * k + r - (l - k))的数对答案也有(1)次的贡献。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x)
{
int s = 0, c = getchar();
x = 0;
while (isspace(c))
c = getchar();
if (c == 45)
s = 1, c = getchar();
while (isdigit(c))
x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s)
x = -x;
}
template <typename T>
void write(T x, char c = ' ')
{
int b[40], l = 0;
if (x < 0)
putchar(45), x = -x;
while (x > 0)
b[l++] = x % 10, x /= 10;
if (!l)
putchar(48);
while (l)
putchar(b[--l] | 48);
putchar(c);
}
const int N = 1e5 + 8;
int n, k, l, d, r;
LL a[N];
LL solve(LL a[], int k)
{
LL ans = 0;
for (int i = k; i < d * k; ++i)
{
ans += a[i] * (1 + (l - k) * (i % k == 0));
}
ans += a[d * k] * min(r + 1, l - k + 1);
if (r > l - k)
{
for (int i = d * k + 1, yu = r - l + k; yu; ++i, --yu)
{
ans += a[i];
}
}
return ans;
}
int main(void)
{
int kase;
read(kase);
for (int ii = 1; ii <= kase; ii++)
{
read(n);
read(l);
read(k);
for (int i = 1; i <= n; ++i)
{
read(a[i]);
}
sort(a + 1, a + 1 + n, greater<int>());
d = n / l;
r = n % l;
LL ans1 = solve(a, k);
sort(a + 1, a + 1 + n);
k = l - k + 1;
LL ans2 = solve(a, k);
printf("%lld %lld
", ans1, ans2);
}
return 0;
}
D. Link Cut Tree (Hdu 6841)
题目大意
qwq
解题思路
qwq
神奇的代码
qwq
E. Battle for Wosneth2 (Hdu 6842)
题目大意
初始(Alice)有(n)滴血，(Bob)有(m)滴血。(Alice)有(p\%)命中(Bob)，并使(Bob)减少一滴血，但自身血不变；(Bob)有(q\%)概率命中(Alice)，并使(Alice)减少一滴血，但自身血不变。当一方血量减为(0)时，对方获胜。问(Alice)获胜的概率。答案对(998244353)取模。
解题思路
我们抽象成一个二维平面图，左下角((0,0))，初始位于((n,m))，然后有三个移动方向，问移动到((r,0))的概率是多少((r)是任意一个不大于(n)的数)。
当前位置为((i,j))
-
移动到((i-1, j-1))的概率(a = dfrac{pq}{1 - (1 - p)(1 - q)})
-
移动到((i, j - 1))的概率(b = dfrac{p(1-q)}{1 - (1 - p)(1 - q)})
-
移动到((i - 1, j))的概率(c = dfrac{q(1-p)}{1 - (1 - p)(1 - q)})
值得注意的是，从((i,1))移动到((i,0))的概率是(d = dfrac{p}{1 - (1 - p)(1 - q)})
所以我们先计算移动到((r,1))的概率，最后再计算移动到((r,0))的概率。
这里有两个自由变量。
如果我们假设移动到((r,1))，或者说，水平方向进行了(i = n - r)次移动，还要假设，我们进行了(x)次情况一的移动，则情况二进行了(m - 1 -x)次，情况三进行了(i - x)次移动。
则移动到(m = 1)的概率为
很显然这式子整不动。通常处理方法就是交换求和顺序。我们从实际意义来说明。
我们先假设进行了(x)次情况一的移动，则情况二进行了(m - 1 -x)次，情况三进行了(i)次移动，其中(0 leq i leq n - 1 - x)。
则移动到(m=1)的概率为
而后面这一项可以事先预处理一个前缀和(S(r) = sumlimits_{i = 0}^{r} C_{m - 1 + i}^{i}c^{i})
这样，最终的答案就是
值得注意的是在计算(b^{m - 1 - x})时，万万不可算出(b^{m-1})然后除以(b)除以(b)(取模意义上)。
因为当(b=0)的时候，这样算的话(0^{0} = 0)。
而实际上我们应该认为(0^{0} = 1)，也就是说应当采用快速幂计算 (虽然会多个log)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x)
{
int s = 0, c = getchar();
x = 0;
while (isspace(c))
c = getchar();
if (c == 45)
s = 1, c = getchar();
while (isdigit(c))
x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s)
x = -x;
}
template <typename T>
void write(T x, char c = ' ')
{
int b[40], l = 0;
if (x < 0)
putchar(45), x = -x;
while (x > 0)
b[l++] = x % 10, x /= 10;
if (!l)
putchar(48);
while (l)
putchar(b[--l] | 48);
putchar(c);
}
const LL mo = 998244353;
const int N = 2e5 + 8;
int n, m;
LL jie[N], invjie[N];
LL sum[N];
LL p, q;
LL a, b, c, d;
LL inv100 = 828542813;
LL ans;
LL qpower(LL a, LL b)
{
LL qwq = 1;
while (b)
{
if (b & 1)
qwq = qwq * a % mo;
b >>= 1;
a = a * a % mo;
}
return qwq;
}
LL inv(LL x)
{
return qpower(x, mo - 2);
}
LL C(int n, int m)
{
if (n < m)
return 0;
return jie[n] * invjie[m] % mo * invjie[n - m] % mo;
}
int main(void)
{
int kase;
read(kase);
jie[0] = invjie[0] = 1;
for (int i = 1; i < N; ++i)
{
jie[i] = jie[i - 1] * i % mo;
invjie[i] = inv(jie[i]);
}
for (int ii = 1; ii <= kase; ii++)
{
read(n);
read(m);
read(p);
read(q);
p = p * inv100 % mo;
q = q * inv100 % mo;
d = inv((1 - (1 - p) * (1 - q) % mo + mo) % mo);
a = p * q % mo * d % mo;
b = p * ((1 - q + mo) % mo) % mo * d % mo;
c = q * ((1 - p + mo) % mo) % mo * d % mo;
sum[0] = 1;
LL tmp = c;
for (int i = 1; i < n; ++i)
{
sum[i] = (sum[i - 1] + tmp * C(m - 1 + i, i) % mo) % mo;
tmp = tmp * c % mo;
}
ans = 0;
LL qaq = 1;
// LL qbq = qpower(b, m - 1);
// LL invb = inv(b);
int up = min(m - 1, n - 1);
for (int i = 0; i <= up; ++i)
{
ans = (ans + qaq * qpower(b, m - i - 1) % mo * C(m - 1, i) % mo * sum[n - i - 1] % mo) % mo;
// ans = (ans + qaq * qbq % mo * C(m - 1, i) % mo * sum[n - i - 1] % mo) % mo; // 0^0 = 1
qaq = qaq * a % mo;
// qbq = qbq * invb % mo;
}
ans = ans * p % mo * d % mo;
write(ans, '
');
}
return 0;
}
F. Query on the Tree (Hdu 6843)
题目大意
qwq
解题思路
qwq
神奇的代码
qwq