算法·题目

递归和递推

开关问题

https://www.acwing.com/problem/content/97/
为什么最开始枚举第一行的操作是因为第一行操作确定了，那么整个5x5灯泡的操作都确定了，从0-32枚举意思是 ：不管你第一行灯泡亮还是不亮，我先给你按一下，完事再检查1-4行的灯泡状态保证全亮，最后看最后一行就可以看是否有解。又因为是从00000遍历到11111的所有按法，每次都更新了答案，所以最后输出的就是最优解。

什么意思，首先0-32是枚举的第一行的所有状态，比如11001，完事把两个00按了，这个时候没考虑第一行输入的实际灯泡的亮灭，可能实际输入的是10101，然后在检查1-4行，碰到灭的就按亮。由于枚举了完了第一行的所有状态，肯定可以枚举到一个和实际情况一样的灯泡亮灭序列，这个时候产生的就是答案

就是说，第一行枚举的32是操作种数，为了得到步数最少的，要把每种操作的步数都算一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N=6; //题目中的数据是5X5的二维字符数组，在结尾处有\0
                           //g[][]用来存储25盏灯的初始状态
char g[N][N],backup[N][N]; //backup[][]用来备份这25盏灯，此处用char数组是因为char数组正好可以整存一行
int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0}; //执行开关灯操作对应的五个位置

void turn(int x,int y) //执行开关灯操作
{
    for(int i=0;i<5;i++) //循环五次
    {
        int a=x+dx[i],b=y+dy[i]; //新的坐标位置
        if(a<0||a>=5||b<0||b>=5) continue; //如果新的坐标位置不在方形内重新开始循环
        g[a][b]^=1; //字符1的ASCII码为49,0的ASCII码为48转化为二进制最后一位分别是1,0
    }               //^表示异或运算 0^1=1,1^1=0
}                   //通过位运算来优化操作

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

    while(q--) //执行q次操作
    {
        for(int i=0;i<5;i++) cin>>g[i]; //输入25盏灯的状态

        int res = 10; //初始化答案，只要大于6即可,因为最终是判断能否在六步内完成，如果题目要求输出最小值，也可以变成2e9之类的大数字
        for(int op=0;op<32;op++) //第一行一共5个元素可以操作2^5=32次，这里的op记录的不是灯的情况，而是需要操作的情况，即1表示的不是灯亮，而是需要调亮灯，美剧玩操作之后，要按照操作对第0行操作一遍
        {                        //从一行开始枚举进行操作
            memcpy(backup,g,sizeof g); //备份25盏灯

            int step=0; //step用来存储操作的次数
            for(int i=0;i<5;i++)//枚举第一行的5个位置
            {
                if(op>>i&1) //寻找op第i个位置是1
                {
                    step++; //找到需要点亮的，操作步数加1
                    turn(0,i); //进行操作
                }
            }
				//注意，此时由于前面已经枚举过第一行的操作，g[][]已经被改变，接下来遍历的是已经改变后的g数组
            for(int i=0;i<4;i++)//因为我们从上往下，即从第0行开始调灯， 因此第4行调完以后第5行是固定的，不需要枚举第五行的情况
            {
                for(int j=0;j<5;j++)//枚举该行中5个位置的情况
                {
                    if(g[i][j]=='0') //如果这个位置的灯是灭的，接下来需要点亮
                    {
                        step++; //步骤数加1
                        turn(i+1,j); //对该位置的下一行进行操作，因为对下一行该位置的操作只影响上一行的对应位置，不影响上一行的其他位置，方便接下来一直枚举，这样第五行不会被改变，如果第4行全亮第5行有不亮，说明没有办法把25盏灯泡全部变亮。
                    }
                }
            }

            bool dark=false; //dark变量表示最后一行是否全亮
            for(int i=0;i<5;i++)
            {
                if(g[4][i]=='0') //如果最后一行出现不亮的灯0
                {
                    dark=true; //dark为真
                    break; //终止循环
                }
            }

            if(!dark) res=min(res,step); //最后一行全都亮表示所有灯都点亮了
            memcpy(g,backup,sizeof g); //本次循环结束后将初始状态复原到g数组
        }
//遍历完了当前输入的初始状况的所有操作，得出操作的最小值res
        if(res>6) res=-1; //大于6输出-1

        cout<<res<<endl; //输出答案
    }

    return 0;
}

飞行员兄弟

https://www.acwing.com/problem/content/118/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N=5;
typedef pair<int,int> PII;
bool s[N][N],backup[N][N];
int dx[13]={-3,-2,-1,1,2,3,0,0,0,0,0,0,0},dy[13]={0,0,0,0,0,0,-3,-2,-1,1,2,3,0};
int getx(int a){
	return a/4;
}
int gety(int a){
	return a%4;
}
void turn(int x,int y){
	for(int i = 0;i<13;i++){
		int a = x+dx[i],b= y+dy[i];
		if(a>=0&&a<=3&&b>=0&&b<=3)
			s[a][b]^=1;
	}
} 
priority_queue<PII,vector<PII>,greater<PII>> zero;
int main(){
	for(int i = 0;i<4;i++)
		for(int j  =0;j<4;j++)
			{
				char c;
				cin>>c;
				if(c=='-') s[i][j]=1;
			}
	priority_queue<PII,vector<PII>,greater<PII>> heap;
	int res = 2e9;
	memcpy(backup,s,sizeof s);		
	for(int op=0;op<1<<16;op++){
		auto h  = heap;//heap的备份 ，此时的heap对应的是最小值操作数的heap 
		heap = zero;//清空heap 
			for(int i = 0;i<16;i++)
				if(op>>i&1){
					 int x = getx(i),y=gety(i);
					 turn(x,y);
					 heap.push({x,y}); 
				}
			bool open = true;
			for(int i = 0;i<4;i++)
				for(int  j = 0;j<4;j++)
					if(!s[i][j]){
						open = false;
						break;
					}
					//搞定一种操作方式 
			memcpy(s,backup,sizeof backup);//复原s
			//由于之前清空了heap，此时的heap对应的是目前情况的操作坐标 
			if(!open){//失败，说明此种方式不成功 
					heap = h;//把heap变为之前的最大值 
			}
			else {
				if(heap.size()<res)res=heap.size();
			}
					
	}
		cout<<res<<endl;
		while(!heap.empty()){
			auto t = heap.top();
			heap.pop();
			cout<<(t.first)+1<<' '<<(t.second)+1<<endl;
		}
	
	
	
			return 0;
}

全排列问题

https://www.acwing.com/problem/content/1211/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
int get(int l,int r,int a[]){
	int res = 0 ;
	for(int i = l;i<=r;i++)
		res+=res*10+a[i];
	return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	cin>>n;
	int cnt = 0;
	int x[9]={1,2,3,4,5,6,7,8,9};
	do{
		for(int i = 0;i<=6;i++){
			for(int j = i+1;j<=7;j++){
			     int  a = get(0,i,x);
				 int  b = get(i+1,j,x);
				 int  c = get(j+1,8,x);
			if(a*c+b==c*n)cnt++;
			}
		
	
		}
	}while(next_permutation(x,x+9));//头文件algorithm里面的全排列函数
	cout<<cnt<<endl;
	return 0;
}

枚举问题（dfs处理）

https://www.acwing.com/activity/content/problem/content/1547/

https://www.acwing.com/activity/content/problem/content/1548/

https://www.acwing.com/activity/content/problem/content/1545/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//指数型枚举
#include <iostream>
using namespace std;
const int N=20;
int st[N];
int n;
void dfs(int x){
    if(x>n){
        for(int i =1;i<=n;i++)
            if(st[i]==1) cout<<i<<" ";
            cout<<endl;
            return ;
    }
    st[x] = 2;
    dfs(x+1);
    st[x]=0;
    st[x]=1;
    dfs(x+1);
    st[x]=0;
}
int main(){
    cin>>n;
    dfs(1);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//排列型枚举
#include <iostream>
using namespace std;
const int N=15;
int path[N];
bool st[N];
int n;
void dfs(int x){
    if(x==n){
        for(int i = 0;i<n;i++)
            cout<<path[i]<<' ';
    cout<<endl;
    }
    for(int i = 1;i<=n;i++){
        if(!st[i]){
            st[i]=true;
            path[x] = i;
            dfs(x+1);
            st[i]=false;
        }
    }
}
int main(){
    cin>>n;
    dfs(0);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//组合型枚举
#include <iostream>
using namespace std;
const int N=30;
bool st[N];
int path[N];
int n,m;                   
void dfs(int x,int start){
    if(n-start+x<m)return;
    if(x==m+1){
        for(int i =1;i<=m;i++)
            cout<<path[i]<<' ';
            cout<<endl;
    }
    for(int i = start;i<=n;i++){
        if(!st[i]){
            st[i]=true; 
        path[x]=i;
        dfs(x+1,i+1);
            st[i] = false;
    }
    }

}
int main(){
    cin>>n>>m;
    dfs(1,1);
}

二分

四平方和

https://www.acwing.com/problem/content/1223/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=5e6+10;
int n;
int cnt;
struct Sum{
	int s,c,d;
	bool operator<(const Sum&w)const{
	   if(s!=w.s) return s<w.s;
	   if(c!=w.c) return c<w.c;
	   return d<w.d;
	}
}sum[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

	cin>>n;
	
	for(int i =0;i*i<=n;i++)
		for(int j =i;j*j+i*i<=n;j++)
			sum[cnt++] = {i*i+j*j,i,j};
	sort(sum,sum+cnt);
	for(int a = 0;a*a<=n;a++)
		for(int b = a;a*a+b*b<=n;b++){
			int t = n-a*a-b*b;
			int l = 0 , r = cnt-1;
			while(l<r){
				int mid = l+r>>1;
				if(sum[mid].s>=t) r = mid;
				else l = mid+1;
			}
			if(sum[l].s==t){
				 cout<<a<<' '<<b<<' '<<sum[l].c<<' '<<sum[l].d;
				 return 0;
				
			}
			
			
		}
}

前缀和

K倍区间

https://www.acwing.com/problem/content/1232/

原理：

(a−b)≡0(mod m)⇿a≡b(mod m)(a-b)≡0(mod~m) ⇿ a≡b(mod ~m) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, k;
LL s[N], cnt[N];

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }//初始化前缀和

    LL res = 0;
    cnt[0] = 1;//cnt[i]，里面的i记录的是余数，cnt[i]记录的是余数为i的前缀和的个数,由于余数为0的时候自己就是一种方案，所以加一
    for (int i = 1; i <= n; i ++ )//遍历前缀和
    {
        res += cnt[s[i] % k];//res = res+cnt[s[i]%k],这里s[i]%k对应的是当前前缀和的余数，cnt记录的是余数的数量，cnt[s[i]%k]即与s[i]同余的前缀和的数量，因为(a-b)≡0(mod~m) ⇿ a≡b(mod ~m)，所以当第一个s[i]%k=m的时候，此时余数为m的只有一个，它本身不构成方案，至少得另一个出现才构成方案，因此当有第二个同余m出现的时候，s[i]-s[j]≡0(mod k)，此时出现一个前缀和区间，同理，当第三个出现的时候,除去已经记录的s[i]s[j],s[i]s[k]，s[j]s[k]之间有两个前缀和区间，由此可见，当第n个同余的前缀和出现的时候，抛开之前已经记录的区间，其会和之前所有的同余前缀和(n-1个)产生新的n-1个区间，由于余数非0的cnt最初为0，所以不需要减，直接加等于。
        cnt[s[i] % k] ++ ;//将该前缀和加入
    }

    printf("%lld\n", res);

    return 0;
}

递增三元组

https://www.acwing.com/problem/content/description/1238/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <iostream>
#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], s[N];

int main()
{
    scanf("%d", &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] ++ ;
//预处理出每个b[i]与a[i]和c[i]相关的前缀和
    // 求as[]
    for (int i = 0; i < n; i ++ ) cnt[a[i]] ++ ;//cnt记录的是某个数字出现的次数，将a数组中的所有数字出现的次数录入，其中i是从小到大的，所以里面的数已经排好序，可以按序取次数
    for (int i = 1; i < N; i ++ ) s[i] = s[i - 1] + cnt[i];   // 求cnt[]的前缀和，s[i]记录的即0-i中小于等于i的数的个数
    for (int i = 0; i < n; i ++ ) as[i] = s[b[i] - 1];//as[i]记录小于b[i]的数字出现的次数。

    // 求cs[]，重复as过程
    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 - 1] - s[b[i]];//因为是找大于b[i]，从n+1到最大值的出现次数。

    // 枚举每个b[i]
    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += (LL)as[i] * cs[i];

    cout << res << endl;

    return 0;
}

数论

  • 如果a,b均是正整数且互质，那么ax+by,x>=0,y>=0不能凑出的最大数是ab-a-b

    (a−1)(b−1)−1(a-1)(b-1)-1

动态规划

地宫取宝

https://www.acwing.com/problem/content/1214/

4层dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55, MOD = 1000000007;

int n, m, k;
int w[N][N];//记录价值的数组
int f[N][N][13][14];//dp数组，f[i][j][cnt][value]ij记录的是当前走到的点的坐标,cnt记录的是已经取了k件物品，value记录的是取到的最后一件物品的价值，由于只有宝箱的价值大于手上的物品的价值才能取得，因此当取走宝箱里面的物品之后，其手中的物品的最大价值就是宝箱的价值。整个dp数组最终存储的就是（i，j）点，手中物品数量为cnt，手中物品最大价值为value的方案数量

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            cin >> w[i][j];//存入价值
            w[i][j] ++ ;//因为价值的范围为0-12，如果不增加1，容易产生0和0之间没法取大的情况，因此要先加1
        }
//初始化dp数组
    f[1][1][1][w[1][1]] = 1;//（1，1）如果取得，则(1,1)手中1个物品，最大物品价值为w[1][1]的方案数为1
    f[1][1][0][0] = 1;//（1，1）不取的方案数为1

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {//遍历迷宫
            if (i == 1 && j == 1) continue;//起点
            for (int u = 0; u <= k; u ++ ) 
                for (int v = 0; v <= 13; v ++ )
                {//遍历uv情况
                    int &val = f[i][j][u][v]; //取出方案数量
                    val = (val + f[i - 1][j][u][v]) % MOD; //从上面来的，不取 
                    val = (val + f[i][j - 1][u][v]) % MOD;//从左边来的，不取
                    if (u > 0 && v == w[i][j]) //u>0说明取了，v就是目前的价值
                    {
                        for (int c = 0; c < v; c ++ )//枚举上一个格子的c
                        {
                            val = (val + f[i - 1][j][u - 1][c]) % MOD;
                            val = (val + f[i][j - 1][u - 1][c]) % MOD;
                        }
                    }
                }
        }

    int res = 0;
    for (int i = 0; i <= 13; i ++ ) res = (res + f[n][m][k][i]) % MOD;

    cout << res << endl;

    return 0;
}

波动数列

https://www.acwing.com/problem/content/1216/

假设第一项为x,则长度为n的序列所有的项为

x,x+d1,x+d2,x+d3,...,x+dn−1x,x+d_1,x+d_2,x+d_3,...,x+d_{n-1}

x+x+d1+x+d2+x+d3+...+x+dn−1=nx+(n−1)d1+(n−2)d2+...+dn−1=sx+x+d_1+x+d_2+x+d_3+...+x+d_{n-1}=nx+(n-1)d_1+(n-2)d_2+...+d_n-1=s

x=(s−((n−1)d1+(n−2)d2+(n−3)d3+...+dn−1))n=s−Dnx=\frac{(s-((n-1)d_1+(n-2)d_2+(n-3)d_3+...+d_{n-1}))}{n}=\frac{s-D}{n}

由上可知

s−d≡0(mod n)   s mod n=0   D mod n=0s-d≡0(mod~n)~~~s~mod~n=0~~~D~mod~n=0 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, MOD = 100000007;

int f[N][N];//f[i,j]存储的是只考虑前i项d，且当前的总和mod n 余数为j的集合的数量

int get_mod(int a, int b)   // 求a除以b的正余数
{
    return (a % b + b) % b;
}

int main()
{
    int n, s, a, b;
    cin >> n >> s >> a >> b;

    f[0][0] = 1;//第0项modn余数为0的只有一个
    for (int i = 1; i < n; i ++ )//1-n-1
        for (int j = 0; j < n; j ++ )//因为j是mod n的余数，所以j<n
            f[i][j] = (f[i - 1][get_mod(j - a * (n - i), n)] + f[i - 1][get_mod(j + b * (n - i), n)]) % MOD;

    cout << f[n - 1][get_mod(s, n)] << endl;

    return 0;
}

枚举、模拟

日期问题

https://www.acwing.com/problem/content/1231/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 || month >= 13 || !day) return false;

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

    return true;
}

航班时间

https://www.acwing.com/problem/content/1233/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
int getsecond(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 getsecond(h2,m2,s2)-getsecond(h1,m1,s1)+d*24*3600;
}


int main(){
	string line;
	int cnt;
	cin>>cnt;
	getline(cin,line);
	while(cnt--){
		int t =(get_time()+get_time())/2;
		int hour = t/3600;
		int minute = t%3600/60;
		int second = t%60;
		printf("%02d:%02d:%02d\n",hour,minute,second);
		
		
		
	}
	
	return 0;
	
}

外卖店优先级

https://www.acwing.com/problem/content/1243/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, m, T;
int score[N], last[N];//score表示的是店铺优先级,last表示的是上一次有订单的时刻
bool st[N];//表示是否在优先缓存中

PII order[N];

int main()
{
    scanf("%d%d%d", &n, &m, &T);
    for (int i = 0; i < m; i ++ ) scanf("%d%d", &order[i].x, &order[i].y);
    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].x, id = order[i].y, cnt = j - i;
        i = j;

        score[id] -= t - last[id] - 1;//last后面，t之前有几个时刻
        if (score[id] < 0) score[id] = 0;
        if (score[id] <= 3) st[id] = false; // 以上处理的是t时刻之前的信息
//开始处理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];

    printf("%d\n", res);

    return 0;
}

树状数组

数星星

https://www.acwing.com/problem/content/1267/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 32010;

int n;
int tr[N], level[N];//level数组记录的是某等级的星星的数量，tr记录的是星星图

int lowbit(int x)
{
    return x & -x;
}

void add(int x)//加入一颗行星
{
    for (int i = x; i < N; i += lowbit(i)) tr[i] ++ ;//加入后后面的星星前面的星星数量加一，即星等加一
}

int sum(int x)//记录前面有多少个星星
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x ++ ;//因为y增序，所以只需要考虑x
        level[sum(x)] ++ ;//sum(x)即星等，由于求星等不包括x在内，所以先查星等，再把x加进去
        add(x);
    }

    for (int i = 0; i < n; i ++ ) printf("%d\n", level[i]);

    return 0;
}
算法·题目
http://example.com/2024/04/09/算法·题目/
作者
Kugeln
发布于
2024年4月9日
许可协议