2019 HDOJ Multi-University Training Contest Stage 1(杭电多校)

有个傻逼二分没看出来，刚正面疯狂白给，大锅。

没补的题给出STD，以后再慢慢补。

A：

dp。

 1 #include <cstdio>
 2 #include <vector>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 
10 typedef pair<int, int> piir;
11 
12 const int N = 100 + 5;
13 
14 int n, m, ans;
15 
16 int dp[2][N][N][N];
17 vector <piir> lims[N];
18 
19 inline void Mod(int &x) {
20     static int mod = 998244353;//1e9 + 7;
21     if (x >= mod) x -= mod;
22 }
23 
24 int main() {
25     int Case, ans, l, r, x;
26     int i, j, k, t, p;
27     for (scanf("%d", &Case); Case --; ) {
28         ans = 0;
29         scanf("%d %d", &n, &m);
30         for (i = 1; i <= n; i ++)
31             lims[i].clear();
32         for (i = 0; i < m; i ++) {
33             scanf("%d %d %d", &l, &r, &x);
34             lims[r].push_back(piir(l, x));
35         }
36         dp[0][0][0][0] = 1;
37         for (i = p = 1; i <= n; i ++, p ^= 1) {
38             for (j = 0; j <= i; j ++)
39                 for (k = 0; k <= j; k ++)
40                     for (t = 0; t <= k; t ++)
41                         dp[p][j][k][t] = 0;
42             for (j = 0; j < i; j ++)
43                 for (k = 0; k <= j; k ++)
44                     for (t = 0; t <= k; t ++) {
45                         Mod(dp[p][j][k][t] += dp[p ^ 1][j][k][t]);
46                         Mod(dp[p][i - 1][k][t] += dp[p ^ 1][j][k][t]);
47                         Mod(dp[p][i - 1][j][t] += dp[p ^ 1][j][k][t]);
48                         Mod(dp[p][i - 1][j][k] += dp[p ^ 1][j][k][t]);
49                     }
50             for (j = 0; j < i; j ++)
51                 for (k = 0; k <= j; k ++)
52                     for (t = 0; t <= k; t ++)
53                         for (piir tmp : lims[i])
54                             if (1 + (j >= tmp.first) + (k >= tmp.first) + (t >= tmp.first) != tmp.second)
55                                 dp[p][j][k][t] = 0;
56         }
57         for (i = 0, p = n & 1; i < n; i ++)
58             for (j = 0; j <= i; j ++)
59                 for (k = 0; k <= j; k ++)
60                     Mod(ans += dp[p][i][j][k]);
61         printf("%d
", ans);
62     }
63     return 0;
64 }

STD

B：

原题是codeforces 1100F。比较暴力的做法是线段树维护线性基，但是时间复杂度会挂掉。

题解给了个技巧：贪心地维护序列的前缀线性基(上三角形态)，对于每个线性基，将出现位置靠右的数字尽可能地放在高位，也就是说在插入新数字的时候，要同时记录对应位置上数字的出现位置，并且在找到可以插入的位置的时候，如果新数字比位置上原来的数字更靠右，就将该位置上原来的数字向低位推。在求最大值的时候，从高位向低位遍历，如果该位上的数字出现在询问中区间左端点的右侧且可以使答案变大，就异或到答案里。

对于线性基的每一位，与它异或过的线性基更高位置上的数字肯定都出现在它右侧(否则它就会被插入在那个位置了)，因此做法的正确性显然。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 500000 + 10;
 4 int T, n, m, op, l, r, tmp, ans, a[MAXN], f[MAXN][32], pos[MAXN][32];
 5 inline int Read() {
 6     int x = 0, f = 1; char ch = getchar();
 7     while (ch < '0' || ch > '9') {
 8         if (ch == '-') f = -f;
 9         ch = getchar();
10     }
11     while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
12     return x * f;
13 }
14 char s[30];
15 inline void writeln(int x) {
16     if (x < 0) putchar('-'), x = -x;
17     if (!x) putchar('0');
18     else {
19         int len = 0;
20         while (x) s[++len] = x % 10 + '0', x /= 10;
21         while (len) putchar(s[len--]);
22     }
23     putchar('
');
24 }
25 inline void Add(int i, int x) {
26     int k = i;
27     for (int j = 30; j >= 0; --j) f[i][j] = f[i - 1][j], pos[i][j] = pos[i - 1][j];
28     for (int j = 30; j >= 0; --j) if (x >> j) {
29             if (!f[i][j]) {
30                 f[i][j] = x;
31                 pos[i][j] = k;
32                 break;
33             } else {
34                 if (k > pos[i][j]) {
35                     tmp = k, k = pos[i][j], pos[i][j] = tmp;
36                     tmp = x, x = f[i][j], f[i][j] = tmp;
37                 }
38                 x ^= f[i][j];
39             }
40         }
41 }
42 int main() {
43     //freopen("test.in","r",stdin);
44     //freopen("test.out","w",stdout);
45     T = Read();
46     while (T--) {
47         n = Read(), m = Read();
48         for (int i = 1; i <= n; ++i) a[i] = Read(), Add(i, a[i]);
49         ans = 0;
50         while (m--) {
51             op = Read();
52             if (op) a[++n] = Read()^ans, Add(n, a[n]);
53             else {
54                 l = Read(), r = Read();
55                 l = (l ^ ans) % n + 1, r = (r ^ ans) % n + 1;
56                 if (l > r) swap(l, r);
57                 ans = 0;
58                 for (int j = 30; j >= 0; --j) if ((ans ^ f[r][j]) > ans && pos[r][j] >= l) ans ^= f[r][j];
59                 writeln(ans);
60             }
61         }
62         for (int i = 1; i <= n; ++i)
63             for (int j = 30; j >= 0; --j) f[i][j] = pos[i][j] = 0;
64     }
65     return 0;
66 }

View Code

C：

离散化+背包

 1 #include <bits/stdc++.h>
 2 
 3 template <class T>
 4 bool Reduce(T &a, T const &b) {
 5     return a > b ? a = b, 1 : 0;
 6 }
 7 
 8 const int XN = 1e4 + 11;
 9 const long long INF = 1e18;
10 
11 std::vector<long long> Merge(std::vector<long long> const &a, std::vector<long long> const &b) {
12     std::vector<long long> c(a.size() + b.size() - 1, INF);
13     for (size_t i = 0; i < a.size(); ++i)
14         for (size_t j = 0; j < b.size(); ++j)
15             Reduce(c[i + j], a[i] + b[j]);
16     return c;
17 }
18 
19 std::vector<long long> Go(std::vector<std::pair<int, int>> const &a, int dest) {
20     std::vector<long long> c(a.size(), INF), t(a.size(), INF);
21     c[0] = dest == -1 ? 0 : abs(dest - a[0].first);
22     t[0] = 0;
23     for (int i = 1; i < (int)a.size(); ++i) {
24         int len = abs(a[i].first - a[i - 1].first);
25         for (int j = 0; j < i; ++j)
26             t[j] += len;
27         for (int j = i; j >= 1; --j)
28             Reduce(t[j], t[j - 1] + a[i].second);
29         for (int j = 0; j <= i; ++j)
30             Reduce(c[j], t[j] + (dest == -1 ? 0 : abs(dest - a[i].first)));
31     }
32     return c;
33 }
34 
35 int main() {
36 //  freopen("in","r",stdin);
37     std::ios::sync_with_stdio(0);
38     std::cin.tie(0);
39     int T; std::cin >> T;
40     while (T--) {
41         //std::cerr<<T<<':';
42         int n, m, k; std::cin >> n >> m >> k;
43         static std::tuple<int, int, int> p[XN];
44         std::vector<int> x{1};
45         for (int i = 1; i <= k; ++i) {
46             std::cin >> std::get<0>(p[i]) >> std::get<1>(p[i]) >> std::get<2>(p[i]);
47             x.push_back(std::get<0>(p[i]));
48         }
49         std::sort(x.begin(), x.end());
50         x.erase(std::unique(x.begin(), x.end()), x.end());
51         static std::vector<std::pair<int, int>> a[XN];
52         static long long Ans[XN];
53         for (size_t i = 0; i < x.size(); ++i)
54             a[i].clear();
55         for (int i = 1; i <= k; ++i) {
56             a[std::lower_bound(x.begin(), x.end(), std::get<0>(p[i])) - x.begin()].push_back({std::get<1>(p[i]),
57                     std::get<2>(p[i])});
58             Ans[i] = INF;
59         }
60         for (size_t i = 0; i < x.size(); ++i)
61             std::sort(a[i].begin(), a[i].end());
62         static std::vector<long long> f[2];
63 
64         auto t = a[0];
65         t.insert(t.begin(), {1, 0});
66         f[0] = Go(t, (m + 1) / 2);
67         auto g = Go(t, -1);
68         for (size_t i = 0; i < t.size(); ++i)
69             Reduce(Ans[i], g[i]);
70 
71         for (int i = 1; i < (int)x.size(); ++i) {
72             auto sp = std::lower_bound(a[i].begin(), a[i].end(), std::make_pair((m + 1) / 2, 0));
73             std::vector<std::pair<int, int>> t0(a[i].begin(), sp), t1(sp, a[i].end());
74             t0.push_back({(m + 1) / 2, 0}); std::reverse(t0.begin(), t0.end());
75             t1.insert(t1.begin(), {(m + 1) / 2, 0});
76 
77             auto f0 = Go(t0, (m + 1) / 2), f1 = Go(t1, (m + 1) / 2), g0 = Go(t0, -1), g1 = Go(t1, -1);
78 
79             g0 = Merge(f1, g0); g1 = Merge(f0, g1);
80 
81             assert(g0.size() == g1.size());
82 
83             std::vector<long long> g(g0.size());
84             for (size_t i = 0; i < g.size(); ++i)
85                 g[i] = std::min(g0[i], g1[i]);
86             g = Merge(f[(i - 1) & 1], g);
87 
88             f[i & 1] = Merge(f[(i - 1) & 1], Merge(f0, f1));
89             for (size_t j = 0; j < g.size(); ++j) {
90                 Reduce(Ans[j], g[j] += x[i] - x[i - 1]);
91                 f[i & 1][j] += x[i] - x[i - 1];
92             }
93         }
94 
95         for (int i = 1; i <= k; ++i)
96             std::cout << Ans[i] << (i == k ? '
' : ' ');
97     }
98     return 0;
99 }

View Code

D：

一开始就想到了题解里用堆维护撞车事件的做法，想法正确且显然，时间复杂度O(nlogn)。唯一的难点在于非常难写。

直到比赛结束我都没意识到这题可以二分……不应该。

 1 /* basic header */
 2 #include <iostream>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 const int maxn = 2e5 + 10;
21 struct Car {
22     int l, s, v;
23 } car[maxn];
24 
25 int n;
26 
27 int check(double x) {
28     double currS = car[n].s - car[n].v * x; // 最前面的车行驶x时间之后离stopline的距离，也可以认为是一个“容忍距离”，决定了容忍多少辆车相撞
29     for (int i = n - 1; i >= 0; i--) { // 遍历前面的每一辆车
30         // 如果 前一辆车行驶x时间之后离stopline的距离 比 最前面的车行驶x时间之后离stopline的距离塞下下一辆车 还短
31         // 那么当前这辆车一定不会和身后的车相撞，那么允许后面的车走过stopline
32         if (car[i].s - car[i].v * x <= currS + car[i + 1].l) currS += car[i + 1].l;
33         else currS = car[i].s - car[i].v * x; // 否则会相撞，答案更新为当前的车在前面无阻碍的情况下行驶x时间离stopline的距离
34     }
35     return currS <= eps; // 如果小于等于0，说明行驶x时间后必然可以到达stopline
36 }
37 
38 int main() {
39     while (~scanf("%d", &n)) {
40         rep1(i, 0, n) scanf("%d", &car[i].l);
41         rep1(i, 0, n) scanf("%d", &car[i].s);
42         rep1(i, 0, n) scanf("%d", &car[i].v);
43         double l = 0, r = 1e18; // 二分到达时间
44         while (r - l > eps) {
45             double mid = (l + r) / 2;
46             if (check(mid)) r = mid;
47             else l = mid;
48         }
49         printf("%.6f
", r);
50     }
51     return 0;
52 }

View Code

E：

从一开始就很多人过的题，但由于solo训练所以甩锅给队友(

网络流求最小割模板题。

  1 #include <bits/stdc++.h>
  2 
  3 template <class T>
  4 bool Reduce(T &a, T const &b) {
  5     return a > b ? a = b, 1 : 0;
  6 }
  7 
  8 const int XN = 1e4 + 11;
  9 const int INF = 2e9;
 10 const long long oo = 1e18;
 11 
 12 int n;
 13 long long sp[XN];
 14 
 15 namespace D {
 16     struct Edge {
 17         int to, v;
 18     };
 19 
 20     std::vector<Edge> G[XN];
 21 
 22     void Run() {
 23         static bool ud[XN];
 24         std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> Q;
 25         std::fill(sp + 1, sp + 1 + n, oo);
 26         std::fill(ud + 1, ud + 1 + n, 0);
 27         sp[1] = 0;
 28         Q.push(std::make_pair(0, 1));
 29         while (!Q.empty()) {
 30             int pos = Q.top().second; Q.pop();
 31             if (ud[pos])
 32                 continue;
 33             ud[pos] = 1;
 34             for (auto &e : G[pos]) {
 35                 int u = e.to;
 36                 if (Reduce(sp[u], sp[pos] + e.v))
 37                     Q.push(std::make_pair(sp[u], u));
 38             }
 39         }
 40     }
 41 }
 42 
 43 namespace I {
 44     struct Edge {
 45         int to, cap, v;
 46         Edge *rev, *pre;
 47     } *G[XN], *preArc[XN];
 48 
 49     void AddEdge(int x, int y, int c) {
 50         G[x] = new Edge{y, c, 0, NULL, G[x]};
 51         G[y] = new Edge{x, 0, 0, G[x], G[y]};
 52         G[x]->rev = G[y];
 53     }
 54 
 55     int Aug() {
 56         int d = INF;
 57         for (int pos = n; preArc[pos]; pos = preArc[pos]->rev->to)
 58             Reduce(d, preArc[pos]->cap - preArc[pos]->v);
 59         for (int pos = n; preArc[pos]; pos = preArc[pos]->rev->to) {
 60             preArc[pos]->v += d;
 61             preArc[pos]->rev->v -= d;
 62         }
 63         return d;
 64     }
 65 
 66     long long Run() {
 67         static int num[XN], d[XN];
 68         static Edge *cArc[XN];
 69         std::fill(num + 1, num + n, 0);
 70         std::fill(d + 1, d + 1 + n, 0);
 71         std::copy(G + 1, G + 1 + n, cArc + 1);
 72         num[0] = n; preArc[1] = 0;
 73         long long flow = 0;
 74         for (int pos = 1; d[1] < n;) {
 75             if (pos == n) {
 76                 flow += Aug();
 77                 pos = 1;
 78             }
 79             bool adv = 0;
 80             for (Edge *&e = cArc[pos]; e; e = e->pre) {
 81                 int u = e->to;
 82                 if (e->cap > e->v && d[u] + 1 == d[pos]) {
 83                     adv = 1;
 84                     preArc[pos = u] = e;
 85                     break;
 86                 }
 87             }
 88             if (!adv) {
 89                 if (--num[d[pos]] == 0)
 90                     break;
 91                 d[pos] = n;
 92                 for (Edge *e = cArc[pos] = G[pos]; e; e = e->pre)
 93                     if (e->cap > e->v)
 94                         Reduce(d[pos], d[e->to] + 1);
 95                 num[d[pos]]++;
 96                 if (pos != 1)
 97                     pos = preArc[pos]->rev->to; //cArc
 98             }
 99         }
100         return flow;
101     }
102 }
103 
104 int main() {
105     //freopen("test1.in","r",stdin);
106     std::ios::sync_with_stdio(0);
107     std::cin.tie(0);
108     int T; std::cin >> T;
109     while (T--) {
110         int m; std::cin >> n >> m;
111         for (int i = 1; i <= n; ++i) {
112             D::G[i].clear();
113             I::G[i] = 0;
114         }
115         for (int i = 1; i <= m; ++i) {
116             int x, y, v;
117             std::cin >> x >> y >> v;
118             D::G[x].push_back({y, v});
119         }
120 
121         D::Run();
122 
123         if (sp[n] == oo)
124             std::cout << 0 << '
';
125         else {
126             for (int pos = 1; pos <= n; ++pos)
127                 for (auto &e : D::G[pos])
128                     if (sp[e.to] - sp[pos] == e.v)
129                         I::AddEdge(pos, e.to, e.v);
130 
131             std::cout << I::Run() << '
';
132         }
133     }
134     return 0;
135 }

STD

F：

一开始看错题了，以为是对半取，那就是个傻逼贪心细节题。后来补充了题意之后瞬间难度上升。

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int maxp = 26 + 5;
const int maxn = 400000 + 5;

struct Suffix_Node {
    int trans[maxp], par, len;
    void Clear() {
        memset(trans, 0, sizeof(trans));
        par = len = 0;
    }
};

class Suffix_Automaton {
private:
    Suffix_Node S[maxn];
    int p, np, size, crp;
public:
    Suffix_Automaton(): p(1), np(1), size(1), crp(1) {};
    const void Clear() {
        for (int i = 0; i <= size; ++i) S[i].Clear();
        p = np = size = crp = 1;
    }
    const int Match(const char ch)const {
        return S[crp].trans[ch - 'a'];
    }
    const void Withdraw(const int len) {
        while ( crp != 0 && S[S[crp].par].len >= len ) crp = S[crp].par;
        if ( crp == 0 ) crp = 1;
    }
    const void Transfer(const int len, const char ch) {
        crp = S[crp].trans[ch - 'a'];
        if ( crp == 0 ) crp = 1;
        Withdraw(len);
    }
    const void Insert(const char ch) {
        int x = ch - 'a';
        np = ++size;
        S[np].len = S[p].len + 1;
        while ( p != 0 && !S[p].trans[x] ) S[p].trans[x] = np, p = S[p].par;
        if ( p == 0 ) S[np].par = 1;
        else {
            int q, nq;
            q = S[p].trans[x];
            if ( S[q].len == S[p].len + 1 ) S[np].par = q;
            else {
                nq = ++size;
                S[nq] = S[q], S[nq].len = S[p].len + 1;
                S[np].par = S[q].par = nq;
                while ( p != 0 && S[p].trans[x] == q ) S[p].trans[x] = nq, p = S[p].par;
            }
        }
        p = np;
    }
} SAM;

string s;
ll f[maxn], p, q;

ll DP() {
    SAM.Insert(s[0]);
    f[0] = p;
    int l = 1, r = 0;
    for (int i = 1; i < (int)s.size(); ++i) {
        ++r;
        f[i] = f[i - 1] + p;
        while ( ( !SAM.Match(s[i]) || r - l + 1 > (i + 1) / 2 ) && l <= r ) {
            SAM.Insert(s[l++]);
            SAM.Withdraw(r - l);
        }
        SAM.Transfer(r - l + 1, s[i]);
        if (l <= r) {
            f[i] = min(f[i], f[i - (r - l + 1)] + q);
        }
    }
    SAM.Clear();
    return f[s.size() - 1];
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0); std::cout.tie(0);
    while ( cin >> s >> p >> q ) {
        ll ans = DP();
        cout << ans << '
' ;
    }
    return 0;
}

STD

G：

题意为求分子分母均小于等于某个值n的第k大的最简分数。

  1 #include <bits/stdc++.h>
  2 
  3 typedef std::pair<long long, long long> Frac;
  4 
  5 Frac operator + (Frac a, Frac b) {
  6     long long y = a.second / std::__gcd(a.second, b.second) * b.second,
  7               x = a.first * (y / a.second) + b.first * (y / b.second);
  8     return {x, y};
  9 }
 10 
 11 Frac operator /(Frac a, int b) {
 12     long long x = a.first, y = a.second * b,
 13               d = std::__gcd(x, y);
 14     return {x / d, y / d};
 15 }
 16 
 17 const int N = 1e6, XN = N + 11;
 18 
 19 int prime[XN], mu[XN], mert[XN], pcnt;
 20 
 21 void Prep() {
 22     static bool notPrime[XN];
 23     mu[1] = 1;
 24     for (int i = 2; i <= N; ++i) {
 25         if (!notPrime[i]) {
 26             prime[++pcnt] = i;
 27             mu[i] = -1;
 28         }
 29         for (int j = 1; j <= pcnt && i * prime[j] <= N; ++j) {
 30             notPrime[i * prime[j]] = 1;
 31             if (i % prime[j] == 0) {
 32                 mu[i * prime[j]] = 0;
 33                 break;
 34             } else
 35                 mu[i * prime[j]] = -mu[i];
 36         }
 37     }
 38     for (int i = 1; i <= N; ++i)
 39         mert[i] = mert[i - 1] + mu[i];
 40 }
 41 
 42 long long Sum(long long n, long long a, long long b, long long m) {
 43     if (b == 0)
 44         return n * (a / m);
 45     else if (a >= m)
 46         return n * (a / m) + Sum(n, a % m, b, m);
 47     else if (b >= m)
 48         return (n - 1) * n / 2 * (b / m) + Sum(n, a, b % m, m);
 49     else
 50         return Sum(((__int128)b * n + a) / m, (a + (__int128)b * n) % m, m, b);
 51 }
 52 
 53 long long Count(Frac x, int n) {
 54     long long res = 0;
 55     for (int l = 1, r; l <= n; l = r + 1) {
 56         r = n / (n / l);
 57         res += Sum(n / l + 1, 0, x.first, x.second) * (mert[r] - mert[l - 1]);
 58     }
 59     return res;
 60 }
 61 
 62 Frac Gen(long long a, long long b, int n, long long k) {
 63     Frac l{0, 1}, mid{1, 1}, r{1, 0}, res{-1, -1};
 64     long long x = a, y = b;
 65     while (x != y && std::max(mid.first, mid.second) <= n) {
 66         if (a * mid.second < b * mid.first)
 67             res = mid;
 68         if (x < y) {
 69             std::tie(l, mid, r) = std::make_tuple(l, std::make_pair(l.first + mid.first, l.second + mid.second), mid);
 70             y -= x;
 71         } else {
 72             std::tie(l, mid, r) = std::make_tuple(mid, std::make_pair(mid.first + r.first, mid.second + r.second), r);
 73             x -= y;
 74         }
 75     }
 76     assert(Count(res, n) == k);
 77     return res;
 78 }
 79 
 80 int main() {
 81     std::ios::sync_with_stdio(0);
 82     std::cin.tie(0);
 83     Prep();
 84     int T; std::cin >> T;
 85     while (T--) {
 86         int n; long long k;
 87         std::cin >> n >> k;
 88         Frac l{0, 1}, r{1, 1}, pivot{-1, -1};
 89         for (int t = 40; t--;) {
 90             Frac mid = (l + r) / 2;
 91             if (Count(mid, n) < k) {
 92                 pivot = mid;
 93                 l = mid;
 94             } else
 95                 r = mid;
 96         }
 97         auto Ans = Gen(pivot.first, pivot.second, n, k);
 98         std::cout << Ans.first << '/' << Ans.second << '
';
 99     }
100     return 0;
101 }

View Code

H：

仙人掌相关题。分治+fft。

  1 #include <bits/stdc++.h>
  2 
  3 const int XN = (1 << 18) + 11, P = 998244353;
  4 
  5 int Add(int x, int const &y) {
  6     return (x += y) >= P ? x - P : x;
  7 }
  8 
  9 void AddBy(int &x, int const &y) {
 10     ((x += y) >= P) && (x -= P);
 11 }
 12 
 13 int Minus(int x, int const &y) {
 14     return (x -= y) < 0 ? x + P : x;
 15 }
 16 
 17 int Mul(long long x, int const &y) {
 18     return x * y % P;
 19 }
 20 
 21 void MulBy(int &x, int const &y) {
 22     x = (long long)x * y % P;
 23 }
 24 
 25 int Pow(long long base, int v) {
 26     long long res;
 27     for (res = 1; v; v >>= 1, (base *= base) %= P)
 28         if (v & 1)
 29             (res *= base) %= P;
 30     return res;
 31 }
 32 
 33 int Inverse(int x) {
 34     return Pow(x, P - 2);
 35 }
 36 
 37 int Make2(int x) {
 38     return 1 << ((32 - __builtin_clz(x)) + ((x & (-x)) != x));
 39 }
 40 
 41 void NTT(int a[], int n, int op) {
 42     for (int i = 1, j = n >> 1; i < n - 1; ++i) {
 43         if (i < j)
 44             std::swap(a[i], a[j]);
 45         int k = n >> 1;
 46         while (k <= j) {
 47             j -= k;
 48             k >>= 1;
 49         }
 50         j += k;
 51     }
 52     for (int len = 2; len <= n; len <<= 1) {
 53         int rt = Pow(3, (P - 1) / len);
 54         for (int i = 0; i < n; i += len) {
 55             int w = 1;
 56             for (int j = i; j < i + len / 2; ++j) {
 57                 int u = a[j], t = Mul(a[j + len / 2], w);
 58                 a[j] = Add(u, t), a[j + len / 2] = Minus(u, t);
 59                 w = Mul(w, rt);
 60             }
 61         }
 62     }
 63     if (op == -1) {
 64         std::reverse(a + 1, a + n);
 65         int in = Inverse(n);
 66         for (int i = 0; i < n; ++i)
 67             a[i] = Mul(a[i], in);
 68     }
 69 }
 70 
 71 void Contrb(int A[], int An, int B[], int Bn, int offset, int C[], int L, int R) {
 72     if ((long long)An * Bn < 1000000) {
 73         for (int i = 0; i < An; ++i)
 74             for (int j = 0; j < Bn; ++j) {
 75                 int k = i + j;
 76                 if (L <= k + offset && k + offset <= R)
 77                     AddBy(C[k + offset], Mul(A[i], B[j]));
 78             }
 79         return;
 80     }
 81     static int a[XN], b[XN];
 82     int n = Make2(An + Bn - 1);
 83     for (int i = 0; i < n; ++i) {
 84         a[i] = i < An ? A[i] : 0;
 85         b[i] = i < Bn ? B[i] : 0;
 86     }
 87     NTT(a, n, 1); NTT(b, n, 1);
 88     for (int i = 0; i < n; ++i)
 89         a[i] = Mul(a[i], b[i]);
 90     NTT(a, n, -1);
 91     for (int i = 0; i < n; ++i)
 92         if (L <= i + offset && i + offset <= R)
 93             AddBy(C[i + offset], a[i]);
 94 }
 95 
 96 int a[XN], b[XN], c[XN], d[XN], n, inv[XN];
 97 
 98 void DC(int L, int R) {
 99     if (L == R) {
100         if (L == 1)
101             a[L] = 1;
102         else
103             MulBy(a[L], inv[L - 1]);
104         AddBy(b[L], a[L]);
105         AddBy(c[L], a[L]);
106         int x = Mul(L, Mul(Add(Add(b[L], c[L]), L % 2 == 0 ? b[L / 2] : 0), inv[2]));
107         for (int i = L; i <= n; i += L)
108             AddBy(d[i], x);
109     } else {
110         int M = (L + R) / 2;
111         DC(L, M);
112         auto Calc = [&](int L1, int R1, int L2, int R2) {
113             Contrb(a + L1, R1 - L1 + 1, d + L2, R2 - L2 + 1, L1 + L2, a, M + 1, R);
114             Contrb(a + L1, R1 - L1 + 1, b + L2, R2 - L2 + 1, L1 + L2, b, M + 1, R);
115             static int a2[XN];
116             for (int i = L1; i <= R1; ++i)
117                 a2[i] = i % 2 == 0 ? a[i / 2] : 0;
118             Contrb(a2 + L1, R1 - L1 + 1, c + L2, R2 - L2 + 1, L1 + L2, c, M + 1, R);
119         };
120         if (L != 1) {
121             Calc(L, M, 1, R - L);
122             Calc(1, R - L, L, M);
123         }
124         Calc(L, M, L, M);
125         DC(M + 1, R);
126     }
127 }
128 
129 int main() {
130     std::ios::sync_with_stdio(0);
131     std::cin.tie(0);
132     std::cin >> n;
133     for (int i = 1; i <= n; ++i)
134         inv[i] = Pow(i, P - 2);
135     DC(1, n);
136     for (int i = 1; i <= n; ++i)
137         std::cout << a[i] << '
';
138     return 0;
139 }

View Code

I：

一位位地构造答案字符串，每次贪心地加能加入的最小的字符(判断能否加入只要判断加入之后原字符串剩下的后缀中的每种字符的数目能否足够满足条件)。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i)
 4 #define dwn(i, j, k) for (int i = int(j); i >= int(k); -- i)
 5 const int N = 1e5 + 7;
 6 char s[N], s1[N];
 7 int k, n, cnt[N][26], l[26], r[26], used[26];
 8 vector<int> g[26];
 9 int main() {
10     while (~scanf("%s%d", s, &k)) {
11         memset(used, 0, sizeof(used));
12         rep(i, 0, 25) scanf("%d%d", l + i, r + i);
13         n = strlen(s);
14         memset(cnt[n], 0, sizeof(cnt[n]));
15         for (int i = 0; i < 26; ++i)
16             g[i].clear();
17         dwn(i, n - 1, 0) rep(j, 0, 25) cnt[i][j] = cnt[i + 1][j] + (s[i] == 'a' + j);
18         rep(i, 0, n - 1) g[s[i] - 'a'].push_back(i);
19         // for (int i: g[0]) cout << i << " "; cout << endl;
20         // for (int i: g[1]) cout << i << " ";cout << endl;
21         vector<int>::iterator head[26];
22         rep(i, 0, 25) head[i] = g[i].begin();
23         int last = -1;
24         rep(i, 0, k - 1) {
25             bool f1 = 0;
26             rep(j, 0, 25) {
27                 if (used[j] == r[j]) continue;
28                 while (head[j] != g[j].end() && (*head[j]) <= last) head[j] ++;
29                 if (head[j] == g[j].end()) continue;
30                 used[j] ++;
31                 bool flag = 1;
32                 int pos = *head[j], sum = 0;
33 
34                 rep(t, 0, 25) {
35                     if (cnt[pos + 1][t] + used[t] < l[t]) flag = 0;
36                     sum += max(l[t] - used[t], 0);
37                 }
38                 if (sum > k - i - 1) flag = 0;
39                 sum = 0;
40                 rep(t, 0, 25) {
41                     sum += min(cnt[pos + 1][t], r[t] - used[t]);
42                 }
43                 if (sum < k - i - 1) flag = 0;
44                 // cout << i << " " << j << " " << flag << endl;
45                 if (!flag) used[j] --;
46                 else {
47                     s1[i] = 'a' + j;
48                     f1 = 1;
49                     last = pos;
50                     break;
51                 }
52             }
53             if (!f1) {
54                 printf("-1
");
55                 goto end;
56             }
57         }
58         /*int cc[26];
59         rep(i, 0, 25) cc[i] = 0;
60         rep(i, 0, k - 1) cc[s1[i] - 'a'] ++;
61         rep(i, 0, 25) {
62             if (cc[i] < l[i] || cc[i] > r[i]) {
63                 cout << i << endl;
64                 cout << cc[i] << " " << l[i] << " " << r[i] << endl;
65             }
66         }*/
67         s1[k] = 0;
68         printf("%s
", s1);
69 end:;
70     }
71     return 0;
72 }

STD

J：

记忆化搜索。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <cstring>
  6 #include <string>
  7 #include <algorithm>
  8 
  9 using namespace std;
 10 
 11 const int maxn = 105;
 12 
 13 long long mod = 998244353;
 14 
 15 int n, m, t;
 16 
 17 long long f[maxn][maxn][maxn];
 18 
 19 int a[maxn];
 20 int b[maxn];
 21 int pa[maxn];
 22 int pb[maxn];
 23 bool vis[maxn];
 24 
 25 int read(){
 26     int x;
 27     scanf("%d", &x);
 28     return x;
 29 }
 30 
 31 int dfs(int x, int l, int r){
 32     if(f[x][l][r] != -1)return 0;
 33     f[x][l][r] = 0;
 34     if(l == r){
 35         f[x][l][r] = 1;
 36         if(a[x] != b[l]){
 37             if(a[x] and b[l]){
 38                 f[x][l][r] = 0;
 39             }else if(a[x] and pb[a[x]] and pb[a[x]] != l){
 40                 f[x][l][r] = 0;
 41             }else if(b[l] and pa[b[l]] and pa[b[l]] != x){
 42                 f[x][l][r] = 0;
 43             }
 44         }
 45         return 0;
 46     }
 47     
 48     if(r + 1 == l)f[x][l][r] = 1;
 49     if(r < l)return 0;
 50     
 51     if(a[x]){
 52         if(pb[a[x]]){
 53             if(pb[a[x]] < l or pb[a[x]] > r){
 54                 f[x][l][r] = 0;
 55             }else{
 56                 dfs(x + 1, l, pb[a[x]] - 1);
 57                 dfs(x + pb[a[x]] - l + 1, pb[a[x]] + 1, r);
 58                 f[x][l][r] = f[x + 1][l][pb[a[x]] - 1] * f[x + pb[a[x]] - l + 1][pb[a[x]] + 1][r] % mod;
 59             }
 60             return 0;
 61         }
 62         
 63         int maxx = l;
 64         
 65         for(int i=l;i<=r;i++){
 66             if(pa[b[i]]){
 67                 if(pa[b[i]] < x or pa[b[i]] > x + r - l)break;
 68                 maxx = max(maxx, l + pa[b[i]] - x);
 69             }
 70             if(b[i])continue;
 71             if(i < maxx)continue;
 72             dfs(x + 1, l, i - 1);
 73             dfs(x + i - l + 1, i + 1, r);
 74             f[x][l][r] = (f[x][l][r] + f[x + 1][l][i - 1] * f[x + i - l + 1][i + 1][r]) % mod;
 75         }
 76         return 0;
 77     }
 78     
 79     int maxx = l;
 80         
 81     for(int i=l;i<=r;i++){
 82         if(pa[b[i]]){
 83             if(pa[b[i]] < x or pa[b[i]] > x + r - l)break;
 84             maxx = max(maxx, l + pa[b[i]] - x);
 85         }
 86         if(i < maxx)continue;
 87         dfs(x + 1, l, i - 1);
 88         dfs(x + i - l + 1, i + 1, r);
 89         f[x][l][r] = (f[x][l][r] + f[x + 1][l][i - 1] * f[x + i - l + 1][i + 1][r]) % mod;
 90     }
 91     
 92     return 0;
 93 }
 94 
 95 int main(){
 96     int i, j;
 97     long long ans = 0;
 98     int T;std::cin>>T;
 99     while(T--) {
100         scanf("%d", &n);
101         long long cnt=0;
102         memset(pa,0,sizeof(pa));
103         memset(pb,0,sizeof(pb));
104         memset(vis,0,sizeof(vis));
105         for(i=1;i<=n;i++){
106             a[i] = read();
107             if(a[i])pa[a[i]] = i;
108             vis[a[i]] = true;
109         }
110         
111         for(i=1;i<=n;i++){
112             b[i] = read();
113             if(b[i])pb[b[i]] = i;
114             vis[b[i]] = true;
115         }
116         
117         memset(f, -1, sizeof(f));
118         
119         dfs(1, 1, n);
120         ans = f[1][1][n];
121         
122         for(i=1;i<=n;i++){
123             if(!vis[i])cnt++;
124         }
125         
126         for(i=1;i<=cnt;i++){
127             ans = ans * i % mod;
128         }
129         
130         printf("%lld
", ans);
131     }
132     return 0;
133 }

View Code

K：

数论反演。

  1 #include <bits/stdc++.h>
  2 
  3 struct Istream {
  4     template <class T>
  5     Istream &operator >>(T &x) {
  6         static char ch; static bool neg;
  7         for (ch = neg = 0; ch < '0' || '9' < ch; neg |= ch == '-', ch = getchar());
  8         for (x = 0; '0' <= ch && ch <= '9'; (x *= 10) += ch - '0', ch = getchar());
  9         x = neg ? -x : x;
 10         return *this;
 11     }
 12 } fin;
 13 
 14 struct Ostream {
 15     template <class T>
 16     Ostream &operator <<(T x) {
 17         x < 0 && (putchar('-'), x = -x);
 18         static char stack[233]; static int top;
 19         for (top = 0; x; stack[++top] = x % 10 + '0', x /= 10);
 20         for (top == 0 && (stack[top = 1] = '0'); top; putchar(stack[top--]));
 21         return *this;
 22     }
 23 
 24     Ostream &operator <<(char ch) {
 25         putchar(ch);
 26         return *this;
 27     }
 28 } fout;
 29 
 30 const int N = 1e7, XN = N + 11, P = 998244353;
 31 
 32 int Add(int x, int const &y) {
 33     return (x += y) >= P ? x - P : x;
 34 }
 35 
 36 int Minus(int x, int const &y) {
 37     return (x -= y) < 0 ? x + P : x;
 38 }
 39 
 40 int Mul(long long x, int const &y) {
 41     return x * y % P;
 42 }
 43 
 44 int prime[XN], phi[XN], pcnt;
 45 void Prep() {
 46     static bool notPrime[XN];
 47     phi[1] = 1;
 48     for (int i = 2; i <= N; ++i) {
 49         if (!notPrime[i]) {
 50             prime[++pcnt] = i;
 51             phi[i] = i - 1;
 52         }
 53         for (int j = 1; j <= pcnt && i * prime[j] <= N; ++j) {
 54             notPrime[i * prime[j]] = 1;
 55             if (i % prime[j] == 0) {
 56                 phi[i * prime[j]] = phi[i] * prime[j];
 57                 break;
 58             } else
 59                 phi[i * prime[j]] = phi[i] * phi[prime[j]];
 60         }
 61     }
 62 }
 63 
 64 int Sum1(long long x) {
 65     return x * (x + 1) / 2 % P;
 66 }
 67 
 68 int Sum2(long long x) {
 69     return (x * (x + 1)) % (6ll * P) * (2 * x + 1) / 6 % P;
 70 }
 71 
 72 int Calc(int a, __int128 L, __int128 R) {
 73     int res = 0;
 74     for (int d = 1; 1LL * d * d <= a; ++d)
 75         if (a % d == 0) {
 76             res = Add(res, Mul((R / d - L / d) % P, phi[d]));
 77             if (a != d * d)
 78                 res = Add(res, Mul((R / (a / d) - L / (a / d)) % P, phi[a / d]));
 79         }
 80     return res;
 81 }
 82 
 83 int main() {
 84     //freopen("input","r",stdin);
 85     Prep();
 86     int T;
 87     fin >> T;
 88     while (T--) {
 89         __int128 n; fin >> n;
 90         if (n <= 7) {
 91             fout << n << '
';
 92         } else {
 93             int r; for (r = 1; (__int128)(r + 2) * (r + 2) * (r + 2) - 1 <= n; ++r);
 94             int Ans = Calc(r + 1, (__int128)(r + 1) * (r + 1) * (r + 1) - 1, n);
 95             for (int T = 1; T <= r; ++T)
 96                 Ans = Add(Ans, Mul(phi[T], Add(Add(Mul(3 * T, Sum2(r / T)), Mul(3, Sum1(r / T))), r / T)));
 97             fout << Ans << '
';
 98         }
 99     }
100     return 0;
101 }

View Code

L：

推式子数论题。NTT。

  1 #include <bits/stdc++.h>
  2 
  3 const int XN = 2e6 + 11, P = 998244353;
  4 
  5 int Pow(long long base, int v) {
  6     long long res;
  7     for (res = 1; v; v >>= 1, (base *= base) %= P)
  8         if (v & 1)
  9             (res *= base) %= P;
 10     return res;
 11 }
 12 
 13 int D(int x) {
 14     ((x >= P) && (x -= P)) || ((x < 0) && (x += P));
 15     return x;
 16 }
 17 
 18 void NTT(int a[], int n, int op) {
 19     for (int i = 1, j = n >> 1; i < n - 1; ++i) {
 20         if (i < j)
 21             std::swap(a[i], a[j]);
 22         int k = n >> 1;
 23         while (k <= j) {
 24             j -= k;
 25             k >>= 1;
 26         }
 27         j += k;
 28     }
 29     for (int len = 2; len <= n; len <<= 1) {
 30         int rt = Pow(3, (P - 1) / len);
 31         for (int i = 0; i < n; i += len) {
 32             int w = 1;
 33             for (int j = i; j < i + len / 2; ++j) {
 34                 int u = a[j], t = 1LL * a[j + len / 2] * w % P;
 35                 a[j] = D(u + t), a[j + len / 2] = D(u - t);
 36                 w = 1LL * w * rt % P;
 37             }
 38         }
 39     }
 40     if (op == -1) {
 41         std::reverse(a + 1, a + n);
 42         int in = Pow(n, P - 2);
 43         for (int i = 0; i < n; ++i)
 44             a[i] = 1LL * a[i] * in % P;
 45     }
 46 }
 47 
 48 std::vector<int> Conv(std::vector<int> const &A, std::vector<int> const &B, int N) {
 49     static int a[XN], b[XN];
 50     auto Make2 = [](int x)->int {
 51         return 1 << ((32 - __builtin_clz(x)) + ((x & (-x)) != x));
 52     };
 53     int n = Make2(A.size() + B.size() - 1);
 54     for (int i = 0; i < n; ++i) {
 55         a[i] = i < A.size() ? A[i] : 0;
 56         b[i] = i < B.size() ? B[i] : 0;
 57     }
 58     NTT(a, n, 1); NTT(b, n, 1);
 59     for (int i = 0; i < n; ++i)
 60         a[i] = 1LL * a[i] * b[i] % P;
 61     NTT(a, n, -1);
 62     std::vector<int> C(N);
 63     for (int i = 0; i < N; i++)
 64         C[i] = a[i];
 65     return C;
 66 }
 67 
 68 const int M = 2e6, XM = M + 11;
 69 
 70 int fact[XM], ifact[XM];
 71 
 72 int C(int n, int m) {
 73     return m <= n ? (long long)fact[n] * ifact[m] % P * ifact[n - m] % P : 0;
 74 }
 75 
 76 int main() {
 77     std::ios::sync_with_stdio(0);
 78     std::cin.tie(0);
 79     fact[0] = 1;
 80     for (int i = 1; i <= M; ++i)
 81         fact[i] = (long long)fact[i - 1] * i % P;
 82     ifact[M] = Pow(fact[M], P - 2);
 83     for (int i = M - 1; i >= 0; --i)
 84         ifact[i] = (long long)ifact[i + 1] * (i + 1) % P;
 85     int T; std::cin >> T;
 86     while (T--) {
 87         int n, m; std::cin >> n >> m;
 88 
 89         std::vector<int> a(n);
 90         for (int i = 0; i < n; ++i) {
 91             std::cin >> a[i];
 92         }
 93 
 94         int cnt[] = {0, 0, 0, 0};
 95         for (int i = 1; i <= m; ++i) {
 96             int x; std::cin >> x;
 97             cnt[x]++;
 98         }
 99 
100         for (int c = 1; c <= 3; ++c) if (cnt[c]) {
101                 std::vector<int> h(n);
102                 for (int i = 0; i * c < n; ++i)
103                     h[i * c] = C(cnt[c] - 1 + i, i);
104                 a = Conv(h, a, n);
105             }
106         long long Ans = 0;
107         for (int i = 0; i < n; ++i)
108             Ans ^= 1LL * (i + 1) * a[i];
109         std::cout << Ans << '
';
110     }
111     return 0;
112 }

View Code

M：

经过转化可以变成判断凸包是否相交的题。

  1 #include <cstdio>
  2 #include <vector>
  3 #include <iostream>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 const int N = 105;
  8 
  9 int n;
 10 
 11 int sgn(long long x) {
 12     return (x > 0) - (x < 0);
 13 }
 14 
 15 struct P {
 16     long long d[3];
 17     long long &operator[](int x) {
 18         return d[x];
 19     }
 20     P () {}
 21     P (long long a, long long b, long long c) {
 22         d[0] = a; d[1] = b; d[2] = c;
 23     }
 24 };
 25 
 26 struct node {
 27     P x;
 28     int y;
 29 } p[N];
 30 
 31 P operator+(P a, P b) {
 32     P c;
 33     for (int i = 0; i < 3; i++)
 34         c[i] = a[i] + b[i];
 35     return c;
 36 }
 37 
 38 P operator-(P a, P b) {
 39     P c;
 40     for (int i = 0; i < 3; i++)
 41         c[i] = a[i] - b[i];
 42     return c;
 43 }
 44 
 45 P operator*(int a, P b) {
 46     P c;
 47     for (int i = 0; i < 3; i++)
 48         c[i] = a * b[i];
 49     return c;
 50 }
 51 
 52 bool operator<(P a, P b) {
 53     return a[1] < b[1] || (a[1] == b[1] && a[2] < b[2]);
 54 }
 55 
 56 long long operator*(P a, P b) {
 57     return a[1] * b[2] - a[2] * b[1];
 58 }
 59 
 60 long long operator^(P a, P b) {
 61     return a[1] * b[1] + a[2] * b[2];
 62 }
 63 
 64 long long det(P a, P b, P c) {
 65     return (b - a) * (c - a);
 66 }
 67 
 68 struct L {
 69     P a, b;
 70     L () {}
 71     L (P x, P y) {
 72         a = x; b = y;
 73     }
 74 };
 75 
 76 bool onSeg(P p, L s) {
 77     return sgn(det(p, s.a, s.b)) == 0 && sgn((s.a - p) ^ (s.b - p)) <= 0;
 78 }
 79 
 80 vector<P> convex(vector<P> p) {
 81     vector<P> ans, S;
 82     for (int i = 0; i < p.size(); i++) {
 83         while (S.size() >= 2
 84                 && sgn(det(S[S.size() - 2], S.back(), p[i])) <= 0)
 85             S.pop_back();
 86         S.push_back(p[i]);
 87     }
 88     ans = S;
 89     S.clear();
 90     for (int i = (int)p.size() - 1; i >= 0; i--) {
 91         while (S.size() >= 2
 92                 && sgn(det(S[S.size() - 2], S.back(), p[i])) <= 0)
 93             S.pop_back();
 94         S.push_back(p[i]);
 95     }
 96     for (int i = 1; i + 1 < S.size(); i++)
 97         ans.push_back(S[i]);
 98     return ans;
 99 }
100 
101 bool PointInPolygon(P p, vector<P> poly) {
102     int cnt = 0;
103     for (int i = 0; i < poly.size(); i++) {
104         if (onSeg(p, L(poly[i], poly[(i + 1) % poly.size()]))) return true;
105         int k = sgn(det(poly[i], poly[(i + 1) % poly.size()], p));
106         int d1 = sgn(poly[i][2] - p[2]);
107         int d2 = sgn(poly[(i + 1) % poly.size()][2] - p[2]);
108         if (k > 0 && d1 <= 0 && d2 > 0) cnt++;
109         if (k < 0 && d2 <= 0 && d1 > 0) cnt--;
110     }
111     if (cnt != 0) return true;
112     return false;
113 }
114 
115 bool SegmentIntersection(L l1, L l2) {
116     long long c1 = det(l1.a, l1.b, l2.a), c2 = det(l1.a, l1.b, l2.b);
117     long long c3 = det(l2.a, l2.b, l1.a), c4 = det(l2.a, l2.b, l1.b);
118     if (sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0) return true;
119     if (sgn(c1) == 0 && onSeg(l2.a, l1)) return true;
120     if (sgn(c2) == 0 && onSeg(l2.b, l1)) return true;
121     if (sgn(c3) == 0 && onSeg(l1.a, l2)) return true;
122     if (sgn(c4) == 0 && onSeg(l1.b, l2)) return true;
123     return false;
124 }
125 
126 bool ConvexHullDivide(vector<P> p1, vector<P> p2) {
127     for (int i = 0; i < p1.size(); i++)
128         if (PointInPolygon(p1[i], p2))
129             return false;
130     for (int i = 0; i < p2.size(); i++)
131         if (PointInPolygon(p2[i], p1))
132             return false;
133     for (int i = 0; i < p1.size(); i++)
134         for (int j = 0; j < p2.size(); j++)
135             if (SegmentIntersection(L(p1[i], p1[(i + 1) % p1.size()]), L(p2[j], p2[(j + 1) % p2.size()])))
136                 return false;
137     return true;
138 }
139 
140 bool check() {
141     vector<P> p1, p2;
142     for (int i = 1; i <= n; i++) {
143         if (p[i].y == 1)
144             p1.push_back(p[i].x);
145         else
146             p2.push_back(p[i].x);
147     }
148     vector<P> c1, c2;
149     c1 = convex(p1);
150     c2 = convex(p2);
151     if (ConvexHullDivide(c1, c2)) return true;
152     return false;
153 }
154 
155 int f(P w, P x) {
156     long long sum = 0;
157     for (int i = 0; i < 3; i++)
158         sum += w[i] * x[i];
159     return sgn(sum);
160 }
161 
162 void PLA() {
163     P w = P(0, 0, 0);
164     int i = 1, cnt = 0;
165     long long cc = 0;
166     while (true) {
167         cc++;
168         if (f(w, p[i].x) != p[i].y) {
169             w = w + p[i].y * p[i].x;
170             cnt = 0;
171         } else {
172             if (++cnt == n) break;
173         }
174         i = i + 1;
175         if (i > n) i -= n;
176     }
177     cout << cc << endl;
178 }
179 
180 int main() {
181     int testcase;
182     cin >> testcase;
183     while (testcase--) {
184         cin >> n;
185         for (int i = 1; i <= n; i++) {
186             cin >> p[i].x[1] >> p[i].x[2] >> p[i].y;
187             p[i].x[0] = 1;
188         }
189         if (!check())
190             puts("Infinite loop!");
191         else {
192             puts("Successful!");
193         }
194     }
195     return 0;
196 }

View Code

隔壁队通过不停地random x1和x2来初步判断b的可能取值范围，也一样过了。天秀。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define mp(a,b) make_pair(a,b)
 5 #define ff first
 6 #define ss second
 7 typedef pair<int,int> pii;
 8 int a[110],b[110],c[110];
 9 int main(){
10     int t;scanf("%d",&t);
11     while(t--){
12         int n;scanf("%d",&n);
13         for(int i=1;i<=n;i++)
14             scanf("%d%d%d",&a[i],&b[i],&c[i]);
15         int ok=0;
16         for(int p=1;p<=1500;p++){
17             int w1=2*rand()-RAND_MAX,w2=2*rand()-RAND_MAX;
18             ll minb=-1e18,maxb=1e18;
19             for(int i=1;i<=n;i++){
20                 ll s=w1*a[i]+w2*b[i];
21                 if(c[i]==1)minb=max(minb,1-s);
22                 else maxb=min(maxb,1-s);
23             }
24             if(minb<=maxb){
25                 ok++;break;
26             }
27         }
28         if(!ok)printf("Infinite loop!
");
29         else printf("Successful!
");
30     }
31 }

code via. lzh

参考：https://www.cnblogs.com/songorz/p/11229659.html