2017南宁网络赛

自用笔记算法

2017南宁网络赛

Train Seats Reservation

题目要求

有编号为从1~100的火车站，现在有人要买票，告诉你n组信息，包括起点和终点火车站的编号以及需要多少个座位，问最少需要准备多少个座位。
比如一个人从1~5，另一人从5~10，只需要一个座位就够了

参考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
#include<bits/stdc++.h>
#define maxn 105
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
LL hashh[maxn];
int main(){
//	freopen("input.txt","r",stdin);
	int n;
	while(scanf("%d",&n)!=EOF){
		if(n==0){
			puts("*");
			break;
		}
		mm(hashh,0);
		for(int i=1;i<=n;i++){
			int s,t;
			LL k;
			scanf("%d%d%lld",&s,&t,&k);
			for(int j=s;j<t;j++) hashh[j]+=k;
		}
		LL ans=0;
		for(int i=1;i<=100;i++) ans=max(ans,hashh[i]);
		printf("%lld\n",ans);
	}
	return 0;
}

思路

模拟 注意区间是左闭右开
求出最大值即可

Auction Bidding

参考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
#include<bits/stdc++.h>
#define maxn 1050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
	int p,id;
	node(int p,int id):p(p),id(id){}
};
int n,m,k;
vector<node>e[maxn];
int cap[maxn],ans[maxn];
bool cmp(node a,node b){
	if(a.p==b.p) return a.id<b.id;
	return a.p>b.p;
}
int main(){
//	freopen("input.txt","r",stdin);
	int n,m;
	scanf("%d%d",&n,&m);
	mm(ans,0);
	for(int i=1;i<=n;i++){
		scanf("%d",&cap[i]);
		int x,y;
		while(scanf("%d",&x)){
			if(x==-1) break;
			scanf("%d",&y);
			if(y>=cap[i]) e[i].push_back(node(y,x));
		}
	}
	for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end(),cmp);
	for(int i=1;i<=n;i++){
		if(e[i].size()==1) ans[e[i][0].id]+=min((int)(cap[i]*1.1),e[i][0].p);
		if(e[i].size()>1) ans[e[i][0].id]+=min(e[i][0].p,(int)(e[i][1].p*1.1));
	}
	scanf("%d",&k);
	for(int i=1;i<=k;i++){
		int x;
		scanf("%d",&x);
		printf("%d\n",ans[x]);
	}
	return 0;
}

思路

按照价格从大到小排序
只存大于等于cap的值 最后只需判断e[i]的大小是1还是大于等于2即可
若等于1：说明第二大的价格小于cap 这部分要当作cap算 若只需判断最大值和cap的1.1倍即可
若大于等于2：直接比较第一大和第二大的1.1倍即可

Overlapping Rectangles

题目要求

矩形面积并

参考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
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 2222;
int cnt[maxn << 2];
int sum[maxn << 2];
int X[maxn];
struct Seg {
	int h , l , r;
	int s;
	Seg(){}
	Seg(int a,int b,int c,int d) : l(a) , r(b) , h(c) , s(d) {}
	bool operator < (const Seg &cmp) const {
		return h < cmp.h;
	}
}ss[maxn];
void PushUp(int rt,int l,int r) {
	if (cnt[rt]) sum[rt] = X[r+1] - X[l];
	else if (l == r) sum[rt] = 0;
	else sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void update(int L,int R,int c,int l,int r,int rt) {
	if (L <= l && r <= R) {
		cnt[rt] += c;
		PushUp(rt , l , r);
		return ;
	}
	int m = (l + r) >> 1;
	if (L <= m) update(L , R , c , lson);
	if (m < R) update(L , R , c , rson);
	PushUp(rt , l , r);
}
int Bin(int key,int n,int X[]) {
	int l = 0 , r = n - 1;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (X[m] == key) return m;
		if (X[m] < key) l = m + 1;
		else r = m - 1;
	}
	return -1;
}
int main(){
//	freopen("input.txt","r",stdin);
	int n;
	while (~scanf("%d",&n) && n) {
		int m = 0;
		while (n --) {
			int a , b , c , d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
			X[m] = a;
			ss[m++] = Seg(a , c , b , 1);
			X[m] = c;
			ss[m++] = Seg(a , c , d , -1);
		}
		sort(X , X + m);
		sort(ss , ss + m);
		int k = 1;
		for (int i = 1 ; i < m ; i ++) {
			if (X[i] != X[i-1]) X[k++] = X[i];
		}
		memset(cnt , 0 , sizeof(cnt));
		memset(sum , 0 , sizeof(sum));
		int ret = 0;
		for (int i = 0 ; i < m - 1 ; i ++) {
			int l = Bin(ss[i].l , k , X);
			int r = Bin(ss[i].r , k , X) - 1;
			if (l <= r) update(l , r , ss[i].s , 0 , k - 1, 1);
			ret += sum[1] * (ss[i+1].h - ss[i].h);
		}
		printf("%d\n",ret);
	}
	puts("*");
	return 0;
}

思路

模版题
扫描线+线段树

Minimum Distance in a Star Graph

题目要求

给你1-N的N个数,构建N维,然后构图的规则是相邻的顶点只能是由第一个字符跟2-n的字符进行交换得来的,问你给出的五个询问中两个节点的最短距离分别是多少？

参考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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
#define maxn 400050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int vis[maxn];
int fac[10]={0,1,2,6,24,120,720,5040,40320,362880};
struct node{
	int num,dep;
	node(int num,int dep):num(num),dep(dep){}
};
int n,ans;
int cantor(int key,int fac[],int n){
	int result,temp[n];
	for(int i=n-1;i>=0;i--){
		temp[i]=key%10;
		key=key/10;
	}
	result=0;
	for(int i=0;i<n-1;i++){
		int tot=0;
		for(int j=i+1;j<n;j++){
			if(temp[j]<temp[i]) tot++;
		}
		result+=tot*fac[n-1-i];
	}
	return result;
}
int getnum(char s[]){
	int num=0;
	for(int i=0;i<n;i++) num=num*10+s[i]-'0';
	return num;
}
int change(int num,int id){
	char s[20];
	int index=n-1;
	while(num){
		char ex=(char)(num%10+'0');
		s[index--]=ex;
		num/=10;
	}
	char temp=s[0];
	s[0]=s[id];
	s[id]=temp;
	int ans=getnum(s);
	return ans;
}
void bfs(int num1,int num2){
	queue<node>q;
	while(!q.empty()) q.pop();
	q.push(node(num1,0));
	int temp=cantor(num1,fac,10);
	vis[temp]=1;
	while(!q.empty()){
		int x=q.front().num;
		int y=q.front().dep;
		q.pop();
		if(x==num2){
			ans=y;
			break;
		}
		for(int i=1;i<=n-1;i++){
			int next=change(x,i);
			int nextt=cantor(next,fac,10);
			if(!vis[nextt]){
				q.push(node(next,y+1));
				vis[nextt]=1;
			}
		}
	}
}
char s1[20],s2[20];
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=5;i++){
		ans=0;
		mm(vis,0);
		scanf("%s %s",s1,s2);
		int num1=getnum(s1);
		int num2=getnum(s2);
		bfs(num1,num2);
		printf("%d\n",ans);
	}
	return 0;
}

思路

bfs+记忆化
数字的交换：转换成字符数组后交换字符再转换成整形 queue里存的是整形数字+宽搜深度(即最后的答案)
记忆化：对整形数字使用set或者map会tle 9位数字也无法直接开o1的数组 因为这里的点是阶乘关系 所以我们想到用康拓展开来hash
就换转成普通的vis数组判重了

本文标题:2017南宁网络赛

文章作者:Hippopmonkey

发布时间:2017-09-26, 11:16:25

最后更新:2017-09-26, 13:19:42

原始链接:http://xuboming8.github.io/2017/09/26/2017南宁网络赛/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 2017南宁网络赛
    1. 1.1. Train Seats Reservation
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. Auction Bidding
      1. 1.2.1. 参考AC代码
      2. 1.2.2. 思路
    3. 1.3. Overlapping Rectangles
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. Minimum Distance in a Star Graph
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
|