@KirinBill
2017-10-05T21:26:45.000000Z
字数 5698
阅读 1059
题解
套题
目录
#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){
int pm=1; char c;
do{
c=getchar();
if(c=='-') pm=-1;
}while(!isdigit(c));
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 MAXL=2005;
int n;
int cnt[26],tot[10];
char s[MAXL];
inline int idx(char c){return c-'A';}
inline void deal(){
for(int i=1;i<=n;++i)
++cnt[idx(s[i])];
}
inline void solve(){
//0
tot[0]=cnt[idx('Z')];
cnt[idx('Z')]=0;
cnt[idx('E')]-=tot[0];
cnt[idx('O')]-=tot[0];
cnt[idx('R')]-=tot[0];
//2
tot[2]=cnt[idx('W')];
cnt[idx('W')]=0;
cnt[idx('O')]-=tot[2];
cnt[idx('T')]-=tot[2];
//4
tot[4]=cnt[idx('U')];
cnt[idx('U')]=0;
cnt[idx('F')]-=tot[4];
cnt[idx('O')]-=tot[4];
cnt[idx('R')]-=tot[4];
//6
tot[6]=cnt[idx('X')];
cnt[idx('X')]=0;
cnt[idx('I')]-=tot[6];
cnt[idx('S')]-=tot[6];
//8
tot[8]=cnt[idx('G')];
cnt[idx('G')]=0;
cnt[idx('E')]-=tot[8];
cnt[idx('H')]-=tot[8];
cnt[idx('I')]-=tot[8];
cnt[idx('T')]-=tot[8];
//3
tot[3]=cnt[idx('T')];
cnt[idx('T')]=0;
cnt[idx('E')]-=tot[3]<<1;
cnt[idx('H')]-=tot[3];
cnt[idx('R')]-=tot[3];
//5
tot[5]=cnt[idx('F')];
cnt[idx('F')]=0;
cnt[idx('E')]-=tot[5];
cnt[idx('I')]-=tot[5];
cnt[idx('V')]-=tot[5];
//1
tot[1]=cnt[idx('O')];
cnt[idx('O')]=0;
cnt[idx('E')]-=tot[1];
cnt[idx('N')]-=tot[1];
//7
tot[7]=cnt[idx('S')];
cnt[idx('S')]=0;
cnt[idx('E')]-=tot[7]<<1;
cnt[idx('N')]-=tot[7];
cnt[idx('V')]-=tot[7];
//9
tot[9]=cnt[idx('E')];
cnt[idx('E')]=0;
cnt[idx('I')]-=tot[9];
cnt[idx('N')]-=tot[9]<<1;
}
int main(){
setIO("number");
scanf("%s",s+1);
n=strlen(s+1);
deal();
solve();
for(int i=0;i<=9;++i){
for(int j=1;j<=tot[i];++j)
putchar(i|'0');
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#include <functional>
using std::queue;
using std::abs;
using std::priority_queue;
using std::vector;
using std::greater;
const int MAXN=100005,MAXHW=505;
int n,h,w,a,b,c;
int dirx[]={1,0,-1,0},diry[]={0,1,0,-1};
long long nearP[MAXHW][MAXHW];
struct node{
int x,y;
long long dis;
node(int x=0,int y=0,long long dis=0):x(x),y(y),dis(dis){}
friend bool operator> (const node &a,const node &b){
return a.dis>b.dis;
}
}p[MAXN];
inline bool inG(node &a){
return 0<=a.x && a.x<=h && 0<=a.y && a.y<=w;
}
inline void BFS(){
static queue<node> que;
memset(nearP,0x7f,sizeof(nearP));
nearP[p[n].x][p[n].y]=0;
for(int i=1;i<n;++i){
nearP[p[i].x][p[i].y]=0;
que.push(node(p[i].x,p[i].y));
}
node u,v;
int d;
while(que.size()){
u=que.front();
que.pop();
d=nearP[u.x][u.y]+1;
for(int i=0;i<4;++i){
v.x=u.x+dirx[i],v.y=u.y+diry[i];
if(inG(v) && nearP[v.x][v.y]>d){
nearP[v.x][v.y]=d;
que.push(v);
}
}
}
for(int i=0;i<=h;++i){
for(int j=0;j<=w;++j)
nearP[i][j]*=c;
}
}
inline long long hp_SPFA(){
static long long dis[MAXHW][MAXHW];
static bool inQ[MAXHW][MAXHW];
static priority_queue<node,vector<node>,greater<node> > hq;
memset(dis,0x7f,sizeof(dis));
memset(inQ,false,sizeof(inQ));
dis[p[1].x][p[1].y]=0;
hq.push(p[1]);
inQ[p[1].x][p[1].y]=true;
node u,v;
long long d;
while(hq.size()){
u=hq.top();
hq.pop();
inQ[u.x][u.y]=false;
d=dis[u.x][u.y]+c;
for(int i=0;i<4;++i){
v.x=u.x+dirx[i],v.y=u.y+diry[i];
if(inG(v) && dis[v.x][v.y]>d){
v.dis=dis[v.x][v.y]=d;
if(!inQ[v.x][v.y]){
hq.push(v);
inQ[v.x][v.y]=true;
}
}
}
v.y=u.y;
for(v.x=0;v.x<=h;++v.x){
d=dis[u.x][u.y]+(long long)a*abs(u.x-v.x)+b+nearP[v.x][v.y];
if(dis[v.x][v.y]>d){
v.dis=dis[v.x][v.y]=d;
if(!inQ[v.x][v.y]){
hq.push(v);
inQ[v.x][v.y]=true;
}
}
}
v.x=u.x;
for(v.y=0;v.y<=w;++v.y){
d=dis[u.x][u.y]+(long long)a*abs(u.y-v.y)+b+nearP[v.x][v.y];
if(dis[v.x][v.y]>d){
v.dis=dis[v.x][v.y]=d;
if(!inQ[v.x][v.y]){
hq.push(v);
inQ[v.x][v.y]=true;
}
}
}
}
return dis[p[n].x][p[n].y];
}
int main(){
freopen("express.in","r",stdin);
freopen("express.out","w",stdout);
scanf("%d%d",&h,&w);
scanf("%d%d%d",&a,&b,&c);
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&p[i].x,&p[i].y);
BFS();
printf("%lld",hp_SPFA());
return 0;
}
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
using std::min;
using std::priority_queue;
using std::vector;
using std::greater;
const int MAXN=3005;
int n,m,k,rest,a,b,c;
int stp[MAXN];
long long T;
inline int solve(){
static priority_queue<int,vector<int>,greater<int> > hp;
long long t,cnt,nowt;
int ret=0;
for(int i=1;i<m;++i){
t=(long long)b*(stp[i]-1);
if(t>T) break;
ret+=(i!=1);
cnt=min((long long)stp[i+1]-stp[i]-1,(T-t)/a);
ret+=cnt;
for(int now=cnt+stp[i]+1,nex=stp[i+1];now<nex;now+=cnt){
nowt=t+(long long)c*(now-stp[i]);
if(nowt>T) break;
cnt=1+min((long long)nex-now-1,(T-nowt)/a);
if(rest){
--rest;
hp.push(cnt);
}
else if(hp.top()<cnt){
hp.pop();
hp.push(cnt);
}
else break;
}
}
if((long long)b*(stp[m]-1)<=T) ++ret;
while(hp.size()){
ret+=hp.top();
hp.pop();
}
return ret;
}
int main(){
freopen("ftl.in","r",stdin);
freopen("ftl.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d%d",&a,&b,&c);
scanf("%lld",&T);
for(int i=1;i<=m;++i)
scanf("%d",&stp[i]);
rest=k-m;
printf("%d",solve());
return 0;
}