Problem A Guess a number!
这道题比较容易错注意最小值一定小于-1e9，最大值大于1e9
代码如下:
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-04-13 15:56 5 * Filename : Codeforce_241_2_E.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 34 int main() 35 { 36 freopen("in.txt", "r", stdin); 37 38 int n, x, l, r; 39 string op, c; 40 while(cin >> n){ 41 l = -INF; 42 r = INF; 43 for(int i=0; i<n; i++){ 44 cin >> op >> x >> c; 45 if(c == "Y"){ 46 if(op == "<"){ 47 r = min(r, x-1); 48 }else if(op == "<="){ 49 r = min(r, x); 50 }else if(op == ">"){ 51 l = max(l, x+1); 52 }else{ 53 l = max(l, x); 54 } 55 }else{ 56 if(op == "<"){ 57 l = max(l, x); 58 }else if(op == "<="){ 59 l = max(l, x+1); 60 }else if(op == ">"){ 61 r = min(r, x); 62 }else{ 63 r = min(r, x-1); 64 } 65 } 66 } 67 if(l > r) cout << "Impossible" << endl; 68 else cout << (l+r)/2 << endl; 69 } 70 return 0; 71 }
Problem B Art Union
递推一下即可sum[i][j] = max(sum[i-1][j], sum[i][j-1])+a[i][j];
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-04-13 15:56 5 * Filename : Codeforce_241_2_B.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 int a[50000+10][10], sum[50000+10][10]; 34 int n, m; 35 36 void debug(){ 37 for(int i=0; i<=n; i++){ 38 for(int j=0; j<=m; j++){ 39 cout << sum[i][j] << ' '; 40 }cout << endl; 41 }cout << endl; 42 } 43 44 int main() 45 { 46 // freopen("in.txt", "r", stdin); 47 48 while(cin >> n >> m){ 49 memset(a, 0, sizeof a); 50 memset(sum, 0, sizeof sum); 51 for(int i=1; i<=n; i++) 52 for(int j=1; j<=m; j++) 53 cin >> a[i][j]; 54 for(int i=1; i<=m; i++) sum[1][i] = sum[1][i-1] + a[1][i]; 55 for(int i=1; i<=n; i++) sum[i][1] = sum[i-1][1] + a[i][1]; 56 for(int i=2; i<=n; i++){ 57 for(int j=2; j<=m; j++){ 58 sum[i][j] = max(sum[i-1][j], sum[i][j-1])+a[i][j]; 59 } 60 } 61 for(int i=1; i<=n; i++){ 62 cout << sum[i][m] << ' '; 63 } 64 cout << endl; 65 } 66 return 0; 67 }
Problem C Booking System
贪心尽量让小的桌子坐下钱多的人就可以了。
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-04-13 15:56 5 * Filename : Codeforce_241_2_C.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 1010; 34 struct P{ 35 int a, b, num; 36 }p[LEN]; 37 struct D{ 38 int a, num; 39 }d[LEN]; 40 41 bool cmp(P a, P b){ 42 if(a.a != b.a)return a.b > b.b; 43 else return a.a < b.a; 44 } 45 46 bool cmp2(D a, D b){ 47 return a.a < b.a; 48 } 49 50 int main() 51 { 52 // freopen("in.txt", "r", stdin); 53 54 int n, m; 55 while(cin >> n){ 56 for(int i=0; i<n; i++){ 57 cin >> p[i].a >> p[i].b; 58 p[i].num = i; 59 } 60 cin >> m; 61 for(int i=0; i<m; i++){ 62 cin >> d[i].a; 63 d[i].num = i; 64 } 65 sort(d, d+m,cmp2); 66 sort(p, p+n, cmp); 67 int ans = 0, cnt = 0, f[LEN]; 68 memset(f, -1, sizeof f); 69 for(int i=0; i<m; i++){ 70 int tmp = -1; 71 for(int j=0; j<n; j++){ 72 if(f[j] >= 0) continue; 73 if(d[i].a >= p[j].a && (tmp == -1 || p[j].b > p[tmp].b)){ 74 tmp = j; 75 } 76 } 77 if(tmp == -1) continue; 78 cnt ++; 79 f[tmp] = d[i].num; 80 ans += p[tmp].b; 81 } 82 cout << cnt << ' ' << ans << endl; 83 for(int i=0; i<n; i++){ 84 if(f[i] >= 0){ 85 cout << p[i].num+1 << ' ' << f[i]+1 << endl; 86 } 87 } 88 } 89 return 0; 90 }