A:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n[N];
int m,mm,nn;
int main()
{
scanf("%d%d",&m,&nn);
for(int i=1;i<=m;i++){
cin>>n[i];
}
while(nn--){
scanf("%d",&mm);
int ans=0;
for(int i=20;i>=0;i--)
{
if(ans+(1<<i)<=m){
if(n[ans+(1<<i)]< mm){
ans+=1<<i;
}
}
}
if(n[ans+1]==mm && ans <m) printf("%d ",ans+1);
else printf("-1 ");
}
return 0;
}
B:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+200,INF=2e9;
struct City
{
int id,al;//identifier,altitude
friend bool operator < (City a,City b)
{
return a.al<b.al;
}
};
int n,m,x0,la,lb,ansid;
int h[N],s[N],x[N];
int f[20][N][5],da[20][N][5],db[20][N][5];
double ans=INF*1.0;
multiset<City> q;
void calc(int S,int X)
{
int p=S;
la=0,lb=0;
for(int i=18;i>=0;i--)
if(f[i][p][0] && la+lb+da[i][p][0]+db[i][p][0]<=X)
{
la+=da[i][p][0];
lb+=db[i][p][0];
p=f[i][p][0];
}
}
void pre()
{
h[0]=INF,h[n+1]=-INF;
City st;//start
st.id=0,st.al=INF;
q.insert(st),q.insert(st);
st.id=n+1,st.al=-INF;
q.insert(st),q.insert(st);
for(int i=n;i;i--)
{
int ga,gb;
City now;
now.id=i,now.al=h[i];
q.insert(now);
set<City>::iterator p=q.lower_bound(now);
p--;
int lt=(*p).id,lh=(*p).al;//last
p++,p++;
int ne=(*p).id,nh=(*p).al;//next
p--;
if(abs(nh-h[i])>=abs(h[i]-lh))
{
gb=lt;
p--,p--;
if(abs(nh-h[i])>=abs(h[i]-(*p).al))
ga=(*p).id;
else
ga=ne;
}
else
{
gb=ne;
p++,p++;
if(abs((*p).al-h[i])>=abs(h[i]-lh))
ga=lt;
else
ga=(*p).id;
}//2、预处理
f[0][i][0]=ga,f[0][i][1]=gb;
da[0][i][0]=abs(h[i]-h[ga]);
db[0][i][1]=abs(h[i]-h[gb]);//3、DP初值
}
for(int i=1;i<=18;i++)
for(int j=1;j<=n;j++)
for(int k=0;k<2;k++)
if(i==1)
{
f[1][j][k]=f[0][f[0][j][k]][1-k];
da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][1-k];
db[1][j][k]=db[0][j][k]+db[0][f[0][j][k]][1-k];
}
else
{
f[i][j][k]=f[i-1][f[i-1][j][k]][k];
da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][k];
db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][k];
}//3、倍增优化DP
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&h[i]);
cin>>x0>>m;
for(int i=1;i<=m;i++)
scanf("%d%d",&s[i],&x[i]);//1、输入
pre();
for(int i=1;i<=n;i++)
{
calc(i,x0);
double nowans=(double)la/(double)lb;
if(nowans<ans)
{
ans=nowans;
ansid=i;
}
else
if(nowans==ans && h[ansid]<h[i])
ansid=i;
}
cout<<ansid<<endl;//4、求解问题1
for(int i=1;i<=m;i++)
{
calc(s[i],x[i]);
printf("%d %d\n",la,lb);
}//5、求解问题2
return 0;
}
C:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int nb=0,f=1;
char c=getchar();
while(c>'9' || c<'0'){
if(c=='-') f=-f;
c=getchar();
}
while(c>='0' && c<='9'){
nb=(nb<<3)+(nb<<1)+c-'0';
c=getchar();
}
return nb*f;
}
int n,m,u,v;
int f[66][66][88],g[66][88];
int main(){
n=read(),m=read();
memset(g,0x3f,sizeof(g));
for(int i=1;i<=m;i++){
u=read(),v=read();
f[u][v][0]=1;
g[u][v]=1;
}
for(int p=1;p<=64;p++){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(f[i][j][p-1]==1 && f[j][k][p-1]==1){
f[i][k][p]=1;
g[i][k]=1;
}
}
}
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][k]=min(g[i][k],g[i][j]+g[j][k]);
}
}
}
cout<<g[1][n]<<"\n";
return 0;
}
D:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int nb=0,f=1;
char c=getchar();
while(c>'9' || c<'0'){
if(c=='-') f=-f;
c=getchar();
}
while(c>='0' && c<='9'){
nb=(nb<<3)+(nb<<1)+c-'0';
c=getchar();
}
return nb*f;
}
const int N=2e5;
int d[N][40],mi[N][40];
int n;
long long s[N][40],k;
signed main(){
n=read(),k=read();
for(int i=1;i<=n;i++){
int x=read();
x++;
d[i][0]=x;
}
for(int i=1;i<=n;i++){
int x;
x=read();
s[i][0]=mi[i][0]=x;
}
for(int j=1;j<=34;j++){
for(int i=1;i<=n;i++){
d[i][j]=d[d[i][j-1]][j-1];
s[i][j]=s[i][j-1]+s[d[i][j-1]][j-1];
mi[i][j]=min(mi[i][j-1],mi[d[i][j-1]][j-1]);
}
}
for(int i=1;i<=n;i++){
int now=i,mii=2147483646;
long long sum =0;
for(int j=0;j<=34;j++){
if(k&(1ll<<j)){
sum+=s[now][j];
mii=min(mii,mi[now][j]);
now=d[now][j];
}
}
cout<<sum<<" "<<mii<<"\n";
}
return 0;
}
E:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,f[N][21],mn[N][21],dp[N];
int T,tot1,tot2,head1[N],head2[N];
struct edge1{int to,next;}e1[N<<1];
struct edge2{int get,k,w;}e2[N<<1];
void add_edge1(int u,int v)
{
e1[++tot1].to=v;
e1[tot1].next=head1[u];
head1[u]=tot1;
}
void add_edge2(int pos,int k,int w)
{
e2[++tot2].k=k;
e2[tot2].w=w;
e2[tot2].get=head2[pos];
head2[pos]=tot2;
}
void dfs(int u,int fa)
{
for(int i=1;i<=20;i++)
{
f[u][i]=f[f[u][i-1]][i-1];
mn[u][i]=min(mn[u][i-1],mn[f[u][i-1]][i-1]);
}
for(int i=head2[u];i;i=e2[i].get)
{
int v=e2[i].k;
int tmp=u,minn=1e18;
for(int j=20;j>=0;j--)
{
if(v>=(1<<j))
{
minn=min(minn,mn[tmp][j]);
v-=(1<<j);
tmp=f[tmp][j];
}
}
dp[u]=min(dp[u],e2[i].w+minn);
}
for(int i=head1[u];i;i=e1[i].next)
{
int v=e1[i].to;
if(fa==v) continue;
f[v][0]=u;
mn[v][0]=dp[u];
dfs(v,u);
}
}
signed main()
{
memset(dp,0x3f3f3f,sizeof dp);
n=read(),m=read();
for(int i=1;i<n;i++)
{
int u=read();
int v=read();
add_edge1(u,v);
add_edge1(v,u);
}
for(int i=1;i<=m;i++)
{
int pos=read();
int k=read();
int w=read();
add_edge2(pos,k,w);
}
dp[1]=0;dfs(1,0);
T=read();
while(T--){int a=read();printf("%d\n",dp[a]);}
return 0;
}