博客

A. Adrien and Austin

theme:一堆石子，编号从1~n,两个人轮流操作，每次可以取出1~k个编号连续的石子，问先手赢还是后手？1<=n,k<=1e6

solution:分析怎样的情况会赢，首先如果k>1则无论n是奇数还是偶数，先手取一次都可以分成两段长度相等的连续的段，这时候无论后手怎么操作，先手再在另一堆做对应的操作即可，所以先手必胜。当k==1时，如果n为奇数还是可以分成相等的两段，所以先手必胜，而n是偶数的时候，不能分成相等的两段，且先手 会输。注意特判下0==n,它不受k影响。

#include<bits/stdc++.h>
using namespace std;
#define far(i,t,n) for(int i=t;i<n;++i)
#define pk(a) push_back(a)
#define lowbit(x) x&(-x)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int inf=0x3f3f3f3f;
int mod=1e9+7;
const int maxn=1010;

int main()
{
    int n,k;
    cin>>n>>k;
    if(!n)
        puts("Austin");
    else
    {
        if(1==k)
        {
            if(n&1)
                puts("Adrien");
            else
                puts("Austin");
        }
        else
            puts("Adrien");
    }
}

**

D – Country Meow

theme:给定三维空间中n个点的坐标，在空间中找到一个到这n个点的最大距离最小的点，求这个最小的最大距离。1 ≤ N ≤ 100，−100000 ≤ xi , yi , zi ≤ 100000

solution:最大值最小化，考虑优化算法。这题是典型的最小球覆盖问题，考虑模拟退火解。

#include<bits/stdc++.h>

using namespace std;

const int MAXN=105;
const double EPS=1e-8;
struct Point{
    double x,y,cur;
}Dots[MAXN];
int n;

double Distance(Point a,Point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.cur-b.cur)*(a.cur-b.cur));
}

double Solve(){
    double Step=200,ans=1e9,dis;
    Point cur=Point{0,0,0};
    int far=0;//far为离所选点最远的点
    while(Step>EPS){
        for(int i=1;i<=n;i++)
            if(Distance(cur,Dots[far])<Distance(cur,Dots[i]))
                far=i;
        dis=Distance(cur,Dots[far]);
        ans=min(ans,dis);
        cur.x+=(Dots[far].x-cur.x)/dis*Step;
        cur.y+=(Dots[far].y-cur.y)/dis*Step;
        cur.cur+=(Dots[far].cur-cur.cur)/dis*Step;
        Step*=0.9999;
    }
    return ans;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        double x,y,cur;
        scanf("%lf %lf %lf",&x,&y,&cur);
        Dots[i]=Point{x,y,cur};
    }
    printf("%.7f\n",Solve());
}

**

K、Kangaroo Puzzle

theme:给定n个长度为m的01串，0表示障碍物，初始时1的位置都有一个袋鼠，袋鼠可以上下左右移动，每次移动所有袋鼠一起进行，如果某只袋鼠无法移动则它待在原地，问怎样安排移动方向使得最终所有袋鼠都在一个格子上。保证每只袋鼠能移动到任何不是0的位置上，且不存在袋鼠围成一个圈的情况，问能否在50000步内实现。1 ≤ n, m ≤ 20，输出方向

solution：首先由题意可知袋鼠初始所在位置是连通的，所以一定可以实现所有袋鼠都跳到一格。只要每次找两只在不同位置的袋鼠使它两合并即可。所以最多移动20*20*40=16000步，而题目要求是50000步内，所以随机走50000步也过了。

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
	srand(time(0));
	char t[]={'U','D','L','R'};
	for (int i=0;i<50000;i++) putchar(t[rand()&3]);
	puts("");
}