NOIP2014 提高组 解题报告
Day1
生活大爆炸版石头剪刀布
思路分析
这是一道模拟题，可以为每一个出拳设一个编号，然后预处理一个二维数组来表示某个出拳对另一个出拳的胜负情况，也可以直接记为得分。
本来看这个题目还觉得一时想不到什么较好的方法，但是看一下数据范围，maxn=200，所以直接暴力累加每一场的胜负得分即可。
实现代码
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
| /*
rps
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cmath>
using namespace std;
const int maxn=203;
const int inf=2147483647;
int n,na,nb;
int ta[maxn],tb[maxn];
int win[5][5];
int scorea=0,scoreb=0;
void initwin()
{
win[0][1]=0,win[1][0]=1;
win[0][2]=1,win[2][0]=0;
win[0][3]=1,win[3][0]=0;
win[0][4]=0,win[4][0]=1;
win[1][2]=0,win[2][1]=1;
win[1][3]=1,win[3][1]=0;
win[1][4]=0,win[4][1]=1;
win[2][3]=0,win[3][2]=1;
win[2][4]=1,win[4][2]=0;
win[3][4]=1,win[4][3]=0;
}
void print()
{
for(int i=0;i<=4;++i)
{
for(int j=0;j<=4;++j)
{
cout<<win[i][j]<<' ';
}
cout<<endl;
}
}
void input()
{
scanf("%d%d%d",&n,&na,&nb);
for(int i=1;i<=na;++i)
{
scanf("%d",&ta[i]);
}
for(int i=1;i<=nb;++i)
{
scanf("%d",&tb[i]);
}
}
int main()
{
freopen("rps.in","r",stdin);
freopen("rps.out","w",stdout);
initwin();
//print();
input();
for(int i=1;i<=n;++i)
{
scorea+=win[ta[(i-1)%na+1]][tb[(i-1)%nb+1]];
scoreb+=win[tb[(i-1)%nb+1]][ta[(i-1)%na+1]];
}
printf("%d %d\n",scorea,scoreb);
return 0;
}
|
联合权值
题意分析
给定一棵边权全为1的无根树，且每个节点具有一定权值，求所有互相距离为2的有序点对的权值乘积最大值，和所有有序点对的权值乘积的总和。
思路分析
对于无根树的情况，我们可以任意选取一个节点作为根节点以便处理。
然后我们在这棵有根树上寻找满足题意的有序点对。
要求两个点的距离为2，我们发现在有根树 中只有3种情况满足：
1.某个结点和它的2级祖先
2.某个结点和它的2级子节点
3.某个结点和它的父节点的其他子节点（或者暂且称为它的兄弟）
思考后发现1、2两种情况其实可以只算一种，直接更新最大权值乘积和总权值乘积和，在算权值乘积贡献的时候再将答案乘2累加到总权值和中。
对于第3种情况，我们可以考虑在这些子节点的父节点上进行操作：
首先考虑最大权值积。
对于父节点，我们考虑它的子节点对答案的贡献是它们两两之间的权值乘积。由于所有的权值都是正整数，最有希望能够更新最大值的一定是权值最大的两个子节点。所以我们对每个父节点记录它的子节点中的最大权值，和次大权值。
这里要考虑存在两个最大值相同的情况，所以我们设定最大权值是大于，或等于次大权值的。
然后考虑这些子节点的权值两两乘积和。
假设子节点的权值为wi，该节点的子节点数目为m，那么这个节点的子节点对答案的贡献为：
$$
=(w 1 * w 2+w 1 * w 3+\cdots+w 1 *\\ w m)\\+(w 2 * w 1+w 2 * w 3+\cdots+w 2 * w m)\\+\cdots+(\mathrm{wi} * \mathrm{w} 1+\mathrm{wi} * \mathrm{w} 2+\cdots+\\\mathrm{wi} * \mathrm{w}[\mathrm{i}-1]+\mathrm{wi} * \mathrm{w}[\mathrm{i}+1]+\cdots+\mathrm{wi} * \mathrm{wm})\\
+\cdots+\\
(\mathrm{wm} * \mathrm{w} 1+\mathrm{wm} * \mathrm{w} 2+\cdots+\mathrm{wm} * \mathrm{w}[\mathrm{m}-1])
$$
根据小学学过的乘法分配律，我们将上面的式子改写一下，得到如下的形式：
$$
\begin{array}{l}{=\mathrm{w} 1 *(\mathrm{w} 2+\mathrm{w} 3+\cdots+\mathrm{wm})} \\ {+\mathrm{w} 2 *(\mathrm{w} 1+\mathrm{w} 3+\cdots+\mathrm{wm})} \\ {+\cdots} \\ {+\mathrm{wi}(\mathrm{w} 1+\cdots+\mathrm{w}[\mathrm{i}-1]+\mathrm{w}[\mathrm{i}+1]+\cdots+\mathrm{wm})} \\ {+\mathrm{wm} *(\mathrm{w} 1+\cdots+\mathrm{w}[\mathrm{m}-1])}\end{array}
$$
观察上面的式子，括号里面的式子十分相似。
如果设$\operatorname{sum} w=\sum w i=w 1+w 2+\cdots+w m$，那么上面的式子还可以改写成：
$$
=\mathrm{w} 1 *(\mathrm{sumw}-\mathrm{w} 1) \\ {+w 2 *(\operatorname{sum} w-w 2)} \\ +\cdots \\ {+w i *(\operatorname{sum} w-w i)} \\+\cdots
\\ {+w m *(\operatorname{sum} w-w m)} \\ {=\sum[w i *(\operatorname{sum} w-w i)]} \\ {=\sum\left(\operatorname{sum} w * w i-w i^{2}\right)}\\=\sum(\operatorname{sum} w * w i)-\sum w i^{2}\\=\operatorname{sumw} * \sum w i-\sum w i^{2}=\operatorname{sum} w^{2}-\sum w i^2
$$
如果设$\operatorname{sum} w 2=\sum w i^{2}$，那么最终这个点对总权值乘积和的贡献就是$\operatorname{sum} w^{2}-\operatorname{sum} w 2$
也就是所有子节点的权值和的平方减去所有子节点的权值平方和。
Sumw和sumw2都可以在建树的时候处理出来。
实现代码
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
| /*
link
有序点对!
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cmath>
using namespace std;
void read(int& A)
{
char r;
for(r=getchar();r<48||r>57;r=getchar());
for(A=0;r>=48&&r<=57;r=getchar())A=A*10+r-48;
}
const int maxn=200003;
const int inf=2147483647;
const int p=10007;
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
int n;
struct node
{
int edge1,sum,maxw,maxw2,w;
int num,f,depth,f2;
node()
{edge1=sum=w=f=depth=f2=0;maxw=maxw2=0;}
void initTree();
void calc();
}tree[maxn];
#define root tree[1]
struct EDGE
{
int to,nxt;
void init(int too,int nxtt)
{
to=too,nxt=nxtt;
}
}edge[maxn<<1];
int ek=0;
void addEdge(int from,int too)
{
edge[++ek].init(too,tree[from].edge1);
tree[from].edge1=ek;
}
void input()
{
read(n);
int x,y;
for(int i=1;i<=n-1;++i)
{
read(x),read(y);
addEdge(x,y);
addEdge(y,x);
}
for(int i=1;i<=n;++i)
{
read(tree[i].w);
tree[i].num=i;
}
}
void node::initTree()
{
for(int i=edge1;i;i=edge[i].nxt)
{
#define v edge[i].to
#define son tree[v]
if(son.depth==0)
{
son.depth=depth+1;
son.f=num;
son.f2=f;
son.initTree();
sum+=son.w;
sum%=p;
if(son.w>maxw2)
{
maxw2=son.w;
if(maxw2>maxw)
Swap(maxw,maxw2);
}
}
}
}
int sumw=0,maxww=0;
void node::calc()
{
int tw;
if(f2!=0)
{
tw=w*tree[f2].w;
sumw+=(tw<<1)%p;
sumw%=p;
if(tw>maxww)
maxww=tw;
}
if(edge1!=0&&maxw&&maxw2)
{
tw=maxw*maxw2;
if(tw>maxww)
maxww=tw;
int sum2=0;
for(int i=edge1;i;i=edge[i].nxt)
{
#define v edge[i].to
#define son tree[v]
if(son.depth>depth)
{
sum2+=son.w%p*(sum-son.w)%p;
sum2%=p;
}
}
sumw+=sum2;
sumw%=p;
}
}
int main()
{
freopen("link.in","r",stdin);
freopen("link.out","w",stdout);
input();
root.depth=1;
root.initTree();
for(int i=1;i<=n;++i)
{
tree[i].calc();
}
printf("%d %d\n",maxww,(sumw)%p);
return 0;
}
|
易失分点
题目中在样例说明中提到能“联合权值”的是有序点对，所以在累加与2级祖先的贡献时需要乘2。
飞扬的小鸟
思路分析
容易看出这是一道动态规划题。
先定义一些变量：
f[i][j]表示飞到i列j高度时的最少点击数
up[i],down[i]分别表示第i列点击一次的上升高度和不点击的下降高度
$n^3$做法
考虑f[i][j]如何从上一列转移而来。
根据题目，一般情况有两种转移。
从上一列的上方不点击下落
从上一列的下方点击上升
状态转移方程：
$$
\begin{array}{l}{f[i][j]=} \\ {\operatorname{Min}\{f[i-1][j+\operatorname{down}[i-1]], f[i-1][j-k * u p[i-1]]+k\}}\end{array}
$$
（k为点击次数）
还要考虑j==m的特殊情况，因为如果上升的高度超出当前与上边界的距离，最终到达的高度都是m。
方程：
$$
f[i][m]=\operatorname{Min}\{f[i-1][m-k * u p[i-1]+j]+k\}
$$
（k为点击次数，0<=j<=up[i-1]-1）
于是我们得到了一个O(n3)的算法。这样的算法可以拿到80分。
$n^2$做法
考虑上升过程的转移，我们发现点击两次相当于点击一次到达第i列某位置，再点击一次垂直上升。用方程可以表示为：
$$
\begin{array}{l}{f[i][j-u p[i-1]]=f[i-1][j-2 * u p[i-1]]+1 ;} \\ {f[i][j]=f[i-1][j-2 * u p[i-1]]+2 ;} \\ {\rightarrow f[i][j]=f[i][j-u p[i-1]]+1 ;}\end{array}
$$
也就是说我们可以利用当前位置下方的点作为跳板直接更新当前位置的答案。
所以对于一个位置，它既可以从上一列点击一次直接飞来，也可以从正下方点击若干次间接到达。
状态转移方程：
$$
f[i][j]=\operatorname{Min}(f[i][j], f[i-1][j-u p[i-1]]+1) ; / /直接飞\\f[i][j]=\operatorname{Min}(f[i][j], f[i][j-u p[i-1]]+1);//间接飞
$$
同样，对于j==m也要特殊处理：
$$
\begin{array}{l}{f[i][m]=\operatorname{Min}(f[i][m], f[i][x]+1)} \\ {f[i][m]=\operatorname{Min}([i][m], f[i-1][x]+1)}\end{array}
$$
（x为高度，m-up[i-1]<=x<=m）
从上一列下降的情况不变。
注意
一般来说属于柱子的坐标的f[i][j]应该设为inf，但是在上面这种递推的方法中，下方的柱子所在的位置有可能作为到达上方位置的跳板，所以可以暂时赋值。但是在这一列递推结束后必须将这一列的柱子（如果有）所在的位置的f[i][j]全部重设为inf。
由于上面的递推是基于不断点击上升而成立的，所以在处理某一列时需要先处理上升再处理下降的情况，不然会出现同时下降上升的不合理情况。
实现代码
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
| /*
noip2014 flppy bird
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
void read(int& A)
{
char r;
for(r=getchar(); r<48||r>57; r=getchar());
for(A=0; r>=48&&r<=57; r=getchar())A=A*10+r-48;
}
template<typename T>
T Max(const T& a,const T& b)
{
return a>b?a:b;
}
template<typename T>
T Min(const T& a,const T& b)
{
return a<b?a:b;
}
typedef unsigned int uint;
const int maxn=10003;
const int maxm=1003;
const int inf=2147483647;
const uint uinf=4294967295u;
int n,m,k;
int up[maxn],down[maxn];
int p,l[maxn],h[maxn];
bool exist[maxn];
void input()
{
read(n),read(m),read(k);
for(int i=0; i<=n-1; ++i)
{
read(up[i]),read(down[i]);
}
for(int i=0; i<=n; ++i)
{
l[i]=1;
h[i]=m;
}
for(int i=1; i<=k; ++i)
{
read(p);
exist[p]=true;
read(l[p]),read(h[p]);
++l[p],--h[p];
if(l[p]<1)l[p]=1;
if(h[p]>m)h[p]=m;
}
}
uint f[maxn][maxm];
bool pasted;
int mostarrive=0;
void solve()
{
for(int i=1; i<=n; ++i)
{
for(int j=0; j<=m; ++j)
{
f[i][j]=uinf;
}
}
f[0][0]=uinf;
for(int i=1; i<=n; ++i)
{
pasted=false;
/*从上一列的下方点击上升，
点击多次到达(i,j)相当于先飞到(i,j-up[i-1]再直线上升
*/
for(int j=Max(1,up[i-1]+1); j<=m-1&&j<=h[i]; ++j)
{
if(f[i-1][j-up[i-1]]!=uinf)
f[i][j]=Min(f[i][j],f[i-1][j-up[i-1]]+1);//直接飞
if(f[i][j-up[i-1]]!=uinf)
f[i][j]=Min(f[i][j],f[i][j-up[i-1]]+1);//间接飞
/*注意，在这时候先不用考虑柱子，
因为柱子所在的位置要作为跳到上面位置 的跳板
当前列结束后要将这些格子重设为INF*/
}
//j==m special treatment
for(int k=Max(1,m-up[i-1]); k<=m; ++k)
{
//顶端可以从(i-1,(j-up[i-1])~m)中的任意一格直接飞来
if(f[i-1][k]!=uinf)
f[i][m]=Min(f[i][m],f[i-1][k]+1);
//也可以由下面的格子先到达上面这种情况
if(f[i][k]!=uinf)
f[i][m]=Min(f[i][m],f[i][k]+1);//间接飞
}
/*从上一列的上方自然掉落
注意：下降一定要放在上升之后做，
因为上升那样做的条件是下面的跳板要从上升的状态转移来，
才能达到连续上升的等价效果*/
for(int j=l[i]; j<=h[i]&&j+down[i-1]<=m; ++j)
{
if(f[i-1][j+down[i-1]]!=uinf&&f[i-1][j+down[i-1]]<f[i][j])
f[i][j]=f[i-1][j+down[i-1]];
}
//将用作跳板的实际上不能走的格子重设
//（过河拆桥
for(int j=1; j<l[i]; ++j)f[i][j]=uinf;
for(int j=h[i]+1; j<=m; ++j)f[i][j]=uinf;
//判断当前列能否通过
for(int j=l[i]; j<=h[i]&&!pasted; ++j)
{
if(f[i][j]!=uinf)
{
pasted=true;
if(exist[i])
++mostarrive;
}
}
if(!pasted)return;
}
}
int main()
{
freopen("bird.in","r",stdin);
freopen("bird.out","w",stdout);
input();
solve();
if(pasted)
{
uint ans=uinf;
for(int j=1; j<=m; ++j)
if(f[n][j]<ans)
ans=f[n][j];
printf("1\n%u\n",ans);
}
else
{
printf("0\n%d\n",mostarrive);
}
return 0;
}
|
Day2
无线网络发射器选址
题意分析
给定129*129的一个矩阵，每个坐标有一个权值，求用一个边长为2d的正方形所能覆盖的点的最大权值和，及方案数。
思路分析
对于给定的一个矩阵，求某个子矩阵中所有的点权和常常使用二维前缀和的方法。具体构造方法不再赘述。
于是我们可以预处理出二维前缀和，再处理出每个点作为中心点时这个正方形所覆盖的的的权值和，取最大值即可。
另外计算方案数的时候不需要从头枚举一次。一个最大值第一次出现后将计数器置为1，如果后面有与它值相同的，再将方案数+1。这样不会漏算的原因是在前面一定没有出现过这个最大值。
因为这个矩阵非常小，所以可以直接算而不会超时。
实现代码
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
| /*
wireless
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxx=133;
typedef long long Uint;
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
T Min(const T& a,const T& b){return a<b?a:b;}
Uint pub[maxx][maxx];
Uint sum[maxx][maxx];
Uint cover[maxx][maxx];
int n,d;
void input()
{
scanf("%d%d",&d,&n);
int x,y,k;
for(int i=1;i<=n;++i)
{
scanf("%d%d%d",&x,&y,&k);
pub[x+1][y+1]=k;
}
}
void initSum()
{
sum[1][1]=pub[1][1];
for(int i=1;i<=129;++i)
{
for(int j=1;j<=129;++j)
{
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+pub[i][j];
}
}
}
void initCover()
{
for(int i=1;i<=129;++i)
{
for(int j=1;j<=129;++j)
{
int u=Max(1,i-d),l=Max(1,j-d);
int dd=Min(129,i+d),r=Min(129,j+d);
cover[i][j]=sum[dd][r]-sum[dd][l-1]-sum[u-1][r]+sum[u-1][l-1];
}
}
}
Uint ans=0,maxp=0;
void solve()
{
for(int i=1;i<=129;++i)
{
for(int j=1;j<=129;++j)
{
if(cover[i][j]>maxp)
{
maxp=cover[i][j];
ans=1;
}
else if(cover[i][j]==maxp)
{
++ans;
}
}
}
}
int main()
{
freopen("wireless.in","r",stdin);
//freopen("wireless.out","w",stdout);
input();
initSum();
initCover();
solve();
printf("%lld %lld\n",ans,maxp);
return 0;
}
|
寻找道路
思路分析
首先说明，题目中所谓的“与终点连通”是指从这个点出发能够到达终点。
对点分类
题目要求路径上的所有点的出边都直接或间接与终点相连，于是我们可以对图中的点先分类：
不能到达终点
不用考虑，可以直接删去。
能到达终点
a) 本身能到达终点但是存在出边指向的点不能
b) 本身及出边所指向的点都能到达终点
分类后目标就明确了，如果起点在2-b中，则在2-b的点组成的子图中寻找一条最短路径到达终点，否则直接退出。
判定点
要在2-b中寻找路径，首先要判定哪些点属于2-b。我们一步步筛选。
判定2类点：我们可以构造原图的反图G’，即将图中所有的边反转，然后从终点出发进行一次BFS（当然DFS也可），到达的点都是在原图G中可以到达终点的点。
判定2-b：在2类点的集合中，我们从起点出发，BFS所有能到达的点。对于当前点，如果它的出边中存在指向的点不属于2类点的点，那么它就是2-a类点。
寻找最短路
由于图中的边权都为1，所以在2-b点构成的子图中进行一次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
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
| /*
Road
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=10003;
const int maxm=200003;
typedef unsigned int uint;
const int inf=2147483647;
const uint uinf=4294967295u;
int n,m,s,t;
struct EDGE
{
int to,nxt;
inline void init(int too,int nxtt)
{
to=too,nxt=nxtt;
}
}edge[maxm],redge[maxm];
int ek=0;
struct NODE
{
int edge1,edge2;
uint d;
bool can,can2;
NODE(){edge1=edge2=0;can=false;can2=false;d=uinf;}
}node[maxn];
inline void addEdge(int from,int too)
{
++ek;
edge[ek].init(too,node[from].edge1);
node[from].edge1=ek;
redge[ek].init(from,node[too].edge2);
node[too].edge2=ek;
}
void input()
{
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
if(x!=y)
addEdge(x,y);
}
scanf("%d%d",&s,&t);
}
const int maxnode=maxm;
template<typename T>
struct QUE
{
T ary[maxnode];
int f,ta;
QUE(){f=ta=1;}
inline bool empty(){return f==ta;}
inline void clear(){f=ta=1;}
inline void push(const T& w){ary[ta++]=w;}
T& front(){return ary[f];}
inline void pop(){++f;}
};
QUE<int> q;
bool vis[maxn];
void rebfs()
{
q.push(t);
vis[t]=true;
node[t].can=true;
node[t].can2=true;
while(!q.empty())
{
int fr=q.front();
q.pop();
for(int i=node[fr].edge2;i;i=redge[i].nxt)
{
#define v redge[i].to
if(!vis[v])
{
vis[v]=true;
node[v].can=true;
node[v].can2=true;
q.push(v);
}
#undef v
}
}
}
void bfs()
{
memset(vis+1,0,n*sizeof(bool));
q.clear();
q.push(s);
vis[s]=true;
while(!q.empty())
{
int fr=q.front();
q.pop();
for(int i=node[fr].edge1;i;i=edge[i].nxt)
{
#define v edge[i].to
if(node[v].can)
{
if(!vis[v])
q.push(v),
vis[v]=true;
}
else
node[fr].can2=false;
#undef v
}
}
}
void distance()
{
memset(vis+1,0,n*sizeof(bool));
node[s].d=0;
q.clear();
q.push(s);
vis[s]=true;
while(!q.empty())
{
int fr=q.front();
q.pop();
for(int i=node[fr].edge1;i;i=edge[i].nxt)
{
#define v (edge[i].to)
#define aim node[v]
if(aim.can2&&aim.can&&!vis[v])
{
aim.d=node[fr].d+1;
if(v==t)return;
q.push(v);
vis[v]=true;
}
#undef v
#undef aim
}
}
}
int main()
{
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
input();
rebfs();
if(node[s].can)
bfs();
if(node[s].can2)
distance();
if(node[t].d!=uinf)
printf("%u\n",node[t].d);
else printf("-1\n");
return 0;
}
|
解方程
部分分
根据数据范围，30%的数据为n=1或2，且|ai|<=100。那么可以直接运用代数方法求解。
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
| /*
equation
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=103;
typedef int num;
num a[maxn];
int n,m;
int cnt=0;
int main()
{
freopen("equation.in","r",stdin);
//freopen("equation.out","w",stdout);
scanf("%d%d",&n,&m);
if(n==1)//a0+a1x=0,a1x=-a0,x=-a0/a1
{
for(int i=0;i<=n;++i)
{
scanf("%d",&a[i]);
}
int x=(-a[0])/a[1];
if(x>=1&&x<=m)
printf("1\n%d\n",(-a[0])/a[1]);
else printf("0\n");
}
else if(n==2)
{
for(int i=0;i<=n;++i)
{
scanf("%d",&a[i]);
}
int aa=a[2],bb=a[1],cc=a[0];
int deta=bb*bb-4*aa*cc;
if(deta==0)
{
int x=(-bb)/(2*aa);
if(x>=1&&x<=m&&2*aa*x==-bb)
printf("1\n%d\n",x);
else printf("0\n");
}
else if(deta>0)
{
if((int(sqrt(deta))*int(sqrt(deta)))==deta)
{
bool ok1=false,ok2=false;
int x1=(-bb-sqrt(deta))/(2*aa);
if(x1*2*aa==(-bb-sqrt(deta))&&x1>=1&&x1<=m)
++cnt,ok1=true;
int x2=(-bb+sqrt(deta))/(2*aa);
if(x2*2*aa==(-bb+sqrt(deta))&&x2>=1&&x2<=m)
++cnt,ok2=true;
printf("%d\n",cnt);
if(cnt==1)
{
if(ok1)printf("%d\n",x1);
if(ok2)printf("%d\n",x2);
}
else if(cnt==2)
{
printf("%d\n%d\n",x1,x2);
}
}
}
}
return 0;
}
|
高精度
通过高精度计算大系数。可以得到50分。
取模
如果将方程的系数和某个可能的解x全部模一个数p，那么在模p意义下如果左边的值不为0，x一定不为解。
所以只要我们取足够多且适当的模数，就可以最大可能的去掉不符合的解。
读入
系数的取模，我们可以在读入的时候读一位取模一次，这样最后得到的就是原来的大系数取模的余数。
计算
在计算某个可能解对应左边的表达式的值时，可以用秦九韶算法迭代，起到加速作用。
筛选解
对于一个解x和模数p，如果(x%p)不是解的话，x也一定不是。
反之，如果取了一定的模数，在所有的模数p[i]下，(x%p[i])都是可能解的话，x也一定是一个可能解。
所以我们可以只枚举所有模数的1~(p[i]-1)这些数，然后再枚举1~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
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
| /*
equation
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=103;
const int maxl=10003;
const int maxp=3;
const int maxm=1000003;
const int p[100]={0,9521,9829,9623,9721,6829,7829,829,1007,2017};
int a[maxp+1][maxn];
bool can[maxm];
char s[maxl];
int len;
int n,m;
void input()
{
scanf("%d%d\n",&n,&m);
for(int i=0;i<=n;++i)
{
scanf("%s",s);
len=strlen(s);
int start=0;
if(s[0]=='-')
start=1;
for(int j=start;j<=len-1;++j)
{
for(int k=1;k<=maxp;++k)
{
a[k][i]=(a[k][i]*10+s[j]-48)%p[k];
}
}
if(start==1)
{
for(int k=1;k<=maxp;++k)
{
a[k][i]=-a[k][i];
}
}
}
}
bool is[maxp+1][maxm];
bool judge(int x,int k)
{
int v=0;
for(int i=n;i>=0;--i)
{
v=v*(x%p[k])%p[k]+a[k][i]%p[k];
v%=p[k];
}
if(v!=0)return false;
return true;
}
int cnt=0,ans[maxn];
int main()
{
freopen("equation.in","r",stdin);
freopen("equation.out","w",stdout);
input();
for(int j=1;j<=maxp;++j)
{
for(int i=1;i<=p[j]-1;++i)
{
if(judge(i,j))
{
is[j][i]=true;
}
}
}
for(int i=1;i<=m;++i)
{
bool ok=true;
for(int k=1;k<=maxp&&ok;++k)
{
if(!is[k][i%p[k]])ok=false;
}
if(ok)ans[++cnt]=i;
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;++i)
{
printf("%d\n",ans[i]);
}
return 0;
}
|
失分点
在选择质数时要注意不要选取太大的，不然在计算过程中相乘时会溢出。
