这次测试规模较小，前两题也较水，但需要整理
T1(Jelly的男♂难题1)：
从一个点出发，以四连通的方式扩散，可以走#，不能走o，走过的格子每单位时间会增加1点高度，问扩散完整间屋子需要的时间，以及此时高度的和。
并且（起点格不算高度）
water_lift一看：哇，钻出来一个光头这不s*题吗，
然后爆0了...
这题一看就是喜闻乐见的广搜题,判断由来就是众所周知,当每一步的花费一致并且求最小步数时,用广搜吧.
正确性白书已给出证明,
对于这道题,最小步数很好求,然而看似剩下了一个问题,实际剩下的是2个问题,其中一个可以调一上午(对菜鸡而言,I can do this all day!!!)
第一个问题就是剩下的求高度总和的问题,对于此问题,只需保存下到达每个格子的步数,最后再用最终步数减去该格步数,再求和,即为答案,
公式看起来这个样子:
\(\sum\limits_{i=1}^{n} \ finalstep(代码中的maxn)-step_i+1\)
还有最后一个问题,就是读入,读入搞不好可以调一天...
原因在于你需要读的地图以字符串形式展现,然而每个字符之间有空格...
也就是说在数据读入时要不断处理字符,空格与换行符,(这就很TM糟心了...)
那么考虑这样两种思路:
将非字符(这里指用于表示地图的标点符号)用while语句除去,既然能跳出while循环就说明读到了字符,那么将字符保存...
要么就是不管\(3*7=2147483648%1000\)全部整行读入,然后逐个分析,处理思路如上...
然后最难的问题就完成咧...
至于为什么可以调一上午夸张手法,下一个
其实就是因为其代码实现很容易手残把标记变量或是指针变量(就是用来标记处理字符串位置的东西)写错或者根本来说忽略了细节,或是根本上的读入错误(比如用了gets)会导致山一样的WA
但这样也有好处:
至少我那天上午学会了cmd 的fc(文件比较)...
fc好啊
忘贴代码了:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct node{
int x,y;
int step;
node(int _x,int _y,int _step):x(_x),y(_y),step(_step){}
};
queue<node> q;
int n,m;
string aa;
char pos[505][505];
bool vis[505][505];
int stp[505][505];
int sx,sy;
int mx[5]={0,-1,0,1,0};
int my[5]={0,0,1,0,-1};
int main(){
scanf("%d%d",&n,&m);
char ch=getchar();
while(ch!='\n') ch=getchar();
for(int i=1;i<=n;i++){
getline(cin,aa);
int t=0;
int s=0;
while(t<aa.size()){
if(aa[t]=='*'||aa[t]=='#'||aa[t]=='o')
pos[i][++s]=aa[t];
if(pos[i][s]=='*'){
sx=i;
sy=s;
}
t++;
}
}
vis[sx][sy]=1;
q.push(node(sx,sy,0));
int maxn=0;
while(!q.empty()){
node u=q.front();
q.pop();
for(int i=1;i<=4;i++){
int nx=u.x+mx[i];
int ny=u.y+my[i];
if(nx<=0||n<nx) continue;
if(ny<=0||m<ny) continue;
if(pos[nx][ny]=='#'&&!vis[nx][ny]){
vis[nx][ny]=1;
stp[nx][ny]=u.step+1;
maxn=max(stp[nx][ny],maxn);
q.push(node(nx,ny,u.step+1));
}
}
}
int sum=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i==sx&&j==sy)continue;
if(vis[i][j])
sum+=(maxn-stp[i][j]+1);
sum%=19260817;
}
}printf("%d\n%d\n",maxn,sum);
return 0;
}T2(【音乐会】二重变革):
MD数据范围:
对于20%的数据，\(1\leq n\leq10000\)
对于100%的数据，\(1.5e6\leq n\leq 2e6\ 1\leq X[i] \leq 1e9\)且不保证随机生成
一看把代码贴上去就是T的吗?!
这题真正思路是搞exgcd上去,
证明(黈):
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int x;
inline int read(){
int x=0;
char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x;
}
inline int gcd(const int &a,const int &b){
if(b==0) return a;
return gcd(b,a%b);
}
int ans;
int main(){
scanf("%d",&n);
ans=read();
for(int i=2;i<=n;i++){
x=read();
ans=gcd(ans,x);
}
printf("%d",ans*n);
return 0;
}前两题就这样啦