—— Summon, Light!
0%

发表于 更新于 Valine：

http://codevs.cn/problem/1217/
唉。。。即使是以我四年后的水平也要改一遍。。。
太菜了。。。
应该是目前最常用的线段树写法。。。确实是能过的

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e6;
int lazy[4*N],mv[4*N];
void read(int &x)
{
	char c=getchar();
	x=0;
	while (!(c>='0'&&c<='9'||c=='-')) c=getchar();
	int f=0;
	if (c=='-') {
		f=1;
		c=getchar();
	}
	while (c>='0'&&c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	if (f) x=-x;
}
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
void push_up(int rt)
{
	mv[rt]=min(mv[rt<<1],mv[rt<<1|1]);
}
void build(int l,int r,int rt)
{
	if (l==r) {
		read(mv[rt]);
		return;
	}
	int m=(l+r)>>1;
	build(lson);
	build(rson);
	push_up(rt);
}
void push_down(int rt)
{
	lazy[rt<<1]+=lazy[rt];
	mv[rt<<1]+=lazy[rt];
	lazy[rt<<1|1]+=lazy[rt];
	mv[rt<<1|1]+=lazy[rt];
	lazy[rt]=0;
}
bool update(int l,int r,int rt,int L,int R,int del)
{
	if (L<=l&&r<=R) {
		lazy[rt]+=del;
		mv[rt]+=del;
		if (mv[rt]<0) return false;
		else return true;
	}
	push_down(rt);
	int m=(l+r)>>1;
	bool res=true;
	if (L<=m) res&=update(lson,L,R,del);
	if (!res) return false;
	if (m<R) res&=update(rson,L,R,del);
	push_up(rt);
	return res;
}
int n,m;
int check()
{
	for (int i=1; i<=m; i++) {
		int d,s,t;
		read(d);
		read(s);
		read(t);
		if (!update(1,n,1,s,t,-d)) return i;
	}
	return m+1;
}
int main()
{
	read(n);
	read(m);
	build(1,n,1);
	int ans=check();
	if (ans>m) puts("0");
	else printf("-1\n%d\n",ans);
	return 0;
}

下面介绍一种据说是正解的方法（不超纲的方法）：
二分答案，判断的时候用差分的思想。
差分…差分你懂吧？

好巧啊，我也不懂…
引用一下别人的解释：

懂了吧…

mdzz 看代码吧！

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int n,m;
int a[N],s[N],t[N],d[N],mk[N];
void read(int &x)
{
	char c=getchar();
	x=0;
	while (!(c>='0'&&c<='9'||c=='-')) c=getchar();
	int f=0;
	if (c=='-') {
		f=1;
		c=getchar();
	}
	while (c>='0'&&c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	if (f) x=-x;
}
bool check(int x)
{
	memset(mk,0,sizeof(mk));
	for (int i=1;i<=x;i++)
		mk[s[i]]+=d[i],mk[t[i]+1]-=d[i];
	for (int i=1,sum=0;i<=n;i++){
		sum+=mk[i];
		if (sum>a[i]) return false;
	}
	return true;
}
int solve()
{
	int l=1,r=m+1;
	while (l<r){
		int m=(l+r)>>1;
		if (!check(m)) r=m;
		else l=m+1;
	}
	return r;
}
int main()
{
	read(n);
	read(m);
	for (int i=1;i<=n;i++)
		read(a[i]);
	for (int i=1;i<=m;i++)
		read(d[i]),read(s[i]),read(t[i]);
	int ans=solve();
	if (ans>m) puts("0");
	else printf("-1\n%d\n",ans);
	return 0;
}

线段树的复杂度是 O(MlogN)
二分答案+差分的复杂度是 O(NlogM)
【其实一样
当然线段树常数肯定大一点，比赛的时候也有很多人线段树没满分。
不得不说 NOIP 确实是希望你巧妙的解题的。。。

最后再推荐一下 codevs 。。。
大家公认的界面领先 OJ 界至少3年 ←_←
还有一个原因就是。。。对蒟蒻比较友好。。。

=========2018/02/22=========
codevs 太凉了，推荐一下洛谷，贼6好吧

阅读全文 »

发表于 更新于 Valine：

特殊的日子

每个人的一生中都会或多或少有那么几个对自己很重要的日子，比如对于我来说，这一天就很重要。
答案格式wctf{日期} //友情提示，此题需要暴力破解，但只是爆破这段密文，不是爆破这个网站。。 = =！

题目里提到了暴力破解，应该就是某种不可逆的编码了。我学的比较少，刚开始想到的当然是MD5，不过MD5显然没有8位的。。。

后来直接查了查，发现是CRC32，这个好像在压缩包那边看到过。然后写程序，CRC32在 zlib 里面。

Note

To generate the same numeric value across all Python versions and platforms, use crc32(data) & 0xffffffff. If you are only using the checksum in packed binary format this is not necessary as the return value is the correct 32-bit binary representation regardless of sign.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import zlib

def crc32(para):
    res = zlib.crc32(para.encode("utf-8"))
    return '%x' % (res & 0xffffffff)

std = '4D1FAE0B'.lower()
for year in range(1500,3000):
    for month in range(1,13):
        for day in range(1,32):
            syyyy = str(year)
            smm = str(month)
            if month < 10:
                smm = '0' + smm
            sdd = str(day)
            if day < 10:
                sdd = '0' + sdd
            now = syyyy + smm + sdd
            if crc32(now) == std:
                print(now)

还看到有一种高端的写法：

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
import zlib
def crc32(st):
    crc = zlib.crc32(st.encode('utf-8'))
    if crc > 0:
        return "%x" % (crc & 0xffffffff)
    else:
        return "%x" % (crc & 0xffffffff)
    
#生成年'1000'~'3000'
year = [str(i) for i in range(1000,3000)]
#生成月'01'~'12'
month = [str(i) if i>9 else (str(0)+str(i)) for i in range(1,13) ]
#生成日'01'~'31'
day = [str(i) if i>9 else (str(0)+str(i)) for i in range(1,32) ]
    
#题目所给
realDate = '4D1FAE0B'.lower()
    
#穷举日期计算crc32值然后与题目给的值进行比对，一样则输出
import itertools
#利用itertools.product()生成年月日的所有组合
for item in itertools.product(year,month,day):
    date = ''.join(item)
    if crc32(date) == realDate:
        print(date)
阅读全文 »

发表于 更新于 Valine：

字符统计

题意也没什么好说的，主要是找了找 python 好用的 http 请求库，发现 requests 真的是很好用啊。。。还有就是一定要看清楚表单。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import requests
import re
import string
    
cookie = {'Cookie' : 'wctf_think_language=zh-CN;PHPSESSID=ltbxxxxxxxxxxxxxxxxxxxxfl6'}
r = requests.get("http://ctf.idf.cn/game/pro/37/", cookies = cookie)
    
text = re.search(r'<hr />\s(.*)\s<hr />', r.text, re.S).group(1)
res = ""
res += str(text.count('w'))
res += str(text.count('o'))
res += str(text.count('l'))
res += str(text.count('d'))
res += str(text.count('y'))
print(res)
    
payload = {'anwser':res}
r = requests.post("http://ctf.idf.cn/game/pro/37/", cookies = cookie, data = payload)
print(r.text)
阅读全文 »

发表于 更新于 Valine：

以下全文转载自：http://www.cnblogs.com/372465774y/archive/2012/10/16/2726282.html

// 下面是百度上找的错误证明
函数的积性即：若m,n互质，则φ(mn)=φ(m)φ(n)。由“m,n互质”可知m,n无公因数，

所以φ(m)φ(n)=m(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pn)·n(1-1/p1’)(1-1/p2’)(1-1/p3’)…(1-1/pn’)，//这里已经用了计算公式，而计算公式是需要先有积性前提才推导的

其中p1,p2,p3…pn为m的质因数，p1’,p2’,p3’…pn’为n的质因数，而m,n无公因数，
所以p1,p2,p3…pn，p1’,p2’,p3’…pn’互不相同，
所以p1,p2,p3…pn，p1’,p2’,p3’…pn’均为mn的质因数且为mn质因数的全集，
所以φ(mn)=mn(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pn)(1-1/p1’)(1-1/p2’)(1-1/p3’)…(1-1/pn’)，
所以φ(mn)=φ(m)φ(n)。

查了很多资料会证明了：
// 证明：
在证明前先了解下以下知识：
(a,b)代表最大公约数,[a,b]代表最小公倍数
m|(a-b) <=> a≡b (mod m)
a=pm+r (0<=r<m)
b=qm+r (0<=r<m)
由此可以推出：
性质1：a≡a（mod m），（反身性）
这个性质很显然.因为a-a=0=m·0。
性质2：若a≡b（mod m），那么b≡a（mod m），（对称性）。
性质3：若a≡b（mod m），b≡c（mod m），那么a≡c（mod m），（传递性）。
性质4：若a≡b（mod m），c≡d（mod m），那么a±c≡b±d（mod m），（可加减性）。
性质5：若a≡b（mod m），c≡d（mod m），那么ac≡bd（mod m）（可乘性）。
证明 ：m|(a-b) , m|(c-d) 设 a-b=km c-d=lm (ac-bd)=klm^2+(b+d)m =>m|(ac-bd)
性质6：若a≡b（mod m），那么an≡bn（mod m），（其中n为自然数）。
证明 ： m|(a-b) => m|n*(a-b)
性质7：若ac≡bc（mod m），（c，m）=1，那么a≡b（mod m），（记号（c，m）表示c与m的最大公约数）。
证明 ： m|c(a-b) d=(m,c)=>m/d|(a-b) => a≡b（mod m/d）=>当 d=1时 即（c,m）=1上面结论成立
性质8：若a≡b（mod m），那么a的n次方和b的n次方也对于m同余
证明 ：a^n-b^k=(a-b)(a^(n-1)+a^(n-2)b…b^(n-1)) +m|(a-b) ==>m|(a^n-b^n)
性质9：若 a≡b(mod m1) a≡b(mod m2)… a≡b(mod mi) 则 a≡b(mod [m1,m2,…mi])
证明：m1 |(a-b) m2|(a-b) …mi|(a-b) =>[m1,m2…mi]|(a-b) (因为 a-b里面含了 m集合的所有因子和每个因子的最大个数)
推论 m1,m2…mi两两互质 则 a≡b(mod m1m2…mi);

定义 ： X 代表 M 简化剩余系 个数φ(M) （有关简化正余系含义，百度吧）
Y 代表 N 简化剩余系 个数φ(N)
xi 代表X的元素 yj代表Y的元素

下面证明： φ(MN)=φ(M)φ(N) 其中(M,N)=1
我们需要证明
A: (xiN+yjM,MN)=1, xiN+yjM 代表的集合元素两两不在同一剩余系里 这样个数肯定是φ(M)φ(N)个了
B: xiN+yM 可以代表 MN 的简化剩余系每个元素

证明 A：
(xi,M)=1; => (xiN,M)=1; =>(xiN+yiM,M)=1; …1
(yi,N)=1; => (yiM,N)=1; =>(yiM+xiN,N)=1; …2
由 1,2 => (xiN+yiM,MN)=1; 上面都是由数之间互质才推导的

xiN+yjM≡xkN+ylM (mod MN)
=> xiN+yjM≡xkN+ylM (mod M)
=> xiN≡xkN (mod M)
由性质 7 =>xi≡xk (mod M)=> i=k 同理 j=l 所以 xiN+yjM 代表的集合元素两两不在同一剩余系里
证明 B:
设 Z 是MN 的简化剩余系的集合的任意某个元素
由于 （N,M）=1 => 存在 x0,y0 --> Mx0+Ny0=1 => Mx0Z+Ny0Z=Z
=>存在 x,y --> Mx+Ny=Z …1
(Z,MN)=1; =>(Mx+Ny,M)=1; =>(Ny,M)=1; =>(y,M)=1 =>y≡xi (mod M) 同理可得 x=yj (mod N)
y≡xi (mod M) => Ny≡Nxi (mod MN) 同理 Mx=Myj (mod MN)
根据同余性质
Ny+Mx=Myj+Nxi (mod MN)
=> Z=xiN+yjM (mod MN)
所 MN 的简化剩余系每个元素都可以用 xiN+yjM表示
综上 xiN+yjM 有 φ(M)φ(N)个元素 且每个与 MN互质，xiN+yjM两两不在同一剩余系里面
可得 φ(MN)=φ(M)φ(N) 其中(M,N)=1
http://www.cppblog.com/RyanWang/archive/2009/07/19/90512.aspx?opt=admin

E(x)表示比x小的且与x互质的正整数的个数。

阅读全文 »

发表于 更新于 Valine：

https://www.patest.cn/contests/gplt/L2-012
题意就不用我说了
比赛中写了个丑的不行的程序。。。
于是后来又写了一个非常STL风格的
想了想还是丢到博客了

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <sstream>
#include <string>
#include <algorithm>
using namespace std;

vector<int> a;
map<int,int> pos;

int getint(string s)
{
    stringstream ss;
    ss<<s;
    int res;
    ss>>res;
    return res;
}

bool right(string &s)
{
    if (s.find("root")!=string::npos)
        return (pos[getint(s)]==1);
    int p = s.find_first_of("-1234567890",s.find(" "));
    int x = getint(s);
    int y = getint(s.substr(p,s.size()-p));
    if (s.find("parent")!=string::npos)
        return (pos[x]==pos[y]>>1);
    if (s.find("child")!=string::npos)
        return (pos[x]>>1==pos[y]);
    //contains "siblings"
    return (pos[x]>>1==pos[y]>>1);
}

int main()
{
    int n,m,i,x;
    scanf("%d%d",&n,&m);
    for (i=0;i<n;i++)
    {
        scanf("%d",&x);
        a.push_back(x);
        push_heap(a.begin(),a.end(),greater<int>());
    }
    for (i=0;i<n;i++) pos[a[i]]=i+1;
    scanf("\n");
    while (m--)
    {
        string s;
        getline(cin,s);
        if (right(s)) puts("T");
        else puts("F");
    }
    return 0;
}
阅读全文 »

发表于 更新于 Valine：

http://gdutcode.sinaapp.com/problemset.php?page=2
从1169~1175题

本次代码大多基于 takio 的题解 ，自己看吧。。。
（堆在我的 Github 上了。。。以后题解都不堆网盘了）
本文准备更新一些本人遇到的问题。。。

A 一直没写出来。。。
现在(2016/7/13)终于想起来
又要打怪又要遍历不会处理
简略的也讲不清楚。。。
这个是我根据takio巨的代码改造的 (:з」∠)

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream> 
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
 
const int N=1001;
bool map[N][N];
struct Monster
{
    int id,def,add;
    bool operator>(const Monster& a) const
    {
        return def>a.def;
    }
};
vector<Monster> mon[N];
priority_queue<Monster,vector<Monster>,greater<Monster> > M;
bool vis[N];
int cnt[N],father[N];
int T,n,m,atk;
 
void dfs(int u,int fa)
{
    father[u]=fa;
    for (int i=0;i<cnt[u];i++)
        M.push(mon[u][i]);
    if (cnt[u]) return;
    for (int i=0;i<n;i++)
        if (map[u][i]&&i!=fa) dfs(i,u);
}
 
bool solve()
{
    while (!M.empty()) M.pop();
    dfs(0,-1);
    while (!M.empty())
    {
        Monster tmp=M.top();
        M.pop();
        if (atk<=tmp.def) return 0;
        atk+=tmp.add;
        int &u=tmp.id;
        if (--cnt[u]==0)
        {
            for (int i=0;i<n;i++)
                if (map[u][i]&&i!=father[u]) dfs(i,u);
        }
    }
    return 1;
}
 
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        int x,y,z,i;
        scanf("%d%d",&n,&m);
        memset(map,0,sizeof(map));
        memset(vis,0,sizeof(vis));
        for (i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            map[x][y]=map[y][x]=1;
        }
        for (i=0;i<n;i++) mon[i].clear();
        scanf("%d",&atk);
        for (i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            Monster tmp={x,y,z};
            mon[x].push_back(tmp);
        }
        for (i=0;i<n;i++)
            cnt[i]=mon[i].size();
        if (solve()) puts("Oh yes.");
        else puts("Good Good Study,Day Day Up.");
    }
    return 0;
}

B 想到了第一行没想到第二行
更没想到第三行！
至少我考虑了一下直接 DP 是 O(NM) 于是没写
自我感觉不算特别智障

D 两个条件都想到了。。。
但是 tm 把叶子数错了。。。
竟然拿 1<<s 跟 n-s 比。。。_(:з」∠)_

E 没有想到那么机智的做法。。。
拿了个单调栈乱搞。。。太弱智了。。。

F 优化1其实包含于优化2 。。。
也是2、3两个都想到了。。。
但是感觉既然是随机数据2应该没什么卵用。。。
TLE
看题解加了以后快了好多突然想到容斥的复杂度是指数级别的。。。
就算只扔掉一个数时间也能变成一半。。。

阅读全文 »

发表于 更新于 Valine：

A HDOJ-2544
模板题。不解释了。
顺便学习了一下dij+优先队列的姿势。
【感觉代码量跟普通dij很接近啊。。。
每个点入队一次，复杂度 O(NlogN)

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
62
63
64
65
66
67
68
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

typedef pair<int,int> pii;

const int N=101;
const int M=10001*2;
const int INF=1<<29;
struct edge
{
	int go,next,val;
};
edge eg[M];
int last[N],done[N],d[N],pre[N];
int tot;

void add(int x,int y,int z)
{
	eg[++tot].go=y;
	eg[tot].val=z;
	eg[tot].next=last[x];
	last[x]=tot;
}

int main()
{
	int n,m,i,x,y,z;
	while (scanf("%d%d",&n,&m),n)
	{
		tot=0;
		memset(last,0,sizeof(last));
		for (i=1;i<=m;i++)
		{
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
			add(y,x,z);
		}
		priority_queue<pii,vector<pii>,greater<pii> > q;
		for (i=1;i<=n;i++) d[i]=INF;
		memset(done,0,sizeof(done));
		memset(pre,0,sizeof(pre));
		d[1]=0;pre[1]=1;
		q.push(make_pair(0,1));
		while (!q.empty())
		{
			pii u=q.top();
			q.pop();
			int v=u.second;
			if (done[v]) continue;
			done[v]=1;
			for (i=last[v];i;i=eg[i].next)
			{
				int x=eg[i].go;
				if (d[x]>d[v]+eg[i].val)
				{
					d[x]=d[v]+eg[i].val;
					pre[x]=v;
					q.push(make_pair(d[x],x));
				}
			}
		}
		printf("%d\n",d[n]);
	}
	return 0;
}

B POJ-1860
我放的时候以为是个大水题
其实也就是个类似判正环的。。。
（赋初值为0的话就保证了每次操作不出现负数）
主要是没想到 Bellman-Ford 然后其他的又写不太清楚。。。
后来查了一下还是写 Bellman-Ford 比较简洁：O(NM)

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
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N=101;
const int M=101*2;
const int INF=1<<29;
struct edge
{
	int st,ed;
	double c,r;
};
edge eg[M];
double d[N];
int n,m,tot;

void add(int x,int y,double r,double c)
{
	eg[++tot].st=x;
	eg[tot].ed=y;
	eg[tot].r=r;
	eg[tot].c=c;
}

bool Bellman_Ford(int s,double val)
{
	int i,j;
	for (i=1;i<=n;i++) d[i]=0;
	d[s]=val;
	for (i=1;i<n;i++)
	{
		int f=0;
		for (j=1;j<=tot;j++)
		{
			int u=eg[j].st,v=eg[j].ed;
			if (d[v]<(d[u]-eg[j].c)*eg[j].r)
			{
				f=1;
				d[v]=(d[u]-eg[j].c)*eg[j].r;
			}
		}
		if (f==0) break;
	}
	if (d[s]>val) return true;
	for (j=1;j<=tot;j++)
	{
		int u=eg[j].st,v=eg[j].ed;
		if (d[v]<(d[u]-eg[j].c)*eg[j].r)
			return true;
	}
	return false;
}

int main()
{
	int i,x,y,s;
	double val,r,c;
	scanf("%d%d%d%lf",&n,&m,&s,&val);
	tot=0;
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		scanf("%lf%lf",&r,&c);
		add(x,y,r,c);
		scanf("%lf%lf",&r,&c);
		add(y,x,r,c);
	}
	if (Bellman_Ford(s,val)) puts("YES");
	else puts("NO");
	return 0;
}

C HDOJ-4514
我竟然会有一天因为读入忘记加 !=EOF TLE七次

看了看网上的题解 基本都是并查集+DP。
其实没有必要。。。
无向图判环最基本的方法就是DFS。。。
其次 不成环的话就是森林
每棵树用两次BFS求直径的方法
也就是说这题是DFS+BFS。。。
这样就完全不会有空间的问题
不过我也不知道出题人的本意是哪个。。。
判环时每个点遍历一次，求长度时每个点遍历两次，复杂度 O(N)

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <cstdio>
#include <cstring>

const int N=100001;
const int M=1000001*2;
const int INF=1<<29;
struct edge
{
	int go,next,val;
};
edge eg[M];
int last[N],vis[N],d[N],q[N];
int tot;

void add(int x,int y,int z)
{
	eg[++tot].go=y;
	eg[tot].val=z;
	eg[tot].next=last[x];
	last[x]=tot;
}

bool circle(int u,int pre)
{
	int i,ans=0;
	vis[u]=1;
	for (i=last[u];i!=-1;i=eg[i].next)
	{
		if ((i^pre)!=1)
		{
			if (vis[eg[i].go]) return 1;
			ans|=circle(eg[i].go,i);
			if (ans==1) return 1;
		}
	}
	return ans;
}

void bfs(int s)
{
	int l=0,r=1,i;
	q[1]=s;	d[s]=0;
	while (l<r)
	{
		int u=q[++l];
		for (i=last[u];i!=-1;i=eg[i].next)
		{
			int v=eg[i].go;
			if (d[v]==-1)
			{
				q[++r]=v;
				d[v]=eg[i].val+d[u];
			}
		}
	}
}

int main()
{
	int n,m,i,j,x,y,z;
	while (scanf("%d%d",&n,&m)!=EOF)
	{
		tot=-1;
		for (i=1;i<=n;i++) last[i]=-1;
		for (i=1;i<=m;i++)
		{
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
			add(y,x,z);
		}
		memset(vis,0,sizeof(vis));
		for (i=1;i<=n;i++)
			if (!vis[i])
				if (circle(i,-1)) break;
		if (i<=n) puts("YES");
		else 
		{
			int ans=-1,p;
			memset(vis,0,sizeof(vis));
			for (j=1;j<=n;j++)
				if (!vis[j])
				{
					for (i=1;i<=n;i++) d[i]=-1;
					bfs(j); p=1;
					for (i=1;i<=n;i++)
						if (d[i]>d[p]) p=i;
					for (i=1;i<=n;i++) d[i]=-1;
					bfs(p); p=1;
					for (i=1;i<=n;i++)
						if (d[i]!=-1) vis[i]=1;
					for (i=1;i<=n;i++)
						if (d[i]>d[p]) p=i;
					if (d[p]>ans) ans=d[p];
				}
			printf("%d\n",ans);
		}
	}
	return 0;
}

D HDOJ-2196
【准确的说跟上一题知识点有重叠。。。
很明显题目里给的是一棵树
可以证明，到 u 最远距离的 v 一定是直径的一端。
假设有 v’ 使得 u-v’ 距离更长，
1、u 在直径上：记直径另一端为 s ，显然有 s->u->v’ 比 s->u->v 长，这与 v 为直径一端矛盾。
2、u 不在直径上：记直径另一端为 s ，
以 u 为根，v’ 不能在 u->s 和 u->v 上。
则 (u->v’) + (u->s) 大于 (u->v) + (u->s) 大于等于 (v->s) ，矛盾。

于是只需要求直径两端到各个点的距离。
每个点被遍历三次，复杂度 O(N)

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
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=10001;
const int M=10001*2;
const int INF=1<<29;
struct edge
{
	int go,next,val;
};
edge eg[M];
int last[N],d[N],d2[N],q[N];
int tot;

void add(int x,int y,int z)
{
	eg[++tot].go=y;
	eg[tot].val=z;
	eg[tot].next=last[x];
	last[x]=tot;
}

void bfs(int s,int* d)
{
	int l=0,r=1,i;
	q[1]=s;	d[s]=0;
	while (l<r)
	{
		int u=q[++l];
		for (i=last[u];i!=-1;i=eg[i].next)
		{
			int v=eg[i].go;
			if (d[v]==-1)
			{
				q[++r]=v;
				d[v]=eg[i].val+d[u];
			}
		}
	}
}

int main()
{
	int n,i,p,y,z;
	while (scanf("%d",&n)!=EOF)
	{
		tot=-1;
		for (i=1;i<=n;i++) last[i]=-1;
		for (i=2;i<=n;i++)
		{
			scanf("%d%d",&y,&z);
			add(i,y,z);
			add(y,i,z);
		}
		for (i=1;i<=n;i++) d[i]=-1;
		bfs(1,d);
		for (p=1,i=1;i<=n;i++)
			if (d[i]>d[p]) p=i;
		for (i=1;i<=n;i++) d[i]=-1;
		bfs(p,d);
		for (p=1,i=1;i<=n;i++)
			if (d[i]>d[p]) p=i;
		for (i=1;i<=n;i++) d2[i]=-1;
		bfs(p,d2);
		for (i=1;i<=n;i++)
			printf("%d\n",max(d[i],d2[i]));
	}
	return 0;
}

E HDOJ-4885
题意就是平面上有好多加油站
一个人要从学校回家
这个人有一辆满油的摩托车
跑到 L 距离时会用完油
在加油站加油每次都要加满
而且每次加油之前走的都是直线

阅读全文 »

发表于 更新于 Valine：

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

。。。莫名其妙写了个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;
}
阅读全文 »

发表于 更新于 Valine：

选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;
}

这个实在是太诡异了。。。
一般情况下我都是认为 G++ 比 VC++ 靠谱的
【当然 MinGW 算是其中比较不靠谱的。。。
而且编译环节还都没有问题。。。

===============当天的更新===============
有学长告诉我这个是 IO 的问题 加了读入输出优化就可以过
然后我又去写了一下

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <cstdio>
#include <cstring>

const int N=1000010;
int a[N],q[N],c[N];

void read(int &x)
{
	char c=getchar();
	x=0;
	while (!(c>='0'&&c<='9'||c=='-')) c=getchar();
	int f=0;
	if (c=='-')
	{
		f=1;
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();	
	}
	if (f) x=-x;
}

void write(int x)
{
	if (x==0)
	{
		putchar('0');
		return;
	}
	if (x<0) putchar('-'),x=-x;
	char s[20];
	int i=0;
	while (x)
	{
		s[i++]=x%10+'0';
		x/=10;
	}
	s[i]=0;
	for (i--;i>=0;i--) putchar(s[i]);
}

int  main()
{
	int n,k,i,l,r;
	read(n);
	read(k);
	for (i=1;i<=n;i++) read(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++)
	{
		write(q[l]);
		putchar(' ');
		while (q[r]>=a[i]&&r>=l) r--;
		c[++r]=i;
		q[r]=a[i];
		if (i-k>=c[l]) l++;
	}
	write(q[l]);
	puts("");
	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++)
	{
		write(q[l]);
		putchar(' ');
		while (q[r]<=a[i]&&r>=l) r--;
		c[++r]=i;
		q[r]=a[i];
		if (i-k>=c[l]) l++;
	}
	write(q[l]);
	puts("");
	return 0;
}

果然 AC 了。
这个倒是比较符合我对 G++ 的印象
一般 -o 是不会有什么优化的
那这个问题就比较无聊了。。。
真正用的时候肯定不是 -o 。。。

阅读全文 »