期望得分：100+40+100=240
实际得分：50+40+20=110
T1 start取了min没有用，w(ﾟДﾟ)w Ｏ(≧口≦)Ｏ
T3 代码3个bug ：数组开小了，一个细节没注意，手抖打错变量。。。
细节处理很重要啊！！！！
贪心，按结束时间排序
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 100001 struct node
{
int t,s;
}e[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool cmp(node p,node q)
{
return p.s>q.s;
} int main()
{
freopen("manage.in","r",stdin);
freopen("manage.out","w",stdout);
int n;
read(n);
for(int i=;i<=n;i++) read(e[i].t),read(e[i].s);
sort(e+,e+n+,cmp);
int now=2e9,start;
for(int i=;i<=n;i++)
{
start=min(now,e[i].s);
now=start-e[i].t;
}
if(now>=) printf("%d",now);
else printf("-1");
}
设f[i] 表示 前i种珠子的排列方案
sum[i] 表示前i种珠子的前缀和
cnt[i] 表示第i种珠子的个数
因为第i种珠子的最后一个一定要在第i+1种珠子的最后一个之前
所以 到第i种珠子，第i种的最后一个一定在sum[i]位置上
所以还剩sum[i]-1个位置，还剩cnt[i]-1个珠子
所以 f[i]=f[i-1]*C(sum[i]-1,cnt[i]-1)
可以理解为 在sum[i]-1 个位置上选了cnt[i]-1个位置之后，剩下的位置就是把原来f[i-1]的每一种方案再塞进去
#include<cstdio>
#include<iostream> using namespace std; #define N 100001 #define mod 998244353 int cnt[N],sum[N]; int fac[N*],inv[N*]; int f[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int Pow(int a,int b)
{
int r=;
for(;b;a=1ll*a*a%mod,b>>=)
if(b&) r=1ll*a*r%mod;
return r;
} int getC(int a,int b)
{
return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;
} int main()
{
freopen("qiang.in","r",stdin);
freopen("qiang.out","w",stdout);
int n;
read(n);
for(int i=;i<=n;i++) read(cnt[i]),sum[i]=sum[i-]+cnt[i];
fac[]=inv[]=;
int tot=sum[n];
for(int i=;i<=tot;i++) fac[i]=1ll*fac[i-]*i%mod,inv[i]=Pow(fac[i],mod-);
f[]=;
for(int i=;i<=n;i++) f[i]=1ll*f[i-]%mod*getC(sum[i]-,cnt[i]-)%mod;
printf("%d",f[n]);
}
考场上我是真的不会，~~~~(>_<)~~~~
40分大爆搜
#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; #define N 100001 int n,tot; bool flag1; int sum[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void init()
{
read(n);
for(int i=;i<=n;i++) read(sum[i]),tot+=sum[i];
if(tot<=) flag1=true;
} namespace solve1
{
int mx[];
int ans=; void dfs(int x,int tmp[])
{
if(x==tot+) { ans++; return; }
for(int i=;i<=n;i++)
if(tmp[i])
{
if(tmp[i]==)
{
for(int j=;j<i;j++)
if(!tmp[j] && mx[j]>x && mx[j]!=-) return;
for(int j=i+;j<=n;j++)
if(!tmp[j] && mx[j]<x && mx[j]!=-) return;
}
tmp[i]--;
int last=mx[i]; mx[i]=x;
dfs(x+,tmp);
tmp[i]++;
mx[i]=last;
}
} void work()
{
int rest[];
for(int i=;i<=n;i++) rest[i]=sum[i];
memset(mx,-,sizeof(mx));
dfs(,rest);
printf("%d",ans);
}
} int main()
{
freopen("qiang.in","r",stdin);
freopen("qiang.out","w",stdout);
init();
if(flag1) solve1 :: work();
else printf("%d\n",);
}
20%的数据：Q*N暴力枚举
另外30%的数据：
因为每个函数最多覆盖10个元素，而且保证每个位置只修改一次
所以最多进行10^6 次 单个的修改
用vector记录下每个元素对哪些函数有影响
用线段树维护 函数的和
修改的时候 枚举 这个元素有影响的所有函数，一个一个的在线段树里改
查询直接区间求和
100%的数据：
树状数组+分块
树状数组里记录每个元素的值
把数组分为根号n块，
cnt[i][j]记录 第i块内，第j个元素使用的次数
用 差分+前缀和 即可得到这个数组
用tot[i]记录第i块的函数和
修改的时候，直接修改tot，修改树状数组中的元素
查询的时候，一个块里的直接用tot，凑不成一个块的暴力在树状数组里查
代码3部分均有
#include<cmath>
#include<cstdio>
#include<vector>
#include<iostream> #define lowbit(x) x&-x using namespace std; #define N 100001 typedef long long LL; int n; int a[N];LL sum[N]; int L[N],R[N]; bool flag2=true; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void init()
{
read(n);
for(int i=;i<=n;i++) read(a[i]),sum[i]=sum[i-]+a[i];
for(int i=;i<=n;i++)
{
read(L[i]); read(R[i]);
if(R[i]-L[i]>) flag2=false;
}
} namespace solve2
{
vector<int>v[N];
LL tot[N<<];
LL ans; void build(int k,int l,int r)
{
if(l==r) { tot[k]=sum[R[l]]-sum[L[l]-]; return; }
int mid=l+r>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
tot[k]=tot[k<<]+tot[k<<|];
} void change(int k,int l,int r,int pos,int w)
{
if(l==r) { tot[k]+=w; return; }
int mid=l+r>>;
if(pos<=mid) change(k<<,l,mid,pos,w);
else change(k<<|,mid+,r,pos,w);
tot[k]=tot[k<<]+tot[k<<|];
} void query(int k,int l,int r,int opl,int opr)
{
if(l>=opl && r<=opr) { ans+=tot[k];return; }
int mid=l+r>>;
if(opl<=mid) query(k<<,l,mid,opl,opr);
if(opr>mid) query(k<<|,mid+,r,opl,opr);
} void pre()
{
for(int i=;i<=n;i++)
for(int j=L[i];j<=R[i];j++) v[j].push_back(i);
build(,,n);
} void work()
{
pre();
int m,ty,l,r;
int w,s;
read(m);
while(m--)
{
read(ty); read(l); read(r);
if(ty==)
{
w=r-a[l]; a[l]=r;
s=v[l].size();
for(int i=;i<s;i++) change(,,n,v[l][i],w);
}
else
{
ans=;
query(,,n,l,r);
printf("%I64d\n",ans);
}
}
}
} namespace solve1
{
LL tot[N]; void pre()
{
for(int i=;i<=n;i++) tot[i]=sum[R[i]]-sum[L[i]-];
} void work()
{
pre();
int m,ty,l,r,w;
LL ans;
read(m);
while(m--)
{
read(ty); read(l); read(r);
if(ty==)
{
w=r-a[l]; a[l]=r;
for(int i=;i<=n;i++)
if(L[i]<=l && R[i]>=l) tot[i]+=w;
}
else
{
ans=;
for(int i=l;i<=r;i++) ans+=tot[i];
printf("%I64d\n",ans);
}
}
}
} namespace solve3
{
int siz,mx;
int id[N],cnt[][N+];
unsigned long long tot[],ans;
LL c[N]; void add(int x,int w)
{
while(x<=n)
{
c[x]+=w;
x+=lowbit(x);
}
} LL query(int x)
{
LL t=;
while(x)
{
t+=c[x];
x-=lowbit(x);
}
return t;
} void pre()
{
siz=sqrt(n);
for(int i=;i<=n;i++) id[i]=(i-)/siz+;
mx=(n-)/siz+;
int l,r;
for(int i=;i<=mx;i++)
{
l=(i-)*siz+;
r=min(i*siz,n);
for(int j=l;j<=r;j++)
{
cnt[i][L[j]]++,cnt[i][R[j]+]--;
tot[i]+=sum[R[j]]-sum[L[j]-];
}
for(int j=;j<=n;j++) cnt[i][j]+=cnt[i][j-];
}
for(int i=;i<=n;i++) add(i,a[i]);
} void out(unsigned long long x)
{
if(x/) out(x/);
putchar(x%+'');
} void work()
{
pre();
int m,ty,l,r,w;
int bl,br,tl,tr;
read(m);
while(m--)
{
read(ty); read(l); read(r);
if(ty==)
{
w=r-a[l]; a[l]=r;
add(l,w);
for(int i=;i<=mx;i++) tot[i]+=1ll*cnt[i][l]*w;
}
else
{
ans=;
bl=(l-)/siz+; br=(r-)/siz+;
tl=bl*siz; tr=(br-)*siz+;
for(int i=l;i<=min(r,tl);i++) ans+=query(R[i])-query(L[i]-);
for(int i=bl+;i<br;i++) ans+=tot[i];
if(bl!=br)
for(int i=tr;i<=r;i++) ans+=query(R[i])-query(L[i]-);
out(ans);
printf("\n");
}
}
}
} int main()
{
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
init();
if(n<=) solve1 :: work();
else if(flag2) solve2 :: work();
else solve3 :: work();
}