【感谢牛老板对D题的指点OTZ】
codeforces 842 A. Kirill And The Game【暴力】
给定a的范围[l,r]，b的范围[x,y]，问是否存在a/b等于k。直接暴力判断即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll l, r, x, y, k;
int main() {
bool f;
while(~scanf("%lld%lld%lld%lld%lld", &l, &r, &x, &y, &k)) {
f = ;
for(ll i = x; i <= y; ++i) {
if(i * k >= l && i * k <= r) {
f = ; break;
}
}
if(f) puts("YES");
else puts("NO");
}
return ;
}
31ms
codeforces 842 B. Gleb And Pizza【几何水题】
已知大圆圆心在原点，半径为r，其中外壳厚度为d，给出n个小圆的位置和半径，问有多少个小圆包含在外壳上。水题。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int r, d, x, y, rr, n;
int main() {
bool f;
while(~scanf("%d%d", &r, &d)) {
int cnt = ;
int s1 = (r-d), s2 = r;
scanf("%d", &n);
while(n--) {
scanf("%d%d%d", &x, &y, &rr);
double a = sqrt(x*x+y*y);
if(s1+rr <= a && a <= s2-rr)
cnt++;
}
printf("%d\n", cnt);
}
return ;
}
62ms
codeforces 842 C. Ilya And The Tree【DFS】
题意：给一棵树，根为1，每个节点有一个值，每个节点的美丽值为该节点到根的路径上所有节点的最大公约数，现在要求每个节点的美丽值。每个节点的求解，可以将任意一个节点的值改变为0或者不做任何改变。
题解：从根DFS，用set存储每个节点到根节点的gcd值，记录路径节点都不做改变的gcd值val，往下一个节点走时，若要将节点值置零，直接向set插入val即可，继续操作。最后答案即为每个节点的set的最后一个值（set默认升序排序的）。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
const int N = 2e5+;
int n;
int a[N];
vector<int>g[N];
set<int>s[N];
set<int>::iterator it;
int gcd(int a, int b) {return b?gcd(b, a%b):a;}
void dfs(int u, int fa, int val) {
for(it = s[fa].begin(); it != s[fa].end(); ++it) s[u].insert(gcd(*it, a[u]));
s[u].insert(val);
val = gcd(val, a[u]);
for(int i = ; i < g[u].size(); ++i) if(g[u][i] != fa) dfs(g[u][i], u, val);
}
int main() {
int i, j, x, y;
while(~scanf("%d", &n)) {
for(i = ; i <= n ;++i) {g[i].clear();s[i].clear();}
for(i = ; i <= n; ++i)scanf("%d", &a[i]);
for(i = ; i <= n-; ++i) {
scanf("%d%d", &x, &y);
g[x].push_back(y); g[y].push_back(x);
}
s[].insert();
dfs(, , );
for(i = ; i <= n; ++i)
printf("%d ", *s[i].rbegin());
puts("");
}
return ;
}
311ms
未完待续，，，
codeforces 842 D. Vitya and Strange Lesson【trie+贪心】
题意：mex为一个序列中没出现的非负最小值，现在序列有n个数，有m个询问，每个询问给一个数，将序列中每个数与x异或，然后查询序列的mex值。
题解：其实就是相当于求没出现的数与x异或的最小值。将序列没出现的数以二进制形式插入trie树中，树上跑x异或的最小值，贪心地让某位的值与x对应的位的值相同即可。
//yy：一开始字典树大小开小了，结果郁闷了很久。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long ll;
const int N = ;
const int M = 3e5+;
int n, m;
struct Trie {
int next[];
int v;
void init() {
v = ;
memset(next, -, sizeof(next));
}
}T[N*M*];
int le;
void inser(int x) {
int p = ;
for(int i = N-; i >= ; --i) {
int t = (x>>i) & ;
if(T[p].next[t] == -) {
T[le].init();
T[p].next[t] = le++;
}
p = T[p].next[t];
}
T[p].v = x;
}
void query(int x) {
int i = , p = ;
for(int i = N-; i >= ; --i) {
int t = (x>>i) & ;
if(T[p].next[t] == -) p = T[p].next[t^];
else p = T[p].next[t];
}
printf("%d\n", x ^ T[p].v);
}
bool a[<<N];
int main() {
int i, x, y;
while(~scanf("%d%d", &n, &m)) {
CLR(a, );
for(i = ; i <= n; ++i) {scanf("%d", &x); a[x] = ;}
le = ; T[].init();
for(i = ; i <= (<<N)-; ++i) if(!a[i]) inser(i);
y = ;
while(m--) {
scanf("%d", &x);
y ^= x;
query(y);
}
}
return ;
}
234ms