A.年审的开端

纯签到，注意开long long即可

B.任务A

验题目的时候验题人均错一发的简单题

题意：给定一个数组 a，对于每个 ai，可以将它减一或什么都不做。

问能否是这个数组非递减。

思路：所以，每遇到一个数时，总有两种情况：

当a[i]-a[i-1]<=-1时候，意味着这个序列不是不下降序列，输出，结束。

当a[i]-a[i-1]>=0时候，继续

空间可以优化为1

代码如下：

#include<bits/stdc++.h>
using namespace std;

void solve()
{
    int a, mx,maxx=0;
	bool f = false;
	int n;cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> a;
		maxx = max(maxx, a);
		if(maxx - a >= 2)f = 1;
  		//已经无药可救时，标记
	}
	if(f) puts("No");
	else puts("Yes");
}

signed main()
{
	int t;
	cin>>t;
	while(t--)
	solve();
}

C.任务B

这题本质上考察是模拟算法，注意开 long long，因为0已经是最小 值了所以碰到直接跳出就好，时间复杂度肯定能过，代码如下

#include<bits/stdc++.h>
using namespace std;

void solve()
{
	long long L,R,ans=2024;
    scanf("%lld%lld",&L,&R);
	for(long long i=L;i<=R;i++){
		for(long long j=i+1;j<=R;j++){
			ans=min(ans,(i*j)%2024);
			if(ans==0){					
				printf("0\n");
				return ;
			}
		}
	}
	printf("%lld\n",ans);
}

signed main()
{
	int t;
	cin>>t;
	while(t--)
	solve();
}

D.任务C

这是一道贪心题，但具体怎么贪呢？

首先，根据题意得知，我们需要一个 a 数组和一个 b 数组，可以合成一个结构体。然后，我们需要尽可能的把 bi小的放在前面，这样就可以把结束时间小的先结束，也就是把结构体从大到小来排序，可以实现。可是，如果完成任务的时间加起来超过了 bi秒，则超时，所以我们需要再设一个变量 sum来记录所有完成任务时间长度的总和。

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int a,b;
}s[200010];
bool cmp(node x,node y){return x.b<y.b;}
void solve()
{
    int n,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i].a>>s[i].b;
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        sum+=s[i].a;
        if(s[i].b<sum)
        {
            cout<<"No"<<endl;
            return ;
        }
    }
    cout<<"Yes"<<endl;
    return ;
}
signed main()
{
	int t;
	cin>>t;
	while(t--)solve();
}

E.任务D

首先学个定理

将小数调大的收益必定比将大数调大的收益。

证明：

设未知数 a，b且 a＞b ，同时修改后的数为 x

则修改 a的收益为 x-a ,修改 b 的收益为 x-b

比较x-a和x-b

∵a＞b

∴x-a＜x-b

所以做法如下用堆动态排序序列 A ,然后不断的取最小值，判断是否大于当前修改的值，如果大于则修改，否则就退出循环（因为后面的数都比这一个数要大，再去修改没意义）。

时间复杂度： ∑O(∑bi)

显然过不了，考虑优化。

我们可以先奖修改操作按 ci 从大到小排一边序，这样就可以保证每一个数字都只会被修改一次（除第一次外，如果有比 ai 更大的 ci ，一定在前面修改过了）。

时间复杂度： O(nlogn)

代码如下:

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int count,number;
}b[200010];
bool cmp(node x,node y)
{
	return x.number>y.number; 
}
priority_queue<int,vector<int>,greater<int> > q;
void solve()
{
    int n,m,x;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		q.push(x);
	}
	for(int i=1;i<=m;i++)
		scanf("%d%d",&b[i].count,&b[i].number);
	sort(b+1,b+1+m,cmp);	
	for(int i=1;i<=m;i++)
	{
		while(b[i].count)
		{
			int x=q.top();
			if(x>=b[i].number)
				break;
			q.pop();
			q.push(b[i].number);
			b[i].count--;
		}
	}
	long long ans=0;
	while(q.size())
	{
		ans+=q.top();
		q.pop();
	}
	cout<<ans<<endl;

}
signed main()
{
	int t;
	cin>>t;
	while(t--)solve();
}

F.任务E

一道练手的简单动规题

动规：

一级动规：通俗易懂

数组： f[i][o] 表示前i 个硬币有 o 个正面朝上的概率。

转移方程：枚举是不是正面即可

f[i][o]=f[i−1][o−1]×a[i]+f[i−1][o]×(1−a[i])

注意事项 f[0][0]=1 ，f[i][0]=f[i−1][0]×(1−a[i])

---

二级动规：压维

压维原因： 凡是看见等号左边是[i] 的，右边全是[i−1] 的，就可以压维。

数组： f[o] 表示循环到现在这个时刻有 o 个正面朝上的硬币的概率。

转移方程：

f[o]=f[o−1]×a[i]+f[o]×(1−a[i])

注意事项要逆推f[0]=f[0]×(1−a[i]) 要放在第二重循环后。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n;
double a[3333],f[3333],ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	f[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int o=i;o>=1;o--)
			f[o]=f[o]*(1-a[i])+f[o-1]*a[i];
		f[0]=f[0]*(1-a[i]);
	}
	for(int i=n/2+1;i<=n;i++)
		ans+=f[i];
	printf("%.10f\n",ans);
	return 0;
}

G.任务F

这道题目是一道经典搜索带点博弈论的题，并不难。

我们把这个 n 个格子n−1 个道路抽象成树，然后我们发现先将对方无法到达的点染色没有意义（不会增加自己所能染色的范围），我们应该贪心地将对方所能走的点缩小，向对面的地方走（至少能对染色范围产生 1 点贡献），由于是一棵树，所以向对面走其实就是走 1 号点和 n 号点那条确定的路径，先走到的就得到这个点。我们通过 BFS 来染色，最后判断谁的控制区域更多即可（如果控制区域相同，那么根据树的奇偶性来判断先手还是后手先不能下）。

（讨厌多测）

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

int ans[2],m[200010];

void solve() 
{
	int n;
	cin >> n;
	vector<int> vec[n+1];
    queue<pair<int,int> > que;
    for(int i=0;i<=n;i++)m[i]=0;
	int u,v;
	ans[0]=0;
	ans[1]=1;
	for(int i=1;i!=n;++i) {
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	
	que.push(make_pair(0,1));
	que.push(make_pair(1,n));
	
	//BFS 染色 
	while(!que.empty()) {
		auto u=que.front().second,op=que.front().first;
		que.pop();
		if(m[u]) continue;
		
		m[u]=1;
		ans[op]++;
		
		for(auto v:vec[u]) {
			que.push(make_pair(op,v));
		}
	}
	
	if(ans[0]>ans[1]) cout << "Yes"<<endl;
	else if(ans[0]<ans[1]) cout << "No"<<endl;
	else if(n%2) cout << "Yes"<<endl;
	else cout << "No"<<endl;
	
}

signed main()
{
	int t;
	cin>>t;
	while(t--)solve();
}

H.任务G

出题人只能想到分治fft，不知道有没有别的优化方法

这相当于 n 个一次二项式（形如ptx+(1−pt)）相乘，求乘积，最后算答案。

这里讲一下分治 FFT。

假设我要求出区间 [l,r] 的所有多项式乘积，那么我把区间[l,mid] 和区间[mid+1,r] 的多项式乘积乘起来，即为答案。

考虑时间复杂度。因为每个坐标上只有一个一次二项式，所以这段区间的乘积多项式次数是 O(r−l) 级别的。

每次我需要一个 O((r−l)log2(r−l)) 的 FFT 运算来把两个多项式乘起来。

所以根据主定理，T(n)=2T(⌊2/n⌋)+nlogn=O(nlog2n)。 其实知道fft的原理然后去网上套个板子运用一下就可以了，参考代码意义不大。（fft真的强）

参考代码如下:

#include<bits/stdc++.h>
#define fo(i,a,b) for(auto i(a),_ei(b);i<=_ei;++i)
#define gch(w) for(;w(CH);CH=getchar())
using I=int;using V=void;using namespace std;
using DB=long double;
I n;const I N=500000;
using poly=vector<DB>;
poly a[N];
#define cs const
cs I NMax=500000;
struct fus{
	DB x,y;fus(cs DB _x=0,cs DB _y=0){x=_x;y=_y;}
	fus operator +(cs fus&a)cs&{return fus(x+a.x,y+a.y);}
	fus operator -(cs fus&a)cs&{return fus(x-a.x,y-a.y);}
	fus operator *(cs fus&a)cs&{return fus(x*a.x-y*a.y,x*a.y+y*a.x);}}
aa[NMax],bb[NMax];
I tr[NMax];
const DB PI=acos(-1);
V FFT(fus*a,I n,I op){
	fo(i,0,n-1)if(i<tr[i])swap(a[i],a[tr[i]]);//蝴蝶变换
	for(I len=2,hf=1;len<=n;len<<=1,hf<<=1){
		fus w(cos(2*PI/len),sin(2*PI/len)*op);
		for(fus*i=a;i<a+n;i+=len){
			for(fus bas(1,0),*j=i,*k=i+hf;k<i+len;++j,++k,bas=bas*w){
				fus num=*k*bas;
				*k=*j-num;
				*j=*j+num;}}}
	if(op==-1)fo(i,0,n-1)a[i].x/=n;}
poly convolution(poly a,poly b){
	poly c;c.resize(a.size()+b.size()-1);
	I n(1);for(;n<c.size();n<<=1);
	fo(i,1,n-1)tr[i]=tr[i>>1]>>1|(i&1?n>>1:0);
	fo(i,0,(I)a.size()-1)aa[i]=fus(a[i],0);
	fo(i,0,(I)b.size()-1)bb[i]=fus(b[i],0);
	FFT(aa,n,1);FFT(bb,n,1);
	fo(i,0,n)aa[i]=aa[i]*bb[i];
	FFT(aa,n,-1);
	fo(i,0,(I)c.size()-1)c[i]=aa[i].x;
	fo(i,0,n-1)aa[i]=bb[i]=fus(0,0);
	return c;
}
poly fzfft(I l,I r){
	if(l==r)return a[l];
	I mid=l+r>>1;
	return convolution(fzfft(l,mid),fzfft(mid+1,r));}
I main(){scanf("%d",&n);
	fo(i,1,n){a[i].resize(2);
		scanf("%Lf",&a[i][1]);
		a[i][0]=1-a[i][1];}
	poly ans=fzfft(1,n);DB anss(0);
	for(I i=(n+1)/2;i<ans.size();++i)anss+=ans[i];
	printf("%.11Lf\n",anss);
	return 0;
}