CSP2019 备战计划-9

Task:pj试炼场2-7(续)

T5 P1040

并不需要多少剪枝的深搜

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
#include<bits/stdc++.h>
using namespace std;
int n,dp[50][50],rt[50][50],m[50];
int dfs(int l,int r)
{
if(dp[l][r]>0)return dp[l][r];
if(l>r)return 1;
if(l==r)return m[r];
for(int i=l;i<=r;i++)
if(dfs(l,i-1)*dfs(i+1,r)+dp[i][i]>dp[l][r])
dp[l][r]=dfs(l,i-1)*dfs(i+1,r)+dp[i][i],rt[l][r]=i;
return dp[l][r];
}
void p(int l,int r)
{
if(l>r)return;
if(l==r){cout<<l<<" ";return;}
cout<<rt[l][r]<<" ";
p(l,rt[l][r]-1);
p(rt[l][r]+1,r);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>m[i];
for(int i=1;i<=n;i++)dp[i][i]=m[i];
cout<<dfs(1,n)<<endl;
p(1,n);
}

!!!T6 P1092

写不出来,鸽了

毕竟是tg第四题,真难


Task:pj试炼场2-8

T1 P1162

一道普及-居然卡了这么久。。。

特别要注意像这种数据的情况

1
2
3
4
5
6
7
6
0 0 1 1 1 0
1 1 1 0 1 0
1 0 0 0 0 1
1 1 0 1 1 1
0 1 0 1 0 0
0 1 1 1 0 0

因为这个环把整张图分成了独立的几小块,如果只从左上角搜就会出不去

所以要偷偷地扩大一下,变成这样

1
2
3
4
5
6
7
8
  0 0 0 0 0 0
0 0 0 1 1 1 0 0
0 1 1 1 0 1 0 0
0 1 0 0 0 0 1 0
0 1 1 0 1 1 1 0
0 0 1 0 1 0 0 0
0 0 1 1 1 0 0 0
0 0 0 0 0 0

实际输出不要管加上去的

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
#include<bits/stdc++.h>
using namespace std;
int mapp[35][35];
int m[35][35];
int qx[5]={0,0,-1,1};
int qy[5]={1,-1,0,0};
int n;
int dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int nx=x+qx[i];
int ny=y+qy[i];
if(nx<=n+1&&ny<=n+1&&nx>=0&&ny>=0&&m[nx][ny]==0)
{
m[nx][ny]=2;
dfs(nx,ny);
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>mapp[i][j];
if(mapp[i][j]==1)m[i][j]=1;
}
dfs(1,1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
if(m[i][j]==0)cout<<2<<" ";
else cout<<mapp[i][j]<<" ";
cout<<endl;
}
}

T2 P1032

请注意细节。。。

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
#include<bits/stdc++.h>
using namespace std;
struct node
{
string s;
int step;
};
int n;
string a,b;
string x,y,s1[20],s2[20];
map<string,int> mapp;
string ans;
string change(string &s,int i,int j)//第i位用第j种方法替换
{
ans="";
if(i+s1[j].length()>s.length())return ans;
for(int k=0;k<s1[j].length();k++)if(s[i+k]!=s1[j][k])return ans;
return ans=s.substr(0,i)+s2[j]+s.substr(i+s1[j].length());
}
int sum;
void bfs()//模板搜索
{
queue<node>q;
node s;
s.s=a,s.step=0;
q.push(s);
while(q.size())
{
s=q.front();
q.pop();
string t;
if(mapp.count(s.s)==1)continue;
if(s.s==b)
{
sum=s.step;
break;
}
mapp[s.s]=1;
for(int i=0;i<s.s.length();i++)
for(int j=0;j<n;j++)
{
t=change(s.s,i,j);
if(t!="")
{
node x;
x.s=t;
x.step=s.step+1;
q.push(x);
}
}
}
if(sum>10||sum==0)cout<<"NO ANSWER!"<<endl;//没有看到这个10,所以卡了很久
else cout<<sum<<endl;
}
int main()
{
cin>>a>>b;
while(cin>>s1[n]>>s2[n])n++;//还不给你组数。。。
bfs();
}

T3 P1141

模板BFS(这次是毒瘤码风)

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
#include<bits/stdc++.h>
using namespace std;
int mapp[1010][1010],qx[4]={1,-1,0,0},qy[4]={0,0,-1,1},n,m,x,y,sum,tot,t[1000010],vis[1010][1010];
void dfs(int x,int y,int tot)
{
for(int i=0;i<4;i++)
{
int xx=x+qx[i];
int yy=y+qy[i];
if(mapp[xx][yy]!=mapp[x][y]&&vis[xx][yy]==0&&xx>=1&&yy>=1&&xx<=n&&yy<=n)
{
sum++;
vis[xx][yy]=tot;
dfs(xx,yy,tot);
}
}
}
void check()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(vis[i][j]==0)
{
tot++;
sum=1;
vis[i][j]=tot;
dfs(i,j,tot);
t[tot]=sum;
}
}
}
}
void in()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%1d",&mapp[i][j]);
}
void prin()
{
while(m--)
{
cin>>x>>y;
cout<<t[vis[x][y]]<<endl;
}
}
int main()
{
in();
check();
prin();
}