主页 > 程序人生 > tc终于变绿了。。。

tc终于变绿了。。。

    今天做了一场topcoder，终于让我的万年灰号变成绿色的了。。。

    虽然么有cha人代码，呵呵

   今天的题目不是很难，所以比较轻松的解决了前两个水题

  第一题ImportantTasks是给你两堆数字，让你找出上一堆比下一堆小的数最多有几对，要一一对应。。。

  排序，然后直接水过…

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

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
 
#define PB push_back
#define MP make_pair
 
#define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)
 
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII;
 
 
class ImportantTasks
{
        public:
        int maximalCost(vector <int> complexity, vector <int> computers)
        {
			bool hashh[100]={0};
			int i,j,k=0,l;
			sort(complexity.begin(),complexity.end());
			sort(computers.begin(),computers.end());
 
			for(i=complexity.size()-1;i>=0;i--)
			{
				l=complexity[i];
				for(j=0;j<computers.size();j++)
				{
					if(l<=computers[j]&&!hashh[j])
					{
						hashh[j]=1;
						k++;
						break;
					}
				}
			}
			return k;
        }

第二题KnightsTour就是骑士走棋盘，不过有些点不能走，而且每个点要动态更新权值。。。暴力+模拟。。。水过

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
 
#define PB push_back
#define MP make_pair
 
#define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)
 
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII;
int as[9][9];
 int dir[8][2]={{2,1},{-2,1},{2,-1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
class KnightsTour
{
        public:
        int visitedPositions(vector <string> board)
        {		 
			 int k,i,j;
 
			 struct knight{
				 int x,y;
				 int t;
				 bool ha[9][9];
				 bool move(vector <string> bo)
				 {
					 int i,j,k,si,sj,ax=-1,ay=-1,ass=-1;					 
					 for(i=0;i<8;i++)
					 {
						 si=x+dir[i][0];
						 sj=y+dir[i][1];
						 if(si<0||sj<0||si>=8||sj>=8)
							 continue;
						 if(ha[si][sj])
							 continue;
						 if(bo[si][sj]=='*')
							 continue;
						 if(ax==-1||(ass>as[si][sj])||(ass==as[si][sj]&&ax>si)||(ass==as[si][sj]&&ax==si&&ay>sj))
						 {
							 ax=si;
							 ay=sj;
							 ass=as[si][sj];
						 }
 
					 }
 
					 if(ax!=-1)
					 {
 
 
						 ha[ax][ay]=1;
						 x=ax;
						 y=ay;
						 t++;	
 
						 memset(as,0,sizeof(as));
						 for(i=0;i<bo.size();i++)
						 {
							 for(j=0;j<bo[i].length();j++)
							 {
 
								 if(bo[i][j]=='.'&&!ha[i][j])
								 {
									 for(k=0;k<8;k++)
									 {
										  si=i+dir[k][0];
										  sj=j+dir[k][1];
										 if(si<0||sj<0||si>=8||sj>=8)
											 continue;
										 if(bo[si][sj]!='*'&&!ha[si][sj])
											 as[i][j]++;
 
									 }
								 }
 
							 }
						 }
 
						 return 1;
					 }else
						 return 0;
				 }
			 };
				 knight head;
				 memset(as,0,sizeof(as));
				 for(i=0;i<board.size();i++)
				 {
					 for(j=0;j<board[i].length();j++)
					 {
						 if(board[i][j]=='K')
						 {
							 head.x=i;
							 head.y=j;
							 head.t=1;
							 memset(head.ha,0,sizeof(head.ha));
							 head.ha[head.x][head.y]=1;
							 break;
						 }
 
 
					 }
				 }
				 for(i=0;i<board.size();i++)
					 for(j=0;j<board[i].length();j++)
					 {
						 if(board[i][j]=='.')
						 {
							 for(k=0;k<8;k++)
							 {
								 int si=i+dir[k][0];
								 int sj=j+dir[k][1];
								 if(si<0||sj<0||si>=8||sj>=8)
									 continue;
								 if(board[si][sj]!='*'&&!head.ha[si][sj])
									 as[i][j]++;
 
							 }
 
						 }
					 }
 
				 while(head.move(board));
				 return head.t;
 
 
        }

第三题没能看完，因为临时有事情出去了。。。回来一看，自己的号终于变绿了。。。

 

  话说今天这一场是facebook赞助的。。。

相关日志

, , , , ,

评论:4

参与评论
  1. 回复 耍下
    09/08/27

    高人啊。

    发表评论这里不能用tab，不方便啊。[face:rescue]

    • 回复 混沌的云
      09/08/27

      这样的啊。。。有什么办法么？我对php什么的不太懂啊

  2. 回复 耍下
    09/08/28

    这个应该不是php吧，改html都可以了。

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性： <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

引用:0

下面所列的是引用到本博客的链接
tc终于变绿了。。。 来自 混沌的云
顶部