ABC067

[ABC067B] Snake Toy

题面翻译

输入n个数，输出前k大的数的总和

题目描述

すぬけくんは $ N $ 本の棒を持っています。 $ i $ 番目の棒の長さは $ l_i $ です。

すぬけくんは $ K $ 本の棒を選んでつなげて、ヘビのおもちゃを作りたいです。

ヘビのおもちゃの長さは選んだ棒たちの長さの総和で表されます。 ヘビのおもちゃの長さとしてありうる長さのうち、最大値を求めなさい。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ K $ $ l_1 $ $ l_2 $ $ l_3 $ $ ... $ $ l_{N} $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

5 3
1 2 3 4 5

样例输出 #1

12

样例 #2

样例输入 #2

15 14
50 26 27 21 41 7 42 35 7 5 5 36 39 1 45

样例输出 #2

386

提示

制約

• $ 1  K  N  50 $
• $ 1  l_i  50 $
• $ l_i $ は整数

Sample Explanation 1

長さ $ 3,4,5 $ の棒を選んでつなげると、長さ $ 12 $ のヘビのおもちゃを作ることが可能で、これがありうる長さのうち最大の値です。

思路

直接用优先队列即可解决。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=3e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll l[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    priority_queue<ll,vector<ll>> q;
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>l[i];
        q.push(l[i]);
    }
    ll ans=0;
    while(k--){
        ans+=q.top();
        q.pop();
    }
    cout<<ans;
    return 0;
}

[ABC067C] Splitting Pile

题面翻译

小狸和浣熊制作了 \(N\) 张卡，并堆积成山。卡片山上第 \(i\) 张卡片上写着整数 \(a_i\)。
小狸和浣熊决定分享 \(N\) 张卡。小狸从卡片山上取了几张卡片后，浣熊会把剩下的全部卡片都取出来。此时，无论是小狸还是浣熊都必须取得 \(1\) 张以上的卡。
如果小狸和浣熊所持有的卡片上写着的数的总和分别为 \(x, y\)。求出 \(|x - y|\) 中可能值的最小值。

题目描述

すぬけくんとアライグマは $ N $ 枚のカードの山を作りました。カードの山の上から $ i $ 番目のカードには整数 $ a_i $ が書かれています。

$ N $ 枚のカードを分け合うことにしました。 すぬけくんがカードの山の上から何枚かのカードを取ったあと、アライグマは残ったカード全てを取ります。 このとき、すぬけくんもアライグマも $ 1 $ 枚以上のカードを取る必要があります。

すぬけくんとアライグマが持っているカードに書かれた数の総和をそれぞれ $ x,y $ として、$ |x-y| $ を最小化したいです。 $ |x-y| $ としてありうる値の最小値を求めなさい。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_{N} $

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

6
1 2 3 4 5 6

样例输出 #1

1

样例 #2

样例输入 #2

2
10 -10

样例输出 #2

20

提示

制約

• $ 2  N  2  10^5 $
• $ -10^{{9}  a_i  10}{9} $
• $ a_i $ は整数

Sample Explanation 1

すぬけくんが上から $ 4 $ 枚のカードを、アライグマが残った $ 2 $ 枚のカードを取ったとき、$ x=10,y=11 $ となって、$ |x-y| $ は $ 1 $ となり、これが最小です。

Sample Explanation 2

すぬけくんは上から $ 1 $ 枚のカードを、アライグマは残った $ 1 $ 枚を取るしかありえません。このとき $ x=10,y=-10 $ となって、$ |x-y| $ は $ 20 $ となります。

思路

直接用前缀和即可解决。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=3e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll a[MAXN],sum[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    ll ans=LONG_LONG_MAX>>1;
    for(int i=1;i<n;i++){
        ans=min(ans,abs(sum[n]-2*sum[i]));
    }
    cout<<ans;
    return 0;
}

[ABC067D] Fennec VS. Snuke

题面翻译

题目描述

\(Fennec\) 和 \(Snuke\) 正在玩棋盘游戏。

在这个游戏中，有 \(n\) 个格子和 \(n-1\) 条道路， 编号为 \(a_i\) 和 \(b_i\) 的格子通过第 \(i\) 条边相连。这些格子和边组成了一棵树。

第 \(1\) 个格子是黑色，第 \(n\) 个格子是白色，其他格子没有颜色。先手 \(Fennec\) 和后手 \(Snuke\) 交替给格子涂色，两人依次执行以下操作：

\(Fennec\)：将一个与黑色格子相邻且未被涂色的格子涂成黑色。

\(Snuke\)：将一个与白色格子相邻且未被涂色的格子涂成白色。

如果当前行动的玩家无法涂色，他将输掉游戏。请你写一个程序，判断当 \(Fennec\) 和 \(Snuke\) 都采取最佳策略时，谁能获胜。

输入格式

第一行一个整数 \(n\ \ (2 ≤n≤1e5)\)

接下来 \(n-1\)行，每行两个整数 \(a_i\) 和 \(b_i\)，表示 \(a_i\) 和 \(b_i\) 间有一条边 \((1≤a_i ,b_i ≤n)\)

输出格式

若 Fennec 获胜，输出“Fennec”，否则输出“Snuke”（不包含引号）

题目描述

フェネックとすぬけくんがボードゲームで遊んでいます。

このボードゲームには $ 1 $ 番から $ N $ 番までの番号がついた $ N $ 個のマスと、マスどうしをつなぐ $ N-1 $ 本の道が存在しています。 $ a_i $ 番のマスと $ b_i $ 番のマスは $ i $ 番目の道を介して隣り合っています。どの $ 2 $ つのマスも隣接するマスをいくつか辿って必ず辿り着くことが可能です。すなわち、グラフ理論の言葉を用いると、マスと道から構成されるグラフは木です。

はじめに $ 1 $ 番のマスは黒く、$ N $ 番のマスは白く塗られています。その他のマスはまだ色が塗られていません。 先手のフェネックと後手のすぬけくんは残りのマスに交互に色を塗ります。 自分の手番において、$ 2 $ 人はそれぞれ以下のような行動を行います。

• フェネック：黒く 塗られたマスに隣接したマスであって、色が塗られていないマスを $ 1 $ つ選んで 黒く 塗る。
• すぬけくん：白く 塗られたマスに隣接したマスであって、色が塗られていないマスを $ 1 $ つ選んで 白く 塗る。

手番のプレイヤーがマスに色を塗ることができなかったとき、敗者となります。フェネックとすぬけくんが最適に行動したとき勝者はどちらか判定してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ a_1 $ $ b_1 $ $ : $ $ a_{N-1} $ $ b_{N-1} $

输出格式

勝者がフェネックならば Fennec と、すぬけくんならば Snuke と出力せよ。

样例 #1

样例输入 #1

7
3 6
1 2
3 1
7 4
5 7
1 4

样例输出 #1

Fennec

样例 #2

样例输入 #2

4
1 4
4 2
2 3

样例输出 #2

Snuke

提示

制約

• $ 2  N  10^5 $
• $ 1  a_i, b_i  N $
• 与えられるグラフは木

Sample Explanation 1

例えばフェネックがはじめに $ 2 $ 番のマスを黒く塗ると、すぬけくんがどのようにマスを白く塗ったとしてもフェネックが勝者となります。

思路

\(dfs\)。

不难想到最优的策略，就是围追堵截对方的路。

对于某一个点，我们可以统计黑棋和白棋到该点所需要的步数，如果黑棋距离更近，那么黑棋可以先占领，否则，则白棋占领，注意到黑棋具有先手优势，如果两者到该点的点数相等，还是黑棋先占领。

我们只需要\(dfs\)算出两者到每一个点的步数即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=3e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
struct Edge{
    int from,to;
};
vector<Edge> edge[MAXN];
void add(int from,int to){
    Edge e={from,to};
    edge[from].push_back(e);
}
ll dis[5][MAXN];
void dfs(ll to,ll from,ll id){
    dis[id][to]=dis[id][from]+1;
    for(auto t:edge[to]){
        //注意可能遇到父节点 需要跳过
        if(t.to==from)continue;
        dfs(t.to,to,id);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    //建图
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    //黑棋开始dfs
    dfs(1,0,0);
    
    //白棋开始dfs
    dfs(n,0,1);
    
    //id为0是黑棋，1为白棋
    //ans1统计的是黑棋占领的个数，ans2统计的是白棋占领的个数
    ll ans1=0,ans2=0;
    for(int i=1;i<=n;i++){
        if(dis[0][i]<=dis[1][i]){
            ans1++;
        }
        else{
            ans2++;
        }
    }
    if(ans1>ans2){
        cout<<"Fennec";
    }
    else cout<<"Snuke";
    return 0;
}