首页 > 其他分享 >三道dp的题解报告

三道dp的题解报告

时间：2024-04-02 20:14:02浏览次数：23  
标签：le 题解 三道 程序 区间 CPU dp define

三道dp的题解报告

圆

题目来源

牛客练习赛122D题
练习赛链接https://ac.nowcoder.com/acm/contest/75768

题面

原题面为中文就直接放原题面截图了。
image

image

解法

事实上，把\(n\)与\(1\)断掉，断环为链，
把原来的线段看成区间，线段相交就是区间之间部分覆盖(区间有重复部分但是没有相互包含关系)。

  • 我个人喜欢用交叉称呼部分覆盖。

本来线段\(\{1,4\}\)和\(\{2,5\}\)相交，也就是区间\([1,4]\)和\([2,5]\)交叉。

那么要使圆优良，也就是用最少的代价删除一些区间使区间之间没有交叉。换而言之，就是留下价值最大的一些区间，这些区间两两不交叉。

一开始不考虑区间之间相互覆盖的情况，只考虑区间之间要么交叉，要么没有公共部分，这种情况很好考虑。设\(dp_i\)是只留下\([1,i]\)之间的区间时能保留的最大价值。那么对于区间\([l,r]\),权值为\(w\)有很显然的状态转移方程$$dp_r=max(dp_{l-1}+w,dp_r)$$
同时还要注意\(dp_r=max(dp_r,dp_{r-1})\)这样就可以了。
那么一开始 \(dp\) 数组置0，把区间按照\(l\)或者\(r\)升序，保证作转移时\(dp_{l-1}\)已经转移完毕即可。

之后在考虑如何处理区间之间的完全覆盖关系。

事实上很有意思的是，处理完全覆盖关系只要我们会做不覆盖的即可。处理无完全覆盖问题的时候我们知道只保留区间\([1,i]\)之间的区间能达到的最大价值，同理的，我们也可以做到求出只保留\([l,r]\)大区间内的小区间的最大价值。

这有什么用呢?举个例子就很好说明。
区间\([1,4](w=1),[2,3](w=2),[5,6](w=3)\),当只考虑无覆盖，最后我们能保留最大5的价值,但是很显然，我们能够保留所有的区间。这个时候，我按照区间\(r\)升序，然后呢，记录\([l+1,r-1]\)内能够留存的最大价值，加在区间\([l,r]\)上。也就是对于区间\([1,4]\)，内部\([1+1,4-1]\)可以包含区间\([2,3](w=2)\),\([1,4](w=1) \to [1,4](w=3)\),这样算上\([1,4](w=3),[5,6](w=3)\),就可以留下6的价值了。
也就是说，本来\(w\)是单个区间的价值，现在经过处理，就变成区间\([l,r]\)能够提供的最大价值。
再换个角度说，就是一个区间的价值会自动算上区间内被完全覆盖的那些区间能留存的最大价值。完全覆盖问题由区间自己计算，无覆盖我们再用\(dp\)计算。

这种做法有一种离散化的区间\(dp\)的味道，可以从区间\(dp\)角度考虑正确性。

事实上非覆盖处理完全覆盖只能做一层包含嵌套，所以当我们处理一个区间的真正价值时，我们得先处理其包含的所有小区间，先处理小的嵌套，大的一层嵌套直接使用小嵌套的结果，就不用一个区间多层嵌套了。这个只要区间做一个排序即可。

点我查看代码 
#include<bits/stdc++.h> 
#define ll long long 
#define int long long
#define mid ((l+r)>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define inf 0x3f3f3f3f 
typedef int LL;
const signed maxn=(signed)1e6+5;
inline LL read(){
	char ch=getchar();bool f=0;LL x=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}
struct poi{
	int l,r,w,id;
}ar[maxn];
bool operator <(poi a,poi b){
	if(a.l!=b.l) return a.l<b.l;
	if(a.r!=b.r) return a.r>b.r;
	return a.id<b.id;
}
ll dp[maxn],tv[maxn];//tv-true value
signed main()
	{	 
		int n=read(),m=read();
		ll all=0;
		for(int i=1;i<=m;++i){
			int l(read()),r(read()),w(read());
			if(r<l) std::swap(l,r);
			all+=w;
			ar[i]=(poi){l,r,w,i};
		}
		std::sort(ar+1,ar+1+m);
		for(int i=m;i;--i){
			for(int j=1;j<=n;++j) dp[j]=0;
			int x=ar[i].l;
			for(int j=i+1;j<=m&&ar[j].l<ar[i].r;++j){
				if(ar[j].l==ar[i].l) continue;
				while(x<ar[j].l-1) dp[x+1]=std::max(dp[x],dp[x+1]),++x;
				dp[ar[j].r]=std::max(dp[ar[j].l-1]+tv[j],dp[ar[j].r]);
			}
			while(x<ar[i].r-1) dp[x+1]=std::max(dp[x],dp[x+1]),++x;
			tv[i]=ar[i].w+dp[ar[i].r-1];
		}
		for(int i=0;i<=n;++i) dp[i]=0;
		int x=0;
		for(int i=1;i<=m;++i){
			while(x<ar[i].l-1) dp[x+1]=std::max(dp[x],dp[x+1]),++x;
			dp[ar[i].r]=std::max(dp[ar[i].l-1]+tv[i],dp[ar[i].r]);
		}
		while(x<n) dp[x+1]=std::max(dp[x],dp[x+1]),++x;
		printf("%lld\n",all-dp[n]);
		return 0;
	}

Matrix Fraud

题目来源

2024-3-24湖南多校G，为搬题场。
本场搬自Pacific NorthWest February,24 2024
pacnw的比赛所有题面，test，checker，validator和std都可以下载
链接http://www.acmicpc-pacnw.org/results.htm

题目翻译

给定一个\(n\)行，\(m\)列的矩阵，元素为\(0/1\),我们一次操作可以把一个\(0\)变\(1\)或者\(1\)变\(0\)。问最少的操作次数使矩阵满足下列条件

  1. 每一行和每一列都至少有一个\(1\)
  2. 每一行的\(1\)都连续出现。即对于行\(i\),第一个\(1\)出现在列\(s_i\),最后一个1出现在列\(t_i\),此行，只有列落入区间\([s_i,t_i]\)时值为1，其余为0。
  3. \(\forall i\in N,(i\in[1,n-1]) \to (s_i \le s_{i+1})\&(t_i \le t_{i+1})\)
  • 时限 2s,空间2G(pacnw任何问题都开2G大小，并不是此问题对空间有特殊需求)。
  • \(n\times m \le 2e5\)

解法

  • 题解用变量名和代码用的不一样，并且有变量名区分大小写，可能会很混乱，注意观察。

首先挖掘一下题面信息。

随便画一下一个满足条件的矩阵，绿色的是1,黄色的为0。

可以发现，每一列的\(1\)也是连续的。这显然是一个性质。也就是说，对行的要求和对列的要求是一致的，矩阵先转置一下再处理也满足题目要求。
而且为了使每一列都有1,对于每一行\(i\),\(s_{i+1} \le t_i+1\)，不然第\(t_i+1\)列就没有1了，因为\(\forall j \le i,t_j \le t_i+1\),前面几行\(1\)区间已经结束了，\(\forall j>i,s_j \ge s_{i+1}>t_i\)，后面几行\(1\)区间还没开始。

考虑状态转移。

那么设\(dp_{r,s,t}\)代表第\(r\)行，\(s_i=s,t_i=i\)并且第\(1\)行到第\(r-1\)行都满足第三个条件，完成这些条件需要的最小操作数。
记录\(cnt_{r,c}\)为第\(r\)行,第\(1\)列到第\(c\)列中所给矩阵中\(1\)的个数
那么当\(s \le s',t \le t',s' \le t+1\)有转移

\[dp_{r+1,s',t'}\gets dp_{r,s,t}+cnt_{r+1,m}+(t'-s'+1)-2\times (cnt_{r+1,t'}-cnt_{r+1,s'-1}) \]

但每一行有\(m^2\)个区间，这么做\(O(m^4)\),复杂度爆炸。

所以考虑做一些处理降低复杂度。从转移条件入手。首先我们按照\(s(s')\)升序处理(意思就是先把第一行的\(dp_{r,1,t}\)的影响记录下来，再计算\(dp_{r+1,1,t'}\),再开始做\(s=2,s'=2\))，对于同一个\(s\),根据\(t\)的不同，开一个数组(桶)\(ltr\)，根据\(t\)的大小放入不同的桶中，就像这样\(ltr[x]=min\{dp_{r,s,t}\}(t=x)\)，又因为按照\(s\)升序处理，假设处理完第\(L\)列，实际上是这样\(ltr[x]=min\{dp_{r,s,t}\}(t=x\&\&s \le L=s')\),然后可以发现\(s \le s'\)已经满足，只要\(t \le t',s' \le t+1\),也就是\(s'-1 \le t \le t'\)即\(dp_{r=1,s',t'}=min\{ltr[x](s'-1 \le x \le t')\}+(cnt......)\)。\(min\{ltr[x](s'-1 \le x \le t')\}\)可以通过前缀和式计算\(O(m)\)得到
那么就这样通过升序处理，开桶，再通过前缀和就可以\(O(m^2)\)完成转移。
可以看一下代码感受一下

//r是总行数，c是总列数,L,R是枚举区间左右端点
//dp的行维度被滚动优化掉了，只剩s,t
for(int i=2;i<=r;++i){//第i-1行到第i行的转移
			for(int R=0;R<=c;++R) ltr[R]=r*c+1;
			for(int L=1;L<=c;++L){
				for(int R=L;R<=c;++R) ltr[R]=std::min(ltr[R],dp[L][R]);
				int mn=ltr[L-1];
				for(int R=L;R<=c;++R){
					mn=std::min(mn,ltr[R]);
					dp[L][R]=mn+cnt[i][c]-2*(cnt[i][R]-cnt[i][L-1])+(R-L+1) ;
				}
			}
		}

这样代码复杂度\(O(n\times m^2)\)但是当\(n\)很小，\(m\)很大时仍然会超时，所以当\(n>m\)时将矩阵转置，复杂度变为\(O(n\times m\times min(n,m))\le O((n\times m)^{1.5})\),这样复杂度才可以接受。

点我查看全部代码 
#include<bits/stdc++.h> 
#define ll long long 
//#define int long long
#define mid ((l+r)>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define inf 0x3f3f3f3f 
typedef int LL;
const signed maxn=(signed)1e6+5;
inline LL Read(){
	char ch=getchar();bool f=0;LL x=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}
int ltr[505];
int dp[505][505];
signed main()
	{	 
		int r=Read(),c=Read();
		std::vector<std::vector<int>> ar,cnt;
		if(c>r){
			ar.resize(c+3);cnt.resize(c+3);
			for(int j=1;j<=c;++j) ar[j].resize(r+3);
			for(int j=1;j<=c;++j) cnt[j].resize(r+3);
			for(int i=1;i<=r;++i){
				for(int j=1;j<=c;++j)
					scanf("%1d",&ar[j][i]);
			}
			std::swap(r,c);
		}
		else{
			ar.resize(r+3);cnt.resize(r+3);
			for(int i=1;i<=r;++i) ar[i].resize(c+3);
			for(int i=1;i<=r;++i) cnt[i].resize(c+3);
			for(int i=1;i<=r;++i){
				for(int j=1;j<=c;++j){
					scanf("%1d",&ar[i][j]);
				}
			}
		}
		for(int i=1;i<=r;++i){
			cnt[i][0]=0;
			for(int j=1;j<=c;++j){
				cnt[i][j]=cnt[i][j-1]+ar[i][j];
			}
		}
		for(int R=1;R<=c;++R){
			dp[1][R]=cnt[1][c]-2*cnt[1][R]+R;
		}
		for(int L=2;L<=c;++L){
			for(int R=L;R<=c;++R){
				dp[L][R]=r*c;
			}
		}
		for(int i=2;i<=r;++i){
			for(int R=0;R<=c;++R) ltr[R]=r*c+1;
			for(int L=1;L<=c;++L){
				for(int R=L;R<=c;++R) ltr[R]=std::min(ltr[R],dp[L][R]);
				int mn=ltr[L-1];
				for(int R=L;R<=c;++R){
					mn=std::min(mn,ltr[R]);
					dp[L][R]=mn+cnt[i][c]-2*(cnt[i][R]-cnt[i][L-1])+(R-L+1) ;
					//printf("%d ",tp[L][R]);
				}
				//putchar('\n');
			}
		}
		int fin=r*c;
		for(int L=1;L<=c;++L){
				fin=std::min(dp[L][c],fin);
		}
		printf("%d\n",fin);
		return 0;
	}

Hot Start up

题目链接

此题源自codeforces round 854 D2
https://codeforces.com/problemset/problem/1799/D2

题目翻译

你有两个CPU，有\(k\)个程序，有一串长为\(n\)的程序序列(有些程序会在序列中出现多次)，要求按照序列顺序串行执行这些程序，可以自由选择使用哪一个CPU完成(因为程序要串行完成，两个CPU不会同时工作)。正常情况下运行一个程序\(i\)花费时间\(cold_i\),但若是CPU上一个执行的程序仍然是\(i\),那么再执行此程序就只会花费\(hot_i\)秒(\(hot_i \le cold_i\))。问，给定的程序序列和每个程序的\(i\)两种处理时间\(cold_i,hot_i\)，最少需要的处理时间是多少。

  • 时限 \(1s\),空间\(512\)MB。
  • \(1\le n,k\le 3e5,1\le hot_i\le cold_i\le 1e9\)

解法

这是一道我以前做过的题目，非常的有\(dp\)感。以前和现在各有一种解法。先讲我以前的做法。

以前的做法

设\(dp_{i,f}\)为做完第\(i\)个程序时要花费的最小代价，\(f=0\)时为第\(i\)个程序和前一个程序在同一个CPU上运行，\(f=1\)就是不在用一个CPU上运行。

如果不考虑热启动(花费\(hot_i\)秒)，或者只考虑一个程序被连续执行多次导致的热启动，状态转移很简单，照着前一个程序是什么，无脑转移即可，就不列出来了。
然后考虑全部情况，需要一个性质，如果第\(i\)个执行的程序想要热启动，那么就是贪心的找到最近的一次执行的同一个程序，使这两次执行之间的所有程序都在另外一个CPU上运行。
记\(lst_i\)为最近的被执行的同一个程序,若\(lst_i=i-1\)就特判掉，如果是第一次出现,不存在\(lst_i\)就忽略。这样保证了\(lst_i\)存在且与\(i\)不相邻。设\(cssum_{l,r}\)为第\(l\) ~ \(r\)个程序都和前一个程序在同一个CPU执行，这几个程序花费的时间(\(l>r\)时值为\(0\))。
那么有状态转移

\[dp_{i,1}\gets dp_{lst_i+1,1}+cssum_{lst_i+2,i-1} \]

核心就是这个依靠\(cssum\)实现的转移。
代码很简洁，直接上代码。唯一要说的一点，\(cssum\)是一个区间查询问题，可以记录前缀和解决，不必开二维。总复杂度\(O(n)\)。

点我查看代码 
#include<bits/stdc++.h> 
#define ll long long 
#define int long long
#define mid ((l+r)>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define inf 0x3f3f3f3f
#define pii pair<int,int> 
#define MK(a,b) make_pair(a,b)
#define N 300005
using namespace std;
int n,m,k;
const int mod=(int)1e9+7;
const int g=5;
inline int read(){
	char ch=getchar();bool f=0;int x=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}
int ar[N],cold[N],hot[N];
int dp[N][2];//0,same as pre,1,dif
int lst[N],cssum[N];
signed main()
	{	int i,j,u,v;
		int l,r,w,t=1;
		int a,b,c,d;
		t=read();
		while(t--){
			n=read();k=read();
			for(i=1;i<=n;i++) ar[i]=read();
			for(i=1;i<=k;i++) cold[i]=read();
			for(i=1;i<=k;i++) hot[i]=read();
			for(i=1;i<=k;i++) lst[i]=-1;
			cssum[0]=0;
			for(i=1;i<=n;i++) 
				if(ar[i]==ar[i-1])cssum[i]=cssum[i-1]+hot[ar[i]];
				else cssum[i]=cssum[i-1]+cold[ar[i]];
			dp[1][1]=cold[ar[1]];
			dp[1][0]=cold[ar[1]];
			lst[ar[1]]=1;
			for(i=2;i<=n;i++){
				if(lst[ar[i]]==-1){
					dp[i][1]=dp[i][0]=min(dp[i-1][0],dp[i-1][1])+cold[ar[i]];
				}
				else if(lst[ar[i]]==i-1){
					dp[i][1]=min(dp[i-1][0],dp[i-1][1])+cold[ar[i]];
					dp[i][0]=min(dp[i-1][0],dp[i-1][1])+hot[ar[i]];
				}
				else{
					dp[i][0]=min(dp[i-1][0],dp[i-1][1])+cold[ar[i]];
					dp[i][1]=hot[ar[i]]+dp[lst[ar[i]]+1][1]+cssum[i-1]-cssum[lst[ar[i]]+1];
					dp[i][1]=min(dp[i][1],dp[i][0]);
				}
				lst[ar[i]]=i;
			}
			printf("%lld\n",min(dp[n][0],dp[n][1])); 
		}
		return 0;
	}
/*
*/
 
现在的做法

\(dp\)的核心之一就是抓住问题的本质，忽略掉无关信息，把多种情况统合，保留最优解减少情况数量减小复杂度。

本题\(dp\)状态可以如此设置:\(dp_{i,x,y}\)代表做完第\(i\)个程序，两个CPU上次执行的程序分别为\(x,y\)时所需的最小代价。不过即使最后滚动优化掉\(i\)这一维度，这个仍然是\(O(n^2)\)的状态数量，肯定不行，发现第\(i\)个程序本身就一定是CPU最后执行的程序之一，那么就可以减去一维。

设\(dp_{i,x}\)代表做完第\(i\)个程序，另一个CPU上次执行的程序为\(x\)时所需的最小代价。不过这样样每做一个程序都会增加代价，每一次都要\(O(n)\)转移，复杂度不行。

这时候就可以施展一些奇技淫巧，改一下\(dp\)代表的值，想办法减少状态更新的次数。

设\(dp_x\)代表做完当前程序，另一个CPU上次执行的程序分别为\(x\)时可以节省的最大代价。考虑两种情况，如果第\(i\)个程序\(a_i\)和第\(i-1\)个程序\(a_{i-1}\)相同，\(a_i,a_{i-1}\)一定会运行在同一个CPU,直接用变量额外记录\(a_i\)节省的代价，不要\(O(n)\)转移。剩余的情况就是\(a_i \ne a_{i-1}\)，如果和前一个程序运行在同一个CPU，另一个CPU最后的程序不变，代价也不变，不作转移。如果运行在不同的CPU，那么另一个CPU最后运行的就是\(a_{i-1}\)。记录\(dp\)数组中最大节省代价为\(mx\),如果要求\(a_i\)热启动，就只能从\(dp_{a_i}\)转移，如果没有要求热启动，就可以挑选最大节省代价转移，也就是从\(mx\)转移。
总而言之，有状态转移$$dp_{a_{i-1}}=max(dp_{a_{i-1}},dp_{a_i}+cold_{a_i}-hot_{a_i},mx)$$

核心就是这样，复杂度\(O(n)\)。答案就是总价值减去最大节省价值。剩下的就是代码细节。稍微提一下，我直接预处理了程序序列，把一个程序连续多次执行预处理掉了，这样就不用分类讨论。

点我查看代码 
#include<bits/stdc++.h> 
#define ll long long 
#define mid ((l+r)>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define inf 0x3f3f3f3f
#define pii pair<int,int>
const signed maxn=3e5+5;
typedef int LL;
inline LL Read(){
	char ch=getchar();bool f=0;LL x=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f)x=-x;return x;
}
int n,m,k;
ll dp[maxn];
int ar[maxn],br[maxn],tn;
int hot[maxn],cold[maxn];
signed main()
	{	
		LL T=Read();
		while(T--){
			m=Read();k=Read();
			for(int i=1;i<=m;++i) br[i]=Read();
			for(int i=1;i<=k;++i) cold[i]=Read();
			for(int i=1;i<=k;++i) hot[i]=Read();
			ll Cost=cold[br[1]];
			ar[1]=br[1];n=1;
			for(int i=2;i<=m;++i){
				if(ar[n]==br[i]) Cost+=hot[br[i]];
				else{
					ar[++n]=br[i];Cost+=cold[br[i]];
				}
			}
			for(int i=1;i<=k;++i) dp[i]=-inf;
			ll mx=0;
			for(int i=2;i<=n;++i){
				dp[ar[i-1]]=std::max({dp[ar[i-1]],dp[ar[i]]+cold[ar[i]]-hot[ar[i]],mx});				
				mx=std::max(mx,dp[ar[i-1]]);
			}
			printf("%lld\n",Cost-mx);
		}
		return 0;
	}

标签：le,题解,三道,程序,区间,CPU,dp,define
From： https://www.cnblogs.com/LOOP-0/p/18111393

相关文章

  • 题解：AT_abc176_e [ABC176E] Bomber
    分析我们可以用\(hf\)和\(wf\)分别储存每行的目标数及每列的目标数。然后我们可以贪心：若想摧毁最多的目标，则选定的位置所在的行是所有行中目标最多的，所在的列是所有列中目标最多的（感性理解一下）。但是，选定的位置也可能有一个目标。在统计摧毁的目标数时，该目标被算了两次......
  • 数位 dp / lianggj 让你学小专题应该怎么办
    P4999#include<bits/stdc++.h>#defineintlonglong#defineup(i,l,r)for(inti=l;i<=r;++i)#definedn(i,r,l)for(inti=r;i>=l;--i)usingnamespacestd;constintN=20,M=9*18+5,P=1e9+7;intt,l,r,f[N][M],a[N],len,ans;/*Q：查询......
  • P2143 [JSOI2010] 巨额奖金 题解
    P2143[JSOI2010]巨额奖金题解矩阵树定理+Kruskal最小生成树计数。思路MST都是喵喵题。引理1：所有合法的权值相同边的连边方案，得到的连通块情况是相同的。感性理解：如果不相同意味着至少有一条边可以连通一对连通块。所以我们可以这么做：先跑Kruskal标记树边，然后枚举......
  • 状压dp板子（cf div4 #937）
    #include<bits/stdc++.h>usingnamespacestd;intn;vector<int>v[20];stringa[20],b[20];booldp[500010][20];voiddfs(ints,intnow){dp[s][now]=true;for(autonxt:v[now]){if(s&(1<<nxt))continue;......
  • RudderStack 开源CDP 平台
    RudderStack是基于golang开发的开源CDP平台包含的特性eventstreaming 支持16+sdkprofiles 快速基于dw或者datalake构建客户画像reverseetl 支持反向etl数据治理 支持增强追踪，方便对于一些隐私数据的管理event转换 支持基于js以及python进行数据修复200+......
  • P1967 [NOIP2013 提高组] 货车运输 题解
    P1967[NOIP2013提高组]货车运输原题地址思路：由于题目要求的是使两点之间的最小边权最大，所以可以构造最大生成树（最大生成树一定是最大瓶颈生成树，而瓶颈生成树上两点之间的路径，在原图中的所有路径中，最小边权仍然最大，即满足题目要求，详见https://oi-wiki.org/graph/mst/#性质），......
  • Golang | Leetcode Golang题解之第4题寻找两个正序数组的中位数
    题目：题解：funcfindMedianSortedArrays(nums1[]int,nums2[]int)float64{iflen(nums1)>len(nums2){returnfindMedianSortedArrays(nums2,nums1)}m,n:=len(nums1),len(nums2)left,right:=0,mmedian1,median2:=0,0......
  • CF1935D Exam in MAC 题解
    ExaminMAC题意\(t\)组数据。给定一个大小为\(n\)的集合\(s\)和一个整数\(c\)，保证\(0\leqslants_i\leqslantc(1\leqslanti\leqslantn)\)。求有多少对整数数对\((x,y)\)，满足：\(0\leqslantx\leqslanty\leqslantc\)。\(x+y\notins\)且\(y-x\not......
  • 2024最新一线互联网大厂常见高并发面试题解析
    面试官：临界区是什么？答：临界区用来表示一种公共资源或者说是共享资源，可以被多个线程使用。但是每一次，只能有一个线程使用它，一旦临界区资源被占用，其他线程要想使用这个资源，就必须等待。比如，在一个办公室里有一台打印机，打印机一次只能执行一个任务。如果小王和小明同时需要打......
  • 树形DP+树上路径贡献
    题目一棵树有n个节点，每个节点都同有一个符号+或者-，表示该节点是正极节点还是负极节点。如果从正极走到负极，或者从负极走到正极，都会受到1点伤害。现在需要知道走过所有路径后会受到的总伤害是多少？树上任意2点存在唯一的路径。需要计算所有任意2点的路径的伤害和。注意：从u到，和从v......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99