wap建站教程_烟台网站建设平台_外贸网站建站_国际军事新闻今日头条

A - Orders

按照交付时间从小到大排序，看上次交付和这次交付之间过了多少天，得到新加工出的数量，每次判断即可。

#include <bits/stdc++.h>
#define A 100010using namespace std;
typedef long long ll;
struct node {ll a, b;friend bool operator < (const node x, const node y) {return x.a < y.a;}
}e[A];
int n, k;int main(int argc, char const *argv[]) {int T; cin >> T;while (T--) {cin >> n >> k;for (int i = 1; i <= n; i++) cin >> e[i].a >> e[i].b;sort(e + 1, e + n + 1);ll sum = 0; ll now = 0; bool f = 0;for (int i = 1; i <= n; i++) {sum += k * (e[i].a - now);if (sum - e[i].b < 0) {f = 1;break;}sum -= e[i].b;now = e[i].a;}puts(f ? "No" : "Yes");}
}

B - Building Company

员工不是消耗品，自然是越多越好，因为能承接更多的工程。所以可以不断遍历所有工程，只要能承接就接下，承接完一个工程后会给一定数量的员工，得到这些员工后就可以承接更多的工程。直到在某一次遍历中没有工程可以承接为止。但是工程数量n为105，复杂度无法接受。
当我们完成一个工程得到一定数量的员工后，我们只需要考虑新添加的员工可能满足的工程即可。可以用优先队列来维护每项工程还有多少条件没有满足，由于员工编号的值域很大，所以需要使用map；使用一个队列维护满足条件的工程，完成工程后将其从队列中取出。
处理完输入后，先遍历一遍员工，将初始员工就能完成的工程放入队列中。接着处理队列中的工程，每完成一个工程，就将员工数量加上完成其给的奖励，用更新后的员工数量看还有没有能完成的工程。

#include <bits/stdc++.h>
#define A 100010
#define P pair<int, int>using namespace std;
typedef long long ll;
// 对应编号的员工完成second工程需要first人
map<int, priority_queue<P, vector<P>, greater<P> > > req;
// 初始条件下key类员工有value人
map<int, ll> peo;
// 队列存储可以完成的工程
queue<int> q;
// 第i项工程完成后可以给的员工种类和数量
vector<P> reward[A];
int g, t[A], u[A], n, m[A], a, b, k, ans;int main(int argc, char const *argv[]) {cin >> g;for (int i = 1; i <= g; i++) {cin >> t[i] >> u[i];peo[t[i]] = u[i];}cin >> n;for (int i = 1; i <= n; i++) {cin >> m[i];if (m[i] == 0) q.push(i);for (int j = 1; j <= m[i]; j++) {cin >> a >> b;req[a].push(make_pair(b, i));}cin >> k;for (int j = 1; j <= k; j++) {cin >> a >> b;reward[i].push_back(make_pair(a, b));}}for (int i = 1; i <= g; i++) {auto &tmp = req[t[i]];while (!tmp.empty()) {P fr = tmp.top();if (fr.first > peo[t[i]]) break;tmp.pop();if (--m[fr.second] == 0) q.push(fr.second);}}while (!q.empty()) {int fr = q.front(); q.pop();for (auto i : reward[fr]) {peo[i.first] += i.second;auto &tmp = req[i.first];while (!tmp.empty()) {P fr2 = tmp.top();if (fr2.first > peo[i.first]) break;tmp.pop();if (--m[fr2.second] == 0) q.push(fr2.second);}}ans++;}cout << ans << endl;
}

D - Fast and Fat

让最慢的速度最大，题意符合二分的单调性。
假设我们二分出来一个最慢速度$x$：

• 对于$v_i<x$的人，他是一定要被别人搬着跑的，在这些人里体重越大的越难搬。
• 对于$v_i\ge x$的人，他可以搬着别人跑，假设他搬的人是$j$，那么必须满足$v_i-(w_j-w_i)>x$（$w_j<w_i$时一定成立，所以已经考虑在内），移项得到$v_i+w_i-x>w_j$，也就是说他最大可以搬重量为$v_i+w_i-x$的人，$v_i+w_i$最大的人就是最能搬的那一个。

所以$check$的时候让最能搬的那一个去搬$v_i<x$的人里重量最大的，如果能搬动就匹配成功，然后在剩下的里继续找最能搬的和重量最大的，这个可以用优先队列（大根堆）来实现。如果出现最能搬的搬不动重量最大的，那么这个答案$x$就无法满足。
最后判断$v_i<x$的人是不是都被别人搬走了。

#include <bits/stdc++.h>
#define A 100010using namespace std;
struct node {int v, w;friend bool operator < (const node a, const node b) {return a.v < b.v;}
}e[A];
int n;
bool check(int x) {priority_queue<int> vw, w;for (int i = 1; i <= n; i++)if (e[i].v >= x) vw.push(e[i].v + e[i].w);else w.push(e[i].w);while (!vw.empty() and !w.empty())if (vw.top() - w.top() >= x) vw.pop(), w.pop();else return false;return w.empty();
}int main(int argc, char const *argv[]) {int T; cin >> T;while (T--) {cin >> n;for (int i = 1; i <= n; i++) cin >> e[i].v >> e[i].w;sort(e + 1, e + n + 1);int l = 1, r = 1e9;while (l <= r) {int m = (l + r) >> 1;if (check(m)) l = m + 1;else r = m - 1;}cout << l - 1 << endl;}
}

G - Matching

对于式子$i-j=a_i-a_j$，移项得$i-a_i=j-a_j$，将$i-a_i$相同的$i$放到同一个集合里，这个集合的任意两个点之间有连边。题目要求选出的任意两条边没有公共的节点，也就是说一个点只能出现一次，其贡献为$a_i$。题目要求贡献最大，我们对这些集合分别操作，因为集合之间互不影响（集合之内才有连边）。由于拿出两个点才能产生贡献，所以我们将这些点的贡献从大到小排序后，从集合中两个两个地拿出点，直到某个点的贡献小于$0$。
这里有一个边界情况，当$a_i>0$且$a_{i+1}<0$，第$i$个元素为取出的第一个元素时，若$a_i+a_{i+1}>0$，则把这两个点也取上，然后$break$。

#include <bits/stdc++.h>
#define A 100010using namespace std;
typedef long long ll;
int n;
ll a[A];
map<ll, set<int> > m;int main(int argc, char const *argv[]) {int T; cin >> T;while (T--) {m.clear();cin >> n;for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]);m[i - a[i]].insert(i);}ll sum = 0;for (auto i : m) {ll x = 0;multiset<ll, greater<ll> > s;for (auto j : i.second) s.insert(a[j]);bool f = 0; ll ss = 0;for (auto j : s) {if (j >= 0 and f) x += (ss + j), ss = 0, f = 0; // 第二个元素else if (j >= 0 and !f) ss += j, f = 1; // 第一个元素else if (j < 0 and f and j + ss > 0) { // 边界x += (j + ss);break;}}if (x > 0) sum += x;}printf("%lld\n", sum);}
}

H - Three Dice

枚举三个骰子的所有可能情况，数组值为$0$表示红色的$1$和$4$，数组值为$1$表示黑色的$2、3、5、6$。

#include <bits/stdc++.h>using namespace std;
int a, b;
int c[7] = {0, 0, 1, 1, 0, 1, 1}, d[2];int main(int argc, char const *argv[]) {cin >> a >> b;for (int i = 1; i <= 6; i++)for (int j = 1; j <= 6; j++)for (int k = 1; k <= 6; k++) {d[0] = 0; d[1] = 0;d[c[i]] += i; d[c[j]] += j; d[c[k]] += k;if (a == d[0] and b == d[1]) return puts("Yes") & 0;}puts("No");return 0;
}

J - Not Another Path Query Problem

对于整数$a$和$b$，$a\&b\le max(a,b)$，也就是一个数与另一个数相与之后，结果一定不会变大。如果我们找的路径的相与值大于等于$V$，那路径上的每一个点一定都不能小于$V$，但是即使都比$V$大，相与之后的结果也不一定能大于等于$V$。
假设$V$为$38$，其二进制为$100110$，点$1$到$2$有一条权值为$40(101000)$的边，点$2$到$3$有一条权值为$48(110000)$的边，这两条边的相与值为$32<m$。但如果点$2$到点$3$的边的权值为$44(101100)$，这两条边有一个公共二进制前缀$101$，只要其它要加进来的边也有一个共同的前缀$101$，不用管后面的二进制是$0$是$1$，那就还能保证相与的值大于$V$。
我们记录下$V$的每一位二进制的值，在输入边时，也将边权进行二进制分解，从高位到低位进行枚举。如果边权的某一位是$1$而$V$是$0$，说明这条边的权值比$V$大，我们在这一位上记下这条边（将这条边的两个点加入这一位的并查集，在同一并查集内代表两点连通）；如果边权的某一位是$0$而$V$是$1$，那后面就再也不可能出现公共前缀能大于$V$了，直接$break$。
在查询时，假设要查询的两个点为$a$和$b$，从二进制的高位到低位枚举，如果在某一位上$a$和$b$在同一个并查集内，那么就是有一条路径能满足相与的值大于$V$，因为这个并查集内的所有点有一个大于$V$的公共前缀。
上面只是判断了大于$V$的路径，等于$V$的路径没有考虑进去，因为每一位都相同是不会被加入并查集的，但是这个路径的相与值等于$V$，是合法的，需要单独判断一下，题目中$V<2^{60}$，也就是$V$的二进制到不了第$60$位，所以我们把等于$V$的路径放到第$60$位上去单独判断。

#include <bits/stdc++.h>
#define A 100010using namespace std;
typedef long long ll;
int fa[A][61], n, m, q, a, b, d[A];
ll V, c;
int find(int x, int v) {return x == fa[x][v] ? x : (fa[x][v] = find(fa[x][v], v));}
void merge(int x, int y, int v) {int fx = find(x, v), fy = find(y, v);if (fx == fy) return;fa[fx][v] = fy;
}int main(int argc, char const *argv[]) {cin >> n >> m >> q >> V;for (int i = 1; i <= n; i++)for (int j = 0; j <= 60; j++)fa[i][j] = i;for (int i = 59; i >= 0; i--) d[i] = ((V >> i) & 1);for (int i = 1; i <= m; i++) {scanf("%d%d%lld", &a, &b, &c);if ((c & V) == V) merge(a, b, 60);for (int j = 59; j >= 0; j--)if (!d[j] and ((c >> j) & 1)) merge(a, b, j);else if (d[j] and !((c >> j) & 1)) break;}while (q--) {scanf("%d%d", &a, &b);bool f = 0;for (ll i = 60; i >= 0; i--)if (find(a, i) == find(b, i)) {f = 1;break;}puts(f ? "Yes" : "No");}
}

L - Puzzle: Sashigane

从黑色方格开始向外扩展，每次通过添加一个两边相等的$L$构成一个正方形，这样不断构造正方形就一定可以得到一个解，并且$L$的个数为$n-1$。$dfs$记录这个正方形的左上角和右下角坐标。

#include <bits/stdc++.h>using namespace std;
int n, bi, bj;
void dfs(int x1, int y11, int x2, int y2, int len) {if (len == n) return;if (x1 > 1 and y11 > 1) { // 左上x1--; y11--;cout << x1 << " " << y11 << " " << len << " " << len << endl;dfs(x1, y11, x2, y2, len + 1);}else if (x1 > 1 and y2 < n) { // 右上x1--; y2++;cout << x1 << " " << y2 << " " << len << " " << -len << endl;dfs(x1, y11, x2, y2, len + 1);}else if (x2 < n and y11 > 1) { // 左下x2++; y11--;cout << x2 << " " << y11 << " " << -len << " " << len << endl;dfs(x1, y11, x2, y2, len + 1);}else { // 右下x2++; y2++;cout << x2 << " " << y2 << " " << -len << " " << -len << endl;dfs(x1, y11, x2, y2, len + 1);}
}int main(int argc, char const *argv[]) {cin >> n >> bi >> bj;if (n == 1) return puts("Yes\n0") & 0;cout << "Yes\n" << n - 1 << endl;dfs(bi, bj, bi, bj, 1);
}

后来发现$dfs$有些多余，本质就是做$n-1$次，只需要一条路径，所以可以直接$for$循环解决。

#include <bits/stdc++.h>using namespace std;
int n, bi, bj;int main(int argc, char const *argv[]) {cin >> n >> bi >> bj;if (n == 1) return puts("Yes\n0") & 0;int x1 = bi, y11 = bj, x2 = bi, y2 = bj;cout << "Yes\n" << n - 1 << endl;for (int len = 1; len < n; len++)if (x1 > 1 and y11 > 1) {x1--; y11--;cout << x1 << " " << y11 << " " << len << " " << len << endl;}else if (x1 > 1 and y2 < n) {x1--; y2++;cout << x1 << " " << y2 << " " << len << " " << -len << endl;} else if (x2 < n and y11 > 1) {x2++; y11--;cout << x2 << " " << y11 << " " << -len << " " << len << endl;} else {x2++; y2++;cout << x2 << " " << y2 << " " << -len << " " << -len << endl;}
}