526互联

Codeforces Round #887 Div.2 A-E

发布时间 2023-07-24 22:06:21作者: weakpyt

Codeforces Round #887 Div.2 一定要手玩哦

前言：

一定要手玩，一定要手玩！

我今早一手玩发现C很TM简单，如果赛时我能切C说不定直接上1800.。。。

时隔多年，我的Codeforces Rating(1718) 再次超越了 @cqbzlhy(1674)！！！

赛时错误：

  1. B题出得太慢了->劣于pzj半小时。%%%pzj
  2. C没有手玩，瞪眼半天看不出来
  3. D由于特判问题RE了两发！！！！！(还好不是WA不计罚时)

这次怎么DF全是构造啊。。。。。

要想题目考思维，数学构造加几何！

A-Desorting

简单题。找到差的最小值，将其除以2再加一就是答案。注意负数直接输出0.

B-Fibonaccharsis

题意：给定 \(n,k\) 求有多少个类斐波那契数列的第 \(k\) 项为 \(n\)。

有意思，设 \(Fib[1]=0,Fib[2]=1,Fib[n]=Fib[n-1]+Fib[n-2](n>2)\)。

注意到可以枚举该类斐波那契数列的第一项，则第二项显然是唯一的且具有单调性的。二分查找即可。

斐波那契数列增长非常快，\(Fib[n]=(\frac{\sqrt 5+1}{2})^n-(\frac{\sqrt 5-1}{2})^n\)，指数级增长。故时间复杂度 \(O(n\log nk)\)，实际上有效的 \(k\) 在 \(2\times 10^5\) 范围内是不超过35的。

        if(n==0){  
            cout<<"1\n";continue;        
        }
        if(k>35){
			cout<<"0\n";continue;
		}
		int ans=0;
		for(int i=0;i<=n;i++){
			int l=i,r=n-i;
			while(l<r){
				int j=l+r>>1;
				int a=i,b=j,tag=0;
				for(int p=3;p<=k;p++){
					int z=a+b;
					if(p==k){
						if(z>=n)r=j;
						else l=j+1;
					}
					if(z>n){
						r=j;break;
					}
					a=b,b=z;
				}
			}
			int j=l;
			int a=i,b=j,tag=0;
			for(int p=3;p<=k;p++){
				int z=a+b;
				if(p==k&&z==n){
					ans++;
				}
				if(z>n){
					break;
				}
				a=b,b=z;
			}
		}
		cout<<ans<<"\n";

事实上，这不够数学。

注意到类斐波那契数列 \(f\)，\(f[1]=a,f[2]=b,f[3]=a+b,f[4]=a+2b,f[5]=2a+3b,f[6]=3a+5b……\)，它的系数是斐波那契数列，所以事实上应该是枚举首项，根据系数关系直接推断的。(或者说丢番图方程范围内整数解个数？)

C-Ntarsis'Set

题意：

给定序列 \(a_1\sim a_n\)，有集合 \(S=\lbrace 1,+\infty\rbrace\)，定义一次操作为：将 \(S\) 中排名为 \(a_1\sim a_n\) 的数一次性删去。求 \(k\) 次操作后序列的最小值。

\(1\le n,k\le 2\times 10^5\)

由于我们只求最小值，所以先只关心最小值的变化情况。
例如在 \(a={1,3,5,6,7}\) 时，最小值分别为 \(1,4,9,14,19,24\)
观察多组数据，容易发现在 \(k\) 时刻的最小值和在 \(k-1\) 时刻的最小值之差 \(d_k\) 取决于 \(k\) 时刻最小值 \(x_k\) 大于等于的 \(a_i\) 的个数。

也即 \(d_k=\sum_{i=1}^n[x_k\ge a_i]\)，这显然是单调不减的。我们可以维护 \(d\)，用一个指针更新它，并不断累加最小值即可。

时间复杂度： \(O(n+k)\)

边界：\(x_0=0,d_0=0\)——>注意这样的话我们等价于求的是 \(S\) 从0开始的答案，所以最后要+1。

#include<iostream>
using namespace std;
int a[505050],n,t,k;
int main(){
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--){
		cin>>n>>k;
		for(int i=1;i<=n;i++)cin>>a[i];
		int x=0,d=0;
		while(k--){
			while(d+1<=n&&a[d+1]<=x+d+1)++d;
			x+=d;
		}
		cout<<x+1<<"\n";
	}
}

学到的东西：
找规律问题可以关注 \(\Delta\) 的变化情况

手玩几组样例，明确关注点。

D-Imbalanced Arrays

要求构造一个长为 \(n\) 的数组b，满足以下条件：

  1. \(-n\le b[i]\le n\)
  2. \(\forall i,j\in[1,n],b[i]+b[j]\neq 0\)
  3. \(a[i]=\sum_{k=1}^n[b[k]+b[i]>0]\)

题解：注意到，若 \(b\) 的所有值的绝对值构成了一个 \(1\sim n\) 的排列，则必定满足条件 1,2

那么只需要考虑条件3。注意到 \(a[i]>a[j]\implies b[i]>b[j]\)，而顺序在此题没有要求，只要我们记下每个 \(a\) 的id即可。将 \(a\) 从小到大排序，这就确定了大小关系。

这时候我们来考虑一个数为正数的条件：\(a[i]\ge n-i+1\)，因为正数加上正数一定是正数。我们设 \(x\) 为满足 \(a[x]\ge n-x+1\) 的最小 \(x\) ，这个就是最小的正数。

那么 \(\forall i\ge x,a[i]\) 的意义是：绝对值小于它的负数的个数与其他正数的个数之和。于是 \(a[i]-(n-x+1)+j-x+1\) 就是 \(i\) 所代表的数字的绝对值的排名。由于它是正数，所以直接确定了它的值。

当我们确定完正数的值的时候，负数的值就把排列里剩下的数按大小关系分配即可(这个数可以算出来，用来判无解)。

最后判一下无解。

注意特判：当 \(a\) 全部为 \(0\) 时候，全输出 \(-1\) 即可。

struct node{
	int id,x;
	bool operator<(const node b){
		return x<b.x;
	}
}a[505050];
int b[505050],cnt[505050],tot,vis[505050]; 
int main(){
	int t=read(),n;
	while(t--){
		for(int i=1;i<=n;i++)vis[i]=0;
		n=read();tot=0;
		for(int i=1;i<=n;i++)a[i].x=read(),a[i].id=i;
		sort(a+1,a+n+1);
		int x=-1;
		for(int i=1;i<=n;i++){
			if(a[i].x>=n-i+1){
				x=i;
				for(int j=i;j<=n;j++){
					int p=a[j].x;p-=n-i+1;p+=j-i+1;vis[p]=1;
					b[a[j].id]=p;
				}
				break; 
			}
		}
		if(x==-1){
			cout<<"YES\n";for(int i=1;i<=n;i++)cout<<"-1 ";cout<<"\n";continue;
		}
		int j=1,k=0;
		for(int i=x-1;i;i--){
			while(vis[j]&&j<=n)++j,++k;
			b[a[i].id]=-j;
			if(n-x+1-k!=a[i].x){
				b[a[i].id]=-n-1; 
			}
			vis[j]=1;--k;
		}
		int tag=0;
		for(int i=1;i<=n;i++){
			if(b[i]>n||b[i]<-n){
				cout<<"NO\n";tag=1;break;
			}
		}
		if(tag)continue;
		cout<<"YES\n";
		for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<"\n";
	}
}

E-Ina of the Moutain

题意：给定数 \(a[1]\dots a[n]\)，每一次可以任选一个区间，将区间中所有数减一，当某个数等于0后，将变为\(k\)，问所有数变为 \(k\) 的最小操作次数。

首先，让我们思考一下如果没有这个模 \(k\)的限制，答案是多少。(思考简化版问题)

设 \(f[i]\) 为前 \(i\) 个数变 \(1\) 的最小操作次数，则 \(f[i]=f[i-1]+\max(0,a[i]-a[i-1])\)。当 \(a[i]>a[i-1]\) 时，先将 \(a[i]\) 调整为 \(a[i-1]\) 然后和 \(a[i-1]\) 合并操作即可。另一种情况：当 \(a[i-1]\) 被减到 \(a[i]\) 时合并操作即可。

那么我们考虑这个问题，逆向思考。

首先，假设我们已经知道了最优方案下每一个 \(a[i]\) 会被减到 \(b[i]\) 次 \(0\)，等价于加了 \(b[i]\) 次 \(k\)，则令 \(c[i]=a[i]+(b[i]-1)k\)，问题就只剩下减小操作不会考虑变为 \(k\) 了。设 \(d[i]=c[i]-c[i-1]\)，答案就为 \(\sum_{i=1}^n\max(0,d[i])\)。理论上，我们枚举每一种情况，计算该式的最小值就为答案。

让我们再来思考一些性质。直觉告诉我们必定存在最优方案使得每一个 \(d[i]<k\)。为什么？因为若 \(d[i]\ge k\)，由于 \(c\) 非负，则 \(c[i]\ge d[i]\ge k\)，将 \(c[i]\) 减去 \(k\)，答案不可能变劣。重复这个操作，直到不存在 \(d[i]\ge k\) 为止(最多影响到 \(d[n]\)，此时再减少 \(c[n]\)就可以了)，我们仍能得到一个答案不变的最优方案。

那么我们来考虑计算答案。

不直观的序列问题，可以转化到平面上，尤其是做差求值，在平面上可以直接通过坐标差体现，转化为路径。

那么每个 \(c[i]\) 最多有两种可能。

我们将 \(c[i]\) 视作点 \((i,c[i])\)，则在直线 \(x=i\) 上，最多只有两个合法的点，且距离等于 \(k\)。问题转化为求 \((0,0)\) 到 \((n+1,0)\) 的最短路。

这里的路径长度定义为：\(\sum_{i=1}^{n+1}\max(0,y_i-y_{i-1})\)

盗个图，例如 \(a={1,2,3,1,3,2,1}\) 的时候，有：

这里是这个题最魔幻的部分，也是最让人着迷的地方(w看了一个下午才懂。。。。)

那么这里显然有贪心策略：能往下走就往下走，走不下去了就往上爬。设走不下去的点为 \(i\)

但，这个往上爬是有技术含量的。可以在之前的某个位置 \(j\) 就向上爬了，代价为 \(k-y_j+y_{j-1}(y_j\le y_{j-1})\)。此时将 \(j\sim i\) 的点的 \(y\) 全部加上 \(k\) 就不会对答案有影响了。

那么我们就是要找到这个向上爬的最小代价。显然我们可以通过优先队列维护每一个向上爬的路。(对于每一个 \(a_i>a_{i-1}\)，有向上的路径，长度为 \(a_i-a_{i-1}\)，对于每一个 \(a_i<a_{i-1}\)，有向上的路径 \(a_i+k-a_{i-1}\))。当然，\(a_i<a_{i-1}\) 相当于走下坡路，是最优选择。

代码是那么地简洁与优雅，令人着迷。

#define int long long
int n,t,k;
signed main(){
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--){
		cin>>n>>k;
		int lst=0,ans=0;priority_queue<int>q;
		for(int i=1;i<=n;i++){
			int x;cin>>x;x%=k;
			if(x>lst){
				q.push(-(x-lst));
				ans-=q.top();
				q.pop(); 
			}
			else q.push(-(k-lst+x));
			lst=x;
		}
		cout<<ans<<"\n";
	}
}

F-Miriany and Matchstick

看不懂，等我今晚爆肝