odeforces Round 700 (Div. 1)
https://codeforces.com/contest/1479
A. Searching Local Minimum
题意:交互题。有一个排列,最多 100 次询问,找到排列中的极小值。每次询问返回询问位置的值。
三分
三分必定能够找到一个极值。
123456789101112131415161718192021222324252627282930313233343536#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define ll long long#define ull unsigned llconst int N = 2e6 + 5;const int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const ll mod = 1e9 + 7;const ll inv2 = (mod + ...
Codeforces Round 698 (Div. 1)
http://codeforces.com/contest/1477
C. Nezzar and Nice Beatmap
题意:给定二维平面上 nnn 个点,要求排列,使得相邻三个点以中间的那个点为中心点构成的夹角为锐角。
构造
首先要发现对于三个点 A,B,C,如果此时不是锐角,则交换任意一对相邻点,变成 A,C,BA,C,BA,C,B 或者 B,A,CB,A,CB,A,C,都是锐角,因为三角形里最多只会有一个非锐角。
那么就可以在加入点的同时调整已有点。
例如已有 A,B,C,DA,B,C,DA,B,C,D,先直接加入 EEE,发现 C,D,EC,D,EC,D,E 为钝角,则调整为 A,B,C,E,DA,B,C,E,DA,B,C,E,D,此时又发现 B,C,EB,C,EB,C,E 为钝角,再调整为 A,B,E,C,DA,B,E,C,DA,B,E,C,D,又发现 A,B,EA,B,EA,B,E 为钝角,再调整为 A,E,B,C,DA,E,B,C,DA,E,B,C,D,这样一定就不会再有钝角了。
123456789101112131415161718192021222324252 ...
Codeforces Round 696 (Div. 2)
http://codeforces.com/contest/1474
C. Array Destruction
题意:给定一个数组。先选择一个数 x,再从数组中选择两个和为 x 的数,从数组中删去,并 x 变成这两个数中大的那个。问是否可行,以及每一步的选择。
最开始的用来合成 x 的两个数中,必定有一个是数组中最大的数,否则它以后就用不到了。所以只需要再枚举另一个数。
这样就已知 x 与两个数中大的那个数了,之后的每一步就都是可以模拟下去的了。
所以对每一次枚举,O(n)O(n)O(n) 模拟进行验证。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define l ...
Codeforces Round 694 (Div. 1)
http://codeforces.com/contest/1470
D. Strange Housing
题意:给定一张无向图,要求对一些点染色,再保留包含染色点的边,满足新图包含所有原图上的点且连通,且新图上每条边恰有一个染色点。
生成树
先求出任意一个生成树,dfs,如果与它相邻的点没有被染色的,则染它。
显然这样不会有边两端点都染色。再证明必定包含所有点且联通。
假设不连通,有两个连通块,则生成树必定有一条边的两个端点都未染色。设为 u,v,fa[v]=uu,v,fa[v]=uu,v,fa[v]=u,uuu 由于某种原因未染色,当dfs到 vvv 时,不染 vvv 必定是因为之前被dfs过的点中存在 被染色且与 vvv 在原图上相连的点,而这个点必定是 vvv 的子树外的点,所以 vvv 的子树必定已经与其它点连通了。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include <bits/stdc ...
Codeforces Round 691 (Div. 1)
http://codeforces.com/contest/1458
B. Glass Half Spilled
题意:有 nnn 杯水,每杯最大容量为 aia_iai,杯中已经有了 bib_ibi 的水,可以从任意杯中倒水至任意杯中,每次倒水时会洒出一半,问对于每个 1≤i≤n1\le i\le n1≤i≤n,选择 iii 杯,最多能有多少水。
dp
起初一直想着直接dp出答案,但是这样需要很多分类讨论,而且还涉及到小数的问题。
但是可以换一种思路,在dp时先不倒水,dp[i][j][k]dp[i][j][k]dp[i][j][k] 表示前 iii 杯,选择 jjj 杯,选中的杯子的总容量为 kkk 的最大水量。
则转移就很简单了 dp[i][j][k]=dp[i−1][j][k]dp[i][j][k]=dp[i-1][j][k]dp[i][j][k]=dp[i−1][j][k] 不选当前杯子,dp[i][j][k]=dp[i−1][j−1][k−a[i]]+b[i]dp[i][j][k]=dp[i-1][j-1][k-a[i]]+b[i]dp[i][j][k]=dp[i−1 ...
Codeforces Round 684 (Div. 1)
http://codeforces.com/contest/1439
A2. Binary Table (Hard Version)
题意:给定一个01矩阵,每次操作选择一个 2∗22*22∗2 的区域,翻转其中 3 个。要求在 nmnmnm 次操作内把矩阵变为全 0.
构造
观察发现对于一个 2∗22*22∗2 的区域,总可以用不超过 4 次操作把所有点变为 0.
所以如果 n,mn,mn,m 都为偶数,可以对一些不重叠的 2∗22*22∗2 的区域分别操作变为全 0.
上限 nmnmnm 的本质是不超过一次操作把一点变为 0.
如果 n,mn,mn,m 为奇数,则先处理掉一行一列,再用偶数的方法做。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899#in ...
Codeforces Round 683 (Div. 1)
http://codeforces.com/contest/1446
C. Xor Tree
题意:给定一个n个数都不相同的数列,每个数和另一个数相连无向边,满足它与另一个数的异或值小于它与其它数的异或值,两个数互相连边算作连一次。要求删去最少的数,使得得到一棵树。
字典树
试一下就能发现不会成环,所以要形成树只要满足只有一对点互相连边。
把所有数都插进Trie里,对于节点 u,它的左子树里的所有节点必定只会与左子树中点相连,所以如果左子树中选择了大于等于2个点,则这两个点必定会形成一条互相的连边。而如果左子树只选一个点,则这个点不会形成互相的连边。
Trie上dp
ans[u]=max(ans[lson(u)]+1,ans[rson(u)]+1)ans[u]=\max(ans[lson(u)]+1,ans[rson(u)]+1)ans[u]=max(ans[lson(u)]+1,ans[rson(u)]+1)。
如果只有左子树或只有右子树,则 ans[u]=ans[lson(u)]ans[u]=ans[lson(u)]ans[u]=ans[lson(u)]。
如果是叶子,则返回 ...
Codeforces Round 682 (Div. 2)
http://codeforces.com/contest/1438
C. Engineer Artem
题意:给定一个矩阵,对每个数可以+1一次或者不动,要构造出每个数和相邻的四个数都不同。
构造
当遇到需要两个数不同时,可以考虑变成一奇一偶。
而一次+1操作恰好可以改变奇偶性。
把矩阵变成奇偶交错的情况。
123456789101112131415161718192021222324252627282930#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define ll long longconst int N = 2e6 + 10;const int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const ll mod = 998244353;int T;int n, m;int a[110][ ...
Codeforces Round 679 (Div. 2)
http://codeforces.com/contest/1435
C. Perform Easily
题意:6 个数,分别为 aia_iai,有 n 个数的数组 bbb,对每个数,选择一个 aaa,得到 ci=bi−ajc_i=b_i-a_jci=bi−aj,要使得 ccc 的最大值和最小值之差最小。
尺取法
把这 6n6n6n 个数从小到大排列,只要一个区间满足有 n 种不同的 b,则满足条件,这时就可以和答案比较。
123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h>using namespace std;#define ll long long#define debug(x) cout<<#x<<":\t"<<xconst int N = 2e6 + 10;const int INF = 0x3f3f3f3f;int a[10];int n;int b[N];int ...
Codeforces Round 678 (Div. 2)
http://codeforces.com/contest/1436
D. Bandit in a City
题意:给定一棵有根树,以1为根。每个点有一些人,这些人最终都走到叶子,要使得包含人最多的叶子上包含的人数最少。
这就是要求均分,且每个点只能向子孙分配。
树上的均分可以从下向上遍历,同时求均值,这样就能保证那些本来就很多,而又没法向其它点分配的点均值不会变小。
1234567891011121314151617181920212223242526272829303132333435#include <bits/stdc++.h>using namespace std;#define ll long long#define debug(x) cout<<#x<<":\t"<<xconst int N = 2e6 + 10;const int INF = 0x3f3f3f3f;const ll mod = 1e9 + 7;int n;vector<int>G[N];ll a[N],sum[N],cn ...