CSP题解

CSP题解

本蒟蒻是因为CSP网站不能查看已经提交的代码，所以借此记录，大佬们轻喷

1> 第24次CSP 第1题 序列查询

       最开始想到用upper_bound，upper_bound在数组中找到的第一个大于x的下标-1就是数组中最大的小于等于x的下标，但是要遍历N，二分查找复杂度log(n)，时间复杂度大 （虽然能AC）

        然后仔细想，区间[a[i-1] ，a[i])的f值都为a[i]，所以遍历数组,只需O(n)的复杂度

#include
using namespace std;

int n,m;
const int maxn = 1e5 + 5;
int a[maxn],r,g;
long long ans;

int main(){
	cin >> n >> m;
	r = m / (n+1); //g = x / r;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	int i = 1;
	for(;i<=n;i++){
        //区间[a[i-1], a[i]-1 ] f值相同 值为i-1
        ans += (i-1) * (a[i] - a[i-1]);
	}
	//遍历完了数组 边界还在没跑完 （最后一个数在边界上或者左边）
    //f相同区间 [ a[i-1] , m-1 ]  f值为 i - 1
	if(a[i-1] <= m-1){
		ans += (i-1) * (m - a[i-1]);
	}
	cout << ans << endl;
	return 0;
}

2> 第24次CSP 第2题 序列查询新解

        同样遍历数组，对于每一个f值相同的区间，检查g值是否相同，为了更快，检查g值相同区间不能挨个遍历，观察式子可以用余数的性质挨个查询g值相同的区间。

#include
using namespace std;

int n,m;
const int maxn = 1e5 + 5;
int a[maxn],r,g;
long long ans;

int main(){
	cin >> n >> m;
	r = m / (n+1); //g = x / r;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	int i = 1;
	for(;i<=n;i++){
        //区间[a[i-1], a[i]-1 ] f值相同 值为i-1
        //下面检查这段区间[ a[i-1], a[i]-1 ]里的g值是否等于i-1 
        int pos = a[i-1];
        int gr, cnt;
        while(pos < a[i]){// r - pos % r
            g = pos / r;
            //寻找相同g值的区间
            gr = pos + r - pos % r; // [pos ,  pos + r-pos%r) 的g值相同 但要检查这个区间是否在相同的f区间内
            if(gr <= a[i]){ // 在f相同的区间内 数量为 r - pos%r
                cnt = r - pos % r;
                ans += abs(g - (i-1)) * cnt;
                pos += r - pos % r;
                //cout << "pos = "<< pos << endl;
            }
            else if(gr > a[i]){//超出了f相同的区间 只取到a[i] 数量为a[i] - pos
                cnt = a[i] - pos;
                ans += abs(g - (i-1)) * cnt;
                pos = a[i];
                // cout << "pos = "<< pos << endl;
            }
        }
	}
	//遍历完了数组 边界还在没跑完 （最后一个数在边界上或者左边）
    //f相同区间 [ a[i-1] , m-1 ]  f值为 i - 1
	if(i>n && a[i-1] <= m-1){
		int pos = a[i-1];
        int gr, cnt;
        while(pos < m){
            g = pos / r;
            //寻找相同g值的区间
            gr = pos + r - pos % r; // [pos , pos+pos%r) 的g值相同 但要检查这个区间是否在相同的f区间内
            if(gr <= m){ // 在f相同的区间内 数量为 pos%r
                cnt =r - pos % r;
                ans += abs(g - (i-1)) * cnt;
                pos += r - pos % r;
                 //cout << "pos = "<< pos << endl;
            }
            else if(gr > m){//超出了f相同的区间 只取到m 数量为m - pos
                cnt = m - pos;
                ans += abs(g - (i-1)) * cnt;
                pos = m;
                // cout << "pos = "<< pos << endl;
            }
        }
	}
	cout << ans << endl;
	return 0;
}

3> 第23次CSP 第1题 数组推导

sum_max时，a数组的每个数都取当前b数组的数，也就是b数组本身，求和即可

sum_min时，在b数组出现增加的时候的位置，a数组取b数组当前位置的数，其余位置(未增加)均取0即可

#include 
#include 
using namespace std;
const int maxn = 1e5 + 5;
int n, b[maxn], sum_max, sum_min;

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        sum_max += b[i];
        sum_min += (b[i] > b[i-1]) ? b[i] : 0;
    }
    cout << sum_max << endl << sum_min << endl;
    return 0;
}

4> 第23次CSP 第2题 非零段划分

#include
using namespace std;

int n,m;
const int maxn = 5e5 + 5;
int a[maxn],cnt[10005];

int main(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	n = unique(a + 1, a + 1 + n) - (a + 1);//unique返回的是不重复元素的下一个元素的位置
	a[n+1] = 0;//n后面的值unique函数是没有删除原有元素的
	for(int i=1;i<=n;i++){
		int x = a[i-1], y = a[i], z = a[i+1];
		if(x < y && y > z) cnt[y]++;
		if(x > y && y < z) cnt[y]--;
	}
	int sum = 0, ans = 0;
	for(int i=10000;i>=0;i--){
		sum += cnt[i];
		ans = max(ans, sum);
	}
	cout << ans << endl;
	return 0;
}