2019 CSP-S 시뮬레이션 10 유니언 데이 3

102010 단어 경기 총결산정예 합숙 훈련

문서 목록

  • 19CSP-S 아날로그 10 유니언 데이 3
  • 제목
  • A. 최장 01 하위 시퀀스
  • B. 경로 길이
  • C. Dynamic Matrix 최단거리
  • 코드
  • A. 최장 01 하위 시퀀스 시험장 코드
  • B. 경로 길이 경기 후 코드
  • C. 동적 매트릭스 최단거리 경기 후 코드

    • 19CSP-S 시뮬레이션 10 유니언 데이 3


    link
    100+0+40=140 (rk=40)

    제목.


    A. 최장 01 하위 시퀀스

  • n2n^2n2의 폭력은 매우 간단하다. 매거 중간에 몇 개의 0을 사이에 두고 매번 O(n)O(n)O(n)검사
  • 매거 0의 개수는 절약할 수 없다. 매번 검사할 때 최적화를 고려하면 출제자와 대부분의 정해는 모두 2분의 1의 위치이다. 내 시험장은 배로 늘어나고 0이 된다. 복잡도는 모두 O(nl o g 2 n) O(nlog^2n) O(nlog2n) O(nlog2n)이다. 그런데 나는 왜 거의 느리게 뛰는지 모르겠다

    • B. 경로 길이


    이 시험장은 바로 쓰지 않았고 9시에 도착하자마자 CF CF CF를 치러 갔는데 결국 CF CF CF도 몇 점 더 주지 않았다.
  • 이 문제를 검색해 보면 시험을 통해 40점을 얻을 수 있는 좋은 성적
  • 40점의 폭력도 각 점에 대해 모든 거리를 계산할 수 있다. 배낭은bitset 저장 최적화 상수만 60점이라고 한다
  • 정해는 각 점의 모든 거리를 기록할 필요가 없다는 것을 발견했다. 1011z≤x≤y≤z\rac{10} {11} z\leq x\leq y\leq z 1110z≤x≤y≤z가 존재할 때 yy 이 거리는 기록하지 않아도 된다. 왜?y y를 덮어쓰는 질문이 x x x 또는zz로 대답할 수 있는지 살펴보면 알 수 있습니다. 분명히 y를 포함하는 질문 구간에는 x x x 또는zz
    • 가 포함되어 있습니다.
  • 그러면 각 점에 기록해야 할 개수는 O(l o g n) O(logn) O(logn) 레벨입니다. 왜냐하면 log ⁡ 1.11 e 9\log{1.1} {1e9} log1.1 e9 대략 200+, 우리가 도달할 수 있는 거리를 수조에 넣으면 0/1 0/1 0/1 0/10 10/1 0/1을 사용하지 않아도 됩니다. 매번 폭력 합병이 직접 정렬될 때마다 문제가 크지 않습니다
  • 모든 방향이 있는 x-3>yx->yx-3>y에 x

    C. Dynamic Matrix 최단 거리

  • 이 문제는 사실 간단한 문제인 것 같았는데 시험장에서 생각이 안 났어요
  • 임의의 문의에 대해 현재의 국면은 반드시 또 일부 열에 일부 줄을 더해서 격자형을 형성한다
  • 격자 모양의 최단거리 상황에 대해 우리는 분류 토론이 드물다
  • 첫 번째, 한 점의 행과 다른 점의 열이 연결되거나 행렬이 바뀌면 답은 맨해튼 거리
  • 두 번째, 두 점 모두 줄이 있고 임의의 열을 더하면 중간에 있는 답이 맨해튼 거리라면 더 크고 행렬도 바꿀 수 있다
  • 세 번째, 두 점 사이의 모든 줄 또는 모든 열이 연결되는
  • 그러면 유지보수를 하면 줄과 열에 대해 각각 라인 트리를 짓는 것이다. 조작은 단일 수정과 조회 구간의 최고치를 포함한다. 그 중에서 두 번째 중 두 번째 것은 어느 위치에서 왼쪽에서 시작하거나 오른쪽에서 시작하여 첫 번째 숫자보다 큰 위치를 찾아야 한다
  • 상황을 다 고려하면 쓰기 쉽다

    • 코드


    A. 최장 01 하위 시퀀스 시험장 코드

    #include
#define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
#define For(i,a,b) for (register int i=(a);i>=(b);i--)
#define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
#define mem(i,j) memset(i,j,sizeof(i))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,a[N],nxt1[N],pos1,nxt0[21][N],pos0,ans=0;
char s[N];
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return f*x;
}
inline void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	if (x>9) write(x/10);
	putchar(x%10+'0');
	return;
}
inline int pan1()
{
	int ret=1;
	FOR(i,1,n) ret&=(a[i]==0);
	return ret;
}
inline void pan2()
{
	int cnt=0;
	FOR(i,1,n) cnt+=(a[i]==1);
	ans=max(ans,cnt);
	return;
}
inline int get0(int pos,int k)
{
	if (pos==-1) return -1;
	while (k)
	{
		int step=log2(k);
		pos=nxt0[step][pos];
		if (pos==-1) return -1;
		k-=(1<<step);
	}
	return pos;
}
inline int solve(int gap)
{
	int ret=0,pos;
	if (a[1]) pos=get0(1,gap);
	else pos=get0(1,gap-1);
	if (pos==-1) return 0;
	ret+=gap;
	while (pos!=-1)
	{
		pos=nxt1[pos];
		pos=get0(pos,gap);
		if (pos!=-1) ret+=gap+1;
	}
	return ret;
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("myans.out","w",stdout);
	mem(nxt0,-1);
	scanf("%s",s+1);
	n=strlen(s+1);
	FOR(i,1,n) a[i]=(s[i]=='1');
	if (pan1()) {write(0);putchar('
    '    );exit(0);}
	pos1=-1;
	For(i,n,1)
	{
		nxt1[i]=pos1;
		if (a[i]) pos1=i;
	}
	pos0=-1;
	For(i,n,1)
	{
		nxt0[0][i]=pos0;
		if (!a[i]) pos0=i;
	}
	FOR(j,1,20)
		For(i,n,1) if (nxt0[j-1][i]!=-1) nxt0[j][i]=nxt0[j-1][nxt0[j-1][i]];
	FOR(k,1,(n-1)/2) 
		ans=max(ans,solve(k));
	pan2();
	write(ans);
	putchar('
    '    );
	return 0;
}

    B. 경로 길이 경기 후 코드

    #include
#define FOR(i,a,b) for (register ll i=(a);i<=(b);i++)
#define For(i,a,b) for (register ll i=(a);i>=(b);i--)
#define mem(i,j) memset(i,j,sizeof(i))
#define GO(u) for (register ll j=f[u];j!=-1;j=nxt[j])
#define pb push_back
using namespace std;
typedef long long ll;
const ll N=2e5+5;
ll n,tag,ans[N],m,q,tmp1,tmp2,tmp3;
ll tot=0,f[N],nxt[N<<1];
vector <ll> vec[N],T;
vector <ll> :: iterator it;
struct E
{
	ll u,v,w;
}e[N<<1];
inline void add(ll u,ll v,ll w)
{
	tot++;
	nxt[tot]=f[u];
	f[u]=tot;
	e[tot]=(E){u,v,w};
	return;
}
inline ll read()
{
	ll x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return f*x;
}
inline void write(ll x)
{
	if (x<0) putchar('-'),x=-x;
	if (x>9) write(x/10);
	putchar(x%10+'0');
	return;
}
inline void solve()
{
	vec[1].pb(0);
	FOR(i,2,n)
	{
		T.clear();
		GO(i)
		{
			ll v=e[j].v,w=e[j].w;
			FOR(k,0,(ll)vec[v].size()-1)
				T.pb(w+vec[v][k]);
		}
		sort(T.begin(),T.end());
		FOR(j,0,(ll)T.size()-1)
		{
			while (vec[i].size()>=2&&(10.0*T[j]/11<=vec[i][(ll)vec[i].size()-2])) vec[i].pop_back();
			vec[i].pb(T[j]);
		}
	}
	return;
}
inline void debug()
{
	FOR(i,1,n)
	{
		printf("# %d :
    "    ,i);
		FOR(j,0,(ll)vec[i].size()-1) printf("%d ",vec[i][j]);
		putchar('
    '    );
	}
	return;
}
int main()
{
//	freopen("data.in","r",stdin);
	mem(f,-1);
	n=read(),m=read(),q=read();
	FOR(i,1,m) tmp1=read(),tmp2=read(),tmp3=read(),add(tmp2,tmp1,tmp3);
	solve();
//	debug();
	while (q--)
	{
		ans[0]++;
		tmp1=read(),tmp2=read();
		it=lower_bound(vec[tmp1].begin(),vec[tmp1].end(),tmp2);
		if (it==vec[tmp1].end()) ans[ans[0]]=0;
		else
		{
			ll val=*it;
			if (10.0*val/11<=tmp2) ans[ans[0]]=1;
			else ans[ans[0]]=0;
		}
	}
	FOR(i,1,ans[0])
	{
		if (ans[i]) printf("YES
    "    );
		else printf("NO
    "    );
	}
	return 0;
}

    C. Dynamic Matrix 최단거리 경기 후 코드

    #include
#define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
#define For(i,a,b) for (register int i=(a);i>=(b);i--)
#define mem(i,j) memset(i,j,sizeof(i))
#define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int inf=1e6;
int n,m,q,ans[3*N],time_now=0,Row[N],Col[N];
int opt,tmp1,tmp2,tmp3,tmp4,tmp5,check;
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return f*x;
}
inline void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	if (x>9) write(x/10);
	putchar(x%10+'0');
	return;
}
struct Segment_Tree
{
	int mn[N<<2],mx[N<<2];
	inline void up(int p) {mn[p]=min(mn[p<<1],mn[p<<1|1]);mx[p]=max(mx[p<<1],mx[p<<1|1]);return;}
	inline void bd(int p,int l,int r)
	{
		mn[p]=mx[p]=0;
		if (l==r) {Row[l]=Col[l]=0;return;}
		int ls=p<<1,rs=p<<1|1,mid=(l+r)>>1;
		bd(ls,l,mid);bd(rs,mid+1,r);
		up(p);
		return;
	}
	inline void md(int p,int l,int r,int k,int v)
	{
		if (l==r) {mn[p]=v;mx[p]=v;return;}
		int ls=p<<1,rs=p<<1|1,mid=(l+r)>>1;
		if (k<=mid) md(ls,l,mid,k,v);
		else md(rs,mid+1,r,k,v);
		up(p);
		return;
	}
	inline int qr_min(int p,int l,int r,int L,int R)
	{
		if (L<=l&&r<=R) return mn[p];
		int ls=p<<1,rs=p<<1|1,mid=(l+r)>>1,ret=inf;
		if (L<=mid) ret=min(ret,qr_min(ls,l,mid,L,R));
		if (R>mid) ret=min(ret,qr_min(rs,mid+1,r,L,R));
		if (ret==inf) return -1;
		return ret;
	}
	inline int qr_max(int p,int l,int r,int L,int R)
	{
		if (L<=l&&r<=R) return mx[p];
		int ls=p<<1,rs=p<<1|1,mid=(l+r)>>1,ret=0;
		if (L<=mid) ret=max(ret,qr_max(ls,l,mid,L,R));
		if (R>mid) ret=max(ret,qr_max(rs,mid+1,r,L,R));
		return ret;
	}
	inline int find_left(int lim,int pos,int v)
	{
		int L=1,R=pos,MID,ret=-1;
		while (L<R)
		{
			MID=(L+R+1)>>1;
			if ((check=qr_max(1,1,lim,MID,pos))>=v) L=MID,ret=0;
			else R=MID-1;
		}
		if (qr_max(1,1,m,pos,L)>=v) ret=0;
		if (ret==-1) return ret;
		return L;
	}
	inline int find_right(int lim,int pos,int v)
	{
		int L=pos,R=lim,MID,ret=-1;
		while (L<R)
		{
			MID=(L+R)>>1;
			if ((check=qr_max(1,1,m,pos,MID))>=v) R=MID,ret=0;
			else L=MID+1;
		}
		if ((check=qr_max(1,1,m,pos,L))>=v) ret=0;
		if (ret==-1) return ret;
		return L;
	}
}row,col;
inline int solve(int a,int b,int c,int d,int v)
{
	if (a==c&&b==d) return 0;
	v=time_now-v;//            v      
	int dis=abs(a-c)+abs(b-d);
	int A=Row[a],B=Col[b],C=Row[c],D=Col[d];
	if (max(A,B)<v||max(C,D)<v) return -1;
	//case 1:   
	if (A>=v&&D>=v) return dis;
	if (B>=v&&C>=v) return dis;
	//case 2:   
	if (a>c) swap(a,c),swap(A,C);
	if (b>d) swap(b,d),swap(B,D);
	if (row.qr_min(1,1,n,a,c)>=v) return dis;
	if (col.qr_min(1,1,m,b,d)>=v) return dis;
	//case 3:"2+1" 
	int tmp,ret=inf;
	if (A>=v&&C>=v)
	{
		if (col.qr_max(1,1,m,b,d)>=v) return dis;
		tmp=col.find_left(n,b,v);
		if (tmp!=-1) ret=min(ret,abs(a-c)+abs(b-tmp)+abs(d-tmp));
		tmp=col.find_right(n,d,v);
		if (tmp!=-1) ret=min(ret,abs(a-c)+abs(b-tmp)+abs(d-tmp));
	}
	if (B>=v&&D>=v)
	{
		if (row.qr_max(1,1,n,a,c)>=v) return dis;
		tmp=row.find_left(m,a,v);
		if (tmp!=-1) ret=min(ret,abs(b-d)+abs(a-tmp)+abs(c-tmp));
		tmp=row.find_right(m,a,v);
		if (tmp!=-1) ret=min(ret,abs(b-d)+abs(a-tmp)+abs(c-tmp));
	}
	if (ret!=inf) return ret;
	return -1;
}
int main()
{
	
	n=read(),m=read(),q=read();
	row.bd(1,1,n);
	col.bd(1,1,m);
	while (q--)
	{
		time_now++;
		opt=read(),tmp1=read();
		if (opt==3) tmp2=read(),tmp3=read(),tmp4=read(),tmp5=read();
		switch (opt)
		{
			case 1:
				Row[tmp1]=time_now;
				row.md(1,1,n,tmp1,time_now);
				break;
			case 2:
				Col[tmp1]=time_now;
				col.md(1,1,m,tmp1,time_now);
				break;
			case 3:
				ans[0]++;
				ans[ans[0]]=solve(tmp1,tmp2,tmp3,tmp4,tmp5);
				break;
		}
	}
	FOR(i,1,ans[0]) write(ans[i]),putchar('
    '    );
	return 0;
}
    Django_ 세팅 Error
    [Django] 나만의 쇼핑몰 만들기 - 상품 등록하고 상품 페이지에 나타내기

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage