【解题报告】NOIP2015
Day1
T1 神奇的幻方
思路
这不就是按照题目所给信息模拟一下咩？
过了
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int s[50][50];
int main()
{
cin>>n;
int x=1,y=(n+1)/2;
for(int i=1;i<=n*n;i++)
{
s[x][y]=i;
if(!s[(x-2+n)%n+1][y%n+1])
x=(x-2+n)%n+1,y=y%n+1;
else x=x%n+1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<s[i][j]<<" ";
cout<<endl;
}
return 0;
}
|
T2 信息传递
并查集求最小环并利用地址传参
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=2000005;
int n;
int fa[maxn];
int ans=99999999;
void init()
{
for(int i=1;i<=n;i++)
fa[i]=i;
}
int get(int x,int &cnt)
{
cnt++;
if(x==fa[x])
return x;
else
return get(fa[x],cnt);
}
int main()
{
cin>>n;
init();
for(int i=1;i<=n;i++)
{
int cnt=0;
int x;
cin>>x;
if(get(x,cnt)==i)
ans=min(ans,cnt);
else
fa[i]=x;
}
cout<<ans<<endl;
return 0;
}
|
T3 斗地主
思路
巨大模拟，狗都不做
发现出顺子可以出出来的牌，那么我们就从顺子作为第一个搜索
然后四带二，三带二，三带一，上单
这样我们就按照这个顺序依次搜索+回溯
就写完了，就是这个代码难度是真的大
到现在我还是不想写这个恶心的代码
随便嫖一篇过来（版权联系
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define int long long
using namespace std;
int T,n,ans;
int a[20];
void dfs(int x)
{
if(x>=ans) return ;
int k=0;
for(int i=3;i<=14;i++)
{
if(a[i]==0) k=0;
else
{
k++;
if(k>=5)
{
for(int j=i;j>=i-k+1;j--)
a[j]--;
dfs(x+1);
for(int j=i;j>=i-k+1;j--)
a[j]++;
}
}
}
k=0;
for(int i=3;i<=14;i++)
{
if(a[i]<=1) k=0;
else
{
k++;
if(k>=3)
{
for(int j=i;j>=i-k+1;j--)
a[j]-=2;
dfs(x+1);
for(int j=i;j>=i-k+1;j--)
a[j]+=2;
}
}
}
k=0;
for(int i=3;i<=14;i++)
{
if(a[i]<=2) k=0;
else
{
k++;
if(k>=2)
{
for(int j=i;j>=i-k+1;j--)
a[j]-=3;
dfs(x+1);
for(int j=i;j>=i-k+1;j--)
a[j]+=3;
}
}
}
for(int i=2;i<=14;i++)
{
if(a[i]<=3)
{
if(a[i]<=2) continue;
a[i]-=3;
for(int j=2;j<=15;j++)
{
if(a[j]<=0||j==i) continue;
a[j]--;
dfs(x+1);
a[j]++;
}
for(int j=2;j<=14;j++)
{
if(a[j]<=1||j==i) continue;
a[j]-=2;
dfs(x+1);
a[j]+=2;
}
a[i]+=3;
}
else
{
a[i]-=3;
for(int j=2;j<=15;j++)
{
if(a[j]<=0||j==i) continue;
a[j]--;
dfs(x+1);
a[j]++;
}
for(int j=2;j<=14;j++)
{
if(a[j]<=1||j==i) continue;
a[j]-=2;
dfs(x+1);
a[j]+=2;
}
a[i]+=3;
a[i]-=4;
for(int j=2;j<=15;j++)
{
if(a[j]<=0||j==i) continue;
a[j]--;
for(int k=2;k<=15;k++)
{
if(a[k]<=0||k==j) continue;
a[k]--;
dfs(x+1);
a[k]++;
}
a[j]++;
}
for(int j=2;j<=14;j++)
{
if(a[j]<=1||j==i) continue;
a[j]-=2;
for(int k=2;k<=14;k++)
{
if(a[k]<=1||k==j) continue;
a[k]-=2;
dfs(x+1);
a[k]+=2;
}
a[j]+=2;
}
a[i]+=4;
}
}
for(int i=1;i<=15;i++)
{
if(a[i])
x++;
}
ans=min(ans,x);
}
signed main()
{
cin>>T>>n;
while(T--)
{
ans=1e9;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
if(x==0)
a[15]++;
else if(x==1)
a[14]++;
else
a[x]++;
}
dfs(0);
cout<<ans<<'\n';
}
return 0;
}
|
Day2
T1 跳石头
思路
二分模板题目
我们对于两个石头的距离进行二分
如果对于某个二分的距离，可以在 m 个石头之内使得大于这个二分的距离
那么我们就可以完成
这样，我们尝试更长的距离是否能完成
二分一下下就好啦
主要是要注意二分模板
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define int long long
using namespace std;
const int maxn=50005;
int L,n,m;
int d[maxn];
int mx=-1e9;
int ans=0;
bool check(int x)
{
int cnt=0;
int lst=0;
for(int i=1;i<=n+1;i++)
{
if(d[i]-d[lst]<x)
cnt++;
else
lst=i;
}
return cnt<=m;
}
signed main()
{
cin>>L>>n>>m;
for(int i=1;i<=n;i++)
cin>>d[i],mx=max(mx,d[i]);
d[n+1]=L;
int l=0,r=L;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
l=mid+1,ans=mid;
else
r=mid-1;
}
cout<<ans<<'\n';
return 0;
}
|
T2 子串
思路
不会，参考一下别人
设 f[i][j][k] 表示 A 的前 i 个字符中，使用了 k 个子串，匹配 B 串的前 j 个字符
所以有 f[i][j][k]=f[i−1][j−1][k−1]+f[i−1][j−1][k]
意思是，A 的前 i 个字符中，使用了 k 个子串，匹配 B 串的前 j 个字符的方案数量等于在 A 的前 i−1 个字符里面，使用了 k−1 个子串，匹配了 B串的前 j−1 个字符的方案数量加上 在 A 的前 i−1 个字符里面，使用了 k 个子串，匹配了 B串的前 j−1 个字符的方案数量
简单地来说，就是看最后一个字符是否使用
但是我们无法解决前一个字符和前面有没有连起来以及有没有使用的情况
所以
新的状态转移方程
$
f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]
\
when \space a[i]==b[j]
\
f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k][1]+f[i-1][j-1][k-1][1]
$
然后滚动数组优化一下就可以DP了
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
| #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
const int MOD=1000000007;
int n,m,k;
char a[1005],b[205];
int f[205][205][3];
int main()
{
cin>>n>>m>>k;
scanf("%s%s",a+1,b+1);
f[0][0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>0;j--)
{
if(a[i]==b[j])
{
for(int x=min(j,k);x>0;x--)
{
f[j][x][1]=(f[j-1][x][1]+f[j-1][x-1][0])%MOD;
f[j][x][0]=(f[j][x][0]+f[j][x][1])%MOD;
}
}
else
for(int x=1;x<=m;x++)
f[j][x][1]=0;
}
}
cout<<f[m][k][0]%MOD<<endl;
return 0;
}
|
T3 运输计划
思路
非常毒瘤的题目
LCA+树上差分+二分
先对于每条路径处理一下它的长度，起点终点
二分一个最小路径的长度
在中间用差分，用于删去这一条边，找到最小的一条路径，看它是不是符合答案的，如果是的话，如果不是的话，分别处理
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define int long long
using namespace std;
const int maxn=300005;
struct edge{
int e,next,val;
}ed[maxn<<1];
int en,first[maxn];
void add_edge(int s,int e,int val)
{
en++;
ed[en].next=first[s];
first[s]=en;
ed[en].e=e;
ed[en].val=val;
}
struct node{
int u,v,lca,dist;
}p[maxn<<1];
int n,m,s;
bool vis[maxn];
int fa[maxn][25],dep[maxn];
int dis[maxn];
int num[maxn],tot=0;
void dfs(int x,int pa,int depth)
{
tot++;
num[tot]=x;
dep[x]=depth;
vis[x]=true;
for(int i=1;i<25;i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=first[x];i>0;i=ed[i].next)
{
int v=ed[i].e;
if(!vis[v])
{
fa[v][0]=x;
dis[v]=dis[x]+ed[i].val;
dfs(v,x,depth+1);
}
}
}
int get_lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int t=dep[x]-dep[y];
for(int i=0;i<25;i++)
if((1<<i)&t) x=fa[x][i];
if(x==y) return x;
for(int i=24;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
int tmp[maxn];
bool check(int x)
{
int cnt=0,ans=0;
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=m;i++)
{
if(p[i].dist>x)
{
tmp[p[i].u]++;
tmp[p[i].v]++;
tmp[p[i].lca]-=2;
ans=max(ans,p[i].dist-x);
cnt++;
}
}
if(cnt==0) return true;
for(int i=n;i>=1;i--)
tmp[fa[num[i]][0]]+=tmp[num[i]];
for(int i=2;i<=n;i++)
if(tmp[i]==cnt&&dis[i]-dis[fa[i][0]]>=ans)
return true;
return false;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n-1;i++)
{
int x,y,z;
cin>>x>>y>>z;
add_edge(x,y,z);
add_edge(y,x,z);
s+=z;
}
dis[0]=0;
fa[0][0]=0;
dep[0]=1;
dfs(1,0,1);
for(int i=1;i<=m;i++)
{
cin>>p[i].u>>p[i].v;
p[i].lca=get_lca(p[i].u,p[i].v);
p[i].dist=dis[p[i].u]+dis[p[i].v]-2*dis[p[i].lca];
}
int l=0,r=s;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))
r=mid;
else
l=mid+1;
}
cout<<l<<'\n';
return 0;
}
|
