怎么看网站哪个公司做的,想找个专业做网站公司,wordpress主题个人博客,一级建造师报名官网入口正题
题目链接:https://www.luogu.com.cn/problem/AT5160 题目大意
给出两个长度为nnn的环序列aaa和bbb#xff0c;每次你可以让aaa中的一个数变为它和相邻两个的和。
求最少的步数将aaa变为bbb。 1≤n≤105,1≤ai,bi≤1091\leq n\leq 10^5,1\leq a_i,b_i\leq 10^91≤n≤10…正题
题目链接:https://www.luogu.com.cn/problem/AT5160 题目大意
给出两个长度为nnn的环序列aaa和bbb每次你可以让aaa中的一个数变为它和相邻两个的和。
求最少的步数将aaa变为bbb。
1≤n≤105,1≤ai,bi≤1091\leq n\leq 10^5,1\leq a_i,b_i\leq 10^91≤n≤105,1≤ai,bi≤109 解题思路
被蓝题D烂了。
考虑反过来做每次操作为BiBi−Bi−1−Bi1B_iB_i-B_{i-1}-B_{i1}BiBi−Bi−1−Bi1。
然后考虑怎么搞这个东西注意到BiB_iBi不能够减到负数所以同理也不能减到小于AiA_iAi考虑如果对于一个Bi≥Bi−1Bi1B_i\geq B_{i-1}B_{i1}Bi≥Bi−1Bi1那么此时位置i−1i-1i−1和i1i1i1显然都是不能动的那么我们动BiB_{i}Bi就一定是最优的。
还有如果BiAiB_iA_iBiAi时那么BiB_iBi就是不可以再操作的了。
具体地我们每次找到最大的可操作的BiB_iBi然后把它减到不能再减即可然后过程中判断是否无解即可。
由于每次至少减半所以每个数应该会操作最多logloglog次。
时间复杂度O(nlognlogw)O(n\log n\log w)O(nlognlogw) code
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
const ll N2e510;
ll n,a[N],b[N],ans;
priority_queuepairint,int q;
ll pl(ll x){return (x1)?n:(x-1);}
ll pr(ll x){return (xn)?1:(x1);}
signed main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,a[i]);for(ll i1;in;i){scanf(%lld,b[i]),q.push(mp(b[i],i));if(a[i]b[i])return puts(-1)0;}while(!q.empty()){ll xq.top().second;q.pop();if(b[x]a[x])continue;ll db[pl(x)]b[pr(x)];if(b[x]-da[x])break;ans(b[x]-a[x])/d;b[x]-(b[x]-a[x])/d*d;if(b[x]!a[x])q.push(mp(b[x],x));}if(q.size())puts(-1);else printf(%lld\n,ans);return 0;
}
