牛客集训派对day3
牛客集训派对day3
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("%.1lf\n", 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("%d\n", sz - i);
for(;i < sz; ++i){
printf("%d%c", p[i], "\n "[i < sz-1]);
}
}
return 0;
}