The 13th Shandong ICPC Provincial Collegiate Programming Contest
The 13th Shandong ICPC Provincial Collegiate Programming Contest
A. Orders
题意：有n个订单， 每日可生产k个产品，每个订单给出交付日和交付数量，是否能完成所有订单。
思路：按照交付日期进行排序，然后记录当前累计的产品数，能交付就交付，否则直接输出NO。
AC code：
void solve() {
int n, k; cin >> n >> k;
vector<PII> q(n);
for (int i = 0; i < n; i ++) {
cin >> q[i].first >> q[i].second;
}
sort(q.begin(), q.end());
int now = 0, last = 0;
for (int i = 0; i < n; i ++) {
now += (q[i].first - last) * k;
if (now >= q[i].second) now -= q[i].second, last = q[i].first;
else {
cout << "No" << endl;
return;
}
}
cout << "Yes" << endl;
}
B. Building Company
题意：
当前公司有g种员工，给出每种员工的编号以及数量；
现在需要承接n个项目，每种项目给出所需的m种员工编号以及所需数量；
如果当前公司员工数大于等于所需的各种员工数，则完成该项目，然后会有k种员工及相应数量加入公司；
每个项目最多完成一次，现在计算最多可以完成多少项目。
思路：
- 首先记录当前公司中每种员工的数量；
- 对于每项工程，记录第i项工程缺失的员工种类数，如果缺失数为0即当前可以完成该项目则存入一个队列中；
- 对于每种员工，若第i个项目缺少j种员工，则在第j种员工后记录该项目；
- 然后遍历当前队列，每次取出的即为当前可以完成的项目，然后遍历完成该项目可以获得的j种员工，再对缺少该种员工的项目进行遍历，若有了新增员工的当前项目可以满足，则项目缺失数–，项目缺失数为0则压入队列；
- 存取每种员工所需公司时可以用小根堆的优先队列来存取，当出现大于当前员工数时直接break；
AC code：
void solve() {
unordered_map<int, int> ump;
int g; cin >> g;
for (int i = 0; i < g; i ++) {
int t, u; cin >> t >> u;
ump[t] += u;
}
int n; cin >> n;
int cnt = 0;
queue<int> qq; //存完成的
map<int, int> res; //每个项目差的
map<int, vector<PII>> b;
map<int, priority_queue<PII, vector<PII>, greater<PII>>> mp;
for (int i = 0; i < n; i ++) {
int tt = 0, k1, k2;
cin >> k1;
while (k1 --) {
int u, v; cin >> u >> v;
if (ump[u] < v) {
tt ++;
mp[u].push({v, i});
} //不够
}
cin >> k2;
while (k2 --) {
int u, v; cin >> u >> v;
b[i].push_back({u, v});
}
if (tt == 0) qq.push(i);
res[i] = tt;
}
int ans = 0;
while (!qq.empty()) {
auto now = qq.front();
ans ++;
qq.pop();
for (auto [x, y] : b[now]) {
ump[x] += y;
while (!mp[x].empty()) {
auto [nd, pp] = mp[x].top();
if (ump[x] >= nd) {
res[pp] -= 1;
mp[x].pop();
if (res[pp] == 0) qq.push(pp);
} else {
break;
}
}
}
}
cout << ans << endl;
}
D. Fast and Fat
题意：跑步比赛，一队有n名队员，给出每名队员的速度以及体重；一个队员可以背着另一个队员，i背j，若j的体重小于i，则对i的速度没有影响，否则i的速度vi - (wj - wi)，若i的速度为负，则i无法背j；
求整体可能的最大速度，团队最慢成员即为团队速度。
思路：
二分团队最小速度，在check函数里将速度慢的人按照重量从大到小存取，然后将符合条件的人按照速度+重量从大到小进行存取，遍历当前不符合条件的人是否都能有人能背并且整体速度符合最小速度。
AC code：
PII q[N];
struct cmp{
bool operator() (const PII a, const PII b) {
return a.first + a.second < b.first + b.second;
}
};
bool check (int aim) {
priority_queue<PII, vector<PII>, cmp> pr;
vector<int> w;
for (int i = 0; i < n; i ++) {
if (q[i].first >= aim){
pr.push(q[i]);
} else {
w.push_back(q[i].second);
}
}
if (pr.size() == n) return true;
if (pr.size() < w.size()) {
return false;
}
sort(w.begin(), w.end(), greater<int>());
for (auto x : w) {
if (!pr.empty()) {
auto [u, v] = pr.top();
pr.pop();
if (u + v - x >= aim) continue;
else {
return false;
}
} else {
return false;
}
}
return true;
}
void solve() {
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> q[i].first >> q[i].second;
}
sort(q, q + n);
int l = 0, r = 2e9;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
E. Math Problem
题意：
给定两个正整数 n和k，你可以执行以下两种类型的运算任意多次(包括零次)：
- 选择一个满足 0<=x<k的整数 x，将n改为k*n+x 。执行一次这个操作需要花费 a 枚金币。每次选择的整数 x可以不同。
- 将 n改为n/k 。执行此操作一次需要花费 b枚金币。
给定正整数 m ，计算将 n 变为 m的倍数所需的最少金币数。请注意， 0 是任何正整数的倍数。
思路：
- 首先一定是先除后乘，才不会覆盖乘的操作，才能最小化使用硬币数；
- 然后枚举除的次数以及乘的次数，当出现符合条件的值时跳出寻找下一可能的操作；
- 枚举乘的操作时，看当前第j次乘后的值，距离最近的比当前值大于等于的m的倍数是否小于k^j，符合则说明当前操作可行；
- 需要注意的是在计算过程中C++会爆longlong，所有我们需要int128来进行存取中间值；
AC code：
ll qmi(int a, int k) {
ll res = 1;
while (k) {
if (k & 1) res = res * a;
a = a * a;
k >>= 1;
}
return res;
}
void solve() {
int n, k, m, a, b; cin >> n >> k >> m >> a >> b;
if (n % m == 0) {
cout << 0 << endl;
return;
}
if (k == 1) {
cout << "-1" << endl;
return;
}
ll now = n;
int ans = 2e18;
for (int i = 0; now > 0; i ++) {
if (i > 0) now /= k;
ll ca = now;
for (int j = 0; ;j ++) {
if (j == 0) {
if (now % m == 0) ans = min(ans, (b * i));
continue;
}
ca *= k;
ll nxt = m * ((ca / m) + (ca % m != 0));
if ((nxt - ca) < (ll)qmi(k, j)) {
ans = min(ans, (b * i + a * j));
break;
}
}
}
cout << ans << endl;
}
G. Matching
题意：
给定一个长度为n的整数序列 ，我们从该序列构建一个无向图G 。更确切地说，对于所有1 <= i,j<=n ，如果 i-j=ai-aj ，则 G中会有一条连接顶点 i和 j 的无向边。这条边的权重为ai+aj 。
请为 G找出一个匹配项，使匹配项中所有边的权重之和最大，并输出这个最大值。
回想一下，无向图的匹配意味着我们从图中选择一些边，使得任意两条边都没有共同的顶点。具体来说，不选择任何边也是匹配。
思路：
- 首先变换一下式子i - ai = j - a[j];
- 然后我们用优先队列存取所有点-权值相等的点，对于每个可以匹配的点取出最大的两个加入到总权值中即为所求；
AC code：
void solve() {
int n; cin >> n;
map<int, priority_queue<int>> mp;
for (int i = 1; i <= n; i ++) {
int x; cin >> x;
mp[i - x].push(x);
}
int cnt = 0;
for (auto [x, y] : mp) {
while (mp[x].size() > 1) {
auto a = mp[x].top(); mp[x].pop();
auto b = mp[x].top(); mp[x].pop();
if (a + b > 0) cnt += a + b;
}
}
cout << cnt << endl;
}
I.Three Dice
题意：略；
思路：枚举即可；
AC code：
void solve() {
int a, b; cin >> a >> b;
for (int x = 1; x <= 6; x ++) {
for (int y = 1; y <= 6; y ++) {
for (int z = 1; z <= 6; z ++) {
int rd = 0, bk = 0;
if (x == 1 || x == 4) rd += x;
else bk += x;
if (y == 1 || y == 4) rd += y;
else bk += y;
if (z == 1 || z == 4) rd += z;
else bk += z;
if (rd == a && bk == b) {
cout << "Yes" << endl;
return;
}
}
}
} cout << "No" << endl;
}
L. Puzzle: Sashigane
题意：在n*n的白色正方形矩阵中，有一个黑色方块，现在需要将除了黑色方块外的所有白色方块用L形覆盖；
思路：围绕黑色方块向外拓即可，n-1次内必成；
AC code：
void solve() {
int n, x, y; cin >> n >> x >> y;
cout << "Yes" << endl;
cout << n - 1 << endl;
int len = 1, t = 1;
int lx = x, ly = y, rx = x, ry = y;
for (int i = 1; i < n; i ++) {
if (lx > 1 && ly > 1) {
lx --, ly --;
cout << lx << ' ' << ly << ' ' << len << ' ' << len << endl;
} else if (rx < n && ry < n) {
rx ++, ry ++;
cout << rx << ' ' << ry << ' ' << -len << ' ' << -len << endl;
} else if (lx == 1 && ry == n) {
cout << rx + t << ' ' << ly - t << ' ' << -len << ' ' << len << endl;
t ++;
} else if (rx == n && ly == 1) {
cout << lx - t << ' ' << ry + t << ' ' << len << ' ' << -len << endl;
t ++;
}
len ++;
}
}
