URAL 2025 Line Fighting 水题、贪心、均分

Source

UESTC 2016 Summer Training #17 Div.2

URAL 2025

My Solutiion

贪心

尽可能均摊 t = n/k;   res = n - t*k; 然后res个 t+1， n - res 个t， 然后算下就好了

复杂度 O(n)

#include 
#include 

using namespace std;
typedef long long LL;
const int maxn = 1e4 + 8;
/*
const LL Hash = 1e15 + 7;
inline LL mod(LL a)
{
    return a - (a/Hash)*Hash;
}

LL pow_mod(LL a, LL i)
{
    if(i == 0) return mod(1);
    LL t = pow_mod(a, i>>1);
    t = mod(t*t);
    if(i & 1) t = mod(t*a);
    return t;
}
*/

int val[maxn];

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    #endif // LOCAL
    LL T, n, k, t, ans, res;
    scanf("%I64d", &T);
    while(T--){
        ans = 0;
        scanf("%I64d%I64d", &n, &k);
        t = n/k;
        res = n - t*k;
        t++;
        for(int i = 1; i <= res; i++){
            ans += t*(n - i*t);
        }

        n -= res*t;
        t--;
        for(int i = res+1; i <= k; i++){
            if(i != k)ans += t*(n - (i - res)*t);
        }
        printf("%I64dn", ans);

    }
    return 0;
}

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

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx