11/15
10:33
T1:
询问把n个数变成互不相同的数的最小价值。
n <= 10w, ai<=10w
这个做法有很多……可以 先排个序 或者 用set来做 都是可以的
说一下我在考场上的做法:是用到了并查集的思想。开一个数组fa, fa[i]表示大于等于i的第一个没有出现的数字。然后每次修改 find一下就好了
预处理的话 fa[i] = i。 如果一个数出现过的话,fa[i]改为i+1
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
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
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 自行百度书本整理即可
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; } |