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

有个傻逼二分没看出来，刚正面疯狂白给，大锅。
没补的题给出STD，以后再慢慢补。
A：
dp。

文章图片

文章图片

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

STD B：
原题是codeforces 1100F。比较暴力的做法是线段树维护线性基，但是时间复杂度会挂掉。
题解给了个技巧：贪心地维护序列的前缀线性基(上三角形态)，对于每个线性基，将出现位置靠右的数字尽可能地放在高位，也就是说在插入新数字的时候，要同时记录对应位置上数字的出现位置，并且在找到可以插入的位置的时候，如果新数字比位置上原来的数字更靠右，就将该位置上原来的数字向低位推。在求最大值的时候，从高位向低位遍历，如果该位上的数字出现在询问中区间左端点的右侧且可以使答案变大，就异或到答案里。
对于线性基的每一位，与它异或过的线性基更高位置上的数字肯定都出现在它右侧(否则它就会被插入在那个位置了)，因此做法的正确性显然。

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

文章图片

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

View Code C：
离散化+背包

文章图片

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

View Code D：
一开始就想到了题解里用堆维护撞车事件的做法，想法正确且显然，时间复杂度O(nlogn)。唯一的难点在于非常难写。
直到比赛结束我都没意识到这题可以二分……不应该。

文章图片

1 /* basic header */ 2 #include 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= 0; i--) { // 遍历前面的每一辆车 30// 如果前一辆车行驶x时间之后离stopline的距离比最前面的车行驶x时间之后离stopline的距离塞下下一辆车还短 31// 那么当前这辆车一定不会和身后的车相撞，那么允许后面的车走过stopline 32if (car[i].s - car[i].v * x <= currS + car[i + 1].l) currS += car[i + 1].l; 33else currS = car[i].s - car[i].v * x; // 否则会相撞，答案更新为当前的车在前面无阻碍的情况下行驶x时间离stopline的距离 34} 35return currS <= eps; // 如果小于等于0，说明行驶x时间后必然可以到达stopline 36 } 37 38 int main() { 39while (~scanf("%d", &n)) { 40rep1(i, 0, n) scanf("%d", &car[i].l); 41rep1(i, 0, n) scanf("%d", &car[i].s); 42rep1(i, 0, n) scanf("%d", &car[i].v); 43double l = 0, r = 1e18; // 二分到达时间 44while (r - l > eps) { 45double mid = (l + r) / 2; 46if (check(mid)) r = mid; 47else l = mid; 48} 49printf("%.6f\n", r); 50} 51return 0; 52 }

View Code E：
从一开始就很多人过的题，但由于solo训练所以甩锅给队友(
网络流求最小割模板题。

文章图片

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

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

文章图片

#includetypedef 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 << '\n' ; } return 0; }

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

文章图片

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

View Code H：
仙人掌相关题。分治+fft。

文章图片

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

View Code I：
【2019|2019 HDOJ Multi-University Training Contest Stage 1(杭电多校)】一位位地构造答案字符串，每次贪心地加能加入的最小的字符(判断能否加入只要判断加入之后原字符串剩下的后缀中的每种字符的数目能否足够满足条件)。

文章图片

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

STD J：
记忆化搜索。

文章图片

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

View Code K：
数论反演。

文章图片

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

View Code L：
推式子数论题。NTT。

文章图片

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

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

文章图片

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

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

文章图片

1 #include 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 pii; 8 int a[110],b[110],c[110]; 9 int main(){ 10int t; scanf("%d",&t); 11while(t--){ 12int n; scanf("%d",&n); 13for(int i=1; i<=n; i++) 14scanf("%d%d%d",&a[i],&b[i],&c[i]); 15int ok=0; 16for(int p=1; p<=1500; p++){ 17int w1=2*rand()-RAND_MAX,w2=2*rand()-RAND_MAX; 18ll minb=-1e18,maxb=1e18; 19for(int i=1; i<=n; i++){ 20ll s=w1*a[i]+w2*b[i]; 21if(c[i]==1)minb=max(minb,1-s); 22else maxb=min(maxb,1-s); 23} 24if(minb<=maxb){ 25ok++; break; 26} 27} 28if(!ok)printf("Infinite loop!\n"); 29else printf("Successful!\n"); 30} 31 }

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

转载于:https://www.cnblogs.com/JHSeng/p/11232235.html