2020杭电多校第四场

1002.Blow up the Enemy

排序签到题

#include
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int INF = 0x3f3f3f3f;
int t,n,k,now;
struct node{int a;int b;int s;
}x[maxn];
bool cmp(node p,node q)
{return p.s>n;for(int i=1;i<=n;i++){cin>>x[i].a>>x[i].b;k=ceil(100.0/x[i].a)-1;x[i].s=k*x[i].b;}sort(x+1,x+1+n,cmp);double ans=0;ll u=0;for(int i=1;i<=n;i++){if(x[1].s==x[i].s)u++;elsebreak;}ans=(0.5*u+(n-u)*1.0)/n;printf("%.6lf\n",ans);}}

1004.Deliver the Cake

赛时死都找不出bug，赛后看了题解，发现只要建2*n的边就可以了

#include
using namespace std;
#define ll long long
#define pf printf
#define pi acos(-1)
#define pb push_back
const int mod=1e9+7;
const int N=1e6+10;
int n,m,st,en,x;
struct node
{int u,val;
};
struct nod
{ll d;int id;bool operator < (const nod &b) const {return d > b.d;}
};
vectorg[N];
char a[N];
ll dis[N];
int vis[N];
ll spfa()
{for(int i=1;i<=2*n+2;i++)dis[i]=1e16,vis[i]=0;nod s,t;priority_queueq;s.id=st;s.d=0;dis[st]=0;q.push(s);while(!q.empty()){t=q.top();q.pop();if(vis[t.id])continue;vis[t.id]=1;for(int i=0;it.d+v){dis[j]=t.d+v;q.push({dis[j],j});}}}ll aa=min(dis[en],dis[en+n]);for(int i=1;i<=2*n+2;i++)dis[i]=1e16,vis[i]=0;s.id=st+n;s.d=0;dis[st+n]=0;q.push(s);while(!q.empty()){t=q.top();q.pop();if(vis[t.id])continue;vis[t.id]=1;for(int i=0;it.d+v){dis[j]=t.d+v;q.push({dis[j],j});}}}ll bb=min(dis[en],dis[en+n]);return min(aa,bb);
}
int main()
{int t;cin>>t;while(t--){ll ans=5e18;scanf("%d %d %d %d %d",&n,&m,&st,&en,&x);for(int i=1;i<=2*n+2;i++)g[i].clear();scanf("%s",a+1);for(int i=1;i<=m;i++){int u,v,c;int u1=0,u2=0,v1=0,v2=0;scanf("%d %d %d",&u,&v,&c);if(a[u]=='M'){u1=1;u2=1;}else if(a[u]=='L')u1=1;elseu2=1;if(a[v]=='M'){v1=1;v2=1;}else if(a[v]=='L')v1=1;elsev2=1;if(u1==v1){g[u].pb({v,c});g[v].pb({u,c});}if(u2==v2){g[u+n].pb({v+n,c});g[v+n].pb({u+n,c});}if(u1==v2){g[u].pb({v+n,c+x});g[v+n].pb({u,c+x});}if(v1==u2){g[u+n].pb({v,c+x});g[v].pb({u+n,c+x});}}ans=spfa();pf("%lld\n",ans);}return 0;
}

1005.Equal Sentences

dp

#include
using namespace std;
typedef unsigned long long ll;
const int mod=1e9+7;
const int maxn=1e5+10;
char a[maxn][10];
int dp[maxn][2],f[maxn],n;
int main()
{int t,x,y;cin>>t;while(t--){scanf("%d",&n);x=0;for(int i=1;i<=n;i++){f[i]=0;scanf("%s",a[i]);y=strlen(a[i]);if(x==y){int j;for(j=0;j

#include
using namespace std;
typedef long long ll;
const int N=200000+10;
ll n,s,s1,t,h[N],cur[N],cnt=1,vis[N];
pairU,V;
map,ll>m;
struct node{ll to,nt,w;
}e[N*5];
void add(ll u,ll v,ll w)
{e[++cnt]={v,h[u],w};h[u]=cnt;
}
queueq;
bool bfs()
{memset(vis,0,sizeof vis);vis[s]=1;q.push(s);while(!q.empty()){ll u=q.front();q.pop();cur[u]=h[u];for(ll i=h[u];i;i=e[i].nt){ll v=e[i].to,w=e[i].w;if(w&&!vis[v]){vis[v]=vis[u]+1;q.push(v);}}}return vis[t];}
ll dfs(ll u,ll flow)
{if(u==t)return flow;ll res=flow;for(ll i=cur[u];i;i=e[i].nt){ll v=e[i].to,w=e[i].w;if(w&&vis[u]+1==vis[v]){ll now=dfs(v,min(res,w));if(!now)vis[v]=1;else{e[i].w-=now;e[i^1].w+=now;res-=now;}}if(!res)return flow;}return flow-res;
}
int main()
{int T;cin>>T;while(T--){scanf("%lld",&n);memset(cur,0,sizeof cur);memset(h,0,sizeof h);s=1;t=2;cnt=1;m.clear();s1=2;for(int i=1;i<=n;i++){int y,x;scanf("%d %d",&y,&x);U.first=1;U.second=y-x;int flag=0;if(m[U]==0){s1++;m[U]=s1;add(s,m[U],1);add(m[U],s,0);flag=1;}V.first=-1;V.second=y+x;if(m[V]==0){s1++;m[V]=s1;add(m[V],t,1);add(t,m[V],0);flag=1;}//if(flag==1){add(m[U],m[V],1);add(m[V],m[U],0);}}ll ans=0;//cout<

#include
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int INF = 0x3f3f3f3f;
int t,n,k,now,a,b,c,d;
int main()
{scanf("%d",&t);while(t--){cin>>a>>b>>c>>d;double ans=c*1.0;printf("%.7lf\n",ans);}}

#include
using namespace std;
typedef long long ll;
const int N=2000+10;
ll n,s,s1,t,h[N],cur[N],cnt=0,vis[N];
int b[5][2]={0,0,0,-1,-1,0,1,0,0,1};
int f[N][N];
void dfs(int x,int y,int k)
{if(k<=0)return;for(int i=1;i<=4;i++){int xx=x+b[i][0],yy=y+b[i][1];if(f[xx][yy]!=k-i)dfs(xx,yy,k-i);}f[x][y]=k;printf("%d %d %d\n",x,y,k);
}
int main()
{cin>>n;dfs(1000,1000,n);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！