C++题集

# DP问题

# Dice Sum

题目传送门：Atcoder Beginner Contest 248 C Dice Sum (opens new window)
反思：做的时候想到了可能会是DP，但是并没有深入的去想该怎么表示状态，状态转移方程是什么。
思路：
状态表示：dp[i][j]表示前i个数，和为j。
状态转移方程：dp[i][j] = dp[i][j] + (dp[i-1][0]+dp[i][1]+....)

AC代码

#define int long long
using namespace std;
const int mod = 998244353;
const int N = 60,M=2510;
int dp[N][M];
signed main()
{
  int t=1;
  while(t--){
    int n,m,k;cin>>n>>m>>k;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
      for(int j=1;j<=k;j++){
        for(int u=1;u<=m;u++){
          if(j-u>=0){
            dp[i][j] = (dp[i][j] + dp[i-1][j-u]) % mod;
          }
        }
      }
    }
    int ans = 0;
    for(int i=1;i<=k;i++) ans = ( ans + dp[n][i] ) % mod;
    cout<<ans<<endl;
  }
  return 0;
}

# King Bombee

题目传送门：Atcoder Beginner Contest 244 E King Bombee (opens new window)
反思：赛时做的时候就以为纯纯图论，但是自己还是不太熟悉，导致完全没有想到是DP。
题解：
先来思考几个问题：
1.为什么是DP？
ans:取模，奇偶，求方案数
2.怎么表示状态？
ans:用dp[i][j][k],三维数组来表示，dp[i][j][k]表示走到值为i，第j个位置时的数量，k则用0/1表示X出现了奇数次还是偶数次。
3.X出现奇数次和偶数次的状态如何表示？

//如果说这个值和X相等
dp[i][j+1][1/0] += dp[i][j][0/1];
//如果不等呢？
dp[i][j+1][1/0] += dp[i][j][1/0];

AC代码：

点击查看代码

//Ryker
#define int long long
using namespace std;
const int mod = 998244353;
int dp[2010][2010][2];
pair<int, int> v[2010];
signed main() {
	int N,M,K,S,T,X;
//	数列里面要有k+1个点，全部从1-n里面拿
//	要满足起点是s,终点是t，并且A[i]要和A[i+1]相连
//	x出现偶数次
	
//	思路：dp[i][j][k]表示第i个点，序列中第j个位置，x出现的奇数还是偶数次
	cin>>N>>M>>K>>S>>T>>X;
	for(int i=1;i<=M;++i){cin>>v[i].first;cin>>v[i].second;}
	dp[S][0][0]=1;
	for(int i=0;i<K;++i){
		for(int j=1;j<=M;++j){
			int x = v[j].first;int y=v[j].second;
			for(int k=0;k<=1;++k){
//				奇数和偶数的转换
				(dp[x][i+1][k] += dp[y][i][k ^ (X==y)]) %= mod;
				(dp[y][i+1][k] += dp[x][i][k ^ (X==x)]) %= mod;
			}
		}
	}
	cout<<dp[T][K][0]<<endl;
//	x x x z
	return 0;
}

# Choose Elements

题目传送门：Atcoder Beginner Contest 245 C Choose Elements (opens new window)
题意：
给两个数组，A[N],B[N]，然后对每个数（i），你可以选择A[i]或者B[i]，构成一个数组X[N],要求这个数组满足(X[i]-X[i+1])的绝对值小于K

过程：在赛场上始终想的是必须处理到终点，但我并不会处理（，然后想着DFS必然会TLE，一直在这里犹疑不决。

题解：其实这题可以用DP，首先状态表示是DP[i][2]，前i表示走了第i个，第二个维度0表示选A，1表示选B，状态转移的时候注意：如果你前面没走，你后面自然也不能走。
AC代码：

点击查看代码

//Ryker
#define int long long
using namespace std;
const int N = 2e5+10;
int a[N];
int b[N];
int dp[N][2];
int n,k,cnt=0;
signed main() {
	int t=1;
	while(t--){
		cin>>n>>k;
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
		for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
		dp[1][1]=1;dp[1][0]=1;
		for(int i=1;i<n;i++){
			if(abs(a[i]-a[i+1])<=k) if(dp[i][0]) dp[i+1][0] = 1;
			if(abs(a[i]-b[i+1])<=k) if(dp[i][0]) dp[i+1][1] = 1;
			if(abs(b[i]-a[i+1])<=k) if(dp[i][1]) dp[i+1][0] = 1;
			if(abs(b[i]-b[i+1])<=k) if(dp[i][1]) dp[i+1][1] = 1;
		}
		for(int i=1;i<=n;i++){
			if(!dp[i][0]&&!dp[i][1]) break;
			else cnt++;
		}
		if(cnt==n) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

# 搜索问题

# Shortest Good Path(BFS)

题目传送门：Atcoder Beginner Contest 244 F Shortest Good Path (opens new window)

题意：
给你n个点，m条边，无重边，无自环
一个数列如果满足，所有的点都在1-N之间，并且两点之间有边连就可以
还有1/0表示路径经过i点的次数是奇数还是偶数
题解：
1.如何表示？
（1）输入时用一个vector表示，后续用auto得到对应的值。
（2）dis[i][j]中i表示现在的状态「用二进制来表示」，j表示是啥数。
2.如何做？
（1）为什么一开始要u-1，v-1？因为要使用二进制的操作，比如0001，是(1<<0)而不是(1<<1)
（2）BFS，从一个数开始往后搜索，如果没搜过，就继续搜，然后+1，如果搜过了，那就不要了
AC代码：

点击查看代码

//Ryker
#define int long long
using namespace std;
const int N = (1 << 17);
const int INF = 0x3f3f3f3f3f3f3f3f;
int dis[N][17];
vector<int> G[20];
queue<pair<int, int>> Q;
int n,m;
signed main() {
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		u--,v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int M = 1<<n;
	for(int i=0;i<M;i++)
		for(int j=0;j<n;j++)
			dis[i][j]=INF;
//		这里为啥要一开始初始化为1呢？
//		因为我一个数，length为1！
	for(int i=0;i<n;i++){
		dis[1<<i][i]=1;
		Q.push({1<<i,i});
	}
	//		BFS
	while(Q.size()){
		int s = Q.front().first;
		int v = Q.front().second;
		Q.pop();
		for(auto u : G[v]){
			int ns = s ^ (1<<u);
			if(dis[ns][u]<INF) continue;
			dis[ns][u] = dis[s][v] + 1;
//			这就是挑出来的那一个
			Q.push({ns,u});
		}
	}
	int ans = 0;
//	最后是对所有情况进行加总
	for(int i=1;i<M;i++){
		int mm = INF;
		for(int j=0;j<n;j++){
			mm = min(mm,dis[i][j]);
		}
		ans += mm;
	}
	cout<<ans<<endl;
}

# 思维题

# Bracket Sequence Deletion

题目传送门：CodeForces edu 125 C (opens new window)
题意：
1.如果括号可以配对，就可以删去
2.如果括号回文，就可以删去
3.找最短的可以删去的括号对
4.满足两端括号相等时，这一个括号组回文
题解：
1.'))','((','()'这种既是最短，又满足条件，可以直接删去
2.只需要讨论')('这种情况，往后找到第一个')'就可以了。
AC代码：

点击查看代码

//Ryker
#define int long long
using namespace std;
const int N = 5e5+10;
char str[N];
signed main() {
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
//		一开始为0；
		int ans2=0,ans1=0;
		scanf("%s",str+1);
		for(int i=1;i<=n;i++){
			if(str[i] == ')' && str[i+1] == '('){
				int j = i + 1;
				while(j<=n && str[j]!=')') j++;
				if(str[j]==')') ans1++,i=j;
				else {
					ans2 = n-i+1;
					break;
				}
			}
			else if (i != n) {
				ans1++;
				i ++;
			}
			else ans2 = 1;
		}
		cout<<ans1<<" "<<ans2<<endl;
	}
	return 0;
}

# Max Min

题目传送门：Atcoder ABC 247 E (opens new window)
过程：赛时做的时候想的是滑动窗口，但做不出来（
赛后群佬教给了我一种方法==>容斥原理！
首先构造一个函数，这个函数表示区间内的范围的数量。
比如：

//求x到y这个范围中，最大值小于等于x，最小值大于等于y的范围的个数
int getRangeOf(int x,int y)//x最大值，y最小值 
{
	int res = 0;
	for(int i = 1,j = 1;i <= N; ++ i)
	{
		if(a[i] > x || a[i] < y)j = i + 1;
		else res += i - j + 1;
	}
	return res;
}

这样操作之后
再用一个容斥原理（类似于二维前缀和的方式写就可以了！

细节可以看看代码

#include <iostream>
#include <string.h>
//#include <__clang_cuda_cmath.h>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;
const int N1 = 2e5+10;
int N;
int X,Y;
int A[N1];
int rang(int x,int y){
	int res = 0;
	for(int i=1,j=1;i<=N;i++){
		if( A[i] > x || A[i] < y ) j = i + 1;
		else res += i - j + 1;
	}
	return res;
}
signed main(){
	cin>>N>>X>>Y;
	for(int i=1;i<=N;i++) cin>>A[i];
	// Y + 1 因为是底下！
	int ans = rang(X,Y) - rang(X-1,Y) - rang(X,Y+1) + rang(X-1,Y+1);
	printf("%lld\n",ans);
	return 0;
}

# Math

# K-colinear Line

题目传送门：Atcoder 248 E K-colinear Line (opens new window)
题解：
1.一条线就不用考虑了「需要一条线意味着k==1」
2.两个点组成一条线，最多有n*(n-1)/2条线
3.每次挑没走过的，然后判断在不在一条线上可以用向量
「x1,y1」「x2,y2」「x3,y3」 ( y2 - y1 ) / ( x2 - x1 ) = ( y3 - y1 ) / ( x3 - x1 )
这里用的是斜率
得到( y2 - y1 ) * ( x3 - x1 ) = ( y3 - y1 ) * ( x2 - x1 )

AC代码

#define int long long
using namespace std;
const int mod = 998244353;
//const int N = 60,M=2510;
const int N = 310;
int X[N],Y[N];
int f[N][N];
//判断在不在一条直线上
bool strddd(int ze,int on,int tw){
  int a1 = ( X[on] - X[ze] ) * ( Y[tw] - Y[ze] );
  int a2 = ( X[tw] - X[ze] ) * ( Y[on] - Y[ze] );
  return (a1==a2);
}

signed main()
{
  int n,k;cin>>n>>k;
  for(int i=0;i<n;i++) cin>>X[i]>>Y[i];
  if(k==1) {
    printf("Infinity");
    return 0;
  }
  vector<int> list;
  int ans = 0;
  //最多有多少种线
  for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
      f[i][j]=true;
  //开始枚举了
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      if(f[i][j]){
        int cnt = 2;
        list.clear();
        list.push_back(i);
        list.push_back(j);
        for(int ii=j+1;ii<n;ii++){
          if(strddd(i,j,ii)){
            cnt++;
            list.push_back(ii);
          }
        }
        //枚举完记得清理
        for(int ii=0;ii<cnt;ii++)
          for(int jj=ii+1;jj<cnt;jj++)
            f[list[ii]][list[jj]] = false;
        if(cnt >= k) ans++;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

# Polynomial division

题目传送门：Atcoder 245 D (opens new window)
过程：
赛时看这个题：不就是大除法嘛，然后自己做傻眼了，没有想到要减去，要除，然后要找到有效减去位置。
题解：
对于每个不为0的首部，求出A的几倍是C「其实就是B」，把这个值加到B[N]中，然后用一个循环减去C[N]中的值，然后迭代着做。

//Ryker 
#define int long long
const int N = 1e3+10;
int b[N],a[N],c[N];
int n,m;
void solve(){
	int k = n + m;
	//判断这个循环完了没有
	while(k>=0&&!c[k]) k--;
	if(k<0) return;
	//求出了这个前缀
	int ddd = c[k] / a[n];
	b[k-n] += ddd;
	for(int i=0;i<=n;i++) c[i+k-n] -= a[i]*ddd;
	solve();
}
signed main() {
	int t=1;
	while(t--){
		cin>>n>>m;
		for(int i=0;i<=n;i++) cin>>a[i];
		for(int i=0;i<=n+m;i++) cin>>c[i];
		solve();
		for(int i=0;i<=m;i++) cout<<b[i]<<' ';
		cout<<endl;
	}
	return 0;
}

# 贪心问题

# Wrapping Chocolate

题目传送门：Atcoder 245 E (opens new window)
过程：把巧克力放到大小匹配的盒子里，贪心嘛，就是它有两个维度，你怎么贪？
思路：
主要是你如何存，这里用到了vector套pair和multiset的数据结构，sort就很好sort了，先比较vector的第一个维度，然后再比较vector的第二个维度，最后第三个，如果都一样，我盒子的第三个值是1，同样放到前面。
后面的操作就是如果盒子在前面，就放到multiset的数据结构里，如果是巧克力，就进去找有没有合适的盒子。
注意：它这里是用的第二个维度来找，也就是长度，本身宽度是符合要求才会进入multiset的结构中的。

#define int long long
using namespace std;
const int N = 2e5+10;
int n,m;
int a[N],b[N],c[N],d[N];
//难点是选择构造这两个数据结构
vector<array<int,3>> q;
//实现了一个有序数组
multiset<int> s;
signed main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
	for(int i=1;i<=m;i++) scanf("%lld",&c[i]);
	for(int i=1;i<=m;i++) scanf("%lld",&d[i]);
	for(int i=1;i<=n;i++) q.push_back({a[i],b[i],0});
	for(int i=1;i<=m;i++) q.push_back({c[i],d[i],1});
	sort(q.begin(),q.end());
	reverse(q.begin(),q.end());
	for(auto x : q ){
		if(x[2]==1) s.insert(x[1]);
		else {
			auto dd = s.lower_bound(x[1]);
			if(dd==s.end()){
				printf("No\n");
				return 0;
			}
			s.erase(dd);
		}
	}
	printf("Yes\n");
}

# 二分问题

# Range Count Query

题目传送门：Atcoder 248 D Range Count Query (opens new window)
反思：
赛时做的时候只想正常的二分"值"，没有想到可以二分L和R，开一个二维数组用空间换时间
题解：
开一个二维数组，将一样大的值放到同一个维度里，存入这个值的位置，然后二分搜索位置即可。

AC代码

using namespace std;
const int mod = 998244353;
const int N = 2e5+10;
int A[N];
int B[N];
signed main()
{
  int n;cin>>n;
  vector<vector<int>> idx(n+1);
  for(int i=1;i<=n;i++){
    int num;cin>>num;
    idx[num].push_back(i);
  }
  int Q;cin>>Q;
  while(Q--){
    int L,R,X;cin>>L>>R>>X;
    cout<<upper_bound(idx[X].begin(),idx[X].end(), R) - upper_bound( idx[X].begin(),idx[X].end(), L-1)<<endl;
  }
  return 0;
}

# 木材加工

题目传送门：洛谷二分题单木材加工 (opens new window)
反思：
做的时候疯狂写假，始终有一个点会有浮点数错误，唔，还没搞清楚原因（ps:有时这种写法是对的）

while(l<=r){
	int mid = ( l + r ) / 2;
	if(func(mid)>k) r = mid + 1
	else r = mid - 1
}

（有时这种写法是对的，要命哩）

while(l+1<r){
	int mid = ( l + r ) / 2;
	if(func(mid)>k) r = mid;
	else r = mid;
}

::: AC代码

#define int long long
using namespace std;
const int N = 1e6+10;
int n,k;
int A[N];

int func(int ch){
  int ans = 0;
  for(int i=1;i<=n;i++){
    ans += A[i] / ch;
  }
  return ans;
}

signed main()
{
  cin>>n>>k;
  int sum = 0;
  for(int i=1;i<=n;i++) {cin>>A[i];sum+=A[i];}
  // 直接做除法看能分几段咯
  sort(A+1,A+1+n);
  int l = 0, r = A[n];
  // 这里来个边界条件
  while(l + 1<r){
    int mid = ( l + r ) / 2;
    //这里来个具体的，直接得到mid
    //建议使用 l + 1 < r 这样来写
    if(func(mid)>=k) l = mid;
    else r = mid;
  }
  cout<<l<<endl;
  return 0;
}

:::

# 跳石头

题目传送门：洛谷二分题单 P2678 跳石头 (opens new window)
过程：
这道题之前做过一遍了（，现在做还是懵逼的状态，主要是完全不知道怎么二分。
思路：

从答案入手！！！

通过答案来二分，主要是二分函数那一部分的写法，是以一个跳石头的人的思路来看的，
如果说两个石头的之间的距离小于最小距离，那这块石头就要被我丢掉，如果大于捏，直接跳！

AC代码

#define int long long
using namespace std;
const int N = 1e6+10;
int L,n,m;
int A[N];
bool cal(int mid){
  int cnt=0,now=0,i=0;
  while(i<n+1){
    i++;
    if(A[i]-A[now]<mid) cnt++;
    else now = i;
  }
  if(cnt>m) return false;
  return true;
}
signed main()
{
  // l -> 起点到终点的距离
  // n -> 起点和终点之间的岩石数
  // m -> 以及组委会至多移走的岩石数
  cin>>L>>n>>m;
  for(int i=1;i<=n;i++) cin>>A[i];
  int l = 1,r = L;
  A[0] = 0,A[n+1] = L;
  int ans = L;
  while(l+1<r){
    int mid = (l+r)/2;
    if(cal(mid)){
      l = mid;
      ans = mid;
    }else r = mid;
  }
  cout<<ans<<endl;
  return 0;
}

JS每日一题基础数据结构知识

前端知识库@阳树阳树🚀

Choose mode

C++题集

# DP问题

# Dice Sum

# King Bombee

# Choose Elements

# 搜索问题

# Shortest Good Path(BFS)

# 思维题

# Bracket Sequence Deletion

# Max Min

# Math

# K-colinear Line

# Polynomial division

# 贪心问题

# Wrapping Chocolate

# 二分问题

# Range Count Query

# 木材加工

# 跳石头