AtCoder Beginner Contest 332

前面两道阅读理解直接跳过。

C - T-shirts

大意

有两种衬衫，初始时你有a衬衫件，没有b衬衫。穿过的衬衫必须要等到洗完才能继续穿。

接下来天，每天会做三种活动中的一种：

• 洗衣服，之前穿过的衬衫都可以再穿。
• 待家里，两种衬衫都能穿。
• 打比赛，只能穿b衬衫。

问b衬衫至少买多少件，才能满足这天的穿着需求。

思路

如果待家里，肯定能穿a衬衫就穿a衬衫，不够才买b衬衫。

记录已经穿了的a衬衫和b衬衫件数，每到洗衣服天就重置使用过的 a衬衫和b衬衫。

期间b衬衫的最大值即为答案。

代码

#include
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 
#include 
#include 
#include 
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;
 
    vectorint>> a(h, vector<int>(w, 0));
    vectorint>> 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。

设dpi,Sdpi,S表示现在已经分出了组，且集合SS内的数已经被选走了时的最小的平方和。

可得：dpi,S=minT⊆S{dpi−1,T+(∑j∈S∖Twj)2}

注意在计算答案之前，都只能使用整数计算，否则会有精度问题。

代码

#include 
#include 
#include 
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);
    vectorint>> 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

大意

给定一个序列，执行q次以下操作：

• 给定l,r,x，等概率地从区间[l,r]挑一个数改为x

求最后每个元素的期望，对998244353取模。

思路

容易发现变的概率是1r−l+1，不变的概率是r−lr−l+1。

因此每个操作就是对所有满足i∈[l,r]的进行以下修改：

Ai=r−lr−l+1Ai+1r−l+1x

维护一棵支持区间加，区间乘，单点查询的线段树即可。每次对区间[l,r]乘inv(r−l+1)×(r−l)，加上inv(r−l+1)x即可。

代码

#include 
#include 
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 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;
}