首页 > 代码库 > [题解]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小时内）
处理一艘船的时候，解决如下几个任务
- 更新对于已经不在24小时内的船，从last开始while循环，减去它们对应的国籍的游客数，再判断它是否为0，如果是，那么就把当前不同国籍的数量减去1
- 读入该艘船上的游客，如果这个国籍的数量为0，则把当前不同国籍的数量数加1，接着把这个国籍的游客数加1
- 输出这个不同国籍的数量
关于还省内存的事再说一下
- 使用vector
- 用两个一维数组，一个记录每艘船记录的数据在另一个数组中结束的下标，另一个就记录每艘船的游客的国籍
由于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 }
正解呢就是很神奇的方法来做的，首先看张图
设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普及组题解和心得
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。