重庆邮电大学第十届程序设计大赛决赛题解报告

A. 锦神与Jin语言

[Easy] [签到题]

按题意模拟即可

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n, fail = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        int s, t;
        scanf("%d%d", &s, &t);
        if(t == 0) {
            if(s < 90) ++fail;
        }else {
            if(s != 100) ++fail;
        }
    }
    if(fail == 0) puts("oqm");
    else printf("%d\n", fail);
}
int main() {
    solve();
    return 0;
}

H. 锦神与Jigo语言

[Easy] [字符串处理]

按题意模拟即可，有一些需要注意的细节。取模的一种方法是使用unsigned类型的溢出，所有运算相当于自动对$2^{32}$取模；另外也可以用unsigned long long手动取模。

#include <bits/stdc++.h>
using namespace std;
void solve() {
    unsigned ans = 1, num = 0;
    int len = 0;
    string str;
    cin >> str;
    str += ' ';
    for(char ch : str) {
        if(isdigit(ch)) {
            num = num*10u + ch - '0';
            ++len;
        }else {
            if(len > 0) {
                ans *= num;
            }
            num = len = 0;
        }
    }
    printf("%u\n", ans);
}
int main() {
    solve();
    return 0;
}

G. 锦神与Jithon语言

[Easy] [排序]

题意：
是否可以通过交换两相邻元素或者取共轭复数，将A变成B

做法：
交换2相邻元素可以实现任意排列，用抽象代数的语言描述即：
相邻对换可以生成n阶置换群，亦即：
$<(1 \space 2), (2 \space 3), ..., (n-1 \space n)> \space = \space S_n$

问题转化为是否存在A到B的完美匹配。
实部相等，虚部相等或互为相反数的两个复数可以匹配。
这不是二分图匹配模板题吗？
只需要将A和B的虚部取绝对值，排序，然后判断A和B是否相等。想一想为什么？

#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 5;
int n;
void solve() {
    scanf("%d", &n);
    vector<pair<int,int> > a(n), b(n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &a[i].first, &a[i].second);
        a[i].second = abs(a[i].second);
    }
    for(int i = 0; i < n; ++i) {
        scanf("%d%d", &b[i].first, &b[i].second);
        b[i].second = abs(b[i].second);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    puts(a == b ? "yes" : "no");
}
int main() {
    solve();
    return 0;
}

F. 锦神与JHJ语言

[Medium] [置换分解] [快速幂]

做法1：
置换可以分解为轮换，长度为$L$的轮换内部的周期是$L-1$，每个单独处理即可。
复杂度 $O(n)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int a[N], r[N], tmp[N], vis[N];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        --a[i];
        r[i] = i;
    }
    for(int i = 0; i < n; ++i) {
        if(vis[i]) continue;
        vector<int> p;
        int x = i;
        while(!vis[x]) {
            p.push_back(x);
            vis[x] = 1;
            x = a[x];
        }
        int len = p.size();
        int v = m%len;
        if(v > 0) {
            for(int j = 0; j < len ; ++j) {
                r[p[j]] = p[(j+v)%len];
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        printf("%d%c", r[i]+1, " \n"[i+1==n]);
    }
    return 0;
}

做法2：
注意到置换的复合（乘法）满足结合律，因此可以写成幂，自然就可以使用快速幂算法。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
int a[N], r[N], tmp[N];
void mul(int *a, int *b) {
    for(int i = 0; i < n; ++i) {
        tmp[i] = b[a[i]];
    }
    memcpy(a, tmp, n*sizeof(int));
}
void solve() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        --a[i];
        r[i] = i;
    }
    for(; m > 0; m >>= 1) {
        if(m&1) {
            mul(r, a);
        }
        mul(a, a);
    }
    for(int i = 0; i < n; ++i) {
        printf("%d%c", r[i]+1, " \n"[i+1==n]);
    }
}
int main() {
    solve();
    return 0;
}

C. 锦神与Jin#语言

[Medium] [计算几何]

与三角形是否相交可以转化为与每一条边是否相交。
只要有一个有效交点即与三角形相交。
有效交点不能位于射线端点和三角形端点。
这里推荐使用直线的参数方程求交点，其参数$t$可以方便判断交点是否有效。
详见参考代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 5;
const double eps = 1e-8;
struct point {
    double x, y;
    void read() { scanf("%lf%lf", &x, &y); }
    point operator +(point rhs) {
        return (point){x+rhs.x, y+rhs.y};
    }
    point operator -(point rhs) {
        return (point){x-rhs.x, y-rhs.y};
    }
    point operator *(double rhs) {
        return (point){x*rhs, y*rhs};
    }
}A, B, C, p, v;
struct line {
    point p, v;
    double ang;
    line() { }
    line(point a, point b) {
        p = a;
        v = b - a;
        ang = atan2(v.y, v.x);
    }
    bool operator < (const line &rhs) const {
        return ang < rhs.ang;
    }
};
double dot(point A, point B) {
    return A.x*B.x + A.y*B.y;
}
double det(point A, point B) {
    return A.x*B.y - A.y*B.x;
}
int sgn(double x) {
    if(x > eps) return 1;
    if(x < -eps) return -1;
    return 0;
}
int line_line_intersection(line a, line b) {
    point u = a.p - b.p;
    double down = det(a.v, b.v);
    if(sgn(down) == 0) return 0;
    double t1 = det(b.v, u)/down;
    double t2 = det(a.v, u)/down;
    /** t
    segment 0~1
    ray     0~inf
    line    -inf~inf
    **/
    if(t1 < eps || t1 > 1 - eps || t2 < eps) return 0;
    else return 1;
}
int point_in_triangle(point p, point A, point B, point C) {
    int t1 = sgn(det(A-p, B-p)), t2 = sgn(det(B-p, C-p)), t3 = sgn(det(C-p, A-p));
    return t1*t2 >= 0 && t2*t3 >= 0;
}
void solve() {
    A.read();
    B.read();
    C.read();
    p.read();
    v.read();
    line L(p, p+v);
    int ans = line_line_intersection(line(A, B), L) | 
              line_line_intersection(line(B, C), L) | 
              line_line_intersection(line(A, C), L);
    puts(ans ? "yes" : "no");
}
int main() {
    solve();
    return 0;
}

D. 锦神与Jin Script语言

[Medium] [状压DP] [期望DP] [容斥原理]

做法1：
一眼状压DP，牢记 概率顺推，期望逆推
用二进制掩码表示当前状态，$0$和$1$表示是否得到这种限定
记 $dp[mask]$ 表示当前状态 $mask$ 到达目标状态 $2^n - 1（即111...11）$ 需要的期望次数
当前状态可以由 $mask$ 中为 $0$ 的地方变为 $1$ 进行转移，即
$\begin{aligned} dp[mask] = 1 + \sum_{mask[j]=0}^{}{dp[mask|(1<<j)]*p[j]} + (1 - \sum_{mask[j]=0}^{}{p[j]})*dp[mask] \end{aligned}$
化简后为：
$\begin{aligned} dp[mask] = \frac{\begin{aligned}1 + \sum_{mask[j]=0}^{}{dp[mask|(1<<j)]*p[j]}\end{aligned}}{\begin{aligned} \sum_{mask[j]=0}^{}{p[j]} \end{aligned}} \end{aligned}$
初始态$dp[2^n-1] = 0$
最终$dp[0]$即是答案

复杂度 $O(n*2^n)$

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
const int N = 16 + 5;
struct point {
    int x, y;
    void read() {
        scanf("%d%d", &x, &y);
    }
    point operator -(const point &rhs) const {
        return (point){x - rhs.x, y - rhs.y};
    }
    pair<int,int> get_k() {
        int g = __gcd(x, y);
        return make_pair(x/g, y/g);
    }
}p[N];
pair<int,int> kp[N][N];
int n, a[N], vis[N];
int l[N], r[N];
int ans;
inline void remove(int u) {
    r[l[u]] = r[u];
    l[r[u]] = l[u];
}
inline void restore(int u) {
    r[l[u]] = u;
    l[r[u]] = u;
}
void dfs(int k) {
    if(k == n) {
        map<pair<int,int>, int> cnt;
        for(int i = 0; i < n; i += 2) {
            ++cnt[kp[a[i]][a[i+1]]];
        }
        int sum = 0;
        for(auto it : cnt) {
            sum += it.second*(it.second - 1)/2;
        }
        ans = max(ans, sum);
        return;
    }
    if(~k&1) {
        int x = r[0];
        a[k] = x;
        remove(x);
        for(int y = r[0]; y <= n; y = r[y]) {
            a[k+1] = y;
            remove(y);
            dfs(k+2);
            restore(y);
        }
        restore(x);
    }
}
void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        p[i].read();
        for(int j = 1; j < i; ++j) {
            kp[i][j] = kp[j][i] = (p[i] - p[j]).get_k();
        }
    }
    ans = 0;
    r[0] = 1;
    for(int i = 1; i <= n; ++i) {
        l[i] = i - 1;
        r[i] = i + 1;
    }
    dfs(0);
    printf("%d\n", ans);
}
int main() {
    solve();
    return 0;
}

做法2：
利用容斥原理，容易得到，抽卡次数超过 $k$ 次才集齐所有限定的概率为

$P(N>k)=\sum{(1-p_i)^k}-\sum{(1-p_i-p_j)^k}+...$

那么，抽卡次数为 $k$ 时恰好集齐所有限定的概率为

$\begin{equation} \begin{aligned} P(N=k) &= P(N>k-1) - P(N>k) \\ &= \sum{p_i(1-p_i)^{k-1}}-\sum{(p_i+p_j)(1-p_i-p_j)^{k-1}}+... \end{aligned} \end{equation}$

于是，期望为
$\begin{equation} \begin{aligned} E(N) &= \sum_{k=1}^{\infty}k \times P(N=k) \\ &= \sum{\sum_{k=1}^{\infty}{k\times p_i(1-p_i)^{k-1}}} - \sum{\sum_{k=1}^{\infty}{k\times (p_i+p_j)(1-p_i-pj)^{k-1}}}+... \end{aligned} \end{equation}$

容易发现，每一项内部的求和都满足形式

$\begin{equation} \begin{aligned} \sum_{k=1}^{\infty}k \times p(1-p)^{k-1} = p\sum_{k=1}^{\infty}k(1-p)^{k-1} \end{aligned} \end{equation}$

求解该式是很经典的级数问题（高中生都会错位相减），大学生的做法通常是

$\begin{aligned} \sum_{k=0}^{\infty}{x^k}=\frac{1}{1-x}，两边对x求导得 \end{aligned}$
$\begin{aligned} \sum_{k=0}^{\infty}{kx^{k-1}}=\frac{1}{(1-x)^2}，即 \end{aligned}$
$\begin{aligned} \sum_{k=1}^{\infty}{kx^{k-1}}=\frac{1}{(1-x)^2} \end{aligned}$

所以，令 $x=1-p$ 即得到
$\begin{equation} \begin{aligned} p\sum_{k=1}^{\infty}k(1-p)^{k-1} = p \times \frac{1}{p^2} = \frac{1}{p} \end{aligned} \end{equation}$

所以
$\begin{equation} \begin{aligned} E(N) &= \sum{\frac{1}{p_i}} - \sum{\frac{1}{p_i+p_j}}+... \end{aligned} \end{equation}$

时间复杂度 $O(n*2^n)$

#include <bits/stdc++.h>
using namespace std;
const int N = 10 + 5;
int n;
double p[N];
double formula() {
    double ans = 0;
    for(int i = 1; i < 1<<n; ++i) {
        int flag = -1;
        double sum = 0.0;
        for(int j = 0; j < n; ++j) {
            if(i&(1<<j)) {
                flag = -flag;
                sum += p[j];
            }
        }
        ans += flag/sum;
    }
    return ans;
}
void solve() {
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) {
        scanf("%lf", &p[i]);
    }
    printf("%.12f\n", formula());
}
int main() {
    solve();
    return 0;
}

B. 锦神与Jin++语言

[Medium] [搜索]

直接爆搜就能过的水题
随便分析一下：
在地图角落只有$1$种走法，边上有$2$种走法，中间有$3$种。
在$n*m=30$ 的规模下，使得中间的格子数最多的是 $5*6=30$。
此时有$4$个角，$14$个边，$12$个中间，走法数大约为 $2^{14} * 3^{12} = 8.7 * 10^9$
这不是T了吗？
事实上，因为走过的要删掉，搜到后面，很多方向都无法走，方案数会减少不少。
大力出奇迹。

复杂度 $O(能过)$

#include <bits/stdc++.h>
using namespace std;
const int N = 32;
int n, m;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
char s[N][N];
int vis[N][N];
int cnt;
int sx, sy, tx, ty;
inline int in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
int get_next(int x, int y, int d, int &nx, int &ny) {
    nx = x;
    ny = y;
    while(true) {
        nx += dx[d];
        ny += dy[d];
        if(!in(nx, ny)) {
            return 0;
        }
        if(!vis[nx][ny] && s[nx][ny] != '#') {
            return 1;
        }
    }
}
vector<int> path;
int dfs(int x, int y, int dir) {
    if(x == tx && y == ty) {
        if(path.size() == cnt - 1) {
            return 1;
        }
        return 0;
    }
    vis[x][y] = 1;
    for(int d = 0; d < 4; ++d) {
        if((d + 2)%4 == dir) continue;
        int nx, ny;
        if(get_next(x, y, d, nx, ny)) {
            path.push_back(d);
            if(dfs(nx, ny, d)) {
                return 1;
            }
            path.pop_back();
        }
    }
    vis[x][y] = 0;
    return 0;
}
void solve() {
    scanf("%d%d", &n, &m);
    cnt = 0;
    for(int i = 0; i < n; ++i) {
        scanf("%s", s[i]);
        for(int j = 0; j < m; ++j) {
            if(s[i][j] != '#') {
                ++cnt;
            }
            if(s[i][j] == 'S') {
                sx = i;
                sy = j;
            }else if(s[i][j] == 'T') {
                tx = i;
                ty = j;
            }
        }
    }
    path.clear();
    memset(vis, 0, sizeof(vis));
    if(dfs(sx, sy, 4)) {
        static const string ch = "URDL";
        puts("yes");
        for(int u : path) {
            printf("%c", ch[u]);
        }
        puts("");
    }else {
        puts("no");
    }
}
int main() {
    solve();
    return 0;
}

E. 锦神与objective-Jin语言

[Hard] [线段树] [字符串Hash]

题意：
$1 \sim n$的排列 $A\{n\}$里是否存在三元组$(i,j,k)$满足$0 < i < j < k \leq n$ 且 $A_i + A_k = 2 * A_j$。即是否存在长度为3的子序列是等差数列。

做法：
考虑固定一个$A_j$，在左边找 $A_i$，右边找 $A_k$
如果将某个数字是否出现在$A_j$左边存为一个$01$字符串，$1$表示出现过，那么判断是否存在能与$A_j$组成等差数列的$A_i$和$A_j$，就可以转化为，判断以$A_j$为中心的字符串是否是回文串。想一想为什么？
这是因为，如果一对数值上满足条件的$A_i$和$A_k$同时在$A_j$的一侧，那么要么同为$0$，要么同为$1$。反之，如果一个是$0$一个是$1$，则A_i$和$A_k$必然一边一个，可以找到这样的三元组。

现在要实现修改字符和判断一个子串是不是回文串。
这是线段树（或树状数组）维护hash的模板题。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 100000 + 5;
const ULL base = 131;
int T;
int n, a[N];
ULL f[N];
void init() {
    f[0] = 1;
    for(int i = 1; i < N; ++i) {
        f[i] = f[i-1]*base;
    }
}
#define root 1,n,1
#define lson l,m,o<<1
#define rson m+1,r,o<<1|1
ULL h1[N*4], h2[N*4];
inline void push_up(int o, int L) {
    h1[o] = h1[o<<1]*f[(L>>1)] + h1[o<<1|1];
    h2[o] = h2[o<<1|1]*f[L-(L>>1)] + h2[o<<1];
}
void build(int l, int r, int o) {
    if(l == r) {
        h1[o] = h2[o] = 0;
        return;
    }
    int m = l + r >> 1;
    build(lson);
    build(rson);
    push_up(o, r-l+1);
}
void modify(int p, int l, int r, int o) {
    if(l == r) {
        h1[o] = h2[o] = 1;
        return;
    }
    int m = l + r >> 1;
    if(p <= m) modify(p, lson);
    else modify(p, rson);
    push_up(o, r-l+1);
}
ULL query1(int L, int R, int l, int r, int o) {
    if(L <= l && R >= r) {
        return h1[o];
    }
    int m = l + r >> 1;
    if(L > m) return query1(L, R, rson);
    else if(R <= m) return query1(L, R, lson);
    else return query1(L, m, lson)*f[R-m] + query1(m+1, R, rson);
}
ULL query2(int L, int R, int l, int r, int o) {
    if(L <= l && R >= r) {
        return h2[o];
    }
    int m = l + r >> 1;
    if(L > m) return query2(L, R, rson);
    else if(R <= m) return query2(L, R, lson);
    else return query2(L, m, lson) + query2(m+1, R, rson)*f[m-L+1];
}
void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    build(root);
    int flag = 0;
    for(int i = 1; i <= n; ++i) {
        int x = a[i];
        int len = min(x-1, n-x);
        int l = x - len, r = x + len;
        if(l < r && query1(l, r, root) != query2(l, r, root)) {
            flag = 1;
            break;
        }
        modify(x, root);
    }
    puts(flag ? "yes" : "no");
}
int main() {
    init();
    solve();
    return 0;
}

I. 锦神与Kotjin语言

[Hard] [2-SAT]

每个发射器只有2种选择，是典型的2-SAT模型
对每个格子，往4个方向寻找最近的发射器'S'（遇墙则停）
如果该格子是'S'，则4个方向上的发射器不能照到它
如果该格子是'.'，按4个方向上的发射器数量讨论：
0: gg
1: 钦定照
2: 两者选1
3: 同一直线上的两个不能照，单独的那个钦定照
4: gg
显然所有需要满足的条件只有2类：
$x = v1 \space or \space y = v2 \\ x = v1$

复杂度 $O(n*m*max(n,m))$

#include <bits/stdc++.h>
using namespace std;
const int N = 50 + 5;
int T;
int n, m;
char s[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int id[N][N], C;
inline int in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
struct TwoSat {
    static const int M = N*N*2;
    vector<int> G[M];
    int mark[M], S[M], C, n;
    void init(int _n) {
        n = _n;
        for(int i = 0; i < n+n; i++) G[i].clear();
        memset(mark, 0, sizeof(mark));
        C = 0;
    }
    void clear() {
        while(C) mark[S[--C]] = 0;
    }
    void add_or(int x, int xval, int y, int yval) { /** x or y ==> !x -> y and !y -> x **/
        x = x<<1|xval;
        y = y<<1|yval;
        G[x^1].push_back(y);
        G[y^1].push_back(x);
    }
    void assign(int x, int xval) { /** x = val ==> !x -> x **/
        x = x<<1|xval;
        G[x^1].push_back(x);
    }
    int dfs(int u) {
        if(mark[u^1]) return 0;
        if(mark[u]) return 1;
        mark[u] = 1;
        S[C++] = u;
        for(int v : G[u]) {
            if(!dfs(v)) return 0;
        }
        return 1;
    }
    int solve() {
        for(int i = 0; i < n+n; i += 2) {
            if(mark[i] || mark[i+1]) continue;
            C = 0;
            if(!dfs(i)) {
                clear();
                if(!dfs(i+1)) return 0;
            }
        }
        return 1;
    }
}solver;
int detect(int x, int y, int d) {
    while(1) {
        x += dx[d];
        y += dy[d];
        if(!in(x, y) || s[x][y] == '#') return -1;
        if(s[x][y] == 'S') return id[x][y];
    }
    return -1;
}
void solve() {
    C = 0;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) {
        scanf("%s", s[i]);
        for(int j = 0; j < m; ++j) {
            if(s[i][j] == 'S') {
                id[i][j] = C++;
            }else {
                id[i][j] = -1;
            }
        }
    }
    solver.init(C);
    int ok = 1;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(s[i][j] == '.') {
                int a[4], cnt = 0;
                for(int k = 0; k < 4; ++k) {
                    a[k] = detect(i, j, k);
                    if(a[k] != -1) {
                        ++cnt;
                    }
                }
                if(cnt == 0 || cnt == 4) {
                    ok = 0;
                    break;
                }
                if(cnt == 1) {
                    for(int k = 0; k < 4; ++k) {
                        if(a[k] != -1) {
                            solver.assign(a[k], k&1);
                        }
                    }
                }
                if(cnt == 2) {
                    int p = 0, v[2];
                    for(int k = 0; k < 4; ++k) {
                        if(a[k] != -1) {
                            v[p++] = k;
                        }
                    }
                    if(v[0] == (v[1]^2)) {
                        ok = 0;
                        break;
                    }else {
                        solver.add_or(a[v[0]], v[0]&1, a[v[1]], v[1]&1);
                    }
                }
                if(cnt == 3) {
                    for(int k = 0; k < 4; ++k) {
                        if(a[k] == -1) {
                            solver.assign(a[k^2], k&1);
                            solver.assign(a[k^1], k&1);
                            solver.assign(a[k^3], k&1);
                        }
                    }
                }
            }else if(s[i][j] == 'S') {
                int x = id[i][j];
                for(int k = 0; k < 4; ++k) {
                    int y = detect(i, j, k);
                    if(y != -1) {
                        solver.assign(x, ~k&1);
                    }
                }
            }
        }
    }
    if(ok && solver.solve()) {
        puts("ojs");
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(s[i][j] == 'S') {
                    int u = id[i][j];
                    s[i][j] = solver.mark[u<<1] == 1 ? '|' : '-';
                }
            }
            puts(s[i]);
        }
    }else {
        puts("tnl");
    }
}
int main() {
    solve();
    return 0;
}