好久没写总结了

这几天都是上午下午连着考

所以貌似没时间

直接进入正题

【正题之前：这套题TM真的是NOIP模拟？】

Day1

1.rho

首先密度最大的时候肯定是一条边两个点

证明一下

假设有三个点两条边（肯定比三条边优吧）

那么密度为

显然总能找到其中一条边两个点使（当且仅当v1=v2=v3=0时等号成立（也许吧））

所以枚举每一条边就可以了

代码：

// <rho.cpp> - 10/28/15 08:19:18
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
int dq[10001];
double ans;
int main(){
	freopen("rho.in","r",stdin);
	freopen("rho.out","w",stdout);
	int n=getint(),m=getint();
	for(int i=0;i<n;i++)dq[i]=getint();
	for(int i=0;i<m;i++){
		int u=getint()-1,v=getint()-1,w=getint();
		ans=max(ans,double(dq[u]+dq[v])/double(w));
	}
	printf("%.6lf",ans);
	return 0;
}

// <rho.cpp> - 10/28/15 08:19:18

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <ctime>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

int dq[10001];

double ans;

int main(){

freopen("rho.in","r",stdin);

freopen("rho.out","w",stdout);

int n=getint(),m=getint();

for(int i=0;i<n;i++)dq[i]=getint();

for(int i=0;i<m;i++){

int u=getint()-1,v=getint()-1,w=getint();

ans=max(ans,double(dq[u]+dq[v])/double(w));

}

printf("%.6lf",ans);

return 0;

}

2.light

没A不写了

反正是最短路

3.permutation

没A不写了

反正不会主席树

Day2

1.triangle

先找规律

发现第n行第m列为

然后就可以做了

先预处理出1到100000的阶乘

然后用费马小定理+快速幂每次求逆元就好了

代码：

// <triangle.cpp> - 10/29/15 08:33:15
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
const int mod=1000000009;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
lol pow(lol a,int b){
	lol ans=1;
	while(b!=0){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
lol ans,jc[100001];
int main(){
	freopen("triangle.in","r",stdin);
	freopen("triangle.out","w",stdout);
	jc[0]=1;
	for(int i=1;i<=100000;i++)jc[i]=(jc[i-1]*i)%mod;
	int T=getint();
	while(T--){
		int a=getint(),b=getint(),n=getint(),m=getint();
		ans=pow((lol)a,n-m)*pow((lol)b,m-1)%mod;
		ans=ans*jc[n-1]%mod*pow((lol)jc[m-1],mod-2)%mod*pow((lol)jc[n-m],mod-2)%mod;
		cout<<ans<<endl;
	}
	return 0;
}

// <triangle.cpp> - 10/29/15 08:33:15

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

const int mod=1000000009;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

lol pow(lol a,int b){

lol ans=1;

while(b!=0){

if(b&1)ans=ans*a%mod;

a=a*a%mod;

b>>=1;

}

return ans;

}

lol ans,jc[100001];

int main(){

freopen("triangle.in","r",stdin);

freopen("triangle.out","w",stdout);

jc[0]=1;

for(int i=1;i<=100000;i++)jc[i]=(jc[i-1]*i)%mod;

int T=getint();

while(T--){

int a=getint(),b=getint(),n=getint(),m=getint();

ans=pow((lol)a,n-m)*pow((lol)b,m-1)%mod;

ans=ans*jc[n-1]%mod*pow((lol)jc[m-1],mod-2)%mod*pow((lol)jc[n-m],mod-2)%mod;

cout<<ans<<endl;

}

return 0;

}

2.interval

我做的是非正解n方算法

枚举每一个k，向两边扩展

用m[i]记录向左扩展到i时区间最长值

可以发现从k到k扩展到的最右端点之间是不可能存在比k更优的结果的

于是搜完k直接从扩展到的最右端点+1处再扩展就好了

于是就能骗过了

代码：

// <interval.cpp> - 10/29/15 08:33:15
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
int a[500001];
int m[500001];
int main(){
	freopen("interval.in","r",stdin);
	freopen("interval.out","w",stdout);
	int n=getint(),MAX=0;
	for(int i=0;i<n;i++){
		a[i]=getint();
		if(a[i]==1){cout<<n-1<<" "<<1<<endl<<1;return 0;}
	}
	for(int i=0;i<n;i++){
		int l=0;
		int k;
		for(k=i+1;k<n&&a[k]%a[i]==0;k++)l++;
		for(k=i-1;k>=0&&a[k]%a[i]==0;k--)l++;
		m[k+1]=max(m[k+1],l);
		MAX=max(MAX,m[k+1]);
	}
	int sum=0;
	for(int i=0;i<n;i++)if(m[i]==MAX)sum++;
	cout<<MAX<<" "<<sum<<endl;
	for(int i=0;i<n;i++)if(m[i]==MAX)cout<<i+1<<" ";
	return 0;
}

// <interval.cpp> - 10/29/15 08:33:15

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

int a[500001];

int m[500001];

int main(){

freopen("interval.in","r",stdin);

freopen("interval.out","w",stdout);

int n=getint(),MAX=0;

for(int i=0;i<n;i++){

a[i]=getint();

if(a[i]==1){cout<<n-1<<" "<<1<<endl<<1;return 0;}

}

for(int i=0;i<n;i++){

int l=0;

int k;

for(k=i+1;k<n&&a[k]%a[i]==0;k++)l++;

for(k=i-1;k>=0&&a[k]%a[i]==0;k--)l++;

m[k+1]=max(m[k+1],l);

MAX=max(MAX,m[k+1]);

}

int sum=0;

for(int i=0;i<n;i++)if(m[i]==MAX)sum++;

cout<<MAX<<" "<<sum<<endl;

for(int i=0;i<n;i++)if(m[i]==MAX)cout<<i+1<<" ";

return 0;

}

3.bwg

这道题直接暴力加一点剪枝就能过了【数据太水】

然而我不想写了

那就END了XD