前面两道阅读理解直接跳过。
C - T-shirts
大意
有两种衬衫,初始时你有a衬衫件,没有b衬衫。穿过的衬衫必须要等到洗完才能继续穿。
接下来天,每天会做三种活动中的一种:
- 洗衣服,之前穿过的衬衫都可以再穿。
- 待家里,两种衬衫都能穿。
- 打比赛,只能穿b衬衫。
问b衬衫至少买多少件,才能满足这天的穿着需求。
思路
如果待家里,肯定能穿a衬衫就穿a衬衫,不够才买b衬衫。
记录已经穿了的a衬衫和b衬衫件数,每到洗衣服天就重置使用过的 a衬衫和b衬衫。
期间b衬衫的最大值即为答案。
代码
#include<iostream>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, m;
string s;
cin >> n >> m >> s;
int p = m, l = 0, b = 0;
for(int i = 0; i < n; i++){
if(s[i] == '0') p = m, l = b;
else if(s[i] == '1'){
if(p > 0) p--;
else if(l > 0) l--;
else b++;
}else{
if(l > 0) l--;
else b++;
}
}
cout << b << endl;
return 0;
}
D - Swapping Puzzle
大意
给定两个矩阵和,通过下面两个操作,让矩阵变成矩阵:
- 交换相邻两行
- 交换相邻两列
问最小的操作次数。
思路
用表示现在的第行原来的行数,表示现在的第列原来的列数。
枚举的全排列,计算的逆序对数量总和(逆序对数量就是交换次数),打擂台去最小值。
代码
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int h, w;
cin >> h >> w;
vector<vector<int>> a(h, vector<int>(w, 0));
vector<vector<int>> b(h, vector<int>(w, 0));
for(auto &i: a) for(auto &j: i) cin >> j;
for(auto &i: b) for(auto &j: i) cin >> j;
vector<int> p(h), q(w);
iota(p.begin(), p.end(), 0);
iota(q.begin(), q.end(), 0);
auto check = [&]() -> bool{
for(int i = 0; i < h; i++)
for(int j = 0; j < w; j++)
if(a[p[i]][q[j]] != b[i][j]) return false;
return true;
};
int ans = INF;
do{
do{
if(!check()) continue;
int num = 0;
for(int j = 0; j < h; j++)
for(int i = 0; i < j; i++) num += p[i] > p[j];
for(int j = 0; j < w; j++)
for(int i = 0; i < j; i++) num += q[i] > q[j];
ans = min(ans, num);
} while(next_permutation(q.begin(), q.end()));
} while(next_permutation(p.begin(), p.end()));
cout << (ans == INF? -1: ans) << endl;
return 0;
}
E - Lucky Bag
大意
将个物品放到个袋子中,每个物品有一个重量,放入袋子中后,设每个袋子内物品总重,求这些袋子内物品总重数据 的方差最小值。
思路
求方差,只需要最小化平方和。
数据量很小,考虑状压DP。
设表示现在已经分出了组,且集合内的数已经被选走了时的最小的平方和。
可得:
注意在计算答案之前,都只能使用整数计算,否则会有精度问题。
代码
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
#define int long long
typedef long double real;
const int INF = 3e18;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, d;
cin >> n >> d;
vector<int> w(n), s(1 << n);
vector<vector<int>> f(n + 1, vector<int>(1 << n));
for (int i = 0; i < n; i++) {
cin >> w[i];
for (int j = 0; j < (1 << n); j++)
if (j >> i & 1) s[j] += w[i];
}
for (int i = 0; i < (1 << n); i++) s[i] *= s[i];
for (int i = 1; i < (1 << n); i++) f[0][i] = INF;
for (int i = 1; i <= d; i++)
for (int j = 0; j < (1 << n); j++) {
f[i][j] = s[j];
for (int k = j; k; k = j & k - 1) f[i][j] = min(f[i][j], f[i - 1][k] + s[j ^ k]);
}
real ans = 1.0L * (f[d][(1 << n) - 1] * d - s[(1 << n) - 1]) / (d * d);
cout << fixed << setprecision(15) << ans << endl;
return 0;
}
F - Random Update Query
大意
给定一个序列,执行次以下操作:
- 给定,等概率地从区间挑一个数改为
求最后每个元素的期望,对取模。
思路
容易发现变的概率是,不变的概率是。
因此每个操作就是对所有满足的进行以下修改:
维护一棵支持区间加,区间乘,单点查询的线段树即可。每次对区间乘,加上即可。
代码
#include <iostream>
#include <vector>
using namespace std;
#define int long long
const int P = 998244353;
int qpow(int a, int k){
int res = 1;
while (k){
if (k & 1) res = res * a % P;
a = a * a % P;
k >>= 1;
}
return res;
}
int inv(int x){
return qpow(x, P - 2);
}
struct segment{
struct Node{
int l = 0, r = 0, add = 0, mul = 0, sum = 0;
};
vector<Node> tr;
segment(vector<int> &a){
int n = a.size();
tr.resize(n << 2);
build(1, 1, n, a);
}
void pushdown(int u){
int len1 = tr[u << 1].r - tr[u << 1].l + 1;
int len2 = tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1;
tr[u << 1].sum = ((tr[u << 1].sum * tr[u].mul) % P + (tr[u].add * len1) % P)% P;
tr[u << 1 | 1].sum = ((tr[u << 1 | 1].sum * tr[u].mul) % P + (tr[u].add * len2) % P) % P;
tr[u << 1].mul = (tr[u << 1].mul * tr[u].mul) % P;
tr[u << 1 | 1].mul = (tr[u << 1 | 1].mul * tr[u].mul) % P;
tr[u << 1].add = ((tr[u << 1].add * tr[u].mul) % P + tr[u].add) % P;
tr[u << 1 | 1].add = ((tr[u << 1 | 1].add * tr[u].mul) % P + tr[u].add) % P;
tr[u].add = 0;
tr[u].mul = 1;
}
void pushup(int u){
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % P;
}
void build(int u, int l, int r, vector<int> &a){
tr[u].l = l, tr[u].r = r, tr[u].mul = 1;
if(l == r) tr[u].sum = a[l - 1] % P;
else{
int mid = l + r >> 1;
build(u << 1, l, mid, a), build(u << 1 | 1, mid + 1, r, a);
pushup(u);
}
}
int query(int u, int i){
if(tr[u].l == i && tr[u].r == i) return tr[u].sum % P;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(i <= mid) return query(u << 1, i);
else return query(u << 1 | 1, i);
}
void modify(int u, int l, int r, int v, bool f){
if(tr[u].l == l && tr[u].r == r){
if(!f){
tr[u].sum = (tr[u].sum + v * (tr[u].r - tr[u].l + 1)) % P;
tr[u].add = (tr[u].add + v) % P;
}
else{
tr[u].sum = (tr[u].sum * v) % P;
tr[u].mul = (tr[u].mul * v) % P;
tr[u].add = (tr[u].add * v) % P;
}
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) modify(u << 1, l, r, v, f);
else if(l > mid) modify(u << 1 | 1, l, r, v, f);
else{
modify(u << 1, l, mid, v, f);
modify(u << 1 | 1, mid + 1, r, v, f);
}
pushup(u);
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for(auto &i: a) cin >> i;
segment seg(a);
while(q--){
int l, r, z;
cin >> l >> r >> z;
int len = r - l + 1;
seg.modify(1, l, r, (inv(len) * (len - 1)) % P, true);
seg.modify(1, l, r, (inv(len) * z) % P, false);
}
for(int i = 1; i <= n; i++) cout << seg.query(1, i) << ' ';
cout << endl;
return 0;
}