正文
noip2016普及组 题解
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
T1
大水题,不解释
上考场代码
#include <algorithm>
#include <cstdio>
using namespace std;
int main() {
freopen("pencil.in","r",stdin);
freopen("pencil.out","w",stdout);
int n,Min = 0x7fffffff;
scanf("%d",&n);
;i <= ;i++) {
int number,money,count;
scanf("%d%d",&number,&money);
count = n/number;
if (n%number) count++; //count为需要买的包数
Min = min(Min,count*money); //取最小的
}
printf("%d",Min);
;
}
T2
简单的模拟,生成date1到date2的所有日期,判断是否回文
上考场代码
#include <cstdio>
,,,,,,,,,,,,};
inline bool check(int date) { //判断是否回文
];
t[] = ;
while (date) {
t[++t[]] = date%;
date /= ;
}
;i <= ;i++)
-i+]) return false;
return true;
}
inline int next(int i) { //生成下一个日期
int year,month,day;
day = (i%)+((i/%)*); //取出日
i /= ;
month = (i%)+((i/%)*); //取出月
i /= ;
year = (i%)+((i/%)*)+((i/%)*)+i/*; //取出年
) && year%) || !(year%)) m[] = ; //判断是否为闰年
day++; //下一天
) { //若到了月底,则变到下一月
day = ;
month++;
}
) { //若到了年底,则变到下一年
month = ;
year++;
}
+year*; //把年月日变成8位数字
}
int main() {
freopen("date.in","r",stdin);
freopen("date.out","w",stdout);
;
scanf("%d%d",&date1,&date2);
for (int i = date1;i <= date2;i = next(i)) //生成date1到date2的所有日期
if (check(i)) ans++; //判断是否回文
printf("%d",ans);
;
}
T3
考场上写了个暴力模拟,70分......出来后发现还是可以做的,写个队列就行了,超出86400s的就出队
70分考场代码
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
],k[];
];
map<];
int main() {
freopen("port.in","r",stdin);
freopen("port.out","w",stdout);
scanf("%d",&n);
;i <= n;i++) {
scanf("%d%d",&t[i],&k[i]);
;j <= k[i];j++) scanf("%d",&x[i][j]);
,R = i,pos = i;
while (L <= R) {
;
) {
pos = mid;
R = mid-;
} ;
}
;
memset(tmp,false,sizeof(tmp));
for (int j = pos;j <= i;j++)
;l <= k[j];l++)
if (!tmp[x[j][l]]) {
ans++;
tmp[x[j][l]] = true;
}
printf("%d\n",ans);
}
;
}
100分代码
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
,vis[];
struct Queue { int t,x; };
queue<Queue> Q;
inline int read(int &x) { //读入优化
char ch;
');
x = ch-';
+ch-';
}
int main() {
freopen("port.in","r",stdin);
freopen("port.out","w",stdout);
read(n);
;i <= n;i++) {
int t,k;
read(t),read(k);
,x;i <= k;i++) {
read(x);
if (!vis[x]) ans++; //若这个乘客是其他国籍,则统计
vis[x]++; //统计
Q.push((Queue){t,x}); //加入队列
}
while (true) { //把86400以外的排除
Queue head = Q.front();
+ <= head.t && head.t <= t) break;
else {
vis[head.x]--;
if (!vis[head.x]) ans--;
Q.pop();
}
}
printf("%d\n",ans);
}
;
}
T4
考场上想不出,于是打了个暴力,40分......
40分考场暴力代码
#include <cstdio>
int main() {
],ans[][];
scanf("%d%d",&n,&m);
;i <= m;i++) scanf("%d",&x[i]);
;a <= m;a++)
;b <= m;b++)
if (a != b)
;c <= m;c++)
if (c != a && c != b && (double)x[b]-(double)x[a] < (double)((double)x[c]-(double)x[b])/3.0)
;d <= m;d++)
*(x[d]-x[c])) {
ans[a][]++;
ans[b][]++;
ans[c][]++;
ans[d][]++;
}
;i <= m;i++) printf(],ans[i][],ans[i][],ans[i][]);
;
}
4重循环是用不到n的,没有白给的条件,没有没用的数据!!!
我们可以把这4个数看作是个数轴上的点,根据题目给的条件,可知AB=2*CD,BC>6*CD,AD>9*CD
那么,我们只需要确定D,就可以确定C点,然后再找AB。我们也可以通过找C来确定ABD。
100分代码
#include <cstdio>
],vis[],a[],b[],c[],d[];
int main() {
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
scanf("%d%d",&n,&m);
;i <= m;i++) {
scanf("%d",&x[i]);
vis[x[i]]++; //把所有数记在数轴上
}
;i <= n/;i++) { //枚举CD的长度
;
+;j <= n;j++) {
sum += vis[j-(*i+)]*vis[j-(*i+)+*i];
d[j] += sum*vis[j-i];
c[j-i] += sum*vis[j];
}
sum = ;
*i+);j >= ;j--) { //枚举CD两点,确定AB的个数
sum += vis[j+(*i+)]*vis[j+(*i+)-i];
a[j] += sum*vis[j+*i];
b[j+*i] += sum*vis[j];
}
}
;i <= m;i++) printf("%d %d %d %d\n",a[x[i]],b[x[i]],c[x[i]],d[x[i]]);
;
}
#include <algorithm> #include <cstdio> using namespace std; int main() { freopen("pencil.in","r",stdin); freopen("pencil.out","w",stdout); int n,Min = 0x7fffffff; scanf("%d",&n); ;i <= ;i++) { int number,money,count; scanf("%d%d",&number,&money); count = n/number; if (n%number) count++; //count为需要买的包数 Min = min(Min,count*money); //取最小的 } printf("%d",Min); ; }
T2
上考场代码
#include <cstdio> ,,,,,,,,,,,,}; inline bool check(int date) { //判断是否回文 ]; t[] = ; while (date) { t[++t[]] = date%; date /= ; } ;i <= ;i++) -i+]) return false; return true; } inline int next(int i) { //生成下一个日期 int year,month,day; day = (i%)+((i/%)*); //取出日 i /= ; month = (i%)+((i/%)*); //取出月 i /= ; year = (i%)+((i/%)*)+((i/%)*)+i/*; //取出年 ) && year%) || !(year%)) m[] = ; //判断是否为闰年 day++; //下一天 ) { //若到了月底,则变到下一月 day = ; month++; } ) { //若到了年底,则变到下一年 month = ; year++; } +year*; //把年月日变成8位数字 } int main() { freopen("date.in","r",stdin); freopen("date.out","w",stdout); ; scanf("%d%d",&date1,&date2); for (int i = date1;i <= date2;i = next(i)) //生成date1到date2的所有日期 if (check(i)) ans++; //判断是否回文 printf("%d",ans); ; }
T3
考场上写了个暴力模拟,70分......出来后发现还是可以做的,写个队列就行了,超出86400s的就出队
70分考场代码
#include <cstring> #include <cstdio> #include <map> using namespace std; ],k[]; ]; map<]; int main() { freopen("port.in","r",stdin); freopen("port.out","w",stdout); scanf("%d",&n); ;i <= n;i++) { scanf("%d%d",&t[i],&k[i]); ;j <= k[i];j++) scanf("%d",&x[i][j]); ,R = i,pos = i; while (L <= R) { ; ) { pos = mid; R = mid-; } ; } ; memset(tmp,false,sizeof(tmp)); for (int j = pos;j <= i;j++) ;l <= k[j];l++) if (!tmp[x[j][l]]) { ans++; tmp[x[j][l]] = true; } printf("%d\n",ans); } ; }
#include <cstdio> #include <queue> #include <map> using namespace std; ,vis[]; struct Queue { int t,x; }; queue<Queue> Q; inline int read(int &x) { //读入优化 char ch; '); x = ch-'; +ch-'; } int main() { freopen("port.in","r",stdin); freopen("port.out","w",stdout); read(n); ;i <= n;i++) { int t,k; read(t),read(k); ,x;i <= k;i++) { read(x); if (!vis[x]) ans++; //若这个乘客是其他国籍,则统计 vis[x]++; //统计 Q.push((Queue){t,x}); //加入队列 } while (true) { //把86400以外的排除 Queue head = Q.front(); + <= head.t && head.t <= t) break; else { vis[head.x]--; if (!vis[head.x]) ans--; Q.pop(); } } printf("%d\n",ans); } ; }
T4
考场上想不出,于是打了个暴力,40分......
40分考场暴力代码
#include <cstdio>
int main() {
],ans[][];
scanf("%d%d",&n,&m);
;i <= m;i++) scanf("%d",&x[i]);
;a <= m;a++)
;b <= m;b++)
if (a != b)
;c <= m;c++)
if (c != a && c != b && (double)x[b]-(double)x[a] < (double)((double)x[c]-(double)x[b])/3.0)
;d <= m;d++)
*(x[d]-x[c])) {
ans[a][]++;
ans[b][]++;
ans[c][]++;
ans[d][]++;
}
;i <= m;i++) printf(],ans[i][],ans[i][],ans[i][]);
;
}
4重循环是用不到n的,没有白给的条件,没有没用的数据!!!
我们可以把这4个数看作是个数轴上的点,根据题目给的条件,可知AB=2*CD,BC>6*CD,AD>9*CD
那么,我们只需要确定D,就可以确定C点,然后再找AB。我们也可以通过找C来确定ABD。
100分代码
#include <cstdio> int main() { ],ans[][]; scanf("%d%d",&n,&m); ;i <= m;i++) scanf("%d",&x[i]); ;a <= m;a++) ;b <= m;b++) if (a != b) ;c <= m;c++) if (c != a && c != b && (double)x[b]-(double)x[a] < (double)((double)x[c]-(double)x[b])/3.0) ;d <= m;d++) *(x[d]-x[c])) { ans[a][]++; ans[b][]++; ans[c][]++; ans[d][]++; } ;i <= m;i++) printf(],ans[i][],ans[i][],ans[i][]); ; }
4重循环是用不到n的,没有白给的条件,没有没用的数据!!!
#include <cstdio> ],vis[],a[],b[],c[],d[]; int main() { freopen("magic.in","r",stdin); freopen("magic.out","w",stdout); scanf("%d%d",&n,&m); ;i <= m;i++) { scanf("%d",&x[i]); vis[x[i]]++; //把所有数记在数轴上 } ;i <= n/;i++) { //枚举CD的长度 ; +;j <= n;j++) { sum += vis[j-(*i+)]*vis[j-(*i+)+*i]; d[j] += sum*vis[j-i]; c[j-i] += sum*vis[j]; } sum = ; *i+);j >= ;j--) { //枚举CD两点,确定AB的个数 sum += vis[j+(*i+)]*vis[j+(*i+)-i]; a[j] += sum*vis[j+*i]; b[j+*i] += sum*vis[j]; } } ;i <= m;i++) printf("%d %d %d %d\n",a[x[i]],b[x[i]],c[x[i]],d[x[i]]); ; }