牛客集训派对day3
- 2020 年 2 月 18 日
- 笔记
A.Knight
题目描述 有一张无限大的棋盘，你要将马从(0,0)移到(n,m)。 每一步中，如果马在(x,y)，你可以将它移动到(x+1,y+2),(x+1,y-2),(x-1,y+2),(x-1,y-2),(x+2,y+1),(x+2,y-1),(x-2,y+1)或(x-2,y-1)。 你需要最小化移动步数。
输入描述: 第一行一个整数t表示数据组数 (1≤ t≤ 1000)。 每组数据一行两个整数n,m (|n|,|m|≤ 109)。
输出描述: 每组数据输出一行一个整数表示最小步数。
示例1 输入 2 0 4 4 2 输出 2 2
不妨假设 x>=y>=0。 当 x<=2y 时，定义每一步的冗余值 wi=3-dx-dy，那么∑wi=∑(2-dx)=3 步数-x-y，显然我们只需要最小化冗余值。我们先只用(+2,+1)(若 x 为奇数则 加一步(+1,+2))走到(x,y’)，然后通过将(+2,+1)替换为 2 个(+1,+2)使得 0<=y-y’<3。 若 y-y’=0，则冗余值为 0，显然最小。 若 y-y’=1，则将(+1,+2)替换为(+2,+1)和(-1,+2)或将 2 个(+2,+1)替换为 (+1,+2),(+1,+2),(+2,-1)，冗余值为 2，显然最小。（此处需要特判(2,2)） 若 y-y’=2，则加上(+2,+1)和(-2,+1)，冗余值为 4，由于不存在冗余值为 1 的步，所以最小。 当 x>2y 时，定义每一步的冗余值 wi=2-dx，那么∑wi=∑(2-dx)=2步数-x， 显然我们只需要最小化冗余值。我们先只使用(+2,+1)走到(2y,y)，然后用 (+2,+1)和(+2,-1)走到(x’,y)使得 0<=x-x’<4。 若 x-x’=0 则冗余值为 0，显然最小。 若 x-x’=1 则将之前的(+2,+1)改为(+1,+2)和(+2,-1)，冗余值为 1，显然最 小。（此处需要特判(1,0)） 若 x-x’=2 则加上(+1,+2)和(+1,-2)，冗余值为 2，由 x/2+y 的奇偶性可知 最小。 若 x-x’=3 则加上(+2,+1),(+2,+1),(-1,-2)，冗余值为 3，由 x/2+y 的奇偶 性可知最小。 时间复杂度 O(t)
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll fun(ll x, ll y) { if (x == 1 && y == 0) { return 3; } if (x == 2 && y == 2) { return 4; } ll delta = x - y; if (y>delta) { return delta - 2 * floor(((double)(delta-y)) / 3.0); } else { return delta - 2 * floor(((double)(delta-y)) / 4.0); } } int main() { //freopen("in.txt", "r", stdin); int t; cin >> t; while (t--) { ll x, y; cin >> x >> y; x = abs(x); y = abs(y); if (x < y) { swap(x, y); } cout << fun(x, y) << endl; } return 0; }
D. Shopping
题目描述 你要买n件物品，其中有一些是凳子。 商场正在举行促销活动，如果购物车中有至少一个凳子，那么你可以半价购买这个购物车中最贵的一个物品。 你有m辆购物车，请最小化你的花费。
输入描述: 第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。 每组数据第一行两个整数n,m (1 ≤ n,m ≤ 1000)，接下来n行每行两个整数ai,bi，分别表示第i件物品的价格以及它是否是凳子 (1 ≤ ai ≤ 105, 0 ≤ bi ≤ 1)。
输出描述: 每组数据输出一行一个实数表示最小花费，保留一位小数。
示例1
输入 2 5 1 1 0 2 1 3 1 4 0 5 0 5 10 1 0 2 1 3 1 4 0 5 0
输出 12.5 10.5
显然可以将最贵的 min(m,凳子个数)个物品打折。 时间复杂度 O(tn)
#include <bits/stdc++.h> using namespace std; int t; int n,m; int main(){ //freopen("in.txt", "r", stdin); scanf("%d", &t); int a,b; while(t--){ scanf("%d%d", &n, &m); vector<int> v; int cnt = 0; for(int i = 0; i < n; ++i){ scanf("%d%d", &a, &b); if(b == 1) ++cnt; v.push_back(a); } sort(v.begin(), v.end()); double ans = 0.0; int sz = v.size(); m = min(m, cnt); for(int i = sz-1,j=1; i >= 0; --i,++j){ if(j <= m) ans += v[i]/2.0; else ans += v[i]; } printf("%.1lfn", ans); } return 0; }
H.Travel
题目描述 魔方国有n座城市，编号为。城市之间通过n-1条无向道路连接，形成一个树形结构。 澜澜打算在魔方国进行m次旅游，每次游览至少一座城市。为了方便，每次旅游游览的城市必须是连通的。此外，澜澜希望游览所有城市恰好一次。 澜澜想知道有多少种旅游方案满足条件，两个方案不同当且仅当存在某一次旅游游览了不同的城市。 澜澜不会数数，所以只好让你来帮他数方案。
输入描述: 第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。 每组数据第一行两个整数n,m ，接下来n-1行每行两个整数ai,bi表示一条道路 (1≤ ai,bi≤ n)。
输出描述: 每组数据输出一行一个整数表示方案数对109+7取模的结果。
示例1
输入 2 3 1 1 2 1 3 3 2 1 2 1 3
输出 1 4
把树分成 m 个连通块的方案数是 C(n-1,m-1)，乘上 m!就行了。 时间复杂度 O(∑n)
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL MOD = 1e9 + 7; #define MAX_N 100100 LL f[MAX_N]; void init(){ f[0] = f[1] = 1LL; for(int i = 2; i < MAX_N; ++i) f[i] = i * f[i - 1] % MOD; } LL powN(LL a, LL n){ LL base = a, res = 1LL; while(n){ if(n & 1) res = res * base % MOD; base = base * base % MOD; n >>= 1; } return res; } LL inv(LL a, LL MOD){ return powN(a, MOD - 2LL); } LL C(LL n, LL m){ if(m == 0) return 1; if(n < 0 || n < m) return 0; return (f[n] % MOD) * (inv(f[m], MOD) * inv(f[n - m], MOD) % MOD) % MOD; } int main(){ //freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); int t,a,b; LL n,m; cin >> t; init(); while(t--){ cin >> n >> m; for(int i = 0; i < n - 1; i++) cin >> a >> b; cout << (C(n-1, m-1) * f[m]) % MOD<< endl; } return 0; }
I.Metropolis
题目描述 魔方国有n座城市，编号为。城市之间通过n-1条无向道路连接，形成一个树形结构。 在若干年之后，其中p座城市发展成了大都会，道路的数量也增加到了m条。 大都会之间经常有贸易往来，因此，对于每座大都会，请你求出它到离它最近的其它大都会的距离。
输入描述: 第一行三个整数n,m,p (1 ≤ n,m ≤ 2*105,2 ≤ p ≤ n)，第二行p个整数表示大都会的编号 (1≤ xi≤ n)。接下来m行每行三个整数ai,bi,li表示一条连接ai和bi，长度为li的道路 (1 ≤ ai,bi ≤ n,1 ≤ li ≤ 109)。 保证图是连通的。
输出描述: 输出一行p个整数，第i个整数表示xi的答案。 示例1
输入 5 6 3 2 4 5 1 2 4 1 3 1 1 4 1 1 5 4 2 3 1 3 4 3
输出 3 3 5
把所有大都会设为源点跑多源最短路，记下每个点是由哪个源点扩展的。 如果从源点 i 出发走到了一个由另一个源点 j 扩展到的点 k，那么从 i 出发 经过 k 的最短距离肯定是 dis[i][j]，那么就没有必要继续走下去了。所以只要枚 举所有两端由不同源点扩展的边更新答案就行了。 时间复杂度 O((n+m)logn)
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define MAX_N 200100 const LL INF = 1e15; struct Edge{int to; LL cost;}; typedef pair<LL, int> P; int T; int n,m,k; int p[MAX_N]; int is[MAX_N]; LL d[MAX_N]; LL ans[MAX_N]; vector<Edge> G[MAX_N]; void dijstra(){ for(int i = 1; i <= n; ++i) d[i] = INF; priority_queue<P, vector<P>, greater<P> > que; for(int i = 1; i <= k; ++i){ que.push(P(d[p[i]] = 0, p[i])); } while(!que.empty()){ P p = que.top(); que.pop(); int v = p.second; if(p.first > d[v]) continue; for(int i = 0; i < G[v].size(); ++i){ Edge e = G[v][i]; if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; is[e.to] = is[v]; // e.to是由v扩展的 que.push(P(d[e.to], e.to)); } else if(is[v] != is[e.to]){ // 不同源点扩展的边 ans[is[v]] = min(ans[is[v]], d[v] + d[e.to] + e.cost); ans[is[e.to]] = min(ans[is[e.to]], d[v] + d[e.to] + e.cost); } } } } int main(){ //freopen("in.txt", "r", stdin); int u,v; LL c; scanf("%d%d", &n, &m); for(int i = 0; i <= n; ++i) G[i].clear(); scanf("%d", &k); for(int i = 1; i <= k; ++i){ scanf("%d", &p[i]); ans[p[i]] = INF; is[p[i]] = p[i]; } for(int i = 1; i <= m; ++i){ scanf("%d%d%lld", &u, &v, &c); G[u].push_back((Edge){v, c}); G[v].push_back((Edge){u, c}); } dijstra(); for(int i = 1; i <= k; ++i){ printf("%lld%c", ans[p[i]], "n "[i < k]); } return 0; }
J. Graph Coloring I
题目描述 修修在黑板上画了一些无向连通图，他发现他可以将这些图的结点用两种颜色染色，满足相邻点不同色。 澜澜不服气，在黑板上画了一个三个点的完全图。修修跟澜澜说，这个图我能找到一个简单奇环。 澜澜又在黑板上画了一个n个点m条边的无向连通图。很可惜这不是一道数数题，修修做不出来了。 澜澜非常得意，作为一位毒瘤出题人，有了好题当然要跟大家分享，于是他把这道题出给你做了。
输入描述: 第一行两个整数n,m (1≤ n,m≤ 3*105)，接下来m行每行两个整数ai,bi表示一条边 (1≤ ai,bi≤ n)。 保证图连通，并且不存在重边和自环。 输出描述: 如果你能把图二染色，第一行输出0，第二行输出n个整数表示每个点的颜色 (0≤ xi≤ 1)。如果有多种合法方案，你可以输出任意一种。 如果你能找到一个简单奇环，第一行输出环长k，第二行输出k个整数表示环上结点编号 (1≤ yi≤ n)，你需要保证yi和yi+1之间有边，y1和yn之间有边。如果有多种合法方案，你可以输出任意一种。 如果两种情况都是可行的，你只需要输出任意一种。 如果两种情况都是不可行的，请输出一行一个整数-1。
示例1
输入 3 2 1 2 1 3
输出 0 0 1 1
示例2 复制 3 3 1 2 1 3 2 3
输出 3 1 2 3
判一下是不是二分图就行了。 时间复杂度 O(n+m)
#include <bits/stdc++.h> using namespace std; const int MAX_N = 3*1e5+100; int color[MAX_N]; vector<int> G[MAX_N]; vector<int> p; int n,m; int s,e; bool dfs(int u, int c){ color[u] = c; p.push_back(u); for(int i = 0; i < G[u].size(); ++i){ int v = G[u][i]; if(color[u] == color[v]) {s = v, e = u;return false;} if(!color[v]){ if(!dfs(v, 3 - c)) return false; } } p.erase(--p.end()); return true; } int main(){ //freopen("in.txt", "r", stdin); scanf("%d%d", &n, &m); int u,v; for(int i = 1; i <= m; ++i){ scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } memset(color, 0, sizeof(color)); if(dfs(1, 1)){ puts("0"); for(int i = 1; i<= n; ++i){ printf("%d%c", color[i]-1, "n "[i < n]); } } else { int i = -1; int sz = p.size(); while(p[++i] != s); printf("%dn", sz - i); for(;i < sz; ++i){ printf("%d%c", p[i], "n "[i < sz-1]); } } return 0; }
