A - Broken Keyboard
按照题意模拟即可啦，只需要看连续这一段的字母个数的奇偶性即可。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
string s;
set<char> ans;
inline void solve()
{
ans.clear();
cin >> s;
s.push_back('#');int n = s.size();
int cnt = 1;
for (int i = 0; i < n - 1; ++i)
{
if (s[i + 1] != s[i])
{
if (cnt & 1)
ans.insert(s[i]);
cnt = 1;
}
else
cnt++;
}
for(auto i : ans)
cout << i;
cout << '\n';
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
B - Binary Palindromes
把串分成三类：0 的个数和 1 的个数都是奇数、其中一个是奇数另一个是偶数、两个都是偶数，只有第一类串不能构成回文，我们就需要尽量消除第一类的。
有几种办法可以消除：优先考虑两个第一类串互相交换一个 0 和 1，这样就变成第三类串，这样最后只剩下 0 个或 1 个一类串，这个时候用一个第二类串去和剩下的一类串交换一次即可。这样，所有的一类串就消除完了。
...不过我代码中分类编号有点不一样就是了
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int t1, t2, t3, ans;
inline void solve()
{
ans = 0;
int n;
cin >> n;
t1 = t2 = t3 = 0;
for (int i = 1; i <= n; ++i)
{
string s;
cin >> s;
int _0 = 0, _1 = 0;
for (auto j : s)
(j == '0') ? _0++ : _1++;
if ((_0 & 1) && (_1 & 1))
t3++;
else if ((!(_0 & 1)) && (!(_1 & 1)))
t1++;
else
t2++;
}
ans = t1 + t2 + (t3 / 2) * 2;
if (t2 && (t3 & 1))
ans++;
cout << ans << '\n';
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
C - Minimize The Integer
贪心，从高位往地位，当前这一位是奇数的话就找一个满足位置最靠前的数字最小的偶数，并且该偶数小于该奇数的话就把那个偶数移过来；当前位置是偶数的话同理。之后用一个 vis 记录一下哪些位置被移动过即可。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n;
char s[N];
vector<int> pos[10];
int ans[N];
bool vis[N];
inline void solve()
{
scanf(
n = strlen(s + 1);
mem(vis, 0, n, bool);
for (int i = 0; i < 10; ++i)
pos[i].resize(0);
for (int i = 1; i <= n; ++i)
pos[s[i] - '0'].push_back(i);
for (int i = 0; i < 10; ++i)
reverse(vecall(pos[i]));
int e = 0;
for (int i = 1; i <= n; ++i)
{
if (vis[i])
continue;
if ((s[i] - '0') & 1)
{
int mnpos = inf, num = -1;
for (int j = 0; j < 10; j += 2)
{
if (!pos[j].empty() && mnpos > pos[j].back())
mnpos = pos[j].back(), num = j;
}
if (num != -1 && num < s[i] - '0')
{
ans[++e] = num;
i--;
vis[pos[num].back()] = 1;
}
else
ans[++e] = s[i] - '0';
pos[ans[e]].pop_back();
}
else
{
int mnpos = inf, num = -1;
for (int j = 1; j < 10; j += 2)
{
if (!pos[j].empty() && mnpos > pos[j].back())
mnpos = pos[j].back(), num = j;
}
if (num != -1 && num < s[i] - '0')
ans[++e] = num, vis[pos[num].back()] = 1, i--;
else
ans[++e] = s[i] - '0';
pos[ans[e]].pop_back();
}
printf(
}
cout << '\n';
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
D - Salary Changing
二分，下界显然就是所有的 $l_i$ 的中位数，接下来二分一个答案 $x$，check 的时候贪心：显然每个数能选得越小就越好，这样花的钱总和就越小。按照 $l_i$ 排序，把 $l_i$ 大的那些尽量选做中位数之后的，这样剩下的就全部选 $l_i$，这样就可以保证选出来的总和最小。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n;
ll s, suml;
struct person
{
ll l, r;
bool operator<(const person &rhs) const
{
return l > rhs.l || (l == rhs.l && r > rhs.r);
}
} p[N];
bool f1(ll x)
{
int numr = 0;
ll sum = suml, ss = s;
for (int i = 1; i <= n; ++i)
{
if (p[i].r >= x)
numr++, sum -= p[i].l, ss -= max(p[i].l, x);
if (ss < 0)
return false;
if (numr == (n + 1) / 2)
{
break;
}
}
if (numr < (n + 1) / 2 || ss < sum)
return false;
else
return true;
}
inline void solve()
{
suml = 0;
scanf(
for (int i = 1; i <= n; ++i)
scanf(
sort(p + 1, p + n + 1);
ll L = p[n / 2 + 1].l, R = s, ans = 0;
while (L <= R)
{
ll mid = (L + R) >> 1;
bool chk = f1(mid);
if (chk)
ans = mid, L = mid + 1;
else
R = mid - 1;
}
cout << ans << '\n';
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
E1 - Voting (Easy Version)
E2 - Voting (Hard Version)
这里只说 E2。
按照 $m_i$ 排序，从 $m_i$ 大的一边入手。显然对于一个人，买了的人数+$m_i$ 比他小的人数 < 自己的 $m_i$ 的话就需要从 $m_i$ 大的人里面买，贪心地买的越少越好，这里一个 set 或者优先队列就可以。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
int n;
struct voter
{
int p, m;
bool operator<(const voter &rhs) const { return m < rhs.m; }
} a[N];
multiset<int> s;
ll ans;
inline void solve()
{
s.clear();
scanf(
for (int i = 1; i <= n; ++i)
scanf(
sort(a + 1, a + n + 1);
int buyer = 0;
ans = 0;
for (int i = n; i >= 1; --i)
{
s.insert(a[i].p);
if (a[i].m > i - 1 + buyer)
{
while (i - 1 + buyer != a[i].m)
{
ans += (*s.begin());
s.erase(s.begin());
buyer++;
}
}
}
cout << ans << '\n';
}
int main()
{
TIME__START = clock();
int Test = 1;
scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
F - Red-White Fence
显然对于每一个 $b_i$ 都是一个单独的问题。接下来开始入手。
把 $a_i$ 从小到大排序并且 unique，设 $cnt(i)$ 表示高度为 $i$ 的白条个数，设 $dp(i,j)$ 表示前 $i$ 小里面选了 $j$ 个白条的方案数，有下面的转移方程：$dp(i,j)=dp(i-1,j)+2\times dp(i-1,j-1)+dp(i-1,j-2)\times [cnt(i)\ge 2]$，分别表示不选、只选一个、选两个。
但这个 dp 是 $\mathcal{O}(n^2)$ 的，怎么优化？
优化就考虑把上面最后一项分成两部分：第一部分，$cnt(i)=1$，那么就有 $dp(i,j)=dp(i-1,j)+2\times dp(i-1,j-1)$，这是一个牛顿二项式那种，可以根据组合意义，得到 $dp(i,j)=\binom{cntn}{i}2^i$；第二部分，$cnt(i)\ge 2$，那么就有 $dp(i,j)=\binom{2\cdot cntm}{i}$。上面 $cntn$ 表示 $cnt(i)=1$ 的白条个数，$cntm$ 表示 $cnt(i)\ge 2$ 的白条个数，这两个东西可以写成俩生成函数：$F=\sum\limits_{k=0}^{cntn}\binom{cntn}{k}2^kx^k$ 和 $G=\sum\limits_{k=0}^{2\cdot cntm}\binom{2\cdot cntm}{k}x^k$，用 NTT 把这两个卷起来，然后 $F(i)$ 的系数就是 $i+1+b$ 的贡献。
时间复杂度 $\mathcal{O}(nk\log n)$。
#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
printf("\n\nTime used:
system("pause");
#endif
}
const int Lim = 1 << 20;
struct polyntt
{
typedef vector<int> Vi;
int add(int a, int b) { return (a += b) >= mod ? a - mod : a; }
int sub(int a, int b) { return (a -= b) >= 0 ? a : a + mod; }
int mul(long long a, int b) { return a * b
int ksm(int a, int b)
{
int ret = 1;
while (b)
{
if (b & 1)
ret = 1ll * ret * a
a = 1ll * a * a
b >>= 1;
}
return ret;
}
int rev[Lim + 5], lg2[Lim + 5], rt[Lim + 5], irt[Lim + 5];
int n, k, lim, type;
void init() //求原根
{
for (int i = 2; i <= Lim; i++)
lg2[i] = lg2[i >> 1] + 1;
rt[0] = 1;
rt[1] = ksm(3, (mod - 1) / Lim); //第一个原根
irt[0] = 1;
irt[1] = ksm(rt[1], mod - 2); //费马小
for (int i = 2; i <= Lim; i++)
{
rt[i] = mul(rt[i - 1], rt[1]);
irt[i] = mul(irt[i - 1], irt[1]);
}
}
void NTT(Vi &f, int type, int lim)
{
f.resize(lim);
int w, y, l = lg2[lim] - 1;
for (int i = 1; i < lim; i++)
{
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l);
if (i >= rev[i])
continue;
swap(f[i], f[rev[i]]); //蝴蝶
}
l = Lim >> 1;
for (int mid = 1; mid < lim; mid <<= 1)
{
for (int j = 0; j < lim; j += (mid << 1))
{
for (int k = 0; k < mid; k++)
{
w = type == 1 ? rt[l * k] : irt[l * k];
y = mul(w, f[j | k | mid]);
f[j | k | mid] = sub(f[j | k], y);
f[j | k] = add(f[j | k], y);
}
}
l >>= 1;
}
if (type == 1)
return;
y = ksm(lim, mod - 2);
for (int i = 0; i < lim; i++)
f[i] = mul(f[i], y);
}
void NTTTMD(Vi &F, Vi &G)
{
int n = F.size() + G.size();
lim = 1;
while (lim <= n)
lim <<= 1;
F.resize(lim);
G.resize(lim);
NTT(F, 1, lim), NTT(G, 1, lim);
for (int i = 0; i < lim; i++)
F[i] = mul(F[i], G[i]);
NTT(F, -1, lim);
F.resize(n - 1);
}
} myntt;
int n, k, a[N], b[10], q[N], Q, cnt[N];
ll ans[1000050], fac[N], invfac[N];
ll C(ll n, ll m) { return n < m ? 0 : (fac[n] * invfac[m]
inline void solve()
{
myntt.init();
fac[0] = invfac[0] = 1;
for (int i = 1; i <= 3e5; ++i)
fac[i] = fac[i - 1] * i
scanf(
for (int i = 1; i <= n; ++i)
scanf(
for (int i = 1; i <= k; ++i)
scanf(
scanf(
for (int i = 1; i <= Q; ++i)
scanf(
sort(a + 1, a + n + 1);
int m = unique(a + 1, a + n + 1) - a - 1;
for (int T = 1; T <= k; ++T)
{
vector<int> F, G;
int cntn = 0, cntm = 0;
for (int i = 1; i <= m && a[i] < b[T]; ++i)
{
if (cnt[a[i]] == 1)
cntn++;
else
cntm++;
}
for (int i = 0; i <= cntn; ++i)
F.push_back(myntt.mul(C(cntn, i), myntt.ksm(2, i)));
for (int i = 0; i <= 2 * cntm; ++i)
G.push_back(C(2 * cntm, i));
myntt.NTTTMD(F, G);
for (int i = 0; i < (int)F.size(); ++i)
ans[i + 1 + b[T]] = myntt.add(ans[i + 1 + b[T]], F[i]);
}
for (int i = 1; i <= Q; ++i)
printf(
}
int main()
{
TIME__START = clock();
int Test = 1;
// scanf(
while (Test--)
{
solve();
// if (Test)
// putchar('\n');
}
TIME__END = clock();
program_end();
return 0;
}
Comments NOTHING