- 博客(242)
- 收藏
- 关注
RSS订阅
原创 Atcoder Grand Contest 034 简要题解
Kenken Race考虑两个人不互相影响的情况，显然只需要判断是否存在两个相邻的障碍即可；当原来在前面的人要走到后面时，需要存在三个连续的空位来跳过去。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 freopen("input.txt", "r", stdin);...
2019-06-06 20:38:33
1691
2
原创 Atcoder Grand Contest 033 简要题解
A - Darker and Darker多源最短路。#include <bits/stdc++.h>using namespace std;const vector<int> dx = {1, 0, -1, 0};const vector<int> dy = {0, 1, 0, -1};int main() {#ifdef wxh01091...
2019-05-06 20:01:03
999
原创 CodeForces Gym 102055 简要题解
Mischievous Problem Setter模拟。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 freopen("input.txt", "r", stdin);#endif ios::sync_with_stdio(false); cin.tie(0...
2019-04-22 08:02:03
1927
原创 HNOI 2019 简要题解
fish枚举 ADADAD ， BCBCBC 的限制相当于 ADADAD 是 BCBCBC 中垂线且 BCBCBC 中点在 ADADAD 上，预处理所有中垂线，排序之后二分即可；EFEFEF 的限制可以双指针扫一下。#include <bits/stdc++.h>using namespace std;struct point { int x, y; point(...
2019-04-15 19:42:16
1118
原创 ZJOI 2019 Day 1 简要题解
mahjong期望和牌巡数等于对于所有 i≥0i\ge 0i≥0 ，摸了 iii 张牌仍然没和的概率之和。考虑如何DP一堆牌是否能和，七对子可以直接把对子记下来，而普通的集合需要跑一个DP，记 f(i,a,b,c)f(i, a,b,c)f(i,a,b,c) 表示考虑前 iii 张，aaa 表示是否有雀头， bbb 表示 i−2,i−1,ii-2,i-1,ii−2,i−1,i 的顺子个数， ccc...
2019-04-12 21:14:44
744
原创 十二省联考 2019 简要题解
xor暴力。#include <bits/stdc++.h>using namespace std;typedef unsigned int uint;const int N = 523456;const int M = 22345678;struct node { int l, r, s;} trie[M];priority_queue<pair...
2019-04-11 15:44:52
1054
原创 CodeForces Gym 102156 简要题解
Takeover每次贪心选增量最小的。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 freopen("input.txt", "r", stdin);#endif ios::sync_with_stdio(false); cin.tie(0); cout....
2019-04-02 16:49:49
4836
原创 Atcoder Grand Contest 032 简要题解
Limited Insertion考虑最后一次操作，一定是当前序列中最后一个合法的位置（删前面会导致这个位置以后都不合法），模拟即可。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 freopen("input.txt", "r", stdin);#endif io...
2019-03-24 15:17:07
593
原创 JOI Spring Camp 2019 简要题解
Day 1examination直接上三维数点就能过，也可以容斥一下变成二维数点。#include <bits/stdc++.h>using namespace std;template<typename T>class fenwick { public: vector<T> fenw; int n; fenwick(int n)...
2019-03-23 16:17:41
1076
原创 CodeForces Gym 102129 简要题解
Tritwise Mexc0=a1b2+a2b1+a1b1+a2b2c_0 = a_1b_2 + a_2b_1 + a_1b_1 + a_2b_2c0=a1b2+a2b1+a1b1+a2b2c1=a0b2+a2b0+a0b0c_1 = a_0b_2 + a_2b_0 + a_0b_0c1=a0b2+a2b0+a0b0c2=a0b1+a1b0c_2 = a_0b...
2019-03-20 21:11:17
1286
1
原创 Atcoder Grand Contest 031 简要题解
Colorful Subsequence对于每种字符，其要么不选，要么选择一个，所以答案是 ∏(cnti−1)−1\prod (cnt_i-1)-1∏(cnti−1)−1 。#include <bits/stdc++.h>using namespace std;const int md = (int) 1e9 + 7;inline int mul(int x, int...
2019-03-17 19:35:35
785
原创 CodeForces Gym 102056 简要题解
Exotic … Ancient City注意到值域很小，所以可以对每种 www 数只考虑 ≤w\le w≤w 的边的连通块个数。维护一个大小为 2n2n2n 的并查集，表示第 iii 列和第 i+1i+1i+1 列的连通性。考虑右移一列并查集的变化，如果在之前的并查集合并了集合 u+n,v+nu+n, v+nu+n,v+n ，那么在新的并查集上 uuu 和 vvv 会变得连通。如果它们已经连通...
2019-01-09 10:44:59
3427
原创 Atcoder Grand Contest 030 简要题解
Poisonous Cookies答案是 b+min(c,a+b+1)b+\min(c,a+b+1)b+min(c,a+b+1) 。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 freopen("input.txt", "r", stdin);#endif in...
2018-12-30 17:56:32
717
原创 CodeForces Gym 102028 简要题解
Xu Xiake in Henan Province模拟。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 freopen("input.txt", "r", stdin);#endif int tt; scanf("%d", &tt); while ...
2018-12-19 16:46:18
2809
原创 Atcoder Grand Contest 029 简要题解
Irreversible operation求逆序对。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 freopen("input.txt", "r", stdin);#endif string s; cin >> s; long long an...
2018-12-16 15:18:06
1008
原创 CodeForces Gym 102012 简要题解
Rikka with Minimum Spanning Trees因为数据随机，所以MST只有 111 种。注意特判不连通的情况。#include <bits/stdc++.h>using namespace std;typedef unsigned long long ull;const int N = 123456;const int md = 1e9 + 7;...
2018-12-11 10:13:45
6558
原创 CodeForces 1089 简要题解
Alice the Fan预处理 f(wina,winb,scorea,scoreb)f(win_a, win_b, score_a, score_b)f(wina,winb,scorea,scoreb) 表示这个状态能不能到达然后倒着输出方案就行了。#include &lt;bits/stdc++.h&gt;using namespace std;const int N = ...
2018-12-07 17:24:44
1296
原创 CodeForces Gym 101955 简要题解
Sockpuppets建出trie树，那么匹配的东西一定是祖先关系。记 f(x,a,b)f(x,a,b)f(x,a,b) 表示考虑了 xxx 的子树，祖先有 aaa 个小号匹配子树，子树有 bbb 个小号匹配祖先的方案数，背包转移即可。#include <bits/stdc++.h>using namespace std;const int N = 23456;cons...
2018-11-25 14:09:17
1993
2
原创 CodeForces Gym 101981 简要题解
Adrien and Austin特判 n=0n=0n=0 或者 k=1k=1k=1 的情况，当 k&gt;1k&gt;1k>1 的时候，先手取中间，然后后手不管取什么先手取相对的，所以先手必胜。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 fre...
2018-11-21 21:35:38
1691
原创 CodeForces Gym 101978 简要题解
Contest Environment如果第二行有障碍，那么一定无解。否则考虑将 AAA 移过去，对于连续的一段障碍，他需要直接跨越，然后其他人可以任意分配，像这样：*#*A#.B***...*不难发现条件是 . 个数大于等于连续的一段 # 的个数加 333 。#include <bits/stdc++.h>using namespace std;int main...
2018-11-08 08:06:44
554
原创 CodeForces 1070 M. Algoland and Berland
链接：link题意：平面上有 aaa 个红色点和 bbb 个蓝色点，没有三点共线，红蓝点之间可以连边，求一棵生成树，使得第 iii 个蓝点的度数恰好为 rir_iri ，并且生成树的连边在平面上不会在除了端点的地方相交。保证 ∑ri=a+b−1,1≤ri≤a\sum r_i = a+b-1, 1\le r_i\le a∑ri=a+b−1,1≤ri≤a 。题解：考虑用归纳法给出构造...
2018-10-23 10:14:14
487
1
原创 Atcoder Grand Contest 028 简要题解
Two Abbreviations答案要么是 −1-1−1 要么是 lcm(n,m)lcm(n, m)lcm(n,m) 。#include &amp;lt;bits/stdc++.h&amp;gt;using namespace std;int main() {#ifdef wxh010910 freopen(&quot;input.txt&quot;, &quot;r&quot;, stdin
2018-10-15 22:13:49
940
2
原创 CodeForces 1063F. String Journey
链接：link题意：定义一个字符串序列 ttt 是合法的，且仅当 tit_iti 是 ti−1t_{i-1}ti−1 的子串，并且 ti≠ti−1t_i\neq t_{i-1}ti̸=ti−1 。求一个最长的合法字符串序列 ttt ，满足存在一个字符串序列 uuu ，使得 s=u1+t1+u2+t2⋯+uk+tk+uk+1s = u_1 + t_1 + u_2 + t_2\cdo...
2018-10-15 16:04:31
518
原创 CodeForces 1045 简要题解
Last chance线段树优化连边，输出方案先输出容量为 222 的。#include <bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f3f;namespace flow {struct edge_t { int to, cap, rev; edge_t(int t, int c, in...
2018-09-25 20:06:59
847
原创 Japan Alumni Group Summer Camp 2018 Day 2 简要题解
10^N+7模拟。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 freopen("input.txt", "r", stdin);#endif int x, y, z; scanf("%d %d %d", &x, &y, &z); ...
2018-09-18 16:21:10
1674
原创 Atcoder Grand Contest 027 简要题解
Candy Distribution Again模拟。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 freopen("input.txt", "r", stdin);#endif int n, m; scanf("%d %d", &n, &m)...
2018-09-17 20:35:03
588
原创 CodeForces 1023G. Pisces
链接：link题意：有一棵 nnn 个点的树，有边权，进行了 kkk 次观察，每次观察是在第 didid_i 天在 pipip_i 点至少有 fifif_i 条鱼，鱼每天可以走一个单位，问最少有多少条鱼。题解：考虑 Dilworth 定理，求最长反链就行了。一个结论是，考虑子树 xxx 中的一个集合形成反链当且仅当：每个子树内部是反链。存在一个时刻 ttt ...
2018-09-11 10:07:41
1024
原创 CodeForces 1039E. Summer Oenothera Exhibition
链接:link题意：给一个长度为 nnn 的序列，qqq 次询问，每次给一个 kikik_i ，问最少将序列划分成多少段，满足每一段的极差不超过 w−kiw−kiw - k_i 。题解：这个问题是可以贪心的，所以可以对于一个起始位置，可以暴力或者倍增找它的下一个位置 nextinextinext_i 。为了方便我们将询问离线，按照 w−kiw−kiw - k_i 递增的...
2018-09-11 09:54:52
742
原创 Atcoder Grand Contest 026 简要题解
Colorful Slimes 2贪心。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 freopen("input.txt", "r", stdin);#endif int n; scanf("%d", &n); int last = -1...
2018-08-07 13:22:13
568
原创 CodeForces Gym 101635 简要题解
Cakey McCakeFace模拟。#include <bits/stdc++.h>using namespace std;int main() {#ifdef wxh010910 freopen("input.txt", "r", stdin);#endif int n, m; scanf("%d %d", &n, &m); ...
2018-07-12 15:44:23
951
原创 CodeForces Gym 101623 简要题解
Ascending Photo首先离散化，并将相邻的相同的数变成一个。考虑对值域从小到大DP，那么如果 iii 和 i+1i+1i+1 之间没有被切开那么 i+1i+1i+1 和 i+2i+2i+2 之间可能就必须切开，所以只需要维护DP值和上次决策点即可。不难发现只维护最大值和次大值就可以转移了。#include <bits/stdc++.h>using namesp...
2018-07-10 09:48:37
1033
原创 CodeForces Gym 101669 简要题解
Concertsf(i,j)f(i,j)f(i ,j) 表示最后一次匹配的位置 ≤i≤i\le i ，匹配了 jjj 个位置的方案数。#include &lt;bits/stdc++.h&gt;using namespace std;const int N = 100005;const int M = 305;const int mod = 1e9 + 7;int n,...
2018-07-05 21:45:42
1730
原创 CodeForces 997 简要题解
Convert to Ones翻转操作实际就是合并两段 000 ，特判全 111 的情况，假设有 kkk 段 000 ，答案是 (k−1)min(x,y)+y(k−1)min(x,y)+y(k - 1)\min(x, y) + y 。#include &lt;bits/stdc++.h&gt;using namespace std;typedef long long ll;...
2018-07-02 16:07:54
2324
1
原创 LOJ #6440. 万能欧几里得
链接：link题解：考虑处理 AxBAxB\frac{Ax}{B} ，作射线 y=ABxy=ABxy = \frac{A}{B}x ，从原点出发，碰到 y=cy=cy = c 记一个 111 ，碰到 x=cx=cx = c 记一个 000 ，然后要处理出每个 000 之前的 111 的个数。当 A<BA<BA < B 的时候，将 010101 互换变成 101010...
2018-06-29 16:00:22
1412
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人