Lorenzo Von Matterhorn

code

6 年前

时间： 1ms 内存：128M

描述：

Barney住在纽约。纽约市有无限数量的路口，路口为从1开始编号的正整数。在路口i和2*i以及i和2*i +1之间存在双向道路,您可以清楚地看到任意两个路口之间存在唯一的最短路径。

最初任何人都可以免费通过所有道路。但是由于SlapsGiving领先于我们，很快就会有q个连续事件发生。有两种类型的事件：

1.政府制定新规则。规则可以用整数v，u和w表示。作为这一行动的结果，从u到v的最短路径上的所有道路的通过费用增加了w美元。

2. Barney从路口v移动到路口u那里是他想拥抱的一个女孩。他总是使用两个十字路口之间的最短路径（访问最小数量的交叉路口或道路）。

政府需要你的计算。每次Barney去拥抱一个女孩时，他应该支付多少钱

输入：

输入的第一行包含一个整数q（1≤q≤1 000）。

下面q行按时间顺序包含有关事件的信息。每个事件的形式描述

1 v u w如果当政府提出一个新的规则有关从增加从u到v的最短路径上的所有道路的通过费w美元。

2 v u当Barney从路口v到路口u拥抱一个女孩。

1≤v，u ≤10^18，v ≠ u，1≤ w ≤10^9

输出：

对于第二类事件，按相应事件的时间顺序在一行中打印Barney道路的通行费总和。

示例输入：

示例输出：

94
0
32

提示：

参考答案（内存最优[1216]）：

#include<stdio.h>
long long int n;
typedef struct{
	long long int l,r;
	long long int weight;
}stu;
stu a[4100];
long long int top;
long long int see(long long int u,long long int v)
{
	while(u!=v)
	{
		if(u>v)
		{
			u/=2;
		}
		else
		{
			v/=2;
		}
	}
	return u;
}
long long int search(long long int f1,long long int c1,long long int f2,long long int c2)
{
	long long int sum=0;
	long long int mc=see(c1,c2);
	while(mc>f1&&mc>f2)
	{
		sum++;
		mc/=2;
	}
	return sum;
}
int main()
{
	scanf("%lld",&n);
	for(long long int i=0;i<n;i++)
	{
		long long int sta; 
		long long int u,v,w;
		scanf("%lld",&sta);
		if(sta==1)
		{
			scanf("%lld %lld %lld",&u,&v,&w);
			long long int temp=see(u,v);
			if(u!=temp)
			{
				a[top].l=temp;//Í· 
				a[top].r=u;
				a[top].weight=w;
				top++;
			}
			if(v!=temp)
			{
				a[top].l=temp;
				a[top].r=v;
				a[top].weight=w;
				top++;
			}
		}
		else
		{
			scanf("%lld %lld",&u,&v);
			long long int mid=see(u,v);
			long long int sum=0;
			if(u!=mid)
			for(long long int i=0;i<top;i++)
			{
				sum+=search(mid,u,a[i].l,a[i].r)*a[i].weight;
			}
			if(v!=mid)
			for(long long int i=0;i<top;i++)
			{
				sum+=search(mid,v,a[i].l,a[i].r)*a[i].weight;
			}
			printf("%lld\n",sum);
		}
	}
}

参考答案（时间最优[34]）：

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<k;i++)
#define per(i,j,k) for(int i=j;i<=k;i++)
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
map <ll,ll> mp;

void swap(ll &a, ll &b)
{
   ll c;
   c=a;
   a=b;
   b=c;
}
void updateL(ll v,ll u ,ll w)
{
   while(v!=u)
   {
      if(v<u)
         swap(v,u);
      mp[v]+=w;
      v>>=1;
   }
}
void get_ans(ll v,ll u)
{
   ll ans = 0;
   while(v!=u)
   {
      if(v<u)
         swap(v,u);
      ans += mp[v];
      v>>=1;
   }
   printf("%lld\n",ans);
}
int main(void)
{
   int n;
   scanf("%d",&n);
   ll v,u,w;
   int op;
   while(n--)
   {
      scanf("%d",&op);
      if(op&1)
      {
         scanf("%lld%lld%lld",&v,&u,&w);
         updateL(v,u,w);
      }
      else
      {
         scanf("%lld%lld",&v,&u);
         get_ans(v,u);
      }
   }
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。