P2831 앵그리버드 문제풀이

CSDN 동기화
원제 링크
제목 요약:
평면 직각 좌표계의 첫 번째 상한에는 몇 개의 녹색 돼지가 있는데 작은 새는 몇 개의 함수 해석선을 통해 그것들을 없애야 한다.작은 새마다 모든\(y=ax^2+bx(a<0)\)의\(x, y)\)의 모든 녹색 돼지를 없앨 수 있다. 물론 녹색 돼지가 없으면 그냥 간다.최소한 몇 번은 녹색 돼지를 모두 처치할 수 있는지 물어보시오.\(T\) 그룹 데이터.

전기.

실제로 이전에 사기분도론을 한 편 썼는데, 그 안에는 약간 허튼소리를 했다. 기왕 자신이 할 수 있다고 말한 이상 구덩이를 메우지 않겠는가?

계산법 1

\(70\%\)의 데이터에 대해\(n\leq 12\).
실제로는 직접 수색하면 된다.
어떻게 뒤져요?모든 검색 상태에 대해 현재 남은 녹색 돼지의 좌표를 기록하고 현재 걸음수를 기록할 수 있습니다.
\(\text{vector}\)는 요소를 쉽게 삭제할 수 있기 때문에 현재\(\text{vector}\)의 두 좌표를 열거하여\(a, b\)의 값을 계산한 다음\(a<0\)를 판단하고 합법적으로 모든\(y=ax^2+bx\)의 녹색돼지를 삭제하고 다음 층으로 들어갑니다.
이렇게 하면\(\text {long double}\) 를 열지 않으면\(55pts\) 를 얻을 수 있습니다.
켜면\(70pts\)입니다.얼굴이 까맣다
시간 복잡도:\(O (\text {70pts})\.
예상 점수:\(60pts\).실제 점수:\(70pts\).
Link 코드
폭력이 제일 강해!

계산법 2

\(100\%\)의 데이터에 대해\(n\leq 18\),\(T\leq 5\).
분명히, 우리는 위의 검색에서 쓸데없는 상태가 너무 많다는 것을 발견할 것이다.
예를 들어\(1,4\)를 같이 치고\(2,3\)를 같이 치는 것과 때리는 순서를 바꾸는 것은 본질적으로 어떤 차이가 있습니까?아니오. 그러나 검색에서 같은 상태를 반복적으로 검색하는 것과 비슷한 현상이 대량으로 나타날 수 있습니다. 피보나치 수열처럼 굴러갈수록 커지고, 결국\(\text {TLE}\) 라고 생각할 것입니다.
위에서 말한 바와 같이 데이터를 만들어서 두 마리의 녹색 돼지가 함께 칠 수 없도록 보증한다. 즉, 매번 하나만 죽일 수 있다면 이 프로그램의 시간 복잡도\(\cdots\cdots\)
그래서 우리는 이 문제를 해결하고 싶지만,\(\texttt {map >>}\) 를 사용하는 것은 정말 좋지 않다.\(\log\) 가 하나 더 있으면 정해의 음차와 양차가 다르다고 생각한다.그래서 기억화 검색의 본질은\(\text{dp}\)가 아닌가?열거 상태의\(\text{dp}\)는\(\cdots\cdots\)가 아닙니다.
상태 압축\(\text{dp}\), 약칭 상압!
우리는 2진수로 현재 상태를 표시할 수 있다. (분명히 두 가지 상황만 쳤을 뿐, 두 가지 상황은 치지 않았을 뿐이다.) 그리고 모든 해석선 (적어도 두 마리의 녹색 돼지를 쳤을 수 있는) 을 함께 통계한 다음에 매거 상태가 이동하면 된다.그러나 이 견해는 명확하지 않아 이론 모델을 세워야 한다.
\(f\)로 상태를 저장하면\(f 0\)~\(f {{2^n}-1}\)가 모든 상태가 됩니다.현재 해석선을 없앨 수 있는 돼지도 이진수가\(s\)에 존재하고 매거 상태가 될 때마다 모든\(s\)에 대해 이동을 고려해야 한다.

f[k|s[i]]=min(f[k|s[i]],f[k]+1);

즉, 현재 선에\(i\)가 있으면 직접 선으로 해결합니다.그렇지 않으면\(+1\).
하지만 녹색 돼지는 단독으로 맞을 수 있고 다른 돼지와 함께 맞을 수 없다는 것을 발견했다.
이런 돼지에 대해 우리는 모든 돼지를 다시 한 번 열거해서 그것을 갱신해야 한다.

f[k|(1<

분명히 제\(k\)개 상태에 대해 현재 모든 돼지가 맞은 답안은 직접 업데이트하여 이 문제를 해결할 수 있습니다.
마지막\(f {2^n}-1}\)가 답입니다.
시간 복잡도:\(O(2^n\cdot n^2)\).(그러나\(\text{AThousandSuns}\)는\(O(2^n\cdotn)\)의 알고리즘을 제시했다.AThousandSuns의 로곡 블로그 참조)
예상 점수:\(85pts\).실제 점수:\(100pts\).
이론적으로 약\(8.4\times 10^7\)로 꽉 차서 위험하다. 사이드볼이 지나갔다.
기억화 검색이 왜 통과되지 않는지 알 수 있습니다. 기억화는\(\text{map}\) 의 시간 복잡도가\(O (2^n\cdot n^2\log n)\) 이기 때문에\(4\) 배의 상수가 많아져서\(2.7\times 10^8\) 더 위험한 단계에 성공했습니다.물론 상수가 좋으니까 카드가 지나가도 저는 아무 말도 안 할게요.
주의: 해석식을 계산할 때 일정한 정밀도 문제가 있을 수 있으므로\(10^{-6}\)를 보류하면 됩니다.

#pragma GCC optimize(2)
#include
using namespace std;

#define db long double
const int N=1e6+1; 

inline int read(){char ch=getchar(); int f=1; while(ch'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}

inline void write(int x) {
	if(x<0) {putchar('-');write(-x);return;}
	if(x<10) {putchar(char(x%10+'0'));return;}
	write(x/10);putchar(char(x%10+'0'));
}

int n,m,T,cnt=0;
int f[N],s[501];
db x[101],y[101];

int main() {
	T=read(); while(T--) {
		n=read(),m=read();
		memset(f,0x3f,sizeof(f));
		memset(s,0,sizeof(s));
		cnt=0; f[0]=0; //   
		for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
		for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(x[i]-x[j]) {
				double a=(y[i]-y[j]*x[i]/x[j])/x[i]/(x[i]-x[j]);
				double b=(y[i]*x[j]*x[j]/x[i]/x[i]-y[j])/(x[j]*x[j]/x[i]-x[j]);
				if(a<0) { //        
					cnt++;
					for(int k=1;k<=n;k++)
						if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<=1e-6) s[cnt]|=(1<