Loading... 昨天见到的题都好难，就写了一题签到，双向搜索，还是我做过的，然后就早早挂机了，这题今天再看就挺简单的，感觉亏了。 ## H [Cutting Bamboos](https://ac.nowcoder.com/acm/contest/889/H) ### 思路: 砍$x$次竹子砍下来的高度和很容易求，设为$K$，二分答案$mid$,利用主席树求区间内大于$mid$的竹子的个数$cnt$以及这些竹子的高度之和$s$。$s-cnt * mid$既是前$x$次砍下来的竹子的高度，根据其与$k$的关系调整上下界二分即可。 ### 代码 ```cpp #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](https://ac.nowcoder.com/acm/contest/889/D) 直接上代码 ```cpp #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; } ``` Last modification：August 16th, 2019 at 06:11 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
4 comments
不懂代码，这是在用程序做题吗？
是的
测试
滴！访客卡！请上车的乘客系好安全带，现在是：Thu Sep 05 2019 09:44:17 GMT+0800 (中国标准时间)
嗯嗯！写的不错！（我要看哭了！）