蓝桥杯 历届试题 大臣的旅费

。。。其实题意就是树的直径。。。
感觉自己挺傻逼的。。。直径就懂 最远路就不懂。。。
求直径就不用说了吧。。。自己查去。。。

。。。莫名其妙写了个O(n)的DP。。。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10010;
struct edge
{
int go,v,next;
};
edge eg[2*N];
int last[N],fm[N],sm[N];
//fm[] first max 记儿子、孙子等到该节点的最远路 sm[] 次远路
//当然,这两个值不能来自于同一个子树,因为不能重复经过结点
int tot=0;
void add(int x,int y,int z)
{
eg[++tot].go=y;
eg[tot].v=z;
eg[tot].next=last[x];
last[x]=tot;
}
void dfs(int x,int fa)
{
if (last[x]==0) return;
int p=0,q=0,i;
for (i=last[x];i;i=eg[i].next)
{
int u=eg[i].go;
if (u==fa) continue;
dfs(u,x);
if (eg[i].v+fm[u]>p)
{
q=p;
p=eg[i].v+fm[u];
}
else if (eg[i].v+fm[u]>q) q=eg[i].v+fm[u];
}
fm[x]=p;sm[x]=q;
}
int main()
{
int n,i,x,y,z,ans;
scanf("%d",&n);
for (i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs(1,0);
ans=-1;
for (i=1;i<=n;i++)
ans=max(ans,fm[i]+sm[i]);
printf("%d\n",ans*(ans+1)/2+ans*10);
return 0;
}

阅读全文

POJ 2823 //单调队列

选C++交
选C++交
选C++交
【重说三
因为是队里的专题训练。。。
所以我知道这题肯定是单调队列。。。
而且一看数据范围和时限。。。
12000ms 逗我?
随手一交。RE了。。。
再随手一交。尼玛!T了!!!
这怎么可能!!!
单调队列是 O(n) 啊!啊啊啊啊啊!!
然后再各种查资料查程序。。。
提交别人写的 AC 程序竟然还是TLE。。。
过了好几天(没错 好几天!)
跑到POJ的原题交了一下。
果然还是TLE了。。。
然后又开始搜各种搜。。。
直到发现这两个:
http://blog.csdn.net/chl_3205/article/details/8706307
http://blog.csdn.net/yihuikang/article/details/7771170
语言选到C++。。。果然 AC 了。。。
生无可恋的眼神 T^T

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <cstring>
const int N=1000010;
int a[N],q[N],c[N];
int main()
{
int n,k,i,l,r;
scanf("%d%d",&n,&k);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
l=1;
r=0;
for (i=1;i<=k;i++)
{
while (q[r]>=a[i]&&r>=l) r--;
c[++r]=i;
q[r]=a[i];
}
for (;i<=n;i++)
{
printf("%d ",q[l]);
while (q[r]>=a[i]&&r>=l) r--;
c[++r]=i;
q[r]=a[i];
if (i-k>=c[l]) l++;
}
printf("%d\n",q[l]);
l=1;
r=0;
for (i=1;i<=k;i++)
{
while (q[r]<=a[i]&&r>=l) r--;
c[++r]=i;
q[r]=a[i];
}
for (;i<=n;i++)
{
printf("%d ",q[l]);
while (q[r]<=a[i]&&r>=l) r--;
c[++r]=i;
q[r]=a[i];
if (i-k>=c[l]) l++;
}
printf("%d\n",q[l]);
return 0;
}

阅读全文

THE LAST

The Last 标着日语的基本都是韩语。。。刚开始简直吓死。。。xyz说有枪片但我感觉噪声太大。。。最后竟然还是坚持看完了韩语版 ←_← xyz说得对。就是个爱情片。

=============以上火影============
===========以下非常见风格=========

阅读全文

期中游记

本欲“说说”,不想太多。但以此次道路曲折,景致奇葩,槽点满满,令人长文不自禁。——ZY
【本文是一篇关于期中考的长日志。大家可以散了 =。= ——zyyyyy】

最开始看到座位号还没反应过来。
后来仔细一看!卧槽!这种 “0213” 的座位号明显就是 狂拽酷炫叼霸天带我装逼带我飞 啊!
【希望下次有个什么“0233” 之类的 ←_← 】

阅读全文