SRM 522 DIV2总结报告

250的题目:

就是两层for循环考虑一对点,组成一个retangle,然后再一个for检查这两个点之间(横坐标),有多少个点的纵坐标在这两个点之间。

550的题目:

比如AXXX或者XXXA,则输出”Alice”,否则输出”Bob”。

900的题目:

这题其实也很简单,题目没注意,他说了a,b,c都是1~1000 000(注意c也是的)

因为a+b+c<=3000 000,所以可以考虑C的最大值小于3000 000

又因为A*B=C,可以想到线性筛选法,另A=1~1000 000,然后C从A开始,每次加A,然后判断abs的值。

当然,这题也可以暴力,不过要采取适当的剪枝。

代码:

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
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
 
class CorrectMultiplicationTwo
{
public:
    /*
    int getMinimum(int a, int b, int c)
    {
        long long int tmp = a+b+c;
 
        for(int i=1; i<=1000000; ++i)
            for(int j=1; j<=1000000; ++j)
            {
                if(abs(i-a) + abs(j-b) + abs(i*j-c) < tmp)
                    tmp = abs(i-a) + abs(j-b) + abs(i*j-c);
                if(i*j > c)
                    break;
            }
        return tmp;
    }
    */
 
    int getMinimum(int a, int b, int c)
    {
        int x = a, y = b, z = c;
        if(x > y)
            swap(x, y);
        int minn = 3000000;
        int tmp;
        for(int i=1; i<=1000000; ++i)
        {
            for(int j=i; j<=3000000; j+=i)
            {
                tmp = abs(i-x) + abs(j/i-y) + abs(j-z);
                minn = min(minn, tmp);
            }
        }
        return minn;
    }
};

SRM 496 DIV2

这次很郁闷,非常郁闷!!!

500的题里一个j+1我居然写成j了!!!!直接被系统CHA了。

 

250的题目:

水题,用map即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class AnagramFree{
public:
	int getMaximumSubset(vector <string> S)
	{
		map<string, int> mm;
		for(vector<string>::size_type i=0; i<S.size(); ++i)
		{
			sort(S[i].begin(), S[i].begin()+S[i].size());
			mm[S[i]]++;
		}
                         return mm.size();
	}
};

 

500的题目:

暴力,计数即可

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 <iostream>
#include <cmath>
#include <iomanip>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
 
class ColoredStrokes{
public:
	int getLeast(vector <string> picture)
	{
		int high = picture.size(), wide = picture[0].size();
		int cnt = 0;
		// heng
		for(int i=0; i<high; ++i)
		{
			for(int j=0; j<wide; ++j)
			{
				if(picture[i][j] == 'R' || picture[i][j] == 'G')
				{
					if(picture[i][j] == 'G')
						picture[i][j] = 'B';
					while(j+1<wide && (picture[i][j+1] == 'R' || picture[i][j+1] =='G'))
					{
						if(picture[i][j+1] == 'G')   // 这里先写成[i][j]了,导致WA。。。
							picture[i][j+1] = 'B';
						++j;
					}
					++cnt;
				}
			}
		}
 
		// shu
		for(int j=0; j<wide; ++j)
		{
			for(int i=0; i<high; ++i)
			{
				if(picture[i][j] == 'B')
				{
					while(i+1<high && picture[i+1][j] == 'B')
						++i;
					++cnt;
				}
			}
		}
		return cnt;
 
 
	}
};

 

1000的题目直接WS。

SRM 495 DIV2

第二次参加,第一题再也没发生上次的悲剧了。

250:
5分钟看题,5分钟干掉。水题不多说:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class CarrotBoxesEasy{
public:
	int theIndex(vector <int> carrots, int K)
	{
		int _max = -1;
		int idx = -1;
		for(int i=1; i<=K; ++i)
		{
			_max = -1;
			idx = -1;
			for(int j=0; j<carrots.size(); ++j)
				if(carrots[j] > _max)
				{
					_max = carrots[j];
					idx = j;
				}
			--carrots[idx];
		}
		return idx;
	}
};

575:
其实也是水题,但是不知道为何被我想复杂了。
今天再做一次,发现很简单,可以用两个vector A和B,一个存储从最小开始的成立的队列,一个存储从最后开始的成立的队列,然后比较A,B相应元素,若相等,则等于这个值,否则当前位置等于-1.

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
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
 
class ColorfulCards{
public:
	bool Is_prime(int n)
	{
		if(n==1)
			return 0;
		else if(n==2)
			return 1;
		else if(n==3)
			return 1;
		for(int i=2; i*i<=n; ++i)
			if(n%i==0)
				return 0;
	    return 1;
	}
 
	vector <int> theCards(int N, string colors)
	{
		//cout << "N=" << N << " ; " << colors << endl;
		vector<int> beg, end, ans;
		int cnt = 1;
		for(int i=0; i<colors.size(); ++i)
		{
			while( !( (colors[i]=='R'&&Is_prime(cnt)) || (colors[i]=='B'&&!Is_prime(cnt)) ) )
				++cnt;
			beg.push_back(cnt);
			++cnt;
		}
		//for(int i=0; i<beg.size(); ++i)
		//	cout << beg[i] << endl;
		//cout << endl;
 
		cnt = N;
		for(int i=colors.size()-1; i>=0; --i)
		{
			while( !( (colors[i]=='R'&&Is_prime(cnt)) || (colors[i]=='B'&&!Is_prime(cnt)) ) )
				--cnt;
			end.push_back(cnt);
			--cnt;
		}
		//for(int i=0; i<end.size(); ++i)
		//	cout << end[i] << endl;
		//cout << endl;
 
		for(int i=0; i<colors.size(); ++i)
			if(beg[i] == end[colors.size()-1-i])
				ans.push_back(beg[i]);
			else
				ans.push_back(-1);
 
		//for(int i=0; i<ans.size(); ++i)
			//cout << ans[i] << endl;
		return ans;
 
	}
};

这次增加了10几分。。。现在是953分了,下次争取干掉2题。。

SRM 494 DIV2 自己的第一次TC比赛

这是第一次参加TopCoder,也是第二次参加网络赛,第一次是去年的有道难题。

今天怎么说呢,有喜有忧吧。

首先对于TC不熟悉,而且对C++标准库用的也不是很习惯。导致第一题先开始没用map,而是想把first和second融合,然后排序,直接遍历vector。这个方法很麻烦,而且在compile时报错,于是我改成map,但是感觉不可能有错了,却还是报同样的错误,经过miyu提醒,原来是要用类表示出来,而我却是用函数表示的。。。。

汗一把,就因为这个问题,我花了20分钟去找错,结果第一题做完后只剩30多分钟了,而且第一题也只得了112.06分。

于是我抓紧看500的题,题目不难,我直接模拟了,很幸运的过了test,然后得了308.22分,我以为这次可以得400多分了,结果还不错,毕竟第一次做,还在250的题目上浪费了这么多。

结果,接下来的Challenge就让我郁闷了,居然500的题目被Cha了。。。

结果最后只有112.06分,排在700多名,没关系,毕竟第一次,下次加油了!

还有,要多熟悉以下C++标准库了!

刚看了以下rate,是934.绿色名字了,估计下次就会直线下降的。。。。

PS:睡觉了。。。已经凌晨3点多了。。。眼睛开始发花=。=