NOIP2018 普及组全国热身赛 第四场
先来看一下我这个蒟蒻的成绩吧……
第四名这个就是我啦
其实我那个名字的意义呢——如下图所示
算了我我我不瞎扯了
以下内容为正文
————————————————分割线—————————————————
A. Hello, A * B
WZB刚学习了输入输出,他遇到了一道这样的题目。
输入2个整数a和b
保证输入的a和b在long long范围之内,即满足
−9223372036854775808≤a,b≤9223372036854775807
计算a∗b的值,即这两个数字的乘积。
如果a∗b在 long long 范围之内,即满足−9223372036854775808≤a∗b≤9223372036854775807
那么输出一行一个整数表示a∗ba∗b的结果。
如果a∗ba∗b不在long long范围之内,即越界了,那么输出"\b",不包含引号。
输入描述
输入只有一行,包含用空格分开的两个整数,表示a和b。
输出描述
如果a * b在long long范围之内,输出一行一个整数,表示a * b的结果;否则输出"\b",不包含引号。
样例输入1
4294967296 2147483648
样例输出1
\b
样例输入2
4294967296 -2147483648
样例输出2
-9223372036854775808
数据规模与约定
正确计算a∗b可以得到50分
正确输出"\b"也可以得到50分
这道题的思路很简单,T1大水题嘛,先计算他们乘积,再用乘积除以一个数,看它等不等于另一个数,如果等于直接输出,否则……你懂的
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int main()
{
long long a,b,c;
scanf("%lld %lld",&a,&b);
c=a*b;
if(c/a==b) printf("%lld",c);
else printf("\\b");
return 0;
}
B. 去年今日
输入一个日期(年月日)
输出这个日期365天之前的日期(年月日)是什么
输入描述
输入一个日期,共8个数字,以yyyymmdd的格式输入。
前4位数字表示年份,第5位和第6位表示月份,第7位和第8位表示日期。
输出描述
输出一个日期,共8个数字,以yyyymmdd的格式输出。
前4位数字表示年份,第5位和第6位表示月份,第7位和第8位表示日期。
样例输入
20181101
样例输出
20171101
数据规模与约定
保证输入日期合法,年份的范围是1901到2400(两端都包括)
对于50%的数据,月日部分一定是11月11日。
这道题想特判过去是基本不可能的,最多50~70,为什么不行?因为你不可能考虑得那么全面,所以呢……万事暴力为先
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int yue[15]={0,31,250,31,30,31,30,31,31,30,31,30,31,0};
bool judge(int o)
{
if(o%4==0)
{
if((o%100==0&&o%400!=0)||o%3200==0) return false;
else return true;
}
else return false;
return 0;
}
int main()
{
int a,b,c;
scanf("%4d %2d %2d",&a,&b,&c);
for(int i=1;i<=365;i++)
{
c--;
if(!c)
{
b--;
if(yue[b]!=250) c=yue[b];
else
{
if(judge(a)) c=29;
else c=28;
}
}
if(!b)
{
a--;
b=12;
c=yue[12];
}
}
int ans;
ans=a*10000+b*100+c;
printf("%d",ans);
return 0;
}
C. 最长公共子序列
输入两个数字序列,求最长公共子序列的长度。
输入描述
第一行一个n
接下来一行n个数字,表示第一个数字序列ai。
接下来一行n个数字,表示第二个数字序列bi。
输出描述
输出一行一个数字,表示最长公共子序列的长度
样例输入
6
1 2 3 3 2 1
1 2 3 1 2 3
样例输出
4
数据规模与约定
对于100%的数据,n≤3e5,1≤ai, bi≤n,每个数字在序列ai中最多出现三次。
对于30%的数据,n≤3e3
对于另30%的数据,每个数字在序列ai中最多出现一次。
加了个滚动数组优化还是暴零了,但是……样例党万岁
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int dp[2][300005];
char a[300005],b[300005];
int main()
{
int i,j,n;
bool now,pre;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
for(now=1,pre=0,i=0;i<n;i++)
for(swap(now,pre),j=0;j<n;j++)
if(a[i]==b[j]) dp[now][j+1]=dp[pre][j]+1;
else
dp[now][j+1]=dp[pre][j+1]>dp[now][j]?dp[pre][j+1]:dp[now][j];
printf("%d\n",dp[now][n]);
return 0;
}
D. 扫雷
相信大家都玩过windows下的小游戏扫雷。
考虑在一个n x m的棋盘上玩扫雷,行列都从1开始下标,已知所有c个雷的位置,第i个的位置是xi,yi。
对于每个k(0≤k<9)输出有多少个格子,在8个方向上共有k个雷。
输入描述
输入第一行三个整数n, m, c。
接下来c行,每行两个整数x, y表示雷的位置。
输出描述
输出共9个数字,其中第k(0≤k≤9)k(0≤k≤9)个数字表示,有多少个格子,在8个方向上共有k个雷。
样例输入
3 3 4
1 1
3 3
1 3
3 1
样例输出
0
0
4
0
1
0
0
0
0
数据规模与约定
对于100%的数据,n,m≤1e9, c≤1e5, 1≤xi≤n, 1≤yi≤m,输入的c个雷的位置互不相同。
对于30%的数据,n,m≤1e3
对于另30%的数据,c≤1e3
对于一个普及组的蒟蒻,
离散化和map函数再维护一下就OK了,有30分就已经可以满足了,思路很简单:1.找到点 2.计算和 3.桶排 4.输出
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
char mmap[10001][10001];
int box[10];
int dx[10]={0,0,0,1,-1,1,-1,1,-1};
int dy[10]={0,1,-1,0,0,1,-1,-1,1};
int dfs(int x,int y)
{
int s=0;
for(int i=1;i<=8;i++)
{
int sx=x+dx[i];
int sy=y+dy[i];
if(mmap[sx][sy]=='o') s++;
}
return s;
}
int main()
{
int n,m,c;
int x,y;
scanf("%d %d %d",&n,&m,&c);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
mmap[i][j]='x';
for(int i=1;i<=c;i++)
{
scanf("%d %d",&x,&y);
mmap[x][y]='o';
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mmap[i][j]!='o') box[dfs(i,j)]++;
for(int i=0;i<9;i++)
printf("%d\n",box[i]);
return 0;
}