Codeforces Round #635 (Div. 2)
题目链接
题目大意找到满足三角形边长关系的x,y,zx,y,zx,y,z使得x,y,zx,y,zx,y,z满足a≤x≤b≤y≤c≤z≤da \le x\le b\le y \le c \le z \le da≤x≤b≤y≤c≤z≤d
解题思路我们知道一最短边为底的三角形肯定存在所以我们取特殊值
时间复杂度为O(1)O(1)O(1)
x=a,y=z=cx=a,y=z=cx=a,y=z=c
#include
using namespace std;
int main()
{
int T,a,b,c,d,x,y,z;
cin>>T;
while (T--)
{
cin>>a>>b>>c>>d;
x=a,y=z=c;
cout<<x<<" "<<y<<" "<<z<<endl;
}
return 0;
}
B. Kana and Dragon Quest game
题目链接
题目大意大龙的血量为hhh，你有两个技能A、BA、BA、B分别能够使用n,mn,mn,m次
技能AAA：h=⌊h2⌋+10h=\left\lfloor \frac{h}{2} \right\rfloor + 10h=⌊2h⌋+10
技能BBB：h=h−10h=h-10h=h−10
问你是否能够打败大龙
解题思路我们思考什么时候使用AAA技能能够使怪物的血量减少
也就是解不等式h<⌊h2⌋+10h < \left\lfloor \frac{h}{2} \right\rfloor + 10h<⌊2h⌋+10我们解的h<20h< 20h<20。
所以我们的策略是当h>20h>20h>20时不断地使用AAA技能，直至AAA技能用完或者h≤20h\le20h≤20时停止使用AAA技能，然后判断一下接下来全部使用BBB技能是否能够打败大龙就可以了。
源码#include
using namespace std;
int main()
{
int T,x,m,n;
cin>>T;
while (T--)
{
cin>>x>>n>>m;
while (x>20&&n)
{
x=x/2+10;
n--;
}
if(x>m*10)cout<<"NO"<<endl;else cout<<"YES"<<endl;
}
return 0;
}
C. Linova and Kingdom
题目链接
题目大意一共有nnn个点n−1n-1n−1条边构成一棵以节点111为根的树，每个结点代表一个城市，我们要选取kkk个城市发展工业，其余的城市发展旅游业，求每个工业城市到节点111的道路上所经过的旅游城市数量之和。
解题思路更具样例给的图我们很容易发现1节点肯定需要发展旅游业，这样所得到的结果才最优，所以我们在考虑哪几个城市发展旅游业比较简单。
我们先从只考虑一个旅游城市时，显而易见那么那个旅游城市肯定就是根节点111，答案就是n−1n-1n−1
然后我们考虑寻找第二个旅游城市，比如说我们考虑例题中的333节点，如果我们取了333结点，那么333节点的所有子节点的幸福值就+1+1+1，但是333节点它从一个旅游城市变成了工业城市，所以总的幸福值就会减去333节点还没被选为旅游城市之前的幸福值，我们可以发现如果节点333要被选为旅游城市，那么节点333的所有父节点肯定都已经被选为旅游城市（下面有证明），所以节点333的幸福值就是它到根节点的距离。
接下来我们证明如果节点iii要被选为旅游城市，那么节点iii的所有父节点肯定都已经被选为旅游城市。我们可以使用反证法来证明，如果节点iii的父节点中存在工业城市jjj，因为节点jjj肯定包含节点iii所有的子节点，那么节点jjj的根节点的数量肯定比节点iii多，且需要减去的幸福值肯定不比节点iii多，所以选择jjj肯定比选择iii的解更优。
所以我们得出方程为
ans=∑n−kweigth[i]−dis[i]ans=\sum^{n-k} weigth[i]-dis[i]ans=∑n−kweigth[i]−dis[i]
所以我们只需要将所有的节点根据weigth[i]−dis[i]weigth[i]-dis[i]weigth[i]−dis[i]排序，然后找到最大的n−kn-kn−k项相加即可。
因为我们需要同时得到根节点的距离和子节点的数量两个量，所以我们采用DFS。
源码#include
typedef long long ll;
using namespace std;
const int MAXN = (int)2e5 + 5;
vector G[MAXN];
ll tmp[MAXN];
bool used[MAXN];
int n, k;
int dfs(int x,int d)
{
int res=0;
used[x]=true;
for (int i = 0; i < G[x].size(); i++)if(!used[G[x][i]])res+=dfs(G[x][i],d+1);
tmp[x]=res-d;
return res+1;
}
ll solve()
{
dfs(1,0);
sort(tmp+1,tmp+n+1,greater());
ll ans=0;
for (int i = 1; i > n >> k;
for (int i = 0; i > a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
cout << solve() << endl;
return 0;
}
D. Xenia and Colorful Gems
题目链接
题目大意从r,g,br,g,br,g,b分别找到三个数x,y,zx,y,zx,y,z，使得(x−y)2+(y−z)2+(z−x)2(x-y)^2+(y-z)^2+(z-x)^2(x−y)2+(y−z)2+(z−x)2最小。
解题思路这题我是玄学AC。
我就分析一下我玄（无）学（脑）的思路。
我想啊，这跟距离有点像，所以答案的三个数字肯定是从小到大的，两边的数肯定是对应集合中到中间的那个数的距离最小的，但是中间的那个数是哪个集合的呢，枚举啊，反正才三个。
时间复杂度O(nlog(n))O(n\log(n))O(nlog(n))
#include
typedef long long ll;
using namespace std;
const int MAXN=(int)1e5+5;
ll x[MAXN],y[MAXN],z[MAXN],ans;
int nx,ny,nz;
ll dis(ll a, ll b, ll c)
{
return (a-b)*(a-b)+(a-c)*(a-c)+(b-c)*(b-c);
}
void solve(ll *r,int nr,ll *g,int ng,ll *b,int nb)
{
int gl,bl;
gl=bl=0;
for (int i = 0; i < nr; i++)
{
while(gl+1=abs(g[gl+1]-r[i]))gl++;
while(bl+1=abs(b[bl+1]-r[i]))bl++;
ans=min(ans,dis(r[i],g[gl],b[bl]));
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while (T--)
{
cin>>nx>>ny>>nz;
for (int i = 0; i >x[i];
for (int i = 0; i >y[i];
for (int i = 0; i >z[i];
ans=dis(x[0],y[0],z[0]);
sort(x,x+nx);
sort(y,y+ny);
sort(z,z+nz);
solve(x,nx,y,ny,z,nz);
solve(y,ny,x,nx,z,nz);
solve(z,nz,y,ny,x,nx);
cout<<ans<<endl;
}
return 0;
}
EF补完后再写┭┮﹏┭┮
作者：Eric C.H.Xia
