H Holding Two

题意

就是给定两个数n和m，要求输出一个长宽为n和m的01矩阵，且要求横竖斜都不能有连续的三个数字相同。

题目理解

直接构造就行，其实有很多种构造方法都满足题意，我这里直接以110为基础构造。（唯一一道过了的题）

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pai;
const int N = 20 + 10;
const int mod = 1e9 + 7;


inline bool read(int &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

void solve() {
    int n, m;
    cin >> n >> m;
    int out1 = 1, out2 = 1, cnt = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << out1;
            out1 = (!out1);
        }
        out1 = out2;
        cnt++;
        if (cnt == 2){
            cnt=0;
            out2 = (!out2);
        }
        if (i != n)
            cout << endl;
    }
}

int main() {
    solve();
    return 0;
}

B Boxes

题意

给定n个盒子，每个盒子里面有个球且是黑白中的一种。打开盒子有代价wi，且可以花费代价c获得剩下未开盒子的黑球数量，求获得所有盒子内球色的花费期望。

题目理解

（一开始一看以为数学期望dp，想了半天发现没啥办法构造子问题）开盒子有两种策略，一种是全开不花那个c，还有就是花一次c再开部分盒子。花费c只可能花费一次，而且在数学表示上最开始花还是后面再花没区别，所以可以一开始就把c代价加上。花费c的最优贡献一定是剩下的盒子内全都是黑球，又知道对于下标i及之后的盒子，盒子内有白球的概率为(1-1/2^(n-i))（也就是全黑球的概率为1/2^(n-i)，反过来就是存在白球的概率。又因为求的是期望，因此再乘个wi就完事了。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cmath>

#define fo(ii, nn) for(int ii=1;ii<=nn;ii++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pai;
const int N = 5000000 + 10;
const int mod = 1e9 + 7;
int n;
double c;
double w[N];

inline bool read(ll &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

int qp(int b, int p) {
    int ans = 1;
    int base = b, ansp = p;
    for (; p; p >>= 1) {
        if (p & 1) ans = (long long) ((ans * base));
        base = (long long) ((base * base));
    }
    return ans;
}

void solve() {
    double max1 = 0, max2 = 0, minans = 0;
    cin >> n >> c;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        max1 += w[i];
    }
    sort(w + 1, w + n + 1);
    double base = 1.0;
    for (int i = n; i >= 1; i--) {
        max2 += w[i] * (1.0 - base);
        base /= 2.0;
    }
    max2 += c;
    minans = min(max1, max2);
    printf("%.6lf", minans);
}

int main() {
    int t;
    solve();
    return 0;
}

K King of Range

题意

给定一串n个数字的串，询问m次，每次询问给定一个k。求在数字串中有多少个不同的区间(l,r)满足区间极差>k（不等于），极差为最大值-最小值。

题目理解

极差转换为单调队列维护区间最大值和最小值，遍历左端点l找符合条件的右边界下标数量，不断维护单调数组即可。另外实际操作的时候不需要真的找每一个右边界，只要找到第一个符合条件的右边界r后给答案加上n-r+1即可（因为当前的r如果已经满足了区间极差>k则右边界不管怎么向右移动都不影响这个极差值，且极差只会比之前的极差更大）。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cmath>

#define fo(ii, nn) for(int ii=1;ii<=nn;ii++)

using namespace std;
typedef unsigned long long ll;
typedef pair<int, int> pai;
const int N = 100000 + 10;
const int mod = 1e9 + 7;
int a[N];
int n;
int up[N], down[N];

inline bool read(int &num) {
    //quick read
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF) return false;
    while (in != '-' && (in < '0' || in > '9')) in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') { num *= 10, num += in - '0'; }
    if (IsN) num = -num;
    return true;
}

void query(int k) {
    ll ans = 0;
    int h1 = 1, t1 = 0, h2 = 1, t2 = 0; // 1是递增单调队列，2是递减单调队列，队列头先+1用于避免头=尾时的数量判断错误
    for (int l = 1, r = 1; r <= n; r++) {
        while (h1 <= t1 && a[up[t1]] >= a[r]) t1--; // 前移队尾直到找到可插入ar的位置
        up[++t1] = r;
        while (h2 <= t2 && a[down[t2]] <= a[r]) t2--; // 同理
        down[++t2] = r;
        while (a[down[h2]] - a[up[h1]] > k) {
            ans += 1ll * (n - r + 1); // r后面的区间都满足，因为最大值如何改变都绝对>k
            l++;
            while (l > up[h1]) h1++; // 右移l
            while (l > down[h2]) h2++;
        }
    }
    cout << ans << endl;
}

void solve() {
    int m;
    read(n);
    read(m);
    for (int i = 1; i <= n; i++) {
        read(a[i]);
    }
    fo(i, m) {
        int x;
        read(x);
        query(x); // 查询
    }
}

int main() {
    int t;
    solve();
    return 0;
}