中国场！莫名的激动。题目的风格真的和出题人有关，虽然我只做了三题
题意描述
给定 $a,b,c,d$ 其中 $a \le b \le c \le d$，试找到 $x,y,z$ 其中
- $a \leq x \leq b$
- $b \leq y \leq c$
- $c \leq z \leq d$
使得以 $x,y,z$ 为三角形三边长度构成一个三角形。
解法
一开始的朴素思路是
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <bits/stdc++.h>
using namespace std;
int _,a[5];
int main() {
for(scanf("%d",&_);_;_--) {
for(int i=1;i<=4;i++)scanf("%d",&a[i]);
if(a[1]+a[2]<=a[3]) {
if(a[3]-a[2]<=a[2]) printf("%d %d %d\n",a[3]-a[2]+1,a[2],a[3]);
else printf("%d %d %d\n",a[1],a[3]-a[1]+1,a[3]);
}
else printf("%d %d %d\n",a[1],a[2],a[3]);
}
return 0;
}
|
但是 $x,y,z \le 5\times 10^8$ 。
1
2
3
4
5
6
7
8
9
10
11
|
#include <bits/stdc++.h>
using namespace std;
int _,a[5];
int main() {
for(scanf("%d",&_);_;_--) {
for(int i=1;i<=4;i++)scanf("%d",&a[i]);
printf("%d %d %d\n",a[2],a[3],a[3]);
}
return 0;
}
|
构造一组腰长大于边长的等腰三角形就好了。
题意简述
一个怪物有 $x$ 的血量，你可以执行最多 $n$ 次操作使得其血量等于 $\left\lfloor \frac{x}{2} \right\rfloor + 10$，也可以执行最多 $m$ 次操作使得其血量等于 $x-10$，问能否杀死它。
解法
想尽办法用第一种方法就行了，再判断剩下的血量能否被击杀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <bits/stdc++.h>
using namespace std;
int _,n,m;
double x;
int main() {
for(scanf("%d",&_);_;_--) {
scanf("%lf%d%d",&x,&n,&m);
int ansn=0,ansm=0;
if(x<=m*10) {
puts("YES");
continue;
}
while(ansn<n) {
x=floor(x/2)+10;
ansn++;
}
if(x<=m*10) puts("YES");
else puts("NO");
}
return 0;
}
|
题意简述
给定一棵 $n$ 个节点的树，选择 $k$ 个节点，使得从这些节点出发到根节点经过的非选中的点数量尽可能多，求出最大值。
解法
显而易见的选择 $k$ 个深度最深的点就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2*100005;
int idx,v[maxn*2],first[maxn],nxt[maxn*2],x,y,n,k;
void add(int x,int y) {
v[++idx]=y;
nxt[idx]=first[x];
first[x]=idx;
}
struct node{
int sz,dep;
} a[maxn];
ll ans;
bool cmp(node a1,node a2) {
return a1.dep-a1.sz>a2.dep-a2.sz;
}
void dfs(int u,int fa) {
a[u].sz=1,a[u].dep=a[fa].dep+1;
for(int i=first[u];i;i=nxt[i])
if(v[i]!=fa)
dfs(v[i],u),a[u].sz+=a[v[i]].sz;
}
int main() {
scanf("%d%d",&n,&k);
a[0].dep=0;
for(int i=1;i<=n-1;i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(1,0);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=k;i++) ans+=a[i].dep-a[i].sz;
printf("%lld\n",ans);
}
|
题目太神仙了，先gugugu
