2017icpc青岛

自用笔记算法

2017icpc青岛

B

题目要求

判断一个3×3的矩阵 是否有某一行或者某一列或者对角线是c t z 如果是则输出 否则输出ongoing

参考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
#include<bits/stdc++.h>
using namespace std;
int t;
char mp[5][5];
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		for(int i=1;i<=3;i++) scanf("%s",mp[i]+1);
		int flag=0;
		for(int i=1;i<=3;i++){
			if(mp[i][1]==mp[i][2] && mp[i][2]==mp[i][3] && mp[i][1]!='.'){
				printf("%c\n",mp[i][1]);
				flag=1;
				break;
			}
		}
		if(flag) continue;
		flag=0;
		for(int i=1;i<=3;i++){
			if(mp[1][i]==mp[2][i] && mp[2][i]==mp[3][i] && mp[1][i]!='.'){
				printf("%c\n",mp[1][i]);
				flag=1;
				break;
			} 
		}
		if(flag) continue;
		flag=0;
		if(mp[1][1]==mp[2][2] && mp[2][2]==mp[3][3] && mp[1][1]!='.'){
			printf("%c\n",mp[1][1]);
			flag=1;
		}
		if(flag) continue;
		flag=0;
		if(mp[1][3]==mp[2][2] && mp[2][2]==mp[3][1] && mp[1][3]!='.'){
			printf("%c\n",mp[1][3]);
			flag=1;
		}
		if(flag) continue;
		puts("ongoing");
	}
	return 0;
}

思路

直接模拟

I

题目要求

有一个n×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
#include<bits/stdc++.h>
#define maxn 50
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
char g[maxn][maxn];
int t,n;
void dfs(int x,int y,int dir){
	if(dir==1){
		if(g[x-1][y]=='#' || g[x+1][y]=='#' || g[x][y+1]=='#') return;
		g[x][y]='#';
		y++;
		if(y>n || g[x][y+1]=='#') dfs(x+1,y-1,2);
		else dfs(x,y,dir);
	}
	if(dir==2){
		if(g[x][y-1]=='#' || g[x][y+1]=='#' || g[x+1][y]=='#') return;
		g[x][y]='#';
		x++;
		if(x>n || g[x+1][y]=='#') dfs(x-1,y-1,3);
		else dfs(x,y,dir);
	}
	if(dir==3){
		if(g[x-1][y]=='#' || g[x+1][y]=='#' || g[x][y-1]=='#') return;
		g[x][y]='#';
		y--;
		if(y<1 || g[x][y-1]=='#') dfs(x-1,y+1,4);
		else dfs(x,y,dir);
	}
	if(dir==4){
		if(g[x][y-1]=='#' || g[x][y+1]=='#' || g[x-1][y]=='#') return;
		g[x][y]='#';
		x--;
		if(x<1 || g[x-1][y]=='#') dfs(x+1,y+1,1);
		else dfs(x,y,dir);	
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=0;i<=40;i++){
			for(int j=0;j<=40;j++) g[i][j]=' ';
		}
		dfs(1,1,1);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				printf("%c",g[i][j]);
			}
			puts("");
		}
	}
	return 0;
}

思路

dfs模拟
注意遇到边界或者遇到障碍物就进入下一方向

K

题目要求

给出一些城市的机场顺序 要求从西安出发 经过青岛前先经过上海 离开青岛后最后要到达上海的浦东
上海有2个机场可以相互到达 分别是虹桥和浦东
如果第一次只经过虹桥没有转换 那么第二次只能到浦东
如果要内部交换只能第一次是浦东到虹桥 第二次是虹桥到浦东
每个机场都只能离开和到达一次(除了浦东可以到达两次) 并且都有费用 要求费用最小

参考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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 20050 
using namespace std;
int t,n;
const int base=10005;
struct Edge{
	int from,to,cap,flow,cost;
	Edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),flow(flow),cost(cost){}
};
struct MCMF{
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	int inq[maxn],d[maxn],p[maxn],a[maxn];
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++) G[i].clear();
		edges.clear();
	}
	void AddEdge(int from,int to,int cap,int cost){
		edges.push_back(Edge(from,to,cap,0,cost));
		edges.push_back(Edge(to,from,0,0,-cost));
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	bool BellmanFord(int s,int t,int& flow,int& cost){
		for(int i=0;i<n;i++) d[i]=inf;
		memset(inq,0,sizeof(inq));
		d[s]=0,inq[s]=1,p[s]=0,a[s]=inf;
		queue<int>Q;
		Q.push(s);
		while(!Q.empty()){
			int u=Q.front();
			Q.pop();
			inq[u]=0;
			for(int i=0;i<(int)G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
					d[e.to]=d[u]+e.cost;
					p[e.to]=G[u][i];
					a[e.to]=min(a[u],e.cap-e.flow);
					if(!inq[e.to]){
						Q.push(e.to);
						inq[e.to]=1;
					}
				}
			}
		}
		if(d[t]==inf) return false;
		flow+=a[t];
		cost+=d[t]*a[t];
		int u=t;
		while(u!=s){
			edges[p[u]].flow+=a[t];
			edges[p[u]^1].flow-=a[t];
			u=edges[p[u]].from;
		}
		return true;
	}
	void Mincost(int s,int t){
		int flow=0,cost=0;
		while(BellmanFord(s,t,flow,cost));
		if(flow==3) printf("%d\n",cost);
		else printf("-1\n");
	}
}g;
char s1[15],s2[15];
map<string,int>mp;
int w,id;
int main(){
	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		mp.clear();
		g.init(maxn);
		id=0;
		int S=0,T=20010;
		for(int i=1;i<=n;i++){
			scanf("%s%s%d",s1,s2,&w);
			if(!mp.count(s1)){
				mp[s1]=++id;
				if(strcmp(s1,"Hongqiao")==0) g.AddEdge(mp[s1],mp[s1]+base,2,0);
				else if(strcmp(s1,"Qingdao")==0) g.AddEdge(mp[s1],mp[s1]+base,2,0);
				else g.AddEdge(mp[s1],mp[s1]+base,1,0);
			} 
			if(!mp.count(s2)){
				mp[s2]=++id;
				if(strcmp(s2,"Hongqiao")==0) g.AddEdge(mp[s2],mp[s2]+base,2,0);
				else if(strcmp(s2,"Qingdao")==0) g.AddEdge(mp[s2],mp[s2]+base,2,0);
				else g.AddEdge(mp[s2],mp[s2]+base,1,0);
			}
			g.AddEdge(mp[s1]+base,mp[s2],inf,w);
			g.AddEdge(mp[s2]+base,mp[s1],inf,w);
		}
		g.AddEdge(S,mp["Qingdao"],inf,0);
		g.AddEdge(S,mp["Xian"],inf,0);
		g.AddEdge(mp["Hongqiao"]+base,T,inf,0);
		g.AddEdge(mp["Pudong"]+base,T,inf,0);
		g.Mincost(S,T);
	}
	return 0;
}

思路

MCMF
根据题目要求只能是2种情况
1.西安->···->虹桥->···->青岛->···->浦东
2.西安->···->浦东->虹桥->···->青岛->···->虹桥->浦东
观察两种情况 我们可以分成三段 西安出发的一段 青岛流往两边的两段
两种情况都要求虹桥和青岛连的边流量为2 其余为1 拆点跑mcmf 判断最后是否满流(flow==3)

本文标题:2017icpc青岛

文章作者:Hippopmonkey

发布时间:2017-11-12, 19:47:13

最后更新:2017-11-12, 20:07:05

原始链接:http://xuboming8.github.io/2017/11/12/2017icpc青岛/

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

文章目录
  1. 1. 2017icpc青岛
    1. 1.1. B
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. I
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. K
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
|