NOIP2019 pj备战计划-7

Task:pj试炼场2-7

T1 P1219

经典的八皇后,练回溯的好题目

弄个vis数组记录可不可行,回溯时改成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
#include<bits/stdc++.h>
using namespace std;
int n,cnt;
int a[100];
bool vis[100][5];
void print(int x)
{
for(int i=1;i<=x;i++)cout<<a[i]<<" ";
cout<<endl;
}
void dfs(int l)
{
if(l>n)cnt++;
if(l>n&&cnt>3)return;
if(l>n&&cnt<=3){print(n);return;}
for(int i=1;i<=n;i++)
{
if(vis[i][0]==0&&vis[i+l][1]==0&&vis[l-i+n][2]==0)
{
a[l]=i;
vis[i][0]=vis[i+l][1]=vis[l-i+n][2]=1;
dfs(l+1);
vis[i][0]=vis[i+l][1]=vis[l-i+n][2]=0;
}
}
}
int main()
{
cin>>n;
dfs(1);
cout<<cnt<<endl;
}

T2 P1019

没什么好说的,题目有点小坑就是那个’ ‘+要注意一下,因为不能全包含

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
#include<bits/stdc++.h>
using namespace std;
int n;
string a[25];
int u[25];
int maxx,x;
int chongdie(string s1,string s2)
{
int len1=s1.length(),len2=s2.length();
for(int i=1;i<min(len1,len2);i++)
{
bool f=0;
for(int j=0;j<i;j++)if(s1[len1-i+j]!=s2[j])f=1;
if(!f)return i;
}
return 0;
}
void dfs(string now,int l)
{
maxx=max(l,maxx);
for(int i=0;i<n;i++)
{
if(u[i]>1)continue;
x=chongdie(now,a[i]);
if(x>0)
{
u[i]++;
dfs(a[i],l-x+a[i].length());
u[i]--;
}
}
}
int main()
{
cin>>n;
for(int i=0;i<=n;i++)cin>>a[i];
dfs(' '+a[n],1);
cout<<maxx<<endl;
}

T3 P1101

暴力即可

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
#include<bits/stdc++.h>
using namespace std;
int n;
char mapp[105][105];
bool m[105][105];
int qx[8]={-1,-1,-1,0,0,1,1,1};
int qy[8]={1,-1,0,1,-1,-1,1,0};
string c="yizhong";
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>mapp[i][j];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mapp[i][j]=='y')
{
for(int k=0;k<8;k++)
{
bool flag=0;
queue<int> q;
q.push(i);
q.push(j);
int tmpi=i;
int tmpj=j;
for(int p=1;p<7;p++)
{
int ii=tmpi+qx[k];
int jj=tmpj+qy[k];
if(ii>n||jj>n||ii<1||jj<1)flag=1;
if(c[p]!=mapp[ii][jj])flag=1;
if(flag)
{
while(q.size())q.pop();
break;
}
else
{
q.push(ii);
q.push(jj);
}
tmpi=ii;
tmpj=jj;
}
while(q.size())
{
int x=q.front();
q.pop();
int y=q.front();
q.pop();
m[x][y]=1;
}
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
if(m[i][j])cout<<mapp[i][j];
else cout<<"*";
cout<<endl;
}
}