CodeForces 221(div 2)-白红宇

CodeForces 221(div 2)

阅读量：6077 次

发布时间：2019-06-20

本文共 6946 字，大约阅读时间需要 23 分钟。

无trick水题。。。

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-12-24 22:26 4  * File Name: B.cpp 5  */ 6 #include 
      
        7 #include 
       
         8 #include 
        
          9 #include 
         
          10 #include 
          
           11 #include 
           
            12 #include 
            
             13 #include 
             
              14 #include 
              
               15 #include 
               
                16 #include 
                
                 17 #include 
                 
                  18 #include 
                  
                   19 #include 
                   
                    20 #include 
                    21 #include 
                     
                      22 #include 
                      
                       23 #include 
                       
                        24 #include 
                        
                         25 #include 
                         
                          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_back32 #define sz(v) ((int)(v).size())33 #define all(t) t.begin(),t.end()34 #define INF 99999999999999999935 #define zero(x) (((x)>0?(x):-(x))

vi;46 typedef vector

vs;47 typedef vector

vd;48 typedef pair

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\n", ans / 2);73 }74 return 0;75 }

View Code

YY题。。。结论直接看代码就好了。。。比赛的时候YY出了结论算样例算错了，然后就去想别的方法了。。。。。。

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-12-24 22:26 4  * File Name: B.cpp 5  */ 6 #include 
      
        7 #include 
       
         8 #include 
        
          9 #include 
         
          10 #include 
          
           11 #include 
           
            12 #include 
            
             13 #include 
             
              14 #include 
              
               15 #include 
               
                16 #include 
                
                 17 #include 
                 
                  18 #include 
                  
                   19 #include 
                   
                    20 #include 
                    21 #include 
                     
                      22 #include 
                      
                       23 #include 
                       
                        24 #include 
                        
                         25 #include 
                         
                          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_back32 #define sz(v) ((int)(v).size())33 #define all(t) t.begin(),t.end()34 #define INF 99999999999999999935 #define zero(x) (((x)>0?(x):-(x))

vi;46 typedef vector

vs;47 typedef vector

vd;48 typedef pair

View Code

题意：给一个很大的数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 
      
         7 #include 
       
          8 #include 
        
           9 #include 
         
           10 #include 
          
            11 #include 
           
             12 #include 
            
              13 #include 
             
               14 #include 
              
                15 #include 
               
                 16 #include 
                
                  17 #include 
                 
                   18 #include 
                  
                    19 #include 
                   
                     20 #include 
                     21 #include 
                     
                       22 #include 
                      
                        23 #include 
                       
                         24 #include 
                        
                          25 #include 
                         
                           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))

vi; 46 typedef vector

vs; 47 typedef vector

vd; 48 typedef pair

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

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 }

View Code

题意：有一个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 
      
        7 #include 
       
         8 #include 
        
          9 #include 
         
          10 #include 
          
           11 #include 
           
            12 #include 
            
             13 #include 
             
              14 #include 
              
               15 #include 
               
                16 #include 
                
                 17 #include 
                 
                  18 #include 
                  
                   19 #include 
                   
                    20 #include 
                    21 #include 
                     
                      22 #include 
                      
                       23 #include 
                       
                        24 #include 
                        
                         25 #include 
                         
                          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_back32 #define sz(v) ((int)(v).size())33 #define all(t) t.begin(),t.end()34 #define INF 99999999999999999935 #define zero(x) (((x)>0?(x):-(x))

vi;46 typedef vector

vs;47 typedef vector

vd;48 typedef pair

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 else72 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\n", ans);89 }90 return 0;91 }

View Code