Fork me on GitHub

普转提D6

版权原因,题面不公开

石头

思路

我们设$f_i$表示前$i$个序列中能排出多少序列.那么显然有$f_i=\sum f_j([\sum_{k=1}^{j+1}a_k]是素数)$

代码

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
#include <bits/stdc++.h>
#define int long long
#define ha 987654321
const int N=1e6+10;
using namespace std ;
int n , f[N] , s[N] , vis[N] , num , prime[N] ;
void pre() {
for(int i = 2 ; i < N ; i ++) {
if(!vis[i]) prime[++num] = i ;
for(int j = 1 ; j <N && i*prime[j] <N ; j ++) {
vis[i*prime[j]] = 1 ;
if(i % prime[j] == 0) break ;
}
}
vis[1] = 1 ;
}
int a[2000] ;
signed main () {
pre() ;
scanf("%lld",&n) ;
for(int i = 1 ; i <= n ; i ++) {
int x ;
scanf("%lld",&x) ;
a[i] = x ;
s[i] = s[i-1] + a[i] ;
}
f[0] = 1 ;
for(int i = 1 ; i <= n ; i ++ ) {
for(int j = 0 ; j < i ; j ++) {
if(!vis[s[i]-s[j]]) f[i] = (f[i] + f[j])%ha ;
}
}cout << f[n]%ha << endl ;
return 0 ;
}

载重

思路

先预处理出一个最大生成树,然后$check$两点之间的最大瓶颈路与给定的值的大小关系即可.

代码

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

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

const int N = 1e5 + 10;
const int M = 3e5 + 10;

int n , m , q , t;
int head[N];
struct Edge {
int from;
int to;
int date;
int next;
}e[M << 1] , G[M << 1];
int father[N];

inline bool cmp ( Edge x , Edge y ) {
return x.date > y.date;
}
int find ( int cur ) {
if ( father[cur] != cur )
father[cur] = find ( father[cur] );
return father[cur];
}
inline void Union ( int x , int y ) {
x = find ( x ) , y = find ( y );
father[x] = y;
return;
}
inline bool Judge ( int x , int y ) {
x = find ( x ) , y = find ( y );
if ( x == y )
return true;
else return false;
}
inline void add ( int x , int y , int z ) {
G[++t].to = y;
G[t].from = x;
G[t].date = z;
G[t].next = head[x];
head[x] = t;
return;
}
int p[N][22] , mins[N][22];
int deep[N];
void Creat ( int root , int fa ) {
p[root][0] = fa;
deep[root] = deep[fa] + 1;
for ( int i = head[root] ; i ; i = G[i].next ) {
int j = G[i].to;
if ( j == fa )
continue;
mins[j][0] = G[i].date;
Creat ( j , root );
}
return;
}
inline int LCA ( int x , int y ) {
int minn = 2147483647;
if ( deep[x] > deep[y] )
std :: swap ( x , y );
for ( int i = 21 ; i >= 0 ; i-- )
if ( deep[x] <= deep[y] - ( 1 << i ) ) {
minn = std :: min ( minn , mins[y][i] );
y = p[y][i];
}
if ( x == y )
return minn;
for ( int i = 21 ; i >= 0 ; i-- ) {
if ( p[x][i] == p[y][i] )
continue;
minn = std :: min ( minn , std :: min ( mins[x][i] , mins[y][i] ) );
x = p[x][i];
y = p[y][i];
}
return std :: min ( minn , std :: min ( mins[x][0] , mins[y][0] ) );
}

int main ( void ) {
n = read () , m = read () , q = read ();
for ( int i = 1 ; i <= m ; i++ ) {
int x = read () , y = read () , z = read ();
e[i].from = x;
e[i].to = y;
e[i].date = z;
}
for ( register int i = 1 ; i <= n ; i++ )
father[i] = i;
memset ( mins , 0x3f3f3f3f , sizeof ( mins ) );
std :: sort ( e + 1 , e + 1 + m , cmp );
int NowEdge = 0;
for ( int i = 1 ; i <= m && NowEdge != n - 1 ; i++ ) {
int l = e[i].from , r = e[i].to;
if ( !Judge ( l , r ) ) {
Union ( l , r );
NowEdge++;
add ( l , r , e[i].date );
add ( r , l , e[i].date );
}
if ( NowEdge == n - 1 )
break;
}
for ( int i = 1 ; i <= n ; i++ )
if ( deep[i] == 0 ) {
deep[i] = 1;
p[i][0] = 0;
Creat ( i , 0 );
}
for ( int j = 1 ; j <= 21 ; j++ )
for ( int i = 1 ; i <= n ; i++ ) {
p[i][j] = p[p[i][j - 1]][j - 1];
mins[i][j] = std :: min ( mins[i][j - 1] , mins[p[i][j - 1]][j - 1] );
}
for ( ; q-- ; ) {
int l = read () , r = read () , vv = read ();
if ( !Judge ( l , r ) )
puts ( "No" );
else {
int res = LCA ( l , r );
if ( res >= vv )
puts ( "Yes" );
else
puts ( "No" );
}
}
return 0;
}

分数

思路

我们模拟一下现实中的过程,发现我们需要找出分母所有的质因子并且把他们乘起来就是答案,但是需要写高精度.

代码

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
#include <bits/stdc++.h>
using namespace std;

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

const int MO = 15;
struct Big{
int len, data[10005];
void clear() {
memset ( this , 0 , sizeof ( *this ) );
}
int & operator [] ( int k ) {
return data[k];
}
Big & operator = ( int k ) {
clear();
len = 0;
while ( k ) {
++len;
data[len] = k & MO;
k >>= 4;
}
if ( len == 0 )
++len;
return *this;
}
Big operator * ( Big & A ) {
Big temp;
temp.clear();
temp.len = len + A.len - 1;
for ( int i = 1 ; i <= len ; i++ )
for ( int j = 1 ; j <= A.len ; j++ ) {
temp[i + j - 1] += A[j] * data[i];
temp[i + j] += ( temp[i + j - 1] >> 4 );
temp[i + j - 1] &= MO;
}
while(temp[temp.len + 1])
++temp.len;
return temp;
}
void print(){
for (int i = len; i >= 1; i--)
printf("%X", data[i]);
putchar('\n');
}
} temp , ans;

const int N = 1000005;

int pnum , p[N];
bool f[N];
map < int , bool > M;

void work ( int num ) {
for ( int i = 1 ; i <= pnum ; i++ ) {
if ( num % p[i] == 0 )
if ( M[p[i]] == 0 ) {
M[p[i]] = true;
temp = p[i];
ans = ans * temp;
}
while ( num % p[i] == 0 )
num /= p[i];
}
if ( num != 1 )
if ( M[num] == 0 ) {
M[num] = true;
temp = num;
ans = ans * temp;
}
return;
}

int main ( void ) {
ans = 1;
int T;
T = read ();
memset ( f , true , sizeof ( f ) );
f[0] = f[1] = false;
p[pnum = 1] = 2;
for ( int now = 2 ; now < N ; ) {
for ( int j = 2 * now ; j <= N ; j += now )
f[j] = false;
now++;
while ( now < N && !f[now] )
now++;
if ( f[now] )
p[++pnum] = now;
}
while ( T-- ) {
int x = read () , y = read ();
int d = __gcd ( x , y );
x /= d;
y /= d;
work ( y );
}
ans.print();
return 0;
}

鏼尔德

思路

解:设$d_{i,j}$表示走到结点$i$,被收了$j$次路费,最少花了多少钱。
状态转移方程:考虑上一个结点,不妨设为$k$。$d_{i,j} = min[max(d_{k,j-1} + i到k的路费, d_{k,j})]$
边界:$d_{1,j} = 0$最终解:$d_{n,k}$.

代码

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
#include <cstdio>
#include <queue>
using namespace std;
#define N 3010
#define INF 1000000000000000000
#define LL long long
struct edge {
LL to, cost, next;
};
queue<LL> q;
edge e[N << 1];
bool exist[N];
LL d[N][N], head[N], n, m, K, nedge;
inline LL max(LL x, LL y) {
return x > y ? x : y;
}
inline void link(LL u, LL v, LL w) {
e[++nedge].to = v;
e[nedge].cost = w;
e[nedge].next = head[u];
head[u] = nedge;
}
int main() {
scanf("%lld %lld %lld", &n, &m, &K);
for(LL i = 1; i <= m; i++) {
LL u, v, w;
scanf("%lld %lld %lld", &u, &v, &w);
link(u, v, w); link(v, u, w);
}
for(LL i = 2; i <= n; i++)
fill(&d[i][0], &d[i][N], INF);
q.push(1);
exist[1] = true;
while(!q.empty()) {
LL u = q.front();
q.pop();
exist[u] = false;
for(LL i = head[u]; i; i = e[i].next) {
LL v = e[i].to, w = e[i].cost;
bool flag = false;
for(LL j = 0; j <= K; j++) {
LL t = d[u][j];
if(j) t = max(t, d[u][j - 1] + w);
if(d[v][j] > t) {d[v][j] = t; flag = true;}
}
if(flag && !exist[v]) {
exist[v] = true;
q.push(v);
}
}
}
printf("%lld", d[n][K]);
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:普转提D6

文章作者:KRrrrrrrrr

发布时间:2019年10月28日 - 09:10

最后更新:2019年10月28日 - 16:10

原始链接:http://krrrr.xyz/2019/10/28/普转提D6/

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