17.10.03

上午
- 模拟考试
  - Prob.1（AC）转化为求最多的不重叠的线段（带权）。也真是巧了，前天大米兔才分享过这个题，只是背景故事不同……
  - Prob.2（WA）神题，好像是概率DP，没人做出来，网上还没题解，只有一个光秃秃的STD，看不懂。
  - Prob.3（WA）一个找规律的题，我都做出来了。
    但绝望的错完了，本来以为可以AC呢。
    
    然后发现数据后发现，没注意样例输出的我多输出了1mol的空格……
    
    删除代码里的空格输出后，就AC了……
    
    （怎么能如此粗心！）

下午

入门OJ

入门OJ 2054: [Noip模拟题]数列计数

求组合数取模

复习了一下取模质数是阶乘逆元的O（n）递推求法，

可用于O（1）求组合数

代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int mod=2000003;
int fac[2000005],inv[2000005]; 
int power(int a,int b)
{
	int val=1;
	while(b)
	{
		if(b&1) val=(1ll*val*a)%mod;
		a=(1ll*a*a)%mod; b>>=1; 
	}
	return val;
}
void pre_fac_inv(int n)
{
	fac[0]=fac[1]=1;
	for(int i=2;i<=n;i++) fac[i]=(1ll*fac[i-1]*i)%mod;
	inv[n]=power(fac[n],mod-2);
	for(int i=n;i>1;i--) inv[i-1]=(1ll*inv[i]*i)%mod;
	inv[0]=inv[1];
}
int c(int m,int n)
{
	return 1ll*fac[m]*inv[m-n]%mod*inv[n]%mod;
}
int main(){
	int n;
	scanf("%d",&n);
	pre_fac_inv(2*n);
	int ans=(c(2*n-1,n-1)-n+mod)%mod;
	printf("%d",(ans*2+n)%mod);
	return 0;
}

入门OJ 2055: [Noip模拟题]堆蛋糕

统计两个数组：

v[k]表示同类小于等于k的蛋糕的总数量

w[k]表示同类大于等于k的蛋糕有多少种

那么对于一个k是否可成为答案（即可否分成k组），只需满足：

v[k]+w[k]*3>=3*k

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> 
using namespace std;
int w[3000005],v[3000005];
int cnt[3000005],n,r;
int main(){
	scanf("%d",&n);
	for(int i=1,a;i<=n;i++) scanf("%d",&a),cnt[a]++,r=max(r,a);
	for(int i=1;i<=r;i++) w[cnt[i]]++,v[cnt[i]]+=cnt[i];
	for(int i=1;i<=n;i++) v[i]+=v[i-1];
	for(int i=n;i>=1;i--) w[i]+=w[i+1];
	for(int k=n/3;k>=1;k--){
		if(v[k-1]+w[k]*k>=3*k){
			printf("%d",k);
			break;
		}
	}
	return 0;
}

入门OJ 2059: [Noip模拟题]电费结算

随着用电量的增加，电费单调递增

既然有了单调性，那么二分就好了

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
ll allfi,allused,derfi,oneused;
ll cal(ll used){
	ll fi=0;
	if(used<=100) fi+=2*(used-0);
	else{
		fi+=2*(100-0);
		if(used<=10000) fi+=3*(used-100);
		else{
			fi+=3*(10000-100);
			if(used<=1000000) fi+=5*(used-10000);
			else{
				fi+=5*(1000000-10000);
				fi+=7*(used-1000000);
			}
		}
	}
	return fi;
}
ll binary_search(){
	ll l=1,r=1000000000,mid,ans;
	while(l<=r){
		mid=(l+r)>>1;
		if(cal(mid)<=allfi) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
ll binary_sssssssssearch(){
	ll l=1,r=allused/2,mid,ans;
	while(l<=r){
		mid=(l+r)>>1;
		if(cal(mid)+derfi<=cal(allused-mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
int main(){
	scanf("%lld%lld",&allfi,&derfi);
	allused=binary_search();
	oneused=binary_sssssssssearch();
	printf("%lld",cal(oneused));
	return 0;
}

晚上

入门OJ 2060: [Noip模拟题]序列和

套路做法，但很巧妙：

dmax[i][j][0/1]分别表示选到第i个数，以及选了j段，且该数不选(0)/选(1)的最大值

dmin[i][j][0/1]状态定义与上面类似，但维护的最小值

dmax用来维护实际要选的段的最大值（记为ansmax），dmin用来维护实际不选的段的最小值（即空隙的最小值）（记为ansmin）

最后答案为max（ansmax，tot-ansmin），

这样就巧妙处理了环的问题，无论实际要选的那些段会不会存在首尾相接的情况，对于线性区间来说，要么是实际要选的那些段不超过k段，要么是实际不选的那些段（即空隙）不超过k段。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int a[100005];
int dmin[100005][15][2],dmax[100005][15][2]; 
int n,k,tot,ansmin=0x3f3f3f3f,ansmax=0;
int main(){
	scanf("%d%d",&n,&k);
	memset(dmin,0x3f,sizeof(dmin));
	for(int i=1;i<=n;i++) dmin[i][0][0]=0;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),tot+=a[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++){
			dmin[i][j][0]=min(dmin[i-1][j][0],dmin[i-1][j][1]);
			dmin[i][j][1]=min(dmin[i-1][j][1],dmin[i-1][j-1][0])+a[i];
			ansmin=min(ansmin,min(dmin[i][j][1],dmin[i][j][0]));
			
			dmax[i][j][0]=max(dmax[i-1][j][0],dmax[i-1][j][1]);
			dmax[i][j][1]=max(dmax[i-1][j][1],dmax[i-1][j-1][0])+a[i];
			ansmax=max(ansmax,max(dmax[i][j][1],dmax[i][j][0]));
		}
	printf("%d",max(ansmax,tot-ansmin));
	return 0;
}

入门OJ 2061: [Noip模拟题]最多的约数

深搜，

由唯一分解定理，n=p1^k1*p2^k2*……pn*^pn,依次枚举每个质数的指数

由(k1+1)*(k2+1)*……*(kn+1)得约数个数。

一开始还没想到……

用到两个优化，

1）小素因子多一定比大素因子多要优，所以大的质数的指数不会大于小的质数的指数。

2）由于深搜到的质数的指数至少为1，所以手打的质数表一直到43就够了。

代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
ll n,c,maxy,ans;
int pri[17]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43};
void dfs(ll now,int p,int cnt,int last){
    if(cnt>maxy){
        maxy=cnt;
        ans=now;
    }
    if(cnt==maxy&&now<ans)ans=now;
    for(int i=1;i<=last;i++){
        now*=pri[p];
        if(now>n)break;
        dfs(now,p+1,cnt*(i+1),i);
    }
}
int main(){
    scanf("%lld",&n);
    dfs(1,1,1,63);
    printf("%lld",ans);
    return 0;
}

End
- 感觉考试越来越不仔细，得注意了。
- 耍题效率慢，不太满意，明天要加油呢。