logoChat01.ai

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

बनाया गया: 8 जुलाई 2026

का उपयोग करके उत्तर दिया गया GPT-5.5 Thinking द्वारा Chat01

प्रश्न

#include <bits/stdc++.h>
using namespace std;
const int MAXN=200005;
const int MOD=1e9+7;
int n,Q,s,lef[MAXN],idx,rtlef;
bool visDFS[2000005],cget[MAXN],islf[2000005];
long long f[2000005],cnt[2000005],nodeval[2000005];
vector <int> v[2000005];
vector <long long> w[2000005];
struct Tree
{
int l,r,ls,rs;
}tr[2000005];
struct Node
{
int l,r,id;
}a[MAXN];
int idlf[2000005];
bool cmp(Node x,Node y) {
return x.l<y.l;
}
int Buildgraph1(int fa,int l,int r)
{
int p=++idx;
tr[p].l=l,tr[p].r=r;
if (l==r) {
lef[l]=p;
nodeval[p]=-a[l].l;
islf[p]=1;
idlf[p]=l;
} else {
nodeval[p]=0;
}
if (fa!=0)
{
v[fa].push_back(p);
w[fa].push_back(nodeval[p]);
}
if (l==r) return p;
int midd=(l+r)/2;
tr[p].ls=Buildgraph1(p,l,midd);tr[p].rs=Buildgraph1(p,midd+1,r);
return p;
}
void add(int p,int vto,int ll,int rr,long long ww,int opt)
{
if (ll<=tr[p].l&&tr[p].r<=rr)
{
if (opt==1)
{
v[vto].push_back(p);
w[vto].push_back(ww+nodeval[p]);
}
else
{
v[p].push_back(vto);
w[p].push_back(ww+nodeval[vto]);
}
return;
}
int midd=(tr[p].l+tr[p].r)/2;
if (ll<=midd) add(tr[p].ls,vto,ll,rr,ww,opt);
if (midd<rr) add(tr[p].rs,vto,ll,rr,ww,opt);
}
void dfs(int u)
{
if (visDFS[u]) return;
visDFS[u]=1;
f[u]=2e18;
cnt[u]=0;
if (islf[u])
{
int k=idlf[u];
if (!cget[k])
{
f[u]=a[k].r;
cnt[u]=1;
}
}
for (int i=0;i<v[u].size();i++)
{
int vto=v[u][i];
long long weight=w[u][i];
dfs(vto);
if (f[vto]==2e18) continue;

text
	if (f[vto]+weight<f[u])
	{
		f[u]=f[vto]+weight;
		cnt[u]=cnt[vto];
	}
	else if (f[vto]+weight==f[u])
	{
		cnt[u]=(cnt[u]+cnt[vto])%MOD;
	}
}

}
void dijk()
{
long long minans=2e18;
long long answ=0;

text
for (int i=1;i<=n;i++)
{
	dfs(lef[i]);
	if (f[lef[i]]<minans)
	{
		minans=f[lef[i]];
		answ=cnt[lef[i]];
	}
	else if (f[lef[i]]==minans)
	{
		answ=(answ+cnt[lef[i]])%MOD;
	}
}
cout<<answ<<'\n';

}
int main()
{
cin>>n;
for (int i=1;i<=n;i++) {
cin>>a[i].l>>a[i].r;
a[i].id=i;
}
sort(a+1,a+1+n,cmp);
rtlef=Buildgraph1(0,1,n);
for (int i=1;i<=n;i++) {
int lget=a[i].r;
int leftt=1,rightt=n;
int target=0;
while (leftt<=rightt) {
int midd=(leftt+rightt)/2;
if (a[midd].l<=lget) {
target=midd;
leftt=midd+1;
}
else rightt=midd-1;
}
if (target>=1) {
cget[i]=1;
add(rtlef,lef[i],1,target,a[i].r,1);
} else {
cget[i]=0;
}
}
dijk();
return 0;
}https://www.luogu.com.cn/problem/CF1197E 最小限度DEBUG代码，不加注释，保留代码风格与格式

विचार

undefined

विचार

Verifying handling of equal items in path selection

For identical items in the graph, order matters when selecting among equal inner items. If two dolls have the same inner but different outer values, the valid choices depend on the chains they form. Since out > in, two cannot be part of the same chain. I'll verify this by checking random tests and C++ implementation.

Thought for 3m 7s

उत्तर

题面输入是 out_i in_i，嵌套条件是 out_i <= in_j，所以这里改成 r=out, l=in 后按 l 排序，再做 DAG 最短路计数。(luogu.com.cn)

cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN=200005;
const int MOD=1e9+7;
int n,Q,s;
long long f[MAXN],cnt[MAXN];
vector <int> v[MAXN];
vector <long long> w[MAXN];
struct Node
{
	int l,r,id;
}a[MAXN];
bool cmp(Node x,Node y) {
	return x.l<y.l;
}
void dijk()
{
	for (int i=0;i<=n;i++)
	{
		f[i]=2e18;
		cnt[i]=0;
	}
	f[0]=0;
	cnt[0]=1;
	for (int i=0;i<=n;i++)
	{
		for (int j=0;j<v[i].size();j++)
		{
			int vto=v[i][j];
			long long weight=w[i][j];
			if (f[i]+weight<f[vto])
			{
				f[vto]=f[i]+weight;
				cnt[vto]=cnt[i];
			}
			else if (f[i]+weight==f[vto])
			{
				cnt[vto]=(cnt[vto]+cnt[i])%MOD;
			}
		}
	}
	long long minans=2e18;
	long long answ=0;
	for (int i=1;i<=n;i++)
	{
		if (a[i].r>a[n].l)
		{
			if (f[i]<minans)
			{
				minans=f[i];
				answ=cnt[i];
			}
			else if (f[i]==minans)
			{
				answ=(answ+cnt[i])%MOD;
			}
		}
	}
	cout<<answ<<'\n';
}
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>a[i].r>>a[i].l;
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	for (int i=0;i<n;i++) {
		v[i].push_back(i+1);
		w[i].push_back(a[i+1].l-a[i].l);
	}
	for (int i=1;i<=n;i++) {
		int leftt=1,rightt=n;
		int target=n+1;
		while (leftt<=rightt) {
			int midd=(leftt+rightt)/2;
			if (a[midd].l>=a[i].r) {
				target=midd;
				rightt=midd-1;
			}
			else leftt=midd+1;
		}
		if (target<=n) {
			v[i].push_back(target);
			w[i].push_back(a[target].l-a[i].r);
		}
	}
	dijk();
	return 0;
}

इस प्रश्नोत्तर को साझा करें