srm 569 div2

1、水题，直接穷举就OK了。

1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <map>
 7 #include <stack>
 8 #include <algorithm>
 9 #include <list>
10 #include <ctime>
11 #include <set>
12 #include <queue>
13 #define kfor(i,s,e)  for(int i=s;i<e;i++)
14 typedef long long ll;
15 using namespace std;
16 
17 class TheJediTestDiv2 {
18 public:
19     int countSupervisors(vector<int> students, int Y, int J) {
20         int ct = 0;
21         int res = 5000000;
22         vector<int> studentscopy = students;
23         for (int i = 0; i < students.size(); i++) {
24             students[i] = ((max(0, students[i] - Y)) + (J - 1)) / J;
25             studentscopy[i] = ((max(0, students[i])) + (J - 1)) / J;
26             ct = ct + students[i];
27             cout<<ct<<endl;
28         }
29         for (int i = 0; i < students.size(); i++) {
30             res = min(res, ct - studentscopy[i] + students[i]);
31         }
32         return res;
33     }
34 };

2、找规律即可，若想成功区分，最少是110。

1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <map>
 7 #include <stack>
 8 #include <algorithm>
 9 #include <list>
10 #include <ctime>
11 #include <set>
12 #include <queue>
13 #define kfor(i,s,e)  for(int i=s;i<e;i++)
14 typedef long long ll;
15 using namespace std;
16 
17 class TheDeviceDiv2 {
18 public:
19     string identify(vector <string> plates) {
20         int r=plates.size();
21         int c=plates[0].size();
22         for(int i=0;i<c;i++){
23             int one,zero;
24             one=0;zero=0;
25             for(int j=0;j<r;j++){
26                 if(plates[j][i]=='1'){
27                     one++;
28                 }else{
29                     zero++;
30                 }
31             }
32             if(one<2||zero<1){
33                 return "NO";
34             }
35         }
36         return "YES";
37     }
38 };

3、DP的问题，看的wiki上的答案。

1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <map>
 7 #include <stack>
 8 #include <algorithm>
 9 #include <list>
10 #include <ctime>
11 #include <set>
12 #include <queue>
13 typedef long long ll;
14 using namespace std;
15 ll dp[1205][1205];
16 bool composite[1105];
17 ll MOD = 1000000009;
18 
19 
20 class MegaFactorialDiv2 {
21 public:
22     ll primeAppears(int N, int K, int p)
23     {
24         ll res = 0;
25         // For each factor x:
26         for (int x = p ; x <= N; x+=p) {
27             int c = 0;
28             int y = x;
29             while ( y%p == 0) {
30                 y /= p;
31                 c++;
32             }
33             if (c > 0) {
34                 //how many times does this factor appear?
35                 res += (c * dp[K + N - x - 1][N - x]  ) % MOD;
36             }
37         }
38         return res % MOD;
39     }
40 
41 
42     int countDivisors(int N, int K)
43     {
44         // Precalculate binomial coefficients using Pascal's triangle
45         for (int i=0; i<=K + N; i++) {
46             dp[i][0] = 1;
47             for (int j=1; j<=i; j++) {
48                 dp[i][j] = ( dp[i-1][j-1] + dp[i-1][j] ) % MOD;
49             }
50         }
51 
52         //for each prime between 1 and N: How many times does it appear in N!K?
53         ll res = 1;
54         // For each prime number i between 1 and N: (Use Erathostenes' Sieve)
55         for (int i=2; i<=N; i++) {
56             if (! composite[i]) {
57                 for (int j=i+i; j<=N; j+=i) {
58                     composite[j] = true;
59                 }
60                 res  = (res * (primeAppears(N,K, i ) + 1) ) % MOD;
61             }
62         }
63         return (int)( res % MOD );
64 
65     }
66 };

原文链接: https://www.cnblogs.com/kakamilan/archive/2013/02/14/2911305.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍