A
无trick水题。。。
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-12-24 22:26 4 * File Name: B.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <string> 10 #include <cmath> 11 #include <algorithm> 12 #include <vector> 13 #include <cstdlib> 14 #include <sstream> 15 #include <fstream> 16 #include <list> 17 #include <deque> 18 #include <queue> 19 #include <stack> 20 #include <map> 21 #include <set> 22 #include <bitset> 23 #include <cctype> 24 #include <ctime> 25 #include <utility> 26 27 using namespace std; 28 29 #define clr0(x) memset(x, 0, sizeof(x)) 30 #define clr1(x) memset(x, -1, sizeof(x)) 31 #define pb push_back 32 #define sz(v) ((int)(v).size()) 33 #define all(t) t.begin(),t.end() 34 #define INF 999999999999999999 35 #define zero(x) (((x)>0?(x):-(x))<eps) 36 #define out(x) cout<<#x<<":"<<(x)<<endl 37 #define tst(a) cout<<a<<" " 38 #define tst1(a) cout<<#a<<endl 39 #define CINBEQUICKER std::ios::sync_with_stdio(false) 40 41 const double eps = 1e-8; 42 const double PI = atan(1.0)*4; 43 const int inf = 2147483647 / 2; 44 45 typedef vector<int> vi; 46 typedef vector<string> vs; 47 typedef vector<double> vd; 48 typedef pair<int, int> pii; 49 typedef long long int64; 50 51 inline int Mymod (int a, int b) {int x=a%b; if(x<0) x+=b; return x;} 52 53 int ru[105], chu[105]; 54 55 int main() 56 { 57 // freopen("a.in","r",stdin); 58 // freopen("a.out","w",stdout); 59 // std::ios::sync_with_stdio(false); 60 int n, m; 61 while (scanf ("%d%d", &n , &m) != EOF){ 62 int t1, t2, w; 63 clr0 (chu); clr0 (ru); 64 for (int i = 0; i < m; ++ i){ 65 scanf ("%d%d%d", &t1, &t2, &w); 66 chu[--t1] += w; 67 ru[--t2] += w; 68 } 69 int ans = 0; 70 for (int i = 0; i < n; ++ i) 71 ans += abs(chu[i] - ru[i]); 72 printf ("%d ", ans / 2); 73 } 74 return 0; 75 }
B
YY题。。。结论直接看代码就好了。。。比赛的时候YY出了结论算样例算错了，然后就去想别的方法了。。。。。。
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-12-24 22:26 4 * File Name: B.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <string> 10 #include <cmath> 11 #include <algorithm> 12 #include <vector> 13 #include <cstdlib> 14 #include <sstream> 15 #include <fstream> 16 #include <list> 17 #include <deque> 18 #include <queue> 19 #include <stack> 20 #include <map> 21 #include <set> 22 #include <bitset> 23 #include <cctype> 24 #include <ctime> 25 #include <utility> 26 27 using namespace std; 28 29 #define clr0(x) memset(x, 0, sizeof(x)) 30 #define clr1(x) memset(x, -1, sizeof(x)) 31 #define pb push_back 32 #define sz(v) ((int)(v).size()) 33 #define all(t) t.begin(),t.end() 34 #define INF 999999999999999999 35 #define zero(x) (((x)>0?(x):-(x))<eps) 36 #define out(x) cout<<#x<<":"<<(x)<<endl 37 #define tst(a) cout<<a<<" " 38 #define tst1(a) cout<<#a<<endl 39 #define CINBEQUICKER std::ios::sync_with_stdio(false) 40 41 const double eps = 1e-8; 42 const double PI = atan(1.0)*4; 43 const int inf = 2147483647 / 2; 44 45 typedef vector<int> vi; 46 typedef vector<string> vs; 47 typedef vector<double> vd; 48 typedef pair<int, int> pii; 49 typedef long long int64; 50 51 inline int Mymod (int a, int b) {int x=a%b; if(x<0) x+=b; return x;} 52 53 int ru[105], chu[105]; 54 55 int main() 56 { 57 // freopen("a.in","r",stdin); 58 // freopen("a.out","w",stdout); 59 // std::ios::sync_with_stdio(false); 60 int n, m; 61 while (scanf ("%d%d", &n , &m) != EOF){ 62 int t1, t2, w; 63 clr0 (chu); clr0 (ru); 64 for (int i = 0; i < m; ++ i){ 65 scanf ("%d%d%d", &t1, &t2, &w); 66 chu[--t1] += w; 67 ru[--t2] += w; 68 } 69 int ans = 0; 70 for (int i = 0; i < n; ++ i) 71 ans += abs(chu[i] - ru[i]); 72 printf ("%d ", ans / 2); 73 } 74 return 0; 75 }
C
题意：给一个很大的数m，这个数的各个位上的数字中一定含有至少1个1,6,8,9。你可以重新组织所有数字的顺序，使得重新排列之后的数能被7整除。10^4 <= m <= 10^(10^6)。
注意，排列之后的数不能含有前导0。
解法：把1,6,8,9四个数字放在最后面，根据前面的数*10000除以7的余数，来决定1,6,8,9四个数字的排列顺序即可。至于有没有前导0，特殊处理一下即可。
tag:math, think
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-12-25 14:09 4 * File Name: C.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <string> 10 #include <cmath> 11 #include <algorithm> 12 #include <vector> 13 #include <cstdlib> 14 #include <sstream> 15 #include <fstream> 16 #include <list> 17 #include <deque> 18 #include <queue> 19 #include <stack> 20 #include <map> 21 #include <set> 22 #include <bitset> 23 #include <cctype> 24 #include <ctime> 25 #include <utility> 26 27 using namespace std; 28 29 #define clr0(x) memset(x, 0, sizeof(x)) 30 #define clr1(x) memset(x, -1, sizeof(x)) 31 #define pb push_back 32 #define sz(v) ((int)(v).size()) 33 #define all(t) t.begin(),t.end() 34 #define INF 999999999999999999 35 #define zero(x) (((x)>0?(x):-(x))<eps) 36 #define out(x) cout<<#x<<":"<<(x)<<endl 37 #define tst(a) cout<<a<<" " 38 #define tst1(a) cout<<#a<<endl 39 #define CINBEQUICKER std::ios::sync_with_stdio(false) 40 41 const double eps = 1e-8; 42 const double PI = atan(1.0)*4; 43 const int inf = 2147483647 / 2; 44 45 typedef vector<int> vi; 46 typedef vector<string> vs; 47 typedef vector<double> vd; 48 typedef pair<int, int> pii; 49 typedef long long int64; 50 51 inline int Mymod (int a, int b) {int x=a%b; if(x<0) x+=b; return x;} 52 53 bool del[4]; 54 string temp = "1689"; 55 map<int, string> mp; 56 57 void gao(string s) 58 { 59 stringstream stm(s); 60 int num; stm >> num; 61 int yu = num % 7; 62 if (!mp.count(yu)) mp[yu] = s; 63 } 64 65 int main() 66 { 67 // freopen("a.in","r",stdin); 68 // freopen("a.out","w",stdout); 69 // std::ios::sync_with_stdio(false); 70 mp.clear(); 71 string tt = "1689"; 72 gao(tt); 73 while (next_permutation(tt.begin(), tt.end())) gao(tt); 74 75 string s; 76 while (cin >> s){ 77 clr0 (del); 78 string ss; ss.clear(); 79 int n = sz(s), cnt = 0; 80 for (int i = 0; i < n; ++ i){ 81 if (s[i] == '0'){ 82 ++ cnt; continue; 83 } 84 bool ok = 0; 85 for (int j = 0; j < 4; ++ j) if (s[i] == temp[j] && !del[j]){ 86 del[j] = 1; ok = 1; 87 } 88 if (!ok) ss.pb (s[i]); 89 } 90 91 int len = sz(ss); 92 if (!len){ 93 ss = mp[0]; 94 for (int i = 0; i < cnt; ++ i) ss.pb ('0'); 95 cout << ss << endl; 96 continue; 97 } 98 for (int i = 0; i < cnt; ++ i) ss.pb ('0'); 99 len = sz(ss); 100 int flag = 0; 101 for (int i = 0; i < len; ++ i) 102 flag = (flag*10 + ss[i] - '0') % 7; 103 flag = flag * 10000 % 7; 104 ss += mp[(7 - flag) % 7]; 105 cout << ss << endl; 106 } 107 return 0; 108 }
D
题意：有一个0，1矩阵(最大5000*5000)，你可以无限次数地交换任意两行的位置。求交换之后，单个只含有1的矩形的面积最大，并返回这个面积值。
解法：枚举矩形的左下角是从哪一列开始，统计每一行从这一列开始连续的1有多少个记录在num数组里，然后从大到小遍历num数组，并更新面积值即可。
tag:dp, think, good
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-12-26 12:49 4 * File Name: D.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <string> 10 #include <cmath> 11 #include <algorithm> 12 #include <vector> 13 #include <cstdlib> 14 #include <sstream> 15 #include <fstream> 16 #include <list> 17 #include <deque> 18 #include <queue> 19 #include <stack> 20 #include <map> 21 #include <set> 22 #include <bitset> 23 #include <cctype> 24 #include <ctime> 25 #include <utility> 26 27 using namespace std; 28 29 #define clr0(x) memset(x, 0, sizeof(x)) 30 #define clr1(x) memset(x, -1, sizeof(x)) 31 #define pb push_back 32 #define sz(v) ((int)(v).size()) 33 #define all(t) t.begin(),t.end() 34 #define INF 999999999999999999 35 #define zero(x) (((x)>0?(x):-(x))<eps) 36 #define out(x) cout<<#x<<":"<<(x)<<endl 37 #define tst(a) cout<<a<<" " 38 #define tst1(a) cout<<#a<<endl 39 #define CINBEQUICKER std::ios::sync_with_stdio(false) 40 41 const double eps = 1e-8; 42 const double PI = atan(1.0)*4; 43 const int inf = 2147483647 / 2; 44 45 typedef vector<int> vi; 46 typedef vector<string> vs; 47 typedef vector<double> vd; 48 typedef pair<int, int> pii; 49 typedef long long int64; 50 51 inline int Mymod (int a, int b) {int x=a%b; if(x<0) x+=b; return x;} 52 53 int n, m; 54 int p[5005][5005], num[5005]; 55 char v[5005][5005]; 56 57 int main() 58 { 59 // freopen("a.in","r",stdin); 60 //freopen("a.out","w",stdout); 61 // std::ios::sync_with_stdio(false); 62 while (scanf ("%d%d", &n, &m) != EOF){ 63 string s; 64 for (int i = 0; i < n; ++ i) 65 scanf ("%s", v[i]); 66 for (int i = 0; i < n; ++ i){ 67 int tmp = m; 68 for (int j = m-1; j >= 0; -- j){ 69 if (v[i][j] == '0') 70 tmp = j, p[i][j] = j; 71 else 72 p[i][j] = tmp; 73 } 74 } 75 int ans = 0; 76 for (int i = 0; i < m; ++ i){ 77 clr0 (num); 78 for (int j = 0; j < n; ++ j) num[p[j][i] - i] ++; 79 int pos = 5000; 80 while (pos && num[pos] == 0) -- pos; 81 int cnt = 0; 82 while (pos){ 83 if (num[pos]) cnt += num[pos]; 84 ans = max(cnt*pos, ans); 85 -- pos; 86 } 87 } 88 printf ("%d ", ans); 89 } 90 return 0; 91 }