FoxAndFencing

Topcoder SRM598-Div1-Lv2

题意

在一个数轴上，Ciel 的棋子在 \(x=0\) 处编号为 \(1\)，Liss的棋子在 \(x=d\) 处编号为 \(2\)，两个棋子的最大移动距离与攻击范围为 \(mov,rng\ (\leq10^9)\)，任意一方进行一个操作后检查对方棋子是否在己方棋子攻击范围内，若是则己方获胜。给出初始情况，双方均采用最优策略的情况下，判断游戏结果（Ciel 赢，Liss 赢，平局）。

Tips：一次操作后只检查对方棋子是否在己方攻击范围，而不立即检查己方棋子是否在对方攻击范围，也就是说如果能保证一击必胜那么即使进入对方攻击范围也能赢。

思路

数据范围与题目性质均说明了这题是个大分讨。

先特判开局就结束的情况，并且以下的分类讨论皆自动排除了开局即结束的情况。

考虑到一个性质，一个棋子实际攻击半径为 \(mov+rng\)，因为该棋子可以先移动，然后判对方是否在攻击范围，那么可以得到结论：如果 \(mov_1+rng_1>mov_2+rng_2\)，那么 \(1\) 一定不会输（以下皆反之同理），原因是 \(2\) 在一击必杀前必须保持在 \(1\) 的实际攻击半径之外才安全，而 \(2\) 由于实际攻击范围小于 \(1\)，永远无法一击必杀。

既然 \(2\) 一定不会赢，那么根据最优策略 \(2\) 一定是希望平局，那么 \(2\) 就会竭力逃跑，我们总结 \(1\) 能追上并击杀 \(2\) 的充要条件为：

• \(mov_1>mov_2\)​，很明显，如果不满足该条件二者距离只会越拉越大。
• \(rng_1\geq mov_2+rng_2+1\) 或 \(mov_1+rng_1\geq mov_2+rng_2+mov_2+1\)，\(1\) 在追杀 \(2\) 时在确保一击必杀时必须保持在 \(2\) 的实际攻击半径外避免被反杀，即和 \(2\) 保持至少 \(mov_2+rng_2+1\) 的距离，但如果 \(rng_1\geq mov_2+rng_2+1\)，那么 \(1\) 就可以在 \(2\) 实际攻击半径外安全地击杀 \(2\)，不然就给了 \(2\) 逃跑的机会，逃跑后 \(1\) 和 \(2\) 的距离为 \(mov_2+rng_2+mov_2+1\)，如果 \(1\) 的实际攻击半径大于等于该距离，\(1\) 就能追上并一击必杀，否则即使 \(1\) 跑步速度比 \(2\) 快，每次都会重复“追上-逃跑”这样的循环，游戏平局。另外注意到这两个条件后者其实就是前者的弱化版，所以实际编码时只用判断后者即可。

因此我们也能推出，如果 \(mov_1+rng_1=mov_2+rng_2\)，游戏一定平局。

代码

#include<bits/stdc++.h>
// #define puts(x); puts(x),cout<<__LINE__<<endl;
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
    static char ch[1<<20],*l,*r;
    return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
    T res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
    x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
    static char wtbuff[20];
    static int wtptr;
    if(x==0){
        putchar('0');
    }
    else{
        if(x<0){x=-x;putchar('-');}
        wtptr=0;
        while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
        while(wtptr--) putchar(wtbuff[wtptr]);
    }
    if(endch!='\0') putchar(endch);
}
long long mov[3],rng[3],d;
int main(){
    rd(mov[1]);rd(mov[2]);rd(rng[1]);rd(rng[2]);rd(d);
    if(mov[1]+rng[1]>=d){
        puts("Ciel");
        return 0;
    }
    else if(mov[1]+d<=mov[2]+rng[2]){
        puts("Liss");
        return 0;
    }

    if(mov[1]+rng[1]==mov[2]+rng[2]){
        puts("Draw");
    }
    else if(mov[1]>mov[2] && mov[1]+rng[1]>mov[2]+rng[2]+mov[2]){
        puts("Ciel");
    }
    else if(mov[2]>mov[1] && mov[2]+rng[2]>mov[1]+rng[1]+mov[1]){
        puts("Liss");
    }
    else{
        puts("Draw");
    }
    return 0;
}

Ethernet

Topcoder SRM622-Div1-Lv2

题意

有一颗 \(n\ (\leq 50)\) 个节点的树，节点 \(i\) 的父亲为 fa[i]，到父亲的边的边权为 dis[i]，边权 \(\leq 500\)。现在要将每个点分配到 \(k\) 个连通子图中的一个，使得子图中距离最长的两个点距离小于 \(maxd\)，定义子图为：如果 \(u\) 和 \(v\) 都是该子图的点并且原树中 \(u\) 到 \(v\) 存在边，那么子图中 \(u\) 到 \(v\) 也存在边。求出最小可能的 \(k\)。

思路

首先可以翻译一下题目，题目中对于找子图的描述是“分配”，但实际上我们会发现无论怎么分配，合法的子图一定是原树删掉某些边得到的森林，因为假设原树上两个点 \(u\) 和 \(v\) 都属于一个子图，但 \(u\) 到 \(v\)​ 到的路径上的点属于其他子图，该子图不可能连通，因此不合法。

因此我们只需要贪心断边，记 \(disf[i]\) 为 \(i\) 到其子树最远的点的距离，记录点 \(fa\) 的所有儿子的 \(disf+w\) （\(w\) 为父亲到儿子的边的边权）并从大到小排序，每次判断最大和次大加起来是否会超 \(maxd\)，如果超出则断开最大对应的点到父亲的边。

代码

#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar __getchar
inline char __getchar(){
    static char ch[1<<20],*l,*r;
    return (l==r&&(r=(l=ch)+fread(ch,1,1<<20,stdin),l==r))?EOF:*l++;
}
#endif
template<class T>inline void rd(T &x){
    T res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while('0'<=ch && ch<='9'){res=res*10+ch-'0';ch=getchar();}
    x=res*f;
}
template<class T>inline void wt(T x,char endch='\0'){
    static char wtbuff[20];
    static int wtptr;
    if(x==0){
        putchar('0');
    }
    else{
        if(x<0){x=-x;putchar('-');}
        wtptr=0;
        while(x){wtbuff[wtptr++]=x%10+'0';x/=10;}
        while(wtptr--) putchar(wtbuff[wtptr]);
    }
    if(endch!='\0') putchar(endch);
}
typedef pair<int,int> pii;
const int MAXN=55,MAXD=505;
int n,fa[MAXN],dis[MAXN],maxd,f[MAXN],disf[MAXN];
vector<pii>g[MAXN];
void dfs(int x){
    vector<int>sondis;
    sondis.push_back(0);
    for(auto it:g[x]){
        if(it.first==fa[x]) continue;
        dfs(it.first);
        f[x]+=f[it.first];
        sondis.push_back(disf[it.first]+it.second);
    }
    sort(sondis.begin(),sondis.end());
    while(sondis.size()>=2 && sondis.back()+sondis[sondis.size()-2]>maxd){
        f[x]++;
        sondis.pop_back();
    }
    disf[x]=sondis.back();
}
int main(){
    rd(n);
    for(int i=1;i<=n;i++){
        rd(fa[i]); 
    }
    rd(n);
    for(int i=1;i<=n;i++){
        rd(dis[i]);
        g[fa[i]].emplace_back(i,dis[i]);
        g[i].emplace_back(fa[i],dis[i]);
    }
    rd(maxd);
    n++;
    dfs(0);
    cout<<f[0]+1<<endl;
    return 0;
}