Hack&请求撤下题解

原帖。数据过水被暴力搞过去了，请求撤下暴力题解：题解1和题解2

Hack1 的 in 的程序 & out：

CPP

//in:
#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("1.in","w",stdout);
	int n=100000,t=(n-2)/2,m=t*3;
	cout<<n<<" "<<m<<'\n';
	for(int i=2;i<=t+1;i++)
		cout<<"1 "<<i<<" 1\n";
	for(int i=2;i<=t+1;i++)
		cout<<i<<" "<<t+2<<" 1\n";
	for(int i=t+2;i<n;i++)
		cout<<i<<" "<<i+1<<" 1\n";
	return 0;
}
//out: 50001.00

原理如图，暴力程序每次从

1

开始抵达终点，但当

t

接近

\dfrac n 2

时，时间复杂度约为

O(\dfrac{n^2}4)=O(n^2)

，超时。

Hack2 的 in 的程序 & out：

CPP

//in:
#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("2.in","w",stdout);
	int n=100000,t=n/3,m=t*4;
	cout<<n<<' '<<m<<'\n';
	for(int i=1;i<=t;i++){
		cout<<i*3-2<<' '<<i*3-1<<" 1\n";
		cout<<i*3-1<<' '<<i*3+1<<" 1\n";
		cout<<i*3-2<<' '<<i*3<<" 1\n";
		cout<<i*3<<' '<<i*3+1<<" 1\n";
	}
	return 0;
}
//out: 66666.00

原理类似，用一堆分岔路增加递归数量，暴力程序的时间复杂度此时为

O(2^{\frac n 3})

。

Hack&请求撤下题解

讨论操作

回复

相关推荐

Hack&请求撤下题解