NOIP2016提高组 解题报告
Day1
玩具谜题
【题目描述】略。
思路分析
首先我们容易想到的是把圈拉开成链，也就是将小人按照输入的顺序存储在数组中。
为了代码书写的方便，我们为小人定义一个结构体。
1
2
3
4
5
| struct MAN
{
int face;
char job[];
}
|
其中face是面向的方向，job[]是最后用来输出的职业。
那么我们如何实现不同方向的数呢？通过思考我们发现，面向圈内时向左和面向圈外时向右数的方向其实是一样的。我们联想到 1*1=(-1)*(-1)=1,1*(-1)=(-1)*1=-1的性质，可以设计将朝向和输入的数数的方向的取值映射为1/-1，这样就可以用step*face*direction表示偏移量了。
当然为了实现环的效果，我们在每次寻找下一个小人的时候都要模。
即：
num=( num+step*dir *man[num].face + n ) % n;
其中step是当前指令的步长。同时为了模的时候方便，我们在将小人输入的时候第一个小人下标为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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,m;
struct MAN
{
int face;
char job[1000];
MAN()//构造函数初始化
{
face=0;
}
void inPut()
{
scanf("%d",&face);
if(face==0)face=1;
else if(face==1)face=-1;
scanf("%s",job);
}
void outPut()//调试用输出信息
{
cout<<face<<endl;
printf("%s\n",job);
}
}man[100005];
int main()
{
freopen("toy.in","r",stdin);
freopen("toy.out","w",stdout);
scanf("%d%d",&n,&m);
//输入小人
for(int i=0;i<=n-1;++i)
{
man[i].inPut();
//man[i].outPut();
}
//输入指令
int a,s,num=0,dir;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&a,&s);
if(a==0)a=-1;
dir=man[num].face*a;
num=num+s*dir;
num=(num+n)%n;
}
printf("%s\n",man[num].job);
return 0;
}
|
天天爱跑步
【题目描述】
略
思路分析
剖析问题
首先我们分析单个观察者和单个玩家的情况。
由于问题建立在无根树上，所以可以随便指定一个节点作为根。
然后每个玩家的路径一定就是这样的：从起点S到LCA，从LCA到终点T。
这个路径的两部分的解法是相似的，下面先介绍从起点S到LCA。
条件
显然对于单独的观察者O和玩家P，O能观察到P的条件有两个：
O在S->LCA这条路径上
O出现时P正好跑到O所在的位置
条件1
容易得出O在S->LCA这条路径上的充要条件：
O在以lca为根的子树中，
并且s在以O为根的子树里。
所以如何判断一个点B是不是在A的子树里呢？
一般有两种方法。
第一是在dfs的过程中，我们一般是先访问根再访问它的子节点。所以如果在访问A的函数返回前访问到了B，那么B就在A的子树里。
第二是dfs序。在dfs的前提下，按访问顺序排列点的编号，那么从A点开始一直到A点的一个兄弟以前 的这一段区间，就都是A的子树。
至于在这道题中用哪种，我们下面再讨论。
条件2
由于经过每一条边所花时间都为1，那么在玩家从S到LCA的过程中，到达某个点的时间就是这个点与S的深度差。
要使得路径上某点A的观察者观察到玩家，则观察者出现的时间应该与玩家到达这个点的时间相等。则有：
W[A]=deep[S]-deep[A]
至此，条件已经分析完成。
计数
由于这道题要求的是每个观察者观察到的玩家数量，我们想着“参变分离”，将上面式子中与观察者有关的项和与玩家有关的项分别移到两边，得到：
W[A]+deep[A]=deep[S]
又因为条件1和条件2之间的关系是“且”，即一个玩家要被某观察者观察到需要同时满足这两个条件，所以我们要 求满足条件1的玩家的集合set1 和 满足条件2的玩家的集合set2的交集。有两种想法：
1． 在set1中找满足条件2
2． 在set2中找满足条件1
显然方法2比较麻烦而且难以实现，所以我们选择方法1。所以具体怎么实现呢？
这里我们用到类似于“时间戳”的思想。我们定义一个数组cnt[]，cnt[x]表示当前访问过的满足deep[S]=x的点的个数。那么对于某个点A，在它子树中的点都会在退出A之前被访问过（见条件1-判断方法1）。
那么我们在进入A时记录tmp=cnt[w[A]+deep[A]]，退出时再记录更新的now= cnt[w[A]+deep[A]]，那么A子树中满足条件2的点的个数就是now-tmp。但是根据条件1，我们还要排除掉那些不满足A在LCA子树中的点。
由于此时S已经在A的子树中，那么LCA不是在A的子树外，就是在A的子树里。如果LCA在A的子树外的话，那么S要到达LCA一定会经过A，所以此时A在LCA的子树里。
那么我们要排除的，就是LCA在A的子树里的那些点。如果S的LCA在A的子树里，那么LCA一定比S先访问到。我们利用与上面相同的思想，再定义一个cntlca[]，cntlca[x]存放当前满足deep[S]=x并且LCA已经被访问过的点的个数。那么我们在进入A时记录tmplca=cntlca[w[A]+deep[A]]，退出时再记录更新的nowlca= cntlca[w[A]+deep[A]]，那么要排除的点的个数就是nowlca-tmplca。
所以最后A点的观察员观察到的点的个数就是ans[A]=(now-tmp)-(nowlca-tmplca)。
再考虑一下A在LCA->T的路径。
条件1几乎相同，条件2可以得出类似的式子：
W[A]=(deep[S]-deep[LCA])+(deep[A]-deep[LCA])
同样整理得到：
w[A]-deep[A]=deep[S]-2*deep[LCA]
那么用几乎一样的方法计算即可。略有不同的是，在这种情况中，左边的w[A]-deep[A]的值有可能是负数。那么我们在更新cnt[w[A]-deep[A]]的时候就要处理一下。
这里提供两种方法：
cnt[]用普通数组并将其大小开大一倍，只是访问值的时候cnt[w[A]-deep[A]+maxn];
使用指针模仿负下标数组，详细可以看后面的代码。
只是还要注意一个问题：A=LCA的情况在两段路径都会被算到cntlca[]中而被减掉，因为我们使用的vis[]标记是访问每个节点的时候打的，而用当前节点更新cntlca[]的时候，如果LCA已被访问，就会++cntlca[]。
处理办法：
因为在处理子树完返回的时候已经处理完了子树中的cntlca[]，我们只要在计算两段中的一段路径的答案之后再将当前点算入cntlca[]即可。
实现代码
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
| /*
NOIP 2016 Day1 T2
running
*/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
template<typename T>
void read(T& w)
{
char r;
for(r=getchar();r<48||r>57;r=getchar());
for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
}
const int maxn=300003;
const int maxm=300003;
int n,m,w[maxn];
struct EDGE
{
int to,nxt;
void init(int too,int nxtt)
{
to=too;nxt=nxtt;
}
}edge[maxn<<1];
int ek=0;
int node[maxn],d[maxn],ans[maxn];
const int root=1;
inline void addEdge(int from,int too)
{
edge[++ek].init(too,node[from]);
node[from]=ek;
}
int s[maxm],t[maxm],lca[maxm];
vector<int> res[maxn],ret[maxn],relca[maxn];
//int relca[maxn];
void input()
{
read(n),read(m);
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(w[i]);
}
for(int i=1;i<=m;++i)
{
read(x),read(y);
s[i]=x;
res[x].push_back(i);
t[i]=y;
ret[y].push_back(i);
}
}
int f[maxn];
inline int findf(int x)
{
if(f[x]!=x)
f[x]=findf(f[x]);
return f[x];
}
/*
inline void unite(int a,int b)
{
f[findf(a)]=findf(b);
}
*/
void Tarjan(int k)
{
for(int i=node[k];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(!d[v])
{
d[v]=d[k]+1;
Tarjan(v);
//unite(k,v);
f[v]=k;
}
}
int ss;
ss=res[k].size();
for(int i=0;i<ss;++i)
{
int id=res[k][i];
if(d[t[id]]&&!lca[id])
{
lca[id]=findf(t[id]);
//relca[lca[res[k]]]=ret[k];
relca[lca[id]].push_back(id);
}
}
ss=ret[k].size();
for(int i=0;i<ss;++i)
{
int id=ret[k][i];
if(d[s[id]]&&!lca[id])
{
lca[id]=findf(s[id]);
//relca[lca[res[k]]]=ret[k];
relca[lca[id]].push_back(id);
}
}
}
bool vis[maxn];
int c1[2*maxn],cl1[2*maxn];
int c2[2*maxn],cl2[2*maxn];
int* cnt1=&c1[maxn];
int* cntlca1=&cl1[maxn];
int* cnt2=&c2[maxn];
int* cntlca2=&cl2[maxn];
void dfs(int k)
{
int p1=w[k]+d[k];
int tmp1=cnt1[p1],tmplca1=cntlca1[p1];
int p2=w[k]-d[k];
int tmp2=cnt2[p2],tmplca2=cntlca2[p2];
vis[k]=true;
for(int i=node[k];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(!vis[v])
dfs(v);
}
for(int i=0,ss=res[k].size();i<ss;++i)
{
++cnt1[d[k]];
}
for(int i=0,ss=relca[k].size();i<ss;++i)
{
int id=relca[k][i];
++cntlca1[d[s[id]]];
}
int now1=cnt1[p1],nowlca1=cntlca1[p1];
ans[k]+=(now1-tmp1)-(nowlca1-tmplca1);
for(int i=0,ss=ret[k].size();i<ss;++i)
{
int id=ret[k][i];
++cnt2[d[s[id]]-d[lca[id]]*2];
}
int now2=cnt2[p2],nowlca2=cntlca2[p2];
ans[k]+=(now2-tmp2)-(nowlca2-tmplca2);
for(int i=0,ss=relca[k].size();i<ss;++i)
{
int id=relca[k][i];
++cntlca2[d[s[id]]-d[k]*2];
}
}
void output()
{
for(int i=1;i<=n;++i)
{
printf("%d",ans[i]);
if(i==n)putchar('\n');
else putchar(' ');
}
}
void initf()
{
d[root]=1;
for(int i=1;i<=n;++i)
{
f[i]=i;
}
}
int main()
{
freopen("running.in","r",stdin);
freopen("running.out","w",stdout);
input();
initf();
Tarjan(root);
dfs(root);
output();
return 0;
}
|
换教室
【解释题意】给定一个连通无向图<e,v>与该图中的n个有序结点，现有n个可以替换的方案将有序节点中的一个换成另一个，成功概率ki，求有序节点遍历一次的路径最小期望。
（可能用词不是很准确，但是大概是这样）
思路分析
这题大致上考察了基本的图论和动态规划，以及一些数学知识。
- 期望
期望的概念可以请教数学老师。
（事实上因为对期望不够熟悉导致第一次打的时候动规方程写错）
在本题中可以理解成将一种方案拆分成具有确定概率的几种方案的结果乘上它们的概率的和。
需要注意的是这里拆分的方案的概率之和必须为1。
- 最短路
题目中读入的学校地图需要进行一定的处理，因为题目中提到要选择最短的路径。
在这里我们使用基本的多点最短路算法Floyd。
另外提一下，更新用的中间节点编号（一般用的k）要在最外层循环。不过因为数据水即使放在最里面也有52分……
- 动态规划
这里应该是这道题最重要的部分。有了之前【解释题意】中的背景，我们很容易想到以有序节点的顺序为各个阶段。这样我们大致确定我们的方程是个二维DP f[i][j]；
然而由于题目引入了概率和期望，DP不只是这么简单。
对于当前节点i和上一节点i-1，我们要考虑这样一些情况：
当前节点我们申请换教室
① 上一节点申请
- 两次都通过：
distance[d[i-1]][d[i]] - 仅这次通过：
distance[c[i-1]][d[i]] - 仅上次通过：
distance[d[i-1]][c[i]] - 两次都不过：
distance[c[i-1]][c[i]]
② 上一节点不申请
- 这次通过：
distance[c[i-1]][d[i]] - 这次不通过：
distance[c[i-1]][c[i]]
当前节点我们不申请
① 上一节点申请
- 上次通过：
distance[d[i-1]][c[i]] - 上次不通过：
distance[c[i-1]][c[i]]
② 上一节点不申请：distance[c[i-1]][c[i]]
于是这就造成了一个极为冗长的状态转移方程。我们发现每次还要考虑当前申请不申请，于是我们在原来的基础上再加一位变成f[i][j][2]，
一般定义f[i][j][0]表示第i节课共申请j次且本次不申请的体力期望最小值，
f[i][j][1]表示第i节课共申请j次且本次申请的体力期望最小值。
易错点
概率之和为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
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
| #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
using namespace std;
const int maxn=2033;
const int maxv=333;
const double eps=1e-6;
const double inf=2147483647;
int n,//课的节数
m,//申请的机会数
e,//道路数
v;//节点数
int c[maxn],//原安排课
d[maxn];//想申请课
double k[maxn];//成功概率
int w[maxv][maxv];//最短路
template<typename T>
T Min(const T& a,const T& b){return a>b?b:a;}
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
void Init()
{
for(int i=1;i<=v;++i)
{
w[i][i]=0;
for(int j=i+1;j<=v;++j)
{
w[i][j]=w[j][i]=inf;
}
}
}
void inPut()
{
scanf("%d%d%d%d",&n,&m,&v,&e);
Init();
for(int i=1;i<=n;++i)
scanf("%d",&c[i]);
for(int i=1;i<=n;++i)
scanf("%d",&d[i]);
for(int i=1;i<=n;++i)
scanf("%lf",&k[i]);
int a,b,ww;
for(int i=1;i<=e;++i)
{
scanf("%d%d%d",&a,&b,&ww);
if(a!=b&&ww<w[a][b])//there may be not only one road between two classroom
w[a][b]=w[b][a]=ww;
}
}
void floyd()
{
for(int k=1;k<=v;++k)
{
for(int i=1;i<=v;++i)
{
w[i][i]=0;//there may be two near classes which use same classroom
for(int j=1;j<=v;++j)
{
if(i!=j)
{
if(k!=i&&k!=j
&&w[i][k]!=inf&&w[k][j]!=inf
&&w[i][k]+w[k][j]<w[i][j])
{
w[i][j]=w[i][k]+w[k][j];
}
}
}
}
}
}
const int apply=1,napply=0;
double f[maxn][maxn][2];
//f[i][m][]在使用了m次机会时（包括此次），从起点到达i的体力期望最小值
typedef double db;
void dp()
{
for(int i=1;i<=n;++i)
{
for(int j=0;j<=m;++j)
{
f[i][j][apply]=f[i][j][napply]=inf;
}
}
f[1][0][napply]=f[1][1][apply]=0.0;
for(int i=2;i<=n;++i)
{
f[i][0][napply]=f[i-1][0][napply]+db(w[c[i-1]][c[i]]);
for(int j=1;j<=Min(i,m);++j)
{
//-----------------这一次申请------------------------------
f[i][j][apply]=Min(
f[i-1][j-1][apply] //上一次申请
+ k[i-1]*k[i] *db(w[d[i-1]][d[i]])//两次都通过
+ (1-k[i-1])*k[i] *db(w[c[i-1]][d[i]])//仅这次通过
+ k[i-1]*(1-k[i]) *db(w[d[i-1]][c[i]])//仅上次通过
+(1-k[i-1])*(1-k[i])*db(w[c[i-1]][c[i]]) ,//两次都不通过
f[i-1][j-1][napply] //上一次不申请
+k[i] *db(w[c[i-1]][d[i]]) //这次申请通过
+(1-k[i])*db(w[c[i-1]][c[i]]) ); //这次不通过
//------------------这一次不申请---------------------------
f[i][j][napply]=Min(
f[i-1][j][apply] //上一次申请
+ k[i-1] *db(w[d[i-1]][c[i]]) //申请通过
+(1-k[i-1])*db(w[c[i-1]][c[i]]), //申请不通过
f[i-1][j][napply]+db(w[c[i-1]][c[i]]) );//上一次不申请
}
}
}
int main()
{
freopen("classroom.in","r",stdin);
freopen("classroom.out","w",stdout);
inPut();
floyd();
dp();
double ans=f[n][0][napply];
for(int i=0;i<=m;++i)
{
if(f[n][i][apply]+eps<ans)
ans=f[n][i][apply];
if(f[n][i][napply]+eps<ans)
ans=f[n][i][napply];
}
printf("%.2lf",ans);
return 0;
}
//（虽然过了，但是时间花费较大）
|
Day2
组合数问题
题目描述
给定k，输入t组n，m，
每次求所有$C_i^j$中被k整除的个数。(0≤i≤n, 0≤j≤min{i,m} )
思路分析
- 预处理组合数
先把输入离线，求出最大的n，然后运用组合数的递推式$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$（杨辉三角）求出所有的范围内的组合数%k的值。
- 二维前缀和
在上一步求的时候可以直接把某个组合数是否被k整除存到一个数组is中，值为1。
题目要求读入n、m，求is[0~n][0~min(I,m)]中为真的个数.
这里我们用二维前缀和，sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+is[i][j];
公式看起来比较长但是其实自己画一下很容易理解的。
3．输出
For循环之前读入的n、m，输出sum[ n[i] ][ m[i] ] 即可
易错点
输入的m有可能比n大，这时候只要将m赋为n即可。
在n很大时，$C_i^j$有可能很大，由于题目只要求被k整除，在预处理C的时候每次模k即可。
实现代码
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
| /*
Problem
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn=2033;
const int maxt=10003;
const int inf=2147483647;
typedef unsigned long long LL;
LL C[maxn][maxn];
int sum[maxn][maxn];
int t,n[maxt],m[maxt],k;
int bign=-inf;
int is[maxn][maxn];
void printC()
{
for(int j=-1;j<=bign;++j)
{
printf("%4d",j);
}
printf("\n");
for(int i=0;i<=bign;++i)
{
printf("%4d",i);
for(int j=0;j<=i;++j)
{
printf("%4d",C[i][j]);
}
printf("\n");
}
}
void printsum()
{
for(int j=-1;j<=bign;++j)
{
printf("%4d",j);
}
printf("\n");
for(int i=0;i<=bign;++i)
{
printf("%4d",i);
for(int j=0;j<=i;++j)
{
printf("%4d",sum[i][j]);
}
printf("\n");
}
}
void initC()
{
C[0][0]=C[1][0]=C[1][1]=1;
if(1%k==0)
is[0][0]=is[1][0]=is[1][1]=1;
for(int i=2;i<=bign+5;++i)
{
for(int j=0;j<=i;++j)
{
C[i][j]=(C[i-1][j]%k+C[i-1][j-1]%k)%k;//if you do not mod, only 70
if(C[i][j]%(LL)k==0ul)
is[i][j]=1;
}
}
}
void initSum()
{
for(int i=1;i<=bign;++i)
{
for(int j=1;j<=bign;++j)
{
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+is[i][j];
//printsum();
}
}
}
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;
}
void inPut()
{
for(int e=1;e<=t;++e)
{
read(n[e]),read(m[e]);
if(n[e]>bign)
bign=n[e];
if(m[e]>n[e])
m[e]=n[e];
}
}
void outPut()
{
for(int e=1;e<=t;++e)
{
printf("%d\n",sum[n[e]][m[e]]);
}
}
int main()
{
freopen("problem.in","r",stdin);
freopen("problem.out","w",stdout);
read(t),read(k);
inPut();
initC();
initSum();
/*
------------debug use
printC();
cout<<endl;
printsum();
*/
outPut();
return 0;
}
|
蚯蚓
【题目描述】略
思路分析
首先将读入的蚯蚓从大到小排序。
暴力、优先队列上面的应该比较容易想到，这里我们只讲最优的解法了。
单调队列
我们的做法是开三个队列，一个存放原蚯蚓，一个存放每次切的第一段，一个存第二段。
每次切的时候从三个队列中取出最大的。
这里与普通的优先队列的差别在于，我们可以证明这三个队列都是单调递减的。这样就省下了大量处理数据结构的时间。
证明：
设三个队列为q1[],q2[],q3[],读入数据时已经排序所以任取i＜j，q1[i]≥q1[j]，已经单减。
现在假设有x=q1[1], y=q1[2],有x≥y。（下面除了数组外的[x]表示高斯函数（取整函数））
现在切x，得到
a1=[px],
b1=x-a1=x-[px],
将它们分别存入q2[],q3[]中。
过了一秒，y’=y+q, a1’=[px]+q, b1’=x-[px]+q。
现在我们来切y, 得到
a2=[ p(y+q) ]
b2=y+q-[ p(y+q) ]
我们要证明的是a1’≥a2, b1’≥b2，即：
[px]+q≥[ p(y+q) ]
x-[px]+q≥y+q-[ p(y+q) ]
整理变换得到：
[px]+q≥[ py+pq ] ……①
x-[px]≥y -[ p(y+q) ]，（移项）à x + [ p(y+q) ]≥ y + [px]……②
证明①：
0＜p＜1，0＜pq＜q，
[px]+q＞[px]+pq，
又由高斯函数性质，[px]+pq≥[px+pq]=[ p(x+q) ]；
又x≥y，[p(x+q)] ≥[ p(y+q)]
即[px]+q≥[ p(y+q) ]。
证明②：
直接证有点难度，不过不考虑精度的问题的话可以将这个问题转化为p’=1-p的上一个问题，同理可得。
当然，考试的时候可以打表猜规律……
其他的就没有什么了，主要在于代码实现的好不好。
易错点
输入u，v的时候直接double p=double(u)/double(v)，不然会WA 30分。（我也不知道为什么）
m比n还大，最后产生的蚯蚓数应该以n+m为上限，不然会RE。
实现代码
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
| /*
Earthworm
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<string>
using namespace std;
void read(int& A);//读入优化
template<typename T>
T Min(const T& a,const T& b){return a>b?b:a;}
template<typename T>
T Max(const T& a,const T& b){return a<b?b:a;}
const int maxn=7000003;//50 RE
int q[4][maxn],pos[4],len[4];
int n,m,qq,u,v,t;
double p;
void inPut()
{
read(n),read(m),read(qq);
read(u),read(v),read(t);
p=double(u)/double(v);
for(int i=1;i<=n;++i)
{
read(q[1][i]);
}
sort(q[1]+1,q[1]+n+1,greater<int>());
}
inline int ft(int i,int tt)//第i个队列的队首在时间tt的长度
{
return q[i][pos[i]]+(tt-1)*qq;
}
inline int choose(int tt)
{
if(pos[1]<=len[1]&&pos[2]<=len[2]&&pos[3]<=len[3])
{
int f[4];
for(int i=1;i<=3;++i)f[i]=ft(i,tt);
if(Max(f[1],f[2])>=f[3])
{
if(f[1]>=f[2])
return 1;
else return 2;
}
else return 3;
}
int q1=-1,q2=-1;
if(pos[1]>len[1]&&pos[2]<=len[2]&&pos[3]<=len[3])
{
q1=2,q2=3;
}
if(pos[2]>len[2]&&pos[1]<=len[1]&&pos[3]<=len[3])
{
q1=1,q2=3;
}
if(pos[3]>len[3]&&pos[1]<=len[1]&&pos[2]<=len[2])
{
q1=1,q2=2;
}
if(q1!=-1&&q2!=-1)
{
if(pos[q1]<=len[q1]&&pos[q2]<=len[q2])
{
int f1=ft(q1,m),f2=ft(q2,m);
if(f1>=f2)
{
return q1;
}
else
{
return q2;
}
}
}
int q3=-1;
if(pos[3]>len[3]&&pos[1]>len[1]&&pos[2]<=len[2])
q3=2;
if(pos[3]>len[3]&&pos[2]>len[2]&&pos[1]<=len[1])
q3=1;
if(pos[1]>len[1]&&pos[2]>len[2]&&pos[3]<=len[3])
q3=3;
if(q3!=-1)
{
return q3;
}
return -1;
}
inline void add(int ary,int lengg,int tt)
{
q[ary][++len[ary]]=lengg-(tt)*qq;
}
inline void cut(int ary,int tt)
{
int leng=ft(ary,tt);
int px=int((p)*double(leng));//there need double, or only 70
int dpx=leng-px;
add(2,px,tt);
add(3,dpx,tt);
++pos[ary];
}
void print(int tt)
{
cout<<endl;
for(int e=1;e<=3;++e)
{
cout<<"q"<<e<":";
for(int i=pos[e];i<=len[e];++i)
{
printf("%4d",q[e][i]+(tt-1)*qq);
}
cout<<endl;
}
cout<<endl;
}
void cutting()
{
pos[1]=pos[2]=pos[3]=1,len[1]=n;
for(int ti=1;ti<=m;++ti)
{
int chosen=choose(ti);
if(ti%t==0)
{
printf("%d ",ft(chosen,ti));
}
cut(chosen,ti);
//print(ti+1);
}
printf("\n");
}
void afterm()
{
int chosen;
for(int ti=1;ti<=n+m&&(chosen=choose(m))!=-1;++ti)
{
if(ti%t==0)
{
printf("%d ",ft(chosen,m+1));
}
++pos[chosen];
}
printf("\n");
}
int main()
{
freopen("cut3.in","r",stdin);
//freopen("cut.out","w",stdout);
inPut();
cutting();
afterm();
return 0;
}
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;
}
|
愤怒的小鸟
【题目描述】略
思路分析
预处理
经过数学分析我们可以知道，对于任意两个点一定能找到唯一的一条抛物线过这两点。
但是题目的背景要求a＜0。又因为所有点都在第一象限，由 $-\frac{b}{2a}$＞0得a、b异号，则a＜0时一定有b＞0。
所以我们只要判断存在这样的a即可。
对于任意两只猪A(x1,y1) B(x2,y2)，我们可以列出这样两条式子。
$$
\begin{cases}y_1=ax_1^2+bx_2\\y_2=ax_2^2+bx2\end{cases}\\
解得:\begin{cases}
a=\frac{x_2y_1-x_1y_2}{x_1x_2(x_1-x_2)}\\b=\frac{x_1^2y_2-x_2^2y_1}{x_1x_2(x_1-x_2)}\end{cases}
$$
搜索
接下来我们把每个找到的这样的二元组（a，b）存到A猪和B猪的结构体中，下一步我们选择深度优先搜索，每次搜到最后一只猪的时候更新答案。
为了提高查询抛物线的效率，我们可以采用hash优化一下。
实现代码
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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
| /*
Angrybirds
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cmath>
using namespace std;
const int maxn=20;
const double eps=1e-9;
int t,n,m;
typedef double num;
struct two
{
num t1,t2;
inline two(){t1=t2=0;}
inline two(num tt1,num tt2):t1(tt1),t2(tt2){}
};
bool operator<(const two &a,const two& b)
{
return a.t1==b.t1?a.t1<b.t1:a.t2<=b.t2;
}
inline void read(num &A)
{
scanf("%lf",&A);
}
const int maxt=829;
struct PIG
{
num x,y;
int cnt[maxt+2][maxn];
two aa[maxn];
int re[maxn];
int kaa;
inline void inPut(){read(x),read(y);}
inline void unit(int p);
inline void clear()
{
//x=y=0;
for(;kaa>=1;--kaa)
{
memset(cnt[re[kaa]],0,(cnt[re[kaa]][0]+1)*sizeof(int));
}
}
}pig[maxn];
num geta(const PIG& a,const PIG& b)
{
return (b.x*a.y-a.x*b.y)/(a.x*b.x*(a.x-b.x));
}
num getb(const PIG& a,const PIG& b)
{
return (a.x*a.x*b.y-b.x*b.x*a.y)/(a.x*b.x*(a.x-b.x));
}
int Hash(const num& a,const num& b)
{
return (int(fabs(a))*int(fabs(b))*1000)%(maxt)+1;
}
inline void PIG::unit(int p)
{
num a=geta(*this,pig[p]);
if(!(a<-eps))return;
num b=getb(*this,pig[p]);
two tt(a,b);
int h=Hash(a,b);
bool finded=false;
for(int i=1;i<=cnt[h][0];++i)
{
if(fabs(aa[cnt[h][i]].t1-a)<eps
&&fabs(aa[cnt[h][i]].t2-b)<eps)
{
finded=true;
}
}
if(!finded)
{
cnt[h][++cnt[h][0]]=++kaa;
aa[kaa]=tt;
re[kaa]=h;
}
finded=false;
for(int i=1;i<=pig[p].cnt[h][0];++i)
{
if(fabs(pig[p].aa[pig[p].cnt[h][i]].t1-a)<eps
&&fabs(pig[p].aa[pig[p].cnt[h][i]].t2-b)<eps)
{
finded=true;
}
}
if(!finded)
{
pig[p].cnt[h][++pig[p].cnt[h][0]]=++pig[p].kaa;
pig[p].aa[pig[p].kaa]=tt;
pig[p].re[pig[p].kaa]=h;
}
}
void inPut()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
pig[i].inPut();
}
}
void Init()
{
for(int i=1;i<=n;++i)
{
pig[i].clear();
}
for(int i=1;i<=n;++i)
{
for(int j=i+1;j<=n;++j)
{
pig[i].unit(j);
}
}
}
two used[maxn];
int tk=0;
bool killed(int p)
{
for(int i=1;i<=tk;++i)
{
int h=Hash(used[i].t1,used[i].t2);
for(int j=1;j<=pig[p].cnt[h][0];++j)
{
two& xa=pig[p].aa[pig[p].cnt[h][j]];
if(fabs(xa.t1-used[i].t1)<eps
&&fabs(xa.t2-used[i].t2)<eps)
{
return true;
}
}
}
return false;
}
int sumans;
void solve(int pos,int sum)
{
if(pos==1)
sumans=2147483647,tk=0;
if(pos==n+1)
{
if(sum<sumans)
sumans=sum;
return;
}
if(m==1&&sum>(n/3+1+1))
{
return;
}
if(killed(pos))
{
solve(pos+1,sum);
}
else if(pig[pos].kaa!=0)
{
for(int i=1;i<=pig[pos].kaa;++i)
{
used[++tk]=pig[pos].aa[i];
solve(pos+1,sum+1);
--tk;
}
}
else solve(pos+1,sum+1);
}
int main()
{
freopen("angrybirds.in","r",stdin);
freopen("angrybirds.out","w",stdout);
scanf("%d",&t);
for(int e=1;e<=t;++e)
{
inPut();
Init();
solve(1,0);
printf("%d\n",sumans);
}
return 0;
}
|
这样只能过60分，剩下的点TLE。
