Petrozavodsk Winter-2018. Carnegie Mellon U Contest

2021-02-10 09:22

阅读：583

A. Mines

每个点能爆炸到的是个区间，线段树优化建图，并求出SCC进行缩点。

剔除所有不含任何$n$个点的SCC之后，最小代价为每个入度为$0$的SCC中最小点权之和，用set维护即可。

时间复杂度$O(n\log n)$。

#include
#include
#include
using namespace std;
typedef pairP;
const int N=1000010,M=8000000;
int n,m,i,j,x,y;long long ans;
struct E{
	int p,r,c;
}a[N];
P b[N];
int root,l[N],r[N],tot;
setT[N];
int g[2][N],nxt[2][M],v[2][M],ed,f[N],q[N],t,vis[N],ban[N];
inline void add(int x,int y){
	v[0][++ed]=y;nxt[0][ed]=g[0][x];g[0][x]=ed;
	v[1][ed]=x;nxt[1][ed]=g[1][y];g[1][y]=ed;
}
inline void ADD(int x,int y){
	v[1][++ed]=y;nxt[1][ed]=g[1][x];g[1][x]=ed;
}
int build(int a,int b){
	int x;
	if(a==b)x=::b[a].second;
	else x=++tot;
	if(a==b)return x;
	int mid=(a+b)>>1;
	l[x]=build(a,mid);
	r[x]=build(mid+1,b);
	add(x,l[x]);
	add(x,r[x]);
	return x;
}
void ins(int x,int a,int b,int c,int d,int p){
	if(c>1;
	if(cmid)ins(r[x],mid+1,b,c,d,p);
}
inline int askl(int x){//min >=x
	int l=1,r=n,mid,t;
	while(l>1;
		if(b[mid].first>=x)r=(t=mid)-1;else l=mid+1;
	}
	return t;
}
inline int askr(int x){//max >1;
		if(b[mid].firstfirst;
	while(m--){
		scanf("%d%d",&x,&y);
		if(!ban[f[x]]){
			ans-=T[f[x]].begin()->first;
			T[f[x]].erase(P(a[x].c,x));
			T[f[x]].insert(P(a[x].c=y,x));
			ans+=T[f[x]].begin()->first;
		}
		printf("%lld\n",ans);
	}
}

B. Balls

用set维护所有球和墙的坐标，操作1显然。

对于操作2，删除最左的坐标，将所有坐标减去$1$，然后加入墙的坐标，可以通过记录全局减去多少来实现。

时间复杂度$O(n\log n)$。

#include
#include
using namespace std;
int n,q,p,op,x,tag,i,a[1000000];setT;
int main(){
	scanf("%d%d%d",&n,&q,&p);
	T.insert(p);
	while(n--)scanf("%d",&x),T.insert(x);
	while(q--){
		scanf("%d",&op);
		if(op==1){
			scanf("%d",&x);
			x+=tag;
			T.insert(x);
		}else{
			T.erase(T.begin());
			tag++;
			T.insert(p+tag);
		}
	}
	n=0;
	for(set::iterator it=T.begin();it!=T.end();it++)a[++n]=(*it)-tag;
	for(i=1;i

C. Flip a Coin

设$f[i][j]$表示与$A$串KMP指针为$i$，与$B$串KMP指针为$j$的概率，高斯消元即可。

时间复杂度$O(n^6)$。

#include
#include
#include
#include
using namespace std;
const int N=25,M=505;
const double eps=1e-10;
int n,m,i,j,k,ga[N][2],gb[N][2],cnt,id[N][N];char a[N],b[N];
double g[M][M],x[M],ans[3];
void getnxt(char*a,int n,int g[][2]){
	static int nxt[N];
	for(int j=0,i=2;ifabs(g[k][i]))k=j;
		for(j=i;ji;j--)x[i]-=x[j]*g[i][j];
		x[i]/=g[i][i];
	}
	for(i=0;i

D. Octagons

若相邻两步形如$aa$，说明前进又后退，可以消去。

若连续5步形如$ababa$，说明在某个八边形上顺时针/逆时针走了5步，可以用$bab$替代，即反方向走3步。

如此反复迭代处理，若能消完则说明是封闭路径。

时间复杂度$O(n)$。

#include
#include
const int N=100010;
int n,m,i;char a[N],b[N];
int main(){
	scanf("%s",a+1);
	n=strlen(a+1);
	i=1;
	while(i=2&&b[m]==b[m-1])m-=2;
		if(m>=5&&b[m-4]==b[m-2]&&b[m-2]==b[m]&&b[m-3]==b[m-1]){
			m-=5;
			i-=3;
			a[i]=b[m+2];
			a[i+1]=b[m+3];
			a[i+2]=b[m+4];
		}
	}
	puts(m?"open":"closed");
}

E. Tree Paths

一条路径可行当且仅当最大值-最小值=路径长度。

对树进行点分治，求出重心到每个点路径上的最大值$a_x$、最小值$b_x$以及路径长度$c_x$。

则$(x,y)$可行当且仅当$\max(a_x,a_y)-\min(b_x,b_y)=c_x+c_y$。

将所有点按$a$从小到大排序，依次枚举每个$x$作为$\max(a)$，根据$\min(b)$的讨论转化为$b$在某段区间内的定值计数。

按定值分组处理所有操作，用树状数组维护$b$即可。

时间复杂度$O(n\log^2n)$。

#include
#include
using namespace std;
typedef long long ll;
const int N=50010,OFFSET=2000000;
int n,i,x,y,ce;
int g[N],v[Nf[x])f[x]=son[v[i]];
	}
	if(all-son[x]>f[x])f[x]=all-son[x];
	if(f[x]

F. Very New York

将坐标系旋转$45$度，则每个询问就是询问一个平行坐标轴的正方形内部的点数，扫描线+树状数组即可。

时间复杂度$O(n\log n)$。

#include
#include
using namespace std;
const int N=2100010,K=1000010;
int n,m,x,y,d,bit[N],ans[N],i;
struct E{
	int x,l,r,p;
	E(){}
	E(int _x,int _l,int _r,int _p){
		x=_x,l=_l,r=_r,p=_p;
		if(p){
			l=max(l,1);
			r=min(r,N-1);
			if(l>r)l=1,r=0;
		}
	}
}e[1000000];
inline int sgn(int x){return x!=0;}
inline bool cmp(const E&a,const E&b){return a.x==b.x?sgn(a.p)0)ans[e[i].p]+=ask(e[i].r)-ask(e[i].l-1);
		else ans[-e[i].p]-=ask(e[i].r)-ask(e[i].l-1);
	}
	for(i=1;i

G. Sheep

两个一次函数的差值的最值只可能在端点$0$或者$T$处取到，故可以转化为找一对实数$(x,y)$，使得$\max((f(0)-x)^2+(f(T)-y)^2)$最小。

里面的函数开根号后就是欧几里得距离，故答案就是这$n$个点$(f(0),f(T))$的最小覆盖圆的半径的平方。

时间复杂度$O(n)$。

#include
#include
#include
#include
using namespace std;
double R,eps=1e-10,T;
int n,i,j,k;
struct P{
	double x,y;
}a[100010],O;
inline double dis(P x,P y){
	return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
P center(P x,P y,P z){
	double a1=y.x-x.x,b1=y.y-x.y,
		   c1=(a1*a1+b1*b1)/2,a2=z.x-x.x,
		   b2=z.y-x.y,c2=(a2*a2+b2*b2)/2,
		   d=a1*b2-a2*b1;
	return (P){x.x+(c1*b2-c2*b1)/d,x.y+(a1*c2-a2*c1)/d};
}
int main(){
	scanf("%lf%d",&T,&n);
	for(i=0;iR+eps)
		for(O=a[i],R=0,j=0;jR+eps){
			O=(P){(a[i].x+a[j].x)/2,(a[i].y+a[j].y)/2},R=dis(O,a[i]);
			for(k=0;kR+eps)O=center(a[k],a[j],a[i]),R=dis(O,a[i]);
		}
	printf("%.15f",R*R);
}

H. Bin Packing

状压DP，设$f[S]$表示已经放入了$S$集合的物品后，最少需要多少个背包，在这个基础上还未满的背包已经放入的体积最少是多少。

时间复杂度$O(n2^n)$。

#include
using namespace std;
int n, S;
int a[24];
pair f[1> j & 1)
			{
				int scd = f[i].second + a[j];
				pairnxt;
				if(scd > S)
				{
					nxt = {f[i].first + 1, a[j]};
				}
				else
				{
					nxt = {f[i].first, scd};
				}
				f[i | 1

I. Statistics

首先可以通过01背包求出体积为$V$最少需要的物品数$num$。

最小平均数：即$\frac{V}{num}$。

最小中位数：二分答案$mid$，将所有不超过$mid$的数看作$-1$，超过$mid$的数看作$1$，DP出每种体积最少需要的物品数以及在这个基础上权值和的最小值，若最少需要的物品数为$num$且权值和最小值非正，则可行。

最小众数：二分答案$mid$，将多余物品删去，然后DP求出最少需要的物品数，检查是否是$num$即可。

最小极差：从大到小考虑每个物品作为最小值，DP出每种体积最少需要的物品数以及在这个基础上最大物品的最小可能值即可。

时间复杂度$O(nV\log n)$。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
void fre() {  }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls oinline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template inline void gmin(T1 &a, T2 b) { if (b inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, V;
int v[N], w[N], g[N];
int f[N];
paird[N];
int NUM;
int GetNum(int n, int v[])
{
	int NUM_ = 1e9;
	MS(f, 63); f[0] = 0;
	for(int i = n; i >= 1; --i)
	{
		for(int j = V - 1; j >= 0; --j)if(f[j] >= 0)
		{
			//we want it
			if(j + v[i] > V)continue;
			if(j + v[i] == V)
			{
				gmin(NUM_, f[j] + 1);
			}
			else
			{
				gmin(f[j + v[i]], f[j] + 1);
			}
		}
	}
	return NUM_;
}
double s1()
{
	//try to be max
	return 1.0 * V / NUM;
}
int val(int i, int pos)
{
	return i = 1; --i)
	{
		for(int j = V - 1; j >= 0; --j)if(d[j].first != inf)
		{
			//we want it
			if(j + v[i] > V || d[j].first >= NUM)continue;
			if(j + v[i] == V)
			{
				if(d[j].second + val(i, pos) = 1; --k)
			{
				w[++m] = j;
			}
		}
		int nowNUM = GetNum(m, w);
		if(nowNUM == NUM)r = mid;
		else l = mid + 1;
	}
	return l;
}
int s4()
{
	int ans = inf;
	for(int i = 1; i = 1; --i)
	{
		for(int j = V - 1; j >= 0; --j)if(d[j].first != inf)
		{
			//we want it
			if(j + v[i] > V || d[j].first >= NUM)continue;
			if(j + v[i] == V)
			{
				gmin(ans, d[j].second - v[i]);
			}
			else
			{
				int nxt = d[j].second;
				if(nxt == 0)nxt = v[i];
				gmin(d[j + v[i]], make_pair(d[j].first + 1, nxt));
			}
		}
	}
	return max(ans, 0);
}
int main()
{
	while(~scanf("%d%d",&n, &V))
	{
		MS(g, 0);
		int sum = 0;
		for(int i = 1; i

J. Zigzag

首先特判长度为$2$的情况。

设$f_{i,j,k}$表示仅考虑$a[1..i]$与$b[1..j]$，选择的两个子序列结尾分别是$a_i$和$b_j$，且上升下降状态是$k$时的最大子序列长度，则$f_{i,j,k}=\max(f_{x,y,1-k})+1$，其中$x

考虑将枚举决策点$x,y$的过程也DP掉。设$g_{i,y,k}$表示从某个$f_{x,y,k}$作为决策点出发，当前要更新的是$i$的最优解，$h_{i,j,k}$表示从某个$f_{x,y,k}$作为决策点出发，已经经历了$g$的枚举，当前要更新的是$j$的最优解。转移则是要么开始更新，要么将$i$或者$j$继续枚举到$i+1$以及$j+1$。因为每次只有一个变量在动，因此另一个变量恰好可以表示上一个位置的值，可以很方便地判断是否满足上升和下降。

时间复杂度$O(n^2)$。

#include
#include
#include
using namespace std;
const int N=2010;
int n,m,i,j,k,a[N],b[N],f,g[N][N][2],h[N][N][2],ans;
map >T;
inline void up(int&a,int b){ab[j])up(h[i][j+1][k],g[i][j][k]);
		}
	}
	for(map >::iterator it=T.begin();it!=T.end();it++)
		if(it->second.first>=2&&it->second.second>=2)
			up(ans,2);
	printf("%d",ans);
}

K. Knapsack

当$n\times m$不大时，可以直接$O(nm)$01背包解决。

否则因为数据随机，将两种算法结合即可。

算法1：

将$m$和所有物品的体积缩小一个比率$ratio$使得$O(nm)$01背包可以接受，错误率很低。

算法2：

对于两个状态$A$和$B$，若$A$的体积比$B$的体积大，但是价值不如$B$高，则可以删去$A$。

依次考虑每个物品，将每个状态扩展后和原来状态按体积归并，然后剔除无效状态。

随机数据下期望$O(\log(n!))$个状态，时间复杂度为$O(n\log(n!))=O(n^3)$。

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=510,M=30000010,LEN=6000010;
ll m,f[M],ans;int n,i,cnt;
int ST,EN;
struct P{
	ll w,v;
	P(){}
	P(ll _w,ll _v){w=_w,v=_v;}
}a[N],b[LEN],c[LEN],d[LEN];
inline bool cmp(const P&a,const P&b){return a.w==b.w?a.v>b.v:a.wEN)return;
	int cc=0;
	for(int i=1;ib[o].v)b[++o]=d[i];
	//cnt=min(o,1000000/n);
	cnt=min(o,LEN/2-5);
	up(ans,b[cnt].v);
}
ll cal(ll m){
	ll ratio=(double)(n)*(double)(m)/M;
	ratio=max(ratio,1LL);
	m/=ratio;
	for(i=0;i=w;j--)up(f[j],f[j-w]+v);
	}
	for(i=0;i=w;i--)up(f[i],f[i-w]+v);
		}
		for(i=0;i

上一篇：docker学习（三） Windows 10 安装Docker

下一篇：Bootstrap FileInput中文API文档

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Petrozavodsk Winter-2018. Carnegie Mellon U Contest
文章链接：http://soscw.com/index.php/essay/53512.html

亲，登录后才可以留言！

Petrozavodsk Winter-2018. Carnegie Mellon U Contest

评论

热门文章

推荐文章

最新文章

置顶文章