A.P4343 [SHOI2015]自动刷题机
- 啊对对对，算法都对了，二分写挂了：）
Solution
-
二分答案，每次 \(\mathtt{O(n)}\) 判断当前的 \(mid\) 是否可行，最大和最小分开二分；
-
注意 :
如果不存在这样的 n 则输出 −1。
-
我的挂分中多少有没看到这一行的成分在；
AC code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
const int N=1e5+10;
#define ll long long
int L,k;
int x[N];
ll ans1=-1,ans2;
int check(ll n){
int cnt=0;
ll sum=0;
for(int i=1;i<=L;++i){
sum=max(0ll,sum+x[i]);
if(sum>=n){
++cnt;
sum=0;
}
}
return cnt;
}
void find_min(){
ll l=1,r=1e14;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)>k)
l=mid+1;
else if(check(mid)==k){
r=mid-1;
ans1=mid;
}
else if(check(mid)<k)
r=mid-1;
}
return ;
}
void find_max(){
ll l=1,r=1e18;
while(l<=r){
ll mid=(l+r+1)>>1;
if(check(mid)>k)
l=mid+1;
else if(check(mid)==k){
ans2=mid;
l=mid+1;
}
else if(check(mid)<k)
r=mid-1;
}
return ;
}
int main(){
// freopen("autoac.in","r",stdin);
// freopen("autoac.out","w",stdout);
L=read(),k=read();
for(int i=1;i<=L;++i)
x[i]=read();
ans1=-1;
find_min();
find_max();
if(ans1==-1) puts("-1");
else printf("%lld %lld",ans1,ans2);
return 0;
}
B.P2592 [ZJOI2008]生日聚会
- 暴力居然没有挂分；
C.P4340 [SHOI2016]随机序列
-
今日 T3，我愿称之为最鶸紫题； -
Ta 甚至比永无乡还水；
Solution
-
思考一下，就能发现一个很好的性质：最终答案只和与 \(a_1\) 有乘积关系的项有关，因为其他不和 \(a_1\) 有乘积关系的项必然存在一个式子，其他项都一样，而这一项系数相反。而 \(a_1\) 的系数恒正，永远无法消除。这样的式子可以一一对应，所以除了与 \(a_1\) 有直接全部都消掉了。
-
得出上一个性质，就可以考虑一下这些与 \(a_1\) 有直接乘积关系的项的系数怎么算了。将这个乘积看作一个整体，它后面的项与它一定是 \(+/-\) 连接，也就必然不会对答案产生贡献，再后面的项与这个乘积就完全没有关系了。因此只需要限定这个乘积后的第一个符号为 \(+/-\)，后面的符号就可以随便取，因此 \(a_1\) 到 \(a_i\) 的乘积的系数为:
- \(1\)，如果 \(i=n\)；
- \(2\times 3^{n-i-1}\)，\(i\not =n\)
-
然后可以发现，每个乘积和系数之间只有乘法关系，乘积之间只有加法关系，因此考虑线段树，维护一个 \(sum\) 求和，修改时只有乘法，可以用懒标记维护。
-
对原序列的修改可以转化成：对区间 \([x,n]\) 中每一个数都除以 \(a_x\)，再乘以 \(v\)，输出整个线段树的和；
-
由于题目中要求取 \(\%\)，所以除法用逆元代替；
AC code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
s=s*10+int(ch-'0');
ch=getchar();
}
return s*f;
}
const int N=1e5+10;
const int mod=1e9+7;
#define ll long long
int n,Q;
ll mul[N];
ll fm[N];
ll x[N];
struct memr{
int l,r;
ll sum,tg;
}tr[N<<4];
ll ksm(ll x,int y){
if(y<1) return 1;
ll cnt=1,d=x;
for(;y;y>>=1,(d*=d)%=mod)
if(y&1)
(cnt*=d)%=mod;
return cnt;
}
void pushup(int p){
(tr[p].sum=0ll+tr[p<<1].sum+tr[p<<1|1].sum)%=mod;
return ;
}
void pushdown(int p){
if(tr[p].tg!=1){
(tr[p<<1].sum*=1ll*tr[p].tg)%=mod;
(tr[p<<1|1].sum*=1ll*tr[p].tg)%=mod;
(tr[p<<1].tg*=1ll*tr[p].tg)%=mod;
(tr[p<<1|1].tg*=1ll*tr[p].tg)%=mod;
tr[p].tg=1;
}
return ;
}
void build(int p,int l,int r){
tr[p].l=l,tr[p].r=r;
tr[p].tg=1;
if(l==r){
tr[p].sum=(mul[l]*x[l])%mod;
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
return ;
}
void change(int p,int l,int r,ll v){
if(l<=tr[p].l && tr[p].r<=r){
(tr[p].sum*=1ll*v)%=mod;
(tr[p].tg*=1ll*v)%=mod;
return ;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid) change(p<<1,l,r,v);
if(mid<r) change(p<<1|1,l,r,v);
pushup(p);
return ;
}
int main(){
// freopen("rand.in","r",stdin);
// freopen("rand.out","w",stdout);
n=read(),Q=read();
mul[0]=1;
int a;
for(int i=1;i<=n;++i){
a=read();
(mul[i]=1ll*mul[i-1]*a)%=mod;
(fm[i]=ksm(1ll*a,mod-2))%=mod;
(x[i]=ksm(3,n-i-1)*(i!=n?2:1))%=mod;
}
build(1,1,n);
int v;
for(int i=1;i<=Q;++i){
a=read(),v=read();
change(1,a,n,fm[a]);
change(1,a,n,1ll*v);
fm[a]=ksm(1ll*v,mod-2);
printf("%lld\n",tr[1].sum);
}
return 0;
}