优秀的拆分（power）

死于bitset的下标访问。看了眼之前的博客，然后随便测了点数据没出问题，然后就放心用bitset[0]这种，然后就G了。算法是对的，转换成string以后就能过了。

教训就是不知道bitset的下标访问出来是什么鬼东西。

其实直接用long long或者int都是能轻松切掉的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    while (cin >> n) {
        if (n & 1) {
            puts("-1");
            continue;
        }
        for (int i = log2(n); i; --i)
            if (n >> i) printf("%d ", 1 << i), n -= 1 << i;
        putchar(10);
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll n;
    while (cin >> n) {
        if (n & 1) {
            puts("-1");
            continue;
        }
        int len = log2(n) + 1;
        bitset<32> st(n);
        string s = st.to_string();
        int i = 0;
        while (!(s[i] - '0')) ++i;
        for (int j = 0; i < s.length(); i++, ++j) {
            if (s[i]-'0') {
                printf("%lld ", 1LL << (len - j - 1));
            }
        }
        putchar(10);
    }
    return 0;
}

直播获奖(live)

维护一个有序的vector，暴力即可。

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
using namespace std;
const int maxn = 2e5 + 7;
typedef long long ll;
int n, m, a[maxn];
vector<int> v;
int main() {
    sc(n), sc(m);
    for (int i = 1; i <= n; i++) {
        sc(a[i]);
        int x = max(1, (int)floor(i * m * 0.01));
        v.insert(lower_bound(v.begin(), v.end(), a[i]), a[i]);
        printf("%d ", v[v.size() - x]);
    }
    return 0;
}

想到的最优解法是队友提出来的拿树状数组当桶然后二分查。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 600 + 7;
#define lowbit(x) ((x) & (-x))
#define sc(x) scanf("%d", &(x))
ll tree[N], zero;
int n, w, a;
inline void update(int i, ll x) {
    for (int pos = i; pos < N; pos += lowbit(pos)) tree[pos] += x;
}
inline ll query(int n) {
    if (n < 0) return 0;
    ll ans = 0;
    for (int pos = n; pos; pos -= lowbit(pos)) ans += tree[pos];
    return ans;
}
inline ll query(int a, int b) { return query(b) - query(a - 1); }
inline int getans(int x) {
    int L = 0, R = N, ans = 0;
    while (L <= R) {
        int mid = L + R >> 1;
        if (query(mid, 600) >= x)
            L = mid + 1, ans = mid;
        else
            R = mid - 1;
    }
    return ans;
}
int main() {
    sc(n), sc(w);
    for (int i = 1; i <= n; ++i) {
        sc(a);
        if (!a)
            ++zero;
        else
            update(a, 1LL);
        int x = max(1, i * w / 100);
        printf("%d ", getans(x));
    }
    return 0;
}

感谢朝阳大佬的hack

方格取数（number）

因为不走回头路，拆解成下右+上右两种方案，然后比较最优即可。

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
using namespace std;
const int maxn = 1e3 + 7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int g[maxn][maxn], f[maxn][maxn], a[maxn][maxn];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) sc(a[i][j]);
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++) g[i][j] = f[i][j] = -INF;
    f[1][1] = a[1][1];
    for (int j = 1; j <= m; j++) {    //列
        for (int i = 1; i <= n; i++)  //行
            g[i][j] = f[i][j] =
                max(f[i][j], f[i][j - 1] + a[i][j]);  //从左边走过来
        for (int i = 1; i <= n; i++)
            f[i][j] = max(f[i][j], f[i - 1][j] + a[i][j]);  //从上面走过来
        for (int i = n - 1; i >= 1; i--)
            g[i][j] = max(g[i][j], g[i + 1][j] + a[i][j]);  //从下面走过来
        for (int i = 1; i <= n; i++) f[i][j] = max(g[i][j], f[i][j]);
    }
    cout << f[n][m] << endl;
    return 0;
}