acm.sgu.ru-[140, 180)

Part 2: $[140, 180)$
acm.sgu.ru@CodeForces

140. Integer Sequences

给定一个行向量 $A,$ 构造列向量 $X$ 使得 $A \times X \equiv B \mod P$。
$P \leq 10000, A_i \leq 10 ^ 9$。

Sol

$\gcd$ 变化时暴力更新,复杂度是 $O(nd(n)) < O(n \log n)$ 的。
注意 $A_i > P$ 的情况。

#include <bits/stdc++.h>
using namespace std;

#define N 105
int n, P, B;
int a[N], X[N], q[10101], fr[10101];

void update(int v, int id) {
    int h = 0, t = 0;
    for (int i = 0; i < P; i++) {
        if (fr[i] != -1) {
            q[t++] = i;
        }
    }
    while (h < t) {
        int x = q[h++];
        int y = (x + v) % P;
        if (fr[y] == -1) {
            fr[y] = id;
            q[t++] = y;
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &P, &B);
    for (int i = 1; i <= n; i++) scanf("%d", a + i), a[i] %= P;
    memset(fr, -1, sizeof fr);
    fr[0] = 0;
    int g = P;
    for (int i = 1; i <= n && fr[B] == -1; i++) {
        int ng = __gcd(g, a[i]);
        if (ng != g) {
            g = ng;
            update(a[i], i);    
        }
    }
    if (fr[B] == -1) return puts("NO") * 0;
    puts("YES");
    int x = B;
    while (x) {
        X[fr[x]] ++;
        x = (x + P - a[fr[x]]) % P;
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", X[i], i == n ? '\n' : ' ');
    }
}

141. Jumping Joe

$$
P_1x_1 – N_1x_1 + P_2x_2 – N_2x_2 = P
P_1 + N_1 + P_2 + N_2 = K
$$ 给定 $x_1, x_2, P, K$,解方程。

Sol

exgcd,然后找找最小的解就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) return x = 1, y = 0, a;
    LL t = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return t;
}

LL a, b, P, K;

void chk(LL x, LL y) {
    LL d = abs(x) + abs(y);
    if (d <= K && d % 2 == K % 2) {
        LL c = (K - d) / 2;
        printf("YES\n%lld %lld %lld %lld\n", c + (x > 0 ? x : 0), c + (x < 0 ? -x : 0), y > 0 ? y : 0, y < 0 ? -y : 0);
        exit(0);
    }
}

int main() {
    cin >> a >> b >> P >> K;
    LL x, y, g = exgcd(a, b, x, y);
    if (P % g) return puts("NO") * 0;
    x *= P / g, y *= P / g;
    LL u = b / g, v = a / g;
    chk(x, y);
    for (LL i = -3, base = x / u; i <= 3; i++) {
        chk(x - (base + i) * u, y + (base + i) * v);
    }
    for (LL i = -3, base = y / v; i <= 3; i++) chk(x + (base + i) * u, y - (base + i) * v);
    puts("NO");
}

142. Keyword

询问最短的没有出现过的子串。

Sol
#include <bits/stdc++.h>
using namespace std;

#define N 500111

unordered_set <int> s;
int n;
char t[N];
bool check(int mid) {
    s.clear();
    for (int i = mid; i <= n; i++) {
        int cur = 0;
        for (int j = 0; j < mid; j++) {
            cur = cur * 2 + (t[i - j] == 'b');
        }
        s.insert(cur);
    }
    return s.size() < (1 << mid);
}

void output(int mid) {
    printf("%d\n", mid);
    for (int i = 0; ; i++) if (!s.count(i)) {
        for (int j = 0; j < mid; j++) {
            putchar('a' + i % 2);
            i /= 2;
        }
        putchar('\n');
        return;
    }
}

int main() {
    scanf("%d%s", &n, t + 1);
    int l = 1, r = min(20, n);
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    check(l);
    output(l);
}

143. Long Live the Queen

询问树上最大权连通块。

Sol
#include <bits/stdc++.h>
using namespace std;

#define N 16111

int n, a[N], c[N];
vector <int> E[N];

void dfs(int x, int y) {
    c[x] = a[x];
    for (auto v : E[x]) if (v != y) {
        dfs(v, x);
        c[x] += max(0, c[v]);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs(1, - 1);
    int ans = -1e9;
    for (int i = 1; i <= n; i++) ans = max(ans, c[i]);
    printf("%d\n", ans);
}

144. Meeting

#include <bits/stdc++.h>
using namespace std;
double X, Y, Z;
int main() {
    scanf("%lf%lf%lf", &X, &Y, &Z);
    double a = (Y - X) * 60;
    printf("%.7lf\n", ((a - Z) / a * 2 + Z / a) * Z / a);
}

145. Strange People

求 $k$ 短简单路,输出方案。

Sol

二分或者 A* 搞搞就好了。然而这题 SPJ 挂了。

146. The Runner

原来刻意卡精度自古有之。

#include <bits/stdc++.h>
using namespace std;

double L;
long long s, ll;
int n;
int main() {
    scanf("%lf%d", &L, &n);
    ll = L * 10000 + 0.5;
    while (n--) {
        long long x, y;
        scanf("%lld%lld", &x, &y);
        s += x * y * 10000;
        s %= ll;
    }
    printf("%.4lf\n", min(s, ll - s) / 10000.);
}

147. Black-white king

棋盘上有两个王要约会,有另一个王要阻止他们。然而那个坏人很憨,要求任意时刻他都在他的起点到当前点的最短路上,路径长度定义为步数。另外两个王会沿着某条最短路见面,见面定义为走到相邻的格子里。三个人依次行动,问坏人是否有可能抓到两个人中的一个,能的话输出最快的有可能的步数;否则输出两个王之间的距离。

Sol

感觉题意没啥营养,就不写题解了。

#include <bits/stdc++.h>
using namespace std;

int n;
int p[3], q[3];

bool inter(int x, int yl, int yr, int i) {
    x -= p[2];
    yl -= q[2], yr -= q[2];
    if (abs(x) == i && (yl <= i && yr >= -i)) return true;
    if (abs(x) <= i && ((yl <= -i && yr >= -i) || (yl <= i && yr >= i))) return true;
    return false;
}
int dis;
bool ok(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n && max(abs(x - p[0]), abs(y - q[0])) + max(abs(x - p[1]), abs(y - q[1])) == dis;
}

int check() {
    dis = abs(p[0] - p[1]);
    int dir = p[0] > p[1] ? -1 : 1;
    int l0, r0, l1, r1;
    l0 = r0 = q[0], l1 = r1 = q[1];
    for (int i = 1; i <= dis / 2 - 1; i++) {
        int p0 = p[0] + dir * i, p1 = p[1] - dir * i;
        if (ok(p0, l0 - 1)) l0--;
        if (ok(p0, r0 + 1)) r0++;
        while (!ok(p0, l0)) l0++;
        while (!ok(p0, r0)) r0--;
        if (inter(p0, l0, r0, i)) return i;
        if (ok(p1, l1 - 1)) l1--;
        if (ok(p1, r1 + 1)) r1++;
        while (!ok(p1, l1)) l1++;
        while (!ok(p1, r1)) r1--;
        if (inter(p1, l1, r1, i)) return i;
    }
    return -1;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < 3; i++) scanf("%d%d", p + i, q + i);
    if ((p[0] == p[2] && q[0] == q[2]) || (p[1] == p[2] && q[1] == q[2])) return puts("YES\n0"), 0;
    if (abs(p[0] - p[1]) < abs(q[0] - q[1])) {
        for (int i = 0; i < 3; i++) swap(p[i], q[i]);
    }
    int ret = check();
    if (ret == -1) printf("NO\n%d\n", abs(p[0] - p[1]) - 1);
    else printf("YES\n%d\n", ret);
}

148. B-Station

每层车站现在有一些水,每层有一个容量上限。如果某层的水超过容量上限则这一层会被破坏掉,水会落入下一层;你也可以选择花费相应的代价炸掉一些层。询问破坏最后一层的最优解。

Sol

开始想了很久,还是被 sez 点了一下我才想通的,我好菜。
首先,我们一定会破坏一个后缀;那么破坏一层有两种方法,第一种是炸掉,第二种是淹没掉。显然,不同的后缀起点会导致每一层是炸还是淹没;而从每一层来观察,只要起点到他的水够了就会淹没,二分一下前缀和一下就没了。

#include <bits/stdc++.h>
using namespace std;
#define N 15111
int n;
int w[N], l[N], p[N], sum[N];
bool vis[N];
vector <int> c[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d%d", w + i, l + i, p + i);
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + w[i];
    for (int i = n; i; i--) {
        int L = 1, R = i;
        while (L < R) {
            int mid = (L + R) / 2;
            if (sum[i] - sum[mid - 1] <= l[i]) R = mid;
            else L = mid + 1;
        }
        c[L].push_back(i);
    }
    int su = 0, ans = 0x3f3f3f3f, id = 0;
    for (int i = 1; i <= n; i++) {
        for (auto v : c[i]) su += p[v];
        if (su < ans) ans = su, id = i;
        su -= p[i];
    }
    for (int i = 1; i <= id; i++) {
        for (auto v : c[i]) vis[v] = 1;
        if (i < id) vis[i] = 0;
    }
    for (int i = 1; i <= n; i++) if (vis[i]) printf("%d\n", i);
}

149. Computer Network

求树上每个点最远点距离。

Sol

传 统 艺 能

#include <bits/stdc++.h>
using namespace std;
#define N 10111
int n, a[N], c[N];
struct edge {
    int v, w;
};
vector <edge> E[N];
void dfs(int x) {
    for (auto v : E[x]) {
        dfs(v.v);
        c[x] = max(c[x], c[v.v] + v.w);
    }
}
void f(int x, int z) {
    a[x] = max(c[x], z);
    int ma = z, sma = -1e9;
    for (auto v : E[x]) { 
        int val = c[v.v] + v.w;
        if (val > ma) sma = ma, ma = val;
        else if (val > sma) sma = val;
    }
    for (auto v : E[x]) {
        int val = c[v.v] + v.w;
        f(v.v, v.w + (val == ma ? sma : ma));
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back({i, v});
    }
    dfs(1);
    f(1, 0);
    for (int i = 1; i <= n; i++) printf("%d\n", a[i]);
}

150. Mr. Beetle II

从 $(x_1, y_1)$ 向 $(x_2, y_2)$ 画一条线,问线经过的第 $n$ 个格子是什么,无解输出无解。

Sol

暴力可过,但是我不想写暴力。
考虑在较长边(设为 $x$)上二分,这样每个 $x$ 的边对应至多两个 $y$,并且 $mid$ 个 $x$ 有 $$mid + \lfloor \frac {mid \Delta y } {\Delta x} \rfloor – \frac {mid} {\Delta x / \gcd (\Delta x, \Delta y)}$$ 个,枚举一下边界就做完了。我交换和调整了符号来减少代码量。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
    int x1, y1, x2, y2, n;
    cin >> x1 >> y1 >> x2 >> y2 >> n;
    if (x1 == x2 || y1 == y2) return puts("no solution") * 0; 
    int dx = x2 - x1, dy = y2 - y1;
    bool negx = 0, negy = 0, sw = 0;
    if (dx < 0) negx = 1, dx = -dx;
    if (dy < 0) negy = 1, dy = -dy; 
    if (dx < dy) sw = 1, swap(dx, dy);
    int g = __gcd(dx, dy);
    int totcell = dx + dy - g;
    if (totcell < n) return puts("no solution") * 0;
    int l = 0, r = dx;
    int xg = dx / g;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        int c = int(mid + (LL)dy * mid / dx - mid / xg);
        if (c < n) l = mid;
        else r = mid - 1;
    }
    int c = int(l + (LL)dy * l / dx - l / xg);
    int yy = int((LL)dy * l / dx);
    vector < pair<int, int> > ans;
    ans.push_back({l, yy});
    if (int((LL)dy * (l + 1) / dx) > yy && ((LL)dy * (l + 1) % dx)) {
        ans.push_back({l, yy + 1});
    }
    int ansx = ans[n - c - 1].first, ansy = ans[n - c - 1].second;
    if (sw) swap(ansx, ansy);
    if (negx) {
        ansx = -ansx - 1;
    }
    if (negy) {
        ansy = -ansy - 1;
    }
    ansx += x1; ansy += y1;
    printf("%d %d\n", ansx, ansy);
}

151. Construct a triangle

构造一个满足从一个顶点 $A$ 出发的两条边 $b, c$ 和中线 $m$ 为给定值的三角形。

Sol

取短边所在的非 $A$ 角,可以发现中线长度关于这个角度是凸的。算角度可能比较麻烦,枚举高的话需要考虑锐角和钝角两种情况。第一种取 $h = 0$ 和 $h = m$ 都太小了但是 $m < (b + c) / 2$ 的情况,可以尝试用第二种构造,否则不用。
BETTER: 把 $A, B$ 固定在 $(0, 0), (c, 0)$,然后就是一个二次方程。

#include <bits/stdc++.h>
using namespace std;

double c, b, m, lp, rp, mp;

double chk1(double h) {
    lp = -sqrt(c * c - h * h);
    rp = sqrt(b * b - h * h);
    mp = (lp + rp) / 2;
    double l = sqrt(mp * mp + h * h);
    return l - m;
}

double chk2(double h) {
    lp = sqrt(c * c - h * h);
    rp = sqrt(b * b - h * h);
    mp = (lp + rp) / 2;
    double l = sqrt(mp * mp + h * h);
    return l - m;
}

int main() {
    cin >> c >> b >> m;
    if (m > (b + c) / 2.) return puts("Mission impossible") , 0;
    double l = 0, r = min(m, min(b, c));
    auto chk = chk1;
    if (chk1(l) < 0 && chk1(r) < 0) chk = chk2;
    for (int t = 0; t < 100; t++) {
        double lmid = (l * 3 + r) / 4, rmid = (l + r * 3) / 4;
        if (chk(lmid) > chk(rmid)) l = lmid;
        else r = rmid;
    }
    if (chk(l) > 0) return puts("Mission impossible"), 0;
    if (chk(0) >= 0) l = 0, swap(l, r);
    else r = min(m, min(b, c));
    for (int t = 0; t < 100; t++) {
        double mid = (l + r) / 2;
        if (chk(mid) > 0) r = mid;
        else l = mid;
    }
    printf("%.5lf %.5lf\n", 0., l);
    printf("%.5lf %.5lf\n", lp, 0.);
    printf("%.5lf %.5lf\n", rp, 0.);
}

152. Making round

#include <bits/stdc++.h>
using namespace std;
#define N 10111
int n;
int a[N], b[N], c[N];
int main() {
    scanf("%d", &n);
    int sum = 0;
    for (int i = 1; i <= n; i++) scanf("%d", a + i), sum += a[i];
    int tot = 100;
    for (int i = 1; i <= n; i++) {
        b[i] = a[i] * 100 / sum;
        if (a[i] * 100 % sum) c[i] = 1;
        tot -= b[i];
    }
    for (int i = 1; i <= n; i++) if (c[i] && tot) b[i]++, tot--;
    for (int i = 1; i <= n; i++) printf("%d%c", b[i], i == n ? '\n' : ' ');
}

153. Playing with matches

给定 $n \leq 10 ^ 9$ 个石子,给定操作集合为一个 $[1, 9]$ 的子集,两人轮流取石子,取到最后一个的输掉,问必胜者。

Sol

一个直观的感受是,sg 函数存在循环节。我最初认为循环节是 $9!$ 的约数,但是是错的。循环节很小,最大的循环节由 4 7 8 取到 $25$, for 一下就行了。
注意网上很多题解假了,循环节可能存在一个第一段不一样的情况,需要特判。Hack:

2
1 2
6 9
6 2
6 9

应该输出

SECOND PLAYER MUST WIN
FIRST PLAYER MUST WIN
#include <bits/stdc++.h>
using namespace std;

const int N = 3000;

int K, n, m;

bool dp[N + 1];
vector <int> a;
int ma;
void work() {
    scanf("%d%d", &n, &m);
    a.clear();
    for (int i = 0; i < m; i++) {
        int x; scanf("%d", &x);
        a.push_back(x);
    }
    dp[1] = 0;
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] == 0;
        for (auto v : a) {
            if (i > v) dp[i] |= dp[i - v] == 0;
        }
    }
    for (int j = 1; ; j++) {
        bool flag = 1;
        for (int i = j + 1; i + j < N; i++){
            if (dp[i] != dp[i + j]) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            puts(dp[n < N ? n : n % j + j] ? "FIRST PLAYER MUST WIN" : "SECOND PLAYER MUST WIN");
            return;
        }
    }
    assert(0);
}

int main() {
    scanf("%d", &K);
    while (K--) work();
}

154. Factorial

输出最小的 $n!$ 末尾 0 的数量为给定值的 $n$,或者 No solution

Sol
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int l = 1, r = 5e8;
    while (l < r) {
        int x = (l + r) / 2;
        int ans = 0;
        for (int y = x / 5; y; y /= 5) {
            ans += y;
        }
        if (ans >= n) r = x;
        else l = x + 1;
    }
    int ans = 0;
    for (int y = l / 5; y; y /= 5) {
        ans += y;
    }
    if (ans != n) puts("No solution");    
    else printf("%d\n", l);
}

155. Cartesian Tree

给定 $(\text{key}, \text{val})$ 构造笛卡尔树。

Sol
#include <bits/stdc++.h>
using namespace std;

#define N 50555

struct Node {
    int key, val, fa, L, R;
    bool operator < (const Node &a) const {
        return key < a.key;
    }
} a[N];

int n;
int id[N];
bool cmp(int x, int y) {
    return a[x].key < a[y].key;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int key, val;
        scanf("%d%d", &key, &val);
        a[i] = {key, val, 0, 0, 0};
        id[i] = i;
    }
    sort(id + 1, id + n + 1, cmp);
    int x = 0;
    for (int i = 1; i <= n; i++) {
        int y = id[i];
        while (x != 0) {
            int fa = a[x].fa;
            if (a[y].val < a[x].val) {
                a[x].R = a[y].L;
                a[a[y].L].fa = x;
                a[y].L = x;
                a[x].fa = y;
                x = fa;
            }
            else {
                break;
            }
        }
        a[y].fa = x;
        a[x].R = y;
        x = y;
    }
    puts("YES");
    for (int i = 1; i <= n; i++) {
        printf("%d %d %d\n", a[i].fa, a[i].L, a[i].R);
    }
}

156. Strange Graph

称满足下列性质的无向连通图是 ‘strange’ 的:

  1. $\forall v \in V, \text{deg}_v \geq 2$.
  2. $\forall v \in V \text{ s.t. deg}_v > 2:$
    • 存在且仅存在一个 $u \in \text{adj}_v, \text{deg}_u = 2$.
    • $\text{adj}_v \backslash u$ 是一个团.

给定一个 strange graph,寻找一条哈密顿回路,或者输出不存在。
$N \leq 10 ^ 4, M \leq 10 ^ 5$

Sol

把高度数的点缩起来,就是求欧拉回路。
输出方案很恶心,我调了很久但是过于弱智,选择了不缩点写法。
读题很重要,这道题少读一个限制就要多写一堆特判。

#include <bits/stdc++.h>
using namespace std;
#define N 10111
int n, m;
int bel[N];
bool vis[N];
vector <int> ans;
list <int> E[N];

void dfs(int x, bool go = 0) {
    vis[x] = 1;
    while (E[x].size()) {
        auto it = E[x].begin();
        int v = *it;
        E[x].erase(it);
        if (!vis[v]) {
            if (bel[x] == bel[v] && !go) {
                dfs(v, 1);
                ans.push_back(v);
            }
            else if (bel[x] != bel[v]){
                dfs(v, 0);
                ans.push_back(v);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) if (!bel[i] && E[i].size() > 2) {
        for (auto v : E[i]) if (E[v].size() > 2) bel[v] = i;
    }
    for (int i = 1; i <= n; i++) if (!bel[i]) {
        bel[i] = i;
        if (E[i].size() & 1) {
            puts("-1");
            return 0;
        }
    }
    dfs(bel[1]);
    ans.push_back(bel[1]);
    for (auto v : ans) printf("%d ", v);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注