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();
}