문서 목록

2019-9-15 잡문선강

제목

CF1174E Ehab and the Expected GCD Problem

[ZJOI 2019] 세그먼트 트리

CF1197D Yet Another Subarray Problem

P4965 윌리트의 타자기

P2405 non 천평

코드

CF1174E Ehab and the Expected GCD Problem 코드

[ZJOI 2019] 세그먼트 트리 코드

CF1197D Yet Another Subarray Problem 코드

P4965 윌리트의 타자기 코드

P2405 non 천평 코드

2019-9-15 문항 선강

제목.

CF1174E Ehab and the Expected GCD Problem

link
이 문제는 접두사 GCDGCD가 증가하지 않는다는 느낌을 준다. 그러면 우리가 접두사 GCDGCD를 최대한 다르게 하려고 한다면 우리는 반드시 그것이 천천히 떨어지고 매번 잃어버리기를 바란다. 그러면 나는 매번 반만 낮추는 것이 가장 좋다. 그래서 NTF NTF 결론의 감성적인 이해판이 생겼다.그러나 첫 번째 수가 반드시 222의 차멱은 아니다. 333을 하나 가지고 갈 수도 있다. 마지막 222를 곱할 때 33을 더하면 nn이 터지지 않고 33을 더하면 된다.그래서 첫 번째 수가 2 x 3 y (y = 1 o r 0) 2 ^x3 ^y (y=1 or 0) 2 x3y (y=1 or0) 이므로 D P DP DP 계수를 하면 됩니다

[ZJOI 2019] 세그먼트 트리

이번 주 진제의 보물link 수상을 축하합니다.
충격!매일 나무를 치는 사람은 나무에 이 다섯 가지가 있다는 것을 모른다. 이 문제의 대체적인 사고방식은 다음과 같다.우선 모든 나무의 번호(상대적인 순서)는 답안에 영향을 주지 않는다. 우리는 매번 한 번씩 복사한 것을 알 수 있다. 새로운 mo d i f y modify modify modify는 낡은 것이 움직이지 않는다.그럼 우리 디자인 상태 fu, i f{u, i} fu, i는 i회 작업 후 몇 개의 u u u 점이 t a g tag tag인지를 나타냅니다. 우리는 점을 분류한 후에 각각 D P DP DP 방정식을 작성하여 gu, i g 를 유지해야 한다는 것을 발견했습니다.{u, i} gu, i는 i i i회 조작 후 몇 개의 u u u점에서 1 1 1 1 경로에 t a g tag tag가 없으며 f f f f를 보조적으로 계산하는 것을 나타낸다. 이 라인 트리의 점은 분류를 거친 후에 어떤 것은 매번 개수가 O (l o g n) O (logn) O (logn) 등급을 초과하지 않고 어떤 것은 작은 트리이다. 그러면 전자는 폭력적으로 수정하고 후자는 정상적인 l a zy t a g lazy tag lazy tag

CF1197D Yet Another Subarray Problem

link
이 문제는 추식 시령 i = ⌊i m⌋m + i% m i =\lfloor\urac {m} {m}\rfloor *m+i\%m i = ⌊m+i%m 이면 됩니다. m이 작기 때문에 왼쪽에서 오른쪽으로 쓸었을 때 접두사 최소값을 유지할 때%m로 분류하면 됩니다.

P4965 윌리트의 타자기

link
이 코드는 e a s y easy easy 하지만 사고방식은 s o g o o d so good sogood.저희가 먼저 tr i e trie trie 트리에서 이 문제를 분석해 보도록 하겠습니다.

도달할 수 있는 지점에 표시를 하면 문자를 추가할 때 모든 표지점이 새로운 지점으로 확대되고 옛 지점은 표시를 보존한다. 그러면 우리는 F[c] F[c] F[c]를 유지하고 변c의 노드 개수를 가지면 신속하게 이동할 수 있다

만약에 체크아웃을 받으면 답이 하나 더 나온다. 바로 원래 문자열이 처음부터 이 체크아웃 전의 문자열이다. 그래서 a n s + ans++ ans++ ans++이다. 그러나 체크아웃을 한 후에 어느 점에서 한 걸음 위로 올라가는 것과 같다. 그러면 이 위치의 점은 표시가 하나 있지만 우리는 그것을 두 점으로 간주해야 한다. 그래서 F [x] + F [x]++ F [x]++ F [x]++++++++++++++++++++++ F[x]++++++++++++++++++++++++++++++++ + 는 문제가 없어진다(4591678)

P2405 non 천평

link
이 문제의 사고 난이도가 높지 않기 때문에 반드시 먼저 물품을 nn진법으로 바꿀 수 있다. 왜냐하면 우리 쌍방이 모두 분동을 놓을 수 있기 때문에 우리는 큰 분동으로 작은 방법을 줄일 수 있기 때문에 원래 작은 분동으로 불렀던 물건을 얻을 수 있다. 그러나 이 상감된 조작은 반드시 크기가 서로 인접한 두 분동 사이에 나타나고 반드시 큰 분동은 하나만 쓸 수 있다. 내가 바보가 아니라면,그러면 높이에서 낮은 DP DP DP로

코드

CF1174E Ehab and the Expected GCD Problem 코드

#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=1e6+5;
const int mod=1e9+7;
int n,dp[N][21][2],lim=1,lg=0,ans;
int er[N],san[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 CAL(int x,int y)
{
	if (x<0||y<0) return 0;
	if (!er[x]||!san[y]) return 0;
	int ret=n/(er[x]*san[y]);
	return ret;
}
int main()
{
	mem(dp,0);
	n=read();
	while ((lim<<1)<=n) lim<<=1,lg++;
	er[0]=1;
	FOR(i,1,lg) er[i]=1LL*er[i-1]*2%mod;
	san[0]=1;
	for (register int i=1;san[i-1]*3<=n;i++) san[i]=1LL*san[i-1]*3%mod;
	dp[1][lg][0]=1;
	if (er[lg-1]*3<=n) dp[1][lg-1][1]=1;
	FOR(i,2,n)
		FOR(x,0,lg)
		{
			dp[i][x][0]=(1LL*dp[i-1][x][0]*(CAL(x,0)-i+1)%mod+1LL*dp[i-1][x][1]*(CAL(x,0)-CAL(x,1))%mod+1LL*dp[i-1][x+1][0]*(CAL(x,0)-CAL(x+1,0))%mod)%mod;
			dp[i][x][1]=(1LL*dp[i-1][x][1]*(CAL(x,1)-i+1)%mod+1LL*dp[i-1][x+1][1]*(CAL(x,1)-CAL(x+1,1))%mod)%mod;
		}
	ans=dp[n][0][0];
	write(ans);
	return 0;
}

[ZJOI 2019] 세그먼트 트리 코드

#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=2e5+5;
const int mod=998244353;
int n,m,cnt=1,opt,tmp1,tmp2,ans[N];
int sum[N<<2],f[N<<2],g[N<<2],tag_f[N<<2],tag_g[N<<2];
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 void up(int p)
{
	sum[p]=(1LL*sum[p<<1]+sum[p<<1|1]+f[p])%mod;
	return;
}
inline void bd(int p,int l,int r)
{
	sum[p]=f[p]=0;
	g[p]=1;
	tag_f[p]=tag_g[p]=1;
	if (l==r) return;
	int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
	bd(ls,l,mid);
	bd(rs,mid+1,r);
	up(p);
	return;
}
inline void mul_f(int p,int v)
{
	tag_f[p]=1LL*tag_f[p]*v%mod;
	sum[p]=1LL*sum[p]*v%mod;
	f[p]=1LL*f[p]*v%mod;
	return;
}
inline void mul_g(int p,int v)
{
	tag_g[p]=1LL*tag_g[p]*v%mod;
	g[p]=1LL*g[p]*v%mod;
	return;
}
inline void down(int p)
{
	int ls=p<<1,rs=p<<1|1;
	if (tag_f[p]!=1)
	{
		mul_f(ls,tag_f[p]);
		mul_f(rs,tag_f[p]);
		tag_f[p]=1;
	}
	if (tag_g[p]!=1)
	{
		mul_g(ls,tag_g[p]);
		mul_g(rs,tag_g[p]);
		tag_g[p]=1;
	}
	return;
}
inline void md(int p,int l,int r,int L,int R)
{
	down(p);
	int mid=(l+r)>>1,ls=p<<1,rs=p<<1|1;
	if (L<=l&&r<=R)
	{
		mul_f(ls,2);mul_f(rs,2);
		f[p]=(1LL*f[p]+cnt)%mod;
		up(p);
		return;
	}
	g[p]=(1LL*g[p]+cnt)%mod;
	if (R<=mid)
	{
		md(ls,l,mid,L,R);
		down(rs);
		f[rs]=(1LL*f[rs]+cnt-g[rs]+mod)%mod;
		g[rs]=(1LL*g[rs]+g[rs])%mod;
		mul_g(rs<<1,2);mul_g(rs<<1|1,2);
		mul_f(rs<<1,2);mul_f(rs<<1|1,2);
		up(rs);
	}
	else if (L>mid)
	{
		md(rs,mid+1,r,L,R);
		down(ls);
		f[ls]=(1LL*f[ls]+cnt-g[ls]+mod)%mod;
		g[ls]=(1LL*g[ls]+g[ls])%mod;
		mul_g(ls<<1,2);mul_g(ls<<1|1,2);
		mul_f(ls<<1,2);mul_f(ls<<1|1,2);
		up(ls);
	}
	else
	{
		md(ls,l,mid,L,R);
		md(rs,mid+1,r,L,R);
	}
	up(p);
	return;
}
int main()
{
//	freopen("data.in","r",stdin);
	n=read(),m=read();
	bd(1,1,n);
	FOR(i,1,m)
	{
		opt=read();
		if (opt==1) tmp1=read(),tmp2=read();
		if (opt==1) md(1,1,n,tmp1,tmp2),cnt=(1LL*cnt+cnt)%mod;
		else ans[++ans[0]]=sum[1];
	}
	FOR(i,1,ans[0]) write(ans[i]),putchar('
');
	return 0;
}

CF1197D Yet Another Subarray Problem 코드

#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])
using namespace std;
typedef long long ll;
const ll N=3e5+5;
const ll inf=1e17;
ll n,m,k,a[N],s[N],mn[20],r[N],tmp,ans=0;
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;
}
int main()
{
	n=read(),m=read(),k=read();
	FOR(i,1,m-1) mn[i]=inf;
	FOR(i,1,n) a[i]=read();
	FOR(i,1,n) s[i]=s[i-1]+a[i];
	FOR(i,1,n) r[i]=s[i]-k*(i/m);
	FOR(i,1,n)
	{
		tmp=i%m;
		FOR(j,0,m-1) ans=max(ans,r[i]-mn[j]-k*((i%m-j+m-1)/m));
		mn[tmp]=min(mn[tmp],r[i]);
	}
	write(ans);
	return 0;
}

P4965 윌리트의 타자기 코드

#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=5e6+5;
const int mod=19260817;
int n,m,ans=1,rest,F[100];
char A[N],B[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;
}
int main()
{
	n=read(),m=read();
	rest=n;
	scanf("%s",A+1);
	scanf("%s",B+1);
	FOR(i,1,m)
	{
		int c=B[i]-'A'+1;
		if (1<=c&&c<=26)
		{
			int f=F[c];
			F[c]=ans;
			ans=(1LL*(ans<<1)-f+mod)%mod;
		}
		else
		{
			if (!rest) continue;
			ans++;
			ans%=mod;
			F[A[rest]-'A'+1]++;
			F[A[rest]-'A'+1]%=mod;
			rest--;
		}
	}
	write(ans);
	return 0;
}

P2405 non 천공 코드

#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=2e6+5;
int n,s[N],tmps[N],len=0,r[N],dp[N][2],ans;
inline void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	if (x>9) write(x/10);
	putchar(x%10+'0');
	return;
}
inline int get_yu()
{
	int ret=0;
	FOR(i,1,len)
	{
		ret=(ret<<1)+(ret<<3)+s[i];
		ret%=n;
	}
	return ret;
}
inline void devide()
{
	int now=0,tmplen=0,ready=0;
	FOR(i,1,len) tmps[i]=0;
	FOR(i,1,len)
	{
		now=(now<<1)+(now<<3)+s[i];
		if (now>=n) ready=1;
		if (ready)
		{
			tmps[++tmplen]=now/n;
			now%=n;
		}
	}
	len=tmplen;
	FOR(i,1,len) s[i]=tmps[i];
	return;
}
int main()
{
//	freopen("testdata (1).in","r",stdin);
	char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') s[++len]=c-'0',c=getchar();
	scanf("%d",&n);
	if (n==1) {FOR(i,1,len) write(s[i]);exit(0);}
	while (len)
	{
		r[++r[0]]=get_yu();
		devide();
	}
	dp[r[0]+1][1]=1;
	For(i,r[0],1)
	{
		dp[i][0]=min(dp[i+1][0]+r[i],dp[i+1][1]+n-r[i]);
		dp[i][1]=min(dp[i+1][0]+r[i]+1,dp[i+1][1]+n-r[i]-1);
	}
	ans=dp[1][0];
	write(ans);
	return 0;
}

2019-9-15 문항 선강

문서 목록

2019-9-15 문항 선강

제목.

CF1174E Ehab and the Expected GCD Problem

[ZJOI 2019] 세그먼트 트리

CF1197D Yet Another Subarray Problem

P4965 윌리트의 타자기

P2405 non 천평

코드

CF1174E Ehab and the Expected GCD Problem 코드

[ZJOI 2019] 세그먼트 트리 코드

CF1197D Yet Another Subarray Problem 코드

P4965 윌리트의 타자기 코드

P2405 non 천공 코드

좋은 웹페이지 즐겨찾기