欢乐赛解题报告
2018-06-17 22:32:51来源：未知 阅读 ()
~~一场不欢乐的欢乐赛
时间分配：：T1做的时候还可以，大约三十分钟写了个深搜（鬼知道我为啥不用广搜，大概是因为快半个月没写了）写完后去研究第二题，刚开始以为是贪心，很快写了出来，但是自己推了一会举出了反例。于是自己想了很多方法，但是都是基于贪心，写了一个多小时，写炸了，没办法又改成了贪心。第三题并不会，然后搜索大法过了一个点，（输出-1也是一个点）
整体感觉：：还是太弱，T1是会的，但是还是没做对，大概是独立做题少的缘故吧，平常做题都没有思考太多时间。T2贪心T3暴力，貌似自己啥都不会。到现在第三题好像快要放弃了，题解一点也，看不懂。
题目解析：：
T1：：
水灾（sliker.cpp/c/pas） 1000MS 64MB
大雨应经下了几天雨，却还是没有停的样子。土豪CCY刚从外地赚完1e元回来，知道不久除了自己别墅，其他的地方都将会被洪水淹没。
CCY所在的城市可以用一个N*M(N,M<=50)的地图表示，地图上有五种符号：“. * X D S”。其中“X”表示石头，水和人都不能从上面经过。“.”表示平原，CCY和洪水都可以经过。“*”表示洪水开始地方（可能有多个地方开始发生洪水）。“D”表示CCY的别墅。“S”表示CCY现在的位置。
CCY每分钟可以向相邻位置移动，而洪水将会在CCY移动之后把相邻的没有的土地淹没（从已淹没的土地）。
求CCY回到别墅的最少时间。如果聪哥回不了家，就很可能会被淹死，那么他就要膜拜黄金大神涨RP来呼叫直升飞机，所以输出“ORZ hzwer!!!”。
----------------------------------------------------------------------------------------------------------------------
洪水的强化的强化版，关键处在于人在走第不同的步数时洪水的状态时不同的，在走相同步数时洪水的状态是相同的。通过这个我们可以先推导出人在走第n步时的洪水状态。之后
广搜，条件是下一步要走到的位置洪水没有覆盖且没走过且是‘。’的点。
第一遍做时用的深搜，半个月没写广搜了，思维惯性，T了6个点
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char map[1500][61][61];
bool hsvisited[61][61];
bool renvisited[61][61];
int xgo[4]={1,-1,0,0};
int ygo[4]={0,0,1,-1};
int nowx;int nowy;int fx;int fy;int n;int m;int ans=0x7ffffff;
void dfs(int step,int x,int y)
{
//if(map[step][x][y]=='*')return;//合理化剪枝 算了放循环里吧
if(x==fx&&y==fy)
{
ans=min(step,ans);
return;
}
if(step>ans)return; //最优化剪枝
for(int i=0;i<4;i++)
{
int xn=x+xgo[i];
int yn=y+ygo[i];
if(!renvisited[xn][yn]&&(map[step+1][xn][yn]=='.'||map[step+1][xn][yn]=='D'))
{
renvisited[xn][yn]=true;
dfs(step+1,xn,yn);
renvisited[xn][yn]=false;
}
}
}
int main()
{
freopen("sliker.in","r",stdin);
freopen("sliker.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>map[0][i][j];
if(map[0][i][j]=='S')
{
nowx=i;
nowy=j;
map[0][i][j]='.';
renvisited[i][j]=true;
}
if(map[0][i][j]=='D')
{
fx=i;fy=j;
}
}
for(int z=1;z<=1300;z++) //离线处理 //jiduanqingkuangbukaolvle chutiren meinamewuliao
{
//bool flag=false;
memset(hsvisited,0,sizeof(hsvisited));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(map[z-1][i][j]=='*')
{
for(int op=0;op<4;op++)
{
int xn=i+xgo[op];
int yn=j+ygo[op];
if(map[z-1][xn][yn]=='.')
{
hsvisited[xn][yn]=1;
//flag=true; 这个不能加
}
}
}
map[z][i][j]=map[z-1][i][j];
}
//if(!flag)break;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(hsvisited[i][j])
map[z][i][j]='*';
}
}
dfs(0,nowx,nowy);
if(ans==0x7ffffff)
printf("ORZ hzwer!!!");
else
printf("%d",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
/*
3 3
D.*
...
.S.
*/
/*
3 3
D.*
...
..S
*/
/*
3 6
D...*.
.X.X..
....S.
3 3
D..
...
..S
*/
第二遍做的时候在原来基础上改成了广搜，就可以了
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct note
{int x;int y;int step;};
char map[1500][61][61];
bool hsvisited[61][61];
bool renvisited[61][61];
int xgo[4]={1,-1,0,0};
int ygo[4]={0,0,1,-1};
int nowx;int nowy;int fx;int fy;int n;int m;
queue<note>q;
int main()
{
freopen("sliker.in","r",stdin);
freopen("sliker.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>map[0][i][j];
if(map[0][i][j]=='S')
{
nowx=i;
nowy=j;
map[0][i][j]='.';
renvisited[i][j]=true;
}
if(map[0][i][j]=='D')
{
fx=i;fy=j;
}
}
for(int z=1;z<=1300;z++) //离线处理 //jiduanqingkuangbukaolvle chutiren meinamewuliao
{
memset(hsvisited,0,sizeof(hsvisited));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(map[z-1][i][j]=='*')
{
for(int op=0;op<4;op++)
{
int xn=i+xgo[op];
int yn=j+ygo[op];
if(map[z-1][xn][yn]=='.')
{
hsvisited[xn][yn]=1;
}
}
}
map[z][i][j]=map[z-1][i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(hsvisited[i][j])
map[z][i][j]='*';
}
}
note zz;
zz.x=nowx;
zz.y=nowy;
zz.step=0;
q.push(zz);
while(!q.empty())
{
note op=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xn=op.x+xgo[i];
int yn=op.y+ygo[i];
int s=op.step;
if((map[s+1][xn][yn]=='.'||map[s+1][xn][yn]=='D')&&!renvisited[xn][yn])
{
renvisited[xn][yn]=1;
note iq;
iq.x=xn;
iq.y=yn;
iq.step=s+1;
if(xn==fx&&yn==fy)
{
printf("%d",iq.step);
return 0;
}
q.push(iq);
}
}
}
printf("ORZ hzwer!!!");
fclose(stdin);
fclose(stdout);
return 0;
}
T2某种数列问题 (jx.cpp/c/pas) 1000MS 256MB
众所周知，chenzeyu97有无数的妹子(阿掉！>_<)，而且他还有很多恶趣味的问题，继上次纠结于一排妹子的排法以后，今天他有非(chi)常(bao)认(cheng)真(zhe)去研究一个奇怪的问题。有一堆他的妹子站成一排，然后对于每个妹子有一个美丽度，当然美丽度越大越好，chenzeyu97妹子很多，但是质量上不容乐观，经常出现很多美丽度为负数的妹子(喜闻乐见)，chenzeyu97希望从一排妹子里找出3队连续的妹子，使她们的美丽度和最大。注意，一个妹子不能被编入多个队伍而且一定要拿出三队，不然czy会闲着没事做~。
简单滴说就是：
给定一个数列，从中找到3个无交集的连续子数列使其和最大。
【输入文件】
第一行一个数n，表示数列长度。
接下来有n行，每行一个数，第i行为第i个数。
【输出文件】
仅有一个数，表示最大和。
方法：：假如在做单一的最大子段和的问题时用的dp解法而不是贪心，做这个题就会容易得多。毕竟只是多了一个条件。
状态：：f【i】【j】【flag】表示到第i个数选了j段妹子并且当前数是否要选的状态
#include<cstdio>
#include<algorithm>
using namespace std;
int note[1000001];
int dp[4][1000001][2];
int read()
{
int f=1;
int num=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
num*=10;
num+=c-'0';
c=getchar();
}
return f*num;
}
int main()
{
freopen("jx.in","r",stdin);
freopen("jx.out","w",stdout);
int n=read();
for(int i=1;i<=n;i++)
{
note[i]=read();
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=3;j++)
{
dp[j][i][0]=max(dp[j][i-1][0],dp[j][i-1][1]);
/*既然当前的的不拿，最大值就和当前无关，只需要判断前一步的最大值*/
dp[j][i][1]=max(dp[j][i-1][1]+note[i],max(dp[j][i][1],dp[j-1][i-1][0]+note[i]));
/*当前的若要拿的话 分两种情况*/
/*与上一个连着 单成一个*/
/*但是如果这两种情况都小于0时还不如不选*/
}
}
printf("%d",max(dp[3][n][1],dp[3][n][0]));
return 0;
}
但是，在考试时这个题想不出来dp的方法，就跑了三遍贪心，竟然过了6个点
#include<cstdio>//本来打算用一种贪心+排序。。。算了，贪心三遍吧 我也知道不对万一碰上呢
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int shuru[1000001];
bool visited[1000001];
int ans=0;
int n,top=0;
int read()
{
int f=1;
int now=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
now*=10;
now+=c-'0';
c=getchar();
}
return f*now;
}
int main()
{
freopen("jx.in","r",stdin);
freopen("jx.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
shuru[i]=read();
for(int z=1;z<=3;z++)
{
int su=-9999999;
int wei;
int ge;
int op=0;
int tot=0;
for(int i=1;i<=n;i++)
{
if(visited[i])
{
op=0;
tot=0;
continue;
}
if(op<0)
{
op=0;
tot=0;
}
op+=shuru[i];
tot++;
if(op>su)
{
su=op;
wei=i;
ge=tot;
}
}
ans+=su;
for(int i=wei-ge+1;i<=wei;i++)
visited[i]=1;
}
printf("%d",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
T3
密码锁 1000MS 512MB
Input: password.in
Output: password.out
【题目描述】
hzwer有一把密码锁，由N个开关组成。一开始的时候，所有开关都是关上的。当且仅当开关x1,x2,x3,...xk为开，其他开关为关时，密码锁才会打开。
他可以进行M种的操作，每种操作有一个size[i]，表示，假如他选择了第i种的操作的话，他可以任意选择连续的size[i]个格子，把它们全部取反。（注意，由于黄金大神非常的神，所以操作次数可以无限>_<）
本来这是一个无关紧要的问题，但是，黄金大神不小心他的钱丢进去了，没有的钱他哪里能逃过被chenzeyu97 NTR的命运？>_< 于是，他为了虐爆czy，也为了去泡更多的妹子，决定打开这把锁。但是他那么神的人根本不屑这种”水题”。于是，他找到了你。
你的任务很简单，求出最少需要多少步才能打开密码锁，或者如果无解的话，请输出-1。
【输入格式】
第1行，三个正整数N，K，M，如题目所述。
第2行，K个正整数，表示开关x1,x2,x3..xk必须为开，保证x两两不同。
第三行，M个正整数，表示size[i]，size[]可能有重复元素。
【输出格式】
输出答案，无解输出-1。
方法：：
方法：：查分序列加状压dp。至少已经听明白差分序列了，知道状压dp要用二进制了，其余的还是不会。
代码：：（撬的）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 10010
using namespace std;
int n,m,k,size[110],a[maxn],c[maxn],s[maxn],cnt,step[110][110];
int f[maxn],dis[maxn],dp[1<<22],inf;
struct node
{
int x,t;
};
queue<node>q;
void Bfs(int S,int o)
{
while(!q.empty())q.pop();
memset(f,0,sizeof(f));
memset(dis,127/3,sizeof(dis));
inf=dis[0];
q.push((node)
{
S,0
});
f[S]=1;
dis[S]=0;
while(!q.empty())
{
node p=q.front();
q.pop();
for(int i=1; i<=k; i++)
{
int y=p.x+size[i];
if(y<=n&&f[y]==0)
{
f[y]=1;
dis[y]=p.t+1;
q.push((node)
{
y,dis[y]
});
}
y=p.x-size[i];
if(y>=1&&f[y]==0)
{
f[y]=1;
dis[y]=p.t+1;
q.push((node)
{
y,dis[y]
});
}
}
}
for(int i=1; i<=cnt; i++)
if(dis[c[i]]<inf)step[o][i]=dis[c[i]];
else step[o][i]=inf;
}
int main()
{
// freopen("password.in","r",stdin);
// freopen("password.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1; i<=m; i++)
{
int x;
scanf("%d",&x);
a[x]++;
}
for(int i=1; i<=k; i++)
scanf("%d",&size[i]);
n++;
for(int i=1; i<=n; i++)
s[i]=a[i]-a[i-1];
for(int i=1; i<=n; i++)
if(s[i])
c[++cnt]=i;
for(int i=1; i<=cnt; i++)
Bfs(c[i],i);
memset(dp,127/3,sizeof(dp));
inf=dp[0];
dp[0]=0;
for(int i=0; i<=(1<<cnt)-1; i++)
{
int j;
for(int k=1; k<=cnt; k++)
if((1<<k-1)&i)
{
j=k;
break;
}
for(int k=1; k<=cnt; k++)
if((1<<k-1)&i)
dp[i]=min(dp[i],dp[i^(1<<j-1)^(1<<k-1)]+step[j][k]);
}
if(dp[(1<<cnt)-1]==inf)printf("-1\n");
else printf("%d\n",dp[(1<<cnt)-1]);
return 0;
}
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
- 2019.3.14解题报告&补题报告 2020-03-22
- 结题报告--hih0CoderP1041 2020-03-17
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 结题报告 2020-03-11
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
