A题 水题，考察对行的读入和处理，注意使用long long
#include <iostream> #include <cstring> #include <cstdio> using namespace std; int main() { char ch; long long a, sum=0, Min; char S[200]; while(cin.getline(S, 100)) { Min = 1e9; a = 0; for(int i = 0; i < strlen(S); i++) { if(S[i] == ' ') { Min = min(Min, a); a = 0; } else a = a*10 + S[i] - '0'; } if(a != 0) Min = min(Min, a); sum += Min; } cout<<sum<<endl; }
B题 贪心算法，先排序，然后依次兑换即可，注意使用long long
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; struct T { int x, y; bool operator <(const T &B) const { return y < B.y; } }a[100500]; int main() { long long n, k; while(cin>>n>>k) { for(int i = 0; i < n; i++) cin>>a[i].x>>a[i].y; sort(a, a+n); int ans = -1; for(int i = 0; i < n; i++) { if(k < a[i].y) break; k += a[i].x; ans = i; } cout<<ans+1<<endl; } }
C题 可以用dp做，如果把dp的转移方程变成一个矩阵，那么这个矩阵恰好就是这个图的邻接矩阵，然后只要求它的k次幂即可，注意存在自环和重边的情况
这里可以利用矩阵乘法的一个优化，可以把常数优化很多。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <iomanip> using namespace std; const int mod = 999983; const int maxn = 111; int n,m; struct Matrix { long long v[maxn][maxn]; int n; Matrix() { memset(v, 0, sizeof(v));} Matrix operator *(const Matrix &B) { Matrix C; C.n = n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) { if(v[i][j] == 0) continue; for(int k = 0; k < n; k++) C.v[i][k] = (C.v[i][k] + v[i][j]*B.v[j][k])%mod; } return C; } }A, B; Matrix power(Matrix A, int k) { Matrix ans; ans.n = n; for(int i = 0; i < n; i++) ans.v[i][i] = 1; while(k) { if(k&1) ans = ans*A; A = A*A; k >>= 1; } return ans; } int a, b, k, t; int main() { while(cin>>n>>m>>k>>t) { A.n = n; for(int i = 1; i <= m; i++) { scanf("%d %d", &a, &b); A.v[a-1][b-1]++; if(a != b) A.v[b-1][a-1]++; } B = power(A, k); while(t--) { scanf("%d %d", &a, &b); printf("%d\n", B.v[a-1][b-1]); } } return 0; }
D题 建图后直接floyed即可，在树上的边权是距离除以速度v，然后再枚举出在同一x坐标的两个点，边权为自由落体的时间。（这里代码有个bug，更新边权要用min的方法更新）
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; double eps = 1e-10; double d[111][111]; struct point { double x, y; }p[111]; int n, v, f; double dis(point &A, point &B) { return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y)); } int main() { while(cin>>n>>v) { for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) d[i][j] = 1e8; for(int i = 1; i <= n; i++) { cin>>p[i].x>>p[i].y>>f; if(f == 0) continue; d[i][f] = dis(p[i], p[f])/v; d[f][i] = d[i][f]; } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { if(i == j) continue; if(p[i].x == p[j].x && (p[i].y - p[j].y > eps)) d[i][j] = sqrt((p[i].y - p[j].y)*2/10.0); } for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(d[i][j] - d[i][k] - d[k][j] > eps) d[i][j] = d[i][k] + d[k][j]; printf("%.2f\n", d[1][n]); } }
E题 贪心算法，先排序，最左侧的必须首先覆盖，然后依次类推，不断覆盖，不难证明这是最优的
#include <iostream> #include <algorithm> using namespace std; int a[10000]; int main() { int L, N, l; cin>>L>>N>>l; for(int i = 1; i <= N; i++) cin>>a[i]; sort(a+1, a+1+N); int li = -1000, ans = 0; for(int i = 1; i <= N; i++) { if(a[i] - li > l) { ans++; li = a[i]; } } cout<<ans<<endl; }
F题 动态规划，利用滚动数组，f[j]表示交易了j次但并未买入一个股票的状态，g[j]表示交易了j次但买入了股票的状态，然后对每一个股票都需要做一个买或者不买的决策，最后输出max(g[j])即可
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 10050; long long a[N], f[2][N*2], g[2][N*2]; int main() { long long n, k; while(cin>>n>>k) { k *= 2; for(int i = 1; i <= n; i++) cin>>a[i]; memset(f, 128, sizeof(f)); memset(g, 0, sizeof(g)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= k; j++) { f[i&1][j] = max(g[(i-1)&1][j-1] - a[i], f[i&1][j]); g[i&1][j] = max(f[(i-1)&1][j-1] + a[i], g[i&1][j]); g[i&1][j] = max(g[(i-1)&1][j], g[i&1][j]); f[i&1][j] = max(f[(i-1)&1][j], f[i&1][j]); } } long long ans = 0; for(int j = 0; j <= k; j++) ans = max(ans, g[n&1][j]); cout<<ans<<endl; } }
G题 树型背包动态规划，dp[x][m]表示在x结点用了m个火把向下探索所得到的最大价值，然后转移的时候利用dfs转移即可
#include <iostream> #include <cstring> #include <cstdio> #include <vector> using namespace std; const int maxn = 111, maxm = 111111; vector <int> G[maxn]; int dp[maxn][maxm]; struct thing { int l, v; }a[maxn]; int n, M; void dfs(int x, long long m) { for(int i = 0; i < G[x].size(); i++) { int to = G[x][i]; for(int j = 0; j <= (m*10 - a[to].l)/10; j++) dp[to][j] = dp[x][j] + a[to].v; dfs(to, (m*10 - a[to].l)/10); for(int j = 0; j <= (m*10 - a[to].l)/10; j++) dp[x][j+(a[to].l+9)/10] = max(dp[x][j+(a[to].l+9)/10], dp[to][j]); } } int main() { //freopen("a.txt", "r", stdin); while(cin>>M>>n) { for(int i = 1; i <= n; i++) G[i].clear(); memset(dp, 0, sizeof(dp)); int x, y, L, v; for(int i = 1; i <= n; i++) { cin>>x; while(x--) { cin>>y>>L>>v; G[i].push_back(y); a[y].l = L; a[y].v = v; } } dfs(1, M); cout<<dp[1][M]<<endl; } }
H题 采药
这个题的背包容量非常大，普通的01背包转移在时间和空间上都无法通过
但由于是随机数据，我们可以利用分块的思想进行优化
初始时先把1~C看成一个大整块
然后第一次更新，用这个大整块去更新出来两个分割的小块
（每一块的值代表从l到r这个容量内的dp值，即dp[l~r]。如果l~r内存在dp值不同的数据，则将这一块分成更多的小块来满足dp值相同的条件）
下一次再用这2个分割的小块去更新出更多的小块
如果仅仅这样做，显然空间和时间上通过也很困难
于是我们每次更新后进行一个维护操作
把值相等且相邻的块合并成一个大块，由于随机数据，每一次维护后，块的数量实际上都非常少(sqrt(n)左右)
于是每次更新的复杂度就是100左右
整体复杂度就是n*sqrt(n)(玄学)
实现过程中，有比较多的细节，要多加注意。
#include <iostream> #include <cstring> #include <cstdio> #include <vector> #include <algorithm> #include <map> using namespace std; typedef long long LL; struct Data { LL l, r, v; Data() {} Data(LL _l, LL _r, LL _v):l(_l), r(_r), v(_v) { } }; struct thing { LL cost, v; bool operator <(const thing &B) const { return cost > B.cost; } }a[1111]; vector <Data> B[3]; map<int, LL> M; int n; LL t; int main() { while(cin>>n>>t) { for(int i = 1; i <= n; i++) cin>>a[i].cost>>a[i].v; sort(a+1, a+1+n); LL Sum = 0; for(int i = n; i >= n-10; i--) Sum += a[i].v; B[0].push_back(Data(0, t, 0)); for(int i = 1; i <= n; i++) { B[1].clear(); B[1].push_back(Data(0, min(a[i].cost-1, t), 0)); for(int j = 0; j < B[0].size(); j++) { Data& e = B[0][j]; if(e.l + a[i].cost > t) break; B[1].push_back(Data(e.l + a[i].cost, min(t, e.r + a[i].cost), e.v + a[i].v)); } for(int j = 0, k = 0; j < B[0].size(); j++) { if(B[0][j].r >= B[1][k].l) B[2].push_back(Data(max(B[0][j].l, B[1][k].l), min(B[0][j].r, B[1][k].r), max(B[1][k].v, B[0][j].v))); if(B[0][j].r > B[1][k].r) k++, j--; } B[0].clear(); M.clear(); for(int j = 0; j < B[2].size(); j++) M[B[2][j].v] = B[2][j].r; for(int j = 0; j < B[2].size(); j++) { if(M[B[2][j].v]) { B[0].push_back(Data(B[2][j].l, M[B[2][j].v], B[2][j].v)); M[B[2][j].v] = 0; } } B[2].clear(); } cout<<B[0][B[0].size()-1].v<<endl; B[0].clear(); } }
I题 逛公园
十分有趣的一道题目，由于它是一个有向的完全图且不存在环
首先先证明这样一个结论
* 如果这个图有n个点且不存在环，那么必定有一个点，它的入度是0，出度是n-1
证明：反证法，如果不存在这样一个点，那么不妨设一个入度最小的点x，它的入度是m，那么出度就是n-m-1
考虑所有指向它的m个点中的一个点y，那么可以得到，y也必定指向所有x指向的(n-m-1)个点（因为如果y不全部指向它们，那么肯定会存在环）
然后y的入度就是n - (n-m+1) = m-1，显然y的入度比x的入度小
所以矛盾，所以一定存在一个点的入度是0
那么接下来把这个点直接删掉（并不会对环的存在有任何影响） ，图就变成了n-1个点，那么我们同样可以得到必定有一个点入度是0，出度是n-2。
以此类推，我们得到这个图不存在环，那么这n个点的入度分别是0,1,2....n-1
也就是我们需要决策这n个点的入度分别是多少，以使改变的边数最少
然后可以用状态压缩DP来解决
dp[i][s]表示选了i个点，状态为s所需要改变的最小边数
那么再选下一个点来更新dp[i+1][s+(1<<i)]
最后答案就是dp[n][(1<<n) - 1]
中间还可以利用位运算优化，把n*n*（2^n）优化为n*（2^n）
#include <iostream> #include <cstring> #include <cstdio> #include <vector> using namespace std; int M[20][20]; vector<int> S[20]; int dp[(1<<20)]; int T[(1<<20)], table[20]; int main() { int n; for(int i = 0; i < (1<<20); i++) { int temp = 0; for(int j = 0; j < 20; j++) if((1<<j)&i) temp++; S[temp].push_back(i); T[i] = temp; } while(cin>>n) { memset(table, 0, sizeof(table)); memset(dp, 126, sizeof(dp)); memset(M, 0, sizeof(M)); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin>>M[i][j]; for(int i = 1; i <= n; i++) M[i][i] = 1; for(int i = 1; i <= n; i++) for(int j = n; j >= 1; j--) table[i] = (table[i]<<1) + M[i][j]^1; dp[0] = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { for(int k = 0; k < S[i-1].size(); k++) { int s = S[i-1][k]; if(1<<(j-1)&s) continue; int temp = 0; dp[s + (1<<(j-1))] = min(dp[s + (1<<(j-1))], dp[s] + T[table[j]&(~s)]); } } } cout<<dp[(1<<n)-1]<<endl; } }
J题 过河卒，简单动态规划，把马可以控制的点都删除，然后按照f[i][j] = f[i-1][j] + f[i][j-1]转移就可以
#include <iostream> #include <cstdio> using namespace std; long long dp[2000][2000]; bool flag[2000][2000]; int dx[4] = {-2, -1, 1, 2}; int dy[4] = {1, 2, 2, 1}; int x[2000], y[2000]; int main() { int xb, yb, N; cin>>xb>>yb>>N; for(int i = 0; i < N; i++) cin>>x[i]>>y[i]; for(int i = 0; i < 4; i++) { for(int j = 0; j < N; j++) { if(x[j] + dx[i] < 0) continue; flag[y[j] + dy[i]][x[j] + dx[i]] = 1; if(y[j] - dy[i] < 0) continue; flag[y[j] - dy[i]][x[j] + dx[i]] = 1; } } for(int j = 0; j < N; j++) flag[y[j]][x[j]] = 1; flag[0][0] = 1; dp[0][0] = 1; for(int j = 0; j <= xb; j++) if(!flag[0][j]) dp[0][j] = dp[0][j-1]%((int)1e9+7); for(int i = 1; i <= yb; i++) { if(!flag[i][0]) dp[i][0] = dp[i-1][0]; for(int j = 1; j <= xb; j++) if(!flag[i][j]) dp[i][j] = (dp[i-1][j] + dp[i][j-1])%((int)1e9+7); } cout<<dp[yb][xb]<<endl; }