4-29模拟题

星座

题目描述

世界上有两种人,数星星的人和画星座的人
为了探索我们头顶那美丽的星空,伟大的 C 学给了我们一张星图,这张星图 可以看做一个平面,其中包含了 $n $颗星星,每颗星星可以用平面上的一个点来表 示,C 学告诉我们这张星图中包含着多种神奇的$α- β- γ$星座,这些星座在平 面内构成了很多平行四边形,它们的都有一组边长为γ的对边平行于 $x$ 轴,且另 一组对边平行于一斜率为 $β/ α$的直线, 现在 C 学给了我们若干组询问,每组 询问包含 3 个整数$ α, β和 γ$,对于每组询问请你求出$ x$ 轴上方和下方中$ α- β- γ$星座的个数 (平行四边形不能与 $x $轴有相交的部分)

输入格式与数据范围

第 $1 $行$ 2 $个正整数 $n, m $表示星星的个数 和 询问的个数 ($4 ≤ n ≤ 100000, 1 ≤ m ≤ 10$)

第 $2~n+1 $行 每行$ 2 $个整数$ x, y $表示每颗星星的横纵坐标 ($-1000 ≤ x ≤ 1000, -1000 ≤ y ≤ 1000 $) (数据保证不会有两颗星星在同一个位置)

第 $n+2~n+m+1 $行 每行 $3 $个整数$ α, β$和 $γ$($1 ≤ α≤ 2000,-2000 ≤ β≤ 2000 和 1 ≤ γ≤ 2000$) (当$β= 0 $时,表示一条平行于$ y $轴的直线)

输出格式

输出共 $m $行

每行两个整数 表示 $x$ 轴上方满足条件星座个数 和 $x$ 轴下方满足条件星座 个数

样例

【样例输入】

8 1

1 1

2 1

1 2

2 2

1 -1

2 -1

1 -2

2 -2

1 0 1

【样例输出】

1 1

题解

几何题还是要多画图啊。首先,满足斜率条件的点,肯定与$x$轴有唯一的交点,按这个交点排序之后,只要用一个映射来表示这个点右边距离是$\gamma$有没有点来判断即可,对于相同的$y,x_0$只要分别计算出右边距离为$\gamma$的,放入集合中,计算$c(size,2)$即可。

注意精度是大坑。

code

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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e5+1e3+7;
const double eps=1e-6;
int c[N][3],has[4100][4100];
int n,m,cnt;
struct node{
int x,y;
double x0;
}p[N];
bool cmp(node a,node b)
{
if((fabs(a.x0-b.x0)<eps))
return a.y>b.y;
else
return a.x0<b.x0+eps;
}
void calcC()
{
for(int i=1;i<N;i++)
c[i][0]=1;
c[0][0]=1;
for(int i=1;i<N;i++)
for(int j=1;j<=2&&j<=i;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
int main()
{
freopen("star.in","r",stdin);
freopen("star.out","w",stdout);
calcC();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(y)
p[++cnt].x=x,p[cnt].y=y,has[x+1500][y+1500]=1;
}
n=cnt;
while(m--)
{
int a,b,v,ans1=0,ans2=0;
scanf("%d%d%d",&a,&b,&v);
if(b==0)
a=0,b=1;
for(int i=1;i<=n;i++)
p[i].x0=(double)p[i].x-(double)p[i].y*(double)(a)/(double)(b);
sort(p+1,p+n+1,cmp);
int i=1;
while(i<=n)
{
cnt=0;
while(abs(p[i].x0-p[i+1].x0)<eps&&p[i].y>0)
{
if(has[p[i].x+1500+v][p[i].y+1500])
cnt++;
i++;
}
if(has[p[i].x+1500+v][p[i].y+1500]&&p[i].y>0)
cnt++;
ans1+=c[cnt][2];
cnt=0;
while(abs(p[i].x0-p[i+1].x0)<eps&&p[i].y!=0)
{
if(has[p[i].x+1500+v][p[i].y+1500])
cnt++;
i++;
}
if(has[p[i].x+1500+v][p[i].y+1500]&&p[i].y<0)
cnt++;
ans2+=c[cnt][2];
i++;
}
printf("%d %d\n",ans1,ans2);
}
}

W 的火星工程

题目描述

大老板 W 的伟大工程扩大到了火星,他准备在火星建立一个自己的度假村。在他的度假村里,有两个大饭店 A,B。对于 W 来说,修建度假村必不可少的就

是从 A 饭店向 B 饭店修路,以保证他可以短时间内享受各种美味。火星上有一些中转站,中转站之间以及它们与饭店之间有路径使得能从一个到达另一个(路径为单向)。对于每一条路径,工程师 ZQ 给出了它的两个消费参数 a, b。W 会从A 饭店出发,经过其中的一些路径,最终到达 B 饭店。W 希望他走过的所有道

路的 $\frac {\sum a} {\sum b}$最小,也就是那些道路的 $a$ 值之和除以他们的$ b$ 值之和最小。可是路径实在太多了,W 不知道该如何选择。聪明的你需要帮助他计算出这

个最小值。至于路径的选取方法你就不需要告诉他了。

输入格式

输入两个整数 $n,m$,表示中转站的数量和边的数量。

随后 $m$ 行,每行四个整数 $x,y,a,b$,分别表示路径的两端,路径的$ a,b$ 消费参数。

其中 $0$ 号点与 $n+1$ 号点分别表示 W 的两个饭店 A,B。

注意你并不需要把所有中转站都连入路中,只要保证从 A 饭店可以到达 B饭店就行了。

输出格式

输出一个小数,表示所求的最小值。输出保留小数点后 6 位(printf 保留6位即可)。

样例

【样例输入】

2 3

0 1 1 2

0 2 2 3

1 3 1 3

【样例输出】

0.400000

数据范围

对于 20%的数据,$n, m ≤ 100$;

对于 50%的数据,$n ≤1000$;

对于 100%的数据,$1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000, 0 ≤ x, y ≤ n+1,0 < a,b ≤ 100000$;

数据保证 $0$ 号饭店可以到达$ n+1 $号饭店,任意两个中转站或饭店间最多有一条边,且保证没有路可以构成环。

题解

裸的零一分数规划。因为没有看到单向边,谢了奇怪的判断,各种不知道怎么处理负环,挂掉了。推一下式子吧。

求$min{\frac {\sum a} {\sum b}}$

令$ans=min{\frac {\sum a} {\sum b}}$

设一个布尔数组$x[i]$代表第$i$条边的选择。

则$ans=\frac {\sum a[i]x[i]} {\sum b[i]x[i]}$

设一个函数$f(t)=\sum a[i]x[i]-t\sum b[i]x[i]$

显然函数还跟边的选择有关。但是当$t=ans$时,是可以找出一种选择满足题目条件。

我们可以二分这个$t$,然后只要保证函数最小值大于零以及单调性来判断$t$如何变化。

构造新边$a[i]-tb[i]$,此时函数最小值就是最短路。

然后裸的SPFA或者堆优化dijkstra。

code

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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e4+1e2+7,M=1e5+1e3+7;
const double eps=1e-8;
queue<int>q;
struct node{
int to,a,b,ne;
double tw;
}edg[M*2];
int head[N],cnt=1,n,m;
bool inq[N];
double d[N];
void build(int u,int v,int a,int b)
{
cnt++;
edg[cnt].to=v;
edg[cnt].a=a;
edg[cnt].b=b;
edg[cnt].ne=head[u];
head[u]=cnt;
}
bool spfa(double val)
{
for(int i=0;i<=n+1;i++)
d[i]=M;
memset(inq,false,sizeof(inq));
double ret=0;
for(int i=2;i<=cnt;i++)
edg[i].tw=(double)edg[i].a-(double)edg[i].b*val;
q.push(0);
d[0]=0;
inq[0]=true;
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=false;
for(int tmp=head[u];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(d[v]>d[u]+edg[tmp].tw)
{
d[v]=d[u]+edg[tmp].tw;
if(!inq[v])
q.push(v),inq[v]=true;
}
}
}
return d[n+1]<eps;
}
int main()
{
freopen("wproject.in","r",stdin);
freopen("wproject.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,a,b;
scanf("%d%d%d%d",&x,&y,&a,&b);
build(x,y,a,b);
build(y,x,a,b);
}
double l=0,r=M;
while(r-l>eps)
{
double mid=(l+r)/2;
if(spfa(mid))
r=mid;
else
l=mid;
}
printf("%.6lf",l);
}

A-B=C

题目描述

今天 HYX 同学由于兼爱平生,同时也为了练习如何讲题,来到幼儿园去教小朋友们学习减法,现在他手上有很多盒小木棍,他需要用这些小木棍摆出 A-

B=C 的样子来教小朋友学减法,这时有个聪明机智可爱的小女孩问了 HYX 同学这样一个问题“对于每一盒小木棍能摆出多少形如 A-B=C 式子(对于每一个摆出

的式子要求将小木棍用完)”,HYX 很想回答她的问题,但他发现这并不是一个很好解决的问题,所以为了解决小女孩的问题,HYX 同学希望你能帮它算一算

对于他的每一个盒子所能摆出算式的的数量,当然由于这个数可能很大你只需要输出答案取模 1e9+7 后的值就可以了。(因为小女孩还很年幼,所以她还不知道

0 概念,所以要求 A,B,C 均为正整数,且不能有前导 0) 说明:等号和减号需要使用木棍

数字的样式:

(无图请脑补)

输入输出格式

输入格式
从文件 subtraction.in 中输入数据。

第一行 一个正整数 T 表示 HYX 同学手中盒子的数量

接下来 T 行 每行一个整数 表示每个盒子中小木棍的数量
输出格式
输出到文件 subtraction.out 中。

输出 T 行 第 i 行输出 以 Case #i: ans 的形式输出 ans 为第 i 个盒子所能摆出形如 A-B=C 的式子的个数

样例

【样例输入】

3

1

12

20

【样例输出】

Case #1: 0

Case #2: 1

Case #3: 38

数据范围

对于 $20%$的数据 $1 ≤ T ≤ 10, 1 ≤ N ≤ 24$

对于 $80%$的数据 $1 ≤ T ≤ 30, 1 ≤ N ≤ 500$

对于 $100%$的数据 $1 ≤ T ≤ 1e7, 1 ≤ N ≤ 1e6$

题解

状态转移方程如下,采用记忆化搜索实现。


code

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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e6+1e3+7;
int need[]={6,2,5,5,4,5,6,3,7,6};
int need0[100];
int need1[100];
const int P=1e9+7;
ll dp[N][2][2][2];
bool vis[N][2][2][2];
ll DP(int w,bool s1,bool s2,bool u)
{
if(!s1&&!s2)
{
if(u==0&&w==3)
return 1;
if(u==1&&w==5)
return 1;
return 0;
}
if(w<=3)
return 0;
if(vis[w][s1][s2][u])
return dp[w][s1][s2][u];
vis[w][s1][s2][u]=true;
ll &val=dp[w][s1][s2][u];
val=0;
if(s1&&s2)
{
for(int i=1;i<10;i++)
{
val+=DP(w-need[i]-need[0]-need[(i+u)%10],0,1,i+u>9);
val+=DP(w-need[i]-need[0]-need[(i+u)%10],1,1,i+u>9);
val+=DP(w-need[i]-need[0]-need[(i+u)%10],1,0,i+u>9);
val+=DP(w-need[i]-need[0]-need[(i+u)%10],1,1,i+u>9);
}
for(int i=1;i<10;i++)
for(int j=1;j<10;j++)
{
val+=DP(w-need[i]-need[j]-need[(i+j+u)%10],1,1,i+j+u>9);
val+=DP(w-need[i]-need[j]-need[(i+j+u)%10],0,1,i+j+u>9);
val+=DP(w-need[i]-need[j]-need[(i+j+u)%10],1,0,i+j+u>9);
val+=DP(w-need[i]-need[j]-need[(i+j+u)%10],0,0,i+j+u>9);
}
val+=DP(w-need[0]-need[0]-need[u%10],1,1,u>9);
}
else
if(s1)
{
for(int i=1;i<10;i++)
{
val+=DP(w-need[i]-need[(i+u)%10],0,0,i+u>9);
val+=DP(w-need[i]-need[(i+u)%10],1,0,i+u>9);
}
val += DP(w-need[0]-need[u%10], 1, 0, u>9);
}
else
if(s2)
{
for(int i=1;i<10;i++)
{
val+=DP(w-need[i]-need[(i+u)%10],0,0,i+u>9);
val+=DP(w-need[i]-need[(i+u)%10],0,1,i+u>9);
}
val += DP(w-need[0]-need[u%10], 0, 1, u>9);
}
val%=P;
return val;
}
void exec()
{
int t,x;
for(int i=4;i<=1000;i++)
{
DP(i,1,1,0);
DP(i,1,0,0);
DP(i,0,1,0);
DP(i,1,1,1);
DP(i,1,0,1);
DP(i,0,1,1);
}
scanf("%d",&t);
for (int i=1;i<=t;++i)
{
scanf("%d",&x);
putchar('C'), putchar('a'), putchar('s'), putchar('e'), putchar(' '), putchar('#');
printf("%d:",i);
putchar(' ');
printf("%lld\n",DP(x,1,1,0));
}
}
int main()
{
freopen("subtraction.in", "r", stdin);
freopen("subtraction.out", "w", stdout);
exec();
}