1002.Blow up the Enemy
排序签到题
#include<bits/stdc++.h>
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<q.s;
}
int main()
{
scanf("%d",&t);
while(t--)
{
cin>>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++;
else
break;
}
ans=(0.5*u+(n-u)*1.0)/n;
printf("%.6lf\n",ans);
}
}1004.Deliver the Cake
赛时死都找不出bug，赛后看了题解，发现只要建2*n的边就可以了
#include<bits/stdc++.h>
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;
}
};
vector<node>g[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_queue<nod>q;
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;i<g[t.id].size();i++)
{
int j=g[t.id][i].u;
int v=g[t.id][i].val;
if(dis[j]>t.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;i<g[t.id].size();i++)
{
int j=g[t.id][i].u;
int v=g[t.id][i].val;
if(dis[j]>t.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;
else
u2=1;
if(a[v]=='M')
{
v1=1;
v2=1;
}
else if(a[v]=='L')
v1=1;
else
v2=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<bits/stdc++.h>
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<x;j++)
if(a[i][j]!=a[i-1][j])
break;
if(j<x)
f[i]=1;
}
else
f[i]=1;
x=y;
}
dp[1][0]=1,dp[1][1]=0;
for(int i=2;i<=n;i++)
{
if(f[i])
{
dp[i][1]=dp[i-1][0];
dp[i][0]=dp[i-1][1]+dp[i-1][0];
}
else
{
dp[i][1]=0;
dp[i][0]=dp[i-1][0]+dp[i-1][1];
}
dp[i][0]%=mod;
}
cout<<(dp[n][0]+dp[n][1])%mod<<endl;
}
return 0;1007.Go Running
比赛时作为我们队唯一会网络流的并没有觉得这是到网络流题，赛后听大佬说了思路，又找了大概一个小时bug发现没初始化qaq我太菜了
#include<bits/stdc++.h>
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];
pair<ll,ll>U,V;
map<pair<ll,ll>,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;
}
queue<ll>q;
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<<s1<<endl;
while(bfs())
{
ans+=dfs(s,0xffffffff);
}
printf("%lld\n",ans);
}
return 0;
}
1011.Kindergarten Physics
猜结论。。。
#include<bits/stdc++.h>
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);
}
}1012. Last Problem
爆搜。。。直接构造就行。。。看完题解发现挺简单的，但问题是想不到啊。。。
#include<bits/stdc++.h>
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;
}
京公网安备 11010502036488号