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;
}