Wannafly挑战赛7 - （B，C，E）

本文主要是介绍Wannafly挑战赛7 - （B，C，E），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

还是稍微难一点的题目有意思，B题贪心，C题概率，E题树状数组，不过E题做法应该很多

codeJan与旅行

题目描述 

第一行是一个T≤20代表测试组数。
每组第一行是三个正整数n,m,p，分别代表城市数量、codeJan想要浏览的城市数量和codeJan当前的位置(单位为米)。
第二行包含n个正整数pos[i]表示第i个城市的位置，单位为米。
输入保证pos[i]<pos[i+1](i∈[1,n−1])，并且p ≠ pos[i](i∈[1,n])。

对于每组输入数据输出一个正整数表示 codeJan 至少需要走的距离。

3 
2 2 2 
1 3 
2 2 1 
2 3 
4 3 4 
1 3 5 6

3
2
3

对于第一个样例的坐标最优移动顺序可以是：2→3→1，移动距离一共是3。
对于第二个样例的坐标最优移动顺序可以是：1→2→3，移动距离一共是2。
对于第三个样例的坐标最优移动顺序可以是：4→5→6→5，移动距离一共是3。

2≤n≤105,1≤m≤105 ，1≤p,pos[i]≤109。

题解说的很清楚：可以想象的是如果 m 足够大，codeJan 最后肯定会选择在相邻的两个城市来回走。所以可 以枚举两个相邻的城市 (实际上应该是距离最小的两个城市)。并且直接” 奔向” 这两个城市的应该是最吼的！但是 还要考虑，可能先往后退到 一个城市，再” 奔向” 枚举的城市。 举个例子就明白了：n = 3,m = 10, p = 2，三个城市的位置是 1 10 14。 那么应该先退回到 1，然后再在 10 和 14 之间来回走。  时间复杂度：O(n)

参考博客：http://blog.csdn.net/zhou_yujia/article/details/78986785，博主代码写的很巧妙，

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 100005
int n,m,p;
ll ans;
int a[M];void solve(int loc,int v) //loc是到达的第一个城市，v是起点到loc城市的距离
{int i;//如果是if(loc!=n))调用的slove函数，那么下面for循环就是先后退一步的体现for(i=loc;i>1;i--)  //向左走，loc-i+1为到城市i用的步数{if(loc-i+1>=m)break;ans=min(ans,1ll*(m-(loc-i+1))*(a[i]-a[i-1])+a[loc]-a[i]+v);}//如果是if(loc!=-1)调用的slove函数，那么下面for循环就是先后退一步的体现for(i=loc;i<n;i++) {if(i-loc+1>=m)break;ans=min(ans,1ll*(m-(i-loc+1))*(a[i+1]-a[i])+a[i]-a[loc]+v);}
}int main()
{int T,i,loc;scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&p);loc=-1;for(i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]<p)loc=i;}ans=1e18;if(m==1){if(loc!=-1) //p不在最左边ans=p-a[loc];if(loc!=n)  //p不在最右边ans=min(ans,(ll)(a[loc+1]-p));printf("%lld\n",ans);continue;}if(loc!=-1) //p不在最左边solve(loc,p-a[loc]);if(loc!=n)  //p不在最右边{if(loc==-1)  //注意此处，如果p在最左边，起点要从1开始solve(1,a[1]-p);else         //其余情况在p点右边城市作为起点solve(loc+1,a[loc+1]-p);}printf("%lld\n",ans);}return 0;
}

题目描述 

输入只有一行，包含三个整数x,y,q(0<x,y,q<10000)，分别表示氪一单能得到的宝石数、抽一次卡需要的宝石数以及抽出目标角色卡的概率p乘以10000之后的数。

输出一行，包含一个浮点数，表示抽出目标角色卡期望氪的单数，要求绝对误差或相对误差不超过 1e-9。

6480 280 98

4.921219218795631382

模拟一直抽的过程，当一直抽下去不中的概率就会为零，设置概率无穷小等价值，但概率无穷小时，结束模拟

代码：

#include<bits/stdc++.h>
#define exp 1e-40
using namespace std;
double pp=1,ans,p,num;
int tot,x,y;
int main(){scanf("%d%d%lf",&x,&y,&p);p/=10000.0;while(pp>exp) //pp是氪金到num单时仍然未中的概率,当概率不为无穷小才继续{if(tot<y){ //tot是手头宝石数int temp=(y-tot)/x; //temp氪几单能够开抽if((y-tot)%x!=0)temp++;num+=temp;tot+=temp*x;}tot-=y;        //抽一次ans+=pp*p*num; //这一抽中了，num为氪金总单数pp*=(1-p);     //仍然未中的概率}printf("%.15lf\n",ans);return 0;
}

输入描述:

第一行两个数n,m
之后一行n个数表示a
之后m行每行两个数l,r表示查询的区间

输出描述:

对于每个询问，输出一行一个数表示答案

5 7
30 60 20 20 20
1 1
1 5
2 4
3 4
3 5
2 5
2 3

30
330
160
60
120
240
100

[1,1]的子区间只有[1,1]，其gcd为30
[1,5]的子区间有：
[1,1]=30,[1,2]=30,[1,3]=10,[1,4]=10,[1,5]=10
[2,2]=60,[2,3]=20,[2,4]=20,[2,5]=20
[3,3]=20,[3,4]=20,[3,5]=20
[4,4]=20,[4,5]=20
[5,5]=20
总共330
[2,4]的子区间有：
[2,2]=60,[2,3]=20,[2,4]=20
[3,3]=20,[3,4]=20
[4,4]=20
总共160
[3,4]的子区间有：
[3,3]=20,[3,4]=20
[4,4]=20
总共60
[3,5]的子区间有：
[3,3]=20,[3,4]=20,[3,5]=20
[4,4]=20,[4,5]=20
[5,5]=20
总共120
[2,5]的子区间有：
[2,2]=60,[2,3]=20,[2,4]=20,[2,5]=20
[3,3]=20,[3,4]=20,[3,5]=20
[4,4]=20,[4,5]=20
[5,5]=20
总共240
[2,3]的子区间有：
[2,2]=60,[2,3]=20
[3,3]=20
总共100

备注:

对于100%的数据，有1 <= n , m , ai <= 100000

理解的不好，先贴上以后慢慢看。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 100005
#define mod 1000000007ll n,m,p,tot,temp;
ll a[M],gg[20],pos[20],ans[M],f[M],g[M];struct node{ll l,r,id;bool operator <(const node & obj) const{return r<obj.r;}
}q[M];ll gcd(ll a,ll b)
{return b==0?a:gcd(b,a%b);
}ll lowbit(ll x)
{return x&(-x);
}void add(ll x,ll v)
{ll i=x;while(i<=n){f[i]+=v;g[i]-=x*v;i+=lowbit(i);}
}ll sum(ll x)
{ll res=0,i=x;while(i){res+=(ll)(x+1)*f[i]+g[i];i-=lowbit(i);}return res;
}int main()
{int i,j;scanf("%lld%lld",&n,&m);for(i=1;i<=n;i++)scanf("%lld",&a[i]);for(i=1;i<=m;i++){scanf("%lld%lld",&q[i].l,&q[i].r);q[i].id=i;}sort(q+1,q+m+1);p=1;for(i=1;i<=m;i++){while(p<=q[i].r){for(j=1;j<=tot;j++)  //加入右端点的信息gg[j]=gcd(gg[j],a[p]);gg[++tot]=a[p];pos[tot]=p;temp=0;for(j=1;j<=tot;j++)  //去重if(gg[j]!=gg[j-1]){gg[++temp]=gg[j];pos[temp]=pos[j];}tot=temp;for(j=1;j<tot;j++){add(pos[j],gg[j]);add(pos[j+1],-gg[j]);}add(pos[tot],gg[tot]);add(p+1,-gg[tot]);p++;}ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);}for(i=1;i<=m;i++)printf("%lld\n",ans[i]%mod);return 0;
}

这篇关于Wannafly挑战赛7 - （B，C，E）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！