Day3祭总结

时间线：

• 8：00~8：30 读完题面+T1 30pts
• 8：30~9：30 T2暴力（人类智慧玄学？）
• 9：30~10：00（划水？？？）+重新读T3、T4
• 10：00整 伴随厕所装修的阴乐去实验楼并且在路上莫名想到T1正解
• 10：10~10：40 疯狂搞T1
• 10：40~11：00（摆大烂？？？）开始花时间轴，（认真）思考剩下1.5h干什么（想念贪吃蛇
• 11：00~12：00 T4打表暴力
• 12：00~12：30 T3水分
• 1：00 老师调整测评姬文末换行不再卡分

T1：P2312 [NOIP2014 提高组] 解方程 

qwq 第一眼：不会是高精度吧！应该跟数论有关  算了算了，先拿30再说。打完T2的人类智慧后，开始反复摇摆：？？？先想T1还是先敲T3T4呢，然后去了趟实验楼，电梯里突然想到昨天讲的BSGS，又联想到Hash，随后反应锅来可以左右都对大质数取模  回来之后赶紧敲出来，发现是可以有的，怕遇上生日悖论，有搞了一组大质数

刚交卷：好耶！蒟蒻居然想到了正解！！！跑完后：挂。。。具体原因在于负数取模的地方忘记处理了（以及快读因为平时不写而写得极其丑陋qwq）善良的lb老师改过之后——100pts(圣光普照）

啊对了，习惯性写qp是不对的，平白多了一个log，其实一遍加一遍乘是完全可以的（3个T）

#include
using namespace std;
#define int long long
int n,m,ans[100010],cnt,f=1;
const int p1=1e9+7,p2=998244353;
pair<int,int> read()
{
	pair<int,int>x;
	x.first=x.second=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')
	{
		x.first=(x.first*10+ch-'0')%p1;
		x.second=(x.second*10+ch-'0')%p2;
		ch=getchar();
	}
	return x;
}
pair<int,int>aa[100010];
int a1[100010],a2[100010];
bool check(int x)
{
	int res1=0,res2=0;
	for(int i=n;i>=1;i--)
	{
		res1=((res1+a1[i])*x)%p1;
		res2=((res2+a2[i])*x)%p2;
	}
	if((res1+a1[0])%p1==0&&(res2+a2[0])%p2==0) return 1;
	else return 0;
}
signed main()
{
	//freopen("equation.in","r",stdin);
	//freopen("equation.out","w",stdout);
	scanf("%lld%lld\n",&n,&m);
	for(int i=0; i<=n; i++)
	{
		f=1;
		aa[i]=read();
		a1[i]=aa[i].first*f;
		a2[i]=aa[i].second*f;
	}
	for(int i=1;i<=m;i++)//枚举x 
	{
		int res1=0,res2=0;
		if(check(i)) ans[++cnt]=i;
	}
	printf("%lld\n",cnt);
	for(int i=1;i<=cnt;i++) printf("%lld\n",ans[i]);
	return 0;
}

T2：P4423 [BJWC2011]最小三角形 

跟P7883 平面最近点对（加强加强版） 差不多，但是由于那道题我是人类智慧过掉的，所以这里我也尝试了人类智慧，随机数据非常善良，乱搞60pts，本来很开心，但是当我得知：一次扫7个点即可AC时（我一次扫6个点），我裂开了qwq

 对此，lb老师的建议：其实你可以用时间随机一个5~10的数，然后考完试去找裁判重测~反正取最高分吗  随机数代码：

srand(time(0)); int x=rand()%5+5; cout<

#include
using namespace std;
#define int long long
#define debug cout<<"!!!!!!!!!!";
int n;
double ans=1e9;
struct node{double x,y;}a[100010];
bool cmp(node aa,node bb)
{ return aa.x!=bb.x?(aa.x
double dis(int i,int j)
{ return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)); }
double calc(int m)
{
	for(int i=1;i<=n;i++)
	{
		double xx=a[i].x,yy=a[i].y;
		a[i].x=cos(m)*xx-sin(m)*yy;
		a[i].y=sin(m)*xx+cos(m)*yy;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n&&j<=i+7;j++)
	for(int k=j+1;k<=n&&k<=j+7;k++)
	{
		double temp;
		temp=dis(i,j)+dis(j,k)+dis(i,k);
		ans=min(ans,temp);
	}
}
signed main()
{
	srand(time(0));
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
	calc(rand()%360);
	calc(rand()%360);
    calc(rand()%360);
	printf("%.6lf",ans);
	return 0;
}