A. Line Trip
还算比较简单的,不过本蒟蒻一开始以为是二分答案,二分写到一半突然想到油量直接取两个加油站之间的最大距离就好了。
最大距离能过,剩下必然都能过,要特判a[n]~x距离是两倍,因为x没有加油站,车还要掉头回去。
同时题目要求的范围是n到50就行了,如果开到2e7+5这种庞大的范围并且还用上了,可能就会被大佬hack掉(虽然题目用不到50,但是大佬的hack数据里面用了2e7,那你这道题就没分了)
本蒟蒻读题实在是太慢了,罗里吧嗦讲一堆直接干蒙了。还得多练英文
B. Chip and Ribbon
题目有点长,大意就是有个芯片在a[1],每次可以选择往后走一个(比如到a[2],但是a[n]不能到a[1],还要移动必须瞬移)或者瞬移到某一个位置上(可以原位瞬移)。并且芯片到过的位置都会+1。问你把一个0 0 0 0 0 0序列变成目标序列C最少要瞬移几次。
分析
假设有操作序列A,可以将0 0 0 0 0 0序列变成目标序列C。
那么显然有操作序列A(里面全部变成减法,操作顺序不变),可以将目标序列C变成0 0 0 0 0 0序列。
那么执行整个区间都减1,如果区间中某个数被减到0了,那就必然需要多瞬移一次。
如果是区间两端被减到0了,就缩小区间两端的指针。
可以发现我们执行的次数就是区间减1的次数包括计算中间为0的数量。
每次都去减C序列的最小值,然后每减一次就去更新一次C序列。
可以发现的是每次都减最小值复杂度为n,更新一次复杂度为n,n*n刚好爆了。
由于每次更新的时候都是区间修改,我们考虑差分维护C序列。
在原序列中执行次数是区间减1的次数和计算中间为0的数量。
原序列[10,1,5] 差分序列[10,-9,4,-5](-5是n+1的部分)
可以发现差分序列中一旦有负数,那么就是0出现的次数和需要执行区间减1的次数。
因为第一次执行区间减1是免费的,所以输出ans-1
AC代码
#include <bits/stdc++.h>
#define int long long
#define fr first
#define se second
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,a[N],ans;
void solve(){
cin>>n;
for(int i=1,t;i<=n;++i){
cin>>t;
a[i]+=t;
a[i+1]-=t;
}
for(int i=1;i<=n+1;++i)
if(a[i]<0)ans+=-a[i];
cout<<ans-1<<endl;
}
void init(){
for(int i=1;i<=n+1;++i)
a[i]=0;
ans=0;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr);
int t;
cin>>t;
while(t--)solve(),init();
return 0;
}
C. Add, Divide and Floor
B题可能是我的思路有问题,所以想的特别复杂,感觉B题比C题难的多的多。
C题就简单了,你每次可以选择一个数x,让序列中所有的数都执行(ai+x)/2,问执行几次序列相等。
只看一眼肯定蒙,是不是很难的数学题啊
随便举个例子就能做这道题:0 10
假设我们选x=20,那么下一个序列就会变成:0/2+20/2和10/2+20/2
可以发现我们选x=20没有使序列的差更小,反而公共的加上了20/2。
所以我们每次选x都选序列中的最小值就行了,直到最大值变成最小值。
AC代码
#include <bits/stdc++.h>
#define int long long
#define fr first
#define se second
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,minn=LONG_LONG_MAX,maxx=LONG_LONG_MIN,cnt;
void solve(){
cin>>n;
for(int i=1,t;i<=n;++i){
cin>>t;
minn=min(minn,t);
maxx=max(maxx,t);
}
while(maxx!=minn){
maxx=(maxx+minn)/2;
cnt++;
}
if(cnt==0){
cout<<0<<endl;
}else if(cnt<=n){
cout<<cnt<<endl;
while(cnt--)cout<<minn<<" ";
cout<<endl;
}else{
cout<<cnt<<endl;
}
}
void init(){
minn=LONG_LONG_MAX;
maxx=LONG_LONG_MIN;
cnt=0;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr);
int t;
cin>>t;
while(t--)solve(),init();
return 0;
}