CodeForces Round #287 Div.2

A. Amr and Music (贪心)

水题，没能秒切，略尴尬。

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 100 +10;
int a[maxn], r[maxn], ans[maxn];

int cmp(int i, int j) { return a[i] < a[j]; }

int main()
{
    //freopen("in.txt", "r", stdin);

    int n, k;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i) r[i] = i;
    for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
    sort(r, r + n, cmp);
    int sum = 0, cnt = 0;
    for(int i = 0; sum + a[r[i]] <= k && cnt < n; ++i)
    {
        sum += a[r[i]];
        ans[cnt++] = r[i];
    }

    printf("%d\n", cnt);
    for(int i = 0; i < cnt - 1; ++i) printf("%d ", ans[i]+1);
    if(cnt) printf("%d\n", ans[cnt-1]+1);

    return 0;
}

B. Amr and Pins (找规律)

题意：

给出一个圆的半径 和 圆心的始末位置。每次操作只能绕圆周上的点旋转若干角度。求该圆从初位置到末位置最少的操作次数。

分析：

不妨设圆的半径为r，圆心在原点处。

先看只旋转一次的情况，圆心所有可能位置构成的区域为  半径为2r的圆(除去圆心那点)，也可理解为半径为(0, 2r]的圆环区域

再看第二次旋转，其区域为半径在(2r, 4r]的圆环区域。　　//这个不容易画图，自行脑补一下好啦

以此类推。

算法：

所以我们可以先算出圆心始末位置间的距离d，然后根据d和直径2r的关系，最终答案为

#include <cstdio>
#include <cmath>

int main()
{
    //freopen("in.txt", "r", stdin);

    int r, x1, y1, x2, y2, ans;
    scanf("%d%d%d%d%d", &r, &x1, &y1, &x2, &y2);
    double d = sqrt((long long)(x1-x2)*(x1-x2) + (long long)(y1-y2)*(y1-y2));
    ans = (int)ceil(d / 2.0 / r);
    printf("%d\n", ans);

    return 0;
}

C. Guess Your Way Out! (模拟 LCA)

题意：

有一个树高为h的完全二叉树 和 一个目标叶子节点， 给出一种遍历方式(LRLRLR...)

求在到达目标节点时，遍历节点的总数。(不包括目标节点)

具体参见原文Guess Your Way Out!

分析：

以官方题解中的图为例。自己最开始对这道题没什么想法，所以后面的分析相当于题解的翻译。=_=||

从树根开始走到最底端，到达节点X。

如果X刚好是目标节点E，则得到结果为树高h。

否则，找到X和E的 Least Common Ancestor (最小公共祖先)。在右子树遍历之前，一定会遍历完左子树中所有的节点 (图中用红色标出) ，从而退出，进入右子树。

所以在到达右子树之前共遍历sum[h₁] + h - h₁，其中sum[h₁]表示树高为h₁的完全二叉树的节点个数。

在进入右子树后，更新树高h、根节点编号、遍历的方向(L or R)，重复刚才的过程。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long LL;

LL h, n, sum[55], ans = 0;
vector<LL> anc1;

int main()
{
    //freopen("in.txt", "r", stdin);

    for(int i = 0; i <= 50; ++i) sum[i] = (1LL << (i+1)) - 1;
    scanf("%I64d%I64d", &h, &n);
    n += sum[h-1];  //转化成整个二叉树中的编号
    LL x = n;
    anc1.push_back(x);  //目标节点的所有祖先
    while(x != 1)
    {
        x /= 2;
        anc1.push_back(x);
    }
    //for(int i = 0; i < anc1.size(); ++i) printf("%I64d  ", anc1[i]);

    LL node = 1;
    bool choice = false;    //遍历防线(L or R)

    while(node != n)
    {
        vector<LL> anc2;    //当前叶子节点X的祖先
        for(int i = 0; i < h; ++i)
        {
            anc2.push_back(node);
            if(!choice) node = node * 2; else node = node * 2 + 1;
            choice = !choice;
        }
        if(n == node) { ans += h; break; }
        anc2.push_back(node);
        reverse(anc2.begin(), anc2.end());
        //for(int i = 0; i < anc2.size(); ++i) printf("%I64d  ", anc2[i]);

        for(int i = 1; i <= h; ++i) if(anc1[i] == anc2[i])
        {//find LCA
            ans += sum[i-1] + h - i + 1;
            h = i - 1;      //更新树高
            node = anc2[i-1];
            if((anc2[i]<<1) == node)    //更新根节点的编号 及 遍历方向
            {
                node = anc2[i] * 2 + 1;
                choice = false;
            }
            else
            {
                node = (anc2[i] << 1);
                choice = true;
            }
            break;
        }
    }

    printf("%I64d\n", ans);

    return 0;
}