首页 > 其他分享 >Codeforces Round #816 (Div. 2)

Codeforces Round #816 (Div. 2)

时间：2022-09-07 20:23:26浏览次数：76  
标签：const int dis Codeforces stk Div include 816 define

Preface

早上7：20起来早自习，结果不知道背什么遂刷了好久知乎……

下午只有一个思修课，一边划水一遍写题，堪堪做了ABCD

晚上据说有C语言的程序设计？又可以摸鱼了好耶

A. Crossmarket

不难发现如果要跳跃那么一定是跳过较长的那条边，直接做即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n,m;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d",&n,&m); --n; --m;
		if (!n&&!m) { puts("0"); continue; }
		printf("%lld\n",1LL*n+m+min(n,m)+1);
	}
	return 0;
}

B. Beautiful Array

若\(s<b\times k\)则显然不合法，不妨设\(left=s-b\times k\)，显然若\(left>(k-1)\times n\)则亦不合法

否则必然存在一种构造方案，随便分一下就好了

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,k,b; long long s,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%d%d%lld",&n,&k,&b,&s); long long left=s-1LL*k*b;
		if (left<0) { puts("-1"); continue; }
		if (left>1LL*(k-1)*n) { puts("-1"); continue; }
		int p=b/n,q=b%n; for (i=1;i<=n;++i) a[i]=1LL*p*k;
		for (i=1;i<=q;++i) a[i]+=k; for (i=1;i<=n&&left>0;++i)
		if (left>k-1) a[i]+=k-1,left-=k-1; else a[i]+=left,left=0;
		for (i=1;i<=n;++i) printf("%lld%c",a[i]," \n"[i==n]);
	}
	return 0;
}

C. Monoblock

刚开始还在考虑维护连续的区间，以为要写成类似于珂朵莉树那样的东西，后来发现只要维护端点即可

我们找出所有连续段的分界点\(i\)，满足\(a_i\ne a_{i+1}\)，考虑分别考虑每个分界点对答案的贡献

很明显一个区间的答案就是这个区间内的分界点个数加一，因此每个分界点\(i\)的贡献就是\(i\times (n-i)\)

修改的时候讨论一下即可，最后注意要加上区间总数来统计加一的贡献

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,m,a[N],x,y; long long ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=1;i<=n;++i) if (a[i]!=a[i+1]) ans+=1LL*i*(n-i);
	for (i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y); if (a[x]!=a[x+1]) ans-=1LL*x*(n-x);
		if (x>1&&a[x-1]!=a[x]) ans-=1LL*(x-1)*(n-x+1);
		a[x]=y; if (a[x]!=a[x+1]) ans+=1LL*x*(n-x);
		if (x>1&&a[x-1]!=a[x]) ans+=1LL*(x-1)*(n-x+1);
		printf("%lld\n",ans+1LL*n*(n+1)/2LL);
	}
	return 0;
}

D. 2+ doors

刚开始脑抽了没维护无关点WA了好久，还以为算法假了

首先不难发现我们可以对每一位分别考虑，保证在这一位下字典序的最小，综合起来即可得到全局的最小

考虑若某个关系\((i,j)\)的这一位的数字为\(d\)，则：

  • \(d=0\)，则\(i,j\)的这一位上都必须为\(0\)
  • \(d=1\)，则\(i,j\)的这一位上至少有一个为\(1\)

第一种情况直接做即可，对于第二种情况，我们给\(i,j\)之间连边，最后按字典序处理，若某个点选\(0\)那么与之相邻的所有点都要选\(1\)

总复杂度\(O((n+m)\log a_i)\)

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int n,q,x[N<<1],y[N<<1],z[N<<1],a[N],col[N]; vector <int> v[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,k; for (scanf("%d%d",&n,&q),i=1;i<=q;++i) scanf("%d%d%d",&x[i],&y[i],&z[i]);
	for (k=29;~k;--k)
	{
		for (i=1;i<=n;++i) col[i]=-1,v[i].clear();
		for (i=1;i<=q;++i)
		{
			int w=(z[i]>>k)&1; if (w&&x[i]!=y[i])
			v[x[i]].push_back(y[i]),v[y[i]].push_back(x[i]); else col[x[i]]=col[y[i]]=w;
		}
		for (i=1;i<=n;++i) if (!col[i])	for (int j:v[i]) col[j]=1;
		for (i=1;i<=n;++i) if (~col[i]) a[i]|=(col[i]<<k);
		else { col[i]=0; for (int j:v[i]) col[j]=1; }
	}
	for (i=1;i<=n;++i) printf("%d ",a[i]);
	return 0;
}

E. Long Way Home

被搞精度了调了1h过了Test6，然后又挂了好久的Test8，最后发现由于\(dis\)数组初值赋太大了乘法的时候爆负了。。。

题目本身还是非常套路的，我们考虑先用Dijkstra求出到每个点的最短路，然后考虑如果只有一次飞行怎么做

不难发现这是一个非常经典的斜率优化优化DP，由于很久没写过这类题的这里简单讲一下：

转移方程\(new\_dis_i=old\_dis_j+(i-j)^2 (j<i)\)，我们要做的就是对每个\(i\)找出最优的转移点\(j\)

考虑\(i\)的两个转移点\(j,k\)，若\(j\)优于\(k\)，则\(old\_dis_j+(i-j)^2<old\_dis_k+(i-k)^2\)，化简得到\((old\_dis_j+j^2)-(old\_dis_k+k^2)<(2j-2k)\times i\)

我们不难发现，若设\(k_{jk}=\frac{(old\_dis_j+j^2)-(old\_dis_k+k^2)}{(2j-2k)}\)，若\(k_{jk}<i\)，则\(j\)更优，反之若\(k_{jk}>i\)，则\(k\)更优

接下来考虑若存在三个转移点\(x,y,z\)，若\(k_{xy}\ge k_{y,z}\)，那么此时\(y\)必然不可能为最优转移点，证明如下：

  • \(i\ge k_{xy}\ge k_{y,z}\)，此时\(y\)优于\(x\)，\(z\)优于\(y\)，\(z\)为最优转移点
  • \(k_{xy}\ge i\ge k_{y,z}\)，此时\(x\)优于\(y\)，\(z\)优于\(y\)，\(x/z\)为最优转移点
  • \(k_{xy}\ge k_{y,z}\ge i\)，此时\(x\)优于\(y\)，\(y\)优于\(z\)，\(x\)为最优转移点

综上，无论怎样\(y\)均不可能为最优转移点，因此我们只要维护点集使得斜率递增即可

接下来稍加推导就能发现我们只需要找到第一个斜率\(\le i\)的斜率对应的点作为转移点即可

然后直接Rush一发喜提WA

#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#define RI register int
#define CI const int&
#define LL long long
#define CL const LL&
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
const int N=100005;
int n,m,k,x,y,z; LL dis[N],tmp[N]; vector < pair<int,int> > v[N];
struct point
{
	LL x,y; int id;
	inline point(CL X=0,CL Y=0,CI ID=0) { x=X; y=Y; id=ID; }
}stk[N]; double slp[N]; int top;
inline double slope(const point& A,const point& B)
{
	return 1.0*(A.y-B.y)/(A.x-B.x);
}
namespace SP
{
	struct data
	{
		LL v; int p;
		inline data(CL V=0,CI P=0) { v=V; p=P; }
		friend inline bool operator < (const data& A,const data& B)
		{
			return A.v>B.v;
		}
	}; priority_queue <data> hp; bool vis[N];
	inline void Dijkstra(void)
	{
		for (RI i=1;i<=n;++i) vis[i]=0,hp.push(data(dis[i],i));
		while (!hp.empty())
		{
			int now=hp.top().p; hp.pop(); if (vis[now]) continue; vis[now]=1;
			for (auto to:v[now]) if (dis[to.fi]>dis[now]+to.se)
			dis[to.fi]=dis[now]+to.se,hp.push(data(dis[to.fi],to.fi));
		}
	}
};
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=m;++i)
	scanf("%d%d%d",&x,&y,&z),v[x].pb(mp(y,z)),v[y].pb(mp(x,z));
	for (i=2;i<=n;++i) dis[i]=1e18; SP::Dijkstra();
	while (k--)
	{
		for (top=0,i=1;i<=n;++i)
		{
			point now(2LL*i,dis[i]+1LL*i*i,i);
			while (top>=2&&slope(now,stk[top])<=slope(stk[top],stk[top-1])) --top;
			stk[++top]=now; if (top>1) slp[top]=slope(stk[top],stk[top-1]);
			int pos=stk[upper_bound(slp+2,slp+top+1,i)-slp-1].id;
			tmp[i]=dis[pos]+1LL*(i-pos)*(i-pos);
		}
		for (i=1;i<=n;++i) dis[i]=tmp[i]; SP::Dijkstra();
	}
	for (i=1;i<=n;++i) printf("%lld ",dis[i]); return 0;
}

好吧后来通过CF特有的找同病相怜人并观察ta们代码的修改发现这里要避免除法，遂修改

结果还是爆了，如法炮制发现了上面说的爆long long问题，遂艰难通过

#include<cstdio>
#include<queue>
#include<vector>
#define RI register int
#define CI const int&
#define LL long long
#define CL const LL&
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
const int N=100005;
int n,m,k,x,y,z; LL dis[N],tmp[N]; vector < pair<int,int> > v[N];
struct point
{
	LL x,y; int id;
	inline point(CL X=0,CL Y=0,CI ID=0) { x=X; y=Y; id=ID; }
}stk[N]; int top;
inline double slope(const point& A,const point& B)
{
	return 1.0*(A.y-B.y)/(A.x-B.x);
}
inline bool check(const point& A,const point& B,const point& C)
{
	return (A.y-B.y)*(B.x-C.x)>=(B.y-C.y)*(A.x-B.x);
}
namespace SP
{
	struct data
	{
		LL v; int p;
		inline data(CL V=0,CI P=0) { v=V; p=P; }
		friend inline bool operator < (const data& A,const data& B)
		{
			return A.v>B.v;
		}
	}; priority_queue <data> hp; bool vis[N];
	inline void Dijkstra(void)
	{
		for (RI i=1;i<=n;++i) vis[i]=0,hp.push(data(dis[i],i));
		while (!hp.empty())
		{
			int now=hp.top().p; hp.pop(); if (vis[now]) continue; vis[now]=1;
			for (auto to:v[now]) if (dis[to.fi]>dis[now]+to.se)
			dis[to.fi]=dis[now]+to.se,hp.push(data(dis[to.fi],to.fi));
		}
	}
};
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=m;++i)
	scanf("%d%d%d",&x,&y,&z),v[x].pb(mp(y,z)),v[y].pb(mp(x,z));
	for (i=2;i<=n;++i) dis[i]=1e18; SP::Dijkstra();
	while (k--)
	{
		for (top=0,i=1;i<=n;++i) if (dis[i]<=1LL*n*n)
		{
			point now(2LL*i,dis[i]+1LL*i*i,i);
			while (top>=2&&check(stk[top-1],stk[top],now)) --top;
			stk[++top]=now;
		}
		int pos=1; for (i=1;i<=n;++i)
		{
			while (pos<top&&1LL*i*(stk[pos+1].x-stk[pos].x)>=(stk[pos+1].y-stk[pos].y)) ++pos;
			tmp[i]=dis[stk[pos].id]+1LL*(i-stk[pos].id)*(i-stk[pos].id);
		}
		for (i=1;i<=n;++i) dis[i]=tmp[i]; SP::Dijkstra();
	}
	for (i=1;i<=n;++i) printf("%lld ",dis[i]); return 0;
}

Postscript

F看起来有点仙啊，弃了弃了

标签：const,int,dis,Codeforces,stk,Div,include,816,define
From： https://www.cnblogs.com/cjjsb/p/16667140.html

相关文章

  • Educational Codeforces Round 40 (Rated for Div. 2) 补题
    E.WaterTaps题意：每个水龙头有一个流量限制\(a_i\)，温度\(t_i\)，现在让你控制每个水龙头的出水量\(x_i\)，使得最终的水温为\(T\)，水温的公式为$\frac{\sum\limits_{i=1}^{......
  • CodeForces 限时随机挑战
    挑战规则就是初始难度*2400，积分为\(0\)，每次在该难度随机一道题做，每题时限\(35\)分钟，如果没有AC就-1，否则+1，如果积分\(>6\)，那么难度\(+100\)，积分清零，如果积分\(<......
  • 拿到tr循环里的td下的div里的文案
    Elements里的结构如下，需要拿到text文案，首先要拿到tr的循环列表，然后取出每一个tr里的第二个td，再去定位文案   //先定位到tr的上一步WebElementname=driver.fi......
  • Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
    这场打的稀烂。。。A.MainakandArray题意：将数组中某段子序列翻转一次，求a[n]-a[1]最大的值。思路：有三种情况：第一种，将最小的数翻转到第一位，然后用原来的a[n]减去反......
  • python中divmod是什么意思？
    python中divmod()是一个内置函数。pythondivmod()函数把除数和余数运算结果结合起来，返回一个包含商和余数的元组(a//b,a%b)。在python2.3版本之前不允许处理复数......
  • [Editorial] Codeforces Contest 1726
    A.MainakandArray显然如果\([l,r]\)不包括两端那么就不会对答案有影响，那么直接枚举包括两端的情况即可。/*author:Geminidate:September6th,2022url:htt......
  • 9/6 学了一点线性规划，打了一把cf div2被薄纱
    9/6日23:18才参加完cf的一场div2比赛，真难，我只会A题，后面再读题也不会了。希望下一次参赛能会更多。下午学习了数学建模的线性规划部分，深刻的感觉到自己的不足的数学功底，......
  • Educational Codeforces Round 134 D
    D.MaximumAND可以很轻松通过^和&两个操作看出我们要求的两个序列每一位上的1加起来必须等于n才行多一个少一个都不行然后1加起来等于n0自然加起来也等于n0和1的数......
  • Codeforces Round #815 (Div. 2)
    Preface休假强续了一天？刚好找一场题目少的Div.2做一下感觉今天状态不是很好啊，各种傻逼题秒不掉想各种奇怪东西……A.BurenkaPlayswithFractions首先不难发现答案......
  • codeforces.ml/contest/519/problem/E 求树上到任意两个点距离相等的点 树上倍增 分类
    E.AandBandLectureRoomstimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputAandBarep......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99