昨天见到的题都好难，就写了一题签到，双向搜索，还是我做过的，然后就早早挂机了，这题今天再看就挺简单的，感觉亏了。

H Cutting Bamboos

思路:

砍$x$次竹子砍下来的高度和很容易求，设为$K$，二分答案$mid$,利用主席树求区间内大于$mid$的竹子的个数$cnt$以及这些竹子的高度之和$s$。$s-cnt * mid$既是前$x$次砍下来的竹子的高度，根据其与$k$的关系调整上下界二分即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int M = 1e5 + 10;
#define eps 1e-7
typedef pair<int, int> P;
int n, q, a[N],  root[N],tot;
ll sum[N];
double avg;
struct tree{
    int lc, rc,cnt;
    ll sum;
}T[M << 6];
ll s;
int cnt;
void insert(int l, int r, int &cur, int pre, int pos)
{
    T[++tot] = T[pre];
    cur = tot;
    T[cur].cnt++;
    T[cur].sum += pos;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) insert(l, mid, T[cur].lc, T[pre].lc, pos);
    else insert(mid + 1, r, T[cur].rc, T[pre].rc, pos);
}
void query(int l, int r, int x, int y, int k)
{
    if (r <= k){ cnt += T[y].cnt - T[x].cnt; s += T[y].sum - T[x].sum; return; }
    int mid = (l + r) >> 1;
    if (k <= mid){
        query(l, mid, T[x].lc, T[y].lc, k);
    }
    else{
        cnt += T[T[y].lc].cnt - T[T[x].lc].cnt;
        s += T[T[y].lc].sum - T[T[x].lc].sum;
        query(mid + 1, r, T[x].rc, T[y].rc, k);
    }
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] + a[i];
        insert(0, M - 10, root[i], root[i - 1], a[i]);
    }
    int l, r, x, y;
    while (q--)
    {
        scanf("%d%d%d%d", &l, &r, &x, &y);
        double  k = (sum[r] - sum[l - 1])*1.0 / y*x;
        double L = 0, R = 100000;
        while (R - L > eps)
        {
            double mid = (R + L) / 2;
            cnt = 0, s = 0;
            query(0, M - 10, root[l - 1], root[r], mid);//注意mid可能为0，要从0开始
            cnt = r - l + 1 - cnt;
            s = sum[r] - sum[l - 1] - s;
            if (s*1.0-mid*cnt>=k) L = mid;
            else R = mid;
        }
        printf("%.7f\n", L);
    }
    return 0;
}

D Knapsack Cryptosystem

直接上代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (1 << 22) + 4;
ll w, ans[N];
int n, mid,tot;
bool f;
vector<int> g[N];
map<ll, int> mp;
int res[50];
struct node{
    ll val;
    int pos;
    bool operator<(const node&o)const{
        return val>o.val;
    }
}a[50];
vector<int> gg;
void dfs(int step, ll sum)
{
    if (step > mid)
    {
        ans[++tot] = sum;
        g[tot] = gg;
        mp[sum] = tot;
        if (sum == w)
        {
            for (auto i : gg)
                res[i] = 1;
            for (int i = 1; i <= n; i++)
                printf("%d", res[i]);
            exit(0);
        }
        return;
    }
    dfs(step + 1, sum);
    if (sum + a[step].val <= w)
    {
        gg.push_back(a[step].pos);
        dfs(step + 1, sum + a[step].val);
        gg.pop_back();
    }
}
void solve(ll sum)
{
    if (sum + ans[1] > w) return;
    int idx = lower_bound(ans + 1, ans + tot + 1, w - sum) - ans ;
    if (ans[idx] == w - sum) {
        f = true;
    }
    if (f)
    {
        int id = mp[w - sum];
        for (auto i : g[id])
            res[i] = 1;
        for (auto i : gg)
            res[i] = 1;
        for (int i = 1; i <= n; i++)
            printf("%d", res[i]);
        exit(0);
    }
}
 
void dfs2(int step, ll sum)
{
    if (f) return;
    if (step == n + 1)
    {
        solve(sum);
        return;
    }
    dfs2(step + 1, sum);
    if (sum + a[step].val <= w)
    {
        gg.push_back(a[step].pos);
        dfs2(step + 1, sum + a[step].val);
        gg.pop_back();
    }
}
int main()
{
    cin >> n >> w;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i].val);
        a[i].pos = i;
    }
    if (n == 1)
    {
        puts("1");
    }
    else if (n == 2)
    {
        if (a[1].val == w){
            puts("10");
        }
        else if (a[2].val == w){
            puts("01");
        }
        else{
            puts("11");
        }
    }
    else
    {
        sort(a + 1, a + n + 1);
        mid = n / 2 + 1;
        dfs(1, 0);
        gg.clear();
        sort(ans + 1, ans + tot + 1);
        tot = unique(ans + 1, ans + tot + 1) - ans - 1;
        dfs2(mid + 1, 0);
    }
     
    return 0;
}