Codeforces Round #430 (Div. 2) 题解

题目链接：http://codeforces.com/contest/842

A. Kirill And The Game

题意：很迷。解法：将x到y上的每一个数字都乘上k，只要有一个数字大于l并且小于r，就可以yes，如果一个都没有，就NO

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    LL l,r,x,y,k;
    scanf("%lld %lld %lld %lld %lld", &l,&r,&x,&y,&k);
    for(LL i=x; i<=y; i++){
        if(l<=i*k&&i*k<=r){
            puts("YES");
            return 0;
        }
    }
    puts("NO");
    return 0;
}

B. Gleb And Pizza

题意：判断在半径为r-d的圆和半径为r的圆之间的圆有多少个，可以相切。

解法：暴力判断即可。

#include <bits/stdc++.h>
using namespace std;
double getdis(double x1, double x2, double y1, double y2){
    return sqrt((y2-y1)*(y2-y1)+(x2-x1)*(x2-x1));
}
double r, d;
int n;
int main(){
    cin >> r >> d;
    cin >> n;
    int ans = 0;
    for(int i=0; i<n; i++){
        double x, y, rr;
        cin >> x >> y >> rr;
        if(getdis(0,x,0,y)>=(r-d+rr) && r >= getdis(0,x,0,y)+rr){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

C. Ilya And The Tree

题意：给出一棵生成树，每个节点都有一个值，现在要求出每个节点的美丽值的最大值，美丽值的定义为从根节点到该节点(包含)路径上所有点的值的gcd，求解每个点时可以把路径上某一个点的值变为0。你可以认为每个点美丽值的求解是独立的。

解法：

我们用dp数组来保存每个节点在路径上没有改变值的时候的gcd，然后先单独考虑当前点不选的美丽值即dp[u]。然后用vector[u]数组来保存节点v的父亲节点的美丽值的所有可能情况，这里的情况有可能是改变了值后的，也可能没有，但由于我们在这一步一定会算入节点v的值(不算的情况单独考虑)，所以满足最多只改变一次值的要求。每次更新完后去重一下，提高时间效率以及避免超内存等等！

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int head[maxn],edgecnt;
vector <int> G[maxn];
int n, a[maxn], dp[maxn];
struct EDGE{
    int to,next;
}E[maxn*2];
void init(){
    edgecnt=0;
    memset(head,-1,sizeof(head));
}
void add(int u,int v){
    E[edgecnt].to = v,E[edgecnt].next=head[u],head[u]=edgecnt++;
}
void dfs(int u, int fa){
    for(int i=head[u]; ~i; i=E[i].next){
        int v=E[i].to;
        if(v == fa) continue;
        dp[v] = __gcd(dp[u], a[v]);
        G[v].push_back(dp[u]);
        for(int i=0; i<G[u].size(); i++){
            G[v].push_back(__gcd(G[u][i], a[v]));
        }
        sort(G[v].begin(), G[v].end());
        G[v].erase(unique(G[v].begin(),G[v].end()),G[v].end());
        dfs(v, u);
    }
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    init();
    for(int i=1; i<n; i++){
        int u,v;
        scanf("%d %d", &u,&v);
        add(u, v);
        add(v, u);
    }
    dp[1] = a[1];
    G[1].push_back(0);
    dfs(1, -1);
    for(int i=1; i<=n; i++){
        printf("%d ", max(dp[i], G[i].back()));
    }
    printf("\n");
    return 0;
}

D. Vitya and Strange Lesson

题意：数列里有n个数，m次操作，每次给x，让n个数都异或上x。并输出数列的mex值。

解法：01字典树保存每个节点下面有几个数，然后当前总异或的是ans，则ans为1的位的节点左右孩子交换（不用真的交换）。左孩子的值小于左边总节点数则mex在左子树，否则在右子树。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 530010;
int n, m, ans;
namespace Trie{
    int ch[maxn*20][2];
    int cnt[maxn*20];
    int sz;
    void Build(int node, int pos){
        if(pos < 0) return;
        for(int i=0; i<2; i++){
            ch[node][i] = ++sz;
            cnt[sz] = 0;
            Build(ch[node][i], pos-1);
        }
    }
    void init(){
        sz = 0;
        Build(0, 19);
    }
    void insert(int node, int pos, int num){
        if(pos < 0){
            cnt[node] = 1;
            return;
        }
        insert(ch[node][(num>>pos)&1], pos-1, num);
        cnt[node] = cnt[ch[node][0]] + cnt[ch[node][1]];
    }
    int query(int node, int pos, int num){//query mex
        if(pos < 0) return num;
        int lson = (ans&(1<<pos))?1:0;
        if(cnt[ch[node][lson]]<(1<<pos)){
            return query(ch[node][lson], pos-1, num);
        }
        else{
            return query(ch[node][!lson], pos-1, num+(1<<pos));
        }
    }
}
using namespace Trie;
int main()
{
    ans = 0;
    init();
    scanf("%d %d", &n,&m);
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d", &x);
        insert(0, 19, x);
    }
    for(int i=1; i<=m; i++){
        int x;
        scanf("%d", &x);
        ans ^= x;
        printf("%d\n", query(0, 19, 0));
    }
    return 0;
}

E. Nikita and game

题意：每次加入一个点之后，问多少个点可以作为直径的端点。

解法：不会，膜了一发题解。http://blog.csdn.net/cys460714380/article/details/77760526

具体解法如下：描述来自上面的博客。

一条直径有两端考虑把直径的端点分为两部分（被直径中点分开）

那么只要维护两端的直径端点就可以了当加入一个新点的时候检查是否更新了直径如果更新了直径那它就会成为直径一端的唯一一个点
然后看他是到左边的那些端点长还是到右边那些端点长
假如是左边那左边的点都是另一端的点
再检查一下到右边的点的距离有没有跟新直径一样的将它加入另一端的集合如果没更新则检查最大距离是否与直径相同
相同则加入相应一端的集合中

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
int n, fa[maxn][20], dep[maxn];
int lca(int a, int b){
    int res = 0;
    if(dep[a]<dep[b]) swap(a, b);
    int d = dep[a]-dep[b];
    for(int i=18; i>=0; i--){
        if((d>>i)&1){
            a = fa[a][i];
            res += 1<<i;
        }
    }
    if(a == b) return res;
    for(int i=18; i>=0; i--){
        if(fa[a][i] != fa[b][i]){
            res += 1<<(i+1);
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return res+2;
}

int main()
{
    scanf("%d", &n);
    set <int> s1, s2;
    s1.insert(1);
    dep[1] = 1;
    int mx = 1;
    for(int v = 2; v<=n+1; v++){
        int u;
        scanf("%d", &u);
        fa[v][0] = u;
        dep[v] = dep[u]+1;
        for(int i=1;(1<<i)<dep[v]; i++) fa[v][i]=fa[fa[v][i-1]][i-1];
        int dis1 = s1.empty()?0:lca(v, *s1.begin());
        int dis2 = s2.empty()?0:lca(v, *s2.begin());
        if(max(dis1,dis2)>mx){
            mx = max(dis1,dis2);
            if(dis1==mx){
                for(set<int>::iterator it=s2.begin(); it!=s2.end(); it++){
                    if(lca(*it, v) == mx) s1.insert(*it);
                }
                s2.clear();
                s2.insert(v);
            }
            else{
                for(set<int>::iterator it=s1.begin(); it!=s1.end(); it++){
                    if(lca(*it, v) == mx) s2.insert(*it);
                }
                s1.clear();
                s1.insert(v);
            }
        }
        else if(max(dis1,dis2)==mx){
            if(dis1>=dis2) s2.insert(v);
            else s1.insert(v);
        }
        int sz = s1.size()+s2.size();
        printf("%d\n", sz);
    }
    return 0;
}