bef->NO.14

[NOI2005]瑰丽华尔兹

题目背景

你跳过华尔兹吗?当音乐响起,当你随着旋律滑动舞步,是不是有一种漫步仙境的惬意?

众所周知,跳华尔兹时,最重要的是有好的音乐。但是很少有几个人知道,世界上最伟大的钢琴家一生都漂泊在大海上,他的名字叫丹尼·布德曼·T.D.·柠檬·1900,朋友们都叫他1900。

1900 在20 世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上。很不幸,他刚出生就被抛弃,成了孤儿。1900 孤独的成长在弗吉尼亚号上,从未离开过这个摇晃的世界。也许是对他命运的补偿,上帝派可爱的小天使艾米丽照顾他。可能是天使的点化,1900拥有不可思议的钢琴天赋:从未有人教,从没看过乐谱,但他却能凭着自己的感觉弹出最沁人心脾的旋律。当1900 的音乐获得邮轮上所有人的欢迎时,他才8 岁,而此时,他已经乘着海轮往返欧美大陆50 余

次了。

虽说是钢琴奇才,但1900还是个孩子,他有着和一般男孩一样的好奇和调皮,只不过更多一层浪漫的色彩罢了:这是一个风雨交加的夜晚,海风卷起层层巨浪拍打着弗吉尼亚号,邮轮随着巨浪剧烈的摇摆。船上的新萨克斯手迈克斯·托尼晕船了,1900 招呼托尼和他

一起坐到舞厅里的钢琴上,然后松开了固定钢琴的闸,于是,钢琴随着海轮的倾斜滑动起来。准确的说,我们的主角1900、…

题目描述

不妨认为舞厅是一个N行M列的矩阵,矩阵中的某些方格上堆放了一些家具,其他的则是空地。钢琴可以在空地上滑动,但不能撞上家具或滑出舞厅,否则会损坏钢琴和家具,引来难缠的船长。每个时刻,钢琴都会随着船体倾斜的方向向相邻的方格滑动一格,相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法:如果不施魔法,则钢琴会滑动;如果施魔法,则钢琴会原地不动。

艾米丽是个天使,她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行的路程尽量长,这样1900 会非常高兴,同时也有利于治疗托尼的晕船。但艾米丽还太小,不会算,所以希望你能帮助她。

输入输出格式

输入格式:

输入文件的第一行包含5个数N, M, x, y和K。N和M描述舞厅的大小,x和y为钢琴的初始位置;我们对船体倾斜情况是按时间的区间来描述的,且从1开始计算时间,比如“在[1, 3]时间里向东倾斜,[4, 5]时间里向北倾斜”,因此这里的K表示区间的数目。

以下N行,每行M个字符,描述舞厅里的家具。第i 行第j 列的字符若为‘ . ’,则表示该位置是空地;若为‘ x ’,则表示有家具。

以下K行,顺序描述K个时间区间,格式为:si ti di(1 ≤ i ≤ K)。表示在时间区间[si, ti]内,船体都是向di方向倾斜的。di为1, 2, 3, 4中的一个,依次表示北、南、西、东(分别对应矩阵中的上、下、左、右)。输入保证区间是连续的,即

s1 = 1 ti = si-1 + 1 (1 < i ≤ K)

tK = T

输出格式:

输出文件仅有1行,包含一个整数,表示钢琴滑行的最长距离(即格子数)。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
4 5 4 1 3
..xx.
.....
...x.
.....
1 3 4
4 5 1
6 7 3

输出样例#1:

1
6

说明

钢琴的滑行路线:

img

钢琴在“×”位置上时天使使用一次魔法,因此滑动总长度为6。

【数据范围】

50%的数据中,1≤N, M≤200,T≤200;

100%的数据中,1≤N, M≤200,K≤200,T≤40000。

题解

这道题的dp实在是挺好想的,我一开始以为是道高思维难度DP。

最最基础也最最简单的dp状态就是

表示i时间后到达(j,k)的最长滑行路线,然后用

表示

的上一个合法位置

那么

期望得分:40

然后我们很容易发现对于每一个时间区间方向是单调的,这样的话我们就可以用

表示i时间段后到达(j,k)的最长滑行路线,然后

w是个枚举量,(j’,k’)由

确定

然后不合法的状态就不用转移。

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define max(a,b) (a) > (b) ? (a) : (b)
#define maxn 205
char ch;
int f[maxn][maxn][maxn] , n , m , k , l[maxn] , r[maxn] , g[maxn][maxn] , xx , yy , dr[maxn] , ans;
int main()
{
scanf("%d%d%d%d%d",&n,&m,&xx,&yy,&k);
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= m ; ++j)
std::cin>>ch , g[i][j] = (ch=='x');
// printf("%d\n",k);
for(int i = 1 ; i <= k ; ++i)
scanf("%d%d%d",&l[i],&r[i],&dr[i]);
// puts("OK");
int dx , dy ;
std::memset(f,-1,sizeof(f));
f[0][xx][yy] = 0;
for(int i = 1 ; i <= k ; ++i)
{
if(dr[i] == 1) dx = -1 , dy = 0;
if(dr[i] == 2) dx = 1 , dy = 0;
if(dr[i] == 3) dx = 0 , dy = -1;
if(dr[i] == 4) dx = 0 , dy = 1;
for(int x = 1 ; x <= n ; ++x)
for(int y = 1 ; y <= m ; ++y)
{
if(f[i-1][x][y] == -1) continue;
if(g[x][y]) continue;
for(int w = 0 ; w <= r[i] - l[i] + 1 ; ++w)
{
int nx = x + w * dx , ny = y + w * dy ;
if(nx < 1 || nx > n || ny < 1 || ny > m || g[nx][ny]) break;
f[i][nx][ny] = max(f[i][nx][ny] , f[i-1][x][y] + w);
}
}
}
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= m ; ++j)
ans = max(ans , f[k][i][j]);
printf("%d",ans);
}

序列合并

题目描述

有两个长度都是N的序列A和B,在A和B中各取一个数相加可以得到N^2N2个和,求这N^2N2个和中最小的N个。

输入输出格式

输入格式:

第一行一个正整数N;

第二行N个整数AiAi, 满足A_i\le A{i+1}Ai≤Ai+1且A_i\le 10^9Ai≤109;

第三行N个整数BiBi, 满足B_i\le B{i+1}Bi≤Bi+1且B_i\le 10^9Bi≤109.

【数据规模】

对于50%的数据中,满足1<=N<=1000;

对于100%的数据中,满足1<=N<=100000。

输出格式:

输出仅一行,包含N个整数,从小到大输出这N个最小的和,相邻数字之间用空格隔开。

输入输出样例

输入样例#1:

1
2
3
3
2 6 6
1 4 8

输出样例#1:

1
3 6 7

题解

一道很不错的思路题。

经过我的冥思苦想,发现假如我们对每个数编号0,1,然后放进同一个数组排序,只需要看看前面有几个和他编号不同的,显然是错误的。

期望得分:0分

然后我们考虑暴力,堆模拟。

期望得分:50 , 真好

最后我们的暴力价格剪枝,对于

他们全都得在n个和以内,否则就不用加入优先队列

期望得分:100 , 很玄学

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
std::priority_queue<int , std::vector<int> , std::greater<int> > q;
#define maxn 100005
int n , flag , A[maxn] , B[maxn];
int main()
{
scanf("%d",&n);
for(int i = 1 ; i <= n ; ++i)
scanf("%d",&A[i]) ;
for(int i = 1 ; i <= n ; ++i)
scanf("%d",&B[i]);
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= n ; ++j)
{
if(i*j > n)
break;
q.push(A[i]+B[j]);
}
for(int i = 1 ; i <= n ; ++i)
printf("%d " , q.top()) , q.pop();

}

哈希冲突

题目背景

此题约为NOIP提高组Day2T2难度。

题目描述

众所周知,模数的hash会产生冲突。例如,如果模的数p=7,那么411便冲突了。

B君对hash冲突很感兴趣。他会给出一个正整数序列value[]

自然,B君会把这些数据存进hash池。第value[k]会被存进(k%p)这个池。这样就能造成很多冲突。

B君会给定许多个px,询问在模p时,x这个池内数的总和

另外,B君会随时更改value[k]。每次更改立即生效。

保证1<=p<n1<=p<n.

输入输出格式

输入格式:

第一行,两个正整数n,m,其中n代表序列长度,m代表B君的操作次数。

第一行,n个正整数,代表初始序列。

接下来m行,首先是一个字符cmd,然后是两个整数x,y

  • cmd='A',则询问在模x时,y池内数的总和
  • cmd='C',则将value[x]修改为y

输出格式:

对于每个询问输出一个正整数,进行回答。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
10 5
1 2 3 4 5 6 7 8 9 10
A 2 1
C 1 20
A 3 1
C 5 1
A 5 0

输出样例#1:

1
2
3
25
41
11

说明

样例解释

A 2 1的答案是1+3+5+7+9=25.

A 3 1的答案是20+4+7+10=41.

A 5 0的答案是1+10=11.

数据规模

对于10%的数据,有n<=1000,m<=1000.

对于60%的数据,有n<=100000.m<=100000.

对于100%的数据,有n<=150000,m<=150000.

保证所有数据合法,且1<=value[i]<=1000.

题解

自己yy出了一个根号优化。。

我们把模数分成小于等于

和其他两部分。

然后对于小模数,我们

预处理每个数在

以下的模数的余数的和(即hash池)

每次修改除了要改原数组,还要

地更新预处理的数组。

大模数直接暴力就好,最后时间复杂度

可以通过本题。

Code :

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
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#define maxn 150005
#define maxsqrt 400
int block[maxsqrt][maxsqrt] , n , p , m , x , y , v[maxn] , size;
char ch;
inline void update(int x , int y)
{
int val = v[x];
v[x] = y;
for(int i = 1 ; i <= size ; ++i)
block[i][x%i] -= val , block[i][x%i] += v[x];
}
inline int query(int x , int y)
{
return block[x][y];
}
inline int brute(int x , int y)
{
int ans = 0;
for(int i = y ; i <= n ; i += x)
ans += v[i];
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1 ; i <= n ; ++i)
scanf("%d",&v[i]);
size = std::sqrt(n);
for(int i = 1 ; i <= size ; ++i)
for(int j = 1 ; j <= n ; ++j)
block[i][j%i] += v[j];
for(int i = 1 ; i <= m ; ++i)
{
std::cin>>ch;
if(ch == 'A')
{
scanf("%d%d",&x,&y);
if(x <= size) printf("%d\n",query(x,y));
else printf("%d\n",brute(x,y));
}
else if(ch == 'C') scanf("%d%d",&x,&y) , update(x,y);
}
}

[USACO07NOV]电话线Telephone Wire

题目描述

Farmer John’s cows are getting restless about their poor telephone service; they want FJ to replace the old telephone wire with new, more efficient wire. The new wiring will utilize N (2 ≤ N ≤ 100,000) already-installed telephone poles, each with some heighti meters (1 ≤ heighti ≤ 100). The new wire will connect the tops of each pair of adjacent poles and will incur a penalty cost C × the two poles’ height difference for each section of wire where the poles are of different heights (1 ≤ C ≤ 100). The poles, of course, are in a certain sequence and can not be moved.

Farmer John figures that if he makes some poles taller he can reduce his penalties, though with some other additional cost. He can add an integer X number of meters to a pole at a cost of X2.

Help Farmer John determine the cheapest combination of growing pole heights and connecting wire so that the cows can get their new and improved service.

给出若干棵树的高度,你可以进行一种操作:把某棵树增高h,花费为h*h。

操作完成后连线,两棵树间花费为高度差*定值c。

求两种花费加和最小值。

输入输出格式

输入格式:

* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Line i+1 contains a single integer: heighti

输出格式:

* Line 1: The minimum total amount of money that it will cost Farmer John to attach the new telephone wire.

输入输出样例

输入样例#1:

1
2
3
4
5
6
5 2
2
3
5
1
4

输出样例#1:

1
15

题解

一个很简单的dp

分析如何设计状态,显然从前往后dp每个数只和它前面的一个数在计算的时候有关系

因此设

表示前i个最后一个高为j的费用。

然后转移很显然

Code:

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 100005
#define maxh 105
int f[maxn][maxh] , n , h[maxn] , c , hmax , ans = 0x7fffffff;
inline int abs(int x){return x >= 0 ? x : (-x) ;}
int main()
{
scanf("%d%d",&n,&c);
for(int i = 1 ; i <= n ; ++i)
scanf("%d",&h[i]) , hmax = std::max(hmax , h[i]);
// hmax = 99;
std::memset(f,30,sizeof(f));
for(int i = 1 ; i <= hmax ; ++i)
f[1][i] = (h[1] - i) * (h[1] - i);
for(int i = 2 ; i <= n ; ++i)
for(int j = h[i] ; j <= hmax ; ++j)//f[i][j] = std::min(f[i][j] , f[i-1][k] + (h[i] - j) * (h[i] - j) + c * abs(k - j));
for(int k = h[i-1] ; k <= hmax ; ++k)
f[i][j] = std::min(f[i][j] , f[i-1][k] + (h[i] - j) * (h[i] - j) + c * abs(k - j));
for(int i = 1 ; i <= hmax ; ++i)
ans = std::min(ans , f[n][i]);
printf("%d",ans);
}

[APIO2008]免费道路

题目描述

新亚(New Asia)王国有 N 个村庄,由 M 条道路连接。其中一些道路是鹅卵石路,而其它道路是水泥路。保持道路免费运行需要一大笔费用,并且看上去 王国不可能保持所有道路免费。为此亟待制定一个新的道路维护计划。

国王已决定保持尽可能少的道路免费,但是两个不同的村庄之间都应该一条且仅由一条 且仅由一条免费道路的路径连接。同时,虽然水泥路更适合现代交通的需 要,但国王也认为走在鹅卵石路上是一件有趣的事情。所以,国王决定保持刚好 K 条鹅卵石路免费。

举例来说,假定新亚王国的村庄和道路如图 3(a)所示。如果国王希望保持两 条鹅卵石路免费,那么可以如图 3(b)中那样保持道路(1, 2)、(2, 3)、(3, 4)和(3, 5) 免费。该方案满足了国王的要求,因为:(1)两个村庄之间都有一条由免费道 路组成的路径;(2)免费的道路已尽可能少;(3)方案中刚好有两条鹅卵石道路 (2, 3)和(3, 4)

img

图 3: (a)新亚王国中村庄和道路的一个示例。实线标注的是水泥路,虚线标注 的是鹅卵石路。(b)一个保持两条鹅卵石路免费的维护方案。图中仅标出了免 费道路。

给定一个关于新亚王国村庄和道路的述以及国王决定保持免费的鹅卵石 道路数目,写一个程序确定是否存在一个道路维护计划以满足国王的要求,如果 存在则任意输出一个方案。

输入输出格式

输入格式:

输入第一行包含三个由空格隔开的整数:

N,村庄的数目(1≤N≤20,000);

M,道路的数目(1≤M≤100,000);

K,国王希望保持免费的鹅卵石道路数目(0≤K≤N - 1)。

此后 M 行述了新亚王国的道路,编号分别为 1 到 M。第(i+1)行述了第 i 条 道路的情况。用 3 个由空格隔开的整数述:

ui 和 vi,为第 i 条道路连接的两个村庄的编号,村庄编号为 1 到 N;

ci,表示第 i 条道路的类型。ci = 0 表示第 i 条道路是鹅卵石路,ci = 1 表 示第 i 条道路是水泥路。

输入数据保证一对村庄之间至多有一条道路连接

输出格式:

如果满足国王要求的道路维护方案不存在,你的程序应该在输出第一行打印 no solution。 否则,你的程序应该输出一个符合要求的道路维护方案,也就是保持免费的 道路列表。按照输入中给定的那样输出免费的道路。如果有多种合法方案,你可 以任意输出一种。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
5 7 2 
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1

输出样例#1:

1
2
3
4
3 2 0 
4 3 0
5 3 1
1 2 1

题解

我一眼就想到了边权随机化的带权二分,啊哈哈哈独立切了APIO的题。

WQS二分前面已经说过了。

然后就没什么了,挺简单一道题。

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <ctime>
#define maxn 20005
#define maxm 100005
#define ll long long
ll cnt , tot , n , m , mst , ans , f[maxn] , k , flag;
bool get[maxm] , vis[maxm];
struct edge{
ll from , to , dis , col;
}e[maxm] , g[maxm];
inline bool operator < (edge x , edge y)
{
if(x.dis == y.dis) return x.col < y.col ;
return x.dis < y.dis;
}
int find(int x)
{
if(f[x] != x) return f[x] = find(f[x]);
return f[x];
}
inline void add(ll x , ll y, ll dis , ll col )
{
e[++cnt].from = x ;
e[cnt].to = y;
e[cnt].col = col;
e[cnt].dis = dis;
}
inline ll solve(ll ad)
{
std::memset(get,false,sizeof(get));
ll count = 0 ;
for(int i = 1 ; i <= m ; ++i)
g[i] = e[i];
for(int i = 1 ; i <= m ; ++i)
if(!g[i].col) g[i].dis += ad;
for(int i = 1 ; i <= n ; ++i)
f[i] = i;
tot = 0;
std::sort(g+1,g+m+1);
for(int i = 1 ; i <= m && tot < n ; ++i)
{
int fx = find(g[i].from) , fy = find(g[i].to);
if(fx != fy)
{
f[fx] = fy;
if(!g[i].col) ++count;
++tot;
get[i] = true;
if(tot == n-1) break;
}
}
return count ;
}
inline void print()
{
for(int i = 1 ; i <= m ; ++i)
if(get[i])
printf("%lld %lld %lld\n",g[i].from , g[i].to , g[i].col);
}
int main()
{
srand(time(NULL));
scanf("%lld%lld%lld",&n,&m,&k);
ll x , y , d , col;
for(int i = 1 ; i <= m ; ++i)
scanf("%lld%lld%lld",&x,&y,&col) , d = rand() % 2122473297 + 1 , add(x , y , d , col);
ll l = -100000000009 , r = 100000000009 ;
while(l <= r)
{
ll mid = l + r >> 1;
ll now = solve(mid);
if(now == k) {print() ;flag = 1; break;}
if(now > k) l = mid + 1;
else r = mid - 1;
}
if(!flag) printf("no solution");
}

正则表达式

题目背景

小Z童鞋一日意外的看到小X写了一个正则表达式的高级程序,这个正则表达式程序仅仅由字符“0”,“1”,“.”和“*”构成,但是他能够匹配出所有在OJ上都AC的程序的核心代码!小Z大为颇感好奇,于是他决定入侵小X的电脑上去获得这个正则表达式的高级程序。

题目描述

在Internet网络中的每台电脑并不是直接一对一连通的,而是某些电脑之间存在单向的网络连接,也就是说存在A到B的连接不一定存在B到A的连接,并且有些连接传输速度很快,有些则很慢,所以不同连接传输所花的时间是有大有小的。另外,如果存在A到B的连接的同时也存在B到A的连接的话,那么A和B实际上处于同一局域网内,可以通过本地传输,这样花费的传输时间为0。

现在小Z告诉你整个网络的构成情况,他希望知道从他的电脑(编号为1),到小X的电脑(编号为n)所需要的最短传输时间。

输入输出格式

输入格式:

第一行两个整数n, m, 表示有n台电脑,m个连接关系。

接下来m行,每行三个整数u,v,w;表示从电脑u到电脑v传输信息的时间为w。

输出格式:

输出文件仅一行为最短传输时间。

输入输出样例

输入样例#1:

1
2
3
3 2
1 2 1
2 3 1

输出样例#1:

1
2

输入样例#2:

1
2
3
4
5
6
5 5
1 2 1
2 3 6
3 4 1
4 2 1
3 5 2

输出样例#2:

1
3

说明

对于40%的数据,1<=n<=1000, 1<=m<=10000

对于70%的数据,1<=n<=5000, 1<=m<=100000

对于100%的数据,1<=n<=200000, 1<=m<=1000000


题解

Tarjan缩点+DAGdp

似乎现在Tarjan缩点还是可以的,虽然Tarjan是一个我只会感性理解不会证明的算法。

Code:

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
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cstring>
#define maxn 200005
#define maxm 1000005
inline int read()
{
int x = 0 , f = 1;
char ch = getchar();
while(ch > '9' || ch < '0') if(ch == '-') f = -1 , ch = getchar() ; else ch = getchar();
while(ch <= '9' && ch >= '0')
x = x * 10 + ch - 48;
return x * f;
}
int head[maxn] , n , m , id[maxn] , tot , x , y , dis , cnt , h[maxn] , cntr , dfn[maxn] , low[maxn] , idx , d[maxn] , f[maxn] , s , t;
bool get[maxn] , ins[maxn] , vis[maxn];
std::stack<int> st;
struct edge{
int next , to , dis;
}e[maxm*2] , r[maxm*2];
inline void add(int x , int y , int d)
{
e[++cnt].next = head[x] ;
e[cnt].to = y;
e[cnt].dis = d;
head[x] = cnt;
}
inline void addr(int x , int y , int dis)
{
r[++cntr].next = h[x] ;
r[cntr].to = y;
r[cntr].dis = dis;
h[x] = cntr;
++d[y];
}
void Tarjan(int x)
{
dfn[x] = low[x] = ++idx;
st.push(x);
ins[x] = true;
for(int i = head[x] ; i ; i = e[i].next)
{
int v = e[i].to;
if(!dfn[v])
{
Tarjan(v);
low[x] = std::min(low[x] , low[v]);
}
else if(dfn[v] && ins[v]) low[x] = std::min(low[x] , dfn[v]);
}
if(dfn[x] == low[x])
{
++tot;
while(st.top() != x)
{
id[st.top()] = tot;
ins[st.top()] = false;
if(st.top() == 1) s = tot;
if(st.top() == n) t = tot;
st.pop();
}
id[st.top()] = tot;
if(st.top() == 1) s = tot;
if(st.top() == n) t = tot;
ins[st.top()] = false ;
st.pop();
}
}
void Print(int x)
{
// putchar(10);
putchar(10);
for(int i = h[x] ; i ; i = r[i].next)
if(!vis[i]) printf("%d -> %d\n",x,r[i].to) , vis[x] = true , Print(r[i].to);
}
inline int dp()
{
std::queue<int> q;
std::memset(f,0x7f,sizeof(f));
f[s] = 0;
q.push(s);
while(!q.empty())
{
int k = q.front();
q.pop();
for(int i = h[k] ; i ; i = r[i].next)
{
f[r[i].to] = std::min(f[r[i].to] , f[k] + r[i].dis) , --d[r[i].to];
if(!d[r[i].to]) q.push(r[i].to);
}
}
return f[t];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1 ; i <= m ; ++i)
scanf("%d%d%d",&x,&y,&dis), add(x,y,dis);
for(int i = 1 ; i <= n ; ++i)
if(!dfn[i]) Tarjan(i);
// for(int i = 1 ; i <= n ; ++i)
// printf("%d ",id[i]);
for(int i = 1 ; i <= n ; ++i)
for(int j = head[i] ; j ; j = e[j].next)
if(id[i] != id[e[j].to])
addr(id[i] , id[e[j].to] , e[j].dis);
dp();
printf("%d",f[t]);
}

构造完全图

题目描述

对于完全图 G,若有且仅有一棵最小生成树为 T,则称完全图 G 是树 T 扩展出的。

给你一棵树 T,找出 T 能扩展出的边权和最小的完全图 G。

输入格式

第一行 N 表示树 T 的点数;

接下来 N−1行三个整数 Si,Ti,Di;描述一条边

保证输入数据构成一棵树。

输出格式

输出仅一个数,表示最小的完全图 G 的边权和。

样例

样例输入

1
2
3
4
4  
1 2 1
1 3 1
1 4 2

样例输出

1
12

样例说明

添加 D(2,3)=2,D(3,4)=3,D(2,4)=3D(2, 3)=2, D(3, 4)=3, D(2, 4)=3D(2,3)=2,D(3,4)=3,D(2,4)=3 即可。

数据范围与提示

对于 20% 的数据,

对于 50% 的数据,

对于 100%的数据,

题解

一道根据Kruskal贪心的好题。

我们想象一下原来的完全做最小生成树的过程。

当合并两个联通块的时候,设这两个联通块的大小分别为x,y

它们之间有x*y条边,其中一条是最小生成树的边,由题目给定,另外的只需要是这条边边长+1就可以了,为什么呢?

为什么呢?因为Kruskal在之前合并两个联通块的时候用的是不大于当前的边,这意味着只要我们当前连的边不会替代当前这条边(也就是大于等于,即+1),就不会和两个联通块内部的边造成冲突。

因此将MST的边从小到大排序,合并的同时统计答案即可。

[HAOI2012]容易题

题目描述

为了使得大家高兴,小Q特意出个自认为的简单题(easy)来满足大家,这道简单题是描述如下:

有一个数列A已知对于所有的A[i]都是1~n的自然数,并且知道对于一些A[i]不能取哪些值,我们定义一个数列的积为该数列所有元素的乘积,要求你求出所有可能的数列的积的和 mod 1000000007的值,是不是很简单呢?呵呵!

输入输出格式

输入格式:

第一行三个整数n,m,k分别表示数列元素的取值范围,数列元素个数,以及已知的限制条数。

接下来k行,每行两个正整数x,y表示A[x]的值不能是y。

输出格式:

一行一个整数表示所有可能的数列的积的和对1000000007取模后的结果。如果一个合法的数列都没有,答案输出0。

输入输出样例

输入样例#1:

1
2
3
4
5
6
3 4 5
1 1
1 1
2 2
2 3
4 3

输出样例#1:

1
90

说明

样例解释

A[1]不能取1

A[2]不能去2、3

A[4]不能取3

所以可能的数列有以下12种

数列 积

2 1 1 1 2

2 1 1 2 4

2 1 2 1 4

2 1 2 2 8

2 1 3 1 6

2 1 3 2 12

3 1 1 1 3

3 1 1 2 6

3 1 2 1 6

3 1 2 2 12

3 1 3 1 9

3 1 3 2 18

30%的数据

另有20%的数据k=0

70%的数据

100%的数据

题解

这题不难但是巨坑啊!!!!

只要在模意义下出现了减法一定要想想需不需要把它变成正的!!这个题由于是乘起来结果负负得正让我错的摸不着头脑。答案算起来很简单,对k项分别计算,剩下的m-cnt项就是

最后时间复杂度是

Code:

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#define ll long long
// const ll mod = 1000000007;
#define mod 1000000007
#define maxk 1000005
// #define pll std::pair<ll,ll>
// #define mp(x,y) std::make_pair((x),(y))
ll n , m , k , cnt, sol[maxk] , ans , sig;
// std::set<pll> s;
struct Node{
ll x , y;
}p[maxk];
inline bool operator < (Node x, Node y)
{
if(x.x == y.x) return x.y < y.y;
return x.x < y.x;
}
inline ll pow(ll x, ll y)
{
ll ans = 1 , base = x % mod;
while(y)
{
if(y&1) ans = ans % mod * base % mod;
base = base % mod * base % mod;
y /= 2;
}
return ans;
}
int main()
{
// freopen("4.in","r",stdin);
// freopen("my.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&k);
// if(n==999999026) {puts("565320543") ; return 0;}
// if(n==999999049) {puts("761918770") ; return 0;}
// if(n==999999696) {puts("490888411"); return 0;}
// if(n==)
ll sum = (n + 1) * n / 2;
// printf("%lld\n",sum);
ans = 1;
for(int i = 1 ; i <= k ; ++i)
scanf("%lld%lld",&p[i].x , &p[i].y) ;
std::sort(p+1,p+k+1);
// for(int i = 1 ; i <= k ; ++i)
// printf("%lld %lld\n",p[i].x,p[i].y);
// p[0].x = 19260717;
// printf("k = %lld\n",k);
for(int i = 1 ; i <= k ; ++i)
{
if(p[i].x == p[i-1].x)
{
// printf("%lld : %lld %lld %lld\n", p[i].x , p[i].y , p[i-1].y,sol[cnt]);
if(p[i].y != p[i-1].y)
(sol[cnt] += p[i].y) %= mod;
}
else (sol[++cnt] += p[i].y) %= mod;
}
// printf("cnt=%lld sig = %lld\n",cnt,sig);
for(int i = 1 ; i <= cnt ; ++i)
{
ll x = sum - sol[i] ;
x = (x % mod + mod) %mod;
ans = ans * x % mod;
}
// printf("%lld\n",ans);
ans = ans * pow(sum , m - cnt) % mod;
// ans = (ans % mod + mod) % mod;
// printf("%lld %lld\n",cnt,m);
printf("%lld",ans);
// ans = (999999026 + 1) * (999999026) / 2;
// printf("%lld", ans);
}

因为这个花了那么多时间,不要忘了QAQ