牛客集训派对day3

原比赛链接
emmm.国庆刷题狂欢,来自暑假ccpc-wannafly camp day 3的题目

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;
}