C.LongestSimpleCycle(贪心)-创新互联

Problem - 1476C - Codeforces

在资阳等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供成都做网站、网站建设、外贸营销网站建设网站设计制作按需求定制制作,公司网站建设,企业网站建设,品牌网站制作,全网营销推广,外贸网站制作,资阳网站建设费用合理。

你有n条链，第i条链由ci个顶点组成。每条链中的顶点沿链从1到ci独立编号。换句话说，第i条链是由ci个顶点和连接第j个和(j+1)个顶点的(ci-1)条边组成的无向图，每1≤j

现在你决定以下列方式将各链合并为一个图。

第一条链被跳过。
第i条链的第1个顶点通过一条边与第(i-1)条链的第i个顶点相连。
第i条链的最后一个(ci-th)顶点与第(i-1)条链的bi-th顶点以边连接。
第一个测试案例的图片。虚线是联合过程中添加的边。
计算结果图中最长的简单循环的长度。

一个简单的循环是一个链，其中第一个和最后一个顶点也是相连的。如果你沿着简单循环走，这个循环的每个顶点都会被精确访问一次。

输入
第一行包含一个整数t（1≤t≤1000）--测试案例的数量。

每个测试案例的第一行包含一个整数n（2≤n≤105）--你的链的数量。

每个测试用例的第二行包含n个整数c1,c2,...,cn (2≤ci≤109) - 相应链中顶点的数量。

每个测试用例的第三行包含n个整数a1,a2,...,an（a1=-1；1≤ai≤ci-1）。

每个测试案例的第四行包含n个整数b1,b2,...,bn（b1=-1；1≤bi≤ci-1）。

a1和b1都等于-1，它们在图的构建中并没有使用，只是为了索引的一致性而给出。我们保证所有测试案例的n之和不超过105。

输出
对于每个测试案例，打印最长的简单循环的长度。

例子
inputCopy
3
4
3 4 3 3
-1 1 2 2
-1 2 2 3
2
5 6
-1 5
-1 1
3
3 5 2
-1 1 1
-1 3 5
输出拷贝
7
11
8
注意
在第一个测试案例中，最长的简单循环显示在下面。

我们不能用第一条链来增加它，因为在这种情况下，它不会是简单的--第二条链上的顶点2会破坏简单性。

题解:

设sum为此时的长度

x为(a[i],b[i])最靠近1,y为最靠近c[i]的

我们从右往左枚举右边界,如果sum + x + c[i] - y< c[i]

说明此时重新枚举的c[i]为右边界更优,或者此时x == y说明左边界已经走到头需重新枚举右边界

sum = c[i]

或者如果sum + x + c[i] - y >= c[i]

sum肯定要加上这一部分

#include#include
#include#include#include#include#include#include#includeusing namespace std;
#define int long long
int a[100050];
int b[100050];
int c[100050]; 
void solve()
{
	int n;
	cin >>n;
	for(int i = 1;i<= n;i++)
	cin >>c[i];
	for(int i = 1;i<= n;i++)
	cin >>a[i];
	for(int i = 1;i<= n;i++)
	{
		cin >>b[i];
	}
	int x = 1,y = c[n];
	int sum = 0,ans = 0;
	for(int i = n;i >1;i--)
	{
		if(x == y||sum + x + c[i]-y< c[i])
		{
			sum = c[i];
		}
		else
		{
			sum += x + c[i] - y + 1;//+1是因为两条链之间要连边
		}
		y = max(a[i],b[i]);
		x = min(a[i],b[i]);
		ans = max(ans,sum + y -x +1);//+1是因为两条链之间要连边
	}
	cout<< ans<<"\n";
	
}
//0 2 2
signed main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	int t = 1;
	cin >>t;
    while(t--)
	{

		solve();
	} 
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章标题：C.LongestSimpleCycle(贪心)-创新互联
分享链接：http://ybzwz.com/article/dhciep.html

C.LongestSimpleCycle(贪心)-创新互联

其他资讯