洛谷刷题笔记 其三

洛谷刷题笔记：

1.语文成绩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//用差分，如果寻常做法会超时
int s[]={-1,0,5,2,3,4};//原数组
int d[6];
int s1[6];
d[0]=s[0];//-1
for(int i=1;i<n;++i){
    d[i]=s[i]-s[i-1];
}
//现在的d={-1,1,5,-3,1,1}假如要对[1,3]区间(对于d数组的形式)进行操作+1；
d[1]+=1;
d[3+1]-=1;//-1的原因是因为要覆盖到区间，所以出了区间立马加1,如果大于区间，就不管

//现在d={-1,2,5,-3,0,1}
//然后对差分数组d进行前缀和操作还原

s1[0]=d[0];
for(int i=1;i<n;++i){
    s1[i]=d[i]+s1[i-1];
}
//s1={-1,1,6,3,3,4}

2.求和

1
//前缀和，合并一下

3.k倍区间

1
2
3
//首先，单纯用枚举或者前缀和这道题肯定会超时的
//他要求区间和是k的倍数
//可以用同余的思想，先求出前缀和数组，然后同时%k，统计每个结果相同的个数，如果个数大于2，说明，在这个大于2的区间之间有x*(x-1)/2个区间和是k的倍数，接着统计总个数即可

4.地毯：

1
//二维数组的应用

5.激光炸弹

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
//二维前缀和的应用，然后要注意的是输入价值的时候，可能多次在同一区域
long long int pre[5005][5005]={0};
long long int s[5005][5005]={0};
int main(){
	long long int n,m;
	scanf("%lld%lld",&n,&m);
	long long int max=0;
	for(long long int i=0;i<n;++i){
		long long int x,y,v;
		
		scanf(" %lld%lld%lld",&x,&y,&v);
		s[x+1][y+1]+=v;
	} 
	for(int i=1;i<5005;++i){
		for(int j=1;j<5005;++j){
			pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+s[i][j];
		}
	}
	for(int i=m;i<5005;++i){
		for(int j=m;j<5005;++j){
			long long int s1=0;
			s1=pre[i][j]-pre[i-m][j]-pre[i][j-m]+pre[i-m][j-m];
			max=(max>s1)?max:s1;
		}
	}
	printf("%lld",max);
	return 0;
}

6.最大加权矩形

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
//这道题还是二维前缀和，不过因为他没有限制时间，可以直接枚举出所有的二维前缀和区间
//要注意的是，每次前缀和区间计算的时候的范围
int pre[130][130]={0};
int main(){
	int n;
	int max=INT_MIN;
	scanf("%d",&n);
	int s[n][n];

	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			scanf(" %d",&s[i][j]);
		}
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			pre[i][j]=s[i][j];
            if(i>0) pre[i][j]+=pre[i-1][j];
            if(j>0) pre[i][j]+=pre[i][j-1];
            if(i>0 && j>0) pre[i][j]-=pre[i-1][j-1];
		}
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			for(int m=i;m<n;++m){
				for(int w=j;w<n;++w){
					int s1 = pre[m][w];
                    if(i>0) s1-=pre[i-1][w];
                    if(j>0) s1-=pre[m][j-1];
                    if(i>0 && j>0) s1+=pre[i-1][j-1];
					max=(max>s1)?max:s1;
				}
			} 
		}
	}
	printf("%d",max);
	return 0;
}

7.表达式括号匹配

1
//这道题唯一要注意的是括号的数量，并且反括号的数一定不可能大于正括号

8.查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//二分查找，他要求第一个，那就找到了继续往前查找
int fen(int s[n],int n,int t){
	int l=0;
	int r=n-1;
	int mid,id;
	while(r>=l){
        mid=l+(r-l)/2;//确保不越界
		if(s[mid]==t){
			id=mid+1;
            r=mid-1;//向左边继续查找，寻找最小的
		}
        else if(s[mid]<t){
            l=mid+1;
        }
        else if(s[mid]>t){
            r=mid-1;
        }
	}
    return id;
}

9.分巧克力

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
//这题和下一个题的思路是一样的，这题要分巧克力，那就从面积出发，总面积除小孩的人数就可以得到最大，最理想的巧克力面积，可以以此为边界来找真正符合的巧克力数
#include<stdio.h>
#include<limits.h>
int main(){
	int max=INT_MIN;
	int n,k;
	scanf("%d %d",&n,&k);
	int x[n],y[n];
	int num=0;//存数
	int sum=0;
	for(int i=0;i<n;++i){
		scanf(" %d %d",&x[i],&y[i]);
		sum+=x[i]*y[i];
	}
	int l=1,r=1e9,mid;
	
	while(l<=r){
		mid=(l+r)/2;
		num=0;
		for(int j=0;j<n;++j){
			num+=(x[j]/mid)*(y[j]/mid);//这个要分开计算 
		}	
		if(num>=k){
			max=mid;
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	} 
	
	printf("%d",max);
	return 0;
}

10.枚举元组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int path[6];
int dfs(int x,int n,int k){//x是初始数，n是最大数，k是最大组数
    if(x==k){
        for(int i=1;i<k;++i){
            printf("%d",&path[i]);
        }
        printf("\n");
        return;
    }
    for(int i=1;i<n;++i){
        path[x]=i;
        dfs(x+1,n,k);
    }
    
}

11.八皇后

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
//这里a是专门存储皇后的，bcd三个变量分别是标记竖，主斜角，负斜角的，为什么不用一个变量？因为3个变量的计算导致他们的范围都不同
int n;
int count=0;
int a[100],b[100],c[100],d[100];
void dfs(int i){
	if(i>n){
		count++;
		if(count<4){
			for(int i=1;i<=n;++i){
				printf(" %d",a[i]);
			}
			printf("\n");
		}
		return ;
		
	}
	for(int j=1;j<=n;++j){
		if(!b[j] && !c[i-j+n-1] && !d[i+j]){
			a[i]=j;
			b[j]=c[i-j+n-1]=d[i+j]=1;//这里i-j+n-1是为了防止其索引越界
			dfs(i+1);
			b[j]=c[i-j+n-1]=d[i+j]=0;
		}
	}
}
int main(){
	scanf("%d",&n);
	dfs(1);
	printf("%d",count);
	return 0;
}

12.质数筛

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
//用埃氏筛算法
//因为如果一般双循环找质数（素数）可能查找有重复部分，时间就会大大增长，这时，可以用以下办法：
void sieve(bool is_prime[], int n) {
    for (int i = 2; i * i <= n; i++) {//对于一个数n来说，如果它能被某个数i整除，那么i必定小于等于√n，否则i和n/i会互换角色。因此，只需要检查到i的平方大于n，即可确保所有可能的因数都已被检查。
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {//从i*i开始是因为如果i是倍数，那么他所有的倍数就都是合数即非质数
                is_prime[j] = false;
            }
        }
    }
}
int main() {
    int n = 30;
    bool is_prime[100];
    //初始化数组，假设所有数都是质数
    for (int i = 0; i <= 100; i++) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;

    sieve(is_prime, n);

    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) printf("%d ", i);
    }
    return 0;
}

13.金币

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//和约瑟夫问题的思考差不多，也是要列下次数
int main(){
	int k;
	scanf("%d",&k);
	int sum=0;
	int m=0;
	int i=1;
	while(k>0){
		m++;
		if(k<=i) {
			sum+=m*k;
			break; 
		}
		k-=i;
		sum+=i*m;
		i++;
		
	}
	printf("%d",sum);
}