2529: [Poi2011]Sticks - #include <Seter> - using namespace Orz;

2529: [Poi2011]Sticks

Seter posted @ 2012年1月20日 13:37 in BZOJ with tags POI Enumeration , 2360 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=2529

RunID User Problem Result Memory Time Language Code Length Submit Time
192197 Seter 2529 Accepted 23272 kb 1660 ms C++/Edit 869 B 2012-01-20 10:00:00

交错语言CE一次……嘛……2Y魔咒的威力……【不过先有小号1Y的!而且由于很多题目无爱的刷Rank导致2Y也加AC率……】

一开始觉得是神题……只会N^3的暴力555……

这题只要给出任意一组解就可以了,这个条件挺重要的……

【尼玛气死我了,写了半天的题解,结果提交失败,现在只剩下上面那几句了,气死我了!!!我还是写简单版吧反正是水题!!】

先排序,然后对于第i根及以前的棍子中,选择前三长的(当然要不同颜色),如果还不能组成三角形,则说明不存在最长边是第i根棍子的三角形。如果对于每个i都solve一遍还没有,则无解。

于是记录前i根中前三长的异色棍子。第i+1根的颜色如果在这三根中有,则直接替代;否则替代三根中最小的那根即可。

证明自己证……打得累死最后还被吞了,气死我了!!

C++的sort比C的qsort快很多……

 

#include <cstdio>
#include <algorithm>
#define x first
#define y second
using namespace std;
int k,n,s;
pair<int,int> a[1000000],ans[3];
char str[15000000],*p=str;
inline int getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}int main(){
	int i=0,j,N;fread(p,1,15000000,stdin);
	for(k=getint();i++!=k;)for(j=-1,n+=N=getint();++j!=N;)a[s++]=make_pair(getint(),i);
	sort(a,a+s);ans[0]=ans[1]=ans[2]=make_pair(-1,-1);
	for(i=-1;++i!=s;){
		if(ans[0].y==a[i].y)ans[0]=a[i];
		else if(ans[1].y==a[i].y){ans[1]=ans[0];ans[0]=a[i];}
		else{ans[2]=ans[1];ans[1]=ans[0];ans[0]=a[i];}
		if(ans[0].x<ans[1].x+ans[2].x)return printf("%d %d %d %d %d %d\n",ans[0].y,ans[0].x,ans[1].y,ans[1].x,ans[2].y,ans[2].x),0;
	}puts("NIE");
	return 0;
}
By Seter
Alyssa 说:
2022年12月26日 20:08

A stack of sticks is one of the most basic and essential pieces of equipment for any kind of campfire. Even if you don't have a lot of other materials, a few sticks can give you the fire you need to cook food or keep warm. If you're in a forest, look for deadwood that you can break into small pieces. If you Lab grown diamonds can find a downed tree, that's even better. Once you have your sticks, you'll need to gather some tinder - dry leaves, grass, bark, or anything else that will catch fire easily.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee