CCPC2021(Online)Rematch - E. Monopoly

E. Monopoly

题目描述

time limit per test3 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

Little Rabbit loves playing a tabletop game called Monopoly. In the game, players roll the dice to move around the game board, buying and trading properties, and developing them with houses and hotels. Players collect rent from their opponents, with the goal being to drive them into bankruptcy.

One day, Little Rabbit invites Little Horse to play the game with him, but Little Horse stands him up. As a result, Little Rabbit can only play the game on his own. After a while, Little Rabbit finds out another way to play the game.

Let’s consider the map of the game as n integers a1,a2,…,an placed in a circle. If the player lands on ai, his score will change by ai points. Specifically, if ai>0, his score will increase by |ai| points. If ai<0, his score will decrease by |ai| points. And of course, if ai=0, his score won’t change.

As there is nobody else, Little Rabbit doesn’t feel like rolling a dice. So he just moves on the map step by step. Formally, if he now lands on ai and i<n, he will move to ai+1 in the next step. If he now lands on an, he will move to a1 in the next step.

Initially, Little Rabbit has 0 points, and his first step is to land on a1. Little Rabbit wonders how many steps he should take at least to reach exactly x points. (Specifically, since his initial score is 0, he needs 0 steps to reach 0 points.)

输入描述

The first line of the input contains an integer T (1≤T≤20), indicating the number of test cases.

The first line of each test case contains two integers n and m (1≤n,m≤105), indicating the number of integers on the map and the number of queries.

The second line contains n integers a1,a2,…,an (−109≤a1,a2,…,an≤109), indicating the integers on the map.

In the next m lines, each line contains an integer x (−1012≤x≤1012), indicating a query.

It’s guaranteed that ∑n≤5×105 and ∑m≤5×105.

输出描述

For each query, output an integer in a single line, indicating the number of steps he should take at least to reach exactly x points. If it is impossible to reach exactly x points, output −1.

输入样例1：

1
3 5
1 -3 4
1
5
2
0
-10

输出样例1：

1
7
3
0
-1

题意

给定 n 个点的带权环 ，起始权值和为 0 ，从 1 号点开始走 走过便加上对应点的点权
m 次询问 给定 x 询问最小走几步能使权值和等于 x 走不到输出 -1

思路

读入时可统计出 n 个点的点权和 sum
可以根据点权和分 3 种情况
i) sum==0
显然这种情况走大于 n 步是没有意义的 故前缀和能达到 x 的最小位置则是最小步数 否则就是走不到 可以用 map 记录每个前缀和出现的最早位置

ii) sum>0
对于这种情况我们可以将 x 拆分成 x=y+ksum (k>=0) 显然我们需要最小化 k 值即使 y 尽可能取大 而走一圈权值和是递增的故 k>=0 y=x%sum 我们可以通过遍历每个位置的前缀和时 使用 map 里套一个 vector 来记录模意义下相同的 y 的不同前缀和 这里需要注意 x<0 时 y<0 统一处理为 y=y+sum 使得模数为正数 避免负数模之后找不到对应的模 sum 意义下同余的数 这样查询时我们只需要排序后二分找到一个小于等于 x 的最大前缀和 通过记录前缀和出现最早位置的 map 加上 kn 就是最小步数

iii)sum<0
对于这种情况我们只需要翻转每个 a[i] 以及查询的 x 即可转化为sum>0的情况

ps:注意位置的输出要开long long 且注意%lld

Code

#include<bits/stdc++.h>
using namespace std;
#define __T int csT;scanf("%d",&csT);while(csT--)
const int mod=998244353;
const int maxn=1e5+3;

int n,m,fz;
long long a[maxn];
long long sum,x,qz,y;
map<long long,vector<long long>> mp;
map<long long,int> wz,px;

inline void sol()
{
    mp.clear();
    wz.clear();
    px.clear();
    scanf("%d%d",&n,&m);
    sum=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    fz=0;
    if(sum<0)
    {
        fz=1;
        sum=-sum;
        for(int i=1;i<=n;++i)
        {
            a[i]=-a[i];
        }
    }
    qz=0;
    if(sum!=0)
    {
        for(int i=1;i<=n;++i)
        {
            qz+=a[i];
            mp[(qz%sum+sum)%sum].push_back(qz);
            if(wz[qz]==0)wz[qz]=i;
        }
    }
    else
    {
        for(int i=1;i<=n;++i)
        {
            qz+=a[i];
            if(wz[qz]==0)wz[qz]=i;
        }
    }
    while(m--)
    {
        scanf("%lld",&x);
        if(x==0)
        {
            puts("0");
            continue;
        }
        if(fz==1)x=-x;
        if(sum!=0)
        {
            y=x%sum;
            if(y<0)y+=sum;
            if(mp[y].size()==0)
            {
                puts("-1");
                continue;
            }
            if(px[y]==0)
            {
                px[y]=1;
                sort(mp[y].begin(),mp[y].end());
            }
            int xb=lower_bound(mp[y].begin(),mp[y].end(),x)-mp[y].begin();
            if(xb==0)
            {
                if(mp[y][xb]==x)
                {
                    printf("%lld\n",wz[mp[y][xb]]);
                }
                else puts("-1");
            }
            else
            {
                if(xb==mp[x].size())
                {
                    --xb;
                    long long st=(x-mp[y][xb])/sum*n;
                    printf("%lld\n",wz[mp[y][xb]]+st);
                }
                else
                {
                    if(mp[y][xb]==x)
                    {
                        printf("%lld\n",wz[mp[y][xb]]);
                    }
                    else
                    {
                        --xb;
                        long long st=(x-mp[y][xb])/sum*n;
                        printf("%lld\n",wz[mp[y][xb]]+st);
                    }
                }
            }
        }
        else
        {
            if(wz[x]!=0)printf("%d\n",wz[x]);
            else puts("-1");
        }
    }
}

int main()
{
    __T
        sol();
    return 0;
}