Processing math: 100%

HDU6627 equation(分段函数求值)

Posted on | Post modified:

HDU6627 equation(分段函数求值)

题目链接

题意：

两个长度为n的数组a和b和一个正整数C，计算有多少个x满足：

n∑i=1|ai⋅x+bi|=C

思路：

该函数为分段函数，每段的转折点为−biai,先把转折点排序，计最开始的函数值为x⋅suma+sumb,每过一段，就会有一个|ai⋅x+bi|由ai⋅x+bi变为−ai⋅x−bi,那么suma−2⋅ai,sumb变为sumb−2⋅bi。每段函数都是线性的，大力枚举计算即可。然后对答案进行排序(博主忘记排序结果Wa到爆炸)。

代码：

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
#include<bits/stdc++.h>

using namespace std;
const int N = 2e5+100;
struct node{
	long long a,b;
}s[N];
int n;double c;
bool cmp(node x,node y){
	return (x.b*y.a)<(x.a*y.b);
}
bool cmp2(pair<long long, long long> a,pair<long long,long long> b){
	return a.first*b.second<a.second*b.first;
}
vector<pair<long long,long long>> ans;
void make(long long x,long long y){
	if(x==0){
		y=1;
		ans.push_back({x,y});return ;
	}
	long long gg=__gcd(x,y);
	x/=gg;y/=gg;
	if(y<=0){
		x=-x;y=-y;
	}
	ans.push_back({x,y});
	return ;
}
void solve(){
	ans.clear();
	scanf("%d %lf",&n,&c);
	long long sa=0;long long sb=0;
	for(int i=1;i<=n;i++){
		 scanf("%lld %lld",&s[i].a,&s[i].b);
		 sa+=s[i].a;
		 sb+=s[i].b;
	}
	sort(s+1,s+n+1,cmp);
	double up=9999999999999;
	double down=-1.0*double(s[1].b*sa)/double(s[1].a)+sb;
	if(c>=down&&c<=up){
		long long u=(long long)c-sb;
		long long d=sa;
		make(u,d);
	}
	bool flag=0;
	for(int i=2;i<=n;i++){
		double nowr=(-1.0*double(s[i].b)*(sa-2*s[i-1].a)/double(s[i].a))+(sb-2*s[i-1].b);
		double bef=(-1.0*double(s[i-1].b)/double(s[i-1].a))*(sa)+(sb);
		up=max(nowr,bef);
		down=min(nowr,bef);
		if(up==down&&up==c){
			flag=1;break;
		}
		sa-=2*s[i-1].a;
		sb-=2*s[i-1].b;
		if(c>=down&&c<=up){
			long long u=(long long)c-sb;
			long long d=sa;
			make(u,d);			
		}
	}
	sa-=2*s[n].a;
	sb-=2*s[n].b;
	up=9999999999999;
	down=-1.0*double(s[n].b*sa)/double(s[n].a)+sb;
	if(c>=down&&c<=up){
		long long u=c-sb;
		long long d=sa;
		make(u,d);
	}
	if(flag) puts("-1");
	else{
		sort(ans.begin(),ans.end(),cmp2);
		int siz=unique(ans.begin(),ans.end())-ans.begin();
		printf("%d",siz);
		for(int i=0;i<(int)siz;i++) printf(" %lld/%lld", ans[i].first,ans[i].second);
		puts("");
	}
}
int main(){
	int T;scanf("%d",&T);
	while(T--) solve();
	return 0;
}

/*
2 6
0 4
-2 -6
*/