https://acm.ecnu.edu.cn/contest/497/

C. Paint

 

题意：一个长为 nn 的数组，初始全为0，mm 次操作，两种：1. 把最后 xx 个元素全部变为 yy；2. 查询当前有几个不同的数。

栈

用栈模拟，同时记录每种颜色的出现次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n, m;
int cnt[N];
int ans = 1;
stack<pii>st;

int main() {
    scanf("%d%d", &n, &m);
    st.push({1, 0});
    cnt[0] = 1;
    for(int i=1;i<=m;i++){
        int op;
        scanf("%d", &op);
        if(op == 1){
            int x, y;
            scanf("%d%d", &x, &y);
            while(!st.empty() && n - x + 1 <= st.top().first){
                cnt[st.top().second]--;
                if(cnt[st.top().second] == 0)ans--;
                st.pop();
            }
            st.push({n - x + 1, y});
            if(cnt[y] == 0)ans++;
            cnt[y]++;
        }
        else{
            printf("%d\n", ans);
        }
    }
    return 0;
}

 

D. Short Path

 

题意：一张 nn 个节点的无向图，给定每对点的最短距离，要求构造出原图，且满足边长之和最小，输出边长之和。

floyed

在完全图上挑出原图的边。

一条边 (u,v)(u, v) 为原图中的边当且仅当在不经过该边的情况下，uu 与 vv 的最短距离大于该边长度。

可以用floyed算法求得不经过 (u,v)(u, v) 的条件下，uu 与 vv 的最短距离。具体为在更新 dis[i][j]dis[i][j] 时强制要求 i,ji,j 都不能与分割点 kk 重合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

int n;
int a[505][505];
int d[505][505], vis[505][505];

int main() {
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)scanf("%d", &a[i][j]);
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=a[i][j];
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                int nd = d[i][k] + d[j][k];
                if(nd < a[i][j]){
                    puts("-1");
                    return 0;
                }
                if(nd == a[i][j] && k!=i && k!=j)vis[i][j] =vis[j][i]= 1;
            }
        }
    }
    ll ans = 0;
    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(!vis[i][j])ans+=a[i][j];
    printf("%lld\n", ans);
    return 0;
}

 

F. Cake

 

题意：给定平面上一个凸多边形，以及一条直线，问直线分割多边形得到的两块中小的那块的面积。

计算几何

用叉乘求出每个点在直线哪一侧，叉乘求两直线交点，叉乘求多边形面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

struct Point {
    double x, y;

    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

typedef Point Vector;

Vector operator+(Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }

Vector operator-(Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); }

Vector operator*(Vector A, double p) { return Vector(A.x * p, A.y * p); }

Vector operator/(Vector A, double p) { return Vector(A.x / p, A.y / p); }

bool operator<(const Point &a, const Point &b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

const double eps = 1e-10;

int dcmp(double x) {
    if (fabs(x) < eps)return 0;
    else return x < 0 ? -1 : 1;
}

bool operator==(const Point &a, const Point &b) {
    return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}

double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; }

double Length(Vector A) { return sqrt(Dot(A, A)); }

double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }

double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }

double Area(Point A, Point B, Point C) { return fabs(Cross(B - A, C - A)) / 2; }    //无向面积

Point GetLineInteraction(Point P, Vector v, Point Q, Vector w){
    Vector u = P - Q;
    double t = Cross(w, u) / Cross(v, w);
    return P + v * t;
}

int n;
struct Point p[110], a, b;
int vis[110];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf", &p[i].x, &p[i].y);
    }
    scanf("%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y);
    Vector ab = a - b;
    for (int i = 0; i < n; i++) {
        double t = Cross(ab, a - p[i]);
        if (t < 0)vis[i] = -1;
        else if (t > 0)vis[i] = 1;
        else vis[i] = 0;
    }
    for(int i=0;i<n;i++){
        if(vis[i]*vis[(i+1)%n]==-1){
            Point np = GetLineInteraction(p[i],p[(i+1)%n]-p[i], a, ab);
            if(i==n-1)p[n]=np;
            else{
                for(int j=n - 1;j>=i+1;j--)p[j+1] = p[j], vis[j+1]=vis[j];
                p[i+1]=np;
                vis[i+1]=0;
            }
            n++;
            break;
        }
    }
    for(int i=0;i<n;i++){
        if(vis[i]*vis[(i+1)%n]==-1){
            Point np = GetLineInteraction(p[i],p[(i+1)%n]-p[i], a, ab);
            if(i==n-1)p[n]=np;
            else{
                for(int j=n - 1;j>=i+1;j--)p[j+1] = p[j], vis[j+1]=vis[j];
                p[i+1]=np;
                vis[i+1]=0;
            }
            n++;
            break;
        }
    }
    double ans1 = 0, ans2 = 0;
    int st=-1, ed=-1;
    for(int i=0;i<n;i++){
        if(vis[i]==0){
            if(st==-1)st=i;
            else ed=i;
        }
    }
    for(int i=st;i!=ed;i=(i+1)%n){
        ans1+= abs(Cross(p[i]-p[st], p[i+1]-p[st]));
    }
    for(int i=ed;i!=st;i=(i+1)%n){
        ans2+=abs(Cross(p[i]-p[ed], p[(i+1)%n]-p[ed]));
    }
    printf("%.9lf\n", min(ans1, ans2)*0.5);
    return 0;
}

 

G. Construct Palindrome String

 

题意：给定字符串数组 A,BA,B，问有多少种配对情况满足 Ai+BjA_i+B_j 为回文串。

字符串哈希+Trie

共有三种情况：

  1. 回文中心在 AiA_i 中。
  2. 回文中心在 BjB_j 中。
  3. 回文中心在 Ai,BjA_i, B_j 之间，即 Ai,BjA_i, B_j 镜像对称。

对于第一种情况，先把 AiA_i 插入字典树，再对 AiA_i 的后缀找出为回文串的，用字符串哈希判断回文。在字典树上对此时的前缀的位置上cnt+1。枚举 BjB_j，翻转，沿字典树走，最终停下时的位置的cnt就是 BjB_j 的贡献数。

把 AiA_i 整个当作前缀，就可以处理第三种情况。

第二种情况与第一种类似，但由于只有 Ai+BjA_i+B_j 合法，Bj+AiB_j+A_i 不合法，所以要先翻转，再同情况一求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;

ll h1[N], p1[N], h2[N], p2[N], h3[N], p3[N], h4[N], p4[N];
ll m1 = 998244353, m2 = 1e9 + 7;
ll P1 = 233, P2 = 3993;

void init(string s, int n, ll h[], ll p[], ll P, ll mod) {    //从1开始
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = (h[i - 1] * P % mod + s[i] - 'a' + 1) % mod;
        p[i] = p[i - 1] * P % mod;
    }
}

ll hsh(int l, int r, ll h[], ll p[], ll mod) {
    return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
}

ll hsh(int l, int r) {
    return hsh(l, r, h1, p1, m1) * 2000000000ll + hsh(l, r, h2, p2, m2);
}

ll hshr(int l, int r) {
    return hsh(l, r, h3, p3, m1) * 2000000000ll + hsh(l, r, h4, p4, m2);
}

int n, m;
int vis[N];

bool ck(int l, int n) {
    int mid = (l + n) / 2;
    if ((n - l + 1) & 1) {
        if (n - l + 1 == 1)return true;
        return hsh(l, mid - 1) == hshr(1, (n - l + 1) / 2);
    } else {
        return hsh(l, mid) == hshr(1, (n - l + 1) / 2);
    }
}

int tot;
int ch[N][30], cnt[N];

void ini() {
    tot = 0;
    memset(ch, 0, sizeof(ch));
    memset(cnt, 0, sizeof(cnt));
}

void ins(string s) {
    int rt = 0;
    for (int i = 1; s[i]; i++) {
        int c = s[i] - 'a';
        if (!ch[rt][c])ch[rt][c] = ++tot;
        rt = ch[rt][c];
        cnt[rt] += vis[i];
    }
}

int qry(string t) {
    int rt = 0;
    for (int i = 1; t[i]; i++) {
        int c = t[i] - 'a';
        if (!ch[rt][c])return 0;
        rt = ch[rt][c];
    }
    return cnt[rt];
}

string s, rs;
vector<string> v1, v2;

ll cal(vector<string> &v1, vector<string> &v2, int flg) {
    ini();
    ll ans = 0;
    for (string s: v1) {
        rs = s;
        reverse(rs.begin(), rs.end());
        s = '0' + s;
        rs = '0' + rs;
        int le = s.length() - 1;
        fill(vis, vis + le + 1, 0);
        init(s, le, h1, p1, P1, m1);
        init(s, le, h2, p2, P2, m2);
        init(rs, le, h3, p3, P1, m1);
        init(rs, le, h4, p4, P2, m2);
        for (int j = 2; j <= le; j++) {
            if (ck(j, le))vis[j - 1] = 1;
        }
        vis[le] = flg;
        ins(s);
    }
    for (string t: v2) {
        reverse(t.begin(), t.end());
        t = '0' + t;
        ans += qry(t);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        v1.push_back(s);
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> s;
        v2.push_back(s);
    }
    ll ans = 0;
    ans += cal(v1, v2, 1);
    for(string& s:v1){
        reverse(s.begin(), s.end());
    }
    for(string& s:v2){
        reverse(s.begin(), s.end());
    }
    ans += cal(v2, v1, 0);
    cout << ans;
    return 0;
}

 

H. KR-976

 

题意：有初始分数 SS，目标分数 TT，0<S<T≤100000<S<T\le 10000，0<n≤100000<n\le 10000 轮游戏，每轮有 0<m≤100<m\le 10 种情况，每种情况有概率 wi/10000,0<wi≤10000,∑wi=10000w_i/10000,0<w_i\le 10000,\sum w_i=10000 发生，一旦发生就会使分数改变 −10000≤ci≤10000-10000\le c_i\le 10000，每轮只会发生一种情况。一旦分数 ≤0\leq 0，则立即死亡；一旦分数 ≥T\geq T，则立即获胜。问获胜的概率。gcd⁡(c1,⋯ ,cm)≥10\gcd(c_1, \cdots, c_m)\geq 10。

dp

dp[i][j]dp[i][j] 表示在第 ii 轮，净加分为 j∗gcd⁡(c1,⋯ ,cm)j*\gcd(c_1, \cdots, c_m) 的概率。

dp[i+1][j+c[k]]=(dp[i+1][j+c[k]]+dp[i][j]∗w[k])dp[i + 1][j + c[k]] = (dp[i + 1][j + c[k]] + dp[i][j] * w[k]) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
const ll mod = 998244353;

ll Pow(ll a, ll b) {
    ll res = 1ll;
    while (b) {
        if (b & 1)res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int S, T, n, m;
ll inv;
ll w[N], dp[10005][4005];
int c[N];
int B = 2000;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int main() {
    scanf("%d%d%d%d", &S, &T, &n, &m);
    inv = Pow(10000, mod - 2);
    for (int i = 1; i <= m; i++) {
        ll x;
        scanf("%lld%d", &x, &c[i]);
        w[i] = x * inv % mod;
    }
    int g = abs(c[1]);
    for (int i = 2; i <= m; i++)g = gcd(g, abs(c[i]));
    for (int i = 1; i <= m; i++)c[i] = c[i] / g;
    int s = (S + g - 1) / g, t = (T - S + g - 1) / g;
    dp[0][B] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = -s + 1; j < t; j++) {
            if (!dp[i][j + B])continue;
            for (int k = 1; k <= m; k++) {
                dp[i + 1][j + c[k] + B] = (dp[i + 1][j + c[k] + B] + dp[i][j + B] * w[k] % mod) % mod;
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)for (int j = t + B; j <= 4000; j++)ans = (ans + dp[i][j]) % mod;
    printf("%lld\n", ans);
    return 0;
}