A. 给我一张凳子

思路： 很简单，遍历一遍就行，不会就看代码，错了纯没开long long

题解：

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5; 
long long n, a[N], ans;

int main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	freopen ( "step.in", "r", stdin);
	freopen ( "step.out", "w" ,stdout);
	cin>>n;
	for (long long i = 1;i <= n; i ++)
	{
		cin >> a[i];
	}
	for (long long i = 1;i <= n; i ++)
	{
		if ( a[i] < a[i - 1] )
		{
			ans += a[i - 1] - a[i];
			a[i] = a[i - 1];
		}
	}
	cout << ans;
	return 0;
}

B. 枚举是不可能枚举的

思路： 求出a到b之间的所有数，减去a到b之间的所有c的倍数和a到b之间的所有d的倍数，再加上a到b之间的所有c与d的公倍数就行了

题解：

#include <bits/stdc++.h>
using namespace std;

long long a, b, ans, c, d, i;

long long gcd(long long x,long long y){//最大公约数 
	return y?gcd(y,x%y):x;
}

int main()
{
	freopen ("div.in","r",stdin);
	freopen ("div.out","w",stdout);
	cin >> a >> b >> c >> d;
	long long bs = c / gcd(c, d) * d;
	ans = (b - a + 1) - (b / c - ( a - 1) / c) - (b / d - (a - 1) / d) + (b / bs - (a - 1) / bs);
	cout << ans;
	return 0;
}

C. 起遇质数

思路： 先筛出1到1e5之间的所有质数，再用前缀和求出所有符合条件的数就行

题解：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int q, primes[N], cnt, ans, s[N];
vector <int> st(N,1);

void get_primes(int n) {
	st[0]=0,st[1]=0;
	for (int i = 2; i <= n; i ++) {
		if(st[i]){
			for(int j = i + i;j <= n;j += i)
				st[j] = 0;
		}
	}
	for (int i = 1;i <= n; i++ )
	{
		s[i] = s[i - 1];
		if(i % 2 == 1 && st[i] && st[(i + 1) / 2])
			s[i] ++;
	}
}

int main()
{
	freopen ( "qy.in", "r", stdin);
	freopen ( "qy.out", "w", stdout);
	get_primes(100005);
	cin >> q;
//	for(int i = 1;i <= 60;i ++)
//	{
//		cout << st[i] << " ";
//	}
	for(int i = 1;i <= q; i ++)
	{
		int l, r;
		cin >> l >> r;
//		for(int j = l - 1;j <= r;j++) cout<<s[j]<<" ";
		cout << s[r] - s[l-1] << endl;
	}
	return 0;
}

D. 魔法咒语

思路： 完全背包模版，改一点地方就行，详细请见下方代码

题解：

#include <bits/stdc++.h>
using namespace std;

const long long N = 10005;
long long n, dp[N], a[N], b[N], H;

int main()
{
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	freopen ("mana.in" , "r", stdin );
	freopen ("mana.out", "w", stdout);
	cin >> H >> n;
	for (long long i = 1; i <= n; i ++)
	{
		cin >> a[i] >> b[i];
	}
	memset(dp, 0x3f, sizeof dp);
	dp[0] = 0;
	for (long long i = 1; i <= n; i ++)
	{
		for (long long j = 0; j <= H;j ++)
		{
			dp[j] = min( dp[j], dp[max(j- a[i],0*1ll) ] + b[i]);
//			cout << dp[j] << ' ';
		}
//		cout << endl;
	}
	//完全背包模版如下 
//	for(int i = 1;i <= n ;i ++)
//	{
//		for(int j = v[i];j <= m;j ++)
//		{
//			dp[j] = max( dp[j], dp[j - v[i]] + w[i]);
//		}
//	}
	cout << dp[H];
	return 0;
}

E. 简单路径统计

思路： 先建立一个无向图，用vector，再dfs深搜整个图，找出所有路径，计数就行

题解：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6,M = 2e5 + 5;
int n, m, cnt, v[M];
vector <int> adj[M];

void dfs (int u)
{
	if(cnt > N)
		return;
	
	cnt++;
	
	for (int i = 0;i < adj[u].size(); i++)
	{
		int j = adj[u][i];
		
		if(v[j]) continue;
		
		v[j] = 1;
		dfs(j);
		v[j] = 0; 
	}
}

int main()
{
	
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 0;i < m;i ++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	v[1] = 1;
	dfs (1);
	cout << min (cnt, N);
	return 0;
}

F. 自助餐

思路： 01背包模型，输入时间和美味度，排序时间（方便更好操作），处理前N-1道菜，在T-1时间内选择，使用标准的0-1背包DP方法。对于每道菜，我们可以考虑将它作为最后一道菜，然后在剩下的时间（即使超过T-1）内吃完它。详细如下

题解：

#include <bits/stdc++.h>
using namespace std;

const long long N = 3005;
long long n, t, dp[N], ans;
pair <long long , long long> m[N]; 

int main()
{
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	freopen ( "free.in", "r", stdin);
	freopen ( "free.out", "w", stdout);
	cin >> n >> t;
	for(long long i = 1; i <= n;i ++)
	{
		cin >> m[i].first >> m[i].second ;
	}
	sort (m + 1, m + n + 1);
	for (long long i = 1;i <= n;i ++)
	{
		long long a = m[i].first,b = m[i].second;
		if(t - 1 >= 0)
		{
			ans = max(ans, dp[t - 1] + b);
		}
		for(long long j = t - 1;j >= a;j --)
		{
			dp[j] = max(dp[j], dp[j - a] + b);
		}
	}
	ans = max(ans, dp[t - 1]);
	cout << ans;
	return 0;
}