10月17日考试 题解（位运算+状压DP+打表+大模拟）

· · 个人记录

T1 神奇的位运算

题目大意：给定n个长度为m的01串，每一位都有一种位运算，为与(&)，或(|)，异或(^)的一种。现为了确定每一位的位运算的种类，问最少添加多少字符串。

可以发现每一位都必须至少有两个1和一个0。判断一下即可。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=505;
char s[N];
int T,n,m,num[N][2];
int main(){
    scanf("%d",&T);
    while(T--)
    {
        memset(num,0,sizeof(num));
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
        {
            scanf("%s",s+1);
            for (int j=1;j<=m;j++)
                num[j][s[j]-'0']++;
        }
        int k=0;
        for (int i=1;i<=m;i++)
        {
            int flag=0;
            if (num[i][0]<1) flag++;
            if (num[i][1]<2) flag+=2-num[i][1];
            k=max(flag,k);
        }
        printf("%d\n",k);
    }
    return 0;
}

T2 终焉之数列

题目大意：给定一个长度为n的数列a_i，现要求确定一个长度相等的序列b_i，使得b中任意两个数互质且最小化\sum\limits_{i=1}^n |a_i-b_i|。n\leq 100,a_i\leq 30。

发现1-58内只有16个质数，可以考虑状压（选59和选1是等价的）。

设f_{i,s}表示前i个数质因数状态为s的方案数。有转移：

f_{i+1,s'}=f_{i,s}+|num-a_i|

其中，s'为后继状态，num为一个合法的数。对于每个s合法的num可以预处理得到，对于s和num的s'也可以预处理得到。题目要求输出方案，记录一下前驱即可。时间复杂度O(2^{16}\times 58\times n)。

代码：

#include<cstdio>
#include<iostream>
#include<stack>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
const int N=105;
const int M=65536;
int prime[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
int f[N][M+5],g[N][M+5],t[N][M+5],s[N][M+5],a[N],n;
vector<int> v[M+5];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f; 
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for(int i=0;i<(1<<16);i++){
        for(int j=1;j<=58;j++){
            int flag=0;
            for(int k=1;k<=16;k++){
                if((j%prime[k]==0)&&(i&(1<<(k-1)))){
                    flag=1;
                    break;
                }
            }
            if(flag==0){
                v[i].push_back(j);
                int ss=i;
                for(int k=1;k<=16;k++){
                    if((j%prime[k]==0)&&((i&(1<<(k-1)))==0)){
                        ss|=(1<<(k-1));
                    }
                }
                s[j][i]=ss;
            }
        }
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=0;i<(1<<16);i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<v[i].size();k++){
                if(f[j+1][s[v[i][k]][i]]>f[j][i]+abs(v[i][k]-a[j+1])){
                    f[j+1][s[v[i][k]][i]]=f[j][i]+abs(v[i][k]-a[j+1]);
                    g[j+1][s[v[i][k]][i]]=v[i][k];
                    t[j+1][s[v[i][k]][i]]=i;
                }
            }
        }
    }
    int pos,minn=0x3f3f3f3f;
    for(int i=0;i<(1<<16);i++){
        if(f[n][i]<minn){
            pos=i;
            minn=f[n][i];
        }
    }
    stack<int> s;
    for(int i=n;i>=1;i--){
        s.push(g[i][pos]);
        pos=t[i][pos];
    }
    while(!s.empty()){
        int x=s.top();
        s.pop();
        printf("%d ",x);
    }
    return 0;
}

T3 下棋

题目大意：给定n个大小为1\times l_i的棋盘，两个人轮流在上面下棋。规定落子的地方不能有棋子，且不能与其它棋子相邻。问是否先手必胜。

傻逼题。对sg函数打表发现循环节为34，直接判一下即可……

代码：

#include<bits/stdc++.h>
#define reg register
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)
char B[1<<15],*S=B,*T=B;
int read()
{
    reg int s=0,f=1; reg char ch;
    for(;(ch=getchar())<'0'||ch>'9';ch=='-'?f=-f:0);
    for(;ch>='0'&&ch<='9';s=s*10+ch-'0',ch=getchar());
    return s*f;
}
int sg[110]={0,1},vis[110];
int SG(reg int x) {return x<=51?sg[x]:sg[51+(x-51)%34+(!((x-51)%34)?34:0)];}
int main()
{
    for(reg int i=2,k;i<=85;++i)
    {
        vis[sg[i-2]]=i;
        for(reg int j=0;j<=i-3;++j)
            vis[sg[j]^sg[i-3-j]]=i;
        for(k=0;vis[k]==i;++k);
        sg[i]=k;
    }
    for(reg int t=read();t--;)
    {
        reg int ans=0;
        for(reg int n=read();n--;ans^=SG(read()));
        puts(ans?"Alice":"Bob");
    }
    return 0;
}

T4 魔方

题目大意：给定一个三阶魔方，每个格子上有一个数字。给定其平面展开图。对于三阶魔方有18种旋转操作。问经过若干次旋转之后的展开图。

这题太TM傻逼了。没有任何技术含量，就纯粹模拟。让我当了一会码农……

如果旋转的不是中间的部分也会带着旁边的一面旋转……还有注意格子与格子的对应关系（说多了都是泪QAQ）。

没什么多说的，直接上代码……

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int a[7][5][5],tmp[7][5][5];
char s[10005];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//1:3->1->6->5->3
inline void r1(int j)
{
    for (int i=1;i<=3;i++)
    {
        a[1][i][j]=tmp[6][i][j];
        a[3][i][j]=tmp[1][i][j];
        a[5][i][j]=tmp[3][i][j];
        a[6][i][j]=tmp[5][i][j];
    }
    if (j==2) return;
    if (j==1)
    {
        a[2][1][3]=tmp[2][1][1];a[2][2][3]=tmp[2][1][2];a[2][3][3]=tmp[2][1][3];
        a[2][1][2]=tmp[2][2][1];a[2][2][2]=tmp[2][2][2];a[2][3][2]=tmp[2][2][3];
        a[2][1][1]=tmp[2][3][1];a[2][2][1]=tmp[2][3][2];a[2][3][1]=tmp[2][3][3];
    }
    else
    {
        a[4][3][1]=tmp[4][1][1];a[4][2][1]=tmp[4][1][2];a[4][1][1]=tmp[4][1][3];
        a[4][3][2]=tmp[4][2][1];a[4][2][2]=tmp[4][2][2];a[4][1][2]=tmp[4][2][3];
        a[4][3][3]=tmp[4][3][1];a[4][2][3]=tmp[4][3][2];a[4][1][3]=tmp[4][3][3];
    }
}
inline void f1(int j)
{
    for (int i=1;i<=3;i++)
    {
        a[5][i][j]=tmp[6][i][j];
        a[3][i][j]=tmp[5][i][j];
        a[1][i][j]=tmp[3][i][j];
        a[6][i][j]=tmp[1][i][j];
    }
    if (j==2) return;
    if (j==1)
    {
        a[2][1][1]=tmp[2][1][3];a[2][1][2]=tmp[2][2][3];a[2][1][3]=tmp[2][3][3];
        a[2][2][1]=tmp[2][1][2];a[2][2][2]=tmp[2][2][2];a[2][2][3]=tmp[2][3][2];
        a[2][3][1]=tmp[2][1][1];a[2][3][2]=tmp[2][2][1];a[2][3][3]=tmp[2][3][1];    
    }
    else
    {
        a[4][1][1]=tmp[4][3][1];a[4][1][2]=tmp[4][2][1];a[4][1][3]=tmp[4][1][1];
        a[4][2][1]=tmp[4][3][2];a[4][2][2]=tmp[4][2][2];a[4][2][3]=tmp[4][1][2];
        a[4][3][1]=tmp[4][3][3];a[4][3][2]=tmp[4][2][3];a[4][3][3]=tmp[4][1][3];
    }
}
inline void r2(int j)
{
    if (j==1)
    {
        a[4][1][1]=tmp[1][3][1];a[4][2][1]=tmp[1][3][2];a[4][3][1]=tmp[1][3][3];
        a[1][3][3]=tmp[2][1][3];a[1][3][2]=tmp[2][2][3];a[1][3][1]=tmp[2][3][3];
        a[2][1][3]=tmp[5][1][1];a[2][2][3]=tmp[5][1][2];a[2][3][3]=tmp[5][1][3];
        a[5][1][3]=tmp[4][1][1];a[5][1][2]=tmp[4][2][1];a[5][1][1]=tmp[4][3][1];
    }
    if (j==2)
    {
        a[4][1][2]=tmp[1][2][1];a[4][2][2]=tmp[1][2][2];a[4][3][2]=tmp[1][2][3];
        a[1][2][3]=tmp[2][1][2];a[1][2][2]=tmp[2][2][2];a[1][2][1]=tmp[2][3][2];
        a[2][1][2]=tmp[5][2][1];a[2][2][2]=tmp[5][2][2];a[2][3][2]=tmp[5][2][3];
        a[5][2][3]=tmp[4][1][2];a[5][2][2]=tmp[4][2][2];a[5][2][1]=tmp[4][3][2];
    }
    if (j==3)
    {
        a[4][1][3]=tmp[1][1][1];a[4][2][3]=tmp[1][1][2];a[4][3][3]=tmp[1][1][3];
        a[1][1][3]=tmp[2][1][1];a[1][1][2]=tmp[2][2][1];a[1][1][1]=tmp[2][3][1];
        a[2][1][1]=tmp[5][3][1];a[2][2][1]=tmp[5][3][2];a[2][3][1]=tmp[5][3][3];
        a[5][3][3]=tmp[4][1][3];a[5][3][2]=tmp[4][2][3];a[5][3][1]=tmp[4][3][3];
    }
    if (j==2) return;
    if (j==1)
    {
        a[3][1][3]=tmp[3][1][1];a[3][2][3]=tmp[3][1][2];a[3][3][3]=tmp[3][1][3];
        a[3][1][2]=tmp[3][2][1];a[3][2][2]=tmp[3][2][2];a[3][3][2]=tmp[3][2][3];
        a[3][1][1]=tmp[3][3][1];a[3][2][1]=tmp[3][3][2];a[3][3][1]=tmp[3][3][3];
    }
    if (j==3)
    {
        a[6][3][1]=tmp[6][1][1];a[6][2][1]=tmp[6][1][2];a[6][1][1]=tmp[6][1][3];
        a[6][3][2]=tmp[6][2][1];a[6][2][2]=tmp[6][2][2];a[6][1][2]=tmp[6][2][3];
        a[6][3][3]=tmp[6][3][1];a[6][2][3]=tmp[6][3][2];a[6][1][3]=tmp[6][3][3];
    }
}
//2:4->1->2->5->4
inline void f2(int j)
{
    if (j==1)
    {
        a[1][3][1]=tmp[4][1][1];a[1][3][2]=tmp[4][2][1];a[1][3][3]=tmp[4][3][1];
        a[2][1][3]=tmp[1][3][3];a[2][2][3]=tmp[1][3][2];a[2][3][3]=tmp[1][3][1];
        a[5][1][1]=tmp[2][1][3];a[5][1][2]=tmp[2][2][3];a[5][1][3]=tmp[2][3][3];
        a[4][1][1]=tmp[5][1][3];a[4][2][1]=tmp[5][1][2];a[4][3][1]=tmp[5][1][1];
    }
    if (j==2)
    {
        a[1][2][1]=tmp[4][1][2];a[1][2][2]=tmp[4][2][2];a[1][2][3]=tmp[4][3][2];
        a[2][1][2]=tmp[1][2][3];a[2][2][2]=tmp[1][2][2];a[2][3][2]=tmp[1][2][1];
        a[5][2][1]=tmp[2][1][2];a[5][2][2]=tmp[2][2][2];a[5][2][3]=tmp[2][3][2];
        a[4][1][2]=tmp[5][2][3];a[4][2][2]=tmp[5][2][2];a[4][3][2]=tmp[5][2][1];
    }
    if (j==3)
    {
        a[1][1][1]=tmp[4][1][3];a[1][1][2]=tmp[4][2][3];a[1][1][3]=tmp[4][3][3];
        a[2][1][1]=tmp[1][1][3];a[2][2][1]=tmp[1][1][2];a[2][3][1]=tmp[1][1][1];
        a[5][3][1]=tmp[2][1][1];a[5][3][2]=tmp[2][2][1];a[5][3][3]=tmp[2][3][1];
        a[4][1][3]=tmp[5][3][3];a[4][2][3]=tmp[5][3][2];a[4][3][3]=tmp[5][3][1];
    }
    if (j==2) return;
    if (j==1)
    {
        a[3][1][1]=tmp[3][1][3];a[3][1][2]=tmp[3][2][3];a[3][1][3]=tmp[3][3][3];
        a[3][2][1]=tmp[3][1][2];a[3][2][2]=tmp[3][2][2];a[3][2][3]=tmp[3][3][2];
        a[3][3][1]=tmp[3][1][1];a[3][3][2]=tmp[3][2][1];a[3][3][3]=tmp[3][3][1];
    }
    if (j==3)
    {
        a[6][1][1]=tmp[6][3][1];a[6][1][2]=tmp[6][2][1];a[6][1][3]=tmp[6][1][1];
        a[6][2][1]=tmp[6][3][2];a[6][2][2]=tmp[6][2][2];a[6][2][3]=tmp[6][1][2];
        a[6][3][1]=tmp[6][3][3];a[6][3][2]=tmp[6][2][3];a[6][3][3]=tmp[6][1][3];
    }
}
//3:3->4->6->2->3
inline void f3(int i)
{
    for (int j=1;j<=3;j++)
    {
        a[4][i][j]=tmp[3][i][j];
        a[6][3-i+1][3-j+1]=tmp[4][i][j];
        a[2][i][j]=tmp[6][3-i+1][3-j+1];
        a[3][i][j]=tmp[2][i][j];
    }
    if (i==2) return;
    if (i==1)
    {
        a[1][1][1]=tmp[1][1][3];a[1][1][2]=tmp[1][2][3];a[1][1][3]=tmp[1][3][3];
        a[1][2][1]=tmp[1][1][2];a[1][2][2]=tmp[1][2][2];a[1][2][3]=tmp[1][3][2];
        a[1][3][1]=tmp[1][1][1];a[1][3][2]=tmp[1][2][1];a[1][3][3]=tmp[1][3][1];
    }
    else
    {
        a[5][1][1]=tmp[5][3][1];a[5][1][2]=tmp[5][2][1];a[5][1][3]=tmp[5][1][1];
        a[5][2][1]=tmp[5][3][2];a[5][2][2]=tmp[5][2][2];a[5][2][3]=tmp[5][1][2];
        a[5][3][1]=tmp[5][3][3];a[5][3][2]=tmp[5][2][3];a[5][3][3]=tmp[5][1][3];
    }
}
inline void r3(int i)
{
    for (int j=1;j<=3;j++)
    {
        a[3][i][j]=tmp[4][i][j];
        a[4][i][j]=tmp[6][3-i+1][3-j+1];
        a[6][3-i+1][3-j+1]=tmp[2][i][j];
        a[2][i][j]=tmp[3][i][j];
    }
    if (i==2) return;
    if (i==1)
    {
        a[1][1][3]=tmp[1][1][1];a[1][2][3]=tmp[1][1][2];a[1][3][3]=tmp[1][1][3];
        a[1][1][2]=tmp[1][2][1];a[1][2][2]=tmp[1][2][2];a[1][3][2]=tmp[1][2][3];
        a[1][1][1]=tmp[1][3][1];a[1][2][1]=tmp[1][3][2];a[1][3][1]=tmp[1][3][3];
    }
    if (i==3)
    {
        a[5][3][1]=tmp[5][1][1];a[5][2][1]=tmp[5][1][2];a[5][1][1]=tmp[5][1][3];
        a[5][3][2]=tmp[5][2][1];a[5][2][2]=tmp[5][2][2];a[5][1][2]=tmp[5][2][3];
        a[5][3][3]=tmp[5][3][1];a[5][2][3]=tmp[5][3][2];a[5][1][3]=tmp[5][3][3];
    }
}
inline void output()
{
    for (int i=1;i<=3;i++)
        printf("%d %d %d \n",a[1][i][1],a[1][i][2],a[1][i][3]);
    for (int i=1;i<=3;i++)
    {
        printf("%d %d %d ",a[2][i][1],a[2][i][2],a[2][i][3]);
        printf("%d %d %d ",a[3][i][1],a[3][i][2],a[3][i][3]);
        printf("%d %d %d \n",a[4][i][1],a[4][i][2],a[4][i][3]);
    }
    for (int i=1;i<=3;i++)
        printf("%d %d %d \n",a[5][i][1],a[5][i][2],a[5][i][3]);
    for (int i=1;i<=3;i++)
        printf("%d %d %d \n",a[6][i][1],a[6][i][2],a[6][i][3]);
}
int main()
{
    for (int i=1;i<=3;i++)
        for (int j=1;j<=3;j++) a[1][i][j]=read();
    for (int i=1;i<=3;i++)
        for (int j=1;j<=9;j++)
        {
            if (j<=3) a[2][i][j]=read();
            if (j>3&&j<=6) a[3][i][j-3]=read();
            if (j>6&&j<=9) a[4][i][j-6]=read();
        }
    for (int i=1;i<=6;i++)
        for (int j=1;j<=3;j++)
        {
            if (i<=3) a[5][i][j]=read();
            else a[6][i-3][j]=read();
        }
    memcpy(tmp,a,sizeof(tmp));
    scanf("%s",s+1);
    int len=strlen(s+1);
    for (int i=1;i<=len;i++)
    {
        if (s[i]=='a'||s[i]=='b'||s[i]=='c') f1(s[i]-'a'+1);
        if (s[i]=='A'||s[i]=='B'||s[i]=='C') r1(s[i]-'A'+1);
        if (s[i]=='d'||s[i]=='e'||s[i]=='f') f2(s[i]-'d'+1);
        if (s[i]=='D'||s[i]=='E'||s[i]=='F') r2(s[i]-'D'+1);
        if (s[i]=='h'||s[i]=='i'||s[i]=='j') f3(s[i]-'h'+1);
        if (s[i]=='H'||s[i]=='I'||s[i]=='J') r3(s[i]-'H'+1);
        memcpy(tmp,a,sizeof(tmp));
    }
    output();
    return 0;
}