@KirinBill
2017-09-19T17:34:47.000000Z
字数 5498
阅读 1176
题解
套题
目录
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
x=0;
int pm=1; char c;
do{c=getchar();}while(!isdigit(c) && c!='-');
c=='-' ? pm=-1:x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <algorithm>
using std::sort;
const int MAXN=1e5+5;
int n,lim;
int c[MAXN];
long long ans;
inline bool cmp(int a,int b){
return a>b;
}
int main(){
setIO("bookstore");
read(n);
for(int i=1;i<=n;++i)
read(c[i]);
sort(c+1,c+n+1,cmp);
lim=n/3*3;
for(int i=1;i<=lim;i+=3)
ans+=c[i]+c[i+1];
for(int i=lim+1;i<=n;++i)
ans+=c[i];
write(ans);
return 0;
}
不过考试时递推处理感觉比较稳。。。
#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
string in=file+".in",out=file+".out";
freopen(in.c_str(),"r",stdin);
freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
x=0;
int pm=1; char c;
do{c=getchar();}while(!isdigit(c) && c!='-');
c=='-' ? pm=-1:x=c^'0';
while(c=getchar(),isdigit(c))
x=x*10+(c^'0');
x*=pm;
}
template<typename type>
void write(type x,char c=0){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10|'0');
if(c) putchar(c);
}
#include <cstring>
const int MAXN=2005,P=1e9;
int n,m;
int tab[MAXN][MAXN],dp[MAXN][MAXN];
inline void pre_tab(){
for(int i=0;i<MAXN;++i)
tab[0][i]=1;
for(int i=1;i<MAXN;++i){
tab[i][0]=tab[i-1][0];
for(int j=1;j<MAXN;++j)
tab[i][j]=(tab[i-1][j]+tab[i][j-1])%P;
}
for(int i=1;i<MAXN;++i){
for(int j=MAXN-1;j;--j)
tab[i][j]=(tab[i][j]-tab[i][j-1]+P)%P;
}
}
inline int DP(){
memset(dp,0,sizeof(dp));
dp[1][0]=tab[m][0];
for(int i=1;i<=m;++i)
dp[1][i]=(tab[m][i]+dp[1][i-1])%P;
for(int i=2;i<=n;++i){
dp[i][0]=(long long)dp[i-1][0]*tab[m][0]%P;
for(int j=1;j<=m;++j)
dp[i][j]=((long long)dp[i-1][j]*tab[m][j]%P+dp[i][j-1])%P;
}
return dp[n][m];
}
int main(){
setIO("table");
pre_tab();
int T;
read(T);
while(T--){
read(n),read(m);
write(DP(),'\n');
}
return 0;
}
unsigned long long
范围内,这题就很好做了;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ls (u<<1)
#define rs (ls|1)
using std::swap;
using std::min;
using std::abs;
const int MAXN=1e5+5;
int ns,nt;
char cmd[MAXN],s[MAXN],t[MAXN];
class segT{
private:
int n;
struct node{int sum,tag;}d[MAXN<<2];
void upd(int u){
d[u].sum=d[ls].sum+d[rs].sum;
}
void push_d(int u,int l,int r){
if(l==r || !d[u].tag) return;
int mid=l+r>>1;
d[ls].sum=(mid-l+1)*(d[u].tag-1);
d[ls].tag=d[u].tag;
d[rs].sum=(r-mid)*(d[u].tag-1);
d[rs].tag=d[u].tag;
d[u].tag=0;
}
void mdf(int u,int lp,int rp,int l,int r,int k){
if(l<=lp && rp<=r){
d[u].sum=(rp-lp+1)*(k-1);
d[u].tag=k;
return;
}
push_d(u,lp,rp);
int mid=lp+rp>>1;
if(l<=mid) mdf(ls,lp,mid,l,r,k);
if(r>mid) mdf(rs,mid+1,rp,l,r,k);
upd(u);
}
int qry(int u,int lp,int rp,int r,int k){
if(lp>r) return 0;
if(lp==rp) return d[u].sum==k ? lp:0;
if(k==1 && d[u].sum==0) return 0;
else if(k==0 && d[u].sum==rp-lp+1) return 0;
push_d(u,lp,rp);
int mid=lp+rp>>1;
int ret=qry(rs,mid+1,rp,r,k);
if(ret==0) ret=qry(ls,lp,mid,r,k);
return ret;
}
void prt(int u,int lp,int rp,int r,char c[]){
if(lp>r) return;
if(lp==rp){
c[lp]=d[u].sum|'0';
return;
}
push_d(u,lp,rp);
int mid=lp+rp>>1;
prt(ls,lp,mid,r,c);
prt(rs,mid+1,rp,r,c);
}
public:
void sgl_mdf(int pos,int k){mdf(1,1,n,pos,pos,k+1);}
void rge_mdf(int l,int r,int k){
if(l>r) return;
mdf(1,1,n,l,r,k+1);
}
int qry(int r,int k){return qry(1,1,n,r,k);}
void init(int sz){
memset(d,0,sizeof(d));
n=sz;
sgl_mdf(1,1);
}
void out(int r,char c[]){prt(1,1,n,r,c);}
}T;
inline int find(char c[]){
int lastbit=1,lim=strlen(cmd+1)+1;
T.init(lim);
for(int i=1,lowbit;i<=lim;++i){
switch(cmd[i]){
case '1': ++lastbit;
T.sgl_mdf(lastbit,0);
break;
case '2': ++lastbit;
T.sgl_mdf(lastbit,1);
break;
case 'U': --lastbit;
break;
case 'L': lowbit=T.qry(lastbit,1);
T.sgl_mdf(lowbit,0);
T.rge_mdf(lowbit+1,lastbit,1);
break;
case 'R': lowbit=T.qry(lastbit,0);
T.sgl_mdf(lowbit,1);
T.rge_mdf(lowbit+1,lastbit,0);
break;
}
}
T.out(lastbit,c);
return lastbit;
}
inline int cal_dis(){
int n=min(ns,nt);
int lim=n-1<<1,disy=abs(nt-ns)+lim,ret=disy;
bool apart=false;
for(int i=2,disx=0;i<=n;++i){
disy-=2;
if(apart){
disx=disx<<1|1;
if(s[i]=='1') --disx;
if(t[i]=='0') --disx;
}
else if(s[i]!=t[i]){
apart=true;
++disx;
if(s[i]=='1') swap(s,t);
}
if(disx>ret) break;
ret=min(ret,disx+disy);
}
return ret;
}
int main(){
freopen("board.in","r",stdin);
freopen("board.out","w",stdout);
scanf("%s",cmd+1);
ns=find(s);
scanf("%s",cmd+1);
nt=find(t);
printf("%d",cal_dis());
return 0;
}