Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


game解题报告

题目描述

游戏是一个在带权图G上进行的,N个点,M条边,边权c(e),点权w(v),G的点数有偶数个,规则如下;
· 魅音和诗音分别将图中的点染色,诗音黑色,魅音蓝色,魅音先手
· 一个点只能被染一次
· 双方轮流选择点染色,一共选N/2轮,所有点都完成染色
经过 N/2 轮游戏之后,两人都得到了一个顶点集合。对于顶点集合 S ,得分计算方式为
$$ \sum{v∈S}w(v)+\sum{e=(u,v)∈E∩u,v∈S}c(e) $$


解题思路

将边权平分在两个点上(即两人取后差为零),可以发现,对于原来的点集A,B,
他们的权值之差就改为了新点权之差。即我们只需要考虑点权最大了。
那么只需要将新点权排序,从大到小依次选择即可。


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
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
using namespace std;
double dot[1005],v,ans;
int a,b,n,m;
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);

scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
scanf("%lf",&dot[i]);

for(int i = 1;i <= m;i++){
scanf("%d%d%lf",&a,&b,&v);
dot[a] += v/2;
dot[b] += v/2;
}
sort(dot+1,dot+n+1);
for(int i = n;i >=1;i -= 2)
ans += (dot[i]-dot[i-1]);
printf("%d\n",(int)ans);

return 0;
}

Markdown

最近的文章

cyclic解题报告

题目描述 给出一个字符串S与N个操作。每个操作用三元组(L, R, K)进行描述:操作将字符串第L个到第R个位置构成的子串循环移动K次。一次循环移动就是将字符串最后的这个字符移动到第一位,其余的字符顺次后移。 例如,对于字符串abacaba,操作(L=3, R=6, K=1)后得到的字符串即为abb …

于  STL, 字符串 继续阅读
更早的文章

lowbit解题报告

题目描述 这天,LYK在学习树状数组。 当它遇到一个叫lowbit的函数时有点懵逼。lowbit(x)的意思是将x分解成二进制,它的值就是2𝑘,其中k是最小的满足(x &amp; 2𝑘)&gt;0的数。(&amp;是二进制中的and运算)  LYK甚至知道lowbit(x)=(x&amp;-x) …

于  数学 继续阅读