题解 P2827 【蚯蚓】
做法: 差分+单调性优化
2016年T2题目都比T3难吗……这么恐怖……
P20: 直接就加值sort就可以了。
P70: 直接差分,然后放入优先队列进行维护即可(每个数取出来+(i-1)*q,存入时再-i*q,这样就能使得在这一回合不加上q)
然后我们看如何直接写。
其实,我们是可以把它整出单调性的有单调性的
我们用三个队列来表示还没切的蚯蚓,切了的第一段的蚯蚓,切了的第二段蚯蚓,而后面两个序列如果把切成两半的蚯蚓直接放入队尾是有单调性的
我们记录当前切掉的蚯蚓长度为A,下一次切掉的为B
还没切的三个序列为
1: A B C ……
2: 空
3: 空切了第一条
1: B + q C + q ……
2: A × p
3: A × (1 - p)切了第二条
1: C + q ……
2: A × p + q (B + q) × p
3: A × (1 - p) (B + q) × (1-p)我们再比较队列2中的两条
(B + q) × p = B × p + q × p
∵ B < A
∴ B × p < A × p
又∵ 0 < p < 1
∴ p × q < q
综上所述， (B + q) × p < A × p + q看完了应该这就不难证明了吧
我们之前切掉的在第二个切成两半的同时,也会+p,这也就导致了2,3两个序列都是有单调性的。
然后就直接维护队列就好了
Code:
#include<bits/stdc++.h>
#define re register
#define rep(i,a,b) for(re int i=a,i##end=b; i<=i##end; i++)
#define drep(i,a,b) for(re int i=a,i##end=b; i>=i##end; i--)
#define repp(i,a,b) for(re int i=a,i##end=b; i<i##end; i++)
#define drepp(i,a,b) for(re int i=a,i##end=b; i>i##end; i--)
#define Erep(i,x) for(int i=head[x]; i; i=Edge[i].nxt)
#define lowbit(x) (x&-x)
#define debug(x) cout<<#x<<" = "<<x<<endl;
#define coint const int
typedef long long ll;
using namespace std;
template<class T>inline T rd(){
static char ch;static bool neg;static T x;
for(neg=0,ch=0; ch>'9'||ch<'0'; neg|=(ch=='-'),ch=getchar());
for(x=0; ch>='0'&&ch<='9'; x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar());
return neg?-x:x;
}
template<class T>inline T Max(const T &x, const T &y){
return x>y?x:y;
}
template<class T>inline T Min(const T &x, const T &y){
return x<y?x:y;
}
coint N=1e5+5,M=7e6+5;
//bool S1;
struct Heap{
int sum[N+M];
int sz;
Heap(){ sz=0; return; }
inline void push(ll x){
sum[++sz]=x;
int now=sz,nxt;
while(nxt=now>>1,nxt){
nxt=now>>1;
if(sum[now]>sum[nxt]) swap(sum[now],sum[nxt]),now=nxt;
else break;
}
return;
}
inline void pop(){
sum[1]=sum[sz--];
int now=1,nxt;
while(nxt=now<<1,nxt<=sz){
if(nxt<sz && sum[nxt|1]>sum[nxt]) nxt|=1;
if(sum[now]<sum[nxt]) swap(sum[now],sum[nxt]),now=nxt;
else break;
}
return;
}
inline ll top() { return sum[1]; }
inline int size() { return sz; }
inline bool empty() { return !sz; }
}Q;
int n,m,t,u,v,q;
struct P70{
Heap Q;
// priority_queue<ll>Q;
inline void solve(){
double p=1.0*u/v;
rep(i,1,n) Q.push(rd<int>());
int tot=0;
rep(i,1,m){
int now=Q.top()+(i-1)*q; Q.pop();
tot++;
if(tot==t) printf("%d ",now),tot=0;
int nxt1=floor(now*p),nxt2=now-nxt1;
Q.push(nxt1-i*q); Q.push(nxt2-i*q);
}
if(m<=t) puts(" ");
else puts("");
tot=0;
if(Q.size()<t) puts(" ");
else{
while(!Q.empty()){
tot++;
if(tot==t){
printf("%d ",Q.top()+m*q);
tot=0;
}
Q.pop();
}
puts("");
}
return;
}
}p70;
struct P10{
static const int N=1000+5,M=1000+5;
ll A[N+M];
inline void solve(){
rep(i,1,n) A[i]=rd<ll>();
sort(A+1,A+n+1,greater<ll>());
int tot=0;
rep(i,1,m){
ll now=A[1]; A[1]=0;
tot++;
if(tot==t) printf("%lld ",now),tot=0;
A[n+1]=now*u/v;
A[n+2]=now-A[n+1];
rep(j,2,n) A[j]+=q;
n+=2;
sort(A+1,A+n+1,greater<ll>());
n--;
}
if(m<t) puts(" ");
else puts("");
tot=0;
if(!n) puts(" ");
else {
rep(i,1,n){
tot++;
if(tot==t){
printf("%lld ",A[i]);
tot=0;
}
}
puts("");
}
return;
}
}p10;
inline bool cmp(const int &x, const int &y){
return x>y;
}
struct P100{
int A[N],B[M],C[M];
int l1,r1,l2,r2,l3,r3;
inline void solve(){
const double p=1.0*u/v;
rep(i,1,n) A[i]=rd<int>();
sort(A+1,A+n+1,cmp);
l1=1,r1=n,l2=1,r2=0,l3=1,r3=0;
int tot=0;
rep(i,1,m){
int a=(l1<=r1)?A[l1]:-2e9,b=(l2<=r2)?B[l2]:-2e9,c=(l3<=r3)?C[l3]:-2e9;
// printf("now %d , a = %d , b = %d , c = %d \n",i,a,b,c);
int res=Max(a,Max(b,c));
(res==a?l1++,1:(res==b?l2++,2:l3++,3));
res+=(i-1)*q; tot++;
(tot==t && (printf("%d ",res), tot=0));
int nxt1=floor(res*p),nxt2=res-nxt1;
nxt1-=i*q,nxt2-=i*q;
B[++r2]=nxt1,C[++r3]=nxt2;
}
puts(""); tot=0;
rep(i,1,n+m){
int a=(l1<=r1)?A[l1]:-2e9,b=(l2<=r2)?B[l2]:-2e9,c=(l3<=r3)?C[l3]:-2e9;
// printf("now %d , a = %d , b = %d , c = %d \n",i,a,b,c);
int res=Max(a,Max(b,c));
(res==a?(l1++):(res==b?(l2++):(l3++)));
tot++;
(tot==t && (printf("%d ",res+m*q), tot=0));
}
puts("");
return;
}
}p100;
//bool S2;
int main(){
// cout<<(&S2-&S1)/1024.0/1024<<endl;
// freopen("earthworm.in","r",stdin);
// freopen("earthworm.out","w",stdout);
n=rd<int>(),m=rd<int>(),q=rd<int>(),u=rd<int>(),v=rd<int>(),t=rd<int>();
// debug(n); debug(m);
p100.solve();
return 0;
}