2018清北学堂普及组冲刺班6连考总结反思
DAY 1
Problem 1 A(A.cpp/c/pas)
【题目描述】
给出一个n*m的网格，其中小明初始站在（x，y）这个位置，网格内无障碍，小明可以向上下左右四个方向一步走一格，问小明最少走几步可以走出网格。
【输入格式】
输入文件A .in
第一行四个整数n，m，x，y。
【输出格式】
输出文件A.out
一行一个整数表示答案。
【样例输入】
3 3 2 2
【样例输出】
2
【数据范围】
对于 30% 数据 n,m<=3
对于 50% 数据 n,m<=1000
对于 100% 数据 n,m<=1000000000，1<=x<=n,1<=y<=m;
想法：很简单的一道题目，但是我想多了，广搜也会超时呀！！！
源代码
#include <bits/stdc++.h>
using namespace std;
int dx[5]={0,0,-1,0,1};
int dy[5]={0,-1,0,1,0};
struct node
{
long x;
long y;
long ans;
}p,q;
long start_x,start_y,n,m;
int main()
{
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
cin>>n>>m>>start_x>>start_y;
if (start_x < 1 || start_y < 1 || start_x > n || start_y > m)
{
cout<<0;
return 0;
}
queue <node> line;
p.x = start_x;
p.y = start_y;
p.ans = 0;
line.push(p);
while (!line.empty())
{
p = line.front();
// if (p.x == n && p.y == m)
// {
// cout<<p.ans;
// break;
// }
p.ans++;
for (int i = 1; i <= 4; i++)
{
q = p;
int xx = p.x + dx[i];
int yy = p.y + dy[i];
q.x = xx;
q.y = yy;
if (xx < 1 || xx > n || yy < 1 || yy > m)
{
cout<<p.ans<<endl;
return 0;
}
line.push(q);
}
line.pop();
}
}
//50分qoq
我还是搜索写上头了QAQ
std：
#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,ans1,ans2;
int main()
{
cin>>n>>m>>x>>y;
//我也想到直接判断直线距离了呀 哎。。。可惜
ans1 = min(x,abs(x-n));
ans2 = min(y,abs(y-m));
cout<<min(ans1,ans2)+1;
return 0;
}
//当时只想装一下b，然后就没有然后了
反思：要注意审题，对合适的题型使用合适的算法，不要再犯这样坑爹的低级错误了
Problem 2 B(B.cpp/c/pas)
【题目描述】
Lucy家门前的大街上有n家店，lucy是一个喜欢收藏机械键盘的女孩子，这n家店中第i家店卖的键盘价格为V[i]，lucy前前后后有q天心血来潮买电脑，其中第i次买电脑的预算是K[i]，问每一次有多少店的键盘能供lucy选择，能选择当且仅当该店的键盘价格小于等于lucy的预算。
【输入格式】
输入文件B.in。
输入文件第一行两个整数n，q。
接下来一行n个整数，其中第i个整数为V[i]。
第q行每行一个整数K代表该次买电脑的预算。
【输出格式】
输出文件B.out。
输出文件q行，第i行表示第i次买电脑，能有多少家店可供选择。
【样例输入】
6 3
6 5 4 3 2 1
1
3
5
【样例输出】
1
3
5
【数据范围】
对于30%的数据，n，q<=1000。
对于另外30%的数据，n,q<=100000，0<=V[i],K[i]<=100000
对于100%的数据，
n<=100000,m<=100000,0<=V[i],K[i]<=10^9。
想法：自己上来就写了，没看清数据范围QAQ（看清了也写不来 ） 这题是二分呀！！！
源代码
#include <bits/stdc++.h>
using namespace std;
long a[100009],n,q,k,b[100009];
long total;
int main()
{
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
cin>>n>>q;
if (n == 0)
{
for (int i = 1; i <= q; i++)
cout<<0<<endl;
return 0;
}
for (int i = 1; i <= n; i++)
cin>>a[i];
sort(a+1,a+n+1);
for (int i = 1; i <= q; i++)
cin>>b[i];
for (int i = 1; i <= q; i++)
{
total = 0;
for (int j = 1; j <= n; j++)
if (b[i] >= a[j]) total++;
else
break;
cout<<total<<endl;
}
return 0;
}
//30分（楼下风景不错，马上下去，快上天台了）
std：
#include <bits/stdc++.h>
using namespace std;
int n,q,k;
int a[100009];
int main()
{
cin>>n>>q;
for (int i = 1; i <= n; i++)
cin>>a[i];
sort(a+1,a+n+1);
for (int i = 1; i <= q; i++)
{
cin>>k;
int p = upper_bound(a+1,a+n+1,k)-a; //二分函数，找到大于的返回
cout<<k<<endl;
}
return 0;
}
反思：要注意看范围 要注意看范围 要注意看范围（重要的事情说3遍），要加强对二分的练习
Problem 3 C(C.cpp/c/pas)
【题目描述】
有一个无限范围的蜂窝状的网格，小明决定在这个网格中探险。
我们看一下这一张图，来看整个网格的坐标结构。
小明从（0，0）点出发，按照旋涡状移动（见下图），求移动n步后，小明所处的坐标。
【输入格式】
输入文件C.in
输入一行一个整数n。
【输出格式】
输出文件C.out
输出一行两个整数x，y表示小明n步之后所处的坐标。
【样例输入1】
3
【样例输出1】
-2 0
【样例输入2】
7
【样例输出2】
3 2
【数据范围】
对于30%的数据，n<=30；
对于50%的数据，n<=500；
对于100%的数据，n<=10^18;
std:
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int up=577350270;
ll n,rest,x,y;
int main()
{
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
scanf("%I64d",&n);
if (n==0) {printf("0 0");return 0;}
int l=1,r=up,mid,ans;
while (l<=r)
{
mid=(l+r)>>1;
if (3ll*mid*(mid+1)>=n) ans=mid,r=mid-1;else l=mid+1;
}
rest=n-3ll*ans*(ans-1);rest--;
x=ans*2-1,y=2;
if (rest<ans)
{
x-=rest;
y+=2*rest;
}
else
{
x-=ans-1;
y+=2*(ans-1);
rest-=ans-1;
if (rest<=ans) x-=2*rest;
else
{
x-=ans*2;
rest-=ans;
if (rest<=ans)
{
x-=rest;
y-=2*rest;
}
else
{
x-=ans;
y-=2*ans;
rest-=ans;
if (rest<=ans)
{
x+=rest;
y-=2*rest;
}
else
{
x+=ans;
y-=2*ans;
rest-=ans;
if (rest<=ans) x+=2*rest;
else
{
x+=2*ans;
rest-=ans;
x+=rest;
y+=2*rest;
}
}
}
}
}
printf("%I64d %I64d",x,y);
return 0;
}
//dalao代码，没啥想说的