C - Bugged
题意：类似装箱问题，但是最后体积总和不能为10的倍数。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 30001
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
const int MOD=1e9+;
int n,a[],w;
int main(){
int i,j,k;
n=read();
a[]=;
while(n--){
w=read();
for (i=;i>=;i--) a[i+w]|=a[i];
}
for (i=;i>=;i--) if (a[i]&&i%) return printf("%d\n",i),;
puts("");
}
D - Widespread
题意：n只怪物，每只有一个生命值，每次攻击可以指定一只造成A点伤害，其他所有造成B点伤害(A>B)，问全部消灭的最小攻击次数。
题解：二分攻击次数。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 300001
#define int long long
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
const int MOD=1e9+;
int n,a[],w=,mmh=,A,B,L=,R=1e9;
inline bool ju(int x){
int u=B*x,s=;
for (int i=;i<=n;i++)
if (a[i]>u) s+=(a[i]-u+A-)/A;
return s<=x;
}
signed main(){
int i,j,k;
n=read();A=read();B=read();A-=B;
for (i=;i<=n;i++) a[i]=read();
while (L<R){
int mid=L+R>>;
if (ju(mid)) R=mid;else L=mid+;
}
printf("%lld\n",L);
}
E - Meaningful Mean
题意：求一个数组中，平均值不小于k的连续子序列个数。
题解：全部减k之后数据结构处理前缀和即可。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 210001
#define int long long
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
const int MOD=1e9+,M=1e15;
int n,a[MN],ro=,mmh=,k,ls[MN*],rs[MN*],s[MN*],NUM=;
void add(int &p,int l,int r,int k){
if (!p) p=++NUM,ls[p]=rs[p]=s[p]=;
s[p]++;
if (l==r) return;
int mid=l+r>>;
if (k<=mid) add(ls[p],l,mid,k);else add(rs[p],mid+,r,k);
}
int ask(int p,int l,int r,int k){
if (!p) return ;
if (r<=k) return s[p]; int mid=l+r>>;
if (k<=mid) return ask(ls[p],l,mid,k);else return ask(rs[p],mid+,r,k)+ask(ls[p],l,mid,k);
}
signed main(){
int i,j,k;
n=read();k=read();
add(ro,-M,M,);
for (i=;i<=n;i++){
a[i]=read()-k;a[i]+=a[i-];
mmh+=ask(ro,-M,M,a[i]);
add(ro,-M,M,a[i]);
}
printf("%lld\n",mmh);
}
F - Mirrored
题意：记rev(N)为把N在10进制下翻转以后的值（无前导0），给出D，求rev(N)=N+D的N的数量。
题解：好开心在考场上搞了出来。其实就是个暴力。枚举N的位数d，再同时枚举第i和d+1-i位，这样可以确定差中第i位和第d+1-i位的可能值，从而实现剪枝。然后你会发现这玩意可以记忆化……
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MN 21001
#define int long long
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
const int MOD=1e9+;
int n,a[MN],B[MN],x,mmh=,mm[][][][];
inline int M(int x){return x<?x+:x;}
inline void work(int p,int n,int a,int b){
if (mm[p][n][a][b]!=-) {mmh+=mm[p][n][a][b];return;}
int u=mmh;
if (p+p-==n){
if (a==&&b==) mmh+=*(B[p]==);else
if (a==&&b==) mmh+=*(B[p]==);
return;
}
if (p+p->n){
mmh+=a==b;
return;
}
for (int i=p==;i<=;i++)
for (int j=;j<=;j++)
if (M(i-j-b)==B[p]&&(a==(j<i)||j==i)&&(M(j-i)==B[n+-p]||M(j--i)==B[n+-p])){
if (a){
if (j==i&&B[n+-p]==) continue;
work(p+,n,M(j--i)==B[n+-p],i-b-j<);
}else{
if (j==i&&B[n+-p]==) continue;
work(p+,n,M(j--i)==B[n+-p],i-b-j<);
}
}
mm[p][n][a][b]=mmh-u;
}
signed main(){
int i,j,k;
x=n=read();
if (n%) return puts(""),;
for (k=;k<=&&x;k++) B[k]=x%,x/=;k--;
for (int i=k;i<=;i++) memset(mm,-,sizeof(mm)),work(,i,,);
printf("%lld\n",mmh);
}
涨rating啦好开心