技术教程 11.1 正睿停课训练 Day14 正文

11.1 正睿停课训练 Day14

2022-11-10,,,

目录
2018.11.1 正睿停课训练 Day14
A 字符串
B 取数游戏(贪心)
C 魔方(模拟)
考试代码
B
C

2018.11.1 正睿停课训练 Day14

时间：3.5h

期望得分：100+?+60

实际得分：100+80+10

比赛链接

虽然考的不高 但都是每天三道题统计的rank1 2333

A 字符串

题目链接

模拟一下发现，\(k\)为奇数时，串的所有奇数下标位置和偶数下标位置必须分别相同，或是所有字符相同；\(k\)为偶数时，所有字符必须相同。

再判一下特殊情况就行了。

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

#define mod 1000000007

const int N=2005;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline int FP(int x,int k)

{

	int t=1;

	for(; k; k>>=1,x=1ll*x*x%mod)

		if(k&1) t=1ll*t*x%mod;

	return t;

}

int main()

{

//	freopen("A.in","r",stdin);

//	freopen("my.out","w",stdout);

	int n=read(),m=read(),K=read();

	if(n<K||K<=1) return printf("%d\n",FP(m,n)),0;

	if(K==n) return printf("%d\n",FP(m,n+1>>1)),0;

	if(K&1) return printf("%d\n",(int)(1ll*m*m%mod)),0;

	printf("%d\n",m);

	return 0;

}

B 取数游戏(贪心)

题目链接

原题：Codeforces 446B。

取一行对每一列的影响都是相同的，所以可以分开算，先计算取\(i\)次行的结果，此时每列减少\(i*P\)。

然后枚举选\(i\)次列，\(k-i\)次行，就行了。

话说我的贪心是怎么拿80分的。。最大的数据还过了。

//82ms	2144kb

#include <queue>

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 300000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=1005;

int sum[N];

LL f[100005];

std::priority_queue<LL> qr,qc;

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

int main()

{

	int n=read(),m=read(),K=read(),P=read();

	for(int i=1; i<=n; ++i)

	{

		int s=0;

		for(int j=1,tmp; j<=m; ++j) s+=tmp=read(),sum[j]+=tmp;

		qr.push(s);

	}

	for(int i=1; i<=m; ++i) qc.push(sum[i]);

	LL tmp,sc=1ll*m*P,sr=1ll*n*P;

	for(int i=1; i<=K; ++i)

		f[i]=f[i-1]+(tmp=qr.top()), qr.pop(), qr.push(tmp-sc);

	LL ans=f[K],now=0,delta=1ll*K*P;

	for(int i=1; i<=K; ++i)

		delta-=P, now+=tmp=qc.top(), qc.pop(), qc.push(tmp-sr), ans=std::max(ans,now+f[K-i]-delta*i);

	printf("%lld\n",ans);

	return 0;

}

C 魔方(模拟)

题目链接

对每个面上的每个格子标号，然后每次顺时针旋转，就把当前面旋转90度，然后处理一下相邻四个面就行了。

因为我的标号问题所以赋值要注意。。（考场上忘了这个gg）

另外两种操作就是顺时针旋转两次与三次。

注意操作有\(n\)个所以操作序列长度是\(2n\)。。

//6ms	672kb

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

#define ID(x,y,z) (9*((z)-1)+3*((x)-1)+y)

const int N=2e5+5;

int A[60],f[60];

char s[N];

inline bool End()

{

	for(int i=1; i<=54; ++i) if(f[i]!=i) return 0;

	return 1;

}

inline void Print(int *a,int l,int r)

{

	printf("Print(%d~%d):",l,r);

	for(int i=l; i<=r; ++i) printf("%d ",a[i]); puts("");

}

inline void Print2(int *a,int z)

{

	printf("Print2(%d):",z);

	for(int i=1,d=(z-1)*9; i<=9; ++i) printf("%d ",a[d+i]); puts("");

}

inline void Print3()

{

	puts(""); for(int i=1; i<=6; ++i) Print2(A,i); puts("");

}

inline void CW(int z)//Clockwise

{

	static int C[10];

	const int d=(z-1)*9;

	C[1]=A[d+7],C[2]=A[d+4],C[3]=A[d+1],C[4]=A[d+8],C[5]=A[d+5],C[6]=A[d+2],C[7]=A[d+9],C[8]=A[d+6],C[9]=A[d+3];

	for(int i=1; i<=9; ++i) A[d+i]=C[i];

}

inline void Move(int *a,int z,int f)

{

	const int d=(z-1)*9;

	switch(f)

	{

		case 0: a[1]=A[d+1],a[2]=A[d+2],a[3]=A[d+3]; break;

		case 1: a[1]=A[d+7],a[2]=A[d+8],a[3]=A[d+9]; break;

		case 2: a[1]=A[d+1],a[2]=A[d+4],a[3]=A[d+7]; break;

		case 3: a[1]=A[d+3],a[2]=A[d+6],a[3]=A[d+9]; break;

	}

}

inline void Move2(int *a,int z,int f)

{

	const int d=(z-1)*9;

	switch(f)

	{

		case 0: a[3]=A[d+1],a[2]=A[d+2],a[1]=A[d+3]; break;

		case 1: a[3]=A[d+7],a[2]=A[d+8],a[1]=A[d+9]; break;

		case 2: a[3]=A[d+1],a[2]=A[d+4],a[1]=A[d+7]; break;

		case 3: a[3]=A[d+3],a[2]=A[d+6],a[1]=A[d+9]; break;

	}

}

inline void Cover(int *a,int z,int f)

{

	const int d=(z-1)*9;

	switch(f)

	{

		case 0: A[d+1]=a[1],A[d+2]=a[2],A[d+3]=a[3]; break;

		case 1: A[d+7]=a[1],A[d+8]=a[2],A[d+9]=a[3]; break;

		case 2: A[d+1]=a[1],A[d+4]=a[2],A[d+7]=a[3]; break;

		case 3: A[d+3]=a[1],A[d+6]=a[2],A[d+9]=a[3]; break;

	}

}

inline void Rotate(const char c)

{

	static int B[60];

	switch(c)//0上 1下 2左 3右

	{

		case 'U': CW(2), Move2(B,6,0), Move2(B+3,3,1), Move(B+6,5,0), Move(B+9,1,0);

				  Cover(B,3,1), Cover(B+3,5,0), Cover(B+6,1,0), Cover(B+9,6,0);

				  break;

		case 'R': CW(5), Move(B,1,3), Move(B+3,2,3), Move(B+6,3,3), Move(B+9,4,3);

				  Cover(B,2,3), Cover(B+3,3,3), Cover(B+6,4,3), Cover(B+9,1,3);

				  break;

		case 'F': CW(1), Move(B,2,1), Move2(B+3,5,2), Move(B+6,4,0), Move2(B+9,6,3);

				  Cover(B,5,2), Cover(B+3,4,0), Cover(B+6,6,3), Cover(B+9,2,1);

				  break;

		case 'D': CW(4), Move(B,6,1), Move(B+3,1,1), Move2(B+6,5,1), Move2(B+9,3,0);

				  Cover(B,1,1), Cover(B+3,5,1), Cover(B+6,3,0), Cover(B+9,6,1);

				  break;

		case 'L': CW(6), Move(B,2,2), Move(B+3,1,2), Move(B+6,4,2), Move(B+9,3,2);

				  Cover(B,1,2), Cover(B+3,4,2), Cover(B+6,3,2), Cover(B+9,2,2);

				  break;

		case 'B': CW(3), Move(B,5,3), Move2(B+3,2,0), Move(B+6,6,2), Move2(B+9,4,1);

				  Cover(B,2,0), Cover(B+3,6,2), Cover(B+6,4,1), Cover(B+9,5,3);

				  break;

	}

}

void Calc(int n)

{

	for(int i=1; i<=n; ++i)

	{

		Rotate(s[i]);

		if(s[i+1]=='\'') Rotate(s[i]), Rotate(s[i]), ++i;

		else if(s[i+1]=='2') Rotate(s[i]), ++i;

	}

}

int main()

{

	scanf("%s",s+1);

	int n=strlen(s+1),ans=1;

	for(int i=1; i<=54; ++i) A[i]=i;

	Calc(n);

	for(int i=1; i<=54; ++i) f[i]=A[i];

	for(; !End(); ++ans)

		for(int i=1; i<=54; ++i) f[i]=A[f[i]];

	printf("%d\n",ans);

	return 0;

}

考试代码

B

#include <queue>

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

#define MAXIN 300000

//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=1005;

int sum[N];

std::priority_queue<LL> qr,qc;

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

int main()

{

//	freopen(".in","r",stdin);

//	freopen(".out","w",stdout);

	int n=read(),m=read(),K=read(),P=read();

	for(int i=1; i<=n; ++i)

	{

		int s=0;

		for(int j=1,tmp; j<=m; ++j) s+=tmp=read(),sum[j]+=tmp;

		qr.push(s);

	}

	for(int i=1; i<=m; ++i) qc.push(sum[i]);

	LL ans=0;

	for(int dx=0,dy=0; K--; )

	{

		LL x=qr.top()-dx, y=qc.top()-dy;

		if(x-1ll*K*m*P>y-1ll*K*n*P)

			dy+=P, ans+=x, qr.pop(), qr.push(x-m*P);

		else

			dx+=P, ans+=y, qc.pop(), qc.push(y-n*P);

	}

	printf("%lld\n",ans);

	return 0;

}/*

2 2 2 2

1 3

2 4

2 2 5 2

1 3

2 4

1 4 4 1

1 1 1 1

1 4 1 1

1 1 1 1

1 4 2 1

1 1 1 1

1 4 3 1

1 1 1 1

*/

C

//考场上的版本一。发现想简单了，然后换了6*8的状态。

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

const int N=1e5+5,END[10]={0,1,2,3,4,5,6,7};

int A[15];

char s[N];

int Gcd(int x,int y)

{

	return y?Gcd(y,x%y):x;

}

bool Solve2(int n)

{

	for(int i=1; i<=n; ++i) if(s[i]!='L'&&s[i]!='R') return 0;

	int cl=0,cr=0;

	for(int i=1; i<=n; ++i) s[i]=='L'?++cl:++cr;

	cl%=4, cr%=4;

	cl=cl?4/Gcd(4,cl):0;

	cr=cr?4/Gcd(4,cr):0;

	if(!cl||!cr) printf("%d\n",cl+cr);

	else printf("%lld\n",1ll*cl*cr/Gcd(cl,cr));//this shoule be max(ans,1)...

	return 1;

}

inline bool End3()

{

	for(int i=1; i<=7; ++i) if(A[i]!=i) return 0;

	return 1;

}

inline void Rotate3(int n,const char c)

{

	static int B[10];

	for(int i=1; i<=n; ++i)

		if(s[i]==c)

		{

			B[1]=A[4], B[2]=A[1], B[3]=A[2], B[4]=A[3];

			A[1]=B[1], A[2]=B[2], A[3]=B[3], A[4]=B[4];

		}

		else

		{

			B[4]=A[5], B[5]=A[6], B[6]=A[7], B[7]=A[4];

			A[4]=B[4], A[5]=B[5], A[6]=B[6], A[7]=B[7];

		}

}

bool Solve3(int n)

{

	for(int i=1; i<=n; ++i) if(s[i]!='D'&&s[i]!='B') return 0;

	int ans=0;

	for(int i=1; i<=7; ++i) A[i]=i;

	do{

		Rotate3(n,'D'), ++ans;

	}while(!End3());

	printf("%d\n",ans);

	return 1;

}

bool Solve4(int n)

{

	for(int i=1; i<=n; ++i) if(s[i]!='U'&&s[i]!='F') return 0;

	int ans=0;

	for(int i=1; i<=7; ++i) A[i]=i;

	do{

		Rotate3(n,'U'), ++ans;

	}while(!End3());

	printf("%d\n",ans);

	return 1;

}

inline bool End()

{

	for(int i=1; i<=12; ++i) if(A[i]!=i) return 0;

	return 1;

}

inline void Print(int *a,int l,int r)

{

	for(int i=l; i<=r; ++i) printf("%d ",a[i]); puts("");

}

inline void Rotate(int n)

{

	static int B[15];

	for(int i=1; i<=n; ++i,Print(A,1,12))

		switch(s[i])

		{

			case 'U': memcpy(B,A,sizeof B), B[1]=A[2],B[2]=A[3],B[3]=A[4],B[4]=A[1];

					  memcpy(A,B,sizeof B); break;

			case 'R': memcpy(B,A,sizeof B), B[2]=A[10],B[11]=A[2],B[6]=A[11],B[10]=A[6];

					  memcpy(A,B,sizeof B); break;

			case 'F': memcpy(B,A,sizeof B), B[10]=A[1],B[1]=A[9],B[9]=A[5],B[5]=A[10];

					  memcpy(A,B,sizeof B); break;

			case 'D': memcpy(B,A,sizeof B), B[6]=A[5],B[5]=A[8],B[8]=A[7],B[7]=A[6];

					  memcpy(A,B,sizeof B); break;

			case 'L': memcpy(B,A,sizeof B), B[9]=A[4],B[4]=A[12],B[12]=A[8],B[8]=A[9];

					  memcpy(A,B,sizeof B); break;

			case 'B': memcpy(B,A,sizeof B), B[3]=A[11],B[11]=A[7],B[7]=A[12],B[12]=A[3];

					  memcpy(A,B,sizeof B); break;

		}

}

int main()

{

//	freopen(".in","r",stdin);

//	freopen(".out","w",stdout);

	scanf("%s",s+1); int n=strlen(s+1);

	if(Solve2(n)) return 0;

	if(Solve3(n)) return 0;

	if(Solve4(n)) return 0;

	int ans=0;

	for(int i=1; i<=12; ++i) A[i]=i;

	do{

		Rotate(n), ++ans;

	}while(!End());

	printf("%d\n",ans);

	return 0;

}

11.1 正睿停课训练 Day14的相关教程结束。

《11.1 正睿停课训练 Day14.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!