Loi_Vampire's Blog

自己选择的路，就算跪着也要走完

11/15
10:33
TEST

11.15 test

无回复 110 views

试题

T1:

询问把n个数变成互不相同的数的最小价值。

n <= 10w, ai<=10w

这个做法有很多……可以 先排个序 或者 用set来做 都是可以的

说一下我在考场上的做法：是用到了并查集的思想。开一个数组fa， fa[i]表示大于等于i的第一个没有出现的数字。然后每次修改 find一下就好了

预处理的话 fa[i] = i。 如果一个数出现过的话，fa[i]改为i+1

View Code
C++
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
#include <iostream>
#include <cstdio>
using namespace std;
 
int num[100010], fa[200010];
 
int read()
{
    int num = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = - 1; c = getchar();}
    while('0' <= c && c <= '9'){num = num * 10 + (c - '0'); c = getchar();}
    return num * f;
}
 
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
 
int main()
{
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    int n = read();
    for(int i = 1; i <= 100000; i++)
        fa[i] = i;
    int in;
    for(int i = 1; i <= n; i++)
    {
        in = read();
        num[in]++;
        fa[in] = in + 1;
    }
    int ans = 0;
    for(int i = 1; i <= 100000; i++)
    {
        while(num[i] > 1)
        {
            int x = find(i);
            ans += (x - i);
            fa[x] = x + 1;
            fa[i] = fa[x];
            num[i]--;
        }
    }
    printf("%d", ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

 

T2：

n个点 m条有向边，求所有点到一号点的最短路之和。如果有任意一个点无法到达，输出-1.

奇怪的边权生成方式：w = (上一条边的边权 a + b) % c . w初始值为10，第一条边的权值为(10 a + b) % c

对于 30%的数据 n<= 200 , m <= 500 , a,b <= 100, c<=10000 对于 60%的数据 n<=10000 m <= 15000 a,b<=10000 c <= 10^7 对于 100%的数据 n <= 100000 m <= 200000 a,b <= 10^16, c <= 10^9

30分做法：floyd 同时w = (上一条边的边权 * a + b) % c不会爆掉int

60分做法：spfa 同时w = (上一条边的边权 * a + b) % c不会爆掉long long

100分做法：spfa 而这时需要及时取模 w = (((w % c) * (a % c)) % c + (b % c)) % c 要知道%运算时满足分配律的

30分floyd

View Code
C++
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 <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF = 200000000000000ll;
 
LL dis[300][300];
 
int main()
{
    freopen("family.in", "r", stdin);
    freopen("family.out", "w", stdout);
    int n, m;
    LL a, b, c, w = 10;
    scanf("%d%d%I64d%I64d%I64d", &n, &m, &a, &b, & c);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            dis[i][j] = INF;
    for(int i = 1; i <= n; i++)
        dis[i][i] = 0;
    int u, v;
    for(int i = 1; i <= m; i++)    
    {
        scanf("%d%d", &u, &v);
        w = (((w % c) * (a % c)) % c + (b % c)) % c;
        dis[v][u] = min(dis[v][u], w);
    }
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    LL ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(dis[1][i] == INF)
        {
            ans = -1;
            break;
        }
        ans += dis[1][i];
    }
    printf("%I64d", ans);
    return 0;
}

 

100分spfa

View Code
C++
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
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long LL;
const LL INF = 200000000000000;
const int SZ = 200010;
 
struct Edge
{
    int f, t;
    LL d;
}es[SZ];
int first[SZ], nxt[SZ], tot = 1;
LL dis[SZ];
bool vis[SZ];
queue<int> Q;
 
void build(int f, int t, LL d)
{
    es[++tot] = (Edge){f, t, d};
    nxt[tot] = first[f];
    first[f] = tot;
}
 
void spfa(int s)
{
    dis[s] = 0;
    Q.push(s);
    vis[s] = 1;
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop(); vis[u] = 0;
        for(int i = first[u]; i; i = nxt[i])
        {
            int v = es[i].t;
            if(dis[v] > dis[u] + es[i].d)
            {
                dis[v] = dis[u] + es[i].d;
                if(!vis[v])
                {
                    Q.push(v);
                    vis[v] = 1;
                }
            }    
        }
    }
}
 
int main()
{
    freopen("family.in", "r", stdin);
    freopen("family.out", "w", stdout);
    int n, m;
    LL a, b, c, w = 10;
    scanf("%d%d%I64d%I64d%I64d", &n, &m, &a, &b, &c);
    int u, v;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        w = (((w % c) * (a % c)) % c + (b % c)) % c;
        build(v, u, w);
    }
    for(int i = 1; i <= n; i++)
        dis[i] = INF;
    spfa(1);
    LL ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(dis[i] == INF)
        {
            ans = -1;
            break;
        }
        ans += dis[i];
    }
    printf("%I64d", ans);
    return 0;
}

 

T3：

划分型DP 自行百度书本整理即可

View Code
C++
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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int size = 210;
int stone[size];
int n,p;
int f[size][size];
int main()
{
    freopen("true.in","r",stdin);
    freopen("true.out","w",stdout);
    scanf("%d%d",&n,&p);
    for(int i = 1 ; i <= n ; i ++)
        scanf("%d",&stone[i]);
    memset(f,63,sizeof(f));
    f[0][0] = 0;
    for(int i = 1 ; i <= n ; i ++)
        f[i][1] = 0;
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 2 ; j <= n - p ; j ++)
            for(int k = 1 ; k < i ; k ++)
                f[i][j] = min(f[i][j],f[k][j-1]+abs(stone[i]-stone[k]));
    int ans = 2147483641;
    for(int i = n - p ; i <= n ; i ++)
        ans = min(f[i][n-p],ans);
    printf("%d\n",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}