1.

工龄排序

给定学校 N 名教师的工龄，要求按工龄增序输出每个工龄段有多少教师。

输入格式:

输入首先给出正整数N（≤10^5），即教师总人数；随后给出N个整数，即每个教师的工龄，范围在[0, 50]。

输出格式:

按工龄的递增顺序输出每个工龄的教师个数，格式为：“工龄:人数”。每项占一行。如果人数为 0 则不输出该项。要求时间复杂度为O(N)。

输入样例:

8
10 2 0 5 7 2 5 2

输出样例:

0:1
2:3
5:2
7:1
10:1

代码

#include <bits/stdc++.h>

using namespace std;

map<int,int> h;//自动排序

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

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

    for (auto [y , x] : h) cout << y << ':' << x << endl ;

    return 0;

}

2.

acwing796 ：二维前缀和(不一定是真题)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int g[N][N] , s[N][N];
int n , m , q ;

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

    for (int i = 1 ; i <= n ; i ++)
        for (int j = 1 ; j <= m ; j ++)
        {
            cin >> g[i][j];
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + g[i][j] ;
        }    

    while (q --)
    {
        int x1 , y1 , x2 , y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1- 1][y2] + s[x1 - 1][y1 - 1] << endl;
    }
}

补充：acwing 3487.最小面积子矩阵(学长说带k带前缀和，所以我估计是这个)

矩阵元素和：

通过确定上下边界后再确定左右边界O($n^3$)

#include <bits/stdc++.h>

using namespace std;

const int N = 110 ;

int s[N][N];
int n , m , k;

int main()
{
    int sum = 0 ;
    cin >> n >> m >> k ;
    for (int i = 1 ; i <= n ; i ++)
        for (int j = 1 ; j <= m ; j ++)
        {
            cin >> s[i][j] ;
            s[i][j] += s[i - 1][j] ; //第j列的前缀和
        }
    int res = 0x3f3f3f3f ;
    for (int up = 1 ; up <= n ; up ++) //up:上边界
        for (int down = 1 ; down <= n ; down ++) //down:下边界
            for (int r = 1 , l = 1 , sum = 0 ; r <= m ; r ++) //l:左边界, r:右边界
                {
                    sum += s[down][r] - s[up - 1][r];
                    while (l <= m && sum - (s[down][l] - s[up - 1][l]) >= k)
                    {
                        sum -= s[down][l] - s[up - 1][l];
                        l ++;
                    }

                    if (sum >= k) res = min (res , (down - up + 1) * (r - l + 1));
                }

    if (res != 0x3f3f3f3f) cout << res << endl ;
    else puts("-1");

    return 0;

}

3.

acwing821：机器人(跳台阶)

#include <bits/stdc++.h>

using namespace std;

const int N = 20 ;

int n , cnt ;

void func(int n)
{
    if (n <= 0)
    {
        if (n == 0) cnt ++;
        return ;
    }

    func(n - 1);
    func(n - 2);
}

int main()
{
    cin >> n ;
    func(n);
    cout << cnt << endl;
    return 0;
}