tourist 场 Orz。
分类讨论题。
-
将 \(x\) 坐标对齐，然后前后绕。
-
将 \(y\) 坐标对齐，然后左右绕。
两种情况取最小值即可。
复杂度 \(O(1)\)。
#include <bits/stdc++.h>
using namespace std;
int T;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
int w, d, h; cin >> w >> d >> h;
int a, b, x, y; cin >> a >> b >> x >> y;
int tmp = abs(a - x) + h + min(d - b + d - y, b + y);
int tmp2 = abs(b - y) + h + min(w - a + w - x, a + x);
cout << min(tmp, tmp2) << endl;
}
return 0;
}
先将 \(a\) 数组从小到大排序。
如果我们能选 \(i\) 个人，那么必定是排完序后 \(a\) 数组的前 \(i\) 个人。
所以我们枚举每个 \(i\)，如果 \(a_i+1\le i\) 且 \(a_{i+1}>i\)，则可以。
注意一个不选的情况。
复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int T, n, a[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
long long ans = (a[1] != 0);
a[n + 1] = INT_MAX;
for (int i = 1; i <= n; ++i) {
if (a[i] + 1 <= i && i < a[i + 1]) ++ans;
}
cout << ans << endl;
}
return 0;
}
思路对的，赛场上没调出来......
考虑枚举 \(n\) 的每个约数 \(i\)，表示调整完后有 \(i\) 个不同的字符，每个字符出现 \(\frac{n}{i}\) 次。
与其在 \(s\) 上改最少的字符，我们不如直接主动放置字符，使得相同的位最多。
那么显然最少修改次数为：\(n-\sum\limits_{c=0}^{25}\min(cnt_c,\frac{n}{i})\)。
我们可以贪心地放置，相同位尽可能地放，最后再把没匹配上的字符随便插空塞进去就行了。
注意，选的 \(i\) 种字符一定要在原串中出现的尽可能多，所以还要排个序从大往小选。
复杂度 \(O(n\sqrt n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int T, n, a[N];
string s, t, ans;
vector<int> vec[30];
bool cmp(int x, int y) {
return vec[x].size() > vec[y].size();
}
queue<int> q;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n >> s; s = "." + s; t = s; for (int i = 0; i < 26; ++i) vec[i].clear();
for (int i = 1; i <= n; ++i) vec[s[i] - 'a'].push_back(i);
for (int i = 1; i <= 26; ++i) a[i] = i - 1;
sort(a + 1, a + 27, cmp);
int maxn = 0;
for (int i = 1; i <= min(n, 26); ++i) {
if (n % i == 0) {
while (!q.empty()) q.pop();
for (int j = 1; j <= n; ++j) t[j] = '.';
int up = n / i, cnt = 0;
for (int j = 1; j <= i; ++j) {
int tmp = vec[a[j]].size();
int xuan = min(up, tmp); cnt += xuan;
for (int k = 0; k < xuan; ++k) t[vec[a[j]][k]] = (char)(a[j] + 'a');
for (int k = xuan + 1; k <= up; ++k) q.push(a[j]);
}
if (cnt > maxn) {
maxn = cnt;
for (int j = 1; j <= n; ++j) {
if (t[j] == '.') {
t[j] = (char)(q.front() + 'a');
q.pop();
}
}
ans = t;
}
}
}
ans.erase(0, 1);
cout << n - maxn << endl << ans << endl;
}
return 0;
}
有意思的数学+枚举题。
答案最小为 \(1\)。
考虑答案大于 \(1\) 的情况，那么必然有两个数 \(a_i\) 和 \(a_j\) 满足加上 \(x\) 后为完全平方数。
所以我们去枚举他们。
根据平方差公式可知，\(a_j-a_i=(t_1-t_2)(t_1+t_2)\)，其中 \(t1=\sqrt{a_j+x}\)，\(t2=\sqrt{a_i+x}\)。
于是我们可以枚举 \(a_j-a_i\) 的约数，然后相加除二求出 \(t_1\)，再根据 \(x=t_1^2-a_j\) 求出 \(x\)，最后在 \(a_1\) 到 \(a_n\) 中找出有多少个加上 \(x\) 为平方数，取最大值即可。
注意判断枚举时无解的情况。
复杂度 \(O(n^3\sqrt{10^9})\)，实际上要小很多。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50 + 5;
ll T, n, a[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
ll ans = 1;
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
ll cha = a[j] - a[i];
for (ll k = 1; k * k <= cha; ++k) {
ll k2 = cha / k, t1, x;
if ((k + k2) & 1) continue;
t1 = (k + k2) / 2;
x = t1 * t1 - a[j];
if (x >= 0) {
ll cnt = 0;
for (int l = 1; l <= n; ++l) {
ll tmp = sqrt(a[l] + x);
if (tmp * tmp == a[l] + x) ++cnt;
}
ans = max(ans, cnt);
}
}
}
}
cout << ans << endl;
}
return 0;
}
有技巧的神仙模拟题。
容易发现，调整完之后的最大覆盖面积为调整前的覆盖面积。
我们考虑维护两个双端队列，\(q_1\) 和 \(q_2\)，分别维护第一行和第二行的覆盖情况。
先按照左端点从小到大，右端点从大到小，对矩形排序。
接下来这样操作。
-
弹出已经完成的矩形。
-
如果当前矩形只有一行。
-
如果已经被包含，删掉。
-
否则调整其左端点 \(l\)，插入。
-
-
如果矩形有两行。
-
被上下两行包含，删掉。
-
只被上行包含，取右下部分。
-
只被下行包含，取右上部分
-
都没被包含，调整上下两行末尾矩形的右端点 \(r\)。
-
最后按编号输出即可。
复杂度 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int T, n, ans = 0;
struct node{int u, d, l, r, id;}ret[N], res[N];
bool cmp(node x, node y) {return x.l != y.l ? x.l < y.l : x.r > y.r;}
deque<int> q[3];
void popok(int w, int i) {while (!q[w].empty() && ret[q[w].back()].r < ret[i].l) q[w].pop_back();}
bool incl(int w, int i) {return !q[w].empty() && ret[i].r <= ret[q[w].front()].r;}
void clear(int i) {ret[i].u = ret[i].d = ret[i].l = ret[i].r = 0;}
void ins(int w, int i) {
if (w == 1) ret[i].u = 2; else ret[i].d = 1;
if (!q[3 - w].empty()) ret[i].l = ret[q[3 - w].front()].r + 1;
q[3 - w].push_front(i);
}
void adjust(int w, int i) {
while (!q[w].empty()) {
if (ret[q[w].front()].l < ret[i].l) ret[q[w].front()].r = ret[i].l - 1;
else clear(q[w].front());
q[w].pop_front();
}
}
void solve(int i) {
popok(1, i); popok(2, i);
if (ret[i].u == ret[i].d) {
if (incl(ret[i].u, i)) clear(i);
else {
if (!q[ret[i].u].empty()) ret[i].l = ret[q[ret[i].u].front()].r + 1;
q[ret[i].u].push_front(i);
}
} else {
if (incl(1, i) && incl(2, i)) clear(i);
else if (incl(1, i)) ins(1, i);
else if (incl(2, i)) ins(2, i);
else adjust(1, i), adjust(2, i), q[1].push_front(i), q[2].push_front(i);
}
}
int cal(int i) {return !ret[i].u ? 0 : (ret[i].d - ret[i].u + 1) * (ret[i].r - ret[i].l + 1);}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n;
ans = 0;
while (!q[1].empty()) q[1].pop_back(); while (!q[2].empty()) q[2].pop_back();
for (int i = 1; i <= n; ++i) cin >> ret[i].u >> ret[i].l >> ret[i].d >> ret[i].r, ret[i].id = i;
sort(ret + 1, ret + n + 1, cmp);
for (int i = 1; i <= n; ++i) solve(i);
for (int i = 1; i <= n; ++i) ans += cal(i), res[ret[i].id] = ret[i];
cout << ans << endl;
for (int i = 1; i <= n; ++i) {
if (!res[i].u) cout << "0 0 0 0" << endl;
else cout << res[i].u << " " << res[i].l << " " << res[i].d << " " << res[i].r << endl;
}
}
return 0;
}
神仙 DP 题，不愧是 tourist。
容易发现，括号序列一共有 \(1\cdot 3\cdot 5...\cdot (2n-1)\) 种生成方式。
假如 ( 为 \(1\)，) 为 \(-1\)，那么一个序列合法的充要条件为：最小前缀和为 \(0\)，且以 \(0\) 结尾。
现在考虑维护这些前缀和。
如果我们在当前序列某一位后插入一个 ()，且那一位的前缀和为 \(x\),那么相当于把 \(x\) 替换成 \([x,x+1,x]\)。
同理可知，插入 )( 相当于把 \(x\) 替换成 \([x,x-1,x]\)。
定义 \(f_{n,x}\) 为，执行 \(n\) 次操作，初始前缀和为 \(x\) 的方案数。
那么显然有两种转移：
其中，\(i\) 对应第一个 \(x\)，\(j\) 对应 \(x+1\) 和 \(x-1\)，\(n-i-j-1\) 对应第二个 \(x\)。
由于每个部分的操作都是独立的，所以还要乘上组合数。
状态 \(n^2\)，转移枚举 \(O(n^2)\)，总复杂度 \(O(n^4)\)，无法接受。
我们考虑优化掉一个 \(\sum\)。将与 \(j\) 有关的都提到前面来。
定义 \(g_{n,x}=\sum\limits_{i=0}^{n}\dbinom{n}{i}\cdot f_{i,x}\cdot f_{n-i,x}\)
那么转移方程最终可化简为：
最后输出 \(\frac{f_{n,0}}{1\cdot 3\cdot 5...\cdot (2n-1)}\) 即可。
复杂度 \(O(n^3)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 500 + 5, mod = 998244353;
ll n, p, c[N][N], f[N][N], g[N][N];
ll ksm(ll x, ll y) {
ll res = 1;
while (y) {
if (y & 1) res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> p; p = p * ksm(10000, mod - 2) % mod;
for (int i = 0; i <= n; ++i) c[i][0] = 1;
for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
for (int i = 0; i <= n; ++i) f[0][i] = g[0][i] = 1;
for (int i = 1; i <= n; ++i) {
for (int x = 0; x <= n; ++x) {
for (int j = 0; j < i; ++j) {
f[i][x] = (f[i][x] + (p * f[j][x + 1] + (1 - p + mod) * (x ? f[j][x - 1] : 0)) % mod * c[i - 1][j] % mod * g[i - j - 1][x] % mod) % mod;
}
for (int j = 0; j <= i; ++j) {
g[i][x] = (g[i][x] + c[i][j] * f[j][x] % mod * f[i - j][x] % mod) % mod;
}
}
}
ll ans = f[n][0];
for (int i = 1; i <= 2 * n; i += 2) ans = ans * ksm(i, mod - 2) % mod;
cout << ans << endl;
return 0;
}