暑假集训存录
推歌 —— BlackPink 《뚜두뚜두》
착한 얼굴에 그렇지 못한 태도
善良的脸蛋 不屑的态度
가녀린 몸매 속 가려진 volume은 두 배로
纤细的身体里隐藏着两倍的音量
거침없이 직진 굳이 보진 않지 눈치
势不可挡 一直向前 不必察言观色
Black 하면 Pink 우린 예쁘장한 Savage
Black Pink是一体 我们靓丽奔放
원할 땐 대놓고 뺏지
想要的时候 放手去争就行
넌 뭘 해도 칼로 물 베기
无论你做什么 我都会原谅你
두 손엔 가득한 fat check
我手握大额支票
궁금하면 해봐 fact check
好奇的话 就来查明真相
눈 높인 꼭대기
眼望巅峰
물 만난 물고기
如鱼得水
좀 독해 난 Toxic
我有点狠毒
You 혹해 I'm Foxy
我是诱惑你的狐狸
두 번 생각해
再好好想想
흔한 남들처럼 착한 척은 못 하니까
我可不像一般人那样伪善
착각하지 마
你别自欺欺人了
쉽게 웃어주는 건 날 위한 거야
那轻松绽放的笑容是为了我自己
아직은 잘 모르겠지
现在还弄不明白吧
굳이 원하면 test me
若是渴望拥有我 就来一探究竟
넌 불 보듯이 뻔해
你的意图一目了然
만만한 걸 원했다면
如果你甘愿臣服于我
Oh wait til' I do what I do
Oh wait til' I do what I do
Hit you with that ddu-du ddu-du du
Hit you with that ddu-du ddu-du du
Hit you with that ddu-du ddu-du du
Hit you with that ddu-du ddu-du du
지금 내가 걸어가는 거린
我正走向
BLACKPINK 4 way 사거리
BLACKPINK 4 way 十字路口
동서남북 사방으로 run it
向着东南西北 四处奔跑
너네 버킷리스트 싹 다 I bought it
你们的愿望清单我来买单
널 당기는 것도 멀리 밀치는 것도
对你半推半就
제멋대로 하는 bad girl
我是随心所欲的坏女孩
좋건 싫어하건 누가 뭐라 하던
不管谁说什么 我都有我的喜好
When the bass drop it's another banger
When the bass drop it's another banger
두 번 생각해
再好好想想
흔한 남들처럼 착한 척은 못 하니까
我可不像一般人那样伪善
착각하지 마
你别自欺欺人了
쉽게 웃어주는 건 날 위한 거야
那轻松绽放的笑容是为了我自己
아직은 잘 모르겠지
现在还弄不明白吧
굳이 원하면 test me
若是渴望拥有我 就来一探究竟
넌 불 보듯이 뻔해
你的意图一目了然
만만한 걸 원했다면
如果你甘愿臣服于我
Oh wait til' I do what I do
Oh wait til' I do what I do
Hit you with that ddu-du ddu-du du
Hit you with that ddu-du ddu-du du
Hit you with that ddu-du ddu-du du
Hit you with that ddu-du ddu-du du
What you gonna do when I come come through with that that uh uh huh
What you gonna do when I comecome through with that that uh uh
What you gonna do when I come come through with that that uh uh huh
What you gonna do when I comecome through with that that uh uh
뜨거워 뜨거워 뜨거워 like fire
热辣似火 热辣似火
뜨거워 뜨거워 뜨거워 like fire
热辣似火 热辣似火
뜨거워 뜨거워 뜨거워 like fire
热辣似火 热辣似火
뜨거워 뜨거워 뜨거워 like fire
热辣似火 热辣似火
Hit you with that ddu-du ddu-du du
Hit you with that ddu-du ddu-du du
模拟赛
由于时间原因，这里只有 \(7 , 8 , 9\) 三场模拟赛的题解。
7 -- 树上游戏
\(Description\)
这一天， \(Delov\) 在和他的 \(npy\) 们在树上做游戏，他的 \(npy\) 们喜欢不同的位置，所以每个树节点上都有他的 \(npy\)，她们都希望 \(Delov\) 离自己近一些，否则就会不高兴。具体来讲，\(Delov\) 所在节点离某个 \(npy\) 所在节点的树上路径长度即为该节点 \(npy\) 的不满意度。
\(Delov\) 希望能够让所有 \(npy\) 的不满意度的最大值最小，而且，作为时间管理大师， \(Delov\) 拥有分身术，也就是说，他能同时存在于 kk 个节点，对 \(npy\) 来说她们会以离自己最近的\(Delov\)计算不满意度。
\(Delov\) 想知道所有 \(npy\) 的不满意度的最大值的最小值是多少，并把问题抛给你。
\(1 \le k < n < 2 \times 10 ^ 5\)
题解
简单贪心。二分答案一下。
从下往上跳起来，由于还可能是跨子树，所以对于每个子树根，都要跑一遍，由它的儿子记录最远的、未被覆盖的深度。
和 \(Delov\) 在的，最浅的点。
直接转移即可。看代码：
CODE
#include <bits/stdc++.h>
using namespace std ;
const int N = 2e5 + 100 ;
inline int read() {
int x = 0 , f = 1 ;
char c = getchar() ;
while (c < '0' || c > '9') {
if (c == '-') f = -f ;
c = getchar() ;
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0' ;
c = getchar() ;
}
return x * f ;
}
struct EDGE {
int next , to ;
} e[N << 1] ; int head[N] , cnt ;
inline void add(int x , int y) {
++ cnt , e[cnt].to = y , e[cnt].next = head[x] , head[x] = cnt ;
}
int n , K , depth[N] , father[N] , Heavy[N] ;
int num ; int Maxdepth[N] , Coverage[N] ;
void dfs(int x , int fa , int mid) {
int P = 0 , Q = -1 , flag = 0 ;
for (int i = head[x] ; i ; i = e[i].next) {
int y = e[i].to ;
if (y == fa) continue ;
flag = 1 ;
dfs(y , x , mid) ;
P = max(P , Maxdepth[y] + 1) ;
Q = max(Q , Coverage[y] - 1) ;
}
if (!flag) {
Maxdepth[x] = 0 , Coverage[x] = -1 ;
return ;
}
if (P <= Q) {
Maxdepth[x] = -1 ; Coverage[x] = Q ;
} else if (P == mid) {
++ num ;
Maxdepth[x] = -1 ; Coverage[x] = mid ;
} else {
if (x == 1) ++ num ;
Maxdepth[x] = P , Coverage[x] = Q ;
}
}
bool check(int mid) {
num = 0 ;
for (int i = 1 ; i <= n ; ++ i) Maxdepth[i] = Coverage[i] = 0 ;
dfs(1 , 0 , mid) ;
return num <= K ;
}
signed main() {
n = read() , K = read() ;
for (int i = 1 , x , y ; i < n ; ++ i) {
x = read() , y = read() ;
add(x , y) ; add(y , x) ;
}
int left = 1 , right = n - 1 ; int ans ;
while (left <= right) {
int mid = (left + right) >> 1 ;
if (check(mid)) {
ans = mid ;
right = mid - 1 ;
} else left = mid + 1 ;
}
cout << ans ;
}