前言
感觉稍微有些滑稽吧，毕竟每次练的题都是提高组难度的，结果最后的主要任务是普及组抱一个一等奖回来。至于我的分数嘛。。还是在你看完题解后写在[后记]里面。废话不多说，开始题解。
（其实这篇博客只有题解没有心得。）
第一题可以说的内容不是很多吧。直接暴力，计算每种铅笔需要花费的金额。
只不过计算的时候，需要注意如下问题
- 如果不是整数倍，除完后要加1
- 神奇的Linux系统，很多人的第三个点wa了，所以要养成良好的编写代码的习惯
Code
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<stack>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
aFlag = -;
x = getchar();
}
for(u = x - ''; isdigit((x = getchar())); u = u * + x - '');
ungetc(x, stdin);
u *= aFlag;
} int n;
int cost[], num[];
int result; inline void init(){
result = 0xfffffff;
readInteger(n);
for(int i = , b; i <= ; i++){
b = ;
readInteger(num[i]);
readInteger(cost[i]);
b = n / num[i];
if(n % num[i] != ) b += ;
smin(result, b * cost[i]);
}
printf("%d", result);
} int main(){
freopen("pencil.in", "r", stdin);
freopen("pencil.out", "w", stdout);
init();
return ;
}
第二题，暴力也不会TLE，所以就从起始日期枚举到结束日期，中途把进位之类的事情做好，问题就不会很大。
只不过仍然会存在一些问题
- 进位应该从低位开始判断
- 注意进位的边界
如果不小心手抽了，有些日期跳过了，或者有些地方出了点问题，变成了死循环，也很麻烦。
Code
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<stack>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
aFlag = -;
x = getchar();
}
for(u = x - ''; isdigit((x = getchar())); u = u * + x - '');
ungetc(x, stdin);
u *= aFlag;
} typedef class MyDate{
public:
int year;
int month;
int days;
MyDate(){}
MyDate(int num){
days = num % , num /= ;
month = num % , num /= ;
year = num;
}
boolean isHuiWen(){
if((year / ) != (days % )) return false;
if(((year / ) % ) != ((days / ) % )) return false;
if(((year / ) % ) != (month % )) return false;
if((year % ) != ((month / ) % )) return false;
return true;
}
void next(){
days++;
if(month == && days == && (year % != && (year % == || year % == ))){
days = ;
month++;
}else if(month == && days == && (!(year % != && (year % == || year % == )))){
days = ;
month++;
}else if(days == && (month == || month == || month == || month == || month == || month == || month == )){
days = ;
month++;
}else if(days == && (month == || month == || month == || month == )){
days = ;
month++;
}
if(month == ){
month = ;
year++;
}
}
boolean operator !=(MyDate another){
return !(this->days == another.days && this->month == another.month && this->year == another.year);
}
}MyDate; MyDate start;
MyDate _end; inline void init(){
int a, b;
readInteger(a);
readInteger(b);
start = MyDate(a);
_end = MyDate(b);
} inline void solve(){
int result = ;
while(start != _end){
if(start.isHuiWen()) result++;
start.next();
}
if(_end.isHuiWen()) result++;
printf("%d", result);
} int main(){
freopen("date.in", "r", stdin);
freopen("date.out", "w", stdout);
init();
solve();
return ;
}
[小结]
这道题的难度不是特别难，但是，有个很明显的问题代码不简洁，而且好像读入优化也没什必要。。
明明70几行可以打完的程序，我却偏偏打了100行。
如果是C语言用户，可以手打一些函数来代替我写的成员函数
第三题是暴力加优化。
首先讲思路吧。从头到尾扫描。需要一些量比如说上一艘船，对于它来说，在24小时内最早的一艘的位置（数组中）（就记为last吧）。还有当前不同种类的游客。还需要统计每个国籍的游客的数量（在这艘船的24小时内）
处理一艘船的时候，解决如下几个任务
- 更新对于已经不在24小时内的船，从last开始while循环，减去它们对应的国籍的游客数，再判断它是否为0，如果是，那么就把当前不同国籍的数量减去1
- 读入该艘船上的游客，如果这个国籍的数量为0，则把当前不同国籍的数量数加1，接着把这个国籍的游客数加1
- 输出这个不同国籍的数量
关于还省内存的事再说一下
- 使用vector
- 用两个一维数组，一个记录每艘船记录的数据在另一个数组中结束的下标，另一个就记录每艘船的游客的国籍
由于vector太慢(虽说对于这道题已经足够了)，而且经常手抖导致崩掉，果断嫌弃，改用方法2（我也不是说vector一定不好，至少对于很多时候还是挺管用的，效率也没有我说的那么糟糕，只不过我不喜欢而已）
当然现在我很喜欢用vector偷懒 ——2018.2.13
Code
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
aFlag = -;
x = getchar();
}
for(u = x - ''; isdigit((x = getchar())); u = u * + x - '');
ungetc(x, stdin);
u *= aFlag;
} #define DAYSEC 86400 int n;
int tbegin;
int *times;
int listofx[];
int counter[];
int defkinds;
int *endsindex; inline void init(){
readInteger(n);
endsindex = new int[(const int)(n + )];
times = new int[(const int)(n + )];
tbegin = ;
endsindex[] = ;
for(int i = , peo; i <= n; i++){
readInteger(times[i]);
while(times[tbegin] <= times[i] - DAYSEC){
for(int j = endsindex[tbegin - ] + ; j <= endsindex[tbegin]; j++){
counter[listofx[j]]--;
if(counter[listofx[j]] <= ) defkinds--;
}
tbegin++;
}
readInteger(peo);
endsindex[i] = endsindex[i - ] + peo;
for(int j = endsindex[i - ] + ; j <= endsindex[i]; j++){
readInteger(listofx[j]);
if(counter[listofx[j]] == ) defkinds++;
counter[listofx[j]]++;
}
printf("%d\n", defkinds);
}
} int main(){
freopen("port.in", "r", stdin);
freopen("port.out", "w", stdout);
init();
return ;
}
首先呢，想一个正确但不高效的方法，枚举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(滑稽)
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<ctime>
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
aFlag = -;
x = getchar();
}
for(u = x - ''; isdigit((x = getchar())); u = u * + x - '');
ungetc(x, stdin);
u *= aFlag;
} int n, m;
int counter[];
vector<int> poses[];
int *fora, *forb, *forc, *ford;
int *mlist;
int *blist; int mylower_bound(int* a, int from, int end, int val){
int l = from, r = end - ;
while(l <= r){
int mid = (l + r) >> ;
if(val <= a[mid]) r = mid - ;
else l = mid + ;
}
return r + ;
} inline void init(){
readInteger(n);
readInteger(m);
fora = new int[(const int)(n + )];
forb = new int[(const int)(n + )];
forc = new int[(const int)(n + )];
ford = new int[(const int)(n + )];
mlist = new int[(const int)(m + )];
blist = new int[(const int)(m + )];
memset(fora, , sizeof(int) * (n + ));
memset(forb, , sizeof(int) * (n + ));
memset(forc, , sizeof(int) * (n + ));
memset(ford, , sizeof(int) * (n + ));
for(int i = , a; i <= m; i++){
readInteger(a);
counter[a]++;
poses[a].push_back(i);
mlist[i] = blist[i] = a;
}
} inline void solve(){
sort(mlist + , mlist + m + );
for(int i = ; i < n; i++){
if(!counter[i]) continue;
for(int j = i + ; j <= n; j += ){
if(!counter[j]) continue;
int k_start = mylower_bound(mlist, , m + , j + (j - i) * + );
if(k_start == m + ) continue;
for(int k = mlist[k_start]; k <= n; k++){
if(!counter[k]) continue;
int end = k + (j - i) / ;
if(end > n) break;
if(counter[end]){
fora[i] += counter[j] * counter[k] * counter[end];
forb[j] += counter[i] * counter[k] * counter[end];
forc[k] += counter[i] * counter[j] * counter[end];
ford[end] += counter[i] * counter[j] * counter[k];
}
}
}
}
for(int i = ; i <= m; i++){
printf("%d %d %d %d\n", fora[blist[i]], forb[blist[i]], forc[blist[i]], ford[blist[i]]);
}
} int main(){
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);
init();
solve();
return ;
}
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(看了正解后写出来的程序)
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<ctime>
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
aFlag = -;
x = getchar();
}
for(u = x - ''; isdigit((x = getchar())); u = u * + x - '');
ungetc(x, stdin);
u *= aFlag;
} int n, m;
int counter[];
int *fora, *forb, *forc, *ford;
int *mlist;
int *blist; int mylower_bound(int* a, int from, int end, int val){
int l = from, r = end - ;
while(l <= r){
int mid = (l + r) >> ;
if(val <= a[mid]) r = mid - ;
else l = mid + ;
}
return r + ;
} inline void init(){
readInteger(n);
readInteger(m);
fora = new int[(const int)(n + )];
forb = new int[(const int)(n + )];
forc = new int[(const int)(n + )];
ford = new int[(const int)(n + )];
mlist = new int[(const int)(m + )];
blist = new int[(const int)(m + )];
memset(fora, , sizeof(int) * (n + ));
memset(forb, , sizeof(int) * (n + ));
memset(forc, , sizeof(int) * (n + ));
memset(ford, , sizeof(int) * (n + ));
for(int i = , a; i <= m; i++){
readInteger(a);
counter[a]++;
mlist[i] = blist[i] = a;
}
} inline void solve(){
// sort(mlist + 1, mlist + m + 1);
for(int i = ; i * < n; i++){
int len = * i + ;
int s = ;
for(int d = len + ; d <= n; d++){
s += counter[d - len] * counter[d - len + i * ];
ford[d] += s * counter[d - i];
forc[d - i] += s * counter[d];
}
s = ;
for(int a = n - len; a >= ; a--){
s += counter[a + len] * counter[a + len - i];
fora[a] += s * counter[a + i * ];
forb[a + i * ] += s * counter[a];
}
}
for(int i = ; i <= m; i++){
printf("%d %d %d %d\n", fora[blist[i]], forb[blist[i]], forc[blist[i]], ford[blist[i]]);
}
} int main(){
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);
init();
solve();
return ;
}
（PS）
后话
从上面的描述中应该可以猜到我noip普及组的分数了吧。我也就不说了。
怎么说呢。。这也算是一个里程碑吧！虽然oi的路还长。。但是小小地庆祝一下也是可以的。
这次考得比较好的原因主要是心态比较好吧。也感谢四川吧，分数线比起什么浙江300分好多了(真的没有别的意思)，所以说压力没那么大，而且靠差了还有提高组