错题：

[T2]

错因:

1、起初无意用暴力写出代码，后来发现不合适，又重新调整思路； 2、逻辑不清晰，导致代码杂乱；

思路：

推ABCD与输出值的关系式；

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
	freopen("step.in","r",stdin);
	freopen("step.out","w",stdout);
	ll n,a,l=0,sum=0;
	cin>>n;
	for(ll i=0;i<n;i++){
		cin>>a;
		if(a>l) l=a;
		else sum+=l-a;
	} 
	cout<<sum<<endl;
	return 0;
}

[T3]

错因:

没有输出ENDL（花了一个半小时排查问题）；

思路：

1、 运用质数筛，筛出所有质数，再循环遍历所有质数，找出符合题目条件的质数并做标记； 2、 建立前缀和数组，循环到标记点，前缀和数组+1，每次前缀和数组的值都要加上自己的前一项； 3、 循环Q次每次输出前缀和数组的第r项和第l-1项的差值，输出换行；

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll gcd(ll x,ll y){
	if(x%y==0) return y;
	else return gcd(y,x%y);
}
int main(){
	freopen("div.in","r",stdin);
	freopen("div.out","w",stdout);
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll l=c/gcd(c,d)*d;
	ll sum=b-a+1;
	ll canc=b/c-(a-1)/c;
	ll cand=b/d-(a-1)/d;
	ll both=b/l-(a-1)/l;
	cout<<sum-canc-cand+both;
	return 0;
}

[T4]

错因:

对完全背包问题了解不深刻；

思路：

1、 将f数组设置为极大值，将f数组的第0项改为0（当背包容量为0时，背包无法装入物品）； 2、 循环n次，每次输入物品的体积和价值内套循环背包的容量次数，f的第j项变为最小的f[j]，或f[max(0,j-v)]+w; 3、 输出f[h] ;

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N = 1e5+5;
int primes[N], cnt,prime[N];
bool st[N];
void get_primes(int n){
	st[0]=st[1]=1;
	for(int i=2;i<=n;i++){
		if (!st[i]) {
			primes[++cnt] = i;
			for(int j=i+i;j<=n;j+=i) st[j]=1; 
		}
	}
}
int main(){
	freopen("qy.in","r",stdin);
	freopen("qy.out","w",stdout);
	int q;
	cin>>q;
	get_primes(N);
	for(int i=1;i<N;i+=2){
		if(st[i]==0&&st[(i+1)/2]==0) prime[i]=1;
	}
	for(int i=1;i<N;++i){
		prime[i]+=prime[i-1];
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		cout<<prime[r]-prime[l-1]<<endl;
	}
	return 0;
}

[T5]

错因:

一遍AC；

思路：

1、 循环m次，输入u和v,构建u-v和v-u的路径； 2、 设置标记数组的第一项为1，以1为起点进行深搜（深搜时如果cnt大于1e6，则直接返回，否则，cnt+1。循环每次设j为数组adj[u][i],如果vis的第j项被标记过，则直接进入下一层循环，否则，将vis的第j项标记，dfs(j) ，回溯； 3、 如果cnt大于1e6，则直接输出1e6，否则输出cnt；

参考代码

#include<bits/stdc++.h>
using namespace std;
int n,h;
const int N=10010;
int f[N];
int v, w; 
int main(){
	freopen("mana.in","r",stdin);
	freopen("mana.out","w",stdout);
	cin>>h>>n;
	memset(f,0x3f,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;i++){
		cin >> v >> w;
		for(int j = 0; j <= h; j++)
            f[j] =min(f[j], f[max(0,j-v)] + w);
	}
	cout<<f[h];
}

[T6]

错因:

一遍AC；

思路：

1、 循环输入数组w的第i项，排序数组w，设立ans等于0，循环n次，每一层判定t是否大于等于1，如果“是”，则ans为最大的ans，dp[t-1]+b,然后以t-1为开头，a为结尾，每次j-1,dp的第j项，设置为最大的dp第j项，或dp第j-a项+b; 2、 Ans变为最大的ans或dp第t-1项；

参考代码

#include<bits/stdc++.h>
using namespace std;
int n,t,ans;
pair<int,int> w[3010];
int dp[3010];
int main(){
    freopen("free.in","r",stdin);
    freopen("free.out","w",stdout);
	cin>>n>>t;
	for(int i=0;i<n;i++){
		cin>>w[i].first>>w[i].second;
	}
	sort(w,w+n);
	int ans=0;
	for(int i=0;i<n;i++){
		int a=w[i].first,b=w[i].second;
		if(t>=1) ans=max(ans,dp[t-1]+b);
		for(int j=t-1;j>=a;j--) dp[j]=max(dp[j],dp[j-a]+b);
	}
	ans=max(ans,dp[t-1]);
	cout<<ans<<endl;
	return 0;
}