Gym 100541 D. Treasure Box 循环(散乱的前缀+循环体)

Source

UESTC 2016 Summer Training #13 Div.2

Gym 100541D

My Solution

在纸上写几组数据， 发现当k一定大以后就会出现循环， 这可以归类于 循环(散乱的前缀+循环体) 哈哈

Hash[x]  表示但值为 x 时 增加的值

先全部初始化为 -1, 但 x 再次出现时说明开始循环了

找到周期， 然后一次性处理掉在周期内的， 然后处理剩余部分

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e3 + 8;

LL Hash[maxn], Hashi[maxn];

inline LL mod(LL x)
{
    return x - x/100*100;
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    #endif // LOCAL
    int T;
    LL n, k, x, add, i;
    scanf("%d", &T);
    while(T--){
        memset(Hash, -1, sizeof Hash);
        memset(Hashi, 0, sizeof Hashi);
        add = 0;

        scanf("%I64d%I64d", &n, &k);
        x = mod(n);

        for(i = 1; i <= k; i++){
            add += x;
            if(Hash[x] != -1){   //找到周期 (i - Hashi[x])
                add += ((k - i)/(i - Hashi[x]))*(add - Hash[x]);
                i += ((k - i)/(i - Hashi[x]))*(i - Hashi[x]);
                x = mod(x * 2);
                break;
            }
            else{
                Hash[x] = add;
                Hashi[x] = i;
                x = mod(x * 2);
            }
        }
        //处理剩余部分
        for( ; i < k; i++){
            add += x;
            x = mod(x * 2);
        }
        printf("%I64dn", n + add);


    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx