首页 > 代码库 > [题解]noip2016普及组题解和心得

[题解]noip2016普及组题解和心得

[前言]

  感觉稍微有些滑稽吧,毕竟每次练的题都是提高组难度的,结果最后的主要任务是普及组抱一个一等奖回来。至于我的分数嘛。。还是在你看完题解后写在[后记]里面。废话不多说,开始题解。

 


技术分享

技术分享

技术分享


  第一题可以说的内容不是很多吧。直接暴力,计算每种铅笔需要花费的金额。

  只不过计算的时候,需要注意如下问题

  • 如果不是整数倍,除完后要加1
  • 神奇的Linux系统,很多人的第三个点wa了,所以要养成良好的编写代码的习惯

Code(我的源程序)

 

 1 #include<iostream>
 2 #include<fstream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<algorithm>
 8 #include<stack>
 9 #include<set>
10 #include<map>
11 #include<queue>
12 using namespace std;
13 typedef bool boolean;
14 #define smin(a, b) (a) = min((a), (b))
15 #define smax(a, b) (a) = max((a), (b))
16 template<typename T>
17 inline void readInteger(T& u){
18     char x;
19     int aFlag = 1;
20     while(!isdigit((x = getchar())) && x != -);
21     if(x == -){
22         aFlag = -1;
23         x = getchar();
24     }
25     for(u = x - 0; isdigit((x = getchar())); u = u * 10 + x - 0);
26     ungetc(x, stdin);
27     u *= aFlag;
28 }
29 
30 int n;
31 int cost[5], num[5];
32 int result;
33 
34 inline void init(){
35     result = 0xfffffff;
36     readInteger(n);
37     for(int i = 1, b; i <= 3; i++){
38         b = 0;
39         readInteger(num[i]);
40         readInteger(cost[i]);
41         b = n / num[i];
42         if(n % num[i] != 0)    b += 1;
43         smin(result, b * cost[i]);
44     }
45     printf("%d", result);
46 }
47 
48 int main(){
49     freopen("pencil.in", "r", stdin);
50     freopen("pencil.out", "w", stdout);
51     init();
52     return 0;
53 }

技术分享

 

技术分享


  第二题,暴力也不会TLE,所以就从起始日期枚举到结束日期,中途把进位之类的事情做好,问题就不会很大。

  只不过仍然会存在一些问题

  • 进位应该从低位开始判断
  • 注意进位的边界

   如果不小心手抽了,有些日期跳过了,或者有些地方出了点问题,变成了死循环,也很麻烦。

Code(我的源程序)

  1 #include<iostream>
  2 #include<fstream>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<algorithm>
  8 #include<stack>
  9 #include<set>
 10 #include<map>
 11 #include<queue>
 12 using namespace std;
 13 typedef bool boolean;
 14 #define smin(a, b) (a) = min((a), (b))
 15 #define smax(a, b) (a) = max((a), (b))
 16 template<typename T>
 17 inline void readInteger(T& u){
 18     char x;
 19     int aFlag = 1;
 20     while(!isdigit((x = getchar())) && x != -);
 21     if(x == -){
 22         aFlag = -1;
 23         x = getchar();
 24     }
 25     for(u = x - 0; isdigit((x = getchar())); u = u * 10 + x - 0);
 26     ungetc(x, stdin);
 27     u *= aFlag;
 28 }
 29 
 30 typedef class MyDate{
 31     public:
 32         int year;
 33         int month;
 34         int days;
 35         MyDate(){}
 36         MyDate(int num){
 37             days = num % 100, num /= 100;
 38             month = num % 100, num /= 100;
 39             year = num;
 40         }
 41         boolean isHuiWen(){
 42             if((year / 1000) != (days % 10))    return false;
 43             if(((year / 100) % 10) != ((days / 10) % 10))    return false;
 44             if(((year / 10) % 10) != (month % 10))    return false;
 45             if((year % 10) != ((month / 10) % 10))    return false;
 46             return true;
 47         }
 48         void next(){
 49             days++;
 50             if(month == 2 && days == 30 && (year % 100 != 0 && (year % 4 == 0 || year % 400 == 0))){
 51                 days = 1;
 52                 month++;
 53             }else if(month == 2 && days == 29 && (!(year % 100 != 0 && (year % 4 == 0 || year % 400 == 0)))){
 54                 days = 1;
 55                 month++;
 56             }else if(days == 32 && (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12)){
 57                 days = 1;
 58                 month++;
 59             }else if(days == 31 && (month == 4 || month == 6 || month == 9 || month == 11)){
 60                 days = 1;
 61                 month++;
 62             }
 63             if(month == 13){
 64                 month = 1;
 65                 year++;
 66             }
 67         }
 68         boolean operator !=(MyDate another){
 69             return !(this->days == another.days && this->month == another.month && this->year == another.year);
 70         }
 71 }MyDate;
 72 
 73 MyDate start;
 74 MyDate _end;
 75 
 76 inline void init(){
 77     int a, b;
 78     readInteger(a);
 79     readInteger(b);
 80     start = MyDate(a);
 81     _end = MyDate(b);
 82 }
 83 
 84 inline void solve(){
 85     int result = 0;
 86     while(start != _end){
 87         if(start.isHuiWen())    result++;
 88         start.next();
 89     }
 90     if(_end.isHuiWen())    result++;
 91     printf("%d", result);
 92 }
 93 
 94 int main(){
 95     freopen("date.in", "r", stdin);
 96     freopen("date.out", "w", stdout);
 97     init();
 98     solve();
 99     return 0;
100 }

[小结]

  这道题的难度不是特别难,但是,有个很明显的问题代码不简洁,而且好像读入优化也没什必要。。

明明70几行可以打完的程序,我却偏偏打了100行。

  如果是C语言用户,可以手打一些函数来代替我写的成员函数


技术分享

技术分享

 

技术分享

 


  第三题是暴力加优化。

  首先讲思路吧。从头到尾扫描。需要一些量比如说上一艘船,对于它来说,在24小时内最早的一艘的位置(数组中)(就记为last吧)。还有当前不同种类的游客。还需要统计每个国籍的游客的数量(在这艘船的24小时内)

处理一艘船的时候,解决如下几个任务

  1. 更新对于已经不在24小时内的船,从last开始while循环,减去它们对应的国籍的游客数,再判断它是否为0,如果是,那么就把当前不同国籍的数量减去1
  2. 读入该艘船上的游客,如果这个国籍的数量为0,则把当前不同国籍的数量数加1,接着把这个国籍的游客数加1
  3. 输出这个不同国籍的数量

 关于还省内存的事再说一下

  1. 使用vector
  2. 用两个一维数组,一个记录每艘船记录的数据在另一个数组中结束的下标,另一个就记录每艘船的游客的国籍

  由于vector太慢(虽说对于这道题已经足够了),而且经常手抖导致崩掉,果断嫌弃,改用方法2(我也不是说vector一定不好,至少对于很多时候还是挺管用的,效率也没有我说的那么糟糕,只不过我不喜欢而已)

Code(我的源程序)

 

 1 #include<iostream>
 2 #include<fstream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<algorithm>
 8 #include<stack>
 9 #include<set>
10 #include<map>
11 #include<queue>
12 #include<vector>
13 using namespace std;
14 typedef bool boolean;
15 #define smin(a, b) (a) = min((a), (b))
16 #define smax(a, b) (a) = max((a), (b))
17 template<typename T>
18 inline void readInteger(T& u){
19     char x;
20     int aFlag = 1;
21     while(!isdigit((x = getchar())) && x != -);
22     if(x == -){
23         aFlag = -1;
24         x = getchar();
25     }
26     for(u = x - 0; isdigit((x = getchar())); u = u * 10 + x - 0);
27     ungetc(x, stdin);
28     u *= aFlag;
29 }
30 
31 #define DAYSEC    86400
32 
33 int n;
34 int tbegin;
35 int *times;
36 int listofx[300005];
37 int counter[100005];
38 int defkinds;
39 int *endsindex;
40 
41 inline void init(){
42     readInteger(n);
43     endsindex = new int[(const int)(n + 1)];
44     times = new int[(const int)(n + 1)];
45     tbegin = 1;
46     endsindex[0] = 0;
47     for(int i = 1, peo; i <= n; i++){
48         readInteger(times[i]);
49         while(times[tbegin] <= times[i] - DAYSEC){
50             for(int j = endsindex[tbegin - 1] + 1; j <= endsindex[tbegin]; j++){
51                 counter[listofx[j]]--;
52                 if(counter[listofx[j]] <= 0)    defkinds--;
53             }
54             tbegin++;
55         }
56         readInteger(peo);
57         endsindex[i] = endsindex[i - 1] + peo;
58         for(int j = endsindex[i - 1] + 1; j <= endsindex[i]; j++){
59             readInteger(listofx[j]);
60             if(counter[listofx[j]] == 0)    defkinds++;
61             counter[listofx[j]]++;
62         }
63         printf("%d\n", defkinds);
64     }
65 }
66 
67 int main(){
68     freopen("port.in", "r", stdin);
69     freopen("port.out", "w", stdout);
70     init();
71     return 0;
72 }

 技术分享

技术分享

 

技术分享

技术分享


  首先呢,想一个正确但不高效的方法,枚举a,b,c,d然后判断是否存在,理论复杂度O(m4)。

  接着可以发现一个物体的魔法值为2,还有一个魔法值为2,它们的贡献(实在找不到词了),是一样的。所以可以直接枚举数值,并且统计了数量后,可以O(1)判断d是否存在,复杂度降为O(4n3m)

  看着4m有些不爽,决定把它优化掉。既然魔法值一样的物品贡献一样就没必要按照每件来记录作为A、B、C、D物品的次数,直接按照数值来记录,就没有必要去用第四重循环了。

  计算的方法是这样的作为a物品的次数,根据乘法原理,就要加上可作为b物品、c物品和d物品的个数的乘积。没怎么说清楚,但是举个例子就好懂,比如说有1,5,24,26,26。当1作为a物品时,可作为b物品的是5,有一个,可作为c物品的是24,有一个,可作为d物品的是26,有两个,所以应该增加1*1*2次。其他同理。

  为了对付极端数据(不过貌似没有),所以我拍了序,加了个lower_bound,然后并没有AC(滑稽)

技术分享
  1 #include<iostream>
  2 #include<fstream>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<algorithm>
  8 #include<stack>
  9 #include<set>
 10 #include<map>
 11 #include<queue>
 12 #include<ctime>
 13 using namespace std;
 14 typedef bool boolean;
 15 #define smin(a, b) (a) = min((a), (b))
 16 #define smax(a, b) (a) = max((a), (b))
 17 template<typename T>
 18 inline void readInteger(T& u){
 19     char x;
 20     int aFlag = 1;
 21     while(!isdigit((x = getchar())) && x != -);
 22     if(x == -){
 23         aFlag = -1;
 24         x = getchar();
 25     }
 26     for(u = x - 0; isdigit((x = getchar())); u = u * 10 + x - 0);
 27     ungetc(x, stdin);
 28     u *= aFlag;
 29 }
 30 
 31 int n, m;
 32 int counter[15005];
 33 vector<int> poses[15005];
 34 int    *fora, *forb, *forc, *ford;
 35 int *mlist;
 36 int *blist;
 37 
 38 int mylower_bound(int* a, int from, int end, int val){
 39     int l = from, r = end - 1;
 40     while(l <= r){
 41         int mid = (l + r) >> 1;
 42         if(val <= a[mid])    r = mid - 1;
 43         else l = mid + 1;
 44     }
 45     return r + 1;
 46 }
 47 
 48 inline void init(){
 49     readInteger(n);
 50     readInteger(m);
 51     fora = new int[(const int)(n + 1)];
 52     forb = new int[(const int)(n + 1)];
 53     forc = new int[(const int)(n + 1)];
 54     ford = new int[(const int)(n + 1)];
 55     mlist = new int[(const int)(m + 1)];
 56     blist = new int[(const int)(m + 1)];
 57     memset(fora, 0, sizeof(int) * (n + 1));
 58     memset(forb, 0, sizeof(int) * (n + 1));
 59     memset(forc, 0, sizeof(int) * (n + 1));
 60     memset(ford, 0, sizeof(int) * (n + 1));
 61     for(int i = 1, a; i <= m; i++){
 62         readInteger(a);
 63         counter[a]++;
 64         poses[a].push_back(i);
 65         mlist[i] = blist[i] = a;
 66     }
 67 }
 68 
 69 inline void solve(){
 70     sort(mlist + 1, mlist + m + 1);
 71     for(int i = 1; i < n; i++){
 72         if(!counter[i])    continue;
 73         for(int j = i + 2; j <= n; j += 2){
 74             if(!counter[j])    continue;
 75             int k_start = mylower_bound(mlist, 1, m + 1, j + (j - i) * 3 + 1);
 76             if(k_start == m + 1)    continue;
 77             for(int k = mlist[k_start]; k <= n; k++){
 78                 if(!counter[k])    continue;
 79                 int end = k + (j - i) / 2;
 80                 if(end > n)    break;
 81                 if(counter[end]){
 82                     fora[i] += counter[j] * counter[k] * counter[end];
 83                     forb[j] += counter[i] * counter[k] * counter[end];
 84                     forc[k] += counter[i] * counter[j] * counter[end];
 85                     ford[end] += counter[i] * counter[j] * counter[k];
 86                 }
 87             }
 88         }
 89     }
 90     for(int i = 1; i <= m; i++){
 91         printf("%d %d %d %d\n", fora[blist[i]], forb[blist[i]], forc[blist[i]], ford[blist[i]]);
 92     }
 93 }
 94 
 95 int main(){
 96     freopen("magic.in", "r", stdin);
 97     freopen("magic.out", "w", stdout);
 98     init();
 99     solve();
100     return 0;
101 }
85分比赛时写的程序

  正解呢就是很神奇的方法来做的,首先看张图

技术分享

  设c,d之间的差为i,则可以表示为上图。总长度大于9i。如果我们设这个长度是9i + 1,那么看,下图

 技术分享

  a2 - a1 = 1。那么c1,d1可以和a1,b1组合,说明c2,d2也可以和a1,b1组合,也就是说,在计算c,d的时候,只需要累加a,b搭配的方案数,再按照乘法原理就可以求出来了。枚举的量也大大减少了,只需要枚举i和d,a。时间复杂度成功地降为可以接受的范围。

Code(看了正解后写出来的程序)

 

 1 #include<iostream>
 2 #include<fstream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<algorithm>
 8 #include<stack>
 9 #include<set>
10 #include<map>
11 #include<queue>
12 #include<ctime>
13 using namespace std;
14 typedef bool boolean;
15 #define smin(a, b) (a) = min((a), (b))
16 #define smax(a, b) (a) = max((a), (b))
17 template<typename T>
18 inline void readInteger(T& u){
19     char x;
20     int aFlag = 1;
21     while(!isdigit((x = getchar())) && x != -);
22     if(x == -){
23         aFlag = -1;
24         x = getchar();
25     }
26     for(u = x - 0; isdigit((x = getchar())); u = u * 10 + x - 0);
27     ungetc(x, stdin);
28     u *= aFlag;
29 }
30 
31 int n, m;
32 int counter[15005];
33 int    *fora, *forb, *forc, *ford;
34 int *mlist;
35 int *blist;
36 
37 int mylower_bound(int* a, int from, int end, int val){
38     int l = from, r = end - 1;
39     while(l <= r){
40         int mid = (l + r) >> 1;
41         if(val <= a[mid])    r = mid - 1;
42         else l = mid + 1;
43     }
44     return r + 1;
45 }
46 
47 inline void init(){
48     readInteger(n);
49     readInteger(m);
50     fora = new int[(const int)(n + 1)];
51     forb = new int[(const int)(n + 1)];
52     forc = new int[(const int)(n + 1)];
53     ford = new int[(const int)(n + 1)];
54     mlist = new int[(const int)(m + 1)];
55     blist = new int[(const int)(m + 1)];
56     memset(fora, 0, sizeof(int) * (n + 1));
57     memset(forb, 0, sizeof(int) * (n + 1));
58     memset(forc, 0, sizeof(int) * (n + 1));
59     memset(ford, 0, sizeof(int) * (n + 1));
60     for(int i = 1, a; i <= m; i++){
61         readInteger(a);
62         counter[a]++;
63         mlist[i] = blist[i] = a;
64     }
65 }
66 
67 inline void solve(){
68 //    sort(mlist + 1, mlist + m + 1);
69     for(int i = 1; i * 9 < n; i++){
70         int len = 9 * i + 1;
71         int s = 0;
72         for(int d = len + 1; d <= n; d++){
73             s += counter[d - len] * counter[d - len + i * 2];
74             ford[d] += s * counter[d - i];
75             forc[d - i] += s * counter[d];
76         }
77         s = 0;
78         for(int a = n - len; a >= 1; a--){
79             s += counter[a + len] * counter[a + len - i];
80             fora[a] += s * counter[a + i * 2];
81             forb[a + i * 2] += s * counter[a];
82         }
83     }
84     for(int i = 1; i <= m; i++){
85         printf("%d %d %d %d\n", fora[blist[i]], forb[blist[i]], forc[blist[i]], ford[blist[i]]);
86     }
87 }
88 
89 int main(){
90     freopen("magic.in", "r", stdin);
91     freopen("magic.out", "w", stdout);
92     init();
93     solve();
94     return 0;
95 }

(PS)

 


[后记](与正题完全无关)

  从上面的描述中应该可以猜到我noip普及组的分数了吧。我也就不说了。

  怎么说呢。。这也算是一个里程碑吧!虽然oi的路还长。。但是小小地庆祝一下也是可以的。

  (未完待续。。。)

[题解]noip2016普及组题解和心得