模拟赛总结补坑中......我还是太弱了
T1 东东闯魔塔
题目描述
东东最近迷上了一个叫魔塔的游戏。游戏规则是这样的：你有一定的生命值、攻击和防御以及魔防，怪物有一定的生命值、攻击和防御。你与怪物战斗时，你出手对怪物造成的伤害为你的攻击-怪物的防御（至少为0），怪物出手对你造成的伤害为怪物的攻击-你的防御（至少为0）。作战时，你与怪物轮流出手，你先攻击，直到一方生命值减至0以下。特殊地，你的魔防可以降低10倍魔防值的总伤害，最多降至0，即“无损”（先计算总伤害，在此基础上减去10倍的魔防值）。尽管东东的生命值非常多，多到足以应对任何有限伤害，也存在一种情况——东东的攻击不大于怪物的防御，导致始终无法打败怪物。
游戏中有一个商店，你每次可以用金币买1点能力（攻击、防御或魔防）。价格的设定是这样的：初始价格为c个金币，每次你购买能力后，该项能力的价格就升高1个金币，而其余项能力价格不变
东东经过探路，已经知道了前面有n只怪物。第i只怪物的生命值、攻击、防御为hi、si、di。东东有攻击、防御、魔防分别S、D、M，同时有G个金币。东东现在想知道：通过在商店购买能力，使得他对付这些怪的最小总伤害是多少。
输入
第1行输入T，表示有T组测试数据。
每组测试数据的第1行输入6个数：S、D、M、G、c、n。
以下n行，每行3个数：hi、si、di。
输出
每组测试数据一行，如果能够击败所有怪物，则输出最小总伤害，否则输出-1。
样例输入
2
1 1 0 4 1 2
100 10 2
50 20 1
1 1 5 10 1 1
10 1 5
样例输出
1224
-1
样例解释
第一组测试数据中，用4个金币购买2点攻击（花费3个金币）和1点防御，使得对于第一只怪物你的攻击次数为100/(3-2)(向上取整)=100，则怪物攻击次数为100-1=99，所受伤害为99*(10-2)=792，同理，第二只怪物造成的伤害432，因此总伤害为1224。其余方案均不为最优解。
第二组测试数据中，无论如何加点都无法使攻击高于5，故输出-1。
数据范围与约定
对于50%的数据，T=1，0<G<100，0<n<10；
对于100%的数据，0<T≤10，0<G<5000，0<n<100，数据保证在int范围内
题目分析：
不会..... 到现在也不会>.<
貌似是奇奇怪怪的优化暴力..... 反正考场上暴力枚举拿了40....
先附上std代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespacestd;
int hi[101],si[101],di[101],f[10001];
int damage(int s0,int d0,int m0,int h1,int s1,int d1)
{
if(s0<=d1) return-1;
returnmax(0,((h1-1)/(s0-d1))*(max(s1-d0,0))-m0*10);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int s,d,m,g,c,n,i,j,k,l,ans=0x7fffffff,sum=0,flag,t;
scanf("%d%d%d%d%d%d",&s,&d,&m,&g,&c,&n);
for(i=0;i<n;i++)
scanf("%d%d%d",&hi[i],&si[i],&di[i]);
memset(f,0,sizeof(f));
for(i=0;(2*c+i-1)*i/2<=g;i++)
f[(2*c+i-1)*i/2]=i;
for(i=1;i<=g;i++)
f[i]=max(f[i],f[i-1]);
for(i=0;(2*c+i-1)*i/2<=g;i++)
{
for(j=0;(2*c+j-1)*j/2+(2*c+i-1)*i/2<=g;j++)
{
k=f[g-(2*c+j-1)*j/2-(2*c+i-1)*i/2];
flag=1;
sum=0;
for(l=0;l<n;l++)
{
t=damage(s+i,d+j,m+k,hi[l],si[l],di[l]);
if(t==-1)
{
flag=0;
break;
}
sum+=t;
}
if(flag)
ans=min(ans,sum);
}
}
printf("%d\n",ans==0x7fffffff?-1:ans);
}
}
T2 东东的手机
题目描述
经过自己的不懈努力后，东东，终于，成功地让东东爸给他买了一个可以打电话的手机！
但是，他慢慢发现，别人用的都是iPhone7了，自己用的还是诺基亚。这样大的价格差距让他比较不满。东东都已经这样不满了，更何况没有手机的明明呢。
于是东东和明明开始询问有关别人手机价格的信息，但他们都不愿说真实价格，只会说什么“我的比他的便宜100元”之类的话，这让他们在比较所有人时很不方便。好在明明知道的信息足够多，于是东东就去问明明。
明明是个IQ高的孩子，他能记住东东是否知道某两个人的手机价格关系。于是他就在告诉东东的过程中，掺杂着一些假话。这些假话只会在东东已经确定这个价格关系后才出现。
东东是个IQ更高的孩子。他不仅知道明明说了假话，还知道已经确定价格关系后重复出现了无用信息（不包括假话）。
你，IQ最高的孩子，当然就是要求出东东所知的假话数量和无用信息的数量了。
输入
第1行输入两个整数n和m，分别表示人数和明明所知的信息数。
以下m行为明明所知的信息，每行3个数ai、bi、ci，表示ai的手机比bi的手机便宜ci元。
输出
输出一行两个数，用空格隔开，分别表示东东所知的假话数量和无用信息的数量。
样例输入
5 7
1 2 100
2 4 200
1 3 400
4 3 200
1 5 600
3 5 200
4 2 200
样例输出
2 1
样例解释
第1、2、3、5个信息为未知条件，第4个信息为假（应为100元），第6个信息为无用信息，第7个信息为假（应为2比4便宜200元）。
数据范围及约定
对于30%的数据，0<n<200，0<m<400
对于80%的数据，0<n<50000，0<m<100000
对于100%的数据，0<n<200000，0<m<500000, 1≤ai、bi≤n，0<ci<1000
题目分析：
带权并查集
这里定义dis[x]数组为点x到它上一层的距离 即x比它上一层便宜多少元
然后对于询问先判断是否具有可比性(是否在一个集合里)
不在同一个集合里就合并 这里根据dis[]的定义得出：dis[find(x)]=dis[y]-dis[x]+c (dis[find(x)]=find(y))
否则判断大小关系 如果相等则信息没有用 否则就是假话
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int f[300000];
int dis[300000];
int ans1,ans2;
int find(int x)
{
if(f[x]==x) return x;
int tmp=find(f[x]);
dis[x]=dis[x]+dis[f[x]];
f[x]=tmp;
return f[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
int dx=find(x);
int dy=find(y);
if(dx!=dy)
f[dx]=dy,dis[dx]=dis[y]+c-dis[x];
else
{
if(dis[x]-dis[y]!=c) ans1++;
else ans2++;
}
}
printf("%d %d",ans1,ans2);
return 0;
}
T3 东东去旅游
题目描述
东东和东东爸去附近的地方旅游。附近共有n个城市（编号为1~n），并有n-1条连接这n个城市的道路。每条路的长度都有一个固定值。他们所在城市编号为1。他们计划去k个城市，他们会按照计划从所在城市到第1个想要去的城市，再到第2个想要去的城市，……，最后到第k个想要去的城市，然后并返回所在城市（想要去的城市可能会包括所在城市）。东东想知道每次行程中经过的路的长度之和是多少。由于东东只会1000000000以内的加减法，所以这个任务需要你来完成。
输入
第1行输入两个整数n和k，表示城市总数和计划去的城市数。
第2~n行，每行输入3个整数xi、yi、zi，表示城市xi与yi之间有一条长度为zi的道路。
第n+1行，输入k个整数，第i个整数表示计划去的第i个城市的编号。
输出
输出k+1行，每行表示这次行程中经过的路的长度总和。其中第1行为从1到第1个计划城市的路的长度总和，第2~k行为两个计划城市之间的路的长度总和，第k+1行为从第k个计划城市到1的路的长度总和。
样例输入
5 4
1 2 1
1 3 2
3 4 5
3 5 7
2 5 4 3
样例输出
1
10
12
5
2
数据范围及约定
对于20%的数据，0<n<100
对于50%的数据，0<n<2000，0<k<1000
对于100%的数据，0<k<n<50000，1≤xi、yi≤n，0<zi<10^9
题目分析：
这题才是名副其实的水题啊QAQ
相当于多次询问一棵树中两点的路径和 : dis[x]+dis[y]-2*dis[lca(x,y)]
然后这题就A了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,k;
int next[101000],to[101000];
long long val[101000];
int head[101000],a[101000],fa[60000][22],deep[101000];
long long dis[101000];
int tot;
void add(int x,int y,long long c)
{
next[++tot]=head[x];
to[tot]=y;
val[tot]=c;
head[x]=tot;
}
void dfs(int x,int temp)
{
deep[x]=deep[temp]+1;
fa[x][0]=temp;
for(int i=1;fa[x][i-1];i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=next[i])
if(to[i]!=temp) dis[to[i]]=dis[x]+val[i],dfs(to[i],x);
}
void Swp(int &x,int &y)
{
int tmp=x;
x=y;y=tmp;
return;
}
int lca(int x,int y)
{
if(deep[x]<deep[y])Swp(x,y);
int temp=20;
while(temp>=0)
{
if(deep[fa[x][temp]]>=deep[y])
temp--;
}
if(x==y) return ans;
temp=20;
while(temp>=0)
{
if(fa[x][temp]!=fa[y][temp])
x=fa[x][temp],y=fa[y][temp];
temp--;
}
return fa[x][0];
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++)
{
int x,y;
long long c;
scanf("%d%d%lld",&x,&y,&c);
add(x,y,c);add(y,x,c);
}
dfs(1,0);
for(int i=1;i<=k;i++)
scanf("%d",&a[i]);
a[0]=1,a[k+1]=1;
for(int i=1;i<=k+1;i++)
printf("%lld\n",dis[a[i]]+dis[a[i-1]]-2*dis[lca(a[i-1],a[i])]);
return 0;
}