Codeforces Round #525 (Div. 2)题解

题解 CF1088A 【Ehab and another construction problem】

依据题意枚举即可

# include <bits/stdc++.h>

int main()

{

    int x;

    scanf("%d", &x);

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

        for(int j = 1; j <= x; j++)

            if((i % j == 0) && (j * i > x) && ((i / j) < x))

                return 0 * printf("%d %d\n", i, j);

    printf("-1");

    return 0;

}

题解 CF1088B 【Ehab and subtraction】

这种题一上来先排序啊

然后就开始操作了

对于每一次操作，找到第一个\(\geq\)当前已经减去的数的数\(a_i\)，把它减去当前已经减去数的值\(now\),然后把now更新为\(a[i]\),最后再二分（所以知道为什么要排序了吧）找下一个大于\(now\)的数，如果这个位置越界了之后就都输出\(0\)

如果还不理解就看代码

# include <bits/stdc++.h>

# define ll long long

ll a[100010];

int main()

{

    ll n, k;

    ll now = 0, pos = 1;

    scanf("%I64d%I64d", &n, &k);

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

        scanf("%I64d", &a[i]);

    std::sort(a + 1, a + n + 1);

    a[n + 1] = 0x7f7f7f7f7f7f7f;

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

    {

        if(pos == n + 1)

        {

            printf("0\n");

            continue;

        }

        printf("%I64d\n", a[pos] - now);

        now += a[pos] - now;

        ll l = pos + 1, r = n + 1;

        while(l < r)

        {

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

            if(a[mid] > now)

                r = mid;

            else l = mid + 1;

        }

        pos = l;

    }

    return 0;

}

题解 CF1088C 【Ehab and a 2-operation task】

怎么把一个序列弄成单调递增的呢？当然是把它搞成\(1 \cdots n\)啦

我们显然可以找到这样一种构造

• 对于每个数\(a_i\)，通过\(\mod a_i - i + 1\)让它变成\(i\)

这样有一个漏洞：当前的\(a_i\)小于\(i\)怎么办？

我们发现我们还有一次操作机会

所以我们把这次给\(1\)操作：把整个序列加上一个特别大的数（但要满足题目条件）

这样就刚好用了\(n+1\)次操作

# include <bits/stdc++.h>

int a[2010];

int main()

{

    int n;

    scanf("%d", &n);

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

        scanf("%d", &a[i]);

    printf("%d\n", n + 1);

    printf("1 %d %d\n", n, 899999);

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

    {

        a[i] += 899999;

        printf("2 %d %d\n", i, (a[i] - i + 1));

        a[i] %= (a[i] - i + 1);

    }

    return 0;

}