noip模拟赛#38

我打开了#39的problem。。。想了半个小时多发现我一道题都不会写。。。于是我打开了#38的problem

T1：循环数字的定义为能够将该数划分为若干相同长度的段并且都相同。 n=2e18.

=>我只会70%的暴力。。。

正解：

对于[L,R]内的循环整数个数，可以看成是[1,R]内的循环整数个数减去[1,L-1]内的循环整数个数。

对于确定了循环节长度i以及数字长度n的循环整数，在[1,x]内的个数可以用MAX{x div k-10^(i-1)+1,0}算出，其中k是i-1个0，1个1，循环n div i次所得的数字。

例如，若求[1,666666]内长度为6的循环节长度为3的数字只需要用666666 div 1001-100+1=567.如此即可快速算出数字个数。这个公式成立当且仅当x的数字长度等于n。也就是说[1,666666]内长度为5的循环节长度为1的数字等于99999 div 11111-1+1=9.不能使用666666作为被除数。

所以就可以枚举循环节长度以及数字长度，利用以上公式算出循环整数的数字个数。

但是，很容易发现，这种做法会引起重复计算。因为如果一个整数的循环节长度是i，那只要k*i是数字长度的约数，k*i也是该整数的循环节长度，所以每次计算循环节长度为i的循环整数个数的时候也要把循环节长度为i的约数的所有合法循环整数减去。

也就是说，9999在循环节长度是1的时候已经算了一遍，而在循环节长度为2的时候也会算一次，所以要减去。

时间复杂度为O(T*(lgMAX{R})^2),期望得分100%。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=2e6+5;

const int inf=0x7f7f7f7f;

int a[nmax],be[10];

bool pd(int x){

	int cnt=0;while(x) be[++cnt]=x%10,x/=10;

	if(cnt%2||cnt==2){

		rep(i,2,cnt) if(be[i]!=be[i-1]) return 0;

		return 1;

	}else{

		if(cnt==4){

			if(be[1]==be[3]&&be[2]==be[4]) return 1;

			return 0;

		}else{

			if(be[1]==be[3]&&be[1]==be[5]&&be[2]==be[4]&&be[2]==be[6]) return 1;

			if(be[1]==be[4]&&be[2]==be[5]&&be[3]==be[6]) return 1;

			return 0;

		}

	}

}

int main(){

	freopen("circulate.in","r",stdin);freopen("circulate.out","w",stdout);

	rep(i,11,nmax-1) a[i]=a[i-1]+pd(i);

	int n=read(),u,v;

	rep(i,1,n){

		u=read(),v=read();

		printf("%d\n",a[v]-a[u-1]);

	}

	fclose(stdin);fclose(stdout);

	return 0;

}

T2：求多少个长度为n的严格单调递增或严格单调递减的数列。数列的数字[1,n]。n=1e6+5；mod=2e6+3；

=>打表可以发现规律。ans=C(n-1,n-1-n+1)+C(n,n-n+1)+···+C(2*n-2，2*n-2-n+1)。ans=ans*2-n。看出这个之后线性求逆元就可以了。

正解：

我们可以想象，如果要数列不递增或不递减（不考虑只有一种数的情况）那么就可以选出若干个数再排序，所以是一个组合题，不是排列题。

然后我们可以在n-1个空里面放上i个挡板，没有放挡板的位置代表其相邻两个数相等。

如1 / 2,2,2 / 3,就是一个只放了2个挡板的序列，于是我们可以在n-1个数里面取i个位置放挡板，然后从N个数里面取出i个数放进去ANS=sigma{C(N-1,i-1)*C(N,i),1<=i<=N}，由于两个组合数确定了一个参数，另一个参数几乎都需要用到，我们可以使用递推。

C(N,0)=1; C(N,i)=C(N,i-1)*(n-i) div (i+1) 于是就可以递推出所有C(N,i),C(N-1,i)

由于有求余操作，我们可以使用逆元，实现div。

时间复杂度为O(NlogN)，期望得分100%。

好神啊。。。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

#define ll long long

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=2e6+5;

const int inf=0x7f7f7f7f;

const int mod=2e6+3;

int inv[mod+1],fac[nmax];

int main(){

	freopen("array.in","r",stdin);freopen("array.out","w",stdout);

	inv[1]=1;

	rep(i,2,mod) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

	int n=read();

	fac[1]=1;rep(i,2,n+n) fac[i]=1ll*fac[i-1]*i%mod;

	int ans=1;

	rep(i,2,n) ans=(ans+1ll*fac[n+i-2]*inv[fac[i-1]]%mod*inv[fac[n-1]]%mod)%mod;

	printf("%d\n",(ans+ans-n+mod)%mod);

	fclose(stdin);fclose(stdout);

	return 0;

}

T3：给出一个长度为n的数列。数列中的数[1,n]。求最多能够组成多少个长度为3的严格上升序列。

=>想啊想想啊想。。。想他的性质的时候突然想到数的大小是没有用的。。。关键是统计每个数字有多少个后搞。然后贪心。先尽量去那些个数多的。那么弄三个指针扫一下就好了。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

using namespace std;

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=3e6+5;

const int inf=0x7f7f7f7f;

int a[nmax];int vis[nmax];

int main(){

	freopen("cakes.in","r",stdin);freopen("cakes.out","w",stdout);

	int n=read(),u,cnt=0;

	rep(i,1,n){

		u=read();

		if(!vis[u]) vis[u]=++cnt;

		a[vis[u]]++;

	}

	sort(a+1,a+cnt+1);

	//rep(i,1,cnt) printf("%d ",a[i]);printf("\n");

	int ca=cnt-2,cb=cnt-1,cc=cnt,ans=0,tmp;

	while(ca>0&&cb>0&&cc>0&&ca<cb&&cb<cc){

		//printf("%d %d %d\n",ca,cb,cc);

		++ans;--a[ca];--a[cb];--a[cc];

		if(!a[cc]){

			tmp=cb,cb=ca,--ca,cc=tmp;

			if(!a[cc]) tmp=cb,cb=ca,--ca,cc=tmp;

			if(!a[cc]) tmp=cb,cb=ca,--ca,cc=tmp;

		}

		if(!a[cb]) {

			cb=ca,--ca;

			if(!a[cb]) cb=ca,--ca;

		}

		if(!a[ca]) --ca;

	}

	printf("%d\n",ans);

	fclose(stdin);fclose(stdout);

	return 0;

}

/*

6

1 2 3 4 3 2

6

1 1 1 2 2 3

12

1 1 2 5 8 2 2 2 3 3 3 1 3

*/

巴特西

noip模拟赛#38

最新文章

热门文章