Fork me on GitHub

前排打出题人的一套题

不管怎么样,先打死出题人再说qaq…

T1:人贩子$LLFZ$

题意很显然就是最优贸易啊….

一眼看出来是缩点+DP….但是为什么我之前是SPFA过的啊QAQ…
写SPFA比较稳….然后….就写了….

上代码吧….

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
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int INF = 2147483647;
#define G(i,a,b,c) for ( int i = b[a] ; i ; i = c[i].next )

int n , m , t , cnt;
struct Edge {
int to;
int data;
int next;
}e[M] , e_[M];
int head[N] , head_[N];
int maxs[N] , mins[N];
int dis[N] , value[N];
bool inque[N];
std :: queue < int > qu;

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}
inline void add ( int x , int y , int z ) {
e[++t].to = y;
e[t].data = z;
e[t].next = head[x];
head[x] = t;
return;
}
inline void add_ ( int x , int y , int z ) {
e_[++cnt].to = y;
e_[cnt].data = z;
e_[cnt].next = head_[x];
head_[x] = cnt;
return;
}
template < class T >
inline T min ( T x , T y ) {
return x < y ? x : y;
}
template < class T >
inline T max ( T x , T y ) {
return x > y ? x : y;
}
void Heap_Dijkstra () {
std :: memset ( dis , 0x3f3f3f3f , sizeof ( dis ) );
inque[1] = 1 , dis[1] = value[1];
qu.push ( 1 );
while ( !qu.empty () ) {
int j = qu.front ();
inque[j] = 0;
qu.pop ();
G ( i , j , head , e ) {
int k = e[i].to;
if ( dis[k] > min ( dis[j] , e[i].data ) ) {
dis[k] = min ( dis[j] , e[i].data );
if ( !inque[k] ) {
inque[k] = 1;
qu.push ( k );
}
}
}
}
for ( int i = 1 ; i <= n ; i++ )
mins[i] = dis[i];
std :: memset ( dis , -0x3f3f3f3f , sizeof ( dis ) );
inque[n] = 1 , dis[n] = value[n];
qu.push ( n );
while ( !qu.empty () ) {
int j = qu.front ();
qu.pop ();
inque[j] = 0;
G ( i , j , head_ , e_ ) {
int k = e_[i].to;
if ( dis[k] < max ( dis[j] , e_[i].data ) ) {
dis[k] = max ( dis[j] , e_[i].data );
if ( !inque[k] ) {
inque[k] = 1;
qu.push ( k );
}
}
}
}
for ( int i = 1 ; i <= n ; i++ )
maxs[i] = dis[i];
return;
}

int main ( void ) {
freopen ( "child.in" , "r" , stdin );
freopen ( "child.out" , "w" , stdout );
n = read ();
m = read ();
for ( int i = 1 ; i <= n ; i++ )
value[i] = read ();
for ( int i = 1 ; i <= m ; i++ ) {
int x = read () , y = read () , z = read ();
if ( z == 1 ) {
add ( x , y , value[y] );
add_ ( y , x , value[x] );
}
else if ( z == 2 ) {
add ( x , y , value[y] );
add ( y , x , value[x] );
add_ ( y , x , value[x] );
add_ ( x , y , value[y] );
}
}
Heap_Dijkstra ();
int ans = -INF;
for ( int i = 1 ; i <= n ; i++ )
ans = max ( ans , maxs[i] - mins[i] );
printf ( "%d\n" , ans );
return 0;
}

T2 : food

再来拿出题人祭天祭一波…

话说我直接读题读错了然后写了个错误的DP然后还A了是什么鬼啊….

话说我考虑了前缀和,那么我还过了,说明直接加起来然后除就可以?

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

const int N = 15;

int n , ans = -1;
int A , B , C;
int p1 , p2 , p3;
int MaxTime[N];

int f[N][105][105][105];

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}
inline int max ( int x , int y ) {
return x > y ? x : y;
}

int main ( void ) {
freopen ( "food.in" , "r" , stdin );
freopen ( "food.out" , "w" , stdout );
A = read () , B = read () , C = read ();
p1 = read () , p2 = read () , p3 = read ();
n = read ();
for ( int i = 1 ; i <= n ; i++ ) {
MaxTime[i] = read ();
MaxTime[i] = MaxTime[i - 1] + MaxTime[i];
}
for ( int i = 1 ; i <= n ; i++ )
for ( int j = A ; j * p1 <= MaxTime[i] && j<=100 ; j++ )
for ( int k = B; j * p1 + k * p2 <= MaxTime[i] && k <= 100 ; k++ )
for ( int l = C ; j * p1 + k * p2 + l * p3 <= MaxTime[i] && l <=100 ; l++ ) {
f[i][j][k][l] = max ( f[i][j][k][l] , max ( f[i - 1][j - A][k - B][l - C] + 1 , f[i][j - A][k - B][l - C] + 1 ) );
ans = max ( ans , f[i][j][k][l] );
}
printf ( "%d\n" , ans );
return 0;
}

T3: Happy

再吐槽一波为什么Noip模拟赛会考离散对数(然而我并不会….)

其实应该是一道签到题吧。。。

暴力水过….

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

int P , A , B;
bool app[50005];

int main ( void ) {
freopen ( "happy.in" , "r" , stdin );
freopen ( "happy.out" , "w" , stdout );
int T = read ();
while ( T-- ) {
int now = 1;
memset ( app , false , sizeof ( app ) );
P = read () , A = read () , B = read ();
for ( int i = 1 ; ; i++ ) {
now = ( now * A ) % P;
if ( now == B ) {
printf ( "%d\n" , i );
break;
}
if ( app[now] ) {
puts ( "Couldn't Produce!" );
break;
}
app[now] = 1;
}
}
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:前排打出题人的一套题

文章作者:KRrrrrrrrr

发布时间:2018年10月17日 - 20:10

最后更新:2019年10月21日 - 11:10

原始链接:http://krrrr.xyz/2018/10/17/前排打出题人的一套题/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。