3.31考试总结

3.31考试题解及总结

Noip难度的题目还翻车，真的是菜出了天际。自己最近思维出现问题.静不下心来

T1

很明显的套路题，转化为差分数组.我们可以花费(1)的代价来对一个一个位置(+1)另一个位置(-1).最后统计一下大于(k)的之和与小于(-k)的差值之和取个(max)就好了

#include<cstdio>
#include<iostream>
#include<cctype>
#include<cstring>
#include<algorithm>
#define LL long long 
using namespace std;
const int N = 3e5 + 3;
LL ans;
LL n,k;
LL sum[N],a[N];
inline LL read(){
	LL v = 0,c = 1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') c = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		v = v * 10 + ch - 48;
		ch = getchar();	
	}
	return v * c;
}
int main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	n = read(),k = read();
	for(int i = 1;i <= n;++i) a[i] = read();
	for(int i = 1;i <= n + 1;++i) sum[i] = a[i] - a[i - 1];
	LL sum1 = 0,sum2 = 0;
	for(int i = 1;i <= n + 1;++i){
		if(sum[i] > k) sum1 += sum[i] - k;
		else if(sum[i] < -k) sum2 += (-k - sum[i]);
	}
	printf("%lld
",max(sum1,sum2));
	return 0;	
}

T2

DP题目,结果考场上写了一个贪心,喜提20

这道题开到(500000)，但暴力枚举质因子就可以过掉了.时间复杂度(O(nsqrt{n}))

然后由于垃圾lemon默认不开栈又喜提50,开栈之后A掉。

总结：考试浮躁静不下心来做题，不认真思考。以后考试不到收卷不开小差，认真思考题目

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 5e5 + 3;
int f[N];
int n,T;
inline int dp(int x){
	if(f[x] != -1) return f[x];
	f[x] = 2e9;
	for(int i = 2;i * i <= x;++i)
	if(x % i == 0)
	f[x] = min(f[x],min(dp(x - i) + 1,dp(x - (x / i)) + 1));
	f[x] = min(f[x],dp(x - 1) + 1);
	return f[x];
}
int main(){
	scanf("%d%d",&T,&n);
	memset(f,-1,sizeof(f));
	f[1] = 0;
	while(T--){
		int x;scanf("%d",&x);
		if(x < 1){printf("Impossible
");continue;}
		printf("%d
",dp(x));	
	}
	return 0;
}

T3

关于40分做法：

暴力枚举全排列打表

80分:

我们要得到一个(n ^2)的做法。
发现一个区间可以被分成多个区间好的区间,一定可以被分成两个好的区间
因为必定有一个前缀是好的,将这个前缀拿掉之后剩下的区间也一定是好的
而判断一个前缀是否是好的,只需要看(max_1^{i})的值是否为(i)即可
我们设

(g(i))表示(i)的排列个数

(f(i))表示长度为(i)的不可分割的排列个数

(f_n =g_n - sum_{i = 1}^{n - 1}f_ig_{n - i})

大意就是我们枚举好的前缀(i)的,用(f_i) 是因为这个前缀必须不可分割,否则会重复计算.
剩下(n - i)个数可以随便排列.