2020-8-12 队伍训练2

字数统计: 3.2k字   |   阅读时长: 17分
训练题解
序号 题目 Solved Attempted 类型 补题
A Tokitsukaze and Rescue / Sstee1XD DFS＋Dijkstra Sstee1XD、lllllan
B Blow up the Enemy Sstee1XD / 思维 lllllan
C Contest of Rope Pulling / /
D Deliver the Cake / lllllan 拆点建图＋Dijkstra lllllan
E Equal Sentences Sstee1XD / 基础DP lllllan
F Go Running / /
G Kindergarten Physics lllllan / 输入输出
H Last Problem / Sstee1XD
I Tetrahedron / /
J Paperfolding / /

A - Tokitsukaze and Rescue

题意： 给你一张所有点互相直接连通的图，可以炸掉k条边，问你最长的最短路径长度。

题解： 由于所有点都是直接连通的，直接用二维数组存就行了，训练时用链式一直T。方法是dfs，每层进行一次dij，记录每次路径，然后枚举炸掉的路径。（之前写的时候dij还放在了循环了，下次要引起注意。

Sstee1XD 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>

using namespace std;

#define outtime() cerr<<"User Time = "<<(double)clock()/CLOCKS_PER_SEC<<endl
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define bug printf("bug**")
#define coutlf(x) cout << fixed << setprecision(x)
#define uncoutlf  cout.unsetf(ios::fixed)
#define S_IT set<Node>::iterator
#define endl "\n"
#define fi first
#define se second
#define mp(a,b) make_pair(a,b)

int gcd(int a,int b) { return b?gcd(b,a%b):a;}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pII;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
const int maxm = 2507;

template<class T> inline void read(T &x){
    int f=0;x=0;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    if(f)x=-x;
}

int n, k, dis[60], ans;
int path[10][60];
int maps[100][100];

struct qnode{
    int u, w;
    qnode () {}
    qnode (int u, int w) : u(u), w(w) {}
    bool operator < (const qnode &a) const{
        return w > a.w;
    }
};

void Dijkstra(int s, int d) {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<qnode> q;
    q.push(qnode(s, 0));
    dis[s] = 0;
    path[d][1] = -1;
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        for (int i = 1; i <= n; ++i) {
            int w = maps[u][i];
            if (dis[u] + w < dis[i]) {
                dis[i] = dis[u] + w;
                q.push(qnode(i, dis[i]));
                path[d][i] = u;
            }
        }
    }
}

void dfs(int d) {
    Dijkstra(1, d);
    if (d == k) {
        ans = max(ans, dis[n]);
        return;
    }
    for (int i = n; path[d][i] != -1; i = path[d][i]) {
        int v = path[d][i];
        int tmp = maps[i][v];
        maps[i][v] = maps[v][i] = inf;
        dfs(d + 1);
        maps[i][v] = maps[v][i] = tmp;
    }
    
}
void solve() {
    read(n), read(k);
    memset(maps, 0x3f, sizeof(maps));
    int m = (n * (n - 1)) >> 1;
    for (int i = 1, u, v, w; i <= m; ++i) {
        read(u), read(v), read(w);
        maps[u][v] = maps[v][u] = w;
    }
    ans = 0;
    dfs(0);
    printf("%d\n", ans);
}

int _T;

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    read(_T);
    while (_T--) solve();
    return 0;
}
lllllan 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 60;

int T, n, m, k, ans;
int dis[N], pre[N][N], mp[N][N];
struct node{	
	int u, w;
	bool operator <(const node a)const {return a.w < w;}
};
void dijkstra(int cnt){
	memset(dis, inf, sizeof dis);
	priority_queue<node> q;
	q.push({1, 0}); dis[1] = 0;
	while(!q.empty()){
		int u = q.top().u; q.pop();
		for(int i = 1; i <= n; i++){
			int w = mp[u][i];
			if(dis[i] > dis[u] + w){
				dis[i] = dis[u] + w;
				q.push({i, dis[i]});
				pre[cnt][i] = u;
			}
		}
	}
}
void dfs(int u, int cnt){
	dijkstra(cnt);
	if(cnt == k){	ans = max(ans, dis[n]);	return;}
	while(~pre[cnt][u]){
		int v = pre[cnt][u];
		int w = mp[u][v];
		mp[u][v] = mp[v][u] = inf;
		dfs(n, cnt + 1);
		mp[u][v] = mp[v][u] = w;
		u = v;
	}
}
int main(){
	scanf("%d", &T);while(T--){
		memset(mp, inf, sizeof mp);
		memset(pre, -1, sizeof pre);
		scanf("%d%d", &n, &k);
		m = n * (n -1) / 2;while(m--){
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			mp[u][v] = mp[v][u] = w;
		}
		dijkstra(1);	ans = dis[n];
		dfs(n, 0);
		printf("%d\n", ans);
	}
	return 0;
}

B - Blow up the Enemy

题意： 张三和父亲玩fps，每个人开始有100生命值，可以拿一种武器，每次开枪可以扣对方AiA_i生命值，每次间隔DiD_i时间开枪，若对手生命值降到0及以下时自己生命值大于0，则获胜，若同时降到0及以下，则各有50%概率获胜。父亲每次随机拿，问张三获胜概率。

题解： 刚开始读错题意，卡了一会儿，后面就发现是个水题。只要把每把武器能获胜的时间记录下来sort一下，遍历一遍就行了。

Sstee1XD 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>

using namespace std;

#define outtime() cerr<<"User Time = "<<(double)clock()/CLOCKS_PER_SEC<<endl
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define bug printf("bug**")
#define coutlf(x) cout << fixed << setprecision(x)
#define uncoutlf  cout.unsetf(ios::fixed)
#define S_IT set<Node>::iterator
#define endl "\n"
#define fi first
#define se second
#define mp(a,b) make_pair(a,b)

int gcd(int a,int b) { return b?gcd(b,a%b):a;}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pII;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
const int maxn = 1e3 + 7;
int a[maxn], d[maxn], t[maxn];
void cal(int u) {
	int num = (100 + a[u] - 1) / a[u];
	t[u] = (num - 1) * d[u];
}

int n;

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d %d", &a[i], &d[i]), cal(i);
	sort(t + 1, t + 1 + n);
	double div = n * 2;
	double head = 0;
	for (int i = 1; i <= n; ++i) {
		if (t[i] == t[1]) head++;
		else {
			head += 2 * (n - i + 1);
			break;
		}
	}
	printf("%.7f\n", head / div);
}

int _T;

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d", &_T);
	while(_T--) solve();
	return 0;
}
lllllan 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

int T, n, num;
int a[N], d[N], t[N];
int main(){
	scanf("%d", &T);while(T--){
		scanf("%d", &n);
		for(int i = 1; i <= n; i++){
			scanf("%d%d", a+ i, d + i);
			num = (100 + a[i] - 1) / a[i];
			t[i] = (num - 1) * d[i];
		}
		int cnt = 0;
		sort(t + 1, t + n +1);
		for(int i = 1; i <= n; i++)
			if(t[i] == t[1])	cnt++;
			else				break;
		printf("%lf\n", (double)(2 * n - cnt) / (2 * n));
	}
	return 0;	
}

D - Deliver the Cake

题意： n个城市m条边，要求手里拿着蛋糕从城市s到达城市t。限制条件为，每条城市有个方向属性:LRM，如果是属性为L，则必须左手拿蛋糕，如果属性M，则左右手都行；可以在任何位置执行换手操作，需要花费时间x。求最短路。
题解： 本来天真地直接在dijkstra的函数里动手脚，琢磨了好久都觉得写的非常完美，：），WA了，无数遍。

拆点建图

  后来补题学习了隔壁队wmh哥哥的思路，dijkstra的函数不变，原模原样地跑。改变存图方式，读入某条边的时候，如果明确两端的城市的方向属性不同，则直接给这条边的权值加上换手时间x。如果其中一段的城市的方向属性为中性的M，则新建一个点，原来的点可以设其方向属性为左，新建的点设其方向属性为右，然后分别建这两条边。说起来很晦涩，直接上图：![在这里插入图片描述](https://img-blog.csdnimg.cn/2020081222031882.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2MTg3MTU3,size_16,color_FFFFFF,t_70#pic_center =300x200)
  其核心思想就是就是让方向属性中性的城市，一分为二，变成两个带有具体方向属性的城市，然后分别去计算。至于点的编号，则需要作一些小改动，可以把整体的编号乘2，比如编号1的点，其左方向属性的点编号为1 << 1 = 2，其右方向属性的点编号为1 << 1 | 1 = 3。往后所有的点编号同理。最后将起点的两个下属编号与编号0相连，终点的两个下属编号与编号1相连。跑一遍dijkstra的模板求点0到点1的距离。
  采用链式前向星存图，但也要分类讨论，判断某条边两端的方向属性如何，于是···出现又长又丑的代码。我用hand[]数组来记录每个点的方向属性，读入每条边的时候判断两端的方向属性，然后建立新的点，然后存图。光光存图就用了二十几行代码，直接看吐。在这里插入图片描述
  后期的整理归类之后，形成了最后的代码：

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 100;

int T, n, m, s, t, cnt;
int vis[N], head[N];
char hand[N];
ll x, dist[N];
struct edge{	int to, next; ll w;}e[N];
struct node{
	int id; ll w;
	node(int a, ll b){	id = a; w = b;}
	bool operator <(const node a)const{	return a.w < w;}
};
priority_queue<node> q;
void addedge(int x, int y, ll w){ e[cnt].to = y; e[cnt].w  = w; e[cnt].next = head[x]; head[x] = cnt++;}
void doubleadd(int x, int y, ll w){ addedge(x, y, w); addedge(y, x, w);}
void init(){
	cnt = 0;
	for(int i = 0; i < N; i++)	dist[i] = INF, head[i] = -1, vis[i] = 0;
	while(!q.empty())	q.pop();
}
void dijkstra(){
	dist[0] = 0;
	q.push(node(0, 0));
	while(!q.empty()){
		node p = q.top();q.pop();
		if(vis[p.id])	continue;
		vis[p.id] = 1;
		for(int i = head[p.id]; ~i; i = e[i].next){
			edge t = e[i];
			if(!vis[t.to] && dist[t.to] > dist[p.id] + t.w){
				dist[t.to] = dist[p.id] + t.w;
				q.push(node(t.to,dist[t.to]));
			}
		}
	}
	printf("%lld\n", dist[1]);
}
int main(){
	scanf("%d", &T);while(T--){
		init();
		scanf("%d%d%d%d%lld", &n, &m, &s, &t, &x);getchar();
		for(int i = 1; i <= n; i++)	scanf("%c", hand + i);
		while(m--){
			int a, b; ll c;scanf("%d%d%lld", &a, &b, &c);
			if(hand[a] != 'R'){
				if(hand[b] != 'R')	doubleadd(a << 1, b << 1, c);
				if(hand[b] != 'L')	doubleadd(a << 1, b << 1 | 1, c + x);
			}
			if(hand[a] != 'L'){
				if(hand[b] != 'R')	doubleadd(a << 1 | 1, b << 1, c + x);
				if(hand[b] != 'L')	doubleadd(a << 1 | 1, b << 1 | 1, c);
			}
		}
		if(hand[s] != 'R')	addedge(0, s << 1, 0);
		if(hand[s] != 'L')	addedge(0, s << 1 | 1, 0);
		if(hand[t] != 'R')	addedge(t << 1, 1, 0);
		if(hand[t] != 'L')	addedge(t << 1 | 1, 1, 0);
		dijkstra();
	}
	return 0;
}

E - Equal Sentences

题意： 给你一句由英文单词构成的句子，问你最多有几种类似的句子。这里的类似指任意位置上的单词与原句的距离差不超过1，即可以交换相邻的单词，但只能每个单词最多只能交换一次。

题解： 上午写的时候一直没读懂题意，读懂了之后很快就想到了是一个很简单的dp。我们从前往后看，若当前位置的单词与前面的相同，则它们交换与否对答案不造成影响，所以 dpidp_i = dpi−1dp_{i-1}。如果不相同，则他们可以进行交换，则 dpidp_i = dpi−1dp_{i-1} + dpi−2dp_{i-2}。

Sstee1XD 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>

using namespace std;

#define outtime() cerr<<"User Time = "<<(double)clock()/CLOCKS_PER_SEC<<endl
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define bug printf("bug**")
#define coutlf(x) cout << fixed << setprecision(x)
#define uncoutlf  cout.unsetf(ios::fixed)
#define S_IT set<Node>::iterator
#define endl "\n"
#define fi first
#define se second
#define mp(a,b) make_pair(a,b)

int gcd(int a,int b) { return b?gcd(b,a%b):a;}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pII;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;

int n;
int id[maxn], t, dp[maxn];
string s, pre;
void solve() {
	cin >> n;
	pre = "";
	t = 0;
	dp[0] = dp[1] = 1;
	for (int i = 1; i <= n; ++i) {
		cin >> s;
		if (s == pre) id[i] = t;
		else id[i] = ++t;
		pre = s;
	}
	for (int i = 2; i <= n; ++i) {
		if (id[i] == id[i - 1]) dp[i] = dp[i - 1];
		else dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
	}
	printf("%d\n", dp[n]);
}
int _T;
int main() {
	IOS;
	cin >> _T;
	while (_T--) solve();
	return 0;
}
lllllan 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;

int T, n;
int dp[N];
string s[N];
int main(){
	scanf("%d", &T);while(T--){
		scanf("%d", &n);
		dp[0] = dp[1] = 1;
		for(int i = 1; i <= n; i++)	cin >> s[i];
		for(int i = 2; i <= n; i++)
			if(s[i] == s[i - 1])	dp[i] = dp[i - 1];
			else	dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
		printf("%d\n", dp[n]);
	}
	return 0;
}

G - Kindergarten Physics

题意： （其实我是没有看懂的）随便扔两个公式感受一下
  F = G ⋅ m1 · m2 / m2
  G = 6.67430 × 10-11 m3 / (kg ⋅ s2）

题解： 其实不用其实不用，公式里的达到了10-11 恐怖精确度，但是题目的输出只要求10-6 ，所以，所以这题，就是简单的输入输出：）

AC代码 
1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;

int main(){
	int t, a, b, c, d;
	scanf("%d", &t);
	while(t--){
		scanf("%d%d%d%d", &a, &b, &c, &d);
		printf("%lf\n", (double)c);
	}
	return 0;
}
文章目录
  1. A - Tokitsukaze and Rescue
  2. B - Blow up the Enemy
  3. D - Deliver the Cake
  4. E - Equal Sentences
  5. G - Kindergarten Physics
|