题目链接:Codeforces 398C Tree and Array
题目大意:给出n,表示有n个节点,每个节点有个值记录在t[i]中,初始为0,现在要求构造出一棵无向的树,既有n-1条边,保证所有点联通,现在每增加一条边u,v,x(假设u<v)那么t[i]就要增加x(u≤i≤v),现在要求在构造出的树中可以选出不少于n/2对点(u,v)保证∑(u≤i≤v)t[i] = dis(dis为从点u到v的路径上所有边的权值和)
解题思路:t = n/2,将t+1到n逐个相连成一条,然后i和t+i相连(1≤i≤t),这样的话为了使得i和i+1满足,只需要修改t+i和t+i+1这条边的权值即可;如果是奇数的话可以将n点直接舍弃在最后;但是这样只构造出n/2-1条边,这时可以控制一下各个1到3这条路径;n为5的话可以特判一下,因为奇数时我是将n这个点舍弃。
#include <stdio.h>
#include <string.h>
int main () {
int n;
scanf("%d", &n);
if (n == 5) {
printf("1 2 3\n1 3 3\n2 4 2\n4 5 1\n");
printf("3 4\n3 5\n");
} else {
int t = n/2;
for (int i = 1; i <= t; i++) printf("%d %d %d\n", i, i + t, 1);
for (int i = 1; i+t < n; i++) printf("%d %d %d\n", i+t, i+t+1, 2*i-1);
for (int i = 1; i < t; i++) printf("%d %d\n", i, i+1);
printf("1 3\n");
}
return 0;
}
分享到:
相关推荐
Array Shrinking time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given an array a1,a2,…,an. You can perform the following operation ...
题目大意:给出 n 个数,现在可执行的操作是: 找到相邻且数值相等的两个数,即 abs( i – j ) == 1 && a[ i ] == a[ j ] 使得两个数合并为一个数,且数值变为 a[ i ] + 1 问如何操作,能使得最终数列的长度最短 ...
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
打codeforces的神器
codeforces编程网站预测分数插件
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Eugene and an array 题意: 求出一个数列中子区间满足 此区间的任意子区间之和 不为0的区间个数。 思路: 考虑用dp[x]dp[x]dp[x]记录前缀和为xxx的区间右端点。 那么这道题其实可以看成用map记录前缀和的路径,依次...
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
E. Tree Queries time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output You are given a rooted tree consisting of
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
使用 C# + WPF 开发 ...你只需要提前构造好某些题的叉点数据,填入它,OK!一切就是这么的方便! 注:仅适用于 Edu 以及 Div.3 轮比赛赛后 hack,不支持 Div.1/2 赛时 hack。 适用人群:想进入首页 Hack 榜的选手
Codeforces round 678 D2_Codeforces_源码
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done