链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
凯丽王国有 nnn 座城市,每个城市都有一个能量值 viv_ivi,mmm 条单向道路连接着这些城市,但这些路不会构成环,即从任意一个城市出发,都无法回到这个城市。
而大马猴和机智羊要组队参加的下一个项目就是能量收集赛。能量收集赛的规则是:每位参赛者拿着一个能量值为 000 的水晶球,从他所在的城市出发,每经过一个他从未到达的城市,就可以收集这个城市的能量值并加入自己的能量球中,直到走到无法再走为止。
所以每个参赛者都会收集尽可能多的能量。大马猴和机智羊都很聪明,他们在研究了地图之后,各自都能找到能量最多的路线。
然而当他们完成比赛之后,他们才被告知,他们是作为小组参赛,必须交上去两个能量值一样的能量球才行。他们研究发现,只要花费 x×(x+1)xtimes(x+1)x×(x+1) 的钱,就能将能量球的能量值从 xxx 提升为 x+1x+1x+1。
鲨鱼博士想知道,如果大马猴一开始在城市 qqq,机智羊一开始在城市 ppp,那么:
输入描述:
大马猴和机智羊的成绩(刚完成比赛时)分别是多少?
为了使得他们的成绩有效,他们需要花费多少钱?
第一行包含 333 个正整数 nnn,mmm,ttt,分别表示城市的数量,单向道路的数量,询问次数。
第二行 nnn 个正整数 viv_ivi ,依次表示每个城市的能量值。
接下来 mmm 行,每行两个正整数 xix_ixi ,yi y_iyi ,表示存在一条单向道路,可以从城市 xix_ixi 出发到达城市 yiy_iyi 。
接下来 ttt 行,每行两个正整数 qqq , ppp ,表示大马猴和机智羊一开始所在的城市。
输出描述:对于每次询问,输出一行,三个整数,以空格作为分割,分别表示大马猴和机智羊刚完成比赛时的成绩,以及想要使得成绩有效,需要花费的钱。
由于答案太大,请对 109+710^9+7109+7 取模。
链接:登录—专业IT笔试面试备考平台_牛客网
输入
来源:牛客网
复制5 6 1 1 1 1 1 1 1 2 1 3 2 5 3 4 3 5 4 5 1 2
5 6 1 1 1 1 1 1 1 2 1 3 2 5 3 4 3 5 4 5 1 2输出复制4 2 18
4 2 18说明大马猴的路线为 1⇒3⇒4⇒51Rightarrow3Rightarrow4Rightarrow51⇒3⇒4⇒5,收集到的能量为 1+1+1+1=41+1+1+1=41+1+1+1=4;
机智羊的路线为 2⇒52Rightarrow52⇒5,收集到的能量为 1+1=21+1=21+1=2;
想要让两个人的能量值一样,先将机智羊的能量从 222 变为 333,即花费 2×32times32×3 的钱;再从 333 变为 444,即花费 3×43times43×4 的钱,共 2×3+3×4=182times 3+3times4=182×3+3×4=18。
示例2
输入复制8 9 2 2 2 1 2 1 3 5 2 1 2 1 3 2 4 3 4 4 5 4 7 5 8 6 3 6 4 1 6 5 5
8 9 2 2 2 1 2 1 3 5 2 1 2 1 3 2 4 3 4 4 5 4 7 5 8 6 3 6 4 1 6 5 5输出复制11 11 0 3 3 0
11 11 0 3 3 0说明对于第一次询问:
大马猴的路线为 1⇒2⇒4⇒71Rightarrow2Rightarrow4Rightarrow71⇒2⇒4⇒7,收集到的能量为 2+2+2+5=112+2+2+5=112+2+2+5=11;
机智羊的路线为 6⇒3⇒4⇒76Rightarrow3Rightarrow4Rightarrow76⇒3⇒4⇒7,收集到的能量为 3+1+2+5=113+1+2+5=113+1+2+5=11;
两个人的能量值一样,成绩有效。
对于第二次询问:
两个人的路线都为 5⇒85Rightarrow85⇒8,收集到的能量都为 1+2=31+2=31+2=3,显然成绩有效。
备注:
#includetypedef long long ll; typedef double db; using namespace std; const int mod=1e9+7; ll n,m,t; const int N=5e4+5; const int M=5e5+5; vector G[M]; ll f[M]; ll a[N]; ll dfs(ll x,ll fa) { if(f[x]) return f[x]; for(int i=0; i >n>>m>>t; for(int i=1; i<=n; i++) { cin>>a[i]; } for(int i=1; i<=m; i++) { ll x,y; cin>>x>>y; G[x].push_back(y); } for(int i=1;i<=t;i++) { ll p,q; cin>>p>>q; p=dfs(p,0); q=dfs(q,0); cout< q) swap(p,q); p--; q--; ll p1=p+1; ll p2=p+2; ll q1=q+1; ll q2=q+2; if(p%3==0)p/=3; else if(p1%3==0)p1/=3; else p2/=3; if(q%3==0)q/=3; else if(q1%3==0)q1/=3; else q2/=3; ll sum=(q2%mod*q1%mod*q%mod-p2%mod*p1%mod*p%mod+mod)%mod; cout<
#includeusing namespace std; const int N = 200010; int n, m, mod = 1e9+7; long long dp[N], cnt = 0, t, a[N], ans; vector G[N]; long long quick(long long a,long long b,long long p){ long long ans=1; while(b){ if(b&1) ans=(long long)ans*a%p; a=(long long)a*a%p; b>>=1; } return ans; } long long Dfs(int x){ if(dp[x] != -1) return dp[x]; dp[x] = a[x]; for (int j = 0; j < G[x].size(); j++){ // if(In[G[x][j]] > 1 && out[x] > 1){ dp[x] = max(dp[x], Dfs(G[x][j]) + a[x]); // } } return dp[x]; } int main(){ scanf("%d%d%d", &n, &m, &t); for (int i = 1; i <= n; i++){ scanf("%lld", &a[i]); } memset(dp, -1, sizeof(dp)); for (int i = 1; i <= m; i++){ int x, y; scanf("%d%d", &x, &y); G[x].push_back(y); } for (int i = 1; i <= n; i++){ ans = max(ans, Dfs(i)); } while(t--){ int q, p; scanf("%d%d", &q, &p); printf("%lld %lld ", dp[q], dp[p]); long long minn = min(dp[q], dp[p]); long long maxn = max(dp[q], dp[p]); long long ans1 = ((maxn-1) %mod*(maxn)%mod)%mod *(maxn +1)%mod *quick(3,mod-2,mod)%mod; long long ans2 = ((minn-1) %mod*(minn)%mod)%mod *(minn +1)%mod *quick(3,mod-2,mod)%mod; if(ans1 < ans2) ans1 += mod; long long ans = ans1 - ans2; // ans = ans * quick(3,mod-2,mod); printf("%lldn", ans); } // int ans = 0; // cout << ans << endl; return 0; } #includeusing namespace std; #define int long long #define N 500001 #define mod 1000000007 int a[N]; vector ne[N]; int ans[N],v[N]; int dfs(int x){ if(v[x]){ return ans[x]; } v[x]=1; int maxx=0; vector ne1=ne[x]; for(int i=0;i >n>>m>>t; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; ne[x].push_back(y); } for(int i=1;i<=n;i++){ if(!v[i]){ dfs(i); } } while(t--){ int p,q; cin>>p>>q; int x=ans[p],y=ans[q]; cout< y){ int t=x; x=y; y=t; } x--;y--; int sum=0; int y1=y+1,y2=y+2,x1=x+1,x2=x+2; if(y%3==0)y/=3; else if(y1%3==0)y1/=3; else y2/=3; if(x%3==0)x/=3; else if(x1%3==0)x1/=3; else x2/=3; sum=y%mod*y1%mod*y2%mod+mod-x%mod*x1%mod*x2%mod; cout<