首页 > 代码库 > 2016年NK冬季训练赛 民间题解
2016年NK冬季训练赛 民间题解
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题挖坑
2016年NK冬季训练赛 民间题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。