[NOIP2013D1]

T1

Problem

洛谷

Solution

感觉我写的也不是正解。。。

我是先找出每个循环节的长度l。。。然后用快速幂求出10 ^ k % l的值。。

Code

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define ll long long

ll read()

{

    ll x = 0; int zf = 1; char ch;

    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

    if (ch == '-') zf = -1, ch = getchar();

    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();

    return x * zf;

}

ll T[1000005];

int main()

{

    ll n = read(), m = read(), k = read(), x = read();

    T[0] = x;

    int l;

    for (int i = 1; i <= n; i++)

    {

        x = (x + m) % n;

        T[i] = x;

        if (T[i] == T[0])

        {

            l = i;

            break;

        }

    }

    ll ans = 1, now = 10;

    while (k > 0)

    {

        if (k % 2 == 1) ans = ans * now % l;

        now = now * now % l;

        k /= 2;

    }

    printf("%d\n", T[ans]);

}

T2

Problem

洛谷

Solution

首先可以证明当Ai在A中大小排名和Bi在B中大小排名相等时，其差的平方时最小的。。

因此只要控制排名相等就可以了。。所以先排序，然后建立一个排名在A中和B中位置的关系。。。最后用归并排序求逆序对。。

证明（两个数）：设A中两个数a < b，B中两个数c < d

ans1 = (a - c) ^ 2 + (b - d) ^ 2 = a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2 - 2 * a * c - 2 * b * d

ans2 = (a - d) ^ 2 + (b - c) ^ 2 = a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2 - 2 * a * d - 2 * b * c

又因为a * c + b * d - a * d - b * c = (a - b) * (c - d) > 0

所以ans1 < ans2

Code

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define ll long long

ll read()

{

    ll x = 0; int zf = 1; char ch;

    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

    if (ch == '-') zf = -1, ch = getchar();

    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();

    return x * zf;

}

ll ans = 0;

int X[100005], T[100005];

struct node

{

    int val, id;

}a[100005], b[100005];

int cmp(node x, node y)

{

    return x.val < y.val;

}

void merge(int xl, int xr, int yl, int yr)

{

    int l = xl, r = yr, now = l;

    while (xl <= xr && yl <= yr)

    {

        if (X[xl] <= X[yl]) T[now++] = X[xl++];

        else

        {

            T[now++] = X[yl++];

            ans = (ans + xr - xl + 1) % 99999997;

        }

    }

    while (xl <= xr) T[now++] = X[xl++];

    while (yl <= yr) T[now++] = X[yl++];

    for (int i = l; i <= r; i++) X[i] = T[i];

}

void mergesort(int l, int r)

{

    if (l == r) return;

    int mid = (l + r) >> 1;

    mergesort(l, mid);

    mergesort(mid + 1, r);

    merge(l, mid, mid + 1, r);

}

int main()

{

    int n = read();

    for (int i = 1; i <= n; i++)

        a[i].val = read(), a[i].id = i;

    for (int i = 1; i <= n; i++)

        b[i].val = read(), b[i].id = i;

    sort(a + 1, a + n + 1, cmp);

    sort(b + 1, b + n + 1, cmp);

    for (int i = 1; i <= n; i++)

        X[b[i].id] = a[i].id;

    mergesort(1, n);

    printf("%lld\n", ans);

}