1.循环依赖
大氵题，注意读入
2.A
考场口胡了一个线段树，发现更改比较难
20pts:暴力随便搞
正解是维护凹凸包
[y=a imes x^2 + b imes x
]
[frac{y}{x}=a imes x +b
]
发现后面是个直线表达式
(y)的最大值只与(x)的正负和直线表达式的极值有关
直接维护所有直线的凹凸包
注意判断(x=0)，(a=0)的情况，排序时也要排(b)
最后单调指针扫过
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define Max(a,b) (a>b?a:b)
#define ll long long
using namespace std;
const int maxn=1e6+5;
const ll INF=0x3f3f3f3f3f3f3f3f;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,m,q[maxn],head=1,tail;
ll ans[maxn];
struct Node{
int a,b;
}f[maxn];
struct Nodee{
int x,id;
bool operator < (const Nodee &A)const{
return x<A.x;
}
}c[maxn];
bool cmp1(Node A,Node B){return A.a==B.a?A.b<B.b:A.a<B.a;}
bool cmp2(Node A,Node B){return A.a==B.a?A.b<B.b:A.a>B.a;}
inline double queryx(register int i,register int j){
if(f[i].a-f[j].a==0)return 1.0*INF;
return 1.0*(f[j].b-f[i].b)/(f[i].a-f[j].a);
}
signed main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
n=read(),m=read();
for(register int i=1;i<=n;++i){
f[i].a=read(),f[i].b=read();
}
stable_sort(f+1,f+1+n,cmp2);
q[head=1]=1;
for(int i=1;i<=n;i++){
while(head<tail&&(queryx(q[tail],i)<queryx(q[tail-1],i)||f[q[tail]].a==f[i].a&&f[q[tail]].b>=f[i].b))tail--;
q[++tail]=i;
}
for(register int i=1;i<=m;++i)c[i].x=read(),c[i].id=i;
sort(c+1,c+1+m);
int now=1,j=m;
for(register int i=1;i<=m;++i){
if(c[i].x>0){j=i;break;}
else if(c[i].x==0)ans[c[i].id]=0;
else{
while(now<tail&&1LL*f[q[now]].a*c[i].x+f[q[now]].b>=1LL*f[q[now+1]].a*c[i].x+f[q[now+1]].b)now++;
ans[c[i].id]=1LL*f[q[now]].a*c[i].x*c[i].x+1LL*f[q[now]].b*c[i].x;
}
}
stable_sort(f+1,f+1+n,cmp1);
head=1;now=1;tail=0;
for(register int i=1;i<=n;++i){
while(head<tail&&(queryx(q[tail],i)<queryx(q[tail-1],i)||f[q[tail]].a==f[i].a&&f[q[tail]].b<=f[i].b))tail--;
q[++tail]=i; }
for(register int i=j;i<=m;++i){
while(now<tail&&1LL*f[q[now]].a*c[i].x+f[q[now]].b<=1LL*f[q[now+1]].a*c[i].x+f[q[now+1]].b)now++;
ans[c[i].id]=1LL*f[q[now]].a*c[i].x*c[i].x+1LL*f[q[now]].b*c[i].x;
}
for(int i=1;i<=m;i++)printf("%lld
",ans[i]);
return 0;
}
3.B
(10pts) (n<=5 a_i<=5):记搜
人眼明都知道：(O(2^{SUM}))的暴搜10分都拿不到
直接转记搜，注意期望中的初始状态和最终状态
ll DFS(int now,ll sum){
int cnt=0,tmp=0;
if(a[1]==0)return f2[a[1]][a[2]][a[3]][a[4]][a[5]]=0;
if(f2[a[1]][a[2]][a[3]][a[4]][a[5]])return f2[a[1]][a[2]][a[3]][a[4]][a[5]];
ll temp=0;
for(int i=1;i<=n;i++)cnt+=(a[i]!=0);
for(int i=1;i<=n;i++){
if(a[i])a[i]--,temp+=(DFS(now+1,sum*cnt%mol)+1),temp%=mol,a[i]++;
}
//cout<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<temp<<endl;
return f2[a[1]][a[2]][a[3]][a[4]][a[5]]=temp*qpow(cnt,mol-2)%mol;
}
(10pts) (a_i<=1):找规律
打表随便找找
全是(1)的答案为：(frac{cnt+1}{2})
证明：
推推组合数，发现每一步结束的概率为(frac{1}{cnt})，期望为步数，总期望为：(frac{1}{cnt}+frac{2}{cnt}+...+frac{cnt}{cnt})
等差数列球和
(20pts)：(n=2 a_i<=1000):DP
直接DP转移即可，注意处理(j=0)的情况
f[a[1]][a[2]]=g[a[1]][a[2]]=1;
const int mod=qpow(2,mol-2);
for(int i=a[1];i>=1;i--){
for(int j=a[2];j>=0;j--){
if(j)f[i-1][j]+=f[i][j]*mod%mol,f[i-1][j]%=mol,g[i-1][j]+=g[i][j]/2,f[i][j-1]+=f[i][j]*mod%mol,f[i][j-1]%=mol,g[i][j-1]+=g[i][j]/2;
else f[i-1][j]+=f[i][j],f[i-1][j]%=mol,g[i-1][j]+=g[i][j];
}
}
for(int i=a[1];i>=0;i--){
for(int j=a[2];j>=0;j--){
if(i==0)ans+=(a[1]+a[2]-j)*f[i][j]%mol,ans%=mol;
}
}
cout<<ans<<endl;
(100pts) :组合数
发现答案其实是每个数被选的期望之和，即
[ans=a_1+sum_{i=2}^n f_i (f_i为a_i被选的期望次数)
]
其实是单独考虑 (a_1) 和 (a_i)，这里 (a_i) 被选的期望就是 (f_i)
然后可以 (O(n^2)) 做
考虑优化
发现柿子：
[g_i=sum_{i=0}^{a_x-1}i imes frac{inom{a_x+i-1}{i}}{2^{a_1+i}}+a_x imes (1-sum_{i=0}^{a_x-1} frac{inom{a_x+i-1}{i}}{2^{a_1+i}}) (g_i为当a_x为i时的被选的期望次数，其实就是f_i换了下标)
]
(i)枚举的是选完 (a_1) 时 (a_x)选了多少次，前半部分为选完 (a_1) 时未选完 (a_x) 的期望，后半部分为选完 (a_i) 时已选完 (a_x) 的期望
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define Max(a,b) (a>b?a:b)
#define ll long long
#define int long long
using namespace std;
const int maxn=1e6+5,maxe=1e6,mol=323232323;
const ll INF=0x3f3f3f3f3f3f3f3f;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,m,a[maxn],ny[maxn],c[maxn],f[maxn],ny2[maxn],poww[maxn],maxx,g[maxn];
ll ans;
ll qpow(ll _,int __,ll ___=1){
while(__){
if(__&1)___=___*_%mol;
_=_*_%mol;
__>>=1;
}
return ___;
}
void Init(){
c[0]=poww[0]=1;
for(int i=1;i<=maxe;i++)c[i]=c[i-1]*i%mol,poww[i]=poww[i-1]*2%mol;
ny[maxe]=qpow(c[maxe],mol-2);
ny2[maxe]=qpow(poww[maxe],mol-2);
for(int i=maxe-1;i>=0;i--)ny2[i]=ny2[i+1]*2%mol,ny[i]=ny[i+1]*(i+1)%mol;
}
int C(int _,int __){
if(__==0)return 1;
return c[_]*ny[__]%mol*ny[_-__]%mol;
}
signed main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
n=read();Init();
for(int i=1;i<=n;i++)a[i]=read(),maxx=max(maxx,a[i]);
ans=a[1];
f[0]=C(a[1]-1,0)*ny2[a[1]]%mol;
for(int i=1;i<maxx;i++)f[i]=f[i-1]+C(a[1]+i-1,i)*ny2[a[1]+i]%mol,f[i]%=mol,g[i]=g[i-1]+C(a[1]+i-1,i)*ny2[a[1]+i]%mol*i%mol,g[i]%=mol;
for(int i=2;i<=n;i++)ans+=g[a[i]-1]%mol+a[i]*(1-f[a[i]-1]+mol)%mol,ans+=mol,ans%=mol;//,cout<<g[a[i]-1]%mol<<" "<<a[i]*(mol+1-f[a[i]-1])%mol<<endl;
cout<<ans;
return 0;
}
4.C
(40pts):一个一个跳可以把(n<=5000)，随机，(v=1)的拿满
正解没写