比赛链接: https://www.luogu.com.cn/contest/124225#description
A - 三值的排序
难度 ⭐⭐
解题思路
如果a在b应在的位置上, 同时还有个b在a应在的位置, 这时候交换a和b是最优的, 因为交换后就不需要再调整了; 因此我们先把序列排序, 找到每个数应该在哪个区间内; 然后遍历原序列并和排好序的序列作比较, 如果原序列该位置为a, 而排好序的序列该位置为b, 就用map把{a,b}出现的次数记录下来, 说明有多少个a处在了b应在位置上; 这样找出所有矛盾后, 遍历所有可能的情况, 对于mp[{i, j}]和mp[{j, i}], 让它们减去它们当中较小的那个, 而这个较小的数就是最优情况交换的次数; 找完所有最优情况后, 我们只需要遍历1和2的所有情况, 并且将其归为即可, 因为1和2都归为后3自然也归为了, 如果把3的情况也算上反而重复了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m, res;
int x1, x2;
int f[N], g[N];
map<PII, int> mp;
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> f[i];
g[i] = f[i];
}
sort(g + 1, g + 1 + n);
for (int i = 1; i <= n; i++) {
if (f[i] != g[i]) {
mp[{ f[i], g[i] }]++;
}
}
for (int i = 1; i <= 3; i++) {
for (int j = i+1; j <= 3; j++) {
int a = min(mp[{i, j}], mp[{j, i}]);
mp[{i, j}] -= a;
mp[{j, i}] -= a;
res += a;
}
}
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= 3; j++) {
if (i == j) continue;
if (mp[{i, j}]) res += mp[{i, j}];
}
}
cout << res;
return 0;
}
B - 天际线
难度 ⭐⭐⭐⭐
解题思路
一道熟悉的题目, 来还债了属于是...这次正经地用线段树做一下; 因为本题是区间修改, 所以除了一般的左右节点和最大值外我们还需要维护一个懒标记la, 表示这个区间在最高la这个高度是平坦的, 所以如果一个区间最终是平坦的, 那么这个区间的la和maxn相等; 建好树后开始修改操作, 如果该范围包含当前区间, 那么更新最大值和懒标记: maxn=max(maxn, h), la=max(la,h); 如果不完全包含就还是pushdown+左右区间+pushup三件套, pushup就用来更新父节点的最大值, 而pushdown需要用父节点的la去更新左右节点, 注意是用la而不是maxn, maxn只是父节点区间的最大值, 而la是整个父节点区间都可以达到的一个高度, la是可以去影响子节点的; 所以对于左右节点: maxn=max(maxn, fla), la=max(la,fla);
因为坐标最大为1e4, 我们可以去查询每个坐标的最大值, 然后把变化的地方输出即可; 查询时query(1, i, i), 所以当l=i&&r=i时输出这个区间的maxn即可(其实是一个点); 否则就pushdown之后从左右区间找即可;
本题的关键还是在于对la的理解, maxn只是用来最后找答案, 在修改过程中操作的重点的还是la; 而且, 因为这个题最后是找每个点的高度, 所以我们甚至可以把maxn和pushup删去, 因为根据我们对la这个懒标记的定义, 对于点这个区间, 能让其平坦的最大高度就是maxn;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4+10, mod = 1e9 + 7;
int n, m;
int h[N];
struct str {
int l, r;
int maxn, la;
}tr[4*N];
void pushup(int u) {
tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
void pushdown(int u) {
auto & root = tr[u], & left = tr[u << 1], & right = tr[u << 1 | 1];
if (root.la) {
left.maxn = max(left.maxn, root.la);
left.la = max(left.la, root.la);
right.maxn = max(right.maxn, root.la);
right.la = max(right.la, root.la);
root.la = 0;
}
}
void build(int u, int l, int r) {
tr[u] = { l,r };
if (l == r) return;
else {
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
}
void modify(int u, int l, int r, int a) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].maxn = max(tr[u].maxn, a);
tr[u].la = max(tr[u].la, a);
}
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, a);
if (r > mid) modify(u << 1 | 1, l, r, a);
pushup(u);
}
}
int query(int u, int l, int r) {
if (tr[u].l == l && tr[u].r == r) {
return tr[u].maxn;
}
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if (l <= mid) res=query(u << 1, l, r);
if (r > mid) res =query(u << 1 | 1, l, r);
return res;
}
}
signed main() {
IOS;
int a, b, c;
build(1, 1, 10000);
while (cin >> a >> b >> c) {
modify(1, a, c - 1, b);
}
for (int i = 1; i <= 10000; i++){
h[i] = query(1, i, i);
}
for (int i = 1; i <= 10000; ++i){
if (h[i] != h[i - 1]){
printf("%d %d ", i, h[i]);
}
}
return 0;
}
C - Bond
难度 ⭐⭐
解题思路
由n的范围只有20可以想到用状压dp, 状态表示: dp[i]表示用前k个人完成k个任务的最大成功率, i为当前完成哪些任务的状态, k是i中1的个数; 状态计算: dp[i] = max(dp[i], dp[i - (1 << (j-1))] * f[k][j]); f[k][j]表示第k个人完成第j个任务的成功率; 所以我们每次只考虑第k个人完成哪个任务即可, 算是比较典型的一个dp处理方式;
警钟敲烂!!!最后输出的时候记得要用printf, cout输出是默认保留小数点前后6位, 而printf才是保留小数点后6位;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 21, mod = 1e9 + 7;
int n, m;
double dp[1 << N], f[N][N];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
double a;
cin >> a;
f[i][j] = a * 0.01;
}
}
dp[0] = 1.0;
for (int i = 1; i < 1 << n; i++) {
int k = i, num = 0;
while (k) {
if (k & 1) num++;
k >>= 1;
}
for (int j = 1; j <= n; j++) {
if (i >> (j-1) & 1) {
double x = dp[i - (1 << (j-1))];
dp[i] = max(dp[i], x * f[num][j]);
}
}
}
printf("%lf", dp[(1 << n) - 1] * 100);
return 0;
}
D - DEATHSTAR
难度 ⭐
解题思路
既然第i行是用ai和其他数做与运算, 那么对于所有b(i,j)来说, ai是1的位上它们也得是1, 反过来也一样, 所以我们可以把第i行的所有数做与操作, 那么结果一定是ai的一种可能;
神秘代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N=1e3+10;
int n, m;
int f[N][N], q[N];
signed main() {
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>f[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
q[i]|=f[i][j];
}
}
for(int i=1;i<=n;i++){
cout<<q[i]<<' ';
}
return 0;
}
E - 瑞瑞的木板
难度 ⭐⭐
解题思路
贪心问题, 我们可以把切割问题看作是拼接问题, 对于a=b+c, 我们可以选择合成b或者c, 因为最后的和是一样, 如果我们合成b的话, 无论c多大, 这次拼接花费的能量就是a, 所有我们可以c是较大的那个, 我去合成较小的那个数, 所以我们可以用堆去维护当前所有木条的顺序, 每次拼接时条最小的两条合并即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, m, res;
int f[N];
priority_queue<int, vector<int>, greater<int>> q;
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int a;
cin >> a;
q.push(a);
}
while (q.size()>1) {
int a = q.top();
q.pop();
int b = q.top();
q.pop();
res += a + b;
q.push(a + b);
}
cout << res;
return 0;
}
F - Load Balancing S
难度 ⭐⭐⭐
解题思路
因为是问四个二维区间的最小值, 所以我们可以用二维前缀和把区间和处理出来; 因为N的数量只有1000, 而坐标是1e6, 所以我们可以进行离散化处理, 然后枚举两条栅栏的坐标即可, 约为1e7的复杂度, 所以不会超时; 需要注意的是离散化返回的值也得是奇数, 因为有2n的坐标, 所以离散化后坐标的最大值是4n+1; 所以记得设置好边界;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 4e3+50, mod = 1e9 + 7;
int n, m;
vector<int> v;
PII g[N];
int f[N][N];
int find(int u) {
auto t = lower_bound(v.begin(), v.end(), u) - v.begin();
return 2 * t + 1;
}
signed main() {
IOS;
cin >> n;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
g[i] = { a,b };
v.push_back(a);
v.push_back(b);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 1; i <= n; i++) {
int a = find(g[i].first), b = find(g[i].second);
f[a][b]++;
}
n = n * 4 + 10;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
}
}
int minn = 1e9;
for (int i = 2; i <= n; i+=2) {
for (int j = 2; j <= n; j += 2) {
int a = f[i][j];
int b = f[n][j] - f[i][j];
int c = f[i][n] - f[i][j];
int d = f[n][n] - a - b - c;
int maxn = max(max(a, b), max(c, d));
minn = min(minn, maxn);
}
}
cout << minn;
return 0;
}
H - 查单词
难度 ⭐⭐
解题思路
一道比较裸的线段树, 只不过把数据类型改为了字符串, 对此自己写一个max函数即可; 其他操作和线段树的模板差不多, 就不过多赘述了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 5e4 + 10, mod = 1e9 + 7;
int n, m;
string f[N];
struct str{
int l, r;
string maxn;
}tr[4*N];
string cmax(string a, string b) {
int len = min(a.size(), b.size());
for (int i = 0; i < len; i++) {
char c = a[i], d = b[i];
if (c < 'a') c += 32;
if (d < 'a') d += 32;
if (c > d) return a;
else if (c < d) return b;
}
if (a.size() < b.size()) return b;
else return a;
}
void pushup(int u) {
tr[u].maxn = cmax(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
void build(int u, int l, int r) {
if (l == r) tr[u] = { l,r,f[l] };
else {
tr[u] = { l,r };
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
string check(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].maxn;
else {
string res;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) res = check(u << 1, l, r);
if (r > mid) res = cmax(res, check(u << 1 | 1, l, r));
return res;
}
}
signed main() {
IOS;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> f[i];
}
build(1, 1, n);
for (int j = 1; j <= m; j++) {
int a, b;
cin >> a >> b;
cout << check(1, a, b) << endl;
}
return 0;
}
I - 还是 N 皇后
难度 ⭐⭐⭐⭐
解题思路
如果用之前的方法的话一定会超时, 本题的用意是想用位运算进行优化, 因为我们dfs是相当于枚举每一行, 所以我们可以用二进制表示当前这一行哪些位置可以放, 哪些位置不能放, 影响因素有四个: 一是输入给定的不能放的位置为1; 二是列, 如果第i位上已经有皇后了, 那么这一行第i位就是1; 三是主对角线, 如果上一行的第i位上有皇后了, 那个这一行的第i+1位就是1, 四是副对角线, 如果上一行的第i位上有皇后了, 那个这一行的第i-1位就是1; 把这四种情况进行与操作就得到了第i行的状态;
注意边界处的对角线情况可能会让二进制多出1位, 所以我们处理完后要和(1 << n) - 1进行一次与操作, 把多出来的1去掉;
这样我们就得到了第i行的状态表示, 然后我们取反, 这样状态中1的位置就是可以放皇后的位置, 可以用lowbit操作去获取1的位置;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3+10, mod = 1e9 + 7;
int n, m, res, full;
int stu[N];
void dfs(int c,int ld, int rd, int u) {
if (c == full) {
res++;
return;
}
int p = ~(c | ld | rd | stu[u]);
p = p & full;
while (p) {
int a = p & -p;
p -= a;
dfs(c + a, (ld + a) >> 1, (rd + a) << 1, u + 1);
}
}
signed main() {
IOS;
cin >> n;
full = (1 << n) - 1;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
int a = 0;
for (int j = 0; j < s.size(); j++) {
if (s[j] == '.') a |= (1 << n-j-1);
}
stu[i] = a;
}
dfs(0, 0, 0, 1);
cout << res;
return 0;
}