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

using namespace std;

const int N = 10010; // 数据总大小不超过 100 * 100 = 10000
int n,m;
int a[N];

int main()
{
    cin >> n; // 读出第一个数，没有用

    int p = 0; // 定义一个指针，起始指向a[0]位置上
    while(scanf("%d",&a[p]) != EOF) p++;

    sort(a,a + p); // 注意sort()的用法

    //调试代码    
    // for(int i = 0; i < 10; i++) cout << a[i] <<" ";
    // cout << endl;

    //遍历一遍找出缺号和重号的
    for(int i = 1 ; i < p; i++)
    {
        if(a[i] == a[i - 1]) n = a[i];
        if(a[i] == a[i - 1] + 2) m = a[i] - 1;
    }

    cout << m << " " << n << endl;

    return 0;
}

没看y总的讲解，自己写的(AC)

//思路
//1、看个位是否满足2，1，9，0；满足就加上，否则
//2、再看是十位是否满足2，1，9，0；满足就加上，否则……
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;
int n;

bool check(int i)
{
    if(i == 0) return true;
    while(i)
    {
        if(i % 10 == 1 || i % 10 == 2 || i % 10 == 9 || i % 10 == 0) return true;
        i = i / 10;
    }
    return false;
}

int main()
{
    cin >> n;

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(check(i)) ans += i;
    }

    cout << ans;

    return 0;
}

用两个数组

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

using namespace std;

const int N = 10010;

int n;
int a[N],backup[N];

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) 
    {
        scanf("%d",&a[i]);
        backup[a[i]] = i; 
    }// backup存一下a[i]的下标



    int step = 0;
    for(int i = 1; i <= n; i++)
        if(a[i] != i)
        {
            int t = backup[i]; // 保存数 i 的下标
            int temp = a[t];
            //此时backup存 i 的下标也会改变，要更新一下
            backup[i] = i;
            backup[a[i]] = t;

            a[t] = a[i];
            a[i] = temp;

            step++;
        }

/*调试*/    
    // for(int i = 1; i <= n; i++) cout << a[i] << " ";
    // cout << endl;
    // for(int i = 1; i <= n; i++) cout << backup[i] << " ";
    // cout << endl;

    printf("%d",step);

    return 0;
}

暴力方法(只能过一半的数据)

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

using namespace std;

typedef long long ll;
const int N = 10010;
int a[N],b[N],c[N];
int n;


int main()
{
    cin >> 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]);

    ll res = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            for(int k = 0; k < n; k++)
                if(c[k] > b[j] && b[j] > a[i]) res++;

    cout << res <<endl;

    return 0;
}

跟着y总写的还是不明白

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

using namespace std;

typedef long long ll;
const int N = 100010;
int n;
int a[N],b[N],c[N];
int as[N]; // as[i]表示a[]中小于 b[i] 的数的个数
int cs[N]; // cs[i]表示c[]中小于 b[i] 的数的个数
int cnt[N],s[N]; // cnt[i]用来存储数值是i的个数；s[i] 存储数值小于等于 i 的总数


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

    //as前缀和处理
    for(int i = 0; i < n; i++) cnt[a[i]]++;
    for(int i = 1; i < N; i++) s[i] = s[i - 1] + cnt[i];
    for(int i = 0; i < n; i++) as[i] = s[b[i] - 1];

    memset(cnt,0,sizeof cnt);
    memset(s,0,sizeof s);
    //cs前缀和处理
    for(int i = 0; i < n; i++) cnt[c[i]]++;
    for(int i = 1; i <= N; i++) s[i] = s[i - 1] + cnt[i];
    for(int i = 0; i < n; i++) cs[i] = s[N] - s[b[i]];

    //枚举所有的结果
    ll res = 0;
    for(int i = 0; i < n; i++) res += (ll)as[i] * cs[i];

    cout << res << endl;

    return 0;
}

二分的方法(彻彻底底的自己一点点想出来的)

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

using namespace std;

const int N = 100010;
typedef long long ll;

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

int main()
{
    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];


    sort(a+1,a+n+1); // 分别给a，c数组排序 sort()注意下表从1开始，n结束，sort要在最后一个元素的下一位！
    sort(c+1,c+n+1);


    // 调试代码
 /*   for(int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << endl;
    for(int i = 1; i <= n; i++) cout << c[i] << " ";
    cout << endl;
   */


    ll res = 0;

    for(int i = 1; i <= n; i++)
    {
        int la = 1,lc = 1,ra = n,rc = n;
        while(la < ra)
        {
            int mid = (la + ra) / 2;
            // cout << mid <<endl;
            if(a[mid] >= b[i]) ra = mid;
            else la = mid + 1;
        }
        //此时a[la] = a[ra] = 最后一个小于或等于 b[i] 的位置
        int x;
        if(a[la] >= b[i]) x = la - 1; // 此时a[la]是第一个小于等于b[i]的数，a[la]左边的数都是小于等于b[i]的 个数在数值上等于 la-1
        else x = la; // 说明a[i]中所有的数都是小于b[i]的，此时la的在数值上就等于小于b[i]的个数

        while(lc < rc)
        {
            int mid = (lc + rc + 1) / 2;
            if(c[mid] <= b[i]) lc = mid;
            else rc = mid - 1;
        }
        //此时c[lc] = c[rc] = 第一个大于或等于 b[i] 的位置
        int y;
        if(c[lc] <= b[i]) y = lc + 1;
        else y = lc;

        // 调试代码
        // cout << x << " " << y << endl;

        //由于下表有一个减一关系，la恰好就是小于b[i]的个数，
        res += (ll)x * (n - y + 1); // 注意这里x和y都是范围是0~1e5,相乘有可能爆int，先把x转成long long
    }

    cout << res << endl;

    return 0;
}

二刷前缀和法

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

using namespace std;
typedef long long ll;

const int N = 100010;
int n;
int A[N],B[N],C[N];
int AS[N]; // AS[i]表示A数组中小于b[i]的元素个数
int CS[N]; // CS[i]表示C数组中大于b[i]的元素个数
int cnt[N];// cnt[i]表示A/C数组中等于i的元素的个数，cnt[A[i]] --> 数组中A[i]的个数
int s[N];  // s[i]前缀和数组，表示cnt[]中小于等于i的个数之和

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d",&A[i]),A[i]++;
    for(int i = 0; i < n; i++) scanf("%d",&B[i]),B[i]++;
    for(int i = 0; i < n; i++) scanf("%d",&C[i]),C[i]++;
    //解释一下 上面三行+1 的操作
    //因为A[i]、B[i]、C[i]的取值范围是[0,1e5] --> 那么cnt[i]中的元素会从0开始存 --> 前缀和数组要求cnt[i]从1开始存
    //否则要额外处理越界情况，为了减少不必要的麻烦，在读入A[i],B[i],C[i]之后统一都加上一个1，即A[i]、B[i]、C[i]的取值范围是[1,1e5+1]
    //此时cnt[]的范围是[1,1e5+1] --> 保证了s[]求前缀和时，cnt[]从1开始的条件，s[i] = s[i - 1] + cnt[i]

    //先处理A[]
    for(int i = 0; i < n; i++) cnt[A[i]]++;
    for(int i = 1; i <= N; i++) s[i] = s[i - 1] + cnt[i]; // s[i] 表示小于等于i的元素个数有多少个
    for(int i = 0; i < n; i++) AS[i] = s[B[i] - 1]; // 记好AS[i]的意义

    memset(cnt, 0, sizeof cnt);
    memset(s, 0, sizeof s);

    for(int i = 0; i < n; i++) cnt[C[i]]++;
    for(int i = 1; i <= N; i++) s[i] = s[i - 1] + cnt[i];
    for(int i = 0; i <= n; i++) CS[i] = s[N] - s[B[i]]; // C[]中小于等于N的个数 - C[]中小于等于B[i]的个数 = C[]中大于等于B[i]的个数

    ll res = 0;
    //枚举每一个B[i]
    for(int i = 0; i < n; i++) res += (ll)AS[i] * CS[i];

    cout << res;

    return 0;
}

好好考虑 闫氏dp分析法

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

using namespace std;

const int N = 110;

int h[N][N],f[N][N]; // h[][]接收花生，f[][]接收所有最有情况
int n,m;

//本题用二维的dp就 可以求解 [朴素的背包问题~]

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        //读入花生的数据
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                cin >> h[i][j];

        //进行背包处理，闫氏dp分析法
        //只靠率最后面的位置(i,j) 它上面的有两种情况：[上面] =》(i - 1,j)；[左面] =》(i,j - 1);
        //那么(i,j)位置上的最大值 f[i][j] 就是 f[i - 1][j] + h[i][j] 和 f[i][j - 1] + h[i][j] 中的最大值
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                f[i][j] = max(f[i-1][j],f[i][j-1]) + h[i][j];

        cout << f[n][m] <<endl; // 记住：最大值一直在(n,m)位置上
    }


    return 0;
}

朴素背包问题写法(二维)

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

using namespace std;

const int N = 1010;

int f[N][N];
int v[N],w[N];
int n,m;
/*

f[n][m] 表示背包中放入n个物品，n个物品的体积之和为m时的最大价值

*/
int main()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++) // 物品的范围是从1到n
        for(int j = 0; j <= m ; j++) // 容量之和的范围是从0到v
        {
            f[i][j] = f[i-1][j]; // 第i个物品不放入背包时的最大价值

            if(j >= v[i])
                f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]);
                //max里面中的f[i][j] 表示上一句 第i个物品不放入背包时的最大价值；
                //      f[i - 1][j - v[i]] + w[i] 表示第i个物品放入背包时的最大价值；
        }

    cout << f[n][m] << endl; // 最大值一定在 装入n个物品，容量之和为m ==》f[n][m]

    return 0;
}

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

using namespace std;

const int N = 10010,INF = 1000000;
int n;
int a[N];

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

    int res = 0;
    for(int i = 0; i < n; i++)
    {
        int maxv = -INF,minv = INF;
        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;
}

二刷

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

using namespace std;

const int N = 10010;

int n;
int a[N];

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

    int res = 0;
    for(int i = 0; i < n; i++) // 枚举区间的左端点
    {
        int maxn = a[i],minn = a[i];
        for(int j = i; j < n; j++) // 枚举区间的右端点
        {
            maxn = max(maxn,a[j]);
            minn = min(minn,a[j]);
            if(maxn - minn == j - i) res ++; // 很巧妙的简化时间复杂度的方法，一个区间如果是连号区间 恰好等于该区间内的 最大值max-最小值min == 区间长度j - i
        }
    }

    cout << res;

    return 0;
}

关于一个数的下取整：a/b
关于一个数的上取整：
    （1）a/b上取整 = (a+b-1)/b 下取整
    （2）用(double) ceil(x)；返回x的上取整，但是一个double类型，用int()把浮点型转换成整型，但是要引入数学库<cmath>

//100 + 33(1) + 11(1) + 4 + 1 = 149
//1 每次喝完后的n个瓶盖可以换n/3瓶，剩下的瓶盖n%3瓶个
//2 （n/3 + n%3）/ 3 =  
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;
int a[N],n;

int main()
{
    cin >> n;

    a[0] = n;   // a[0] 用来存储总瓶数，a[1]...a[i]用来存储第i次的瓶盖数
    for(int i = 1; i < n; i++)
    {
        a[i] += a[i-1]/3 + a[i-1]%3; // 下一次的瓶盖数
        a[0] += a[i-1]/3;
    }

    printf("%d",a[0]);
    return 0;
}

#include <iostream>

using namespace std;

int main()
{
    int p, q;
    cin >> p >> q;
    cout << (p - 1) * (q - 1) - 1 << endl;

    return 0;
}

/*  两个互质的数p,q不能凑出的最大的数：(p - 1) * (q - 1) - 1    */