总分 : 100 + 30 + 30 = 160
T1
其实就是一个计算贡献的题目。(十足的水题)
我们对于每个数，计算有多少个子集中他为最小值，多少个子集中他为最大值，然后计算贡献即可。
#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(re int i=head[x]; i; i=Edge[i].nxt)
#define lowbit(x) ((x)&-(x))
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define ms(x,a) memset(x,a,sizeof x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define coint const int
#define coll const ll
#define CM cerr<<(&S2-&S1)/1024./1024.<<"MB"<<endl
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; }
bool S1;
coint N=1e6+5;
coint mod=1e9+7;
inline ll POW(ll pre, int x){
ll res=1;
for(; x; x>>=1,pre=pre*pre%mod)
if(x&1) res=res*pre%mod;
return res;
}
int A[N];
bool S2;
int main(){
// CM;
// freopen("A_sample.in","r",stdin);
// freopen("A_sample.out","w",stdout);
ll ans=0;
int n=rd<int>();
rep(i,1,n) A[i]=rd<int>();
sort(A+1,A+n+1);
rep(i,1,n){
ans+=mod-1ll*A[i]*POW(2,n-i)%mod;
ans-=(ans>=mod?mod:0);
// printf("res = %lld
",-1ll*A[i]*POW(2,n-i)%mod);
// debug(ans);
}
reverse(A+1,A+n+1);
rep(i,1,n){
ans+=1ll*A[i]*POW(2,n-i)%mod;
ans-=(ans>=mod?mod:0);
// printf("res = %lld
",1ll*A[i]*POW(2,n-i)%mod);
// debug(ans);
}
printf("%lld
",ans);
return 0;
}
T2
是一道挺好的找性质题目。
首先我们对于这道题画一张图，会发现它水量会有两种分布：一种是斜率(k=1)的，一种是水平线。
然后我们会发现它是多个这样的区间相接而成的。
画出来的图就是这样的。图可能有点丑
我们对于每次更改，肯定是前面的一段全都变成斜率(k=1)或者变成水平线的。
具体的话是(x<0)变成水平线,(x>0)变成(k=1)的直线。
考试的时候想到这里就没往下想了。但还是接下来才是关键
于是我们可以利用这些性质，把他每次倒着加入，就像一个栈一样。
#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(re int i=head[x]; i; i=Edge[i].nxt)
#define lowbit(x) ((x)&-(x))
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define ms(x,a) memset(x,a,sizeof x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first
#define se second
#define coint const int
#define coll const ll
#define CM cerr<<(&S2-&S1)/1024./1024.<<"MB"<<endl
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; }
bool S1;
coint Q=1e6+5;
int st=0;
int n,q;
struct P30{
static coint N=5e7+5;
int A[N];
inline void solve(){
ll ans=0;
rep(i,1,q){
int x=rd<int>();
ans=0;
rep(j,1,n){
A[j]=(x>0 ? Min(A[j]+x,(int)j) : Max(A[j]+x,0));
ans+=A[j];
}
printf("%lld
",ans);
}
return;
}
}p30;
struct P100{
struct element{
int l,r;
bool operator < (const element &_) const { return l<_.l; }
};
ll ans;
element stk[Q];
int sz,lazy;
inline ll calc(coint &l, coint &r){
int L=n-r+1,R=n-l+1;
return 1ll*(L+R)*(R-L+1)>>1;
}
inline void Insert(int x){
x=Min(x,n-lazy);
lazy+=x;
if(lazy==n){
ans=(1ll*n*(n+1)>>1);
stk[sz=1]=(element)<%1,n%>;
return;
}
// debug(lazy);
int l=1,r=1;
while(sz){
if(stk[sz].l-r>=x) break;
x-=stk[sz].l-r;
r=stk[sz].r+1;
ans-=calc(stk[sz].l,stk[sz].r);
sz--;
}
if(x) r+=x;
r--;
if(r) stk[++sz]=(element)<%l,r%>;
ans+=calc(l,r);
return;
}
inline void Delete(int x){
x=Min(x,lazy);
lazy-=x;
if(!lazy){
sz=0;
ans=0;
return;
}
// debug(lazy);
while(sz){
if(stk[sz].r-stk[sz].l+1>=x){
int l=stk[sz].l+x,r=stk[sz].r;
ans-=calc(stk[sz].l,stk[sz].r);
stk[sz]=(element)<%l,r%>;
ans+=calc(stk[sz].l,stk[sz].r);
break;
}
x-=(stk[sz].r-stk[sz].l+1);
ans-=calc(stk[sz].l,stk[sz].r);
sz--;
}
return;
}
inline void solve(){
ans=0; sz=0; lazy=0;
rep(i,1,q){
int x=rd<int>();
printf("%lld
",((x>0) ? (Insert(x),ans) : (Delete(-x),ans)));
}
return;
}
}p100;
bool S2;
int main(){
// CM;
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
n=rd<int>(),q=rd<int>();
// if(n*q<=1e8) return p30.solve(),0;
// p30.solve();
p100.solve();
return 0;
}
T3:
还没补，也不想补。
P20
链的话直接输出2
P40
相当于找出多少个序列，满足每m个节点是联通的。我敲了并查集，炸了10分。