用两个数组

#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;
}

好好考虑 闫氏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;
}

关于一个数的下取整：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    */

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

using namespace std;

//思路转换：由于蚂蚁碰撞后会掉头，这里可以等价地认为继续穿过，该感染的感染，走的方向不变

const int N = 55;
int n;
int x[N];

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

    int left = 0,right = 0; // 分别表示左边向右边走的蚂蚁数量，和右边向左走的蚂蚁数量
    for(int i = 1; i < n; i++)
        if(abs(x[i]) < abs(x[0]) && x[i] > 0) left++;
        else if(abs(x[i]) > abs(x[0]) && x[i] < 0) right++;

    if(x[0] > 0 && right == 0 || x[0] < 0 && left == 0) cout << 1 <<endl;
    else cout << left + right + 1 <<endl; 
    // 为什么加1呢？？ 
          /*1表示最开始感冒的蚂蚁，
          left表示他左边向右走的，
          right表示他右边向左走的*/

    //第一个蚂蚁向右走的情况：
       1.右边向左走得到，必然会被感染
       2.右边向右走的，必然不会被感染
       3.左边向左走，必然不会被感染
       4.左边向右走：
        （1）右边存在向左走，则必然会被感染
        （2）右边不存在向左走，则必然不会被感染
}

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

using namespace std;

typedef long long ll;
const int N = 100010;
int n,k;
ll s[N]; // 存储前缀和
ll cnt[N]; // 存前缀和模k的余数

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) 
    {
        scanf("%lld",&s[i]);
        s[i] = s[i-1] + s[i];
    }

    ll res = 0;

    //两层 for循环会超时！！
    /* 
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
        {
            if( (s[j] - s[j - i]) % k == 0) cnt++;
        }
        */
    cnt[0] = 1; // 为什么cnt[0]等于1呢？？  s[0]是0,0模k余0，所以一开始余数是0的数有一个。
    for(int i = 1; i <= n; i++)
    {
        cnt[s[i] % k]++;
    }

    for(int i = 0; i < k; i++)
    {
        res += cnt[i] * (cnt[i] - 1) / 2;
    }

    printf("%lld",res);
    return 0;
}