SRM468

SRM 468

DIV1 250pt

题意：给出字典，按照一定要求进行查找。

解法：模拟题，暴力即可。

tag:water

score: 0....

这是第一次AC的代码：

  1 /*
  2  * Author:  plum rain
  3  * score :  0
  4  */
  5 #line 11 "T9.cpp"
  6 #include <sstream>
  7 #include <stdexcept>
  8 #include <functional>
  9 #include <iomanip>
 10 #include <numeric>
 11 #include <fstream>
 12 #include <cctype>
 13 #include <iostream>
 14 #include <cstdio>
 15 #include <vector>
 16 #include <cstring>
 17 #include <cmath>
 18 #include <algorithm>
 19 #include <map>
 20 
 21 using namespace std;
 22 
 23 #define CLR(x) memset(x, 0, sizeof(x))
 24 #define PB push_back
 25 #define SZ(v) ((int)(v).size())
 26 #define out(x) cout<<#x<<":"<<(x)<<endl
 27 #define tst(a) cout<<#a<<endl
 28 
 29 typedef vector<string> VS;
 30 
 31 map<char, int> mp;
 32 
 33 class T9
 34 {
 35     public:
 36         string message(vector <string> part, vector <string> dict, vector <string> ke){
 37             int size = SZ (part);
 38             for (int i = 0; i < size; ++ i)
 39                 for (int j = 0; j < SZ(part[i]); ++ j)
 40                     mp[part[i][j]] = i+1;   
 41 
 42             VS dic; dic.clear();
 43             size = SZ (dict);
 44             for (int i = 0; i < size; ++ i){
 45                 string s; s.clear();
 46                 int n = SZ (dict[i]);
 47                 for (int j = 0; j < n; ++ j)
 48                     s.PB (mp[dict[i][j]] + '0');
 49                 dic.PB (s);
 50             }
 51 
 52             for (int i = 0; i < size; ++ i)
 53                 for (int j = 0; j < size-1-i; ++ j){
 54                     bool ok = false;
 55                     if (dic[j] < dic[j+1]) ok = true;
 56                     if (dic[j] == dic[j+1] && dict[j] > dict[j+1])
 57                         ok = true;
 58                     if (ok){
 59                         swap (dic[j], dic[j+1]);
 60                         swap (dict[j], dict[j+1]);
 61                     }
 62                 }
 63 
 64 
 65             string ans; ans.clear();
 66             size = SZ (ke);
 67             string s; s.clear();
 68             for (int i = 0; i < size; ++ i)
 69                 s += ke[i];
 70             size = SZ (s);
 71             string tmp; tmp.clear();
 72             int cnt = 0;
 73             for (int i = 0; i < size; ++ i){
 74                 if (s[i] == '*') cnt += 5;
 75                 if (s[i] == '#') ++ cnt;
 76                 if (s[i] >= '1' && s[i] <= '9') tmp.PB(s[i]);
 77                 if (s[i] == '0'){
 78                     if (tmp.empty() && !cnt){
 79                         ans.PB (' ');
 80                         continue;
 81                     }
 82                     int pos;
 83                     for (int j = 0; j < SZ (dic); ++ j)
 84                         if (dic[j] == tmp){
 85                             pos = j;
 86                             break;
 87                         }
 88                     pos = pos + cnt;
 89                     ans = ans + dict[pos];
 90                     cnt = 0; tmp.clear();
 91                     ans.PB (' ');
 92                 }
 93             }
 94             if (tmp.empty() && !cnt) return ans;
 95             int pos;
 96             for (int i = 0; i < SZ (dic); ++ i)
 97                 if (dic[i] == tmp){
 98                     pos = i;
 99                     break;
100                 }
101             pos = pos + cnt;
102             ans = ans + dict[pos];
103             return ans;
104         }
105 };

View Code

这是后来改进的代码：

 1 /*
 2  * Author:  plum rain
 3  * score :  0
 4  */
 5 #line 11 "T9.cpp"
 6 #include <sstream>
 7 #include <stdexcept>
 8 #include <functional>
 9 #include <iomanip>
10 #include <numeric>
11 #include <fstream>
12 #include <cctype>
13 #include <iostream>
14 #include <cstdio>
15 #include <vector>
16 #include <cstring>
17 #include <cmath>
18 #include <algorithm>
19 #include <utility>
20 #include <map>
21 
22 using namespace std;
23 
24 #define CLR(x) memset(x, 0, sizeof(x))
25 #define PB push_back
26 #define SZ(v) ((int)(v).size())
27 #define out(x) cout<<#x<<":"<<(x)<<endl
28 #define tst(a) cout<<#a<<endl
29 
30 typedef vector<string> VS;
31 
32 map<char, int> mp;
33 
34 bool cmp(pair<string, string> a, pair<string, string> b)
35 {
36     if (a.first < b.first) return true;
37     if (a.first == b.first && a.second < b.second) return true;
38     return false;
39 }
40 
41 class T9
42 {
43     public:
44         string message(vector <string> part, vector <string> dict, vector <string> ke){
45             int size = SZ (part);
46             mp.clear();
47             for (int i = 0; i < size; ++ i)
48                 for (int j = 0; j < SZ(part[i]); ++ j)
49                     mp[part[i][j]] = i+1;   
50 
51             vector<pair<string, string> > D; D.clear();
52             size = SZ (dict);
53             for (int i = 0; i < size; ++ i){
54                 string s; s.clear();
55                 int n = SZ (dict[i]);
56                 for (int j = 0; j < n; ++ j)
57                     s.PB (mp[dict[i][j]] + '0');
58                 D.PB (make_pair(s, dict[i]));
59             }
60             sort (D.begin(), D.end(), cmp);
61 
62             size = SZ (ke);
63             string s; s.clear();
64             for (int i = 0; i < size; ++ i)
65                 s += ke[i];
66             s.PB ('0');
67             size = SZ (s);
68 
69             string tmp; tmp.clear();
70             string ans; ans.clear();
71             int cnt = 0;
72             for (int i = 0; i < size; ++ i){
73                 if (s[i] == '*') cnt += 5;
74                 if (s[i] == '#') ++ cnt;
75                 if (s[i] >= '1' && s[i] <= '9') tmp.PB(s[i]);
76                 if (s[i] == '0'){
77                     if (tmp.empty() && !cnt){
78                         if (i != (size-1))
79                             ans.PB (' ');
80                         continue;
81                     }
82                     int pos;
83                     for (int j = 0; j < SZ (D); ++ j)
84                         if (D[j].first == tmp){
85                             pos = j;
86                             break;
87                         }
88                     pos = pos + cnt;
89                     ans = ans + D[pos].second;
90                     cnt = 0; tmp.clear();
91                     if (i != (size-1))
92                         ans.PB (' ');
93                 }
94             }            
95             return ans;
96         }
97 };
98

View Code

SRM 469

DIV1 250pt

题意：给定n * m的网格中，其中有若干点不能被选择，然后从其他点中选出同行且相邻的两点，问有多少种选择方法？(1 <= n,m <= 10^8)

解法：水题

score: 129.09

tag: math, counting

 1 /*
 2  * Author:  plum rain
 3  * score:   129.09
 4  */
 5 #line 10 "TheMoviesLevelOneDivOne.cpp"
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <sstream>
 9 #include <cstring>
10 #include <algorithm>
11 #include <vector>
12 
13 using namespace std;
14 
15 #define CLR(x) memset(x, 0, sizeof(x))
16 #define SZ(v) ((int)(v).size())
17 #define out(x) cout<<#x<<":"<<(x)<<endl
18 #define tst(a) cout<<#a<<endl
19 
20 typedef long long int64;
21 
22 struct pos{
23     int x, y;
24 };
25 
26 pos a[50];
27 
28 bool cmp(pos a, pos b)
29 {
30     if (a.x < b.x)
31         return true;
32     if (a.x == b.x && a.y < b.y)
33         return true;
34     return false;
35 }
36 
37 int64 gao(int64 size, int64 n, int64 m)
38 {
39     int i = 1;
40     int64 tmp = a[0].x, dif = 0;
41     if (a[0].y == 1) dif = 1;
42     if (a[0].y >= 2) dif = 2;
43     while (i < size){
44         if (tmp == a[i].x){ 
45             if (a[i-1].y == a[i].y-1) ++ dif;
46             else dif += 2;
47             ++ i;
48             continue;
49         }
50         
51         if (a[i-1].y == m) -- dif;
52         if (a[i].y == 1) ++ dif;
53         if (a[i].y >= 2) dif += 2;
54         tmp = a[i].x;
55         ++ i;
56     }
57     if (a[i-1].y == m) -- dif;
58 
59     return n * (m-1) - dif;
60 }
61 
62 class TheMoviesLevelOneDivOne
63 {
64     public:
65         long long find(int n, int m, vector <int> row, vector <int> seat){
66             CLR (a);
67             int size = SZ (row);            
68             for (int i = 0; i < size; ++ i)
69                 a[i].x = row[i], a[i].y = seat[i];
70             sort (a, a+size, cmp);
71 
72             return (gao(size, n, m));
73         }
74 };

View Code

DIV1 500pt

题意：一个人看电影，该人有一个scare值，并且没看1min电影scare减1。有很多部恐怖电影，每部电影长度不同(length[i])，且每部都有一个瞬间增加scare(s[i])值的时刻。如果scare值小于0，则这个人就会睡着，不能再看电影。请问他安排一个电影观看顺序，使得他能看尽可能多的电影。如果有多组观看顺序看到的电影数相同，则输出字典序最小的。(电影数量小等于20)

解法：如果这道题不要求输出字典序最小的，而是随便输出一组，那就是一道很简单的贪心题。- -

　　　状压DP。假设有n部电影，用opt来表示所有电影是否排进观影序列(1为该电影未进入观影序列)，用num[opt]表示观影序列为opt时所能看的电影数量的最大值，用scare表示观影序列为opt时看完观影序列上的电影后的scare值。则状态转移方程为：

　　　if (opt & (1<<i) && scare >= s[i] && scare >= length[i] - 47) num[opt] = 1 + num[opt - (1<<i)]，for i = 0 to n-1。注意还要记录路径。

score: 0

tag:DP, good

 1 /*
 2  * Author:  plum rain
 3  * score :  0
 4  */
 5 #line 10 "TheMoviesLevelTwoDivOne.cpp"
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <sstream>
 9 #include <cstring>
10 #include <algorithm>
11 #include <vector>
12 
13 using namespace std;
14 
15 #define CLR(x) memset(x, 0, sizeof(x))
16 #define PB push_back
17 #define SZ(v) ((int)(v).size())
18 #define out(x) cout<<#x<<":"<<(x)<<endl
19 #define tst(a) cout<<#a<<endl
20 
21 typedef vector<int> VI;
22 
23 const int N = 20;
24 int n;
25 vector<pair<int, int> > a;
26 int num[1<<N], fir[1<<N];
27 
28 VI DP()
29 { 
30     CLR (num); CLR (fir);
31     for (int opt = 1; opt < (1<<n); ++ opt){
32         int flag, tmp = -1;
33         int sca = 74;
34         for (int i = 0; i < n; ++ i)
35             if (!(opt & (1<<i))) sca += 47 - a[i].first;
36 
37         for (int i = 0; i < n; ++ i) if (opt & (1<<i)){
38             int x = 0;
39             if (sca >= a[i].second && sca >= (a[i].first - 47))
40                 x = 1 + num[opt-(1<<i)];
41             if (x > tmp)
42                 tmp = x, flag = i;
43         }
44 
45         num[opt] = tmp;
46         fir[opt] = flag;
47     }
48 
49     int opt = (1<<n) - 1;
50     VI ret; ret.clear();
51     while (opt > 0){
52         ret.PB (fir[opt]);
53         opt -= (1<<fir[opt]);
54     }
55     return ret;
56 }
57 
58 class TheMoviesLevelTwoDivOne
59 {
60     public:
61         vector <int> find(vector <int> ls, vector <int> sc){
62             n = SZ (ls);
63             a.clear();
64             for (int i = 0; i < n; ++ i)
65                 a.PB(make_pair(ls[i], sc[i]));
66 
67             return (DP());
68         }
69 };

View Code

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