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

题面传送门

T1：

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

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

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

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

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

$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这题一眼看感觉不是 $\text{dp}$ ，感觉后面的选择会影响前面的。（充分体现了直觉的不准。。）

$dp$ 思路：

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

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

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

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

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

$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

目前还不会，留坑。