01_数对

题目描述

牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。
但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。
牛牛希望你能帮他计算一共有多少个可能的数对。

输入描述:
输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。

输出描述:
对于每个测试用例, 输出一个正整数表示可能的数对数量。

解题思路

x可以在 [1, n] 上取，但是y只能在 [k, n]上取，因为k以下都不存在大于等于k的余数。
所以遍历y，对于每一个y，统计符合的x的个数，加到count里。

先假设x可以从 [0, n]中取值，那么这段区间至少可以分成(n/k)个完整的、长度为y的区间。
x = 【0，1……y-2，y-1】【y，y+1，……，2y-2，2y-1】……【……】……【……，n】
在每个小区间a上，第i个数a[i]%y的余数是i。这样每一小段上大于等于k的x有y-k个（显然当k=0时，y个数都满足题意）。
【0，1，……，k，k+1，……，y-1】

这样，已经遍历的总数是 ，而其中满足条件的x的总数是

因为
所以还没遍历的数有 个，令它为t。

因为n%y∈[0, y-1]， 则t∈[1, y]。

也就是说我这种方法，至少剩了一个数，至多会把一个整区间（数量为y）都剩下来。
但是无论如何，这个区间last的第i个数last[i]%y一定是i。则最后一个数（n）的余数就是n%y。
如此一来，此区间内从 [k,n%y] 包含共计 n%y-k+1 个数。不过如果算出小于0的数，则不需要减回去，直接当没有就可以了。
所以最后一个区间里包含了 max(n%y-k+1, 0) 个满足条件的x。

java代码实现：

import java.util.Scanner;

    public class Main {
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long n = sc.nextInt();
    long k = sc.nextInt();
    long count = 0;
    if (k == 0) {
        count = n * n;
        //任何一数对，取余时余数必定大于等于0
    } else {
        for (long y = k + 1; y <= n; y++) {
        count += (n / y) * (y - k) + Math.max(0, n % y - k + 1);
        // 假设n=10,k=3，则对y来说只能是4,5,6,7,8,9,10
        // 当y=4,(n/y)*(y-k)代表x小于等于8(8是4的整数倍)时有(3,4),(7,4)，Math.max(0,n%y-k+1)代表x大于8时符合题意的对数为0
        // 当y=5,(n/y)*(y-k)代表x小于等于10(10是5的整数倍)时有(3,5),(4,5),(8,5),(9,5)，Math.max(0,n%y-k+1)代表x大于10时符合题意的对数为0
        // 当y=6,(n/y)*(y-k)代表x小于等于6时有(3,6),(4,6),(5,6),Math.max(0,n%y-k+1)代表x大于6时符合题意的对数为2,分别是(9,6),(10,6)
        // 当y=7,(n/y)*(y-k)代表x小于等于7时有(3,7),(4,7),(5,7),(6,7),Math.max(0,n%y-k+1)代表x大于7时符合题意的对数为1,是(10,7)
        // ...以此类推
        }
    }
    System.out.println(count);
    }
}

02_翻转数列

题目描述

小Q定义了一种数列称为翻转数列:
给定整数n和m, 满足n能被2m整除。对于一串连续递增整数数列1, 2, 3, 4..., 每隔m个符号翻转一次, 最初符号为'-';。
例如n = 8, m = 2, 数列就是: -1, -2, +3, +4, -5, -6, +7, +8.
而n = 4, m = 1, 数列就是: -1, +2, -3, + 4.
小Q现在希望你能帮他算算前n项和为多少。

输入描述:
输入包括两个整数n和m(2 <= n <= 109, 1 <= m), 并且满足n能被2m整除。

输出描述:
输出一个整数, 表示前n项和。

解题思路

首先观察数列，我们可以将一组负正的数出现（如-1，-2,3,4）看做一组，则n个数一共有n/(2m)组，而每一组求和结果为m*m，
于是得到前n项和公式为

java代码实现：

import java.util.Scanner;
public class 翻转数列 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        System.out.println(n * m / 2);
    }
}

03_纸牌游戏

题目描述

牛牛和羊羊正在玩一个纸牌游戏。这个游戏一共有n张纸牌, 第i张纸牌上写着数字ai。
牛牛和羊羊轮流抽牌, 牛牛先抽, 每次抽牌他们可以从纸牌堆中任意选择一张抽出, 直到纸牌被抽完。
他们的得分等于他们抽到的纸牌数字总和。
现在假设牛牛和羊羊都采用最优策略, 请你计算出游戏结束后牛牛得分减去羊羊得分等于多少。
输入描述:
输入包括两行。
第一行包括一个正整数n(1 <= n <= 105),表示纸牌的数量。
第二行包括n个正整数ai(1 <= ai <= 109),表示每张纸牌上的数字。
输出描述:
输出一个整数, 表示游戏结束后牛牛得分减去羊羊得分等于多少。

解题思路

牛牛和羊羊都采用最优策略！这一句很重要，说明他们每次都抽取的剩余纸牌中最大的一张。因为牛牛先抽，那么最大的必然在牛牛手里，第二大在羊羊手里，第三大又在牛牛手里，以此类推。只需要将纸牌数值组成的数组A从大到小排序，A[0]给牛牛，A[1]给羊羊，A[2]给牛牛.....将索引为偶数的项全部给牛牛,为奇数的项全部给羊羊。计算出偶数项和奇数项的差值即可。

java代码实现：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int A[] = new int[n];
    int A1[] = new int[n];
    for (int i = 0; i < n; i++) {
        A[i] = sc.nextInt();
    }
    Arrays.sort(A);
    for (int i =0; i<n; i++) {
        A1[i] = A[n-1-i];
    }
    long sum_n = 0;
    long sum_y = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
        sum_n += A1[i];
        } else
        sum_y += A1[i];
    }
        System.out.println(sum_n - sum_y);
    }
}