@KirinBill
2017-09-19T17:36:05.000000Z
字数 5769
阅读 1257
题解
套题
考试时,永远不要想着能AK。。。
目录
#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);
}
const int MAXN=100005,P=1e9+7;
int n;
int exa[MAXN],both[MAXN],dp[MAXN][2];
inline int DP(){
dp[1][0]=exa[1];
dp[1][1]=both[1];
for(int i=2,rest;i<=n;++i){
rest=both[i-1]-1;
rest= rest<0 ? 0:rest;
dp[i][0]=(long long)dp[i-1][1]*(exa[i]+rest)%P;
dp[i][0]=(dp[i][0]+(long long)dp[i-1][0]*(exa[i]+both[i-1])%P)%P;
dp[i][1]=(long long)both[i]*(dp[i-1][0]+dp[i-1][1])%P;
}
return dp[n][0];
}
int main(){
setIO("choose");
read(n);
for(int i=1;i<=n;++i)
read(exa[i]);
for(int i=1;i<n;++i)
read(both[i]);
write(DP());
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 <algorithm>
using std::sort;
const int MAXN=1e5+5;
int n,m;
int ufs[MAXN];
struct line{
int u,v,w;
line(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
friend bool operator< (const line &a,const line &b){
return a.w<b.w;
}
}ed[MAXN*3];
struct point{
int x,y,z,id;
static bool cmp_x(const point &a,const point &b){
return a.x<b.x;
}
static bool cmp_y(const point &a,const point &b){
return a.y<b.y;
}
static bool cmp_z(const point &a,const point &b){
return a.z<b.z;
}
}p[MAXN];
inline void ufs_init(int n){
for(int i=1;i<=n;++i)
ufs[i]=i;
}
int find_anc(int x){
if(x==ufs[x]) return x;
ufs[x]=find_anc(ufs[x]);
return ufs[x];
}
inline void deal(){
sort(p+1,p+n+1,point::cmp_x);
for(int i=1;i<n;++i)
ed[++m]=line(p[i].id,p[i+1].id,p[i+1].x-p[i].x);
sort(p+1,p+n+1,point::cmp_y);
for(int i=1;i<n;++i)
ed[++m]=line(p[i].id,p[i+1].id,p[i+1].y-p[i].y);
sort(p+1,p+n+1,point::cmp_z);
for(int i=1;i<n;++i)
ed[++m]=line(p[i].id,p[i+1].id,p[i+1].z-p[i].z);
}
inline long long Kruskal(){
ufs_init(n);
sort(ed+1,ed+m+1);
long long ret=0;
for(int i=1,j=0,lim=n-1,ufa,vfa;j<lim;++i){
ufa=find_anc(ed[i].u);
vfa=find_anc(ed[i].v);
if(ufa!=vfa){
ufs[ufa]=vfa;
ret+=ed[i].w;
++j;
}
}
return ret;
}
int main(){
setIO("planet");
read(n);
for(int i=1;i<=n;++i){
read(p[i].x),read(p[i].y),read(p[i].z);
p[i].id=i;
}
deal();
write(Kruskal());
return 0;
}
我开始竟没有想到是,用了Dijkstra的思想A了,不过常数好大啊...
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using std::queue;
using std::max;
using std::min;
const int MAXN=505,INF=1e9;
int n,m;
int dis[MAXN][MAXN];
char mp[MAXN][MAXN];
struct node{
int x,y;
node(int x=0,int y=0):x(x),y(y){}
}s,t;
inline void cal_dis(){
static int last[MAXN];
memset(dis,0x7f,sizeof(dis));
memset(last,-0x3f,sizeof(last));
for(int i=1;i<=n;++i){
for(int j=1,maxd=-INF;j<=m;++j){
if(mp[i][j]=='+') last[j]=i;
maxd=max(maxd,last[j]+j);
dis[i][j]=min(dis[i][j],i+j-maxd);
}
}
memset(last,-0x3f,sizeof(last));
for(int i=1;i<=n;++i){
for(int j=m,maxd=-INF;j;--j){
if(mp[i][j]=='+') last[j]=i;
maxd=max(maxd,last[j]-j);
dis[i][j]=min(dis[i][j],i-j-maxd);
}
}
memset(last,0x3f,sizeof(last));
for(int i=n;i;--i){
for(int j=1,maxd=-INF;j<=m;++j){
if(mp[i][j]=='+') last[j]=i;
maxd=max(maxd,-last[j]+j);
dis[i][j]=min(dis[i][j],-i+j-maxd);
}
}
memset(last,0x3f,sizeof(last));
for(int i=n;i;--i){
for(int j=m,maxd=-INF;j;--j){
if(mp[i][j]=='+') last[j]=i;
maxd=max(maxd,-last[j]-j);
dis[i][j]=min(dis[i][j],-i-j-maxd);
}
}
}
inline bool in_G(int x,int y){
return x>0 && x<=n && y>0 && y<=m;
}
inline bool jud(int lim){
static int dir[][2]={{0,1},{0,-1},{1,0},{-1,0}};
static bool vis[MAXN][MAXN];
static queue<node> que;
if(dis[s.x][s.y]<lim) return false;
while(que.size()) que.pop();
memset(vis,false,sizeof(vis));
que.push(s);
vis[s.x][s.y]=true;
node u;
int x,y;
while(que.size()){
u=que.front();
que.pop();
for(int i=0;i<4;++i){
x=u.x+dir[i][0],y=u.y+dir[i][1];
if(in_G(x,y) && !vis[x][y] && dis[x][y]>=lim){
if(x==t.x && y==t.y) return true;
que.push(node(x,y));
vis[x][y]=true;
}
}
}
return false;
}
inline int bin_chop(){
int l=1,r=n+m,mid;
while(l<=r){
mid=l+r>>1;
if(jud(mid)) l=mid+1;
else r=mid-1;
}
return l-1;
}
int main(){
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%s",mp[i]+1);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(mp[i][j]=='V') s=node(i,j);
else if(mp[i][j]=='J') t=node(i,j);
}
}
cal_dis();
printf("%d",bin_chop());
return 0;
}