先尝试着写暴力，再看看能不能优化

AcWing 1210. 连号区间数

AcWing 1236. 递增三元组
AcWing 1245. 特别数的和
AcWing 1204. 错误票据
AcWing 466. 回文日期
AcWing 787. 归并排序
AcWing 1219. 移动距离
AcWing 1229. 日期问题
AcWing 1231. 航班时间
AcWing 1241. 外卖店优先级
AcWing 788. 逆序对的数量

1.连号区间数

暴力枚举区间的左右断点[i, j]，然后加上一个巧妙的判断是否为连号区间的方式

j - i = max - min

还有一个技巧，在遍历j的同时更新max和min，这样可以大大节省消耗的时间

//连号区间数
//枚举做右端点[i,j]，但是要做优化，一个巧妙的判断方式
#include<bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

int n;
int a[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    long long res = 0;
    for(int i = 0; i < n; i++)
    {
        int maxv = -1e9, minv = 1e9;
        for(int j = i; j < n; j++)
        {
            maxv = max(maxv, a[j]);
            minv = min(minv, a[j]);
            if(maxv - minv == j - i) res++;
        }
    }
    cout << res << endl;

    return 0;
}

2.递增三元组

这道题目经过分析，不难看出可以枚举B中所有元素，然后使用二分查找的方式在A和C中查找符合要求的元素的个数，这样一来，时间复杂度为 $O(nlogn + n(logn)^2)=O(n(logn)^2)$ ，是可以过掉这道题目的，二分根据模板写就行了，还是很简单的。

如果这道题目就这样，只能说一般般，但是这道题目竟然可以使用前缀和求解！！,构造方式十分巧妙！

//递增三元组
//二分查找求解
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

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

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++) scanf("%d", &b[i]);
    for(int i = 0; i < n; i++) scanf("%d", &c[i]);

    sort(a, a + n);
    sort(c, c + n);

    long long res = 0;
    for(int i = 0; i < n; i++)
    {
        int t = b[i];

        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(a[mid] < t) l = mid;
            else r = mid - 1;
        }
        if(a[l] >= t) continue;
        int sza = l + 1;

        l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(c[mid] > t) r = mid;
            else l = mid + 1;
        }
        if(c[l] <= t) continue;
        int szc = n - 1 - l + 1;
        res += (long long) szc * (long long) sza;
    }
    cout << res << endl;

    return 0;
}

前缀和解法

//递增三元组
//前缀和解法
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N], b[N], c[N]; // 原始数组
int cnt_a[N], cnt_c[N];//数量数组
int sa[N], sc[N];// 数量数组的前缀和

int main()
{
    cin >> n;
    //注意要把所有数据+1，因为原始数据有0存在
    for(int i = 1; i <= n; i++) cin >> a[i], cnt_a[++a[i]]++;
    for(int i = 1; i <= n; i++) cin >> b[i], b[i]++;
    for(int i = 1; i <= n; i++) cin >> c[i], cnt_c[++c[i]]++;

    for(int i = 1; i <= 1e5 + 1; i++)
    {
        sa[i] = sa[i - 1] + cnt_a[i];
        sc[i] = sc[i - 1] + cnt_c[i];
    }

    long long res = 0;
    for(int i = 1; i <= n; i++)
    {
        int t = b[i];

        res += (long long)sa[t - 1] * (sc[100001] - sc[t]);
    }
    cout << res << endl;

    return 0;
}

3.特别数的和

这道题目明显是道送分题，没啥好说的，对每个数字求出它的所有数位的大小判断即可

//特别数的和
#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        int t = i;
        while(t)
        {
            int x = t % 10;
            t /= 10;
            if(x == 2 || x == 0 || x == 1 || x == 9)
            {
                res += i;
                break;
            }
        }
    }
    cout << res << endl;
    return 0;
}

4.错误票据

//错误票据
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N];

int main()
{
    int x, i = 0;
    cin >> x;//过滤
    while(cin >> x) a[i++] = x;

    int len = i;//表示数组长度

    sort(a, a + len);

    int n, m;
    for(int i = 1; i < len; i++)
    {
        if(a[i] == a[i - 1]) n = a[i];//重号ID
        else if(a[i] >= a[i - 1] + 2) m = a[i] - 1;//断号ID
    }

    cout << m << " " << n << endl;
    return 0;
}

5.回文日期

学习了判断日期的简洁的写法

另外，对于本问题，有三种考虑方式：

• 枚举合法日期，判断是不是回文串（第一种做法）
• 枚举数字，判断是不是合法日期，是不是回文串（会超时，未展示）
• 枚举回文串，判断是不是合法日期（第二种做法）

第一种做法【枚举合法日期】

//回文日期
#include<bits/stdc++.h>

using namespace std;

bool is30month(int month)
{
    return month == 2 || month == 4 || month == 6 || month == 9 || month == 11;
}

bool isRun(int year)
{
    if(year % 4 == 0 && year % 100 != 0) return true;
    if(year % 400 == 0) return true;
    return false;
}

int get_next(int x)
{
    int day = x % 100;
    x /= 100;
    int month = x % 100;
    x /= 100;
    int year = x;

    day++;
    if(day == 29 && !isRun(year) && month == 2) 
    {
        month++;
        day = 1;
    }
    if(day == 30 && isRun(year) && month == 2)
    {
        month++;
        day = 1;
    }
    if(day == 31 && is30month(month)) 
    {
        month++;
        day = 1;
    }
    if(day == 32 && !is30month(month)) 
    {
        month++;
        day = 1;
    }

    if(month == 13) 
    {
        month = 1;
        year++;
    }
    return year * 10000 + month * 100 + day;
}

bool isHuiWen(int x)
{
    int backup = x, t = 0;
    while(x)
    {
        t = t * 10 + (x % 10);
        x /= 10;
    }
    return t == backup;
}

int main()
{
    int st, ed;
    cin >> st >> ed;

    int res = 0;
    for(int i = st; i <= ed; i = get_next(i))
    {
        if(isHuiWen(i)) res++;
    }
    cout << res << endl;

    return 0;
}

第二种做法【枚举回文串 $O(10^4)$ 】

//回文日期
#include<bits/stdc++.h>

using namespace std;

int months[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

bool check(int date)
{
    int year = date / 10000;
    int month = date % 10000 / 100;
    int day = date % 100;

    if(month == 0 || month > 13) return false;

    if(day == 0) return false;

    if(month != 2 && day > months[month]) return false;

    if(month == 2)
    {
        bool leap = year % 4 == 0 && year % 100 != 0 || year % 400 == 0;
        if(leap && day > 29) return false;
        if(!leap && day > 28) return false;
    }

    return true;
}

int main()
{
    int date1, date2;
    cin >> date1 >> date2;

    int res = 0;
    for(int i = 0; i < 10000; i++)
    {
        int x = i, r = i;
        for(int j = 0; j < 4; j++) r = r * 10 + x % 10, x /= 10;

        if(r >= date1 && r <= date2 && check(r)) res++;
    }

    cout << res << endl;
    return 0;
}

6.归并排序

经典模板，不多说了

//归并排序
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n;
int q[N], tmp[N];

void merge_sort(int q[], int l, int r)
{
    if(l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q,l, mid), merge_sort(q, mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(int i = l, k = 0; i <= r;i++,k++)
        q[i] = tmp[k];
    return;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> q[i];

    merge_sort(q, 0, n - 1);

    for(int i = 0; i < n; i++) cout << q[i] << " ";
    cout << endl;

    return 0;
}

7.移动距离

其实就是个坐标变换公式，注意把下标变成从0开始会更容易处理

//移动距离
//找规律，坐标变换
#include<bits/stdc++.h>

using namespace std;

int main()
{
    int w, m, n;
    cin >> w >> m >> n;
    m--, n--;

    int x1 = m / w, y1 = m % w;
    if(x1 % 2 != 0) y1 = w - 1 - y1;

    int x2 = n / w, y2 = n % w;
    if(x2 % 2 != 0) y2 = w - 1 - y2;

    cout << abs(x1 - x2) + abs(y1 - y2) << endl;

    return 0;
}

8.日期问题

注意printf的一些用法

printf("%2d", a);//打印a，如果位数不够则用空格补位
printf("%02d", a);//打印a，如果位数不够则用0补位

#include<bits/stdc++.h>

using namespace std;

int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

bool check_valid(int year, int month, int day)
{
    if(month == 0 || month > 12) return false;
    if(day == 0) return false;
    if(month != 2)
    {
        if(day > days[month]) return false;
    }
    else
    {
        int leap = year % 100 != 0 && year % 4 == 0 || year % 400 == 0;
        if(day > 28 + leap) return false;
    }
    return true;
}

int main()
{
    int a, b, c;
    scanf("%d/%d/%d", &a, &b, &c);

    for(int date = 19600101; date <= 20591231; date++)
    {
        int year = date / 10000, month = date % 10000 / 100, day = date % 100;
        if(check_valid(year, month, day))
        {
            if(year % 100 == a && month == b && day == c
            || month == a && day == b && year % 100 == c
            || day == a && month == b && year % 100 == c
            )
                printf("%02d-%02d-%02d\n",year, month, day);
        }
    }
    return 0;

}

9.航班时间

两次时间差相加，就会把时差变量消去，也就是最终结果与时差无关
$$ time = (t1 + t + t2 - t)/2 = (t1 + t2) / 2 $$
这道题目的重点在于字符串的处理方式

要记住sscanf、printf("%02d",a)、cin.peek()这几个函数的使用方法

string str;
sscanf(str.c_str(), "%d:%d:%d", &a, &b, &c);
printf("%02d", a);
char c = cin.peek();//查看下一个字符，只是看看不取出
string line;
getline(cin , line);//会读取空格，要过滤掉上一行的空格

代码1

//航班时间
#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int t[5];
        for(int i = 1; i <= 4; i++)
        {
            string str;
            cin >> str;
            int h,m,s;
            sscanf(str.c_str(), "%d:%d:%d", &h, &m, &s);
            t[i] = h * 3600 + m * 60 + s;
            if(i % 2 == 0)
            {
                if(cin.peek() == '\n') continue;
                else 
                {
                    cin >> str;
                    t[i] += 60 * 60 * 24 * (str[2] - '0');
                }
            }
        }

        int res = (t[4] - t[3] + t[2] - t[1]) / 2;
        int h = res / 3600, m = res % 3600 / 60, s = res % 60;
        printf("%02d:%02d:%02d\n",h,m,s);
    }
    return 0;
}

代码2

//航班时间
#include<bits/stdc++.h>

using namespace std;

int get_seconds(int h, int m, int s)
{
    return h * 3600 + m * 60 + s;
}

int get_time()
{
    string line;
    getline(cin, line);

    if (line.back() != ')') line += " (+0)";

    int h1, m1, s1, h2, m2, s2, d;
    sscanf(line.c_str(), "%d:%d:%d %d:%d:%d (+%d)", &h1, &m1, &s1, &h2, &m2, &s2, &d);

    return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + d * 24 * 3600;
}

int main()
{
    int n;
    cin >> n;
    string line;
    getline(cin, line);
    while(n --)
    {
        int time = (get_time() + get_time()) / 2;
        int h = time / 3600, m = time % 3600 / 60, s = time  % 60;
        printf("%02d:%02d:%02d\n", h, m, s);
    }

    return 0;
}

10.外卖店优先级

首先，观察输入数据，发现这些订单是无顺序的，我们第一步就需要对这些订单按照时间排序，然后按照时间从小到大的顺序处理。那么接下来的问题就是如何按照时间排序，并且同时处理一个时刻的所有订单？

直接模拟

在AcWing卡最后一组数据，在蓝桥杯评测系统可以AC

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 1e5 + 10;

int n, m, t;
int store[N];//存储店铺的优先级
vector<int> order[N];//存储订单

int st[N];//每一轮都进行一次判断
bool pro[N];

int main()
{
    cin >> n >> m >> t;

    while(m--)
    {
        int ts, id;
        cin >> ts >> id;
        order[ts].push_back(id);
    }

    for(int i = 1; i <= t; i++)
    {
        memset(st, 0, sizeof st);

        vector<int> &u = order[i];

        for(auto x : u)
        {
            store[x] += 2;
            if(store[x] > 5) pro[x] = true;
            st[x] = 1;
        }
        for(int i = 1; i <= n; i++)
        {
            if(st[i] == 0 && store[i] > 0) 
            {
                store[i] -= 1;
                if(store[i] <= 3) pro[i] = false;
            }
        }
    }

    int res = 0;
    for(int i = 1; i <= n; i++)
        res += (pro[i] == true);
    cout << res << endl;

    return 0;
}

优化

双指针，对于所有连续的没有订单的时间连在一起统一操作

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 1e5 + 10;

int n, m, T;
int score[N], last[N];

bool st[N];

PII order[N];

int main()
{
    cin >> n >> m >> T;

    for(int i = 0; i < m; i++)
    {
        cin >> order[i].first >> order[i].second;
    }

    sort(order, order + m);

    //枚举一下每个订单
    for(int i = 0; i < m;)
    {
        int j = i;
        while(j < m && order[j] == order[i]) j++;
        int t = order[i].first, id = order[i].second, cnt = j - i;
        i = j;

        score[id] -= t - last[id] - 1;
        if(score[id] < 0) score[id] = 0;
        if(score[id] <= 3) st[id] = false;//t时刻之前

        score[id] += cnt * 2;
        if(score[id] > 5) st[id] = true;

        last[id] = t;
    }

    for(int i = 1; i <= n; i++)
    {
        if(last[i] < T)
        {
            score[i] -= T - last[i];
            if(score[i] <= 3) st[i] = false; 
        }
    }

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

12.逆序对的数量

模板题

//逆序对的数量
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n;
int q[N], tmp[N];

LL merge_sort(int l, int r)
{
    if(l >= r) return 0;

    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r)
    {
        if(q[i] > q[j]) 
        {
            res += mid - i + 1;
            tmp[k++] = q[j++];
        }
        else if(q[i] < q[j])
        {
            tmp[k++] = q[i++];
        }
        else
        {
            tmp[k++] = q[i++];
        }
    }
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(int i = l, k = 0; i <= r; i++, k++)
    {
        q[i] = tmp[k];
    }

    return res;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> q[i];

    cout << merge_sort(1, n) << endl;

    return 0;
}