SRM 609(1-250pt, 1-500pt)

嗯。。。。还是应该坚持写题解的好习惯啊。。。

DIV1 250pt

　　这难度是回到srm 300+的250了嘛。。。略

 1 // BEGIN CUT HERE
 2 /*
 3  * Author:  plum rain
 4  * score :
 5  */
 6 /*
 7 
 8  */
 9 // END CUT HERE
10 #line 11 "MagicalStringDiv1.cpp"
11 #include <sstream>
12 #include <stdexcept>
13 #include <functional>
14 #include <iomanip>
15 #include <numeric>
16 #include <fstream>
17 #include <cctype>
18 #include <iostream>
19 #include <cstdio>
20 #include <vector>
21 #include <cstring>
22 #include <cmath>
23 #include <algorithm>
24 #include <cstdlib>
25 #include <set>
26 #include <queue>
27 #include <bitset>
28 #include <list>
29 #include <string>
30 #include <utility>
31 #include <map>
32 #include <ctime>
33 #include <stack>
34 
35 using namespace std;
36 
37 #define clr0(x) memset(x, 0, sizeof(x))
38 #define clr1(x) memset(x, -1, sizeof(x))
39 #define pb push_back
40 #define sz(v) ((int)(v).size())
41 #define all(t) t.begin(),t.end()
42 #define zero(x) (((x)>0?(x):-(x))<eps)
43 #define out(x) cout<<#x<<":"<<(x)<<endl
44 #define tst(a) cout<<a<<" "
45 #define tst1(a) cout<<#a<<endl
46 #define CINBEQUICKER std::ios::sync_with_stdio(false)
47 
48 typedef vector<int> vi;
49 typedef vector<string> vs;
50 typedef vector<double> vd;
51 typedef pair<int, int> pii;
52 typedef long long int64;
53 
54 const double eps = 1e-8;
55 const double PI = atan(1.0)*4;
56 const int inf = 2139062143 / 2;
57 
58 class MagicalStringDiv1
59 {
60     public:
61         int getLongest(string s){
62             int t1 = 0, t2 = sz(s)-1, num = 0;
63             while (t1 <= t2){
64                 while (t1 < sz(s) && s[t1] != '>') ++ t1;
65                 while (t2 >= 0 && s[t2] != '<') -- t2;
66                 if (t1 <= t2) -- t2, ++ t1, num += 2;
67             }
68             return num;
69         }
70         
71 // BEGIN CUT HERE
72     public:
73     void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); }
74     private:
75     template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '"' << *iter << "","; os << " }"; return os.str(); }
76     void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "	Expected: "" << Expected << '"' << endl; cerr << "	Received: "" << Received << '"' << endl; } }
77     void test_case_0() { string Arg0 = "<"; int Arg1 = 4; verify_case(0, Arg1, getLongest(Arg0)); }
78     void test_case_1() { string Arg0 = ">>><<<"; int Arg1 = 6; verify_case(1, Arg1, getLongest(Arg0)); }
79     void test_case_2() { string Arg0 = "<<<>>>"; int Arg1 = 0; verify_case(2, Arg1, getLongest(Arg0)); }
80     void test_case_3() { string Arg0 = "<<<<><>>><>>><>><>><>>><<<<>><>>>>><<>>>>><><<<<>>"; int Arg1 = 24; verify_case(3, Arg1, getLongest(Arg0)); }
81 
82 // END CUT HERE
83 
84 };
85 
86 // BEGIN CUT HERE
87 int main()
88 {
89 //    freopen( "a.out" , "w" , stdout );    
90     MagicalStringDiv1 ___test;
91     ___test.run_test(-1);
92        return 0;
93 }
94 // END CUT HERE
View Code

DIV1 500pt

题意：有k种颜色的球，每种颜色有an[i]个(an[i] > 0)。有两种背包，每种背包都有无限多个，第一种背包里面装的所有球颜色必须相同，第二种背包里面装的球颜色不能有相同的。无论哪一种背包，最多都只能装k个。问，最少用多少个背包能装下所有球。

　　an[i] <= 10^9, k <= 10^5

解法：嗯。。。首先，如果不要求每个背包最多装k个，那就很简单了。直接用an[i]枚举有多少个第二种背包，然后第一种背包的数量就是n - i - 1。

　　　然后，加上每个背包只能装k个的限制条件，就是首先对k个背包预处理一遍，an[i] %= k。后面一步是yy出来的。。。感觉是这样，不知道怎么证。。。

tag:think

  1 // BEGIN CUT HERE
  2 /*
  3  * Author:  plum rain
  4  * score :
  5  */
  6 /*
  7 
  8  */
  9 // END CUT HERE
 10 #line 11 "PackingBallsDiv1.cpp"
 11 #include <sstream>
 12 #include <stdexcept>
 13 #include <functional>
 14 #include <iomanip>
 15 #include <numeric>
 16 #include <fstream>
 17 #include <cctype>
 18 #include <iostream>
 19 #include <cstdio>
 20 #include <vector>
 21 #include <cstring>
 22 #include <cmath>
 23 #include <algorithm>
 24 #include <cstdlib>
 25 #include <set>
 26 #include <queue>
 27 #include <bitset>
 28 #include <list>
 29 #include <string>
 30 #include <utility>
 31 #include <map>
 32 #include <ctime>
 33 #include <stack>
 34 
 35 using namespace std;
 36 
 37 #define clr0(x) memset(x, 0, sizeof(x))
 38 #define clr1(x) memset(x, -1, sizeof(x))
 39 #define pb push_back
 40 #define sz(v) ((int)(v).size())
 41 #define all(t) t.begin(),t.end()
 42 #define zero(x) (((x)>0?(x):-(x))<eps)
 43 #define out(x) cout<<#x<<":"<<(x)<<endl
 44 #define tst(a) cout<<a<<" "
 45 #define tst1(a) cout<<#a<<endl
 46 #define CINBEQUICKER std::ios::sync_with_stdio(false)
 47 
 48 typedef vector<int> vi;
 49 typedef vector<string> vs;
 50 typedef vector<double> vd;
 51 typedef pair<int, int> pii;
 52 typedef long long int64;
 53 
 54 const double eps = 1e-8;
 55 const double PI = atan(1.0)*4;
 56 const int inf = 2139062143 / 2;
 57 
 58 int an[100005];
 59 vi yu;
 60 
 61 class PackingBallsDiv1
 62 {
 63     public:
 64         int minPacks(int n, int a, int b, int c, int mod){
 65             an[0] = a;
 66             for (int i = 1; i < n; ++ i) an[i] = ((int64)an[i-1] * b + c) % mod + 1;    
 67 
 68             int64 num = 0;
 69             for (int i = 0; i < n; ++ i){
 70                 num += an[i] / n;
 71                 an[i] %= n;
 72             }
 73             sort (an, an+n);
 74 
 75             //if (n == 3) for (int i = 0; i < n; ++ i) tst (an[i]);
 76             //cout << endl;
 77 //
 78             int64 cnt = n;
 79             for (int i = 0; i < n; ++ i){
 80                 int64 tmp = an[i] + n - i - 1;
 81                 cnt = cnt > tmp ? tmp : cnt;
 82             }
 83             return (int)(cnt + num);
 84         }
 85         
 86 // BEGIN CUT HERE
 87     public:
 88     void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); }
 89     private:
 90     template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '"' << *iter << "","; os << " }"; return os.str(); }
 91     void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "	Expected: "" << Expected << '"' << endl; cerr << "	Received: "" << Received << '"' << endl; } }
 92     void test_case_0() { int Arg0 = 3; int Arg1 = 4; int Arg2 = 2; int Arg3 = 5; int Arg4 = 6; int Arg5 = 4; verify_case(0, Arg5, minPacks(Arg0, Arg1, Arg2, Arg3, Arg4)); }
 93     void test_case_1() { int Arg0 = 1; int Arg1 = 58; int Arg2 = 23; int Arg3 = 39; int Arg4 = 93; int Arg5 = 58; verify_case(1, Arg5, minPacks(Arg0, Arg1, Arg2, Arg3, Arg4)); }
 94     void test_case_2() { int Arg0 = 23; int Arg1 = 10988; int Arg2 = 5573; int Arg3 = 4384; int Arg4 = 100007; int Arg5 = 47743; verify_case(2, Arg5, minPacks(Arg0, Arg1, Arg2, Arg3, Arg4)); }
 95     void test_case_3() { int Arg0 = 100000; int Arg1 = 123456789; int Arg2 = 234567890; int Arg3 = 345678901; int Arg4 = 1000000000; int Arg5 = 331988732; verify_case(3, Arg5, minPacks(Arg0, Arg1, Arg2, Arg3, Arg4)); }
 96 
 97 // END CUT HERE
 98 
 99 };
100 
101 // BEGIN CUT HERE
102 int main()
103 {
104     //freopen( "a.out" , "w" , stdout );    
105     PackingBallsDiv1 ___test;
106     ___test.run_test(-1);
107        return 0;
108 }
109 // END CUT HERE
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/plumrain/p/srm_609.html