题目一：
小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 = 8, m = 2, 数列就是: -1, -2, +3, +4, -5, -6, +7, +8.
n = 4, m = 1, 数列就是: -1, +2, -3,

  • 可以看出数列被分为n/m2部分，其中每部分的和都相等，所以题目要求的前n项和一定为每部分求和之和，即部分数每部分的和；
  • 那么每部分的和是多少呢，通过题目给出的例子可知：
    当n = 8, m = 2时，部分和为4=2的平方
    当n = 4, m = 1时，部分和为1=1的平方
    以此类推，可以得到部分和为m的平方。

所以，这道题目的最终求解就是在求m*n/2的值。

程序如下：

#include<iostream>
using namespace std;
    typedef long long LL;
int main()
{
    LL n,m;
    cin>>n>>m;
    cout<<n*m/2<<endl;
}

题目二：
牛牛和羊羊正在玩一个纸牌游戏。这个游戏一共有n张纸牌, 第i张纸牌上写着数字ai。
牛牛和羊羊轮流抽牌, 牛牛先抽, 每次抽牌他们可以从纸牌堆中任意选择一张抽出, 直到纸牌被抽完。
他们的得分等于他们抽到的纸牌数字总和。
现在假设牛牛和羊羊都采用最优策略, 请你计算出游戏结束后牛牛得分减去羊羊得分等于多少。

思路：
首先解释一下什么是最优策略：所谓最优就是当轮到自己抽牌时直接选择最大的牌。

因为是两个人是相间抽牌，并且都会抽取最大的牌，所以只需在计算前排序即可，奇数位都是牛牛的，偶数位都是羊羊的。

程序如下：

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAXN=1e5+7;
int st[MAXN] = {0};
int cmp(int a, int b)
{
 return a>b;//降序排列
}
int main()
{
 int n = 0;
 long sum1 = 0;
 long sum2 = 0;
 long dif = 0;
 scanf("%d",&n);
 for (int i = 0; i<n; i++)
 {
  scanf("%d", &st[i]);
 }
 sort(st, st + n, cmp);
 for (int i = 0; i<n;)
 {
        if(i%2==0)
            dif+=st[i];
        else
            dif-=st[i];
  i++;
 }
 printf("%ld", dif);
 return 0;
}

题目三：
小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力。

思路：

使用二分查找法，可最大限度的加快查找速度，防止超时。（二分查找的找上届和找下界需要学习一下）

程序如下：

#include<iostream>
using namespace std;
int n,m;
//计算第一天吃s个巧克力一共需要多少个多少个巧克力
int sum(int s){
    int sum=0;
    for(int i=0;i<n;i++){
        sum+=s;
        s=(s+1)>>1;//向上取整
    }
    return sum;
}
//二分查找
int fun(){
    if(n==1) return m;
    int low=1;
    int high=m;//第一天的巧克力一定是大于等于1小于等于m的
    while(low<high){
        int mid=(low+high+1)>>1;//向上取整
        if(sum(mid)==m) return mid;//如果第一天吃mid个巧克力，刚刚好吃完所有巧克力，那么直接返回
        else if(sum(mid)<m){
            low=mid;
        }else{
            high=mid-1;
        }
    }
    return high;
}
int main()
{
    cin>>n>>m;
    int res=fun();
    cout<<res<<endl;
    return 0;
}