一场爆0模拟赛的垃圾题解。

题面传送门

T1:

T1没有原题,,题意说的还是很清楚,但是考试的时候没有想到用2分。。

这题是2分答案,就是二分需要的天数,只要想到思路,代码还是很短的。

启示:一般让你求最小的答案都可以往二分这方面去想想。

都弄成中位数还是很好证明的,也很常见。

这里先介绍一个 STL\text{STL} : nth_element(b+1,b+mid,b+n+1);nth\_element(b+1,b+mid,b+n+1);

o(n)o(n)找中位数,还是挺好用的。

分析也很难说(更主要是懒),看代码理解一下就好了

#include <bits/stdc++.h>
using namespace std;
ll n,q[500005],b[500005];
inline bool check(ll x){
    ll y=x/n,ans=0,mid=(n+1)>>1ll;
    For(i,1,n) b[i]=q[i]+y;
    For(i,1,x%n) b[i]++;
    nth_element(b+1,b+mid,b+n+1);
    For(i,1,n) ans+=abs(b[mid]-b[i]);
    return ans<=x;
}
int main(){
    freopen("raft.in","r",stdin);
	freopen("raft.out","w",stdout);
    ll ans;
    read(n);
    For(i,1,n) read(q[i]);
    ll l=1,r=1e15;
    while(l<=r){
        ll mid=(l+r)>>1ll;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    write(ans);
}

T2:

T2这题一眼看感觉不是 dp\text{dp} ,感觉后面的选择会影响前面的。(充分体现了直觉的不准。。)

dpdp 思路:

dp[i][j]dp[i][j] 表示先手拿 iji-j 的区间的最大差值。

每一个区间都可以看成一方先手拿走左边 xx 个或右边 xx 个( xx 是任意数),再 dp\text {dp} 剩下的那个区间就好了。

这题应该介于记忆化和 dp\text {dp} 之间的吧。

聪明的读者应该会有一个问题,就是在 dp\text{dp} 的过程中会有先后手的区别。

你可以看成一段区间内的区间的dp值是 当对面为先手的时候的差值,(感性理解一下)

ab=(ba)a-b=-(b-a) ,所以减去就好了。

代码:

int n;
int q[1005],sum[1005],d[1005][1005];
int dfs(int l,int r){
	if(l>r) return 0;
	if(l==r) return d[l][r]=q[l];
	if(d[l][r]!=-INF) return d[l][r];
	For(i,1,r-l+1){
		d[l][r]=max(d[l][r],sum[l+i-1]-sum[l-1]-dfs(l+i,r));
	}
	For(i,1,r-l+1){
		d[l][r]=max(d[l][r],sum[r]-sum[r-i]-dfs(l,r-i));
	}
	return d[l][r];
}
int main(){
	freopen("farcry.in","r",stdin);
	freopen("farcry.out","w",stdout);
	while(1){
		For(i,0,100) q[i]=0,sum[i]=0;
		For(i,0,100)
		For(j,0,100) d[i][j]=-INF;
		read(n);
		if(!n) return 0;
		For(i,1,n) read(q[i]),sum[i]=sum[i-1]+q[i];
		write(dfs(1,n));
		puts("");
	}
}

T3:

​ 垃圾结论题。

​ 这题只要知道歌德巴赫猜想就好了。(不会证没关系,反正在1e18的范围内已经证明了,可以当结论用的。)

  1. 每个大于2的偶数都是两个素数之和。
  2. 每个大于5的奇数都是三个素数之和。

所以答案肯定是1 2 3中间一个。

就直接上代码了。。

inline bool check(ll a){
	if(a%2==0) return false;
	for(int i=3;i<=sqrt(a)+1;i+=2)
		if(a%i==0) return false;
	return true;
}
signed main(){
	freopen("taxes.in","r",stdin);
	freopen("taxes.out","w",stdout);
	int T;
	ll q,ans=0;
	T=read();
	while(T--){
		q=read();
		if(q==2||check(q))cout<<1<<endl;
		else if(q%2==0||(check(q-2))) cout<<2<<endl;
		else cout<<3<<endl;
	}
	
	return 0;
}

T4:

原题:CF786B

目前还不会,留坑。