第一次区域赛网赛啊,果然离现场赛还有一大截啊,今天就做出两题,其实那两题我也不太懂,唉,说多了都是累,补题补题。
9-15更新,赛后补题的时候发现自己的锅很大啊!!!!!!两道题都存在一个非常小的bug,改起来一分钟都不到!!!!!
第一次区域赛网赛啊,果然离现场赛还有一大截啊,今天就做出两题,其实那两题我也不太懂,唉,说多了都是累,补题补题。
9-15更新,赛后补题的时候发现自己的锅很大啊!!!!!!两道题都存在一个非常小的bug,改起来一分钟都不到!!!!!
自己队举办的模拟赛,这次比赛也算是告诉我自己离区域赛的水平还有多远吧,靠队友实力划水了5小时,醉了,把自己现在有能力做的补上先。
题目网址在此
##Wang Xifeng’s Little Plot
题意很简单,要在给出的图中找到一条路,这条路的方向可以是八个方向中的任意一个,而且这条路只能有一个拐弯处,弯角必须是直角。学姐当时给我的做法是枚举每个点的每一个方向,一直贪心就行了,一开始我挺质疑复杂度的,但是没别的好思路也就不劝阻了,结果一发wa,然后开始debug,ORZ由于学姐的代码过于诡异我竟然没有发现判断越界的时候写错符号了,浪费了两个小时,我的锅啊!
#include<bits/stdc++.h>
#define ll long long
using namespace std;
char mapp[105][105];
int n,maxx;
void poi(int x,int y)
{
int w1 = 0,w2 = 0,w3 = 0,w4 = 0,w5 = 0,w6 = 0,w7 = 0,w8 = 0;
for(int i = 1;;i++)
{
if(x + i == n || y + i == n || mapp[x + i][y + i] != '.')
break;
w1++;
}
for(int i = 1;;i++)
{
if(x + i == n || y - i < 0 || mapp[x + i][y - i] != '.')
break;
w2++;
}
for(int i = 1;;i++)
{
if(x - i < 0 || y + i == n || mapp[x - i][y + i] != '.')
break;
w3++;
}
for(int i = 1;;i++)
{
if(x - i < 0 || y - i < 0 || mapp[x - i][y - i] != '.')
break;
w4++;
}
for(int i = 1;;i++)
{
if(x + i == n || mapp[x + i][y] != '.')
break;
w5++;
}
for(int i = 1;;i++)
{
if(x - i < 0 || mapp[x - i][y] != '.')
break;
w6++;
}
for(int i = 1;;i++)
{
if(y + i == n || mapp[x][y + i] != '.')
break;
w7++;
}
for(int i = 1;;i++)
{
if(y - i < 0 || mapp[x][y - i] != '.')
break;
w8++;
}
w2 = max(w2,w3);
w1 = max(w1,w4);
w5 = max(w5,w6);
w7 = max(w7,w8);
maxx = max(maxx,w1 + w2 + 1);
maxx = max(maxx,w5 + w7 + 1);
}
int main(){
while(cin >> n && n)
{
maxx = 0;
for(int i = 0;i < n;i++)
{
for(int j = 0;j < n;j++)
{
cin >> mapp[i][j];
}
}
for(int i = 0;i < n;i++)
{
for(int j = 0;j < n;j++)
{
if(mapp[i][j] == '.')
{
poi(i,j);
}
}
}
cout << maxx << endl;
}
return 0;
}
##Saving Tang Monk
其实也不算难啊,模拟赛的时候有点自暴自弃地觉得自己就是写不了这种广搜,就放弃了,网赛的时候不能放弃了。题意就是唐僧被白骨精抓走辣,然后悟空要去救师傅,给你一个图,K代表起点,T代表师傅所在地,有N种钥匙,用数字1~9表示,还有不超过14条蛇,用S代表,一条蛇杀一次就会死,想要拿到第N把要是要把N-1把钥匙先拿到,拿到全部的钥匙之后才能再救到师傅。状压一下再广搜就行了。
写了一个晚上终于过了样例尼玛竟然给我各种T,调试半小时无果,先扔代码,明天有时间再找学长debug一下吧,我自认为是没啥问题了啊!
还有就是我竟然又忘记优先队列如何自定义排序规则了……真的是老了啊
9-11更新,bug找到了,判断蛇的情况的时候我写成了if(temp.snake >>j)忘记了右移j位后可能还有好几位,谨记。
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#define ll long long
using namespace std;
char mapp[105][105];
int n,m,stx,sty,edx,edy,vis[105][105][10][33],rx[] = {1,-1,0,0},ry[] = {0,0,1,-1},cnt;
struct node
{
int x,y,time,key,snake;
friend bool operator <(node a,node b)
{
return a.time > b.time;
}
};
struct nodd
{
int x,y;
}sn[10];
int bfs()
{
priority_queue<node> q;
node stt;
stt.x = stx,stt.y = sty,stt.time = 0,stt.key = 0,stt.snake = 0;
q.push(stt);
vis[stx][sty][0][0] = 1;
while(!q.empty())
{
node te = q.top();
q.pop();
if(te.x == edx && te.y == edy && te.key >= m)
{
return te.time;
}
for(int i = 0;i < 4;i++)
{
node temp = te;
int nx = temp.x + rx[i],ny = temp.y + ry[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= n)
continue;
if(vis[nx][ny][temp.key][temp.snake])
continue;
if(mapp[nx][ny] == '#')
continue;
if(mapp[nx][ny] == 'S')
{
for(int j = 0;j < cnt;j++)
{
if(nx == sn[j].x && ny == sn[j].y)
{
if((temp.snake >> j) % 2 == 1)
{
temp.time++;
temp.x = nx,temp.y = ny;
vis[nx][ny][temp.key][temp.snake] = 1;
q.push(temp);
}
else
{
temp.snake += (1 << j);
temp.time += 2;
temp.x = nx,temp.y = ny;
vis[nx][ny][temp.key][temp.snake] = 1;
q.push(temp);
}
break;
}
}
}
else if(mapp[nx][ny] >= '1' && mapp[nx][ny] <= '9')
{
if(temp.key + 1 == mapp[nx][ny] - '0')
{
temp.key++;
}
temp.time++;
temp.x = nx,temp.y = ny;
vis[nx][ny][temp.key][temp.snake] = 1;
q.push(temp);
}
else
{
temp.x = nx,temp.y = ny;
temp.time++;
vis[nx][ny][temp.key][temp.snake] = 1;
q.push(temp);
}
}
}
return -1;
}
int main(){
while(cin >> n >> m && (n || m))
{
cnt = 0;
memset(vis,0,sizeof(vis));
memset(sn,0,sizeof(sn));
for(int i = 0;i < n;i++)
{
getchar();
for(int j = 0;j < n;j++)
{
scanf("%c",&mapp[i][j]);
if(mapp[i][j] == 'K')
stx = i,sty = j;
else if(mapp[i][j] == 'T')
edx = i,edy = j;
else if(mapp[i][j] == 'S')
{
sn[cnt].x = i,sn[cnt].y = j;
cnt++;
}
}
}
int ss = bfs();
if(ss == -1)
cout << "impossible\n";
else
cout << ss << endl;
}
return 0;
}
##Lines
题意就是给你一个格子图,每个格子上标记了这个格子被几条线穿过,要求最少划几条线就能满足整个图的标记值。