思路：

先判断能不能一次整好跳过去，如果可以，输出1。
如果不能一次整好跳到，就用最长的跳。两次最长的可以跳到 0 到 最长距离中间的任何一个距离。
跳的次数等于：（x + max(a) - l） / max(a)。 (x / l 向上取整)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n, x;
        cin >> n >> x;
        int l = 0;
        int res = 0;
        for(int i = 0; i < n; i++) 
        {
            int temp;
            cin >> temp;
            if(x == temp) res = 1;
            l = max(l, temp);
        }

        if(res == 1)
        {
            cout << res << endl;
            continue;
        }

        res = 2;
        res = max(res, (x + l - 1) / l);

        cout << res << endl;
    }
}

• 因为 n 为偶数， 可以两两分成一组。

• 假设一组的数是 x, y。 则 -y,x 与 这一组的对应位置乘积之和一定为 0 ，即： -y * x + y * y 一定为 0.

• 所以根据 a 的每个分组分组，就能构造出 b 。 b[i] = -a[i +1], b[i +1] = a[i].

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int a[N], b[N];

int n;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];

        for(int i = 1; i <= n; i += 2)
        {
            b[i + 1] = a[i];
            b[i] = - a[i + 1];
        }
        for(int i = 1; i <= n; i++) cout << b[i] << " ";
        cout << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int a[N], b[N], c[N];

int p[N];
int n;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i = 1; i <= n; i++)
        {
            cin >>a[i];
        }
        for(int i = 1; i <= n; i++)
        {
            cin >> b[i];
        }
        for(int i = 1; i <= n; i++)
        {
            cin >> c[i];
        }

        for(int i = 1; i <= n; i++)
        {   if(i == 1) p[i] = a[i];//第一个直接放就行
            else if(i > 1 && i != n)
            {
                if(p[i - 1] != a[i]) p[i] = a[i];//试着放 a[i]
                else if(p[i - 1] != b[i]) p[i] = b[i];//a[i] 不行放 b[i]
                else p[i] = c[i];//b[i] 不行放 c[i]
            }
            else 
            {

                p[i] = a[i];//最后一个需要和倒数第二个和第一个同时不相等

                if(p[i] == p[1] || p[i] == p[i - 1]) 
                {
                    p[i] = b[i];
                    if(p[i] == p[1] || p[i] == p[i - 1])p[i] = c[i];
                }

            }
        }
        for(int i = 1; i <= n; i++)
        {
            cout << p[i] << " "; 
        }
        cout <<endl;
    }
}

题目解析：

• 如果 a[i] 等于 k，就把 a[i] 和 a[i] 前面一共 k 个数变为 1。

解题思路：

• 从后往前扫描数组，用 l 保存能从 1 到扫描位置能变为 1 的区间。

• 不断向前扫描，更新 l， 并且判读扫描到位置能否变为 1，如果可以，就变为1。

• 输出结果

复杂度：扫描一次数组，O(n).

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2 * 10e5 + 10;

int a[N];

int n;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];

        int l = N;
        for(int i = n; i >= 1; i--)
        {
            l = min(l, i - a[i] + 1);//更新边界
            if(l <= i) a[i] = 1;//i 在边界内，就更新元素
        }

        for(int i = 1; i <= n; i++) cout << a[i] << " ";
        cout << endl;
    }
    return 0;
}

问我为什么？

好听点就是直觉，

说实话就是蒙的.

对不对不知道，不过ac了

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int l, r;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> l >> r;

        int a = r + 1;
        if(l >= (a + 1) / 2) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

• a 升序

• b 降序

• 对应位置元素求和判断

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50;

int a[N], b[N];

int n, x;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n >> x;
        for(int i = 0; i < n; i++) cin >> a[i];
        for(int i = 0; i < n; i++) cin >> b[i];
        sort(a, a + n);//测试用例不严谨，a不排序也能过，hh
        sort(b, b + n, greater<int>());

        int flag = 1;
        for(int i = 0; i < n; i++)
        {
            if(a[i] + b[i] > x) 
            {
                flag = 0;
                break;
            }
        }
        if(flag == 1) cout << "Yes" << endl;
        else cout <<"No" << endl;
    }

    return 0;
}

证明，贪心题靠的就是直觉，

思路：四个角涂与不涂分为16种情况讨论

• 用 0 表示角不涂颜色， 1 表示涂颜色。四个角分别是 d1 d2 d3 d4.

• 需要涂的个数 - 对应角上涂的个数 如果 大于等于 0 且 小于等于 n - 2, 则是一种方案。(去除角后，一条边还剩 n - 2 个格子)

• 枚举4个角的所以情况：0000 — 1111 16种分别判断，有一种符合判定条件，就输出 YES.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n;
        int u, r, d, l;
        cin >> u >> r >> d >> l;
        int flag = 0;
        for(int  i = 0; i < 1 << 4; i++)//16中情况
        {
            int d1, d2, d3, d4;//4个角
            d1 = i & 1;
            d2 = (i >> 1 & 1);
            d3 = (i >> 2 & 1);
            d4 = (i >> 3 & 1);

            //判定条件
            if(u - d1 - d2 >= 0 && u - d1 - d2 <= n - 2 && r - d2 - d3 >= 0 && 
            r - d2 - d3 <= n - 2 && d - d4 - d3 >= 0 && d - d4 - d3 <= n - 2 && l - d4 - d1 >= 0 && l - d4 - d1 <= n - 2)
            {
                flag = 1;
                break;
            }
        }
        if(flag == 1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

分析：

• 题目翻译一下就是：把原来的数组分成两个数组，取划分后两个数组中不存在的最小的非负数。

• 再翻译一下就是：把原来的数组划分成两个数组，第一个是 a1, 第二个是 a2, 每个数组中第一次出现 元素值与下标值不等 的时候，下标值就是mex 的值。

解题思路：

模拟构造两个数组，找出每个数组的 mex 值，求和后输出。

#include <iostream>
#include <cstring>
#include <algorithm>

#include <unordered_map>

using namespace std;

unordered_map<int, int> h;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        for(int i = 0; i <= 100; i++)
        {
            h[i] = 0;
        }
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++)
        {
            int x;
            cin >> x;
            h[x] ++;
        }
        int a1 = 0, a2 = 0;
        for(int i = 0; i <= 100; i++)//模拟构造第一个连续数组。
        {
            if(h[i] >= 1)
            {
                h[i]--;
            }
            else
            {
                a1 = i;
                break;
            }
        }
        for(int i = 0; i <= 100; i++)//模拟构造第二个连续数组
        {
            if(h[i] >= 1)
            {
                h[i]--;
            }
            else
            {
                a2 = i;
                break;
            }
        }
        cout << a1 + a2 << endl;
    }
    return 0;
}

注意：问的是回文子序列，不是子串。

长度大于等于3的回文子序列 等价于 两个相等的元素位置之差大于1

所以：遍历数组，找出两个相等的元素。如果位置之差大于1就输出 YES。

如果遍历完数组，也没找到，就输出 NO。

当然也可以用哈希表记录下元素出现的位置，在 O(N) 时间内过掉。这个方法可以看看其他题解。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010;
int a[N];
int n;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        int flag = 0;
        for(int i = 1; i <= n; i++)//遍历数组
        {
            for(int j = n; j > i; j--)
            {
                if(a[i] == a[j])//发现相等的元素
                {
                    if(j - i + 1 >= 3)//判断位置之差
                    {
                        flag = 1;
                        break;
                    }
                }
            }
            if(flag == 1) break;
        }

        if(flag == 1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

分析下可以知道，移动的次数就是第一个1和最后1个1中间 0 的个数。

例如 0 0 1 0 0 1 0 0 1 0 ,第一个1 和最后一个 1 中有4个 0 ，所以答案是 4

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 55;
int a[N];
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;

        int cnt1 = 0;//记录1 的个数
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i];
            if(a[i] == 1) cnt1++;
        }

        int i = 1, j = n;
        while(a[i] == 0) i++;//第一个1的位置
        while(a[j] == 0) j--;//最后一个1的位置

        cout << j - i + 1 - cnt1 << endl;//第一个1和最后一个1中间0的个数就是答案
    }
}