分类目录归档：前缀和

CSP 202012-2 期末预测之最佳阈值

1条回复

这题也不知道咋回事，我想了个异想天开的做法，也不知道行不行，交上去竟然过了！哈哈哈哈哈哈。
暴力的N^2做法可以得70，我写个异想天开的排序+前缀和做法100。
感觉有必要写个题解，在这里写一下。

本题的大致意思是，给出一堆人的学习努力程度（用一个非负整数表示）和其是否挂科（并不必然成正相关，其中可能混杂学习努力程度高的人也挂科的情况）。要求找到一个学习努力程度基准分数，使得用该基准评判学生的努力程度时，判断对的最多。

我主要利用差分的思想进行解题。对于一个分数，我们其实只需要知道通过与挂科的人数的差值即可。基准分数是否应该低于或高于某一特定学习努力程度分数，在于其能否为总人数作出贡献。例如，如果一个分数有3人通过，3人挂科，则不管选择比他低的基准还是比他高的基准，则都对总的人数做出了3的贡献，可以相互抵消。但若4人通过，3人挂科，则更应该优先选择比其低的基准，因为这样的话，判断对的就多了一个。

首先建立一个map对输入的数据进行排序。由于选择指标的时候只看努力程度不看人，因此可以将同努力程度的人们聚合起来。如果该人挂科，在是否通过的数组cnt里-1，如果通过则+1.这样就产生了一个差分的数组cnt。此时，该数组cnt表示的是在选定该分数作为基准后，通过的人比挂科的人多多少。

然后，对其进行前缀和操作。借助前缀和，我们可以得到数组presum，可以计算选择任意基准分数时，通过的人比挂科的人多多少。还可计算选择任意基准分数时，挂科的人比通过的人多多少（通过对计算值取负）。这样，我们分别计算高于基准分数通过的人比挂科的人多多少，和低于基准分数时挂科的人比通过的人多多少。将他们相加，就可以得到一个判断正确的人数的差分。统计这些差分的最大值，就可以算出对应的基准分数。

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
#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <cstdlib>

using namespace std;

int m;
map<int, int> stat;
int arrSize = 0;
int y[100005], cnt[100005], presum[100005];

int main() {
    ios::sync_with_stdio(false);
    cin >> m;
    while (m--) {
        int y, result;
        cin >> y >> result;
        stat[y] += result ? 1 : -1;
    }
    for (auto iter = stat.begin(); iter != stat.end(); iter++) {
        int ind = iter->first, v = iter->second;
        y[arrSize] = ind;
        cnt[arrSize] = v;
        arrSize++;
    }
    presum[0]=cnt[0];
    for(int i=1;i<arrSize;i++){
        presum[i]=presum[i-1]+cnt[i];
    }
    int index=0, cmpValue=presum[arrSize-1];
    for(int i=1;i<arrSize;i++){
        int tmpV=presum[arrSize-1]-presum[i-1]*2;
        if(tmpV>=cmpValue){
            cmpValue=tmpV;
            index=i;
        }
    }
    cout<<y[index];
}

洛谷 P1220 关路灯

发表评论

我递推啥都不会写垃圾死了，一道对我来说用递推非常难以解决的、难以思考的DP题目被我用记忆化递归解决了，0ms，高兴死我啦！
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈，代码写的那么长。。

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>
#include<cstring>
using namespace std;
int n,c;
int pos[55],power[55];
int prefixPower[55];
int f[55][55][2];
inline int getEnergy(int l,int r){
    return prefixPower[n]-prefixPower[r]+prefixPower[l-1];
}
int dp(int l,int r,int d){
    if(f[l][r][d]!=-1)return f[l][r][d];
    if(l==1&&r==n)return f[l][r][d]=0;
    if(l==1&&r<n)return f[l][r][d]=getEnergy(l,r)*(d?pos[r+1]-pos[r]:pos[r+1]-pos[l])+dp(l,r+1,1);
    if(l>1&&r==n)return f[l][r][d]=getEnergy(l,r)*(d?pos[r]-pos[l-1]:pos[l]-pos[l-1])+dp(l-1,r,0);
    else return f[l][r][d]=min(getEnergy(l,r)*(d?pos[r]-pos[l-1]:pos[l]-pos[l-1])+dp(l-1,r,0),getEnergy(l,r)*(d?pos[r+1]-pos[r]:pos[r+1]-pos[l])+dp(l,r+1,1));
}
int main(){
    ios::sync_with_stdio(false);
    memset(f,-1,sizeof(f));
    cin>>n>>c;
    for(int i=1;i<=n;i++)cin>>pos[i]>>power[i];
    for(int i=1;i<=n;i++)prefixPower[i]=prefixPower[i-1]+power[i];
    cout<<min(dp(c,c,0),dp(c,c,1));
}

Codeforces Round #494 (Div. 3) 1003 A/C/D题解

发表评论

A题：非常简单，只要找重复数字的最大个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
int arr[105];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int tmp;
        cin>>tmp;
        arr[tmp]++;
    }
    int maxn=0;
    for(int i=1;i<=100;i++){
        maxn=max(maxn,arr[i]);
    }
    cout<<maxn;
}

C题：用个前缀和优化一下，剩下的暴力去吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,k;
double arr[5005];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>arr[i];
    for(int i=2;i<=n;i++)arr[i]+=arr[i-1];
    double maxavg=0,curavg;
    for(int i=k;i<=n;i++){
        for(int j=i;j<=n;j++){
            curavg=(arr[j]-arr[j-i])/i;
            maxavg=max(maxavg,curavg);
        }
    }
    printf("%.15lf",maxavg);
}

D题：把所有二的次幂数全部搞到桶里，然后按照次幂由高到低往下减，看最后能不能减到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
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,q;
int bucket[32];
int powarr[32];
int checkpower(int num){
    if(num==1)return 0;
    int cnter=0;
    while(num!=1){
        num/=2;
        cnter++;
    }
    return cnter;
}
void program_init(){
    powarr[0]=1;
    for(int i=1;i<=30;i++){
        powarr[i]=powarr[i-1]*2;
    }
}
int main(){
    program_init();
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int num;
        cin>>num;
        bucket[checkpower(num)]++;
    }
    for(int i=1;i<=q;i++){
        int num,cnter=0;
        cin>>num;
        for(int i=30;i>=0;i--){
            cnter+=min(num/powarr[i],bucket[i]);
            num-=min(num/powarr[i],bucket[i])*powarr[i];
        }
        if(num!=0)cout<<-1<<endl;
        else cout<<cnter<<endl;
    }
}

洛谷10月月赛R2·浴谷八连测R3 -Chtholly- 浮游大陆的68号岛

发表评论

洛谷题号：3932
一个前缀和的破题改了两个钟头，真是罪过。。。
借鉴了xsun2001同学的思路……在此表示感谢。。。
原来xsun2001同学代码中有可能存在的两点错误：第一个，有可能错在read函数里，读入进来的是int。第二，中间的所有计算过程全部需要取模。我把这两点改好之后就没问题了。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
#define MOD 19260817
long long n, m;
long long dis[200005], goods[200005];
long long prefixsum_dis[200005], prefixsum_goods[200005], prefixsum_cost[200005];
//从1到i点的距离/物品数/距离*物品数
#define LeftDis(l,r,x) ((prefixsum_cost[r] - prefixsum_cost[l - 1] + MOD)% MOD - (prefixsum_dis[x] * (prefixsum_goods[r] - prefixsum_goods[l - 1] + MOD) % MOD) + MOD) % MOD
#define RightDis(l,r,x) ((prefixsum_dis[x] * (prefixsum_goods[r] - prefixsum_goods[l - 1] + MOD) % MOD) - (prefixsum_cost[r] - prefixsum_cost[l - 1] + MOD) % MOD +MOD ) % MOD
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 2; i <= n; i++){
        cin >> dis[i];
        dis[i] %= MOD;
    }
    for (int i = 1; i <= n; i++){
        cin >> goods[i];
        goods[i] %= MOD;
    }
    for (int i = 1; i <= n; i++){
        prefixsum_dis[i] = (prefixsum_dis[i - 1] + dis[i]) % MOD;
        prefixsum_goods[i] = (prefixsum_goods[i - 1] + goods[i] % MOD) % MOD;
        prefixsum_cost[i] = (prefixsum_cost[i - 1] + prefixsum_dis[i] * goods[i] % MOD) % MOD;
    }
    for (long long i = 1; i <= m; i++){
        long long result = 0;
        long long x, l, r;
        cin >> x >> l >> r;
        if (l >= x){
            result += LeftDis(l,r,x);
        }
        else if (r <= x){
            result += RightDis(l,r,x);
        }
        else{
            result += LeftDis(x + 1, r, x);
            result += RightDis(l, x - 1, x);
        }

        cout << result%MOD << endl;
    }
    return 0;
}

题解地址：
洛谷月赛R2训练营R3

洛谷/USACO 家的范围 Home on the Range

发表评论

洛谷题号：P2733
思路很简单，我是参考洛谷 最大正方形这道题来写的，都是二维前缀和。

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
int n;
int arr[260][260];
int sum[260][260];
int cow[260];
inline int getSquareSum(int x, int y, int e){
    x--; y--;
    return sum[x + e][y + e] - sum[x + e][y] - sum[x][y + e] + sum[x][y];
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            scanf("%1d", &arr[i][j]);
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
        }
    }
    cow[1] = 1;
    for (int e = 2; e <= 250 && cow[e - 1] > 0; e++){
        for (int x = 1; x <= n - e + 1; x++){
            for (int y = 1; y <= n - e + 1; y++){
                if (getSquareSum(x, y, e) == e*e)
                    cow[e]++;
            }
        }
    }
    for (int i = 2; i <= 250 && cow[i] > 0; i++){
        printf("%d %d\n", i, cow[i]);
    }
}

洛谷 A % B Problem

发表评论

题目编号：1865
用到的思想，一维前缀和，埃式素数筛

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<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
bool prime[1000005];
int prefixsum[1000005];
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    memset(prime,true,sizeof(prime));
    prime[1]=false;
    for(int i=2;i<=m;i++){
        if(!prime[i])continue;
        for(int j=2;i*j<=m;j++){
            prime[i*j]=false;
        }
    }
    for(int i=1;i<=m;i++){
        prefixsum[i]=prefixsum[i-1]+prime[i];
    }
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        if(l<1||r>m){
            cout<<"Crossing the line"<<endl;
            continue;
        }
        cout<<prefixsum[r]-prefixsum[l-1]<<endl;
    }
}

洛谷 最大正方形

发表评论

题号：1387
参考题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1387
作者: hychychyc 更新时间: 2017-06-06 11:25

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
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int n, m;
int arr[105][105];
int sum[105][105];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> arr[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + arr[i][j]; //二维前缀和
        }
    }
    int maxn = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            for (int e = maxn; i + e <= n&&j + e <= m; e++){
                int w = sum[i + e][j + e] - sum[i][j + e] - sum[i + e][j] + sum[i][j];  //这个用二维前缀和计算正方形和
                if (e*e == w){
                    maxn = max(maxn, e);
                }
                else
                    break;
            }
        }
    }
    cout << maxn;
}

放上一张前缀和的图片，写的也很不清楚，也许有助于理解。

20180802更新：
上面代码都是错误的！！！！！！！！！
二维前缀和方程是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
int arr[105][105];
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)cin >> arr[i][j];
    for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + arr[i][j];
    for (int k = min(n, m); k > 0; k--) {
        for (int i = 1; i <= n - k + 1; i++) {
            for (int j = 1; j <= m - k + 1; j++) {
                if (k*k == arr[i + k - 1][j + k - 1] - arr[i - 1][j + k - 1] - arr[i + k - 1][j - 1] + arr[i - 1][j - 1]) { //参考这里
                    cout << k;
                    return 0;
                }
            }
        }
    }
}

动态规划做法：题解https://www.luogu.org/blog/user23035/solution-p1387

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
int arr[105][105];
int main() {
    cin >> n >> m;
    int ans = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        cin >> arr[i][j];
        if(arr[i][j])arr[i][j] = min(min(arr[i - 1][j], arr[i][j - 1]), arr[i - 1][j - 1]) + 1;
        ans = max(ans, arr[i][j]);
    }
    cout << ans;
}

Openjudge 百练 最大子矩阵 题解

发表评论

描述

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。

比如，如下4 * 4的矩阵

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

的最大子矩阵是

9 2
-4 1
-1 8

这个子矩阵的大小是15。输入输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在[-127, 127]。输出输出最大子矩阵的大小。

样例输入

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

样例输出

15

 

继续阅读 →