1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MXN=15;
const int NR=55;
const int nxto[4][2]={
{1,0},{-1,0},{0,1},{0,-1}
};
int s,p;
int n,a,b;
int sx,sy;
int tx[MXN],ty[MXN],dt[MXN];
bool map[NR][NR];
int dis[NR][NR][NR][NR];
bool vis[MXN];
int mx=-1;
void dfs(int curx,int cury,int curf,int curcnt){
if(curcnt==0){
if(dis[curx][cury][sx][sy]*p>curf)return;
mx=max(mx,curf-dis[curx][cury][sx][sy]*p);
return;
}
for(int i=1;i<=n;i++){
if(vis[i])continue;
if(dis[curx][cury][tx[i]][ty[i]]*p>curf)continue;
vis[i]=1;
dfs(tx[i],ty[i],curf+dt[i]-dis[curx][cury][tx[i]][ty[i]]*p,curcnt-1);
vis[i]=0;
}
return;
}
int main(){
scanf("%d%d%d",&s,&p,&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",tx+i,ty+i,dt+i);
scanf("%d%d",&a,&b);
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++)
scanf("%d",&map[i][j]);
scanf("%d%d",&sx,&sy);
//floyd
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++){
dis[i][j][i][j]=0;
if(!map[i][j])continue;
for(int tmp=0;tmp<4;tmp++){
int nx=i+nxto[tmp][0];
int ny=j+nxto[tmp][1];
if(nx<1 || ny<1 || nx>a || ny>b)continue;
if(map[nx][ny])dis[i][j][nx][ny]=1;
}
}
//mid
for(int kx=1;kx<=a;kx++)
for(int ky=1;ky<=b;ky++){
if(!map[kx][ky])continue;
//start
for(int x1=1;x1<=a;x1++)
for(int y1=1;y1<=b;y1++){
if(!map[x1][y1])continue;
//end
for(int x2=1;x2<=a;x2++)
for(int y2=1;y2<=b;y2++){
if(!map[x2][y2])continue;
dis[x1][y1][x2][y2]=min(\
dis[x1][y1][x2][y2],\
dis[x1][y1][kx][ky]+dis[kx][ky][x2][y2]);
}
}
}
memset(vis,0,sizeof(vis));
dfs(1,1,s,n);
printf("%d\n",mx);
return 0;
}
|
我用了一种不是很暴力的模拟，即按照1位，2位，3位…来统计长度，却莫名其妙的错了一个点，也许是极端情况程序被卡了。
纯暴力题目，枚举所有可能的a，b算出c，再计算不同的位数，最后取最小即可
这题爆炸了。。。
本来期望用二分加上搜索得到60分，在适当加优化。结果脑子抽抽，二分的逻辑搞混了，加上搜索时写成了找路径的搜索，最后只得15分，很不满意。
这题没太理解题意，也没算出来，于是输出样例，0分
虽然排名还行（大家都炸了），但自我感觉这次考试发挥很不理想，主要因为第3题调太久了，结果最后还错了。加上好久没弄noilinux，环境不熟悉，还忘记了我的vimrc。现场重新想的，十分浪费时间，以后要搞清轻重主次，记不住就用guide吧。
字符串处理题，就直接一位一位判断
模拟，读入第i位时，如果这位不是零，就将数组的第i项和n-i+1项赋值为这个数即可
这题因为数学不好所以没算出来。
老师说这个数列跟肥不拉几数列有许多关联，包括第i个数列的0与1的个数等等。最后正解好像是利用每个数列都等于前两个数列之和进行二分。然而我连暴力模拟都没敲出来，有些可惜。
搜索题，我首先用floyd（简单易学）预处理出来了每两个宝藏之间的距离，接着用dfs全排列求出所有的路径（路上经过宝藏的顺序），接着用前面预处理出来的东西计算总路程。
最坏复杂度$O(a^3\times b^3+N!)$，t了一个点,90分（劲爆6重循环）