<output id="qn6qe"></output>


      2. 

      <output id="qn6qe"><tt id="qn6qe"></tt></output>
      3. <strike id="qn6qe"></strike>
      
亚洲 日本 欧洲 欧美 视频,日韩中文字幕有码av,一本一道av中文字幕无码,国产线播放免费人成视频播放,人妻少妇偷人无码视频,日夜啪啪一区二区三区,国产尤物精品自在拍视频首页,久热这里只有精品12 
    
    
      
        
    
      

    

    
      


      
	
      
	
      
		
      
    
    
      
        
      
            
      
                
    Petrozavodsk Winter-2018. Carnegie Mellon U Contest
    



            
      
            
      
            
      
                
      

      A. Mines
      

      每個點能爆炸到的是個區間，線段樹優化建圖，并求出SCC進行縮點。
      

      剔除所有不含任何$n$個點的SCC之后，最小代價為每個入度為$0$的SCC中最小點權之和，用set維護即可。
      

      時間復雜度$O(n\log n)$。
      

      

      #include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
typedef pair<int,int>P;
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;
set<P>T[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<=a&&b<=d){
		add(p,x);
		return;
	}
	int mid=(a+b)>>1;
	if(c<=mid)ins(l[x],a,mid,c,d,p);
	if(d>mid)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<=r){
		mid=(l+r)>>1;
		if(b[mid].first>=x)r=(t=mid)-1;else l=mid+1;
	}
	return t;
}
inline int askr(int x){//max <=x
	int l=1,r=n,mid,t;
	while(l<=r){
		mid=(l+r)>>1;
		if(b[mid].first<=x)l=(t=mid)+1;else r=mid-1;
	}
	return t;
}
void dfs1(int x){
	vis[x]=1;
	for(int i=g[0][x];i;i=nxt[0][i])if(!vis[v[0][i]])dfs1(v[0][i]);
	q[++t]=x;
}
void dfs2(int x,int y){
	vis[x]=0;f[x]=y;
	for(int i=g[1][x];i;i=nxt[1][i])if(vis[v[1][i]])dfs2(v[1][i],y);
}
void dfs3(int x){
	if(ban[x])return;
	ban[x]=1;
	for(int i=g[1][x];i;i=nxt[1][i])dfs3(v[1][i]);
}
inline void solve(int x){
	if(vis[x])return;
	vis[x]=1;
	for(int i=g[1][x];i;i=nxt[1][i])dfs3(v[1][i]);
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d%d%d",&a[i].p,&a[i].r,&a[i].c),b[i]=P(a[i].p,i);
	sort(b+1,b+n+1);
	tot=n;
	root=build(1,n);
	for(i=1;i<=n;i++){
		int l=askl(a[i].p-a[i].r);
		int r=askr(a[i].p+a[i].r);
		ins(root,1,n,l,r,i);
	}
	for(t=0,i=1;i<=tot;i++)if(!vis[i])dfs1(i);
	for(i=tot;i;i--)if(vis[q[i]])dfs2(q[i],q[i]);
	ed=0;
	for(i=1;i<=tot;i++)g[1][i]=0;
	for(i=1;i<=tot;i++)for(j=g[0][i];j;j=nxt[0][j])if(f[i]!=f[v[0][j]])ADD(f[i],f[v[0][j]]);
	for(i=1;i<=n;i++)solve(f[i]);
	for(i=1;i<=n;i++)if(!ban[f[i]])T[f[i]].insert(P(a[i].c,i));
	for(i=1;i<=tot;i++)if(!ban[i]&&f[i]==i)ans+=T[i].begin()->first;
	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<cstdio>
#include<set>
using namespace std;
int n,q,p,op,x,tag,i,a[1000000];set<int>T;
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<int>::iterator it=T.begin();it!=T.end();it++)a[++n]=(*it)-tag;
	for(i=1;i<n;i++)printf("%d ",a[i]);
}

      

      

      　　
      

      C. Flip a Coin
      

      設$f[i][j]$表示與$A$串KMP指針為$i$，與$B$串KMP指針為$j$的概率，高斯消元即可。
      

      時間復雜度$O(n^6)$。
      

      

      #include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
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;i<=n;nxt[i++]=j){
		while(j&&a[j+1]!=a[i])j=nxt[j];
		if(a[j+1]==a[i])j++;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<2;j++){
			char t=j==0?'H':'T';
			int k=i;
			while(k&&a[k+1]!=t)k=nxt[k];
			if(a[k+1]==t)k++;
			g[i][j]=k;
		}
	}
}
int main(){
	scanf("%s",a+1);
	n=strlen(a+1);
	scanf("%s",b+1);
	m=strlen(b+1);
	getnxt(a,n,ga);
	getnxt(b,m,gb);
	for(i=0;i<=n;i++)for(j=0;j<=m;j++)id[i][j]=++cnt;
	for(i=1;i<=cnt;i++)g[i][i]=1;
	for(i=0;i<n;i++)for(j=0;j<m;j++){
		for(k=0;k<2;k++){
			int x=ga[i][k],y=gb[j][k];
			g[id[x][y]][id[i][j]]-=0.5;
		}
	}
	g[1][cnt+1]=1;
	for(i=1;i<=cnt;i++){
		for(k=j=i;j<=cnt;j++)if(fabs(g[j][i])>fabs(g[k][i]))k=j;
		for(j=i;j<=cnt+1;j++)swap(g[i][j],g[k][j]);
		for(j=i+1;j<=cnt;j++){
			double t=g[j][i]/g[i][i];
			for(k=i;k<=cnt+1;k++)g[j][k]-=g[i][k]*t;
		}
	}
	for(x[cnt]=g[cnt][cnt+1]/g[cnt][cnt],i=cnt-1;i;i--){
		for(x[i]=g[i][cnt+1],j=cnt;j>i;j--)x[i]-=x[j]*g[i][j];
		x[i]/=g[i][i];
	}
	for(i=0;i<=n;i++)for(j=0;j<=m;j++){
		if(i==n&&j<m)ans[0]+=x[id[i][j]];
		if(i<n&&j==m)ans[1]+=x[id[i][j]];
		if(i==n&&j==m)ans[2]+=x[id[i][j]];
	}
	for(i=0;i<3;i++)printf("%.15f\n",ans[i]);
}

      

      

      　　
      

      D. Octagons
      

      若相鄰兩步形如$aa$，說明前進又后退，可以消去。
      

      若連續5步形如$ababa$，說明在某個八邊形上順時針/逆時針走了5步，可以用$bab$替代，即反方向走3步。
      

      如此反復迭代處理，若能消完則說明是封閉路徑。
      

      時間復雜度$O(n)$。
      

      

      #include<cstdio>
#include<cstring>
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<=n){
		b[++m]=a[i++];
		if(m>=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<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=50010,OFFSET=2000000;
int n,i,x,y,ce;
int g[N],v[N<<1],nxt[N<<1],ok[N<<1],ed,son[N],f[N],all,now,cnt;
ll ans;
struct E{
	int a,b,c;
	E(){}
	E(int _a,int _b,int _c){a=_a,b=_b,c=_c;}
}e[N];
struct W{
	int v,i,op,l,r;
	W(){}
	W(int _v,int _i,int _op,int _l,int _r){
		v=_v;
		i=_i;
		op=_op;
		l=_l;
		r=_r;
	}
}pool[OFFSET];
inline bool cmpw(const W&a,const W&b){
	if(a.v!=b.v)return a.v<b.v;
	return a.i<b.i;
}
inline bool cmp(const E&a,const E&b){return a.a<b.a;}
int bit[N],vis[N],POS;
inline void ins(int x){x++;for(;x<=n+1;x+=x&-x)if(vis[x]<POS)vis[x]=POS,bit[x]=1;else bit[x]++;}
inline int ask(int x){int t=0;for(x++;x;x-=x&-x)if(vis[x]==POS)t+=bit[x];return t;}
inline ll cal(){
	ll ret=0;
	sort(e+1,e+ce+1,cmp);
	int cp=0;
	for(int i=1;i<=ce;i++){
		pool[++cp]=W(e[i].a-e[i].c,i<<1,0,0,e[i].b);
		pool[++cp]=W(e[i].a-e[i].b-e[i].c+OFFSET,i<<1,0,e[i].b+1,n);
		pool[++cp]=W(e[i].b+e[i].c,i<<1|1,1,e[i].b,0);
		pool[++cp]=W(e[i].c+OFFSET,i<<1|1,1,e[i].b,0);
	}
	sort(pool+1,pool+cp+1,cmpw);
	for(int i=1;i<=cp;i++){
		if(i==1||pool[i].v!=pool[i-1].v)POS++;
		if(pool[i].op==1)ins(pool[i].l);
		else ret+=ask(pool[i].r)-ask(pool[i].l-1);
	}
	return ret;
}
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];ok[ed]=1;g[x]=ed;}
void findroot(int x,int y){
	son[x]=1;f[x]=0;
	for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y){
		findroot(v[i],x);
		son[x]+=son[v[i]];
		if(son[v[i]]>f[x])f[x]=son[v[i]];
	}
	if(all-son[x]>f[x])f[x]=all-son[x];
	if(f[x]<f[now])now=x;
}
void dfs(int x,int y,int dis,int ma,int mi){
	ma=max(ma,x);
	mi=min(mi,x);
	if(ma-mi==dis)ans++;
	e[++ce]=E(ma,mi,dis);
	for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y)dfs(v[i],x,dis+1,ma,mi);
}
void dfs2(int x,int y,int dis,int ma,int mi){
	ma=max(ma,x);
	mi=min(mi,x);
	e[++ce]=E(ma,mi,dis);
	for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=y)dfs2(v[i],x,dis+1,ma,mi);
}
void solve(int x){
	int i;
	for(i=g[x];i;i=nxt[i])if(ok[i]){
		ce=0;
		dfs(v[i],x,1,x,x);
		ans-=cal();
	}
	ce=0;
	for(i=g[x];i;i=nxt[i])if(ok[i])dfs2(v[i],x,1,x,x);
	ans+=cal();
	for(i=g[x];i;i=nxt[i])if(ok[i]){
		ok[i^1]=0;
		f[0]=all=son[v[i]];
		findroot(v[i],now=0);
		solve(now);
	}
}
int main(){
	scanf("%d",&n);
	for(ed=i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
	f[0]=all=n;
	findroot(1,now=0);
	solve(now);
	printf("%lld",ans+n);
}
/*
5
1 2
1 3
2 4
2 5
*/

      

      

      　　
      

      F. Very New York
      

      將坐標系旋轉$45$度，則每個詢問就是詢問一個平行坐標軸的正方形內部的點數，掃描線+樹狀數組即可。
      

      時間復雜度$O(n\log n)$。
      

      

      #include<cstdio>
#include<algorithm>
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)<sgn(b.p):a.x<b.x;}
inline void add(int x){for(;x<N;x+=x&-x)bit[x]++;}
inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&x,&y);
		e[++m]=E(x+y,x-y+K,0,0);
	}
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&d);
		e[++m]=E(x+y-d-1,x-y+K-d,x-y+K+d,-i);
		e[++m]=E(x+y+d,x-y+K-d,x-y+K+d,i);
	}
	sort(e+1,e+m+1,cmp);
	for(i=1;i<=m;i++)if(!e[i].p)add(e[i].l);
	else{
		if(e[i].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<=n;i++)printf("%d\n",ans[i]);
}

      

      

      　　
      

      G. Sheep
      

      兩個一次函數的差值的最值只可能在端點$0$或者$T$處取到，故可以轉化為找一對實數$(x,y)$，使得$\max((f(0)-x)^2+(f(T)-y)^2)$最小。
      

      里面的函數開根號后就是歐幾里得距離，故答案就是這$n$個點$(f(0),f(T))$的最小覆蓋圓的半徑的平方。
      

      時間復雜度$O(n)$。
      

      

      #include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
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;i<n;i++){
		double _a,_b;
		scanf("%lf%lf",&_a,&_b);
		a[i].x=_b;
		a[i].y=_a*T+_b;
	}
	random_shuffle(a,a+n);
	for(O=a[0],R=0,i=1;i<n;i++)if(dis(a[i],O)>R+eps)
		for(O=a[i],R=0,j=0;j<i;j++)if(dis(a[j],O)>R+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;k<j;k++)if(dis(a[k],O)>R+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<bits/stdc++.h>
using namespace std;
int n, S;
int a[24];
pair<int,int> f[1<<24];
int main()
{
	while(~scanf("%d%d", &n, &S))
	{
		for(int i = 0; i < n; ++i)
		{
			scanf("%d", &a[i]);
		}
		int top = 1 << n;
		f[0] = {1, 0};
		for(int i = 1; i < top; ++i)f[i] = {100, 0};
		for(int i = 0; i < top; ++i)
		{
			for(int j = 0; j < n; ++j)if(~i >> j & 1)
			{
				int scd = f[i].second + a[j];
				pair<int, int>nxt;
				if(scd > S)
				{
					nxt = {f[i].first + 1, a[j]};
				}
				else
				{
					nxt = {f[i].first, scd};
				}
				f[i | 1 << j] = min(f[i | 1 << j], nxt);
			}
		}
		printf("%d\n", f[top - 1].first);
	}
}

      

      

      　　
      

      I. Statistics
      

      首先可以通過01背包求出體積為$V$最少需要的物品數$num$。
      

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

      最小中位數：二分答案$mid$，將所有不超過$mid$的數看作$-1$，超過$mid$的數看作$1$，DP出每種體積最少需要的物品數以及在這個基礎上權值和的最小值，若最少需要的物品數為$num$且權值和最小值非正，則可行。
      

      最小眾數：二分答案$mid$，將多余物品刪去，然后DP求出最少需要的物品數，檢查是否是$num$即可。
      

      最小極差：從大到小考慮每個物品作為最小值，DP出每種體積最少需要的物品數以及在這個基礎上最大物品的最小可能值即可。
      

      時間復雜度$O(nV\log n)$。
      

      

      #include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() {  }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 5050, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>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];
pair<int,int>d[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 <= pos ? -1 : 1;
}
bool check(int pos)
{
	for(int i = 1; i <= 5000; ++i)d[i] = {inf, inf};
	d[0] = {0, 0};
	for(int i = n; 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) <= 0)return 1;
			}
			else
			{
				gmin(d[j + v[i]], make_pair(d[j].first + 1, d[j].second + val(i, pos)));
			}
		}
	}
	return 0;
}
int s2()
{
	//printf("check() = %d\n", check(2));
	int l = 1;
	int r = n;
	while(l < r)
	{
		int mid = (l + r) / 2;
		if(check(mid))r = mid;
		else l = mid + 1;
	}
	return v[l];
}
int s3()
{
	int l = 1;
	int r = n;
	while(l < r)
	{
		int mid = (l + r) / 2;
		int m = 0;
		for(int j = 1; j <= V; ++j)
		{
			for(int k = min(mid, g[j]); k >= 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 <= 5000; ++i)d[i] = {inf, inf};
	d[0] = {0, 0};
	for(int i = n; 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 <= n; ++i)
		{
			scanf("%d", &v[i]);
			sum += v[i];
			++g[v[i]];
		}
		if(sum < V)
		{
			puts("-1");
			continue;
		}
		sort(v + 1, v + n + 1);
		NUM = GetNum(n, v);
		if(NUM == 1e9)
		{
			puts("-1");
			continue;
		}
		printf("%.10f %d %d %d\n", s1(), s2(), s3(), s4());
	}
	return 0;
}

/*
【trick&&吐槽】


【題意】


【分析】


【時間復雜度&&優化】


*/

      

      

      　　
      

      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<i,y<j$。暴力轉移的時間復雜度為$O(n^4)$，不能接受。
          
      

      考慮將枚舉決策點$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<cstdio>
#include<map>
#include<algorithm>
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<int,pair<int,int> >T;
inline void up(int&a,int b){a<b?(a=b):0;}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]),T[a[i]].first++;
	scanf("%d",&m);
	for(i=1;i<=m;i++)scanf("%d",&b[i]),T[b[i]].second++;
	for(i=0;i<=n;i++)for(j=0;j<=m;j++)for(k=0;k<2;k++)h[i][j][k]=g[i][j][k]=-N;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)for(k=0;k<2;k++){
		if(a[i]==b[j]){
			//newstart
			f=0;
			up(f,h[i][j][k]);
			up(ans,++f);
			//start moving i
			up(g[i+1][j][k^1],f);
		}
		//continue moving j
		up(h[i][j+1][k],h[i][j][k]);
		//continue moving i
		up(g[i+1][j][k],g[i][j][k]);
		//start moving j
		if(k==0){
			if(a[i]<b[j])up(h[i][j+1][k],g[i][j][k]);
		}else{
			if(a[i]>b[j])up(h[i][j+1][k],g[i][j][k]);
		}
	}
	for(map<int,pair<int,int> >::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<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
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.w<b.w;}
inline void up(ll&a,ll b){a<b?(a=b):0;}
inline void add(ll w,ll v){
	if(clock()>EN)return;
	int cc=0;
	for(int i=1;i<=cnt;i++){
		if(w+b[i].w<=m){
			c[++cc]=P(w+b[i].w,v+b[i].v);
		}
	}
	int i=1,j=1,k=0;
	while(i<=cnt&&j<=cc){
		d[++k]=cmp(b[i],c[j])?b[i++]:c[j++];
	}
	while(i<=cnt)d[++k]=b[i++];
	while(j<=cc)d[++k]=c[j++];
	int o=0;
	for(int i=1;i<=k;i++)if(i==1||d[i].v>b[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<n;i++){
		ll w;ll v;
		scanf("%lld%lld",&w,&v);
		a[i].w=w;
		a[i].v=v;
		w/=ratio;
		int j;
		for(j=m;j>=w;j--)up(f[j],f[j-w]+v);
	}
	for(i=0;i<=m;i++)up(ans,f[i]);
}
int main(){
	ST=clock();
	EN=ST+3.7*CLOCKS_PER_SEC;
	scanf("%d%lld",&n,&m);
	if(!n)return puts("0"),0;
	if(m<M&&1LL*n*m<2e8){
		while(n--){
			int w;ll v;
			scanf("%d%lld",&w,&v);
			for(i=m;i>=w;i--)up(f[i],f[i-w]+v);
		}
		for(i=0;i<=m;i++)up(ans,f[i]);
		printf("%lld",ans);
		return 0;
	}
	ans=cal(m);
	random_shuffle(a,a+n);
	b[cnt=1]=P(0,0);
	for(i=0;i<n;i++)add(a[i].w,a[i].v);
	printf("%lld",ans);
}

      

      

      　　
      

      

      

            
      
            
      posted @ 
2018-03-07 23:07 
Claris 
閱讀(1404) 
評論(0) 
 
收藏 
舉報

      
        
      
	    
	    
    
      

      



      

      
    
    
      
    
    
      
    
      
        
      
    
      
        
    
      
    
    
      
    
      
    

      

	
      
	
      
	
	
      
	
      
	
      
	

      



    
      
        
    
      

    
    





主站蜘蛛池模板：
精品一区二区三区不卡|
另类专区一区二区三区|
国产国产午夜福利视频|
久久这里只有精品首页|
国产成人午夜福利在线观看|
人妻中文字幕精品系列|
亚洲国产午夜福利精品|
99精品热在线在线观看视|
精品视频在线观自拍自拍|
六十路老熟妇乱子伦视频|
国产视频一区二区三区麻豆|
麻豆国产成人AV在线播放|
国产精品白丝久久AV网站|
亚洲国产精品久久久久久久|
国产伦一区二区三区精品|
台东县|
色久综合色久综合色久综合|
少妇xxxxx性开放|
办公室强奷漂亮少妇视频|
色爱综合激情五月激情|
四虎永久地址WWW成人久久|
人妻体内射精一区二区三区|
九九九国产|
国产又色又爽又黄的视频在线|
午夜天堂精品久久久久|
一区二区三区四区五区黄色
|
和艳妇在厨房好爽在线观看|
亚洲中文无码手机永久|
精品国产一区二区三区av色诱|
和田市|
偷拍专区一区二区三区|
国产精品综合av一区二区国产馆|
热久久99精品这里有精品|
欧美亚洲国产成人一区二区三区|
思思久99久女女精品|
亚洲色在线v中文字幕|
邢台县|
久久亚洲精品情侣|
无码h片在线观看网站|
伊大人香蕉久久网欧美|
国产99视频精品免费视频6|