SRM149

SRM 149

DIV2 1000pt

题意：

　　对于n个人，第i人有pi的钱。将他们分成不超过四个组，每组统一交费x，对每个人，若他拥有的钱超过x则交费，否则不交费。问最多能使这些人交多少钱。

　　1<= n <= 50，0 <= pi <= 1000。

tag:greedy，think

解法：枚举所有分组情况，每组交费x为该组中最小的pi。如果分组不足四组，补足四组，每组均含一个人钱数为0的人。

Ps：感觉自己的代码写得比题解舒服.....

 1 #line 7 "Pricing.cpp"
 2 #include <cstdlib>
 3 #include <cctype>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <vector>
 9 #include <iostream>
10 #include <sstream>
11 #include <set>
12 #include <queue>
13 #include <fstream>
14 #include <numeric>
15 #include <iomanip>
16 #include <bitset>
17 #include <list>
18 #include <stdexcept>
19 #include <functional>
20 #include <string>
21 #include <utility>
22 #include <map>
23 #include <ctime>
24 #include <stack>
25 
26 using namespace std;
27 
28 #define CLR(x) memset(x, 0, sizeof(x))
29 #define PB push_back
30 #define SZ(v) ((int)(v).size())
31 #define out(x) cout<<#x<<":"<<(x)<<endl
32 #define tst(a) cout<<#a<<endl
33 #define CINBEQUICKER std::ios::sync_with_stdio(false)
34 
35 typedef vector<int> VI;
36 typedef vector<string> VS;
37 typedef vector<double> VD;
38 typedef long long int64;
39 
40 const double eps = 1e-8;
41 const double PI = atan(1.0)*4;
42 const int maxint = 2139062143;
43 
44 inline int MyMod( int a , int b ) { return (a%b+b)%b;}
45 
46 int n, ans;
47 
48 bool cmp(int x, int y)
49 {
50     return x > y;
51 }
52 
53 class Pricing
54 {
55     public:
56         int maxSales(vector <int> p){
57             p.PB(0), p.PB(0), p.PB(0);
58             n = SZ (p);
59             if (!n) return 0;
60             ans = 0;
61             sort (p.begin(), p.end(), cmp);
62 
63             for (int i = 0; i < n; ++ i)
64                 for (int j = i+1; j < n; ++ j)
65                     for (int k = j+1; k < n; ++ k)
66                         for (int a = k+1; a < n; ++ a){
67                             int tmp = 0;
68                             tmp = p[i] * (i+1) + p[j] * (j-i);
69                             tmp += p[k] * (k-j) + p[a] * (a-k);
70                             ans = max (ans, tmp);
71                         }
72                     
73             return (ans);
74         }
75         //by plum rain
76 };

View Code

DIV1 500pt

题意：

　　字符串匹配。给出字典和一个字符串，询问该字符串是否能用字典里的单词表示，有一种表示方法还是多种表示方法，如果只有一种，输出表示方法。

tag:dp

Ps:以后写dp一定要提前写好状态转移方程- -，错了好多次- -。还有，此题要用long long。

 1 #line 7 "MessageMess.cpp"
 2 #include <cstdlib>
 3 #include <cctype>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <vector>
 9 #include <iostream>
10 #include <sstream>
11 #include <set>
12 #include <queue>
13 #include <fstream>
14 #include <numeric>
15 #include <iomanip>
16 #include <bitset>
17 #include <list>
18 #include <stdexcept>
19 #include <functional>
20 #include <string>
21 #include <utility>
22 #include <map>
23 #include <ctime>
24 #include <stack>
25 
26 using namespace std;
27 
28 #define CLR(x) memset(x, 0, sizeof(x))
29 #define PB push_back
30 #define SZ(v) ((int)(v).size())
31 #define out(x) cout<<#x<<":"<<(x)<<endl
32 #define tst(a) cout<<#a<<endl
33 #define CINBEQUICKER std::ios::sync_with_stdio(false)
34 
35 typedef vector<int> VI;
36 typedef vector<string> VS;
37 typedef vector<double> VD;
38 typedef long long int64;
39 
40 const double eps = 1e-8;
41 const double PI = atan(1.0)*4;
42 const int maxint = 2139062143;
43 const int N = 55;
44 
45 inline int MyMod( int a , int b ) { return (a%b+b)%b;}
46 
47 int64 dp[N], pat[N];
48 
49 class MessageMess
50 {
51     public:
52         string restore(vector <string> d, string s){
53             CLR (dp), CLR (pat);
54             int m = SZ (d), n = SZ (s);
55             for (int i = 0; i < n; ++ i){
56                 for (int j = 0; j < m; ++ j){
57                     int size = SZ (d[j]);
58                     int pos = i - size;
59                     if (pos < -1) continue;
60                     string tmp(s, pos+1, size);
61                     if (tmp == d[j]){
62                         if (pos == -1) 
63                             dp[i] += 1, pat[i] = j;
64                         else if (dp[pos] > 0)
65                             dp[i] += dp[pos], pat[i] = j;
66                     }
67                 }
68             }
69 
70             if (!dp[n-1]) return "IMPOSSIBLE!";
71             if (dp[n-1] != 1) return "AMBIGUOUS!";
72             VS ans; ans.clear();
73             int pos = n - 1;
74             while (pos >= 0){
75                 int num = pat[pos];
76                 ans.PB(d[num]);
77                 pos -= SZ (d[num]);
78             }
79             int len = SZ (ans);
80             string ret; ret.clear();
81             ret += ans[len-1];
82             for (int i = len-2; i >= 0; -- i)
83                 ret += " " + ans[i];  
84             return (ret);
85         }
86         
87 //by plum rain
88 };

View Code

DIV1 1000pt

题意：

　　在平面坐标系XOY中，以xi严格递增的顺序给出一些点的坐标(xi, yi)，然后将点(xi, yi)与(x[i+1], y[i+1])连接，得到一条折线。给定整数p，求在这条折线上的某一线段，起点终点分别为(a, b), (a+p, b')，使这一线段平均y值最大，输出最大的平均y值。

　　x, y范围[0, 10000]。

tag:think, (三分法), good

解法：

　　没做出来。官方题解提供了两种方法，第一种方法似乎要用三分法，还不太懂- -。

　　第二种方法是，考虑线段(a, b)——(a+p, b')在折线上移动，记该线段的平均y值为tmp。该线段从原位置移动到(a+1, c)和(a+p+1, c')，则tmp' = tmp - (f(a+1) + f(a)) / 2 + (f(a+p+1) + f(a+p)) / 2), ans = max (tmp, ans)(其中，f(a)表示折线段的在x = a时的y值，ans表示答案)。

　　然后考虑到线段(a, b)——(a+1, c)和线段(a+p, b')——(a+p+1, c')的斜率可能不同，所以答案线段也有可能出现在移动途中。记两线段y值相等的点为(x1, y0) 和 (x2, y0), 则ans = max (ans, tmp' + ((y0 + c) / 2)* (a+1 - x1) - ((y0 + c') / 2) * (a+p+1 - x2))。

PS：

　　返回double类型的要注意精度，并且，如果你使用topcoder的插件，在你自己的电脑上判断答案对错时，有可能因为精度问题而将你的正确答案判为错，输出一下返回值看一下是否正确就行。

 1 /*
 2  * Author:  plum rain
 3  */
 4 #line 11 "topcoder.cpp"
 5 #include <cstdlib>
 6 #include <cctype>
 7 #include <cstring>
 8 #include <cstdio>
 9 #include <cmath>
10 #include <algorithm>
11 #include <vector>
12 #include <iostream>
13 #include <sstream>
14 #include <set>
15 #include <queue>
16 #include <fstream>
17 #include <numeric>
18 #include <iomanip>
19 #include <bitset>
20 #include <list>
21 #include <stdexcept>
22 #include <functional>
23 #include <string>
24 #include <utility>
25 #include <map>
26 #include <ctime>
27 #include <stack>
28 
29 using namespace std;
30 
31 #define CLR(x) memset(x, 0, sizeof(x))
32 #define PB push_back
33 #define SZ(v) ((int)(v).size())
34 #define out(x) cout<<#x<<":"<<(x)<<endl
35 #define tst(a) cout<<#a<<endl
36 #define CINBEQUICKER std::ios::sync_with_stdio(false)
37 
38 typedef vector<int> VI;
39 typedef vector<string> VS;
40 typedef vector<double> VD;
41 typedef long long int64;
42 
43 const double eps = 1e-12;
44 const double PI = atan(1.0)*4;
45 const int maxint = 2139062143;
46 
47 inline int MyMod( int a , int b ) {a = a % b;if (a < 0) a += b; return a;}
48 
49 class GForce
50 {
51     public:
52         double avgAccel(int p, vector <int> a, vector <int> t){
53             int n = SZ (a);
54             VD spd;
55             spd.clear();
56             for (int i = 0; i < n-1; ++ i){
57                 spd.PB(a[i] + 0.0); 
58                 double now = a[i] + 0.0;
59                 double cnt = (a[i+1] - a[i] + eps) / (t[i+1] - t[i] + eps);
60                 for (int j = t[i] + 1; j < t[i+1]; ++ j)
61                     now += cnt, spd.PB (now);
62             }
63             spd.PB (a[n-1]);
64 
65             double tmp = 0.0;
66             for (int i = 0; i < p; ++ i)
67                 tmp += (spd[i] + spd[i+1]) / 2.0;
68             double ans = tmp;
69             for (int i = 1; i < spd.size() - p; ++ i){  
70                 tmp -= (spd[i] + spd[i-1]) / 2.0;
71                 tmp += (spd[i+p] + spd[i+p-1]) / 2.0;
72                 ans = max (ans, tmp);
73                 
74                 double del = (spd[i] + spd[i-1]) / 2.0;
75                 double add = (spd[i+p] + spd[i+p-1]) / 2.0;
76                 double haf = tmp + (3*spd[i]/8.0 + spd[i-1] / 8.0) - (3*spd[i+p]/8.0 + spd[i+p-1]/8.0);
77                 ans = max (ans, haf);
78                 if(fabs(del - add) > eps){
79                     del = (spd[i] - spd[i-1]) / 2.0;
80                     add = (spd[i+p] - spd[i+p-1]) / 2.0;
81                     double x = ((spd[i] - spd[i+p]) / 2.0) / (del - add);
82                     if (x > eps && x < 1- eps){
83                         double y = ((spd[i]*spd[i+p-1] - spd[i+p]*spd[i-1]) / 2.0) / (del - add);
84                         double xy = tmp + (spd[i] + y) * x / 2.0 - (y + spd[i+p]) * x / 2.0;
85                         ans = max (ans, xy);
86                     }
87                 }
88             }
89 
90             double ret = ans / (p + 0.0);
91             return (ret);
92         }
93 };

View Code

SRM 150

DIV2 1100pt

题意：有一个有限大小的平面和一个球，平面上有两种障碍物，第一种障碍物被球撞后会消失，第二种不会。球撞两种障碍物均会反弹，速度不变。给出平面大小和障碍物分布，问球从左上角一某一初速度开始，需要多少时间能让平面上的第一类障碍物全部消失。

解法：模拟。

tag: simulate

  1 #line 10 "BrickByBrick.cpp"
  2 #include <cstdlib>
  3 #include <cctype>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <algorithm>
  8 #include <vector>
  9 #include <iostream>
 10 #include <sstream>
 11 #include <set>
 12 #include <queue>
 13 #include <fstream>
 14 #include <numeric>
 15 #include <iomanip>
 16 #include <bitset>
 17 #include <list>
 18 #include <stdexcept>
 19 #include <functional>
 20 #include <string>
 21 #include <utility>
 22 #include <map>
 23 #include <ctime>
 24 #include <stack>
 25 
 26 using namespace std;
 27 
 28 #define CLR(x) memset(x, 0, sizeof(x))
 29 #define PB push_back
 30 #define SZ(v) ((int)(v).size())
 31 #define out(x) cout<<#x<<":"<<(x)<<endl
 32 #define tst(a) cout<<#a<<endl
 33 #define CINBEQUICKER std::ios::sync_with_stdio(false)
 34 
 35 typedef vector<int> VI;
 36 typedef vector<string> VS;
 37 typedef vector<double> VD;
 38 typedef long long int64;
 39 
 40 const double eps = 1e-8;
 41 const double PI = atan(1.0)*4;
 42 const int maxint = 2139062143;
 43 
 44 inline int MyMod( int a , int b ) {a = a % b;if (a < 0) a += b; return a;}
 45 
 46 //drt
 47 //1 0 2
 48 //0 0 0
 49 //3 0 4
 50 struct STA{
 51     int x, y;
 52     int drt;
 53     int time;
 54     void clr(){
 55         x = 1; y = 0; time = 0;
 56     }
 57 };
 58 
 59 int an[150][150];
 60 int xmax, ymax, tot;
 61 int ans;
 62 
 63 inline int change(char x)
 64 {
 65     if (x == '.') return 0;
 66     if (x == 'B'){
 67         ++ tot;
 68         return 1;
 69     }
 70     if (x == '#') return 2;
 71 }
 72 
 73 void init(VS m)
 74 {
 75     CLR (an);
 76     tot = 0;
 77     ymax = SZ (m);
 78     for (int i = 0; i < ymax; ++ i){
 79         string s = m[i];
 80         xmax = SZ (s);
 81         for (int j = 0; j < xmax; ++ j)
 82             an[2*i+1][2*j+1] = change(s[j]);
 83     }
 84 }
 85 
 86 void move(int& x, int& y, int d, int& t)
 87 {
 88     ++ t;
 89     if (d == 1) -- x, -- y;
 90     if (d == 2) ++ x, -- y;
 91     if (d == 3) -- x, ++ y;
 92     if (d == 4) ++ x, ++ y;
 93 }
 94 
 95 void D(int& x, int& y, int& d)
 96 {
 97     if (!(x & 1)){
 98         if (d & 1) 
 99             -- x, d = (d == 1 ? 2 : 4);
100         else 
101             ++ x, d = (d == 2 ? 1 : 3);
102         return ;
103     }
104     if (d < 3) -- y, d = (d == 1 ? 3 : 4);
105     else ++ y, d = (d == 3 ? 1 : 2);
106 }
107 
108 int solve()
109 {
110     STA sta; sta.clr();
111     sta.drt = 4;
112     int num = 0;
113     while (sta.time < 1000000 && sta.time < ans){
114         move(sta.x, sta.y, sta.drt, sta.time);   
115         
116         int x = sta.x, y = sta.y;
117         int dtmp = sta.drt;
118         D(x, y, sta.drt);
119         if (x >= 0 && x <= 2*xmax && y >= 0 && y <= 2*ymax){
120             if (an[y][x] == 0) sta.drt = dtmp;
121             if (an[y][x] == 1) an[y][x] = 0, ++ num;
122         }
123         if (num == tot){
124             return sta.time;
125         }
126     }
127     return -1;
128 }
129 
130 class BrickByBrick
131 {
132     public:
133         int timeToClear(vector <string> m){
134             init (m);
135 
136             ans = maxint;
137 
138             return (solve());
139         }
140 };

View Code

DIV1 500pt

题意：给一个用‘A’-‘Z’表示颜色的字符串s，要求将一空白字符串变成给定字符串，（每次变化能将任意个连续位置的字符均变为某个任意的字符）问最少变化多少次。比如给定ABGBA，第一次将空白字符串变为AAAAA，第二次变为ABBBA，第三次变为ABGBA，答案为3。(s.size() <= 50)

解法：设置数组，m[][][]。left位置到left+size-1位置此时颜色均为c，将他们变化为给定字符串对应部分所需要最少的变化次数为m[left][size][c]。

　　　状态转移方程：m[][0][] = 0,

　　　　　　　　　　if (color == s[l]) m[left][size][c] = m[left+1][size-1][color];

　　　　　　　　　　else m[left][size][color] = min {1 + m[left][i][color] + m[left+i][size-i][k] | 0 < i <= size, 'A' <= k <= 'Z'}

　　　由于要用到记忆化搜索的思想，我又想写成DP，所以感觉写成了四不像- -

tag:dp, memoization, good

 1 #line 10 "StripePainter.cpp"
 2 #include <cstdlib>
 3 #include <cctype>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <vector>
 9 #include <iostream>
10 #include <sstream>
11 #include <set>
12 #include <queue>
13 #include <fstream>
14 #include <numeric>
15 #include <iomanip>
16 #include <bitset>
17 #include <list>
18 #include <stdexcept>
19 #include <functional>
20 #include <string>
21 #include <utility>
22 #include <map>
23 #include <ctime>
24 #include <stack>
25 
26 using namespace std;
27 
28 #define CLR(x) memset(x, 0, sizeof(x))
29 #define PB push_back
30 #define SZ(v) ((int)(v).size())
31 #define out(x) cout<<#x<<":"<<(x)<<endl
32 #define tst(a) cout<<#a<<endl
33 #define CINBEQUICKER std::ios::sync_with_stdio(false)
34 
35 typedef vector<int> VI;
36 typedef vector<string> VS;
37 typedef vector<double> VD;
38 typedef long long int64;
39 
40 const double eps = 1e-8;
41 const double PI = atan(1.0)*4;
42 const int maxint = 2139062143;
43 
44 inline int MyMod( int a , int b ) {a = a % b;if (a < 0) a += b; return a;}
45 
46 string s;
47 int m[55][55][100];
48 
49 int ask(int l, int n, char c)
50 {
51     int& a = m[l][n][(int)c];
52 
53     if (!n) return 0;
54 
55     if (a != -1) return a;
56     a = maxint;
57 
58     if (c == s[l]){ 
59         a = ask (l+1, n-1, c);
60         return a;
61     }
62 
63     for (int i = 1; i < n; ++ i)
64         for (int j = 'A'; j <= 'Z'; ++ j)
65             a = min (a, 1 + ask(l, i, s[l]) + ask(l+i, n-i, c));
66     a = min (a, 1 + ask(l, n, s[l]));
67     return a;
68 }
69 
70 class StripePainter
71 {
72     public:
73         int minStrokes(string stripes){
74             s.clear();
75             s = stripes;
76             memset (m, -1, sizeof (m));
77 
78             int size = SZ (s);
79             for (int i = 0; i < size; ++ i)
80                 for (int j = 0; j + i <= size; ++ j)
81                     for (int k = 'A'-1; k <= 'Z'; ++ k)
82                         m[i][j][k] = 1 + ask(i, j, (char)k); 
83 
84             return (m[0][size][(int)s[0]]);
85         }
86 };

View Code

------------------------------------------------------------------
现在的你，在干什么呢？
你是不是还记得，你说你想成为岩哥那样的人。