做网站致富,谷歌怎么做网站优化,wordpress换空间后内页全部404,做网站为什么每年都要续费正题
题面链接:https://www.ybtoj.com.cn/contest/62/problem/4 题目大意 nnn个区间#xff0c;如果第xxx个区间和第yyy个区间有交集那么xxx到yyy直接就有一条边。
求这张图上的所有导出子图中有多少棵树。 解题思路
条件可以转换为这些区间联通并且没有一个位置被333个区间…正题
题面链接:https://www.ybtoj.com.cn/contest/62/problem/4 题目大意
nnn个区间如果第xxx个区间和第yyy个区间有交集那么xxx到yyy直接就有一条边。
求这张图上的所有导出子图中有多少棵树。 解题思路
条件可以转换为这些区间联通并且没有一个位置被333个区间同时覆盖。
那么如果一个包含关系出现在这个图里那么被包含的那个一定是作为叶子的。所以可以按照左端点排序后考虑dpdpdp设fi,jf_{i,j}fi,j表示到第iii个区间作为父节点时右端点扩展到的最远的位置。
那么有以下几种转移。
区间iii直接开一个新根节点不选择区间iii选择iii作为一个被包含在[rx1,j][r_x1,j][rx1,j]这个范围内的区间扩展右端点选择iii作为一个被包含在[rx1,∞][r_x1,\infty][rx1,∞]的区间作为新的父节点
预处理一个nextinext_inexti表示iii往右扩展到的第一个左端点的那个区间的即可O(n2)O(n^2)O(n2)转移 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2100,L4000,XJQ1e97;
struct node{int l,r;
}a[N];
int n,nxt[N*2],f[N][N*2],ans;
bool cmp(node x,node y)
{return x.ly.l;}
int main()
{freopen(graph.in,r,stdin);freopen(graph.out,w,stdout);scanf(%d,n);for(int i1;in;i)scanf(%d%d,a[i].l,a[i].r);sort(a1,a1n,cmp);int cnt0;a[n1].lL1; for(int i1;in1;i)while(cntLcnta[i].l)nxt[cnt]i-1;for(int i1;in;i){(f[i][a[i].r]1)%XJQ;for(int j1;jL;j){(f[i][j]f[i-1][j])%XJQ;if(a[i].lj)continue;if(a[i].rj)(f[nxt[a[i].r]][j]f[i-1][j])%XJQ;if(a[i].rj)(f[nxt[j]][a[i].r]f[i-1][j])%XJQ;}}for(int i1;iL;i)(ansf[n][i])%XJQ;printf(%d\n,ans);
}
