知识普及：
Educational使用拓展ACM赛制，没有现场hack，比赛后有12h的全网hack时间。
rank按通过题数排名，若通过题数相等则按罚时排名。
（罚时计算方式：第一次通过每题的时间之和+错误提交次数$\times$10min）
A：
送分题。
#include<bits/stdc++.h>
#define maxn 100005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long using namespace std;
bool may[]; char str[maxn]; inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
} int main(){
int T=read();
while(T--){
scanf("%s",str+);
int n=strlen(str+);
memset(may,,sizeof(may));
for(int i=;i<=n;){
int j=i; while(str[j]==str[j+]) j++;
if((j-i+)%) may[str[i]-'a']=;
i=j+;
}
for(int i=;i<;i++)
if(may[i]) printf("%c",(char)(i+'a'));
cout<<endl;
}
return ;
}
A
B：
送分题。因为根据样例猜结论wa了一发。
看到有人dp？？？这难道不是瓶颈在读入的结论题？
#include<bits/stdc++.h>
#define maxn 100005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long using namespace std;
char str[maxn]; inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
} int main(){
int T=read();
while(T--){
int n=read(),n1=,n0=,t1=;
for(int i=;i<=n;i++){
scanf("%s",str+);
int len=strlen(str+);
if(len%) t1++;
for(int j=;j<=len;j++){
if(str[j]=='') n1++;
else n0++;
}
}
if(n0<n1) swap(n0,n1);
if(t1%){
if(n0%==n1%) cout<<n-<<endl;
else cout<<n<<endl;
}
else if(t1==){
if(n0%==) cout<<n-<<endl;
else cout<<n<<endl;
}
else cout<<n<<endl;
}
return ;
}
B
C：
送分题。
注意到奇数之间的顺序不会变化，偶数之间的顺序也不会变化，于是做一下归并排序的合并操作即可。
#include<bits/stdc++.h>
#define maxn 300005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long using namespace std;
char str[maxn];
int t1[maxn],t0[maxn]; inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
} int main(){
int T=read();
while(T--){
scanf("%s",str+);
int n=strlen(str+);
t1[]=t0[]=;
for(int i=;i<=n;i++){
if((str[i]-'')%) t1[++t1[]]=str[i]-'';
else t0[++t0[]]=str[i]-'';
}
int p1=,p0=;
while(p1<=t1[] || p0<=t0[]){
if(p1>t1[]) printf("%d",t0[p0]),p0++;
else if(p0>t0[]) printf("%d",t1[p1]),p1++;
else{
if(t1[p1]<t0[p0]) printf("%d",t1[p1]),p1++;
else printf("%d",t0[p0]),p0++;
}
}
cout<<endl;
}
return ;
}
C
D：
送分题。
中位数没有太多性质，要么枚举答案要么二分答案。
二分完判一下边界求能达到目标的最小价值即可。
由于没判一个人wa了一发，边界没判好又wa了一发。
#include<bits/stdc++.h>
#define maxn 200005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long using namespace std;
ll n; struct node{ll l,r;}a1[maxn],a2[maxn],e[maxn]; inline ll read(){
ll x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
} inline bool cmp1(node x,node y){return x.r<y.r;}
inline bool cmp2(node x,node y){return x.l<y.l;} inline ll calc(ll x){
ll sum=,n1=,n2=;
for(ll i=;i<=n;i++)
if(e[i].r<x) sum+=e[i].l,n1++;
for(ll i=;i<=n;i++)
if(e[i].l>x) sum+=e[i].l,n2++;
if(n1>n/) return (1ll<<);
if(n2>n/) return ;
ll tp=n/-n1;
for(ll i=;i<=n;i++)
if(a1[i].l<=x && a1[i].r>=x){
if(tp) sum+=a1[i].l,tp--;
else sum+=x;
}
return sum;
} int main(){
ll T=read();
while(T--){
n=read(); ll s=read();
for(ll i=;i<=n;i++){
e[i].l=a1[i].l=a2[i].l=read();
e[i].r=a1[i].r=a2[i].r=read();
}
sort(a1+,a1+n+,cmp2);
if(n==){cout<<min(s,e[].r)<<endl;continue;}
ll l=,r=(ll)(1e9),ans=;
while(l<=r){
ll mid=l+r>>;
//cout<<mid<<":"<<calc(mid)<<endl;
if(calc(mid)<=s) ans=mid,l=mid+;
else r=mid-;
}
printf("%I64d\n",ans);
}
return ;
}
D
E：
送分题。但我把分还给了这个世界。
实际上所有人被m值划分成了若干个阶梯，每个阶梯都会在一起投票。
考虑$m_{i}$最大的那个人。如果他前面的人数还不到$m_{i}$，那不管怎么样都必须花钱买他，否则暂时没有必要买他。
那么按m值排序后倒着考虑每个人，维护一个以$p_{i}$为关键字的小根堆，如果要买就买若干个最小的。
容易用归纳法证明该算法的正确性。复杂度$O(nlogn)$。
（当时是0：40，我在大脑混乱的情况下想写一个给数组直接排序的$O(n^{2}logn)$的做法过E1。）
（然后我没考虑如果给后面的东西按p排序会把有序的m搞乱掉，于是我就对着一发wa on 2沉思到考试结束。）
（这种明显是我的锅当然要甩给石神了！谁让它那么可爱！）
#include<bits/stdc++.h>
#define maxn 200005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long using namespace std;
ll n;
struct node{ll m,p,id;}a[maxn];
priority_queue<ll> q; inline ll read(){
ll x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
} inline bool cmp1(node x,node y){return x.m<y.m;}
inline bool cmp2(node x,node y){return x.p<y.p;} int main(){
ll T=read();
while(T--){
n=read();
for(ll i=;i<=n;i++) a[i].m=read(),a[i].p=read();
sort(a+,a++n,cmp1);
ll num=,ans=;
for(ll i=n;i>=;i--){
q.push(-a[i].p);
while(i-+num<a[i].m) ans+=-q.top(),q.pop(),num++;
}
printf("%I64d\n",ans);
while(!q.empty()) q.pop();
}
return ;
}
E
F：
注意到对于一个红块，它可选的白块范围是确定的。
对于一个$Q_{i}$，如果我们确定了放哪个红块，那么能放的白块数就确定下来了。
那么我们可以预处理每个红块对应的放$i$个白块的方案数。
推组合数复杂度显然不对，但可以考虑生成函数，它的本质也是解决有限或无限元素的组合问题。
如果一个白块的$h_{i}$出现了多于两次，由于要求严格递增，那么它最多只能在两边各放一个。于是我们可以把它当做出现了两次。
根据生成函数相关知识，我们得到：
1.若一个$h_{i}$出现一次，那么它在方案中对应一个$(1+2x)$，表示不放/放左边或放右边。
2.若一个$h_{i}$出现两次，那么它在方案中对应一个$(1+2x+x^{2})$，表示不放/放左边或放右边/放两边。
将这些多项式乘起来，$x^{m}$项的系数就是放m个白块的方案数。
一开始我写了一个卷积快速幂进行$logn$次$NTT$。然后T on 97。（幸好我考场上压根没写）
然后在欧神的教导下我发现：进行一次$NTT$后做点值快速幂就完事了，我根本没学明白。
一些非常致命的细节：
1.写多项式应用题时一定要开一个临时数组然后对其$NTT$，不然会将原数组变换成点值表示。
2.如果你不想开临时数组可以每次把用到的数组清空一遍，注意清空一定要清到$NTT$时的len而不是需要保留的len。
3.强烈不建议$NTT$过去后再$NTT$回来，1s跑不了几次$NTT$。
4.当你把一个数组作为参数传到函数里时是用不了$sizeof(a)$的，这时候这东西只会返回1个变量的$size$。
#include<bits/stdc++.h>
#define maxn 300005
#define maxm 1<<21|1
#define inf 0x7fffffff
#define mod 998244353
#define g 3
#define ll long long
#define rint register ll using namespace std;
ll mx=3e5,h1[maxn],h2[maxn],ind[maxm];
ll p1[maxm],p2[maxm],tq[maxm],tp[maxm];
ll res[][maxm]; inline ll read(){
ll x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
} inline ll mo(ll x){return x>=mod?x-mod:x;}
inline ll power(ll a,ll b){ll ans=;while(b){ans=(b&)?ans*a%mod:ans,a=a*a%mod,b>>=;}return ans;}
inline void copy(ll *a,ll *b){for(rint i=;i<(maxm>>);i++) a[i]=b[i];}
inline void clear(ll *a,ll x){for(rint i=;i<(maxm>>);i++) a[i]=;a[]=,a[]=(x?:),a[]=(x==);} //不能使用sizeof(*a)的形式
inline void print(ll *a){for(rint i=;i<=;i++) cout<<a[i]<<" ";cout<<endl;} namespace P{
inline void ntt(ll *a,ll n,ll op){
for(rint i=;i<n;i++) ind[i]=(i&)?((ind[i>>]>>)|(n>>)):(ind[i>>]>>);
for(rint i=;i<n;i++) if(ind[i]>i) swap(a[i],a[ind[i]]);
for(rint l=;l<=n;l<<=){
ll p=power(g,(mod-)/l);
if(op==-) p=power(p,mod-);
for(rint i=;i<n;i+=l)
for(ll j=i,w=,t;j<i+(l>>);j++,w=w*p%mod)
t=a[j+(l>>)]*w%mod,a[j+(l>>)]=mo(a[j]-t+mod),a[j]=mo(a[j]+t);
}
}
inline ll conv(ll *a,ll n,ll *b,ll m){
ll len=,lim=min(n+m,mx);
while(len<=lim) len<<=;
ntt(a,len,),ntt(b,len,);
for(rint i=;i<len;i++) a[i]=a[i]*b[i]%mod;
ntt(a,len,-); ll inv=power(len,mod-);
for(rint i=;i<len;i++) a[i]=a[i]*inv%mod;
return lim;
}
inline ll conp(ll *a,ll b,ll c){
if(b==){clear(a,);return ;}
ll len=,lim=min(c*b,(ll)mx);
while(len<=lim) len<<=; ntt(a,len,);
for(rint i=;i<len;i++) a[i]=power(a[i],b);
ntt(a,len,-); ll inv=power(len,mod-);
for(rint i=;i<len;i++) a[i]=a[i]*inv%mod;
return lim;
}
} int main(){
ll n=read(),k=read();
for(rint i=;i<=n;i++) h1[i]=read();
for(rint i=;i<k;i++) h2[i]=read();
sort(h1+,h1++n),sort(h2,h2+k);
for(rint i=;i<k;i++){
ll l1=,l2=,now=,n1=,n2=;
while(now<=n){
if(h1[now]>=h2[i]) break;
ll j=now; while(j+<=n && h1[j]==h1[j+]) j++;
if(j==now) n1++; else n2++; now=j+;
}
clear(p1,),l1=;l1=P::conp(p1,n1,l1);
clear(p2,),l2=;l2=P::conp(p2,n2,l2);
//print(p1),print(p2);
l1=P::conv(p1,l1,p2,l2),copy(res[i],p1);
//print(res[i]);
}
ll Q=read();
while(Q--){
ll q=read(),ans=;
for(rint i=;i<k;i++){
ll num=(q-*h2[i])/;
if(num-<) break;
if(num->(ll)mx) continue;
ans=mo(ans+res[i][num-]);
}
printf("%I64d\n",ans);
}
return ;
}
F