ABC322刷题记

ABC322刷题记

T1.A

A - First ABC 2。

妥妥的简单题……

用find函数做就行。（如果不存在那个子串就返回-1，否则返回第一次出现位置）

注意题目中编号是从1开始的。

时间复杂度：O(log(n))。find函数有一定代价，我记得是log。

#include<bits/stdc++.h>
using namespace std;
string str="";
int n=0;
int main(){
    scanf("%d",&n);
    cin>>str;
    //输入
    str=" "+str;
    //处理：把0开头改成1开头
    printf("%d\n",str.find("ABC"));
    //输出答案
    return 0;
}

T2.B

B - Prefix and Suffix。

前两题都一样简单。

用substr截取出t中与s长度相同的前缀和后缀，分别和s比较即可。

时间复杂度先不算了，因为肯定够。

#include<bits/stdc++.h>
using namespace std;
int m=0,n=0;
string s="",t="";
int main(){
    scanf("%d%d",&n,&m);
    cin>>s>>t;
    //输入
    string front=t.substr(0,n),rear=t.substr(m-n,n);
    //去除前缀与后缀
    if(front==s&&rear==s){
        printf("0\n");
    }else{
        if(front==s&&rear!=s){
            printf("1\n");
        }else{
            if(front!=s&&rear==s){
                printf("2\n");
            }else{
                printf("3\n");
            }
        }
    }
    //对号入座，输出不错
    return 0;
}

T3.C

C - Festival。

还是辣墨简单……

用b数组记录某一天是否有烟花，在用ans数组从后往前算，其中ans[i]表示离第i天最近并且时间不比第i天早的放烟花的日子与第i天相差多少。

最后从1到n输出ans的对应项即可。

时间复杂度：O(n)，应该是最优的思路了。

#include<bits/stdc++.h>
#define M 220000
#define N 220000
using namespace std;
int ans[N]={},a[M]={},m=0,n=0;
bool b[N]={};
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
        b[a[i]]=true;
    }
    //输入，并维护b数组
    for(int i=n;i>=1;i--){
        if(b[i]==true){
            ans[i]=0;
            //①当前这一天就有烟花：距离为0
        }else{
            ans[i]=ans[i+1]+1;
            //②当前这一天没有烟花：比明天的距离多一天
        }
    }
    //计算ans
    for(int i=1;i<=n;i++){
        printf("%d\n",ans[i]);
    }
    //输出答案
    return 0;
}

T4.D

D - Polyomino。

客观来说，我这道题没做出来真有些丢人。

其实就是一个dfs，但是一个变量名害我找了1天6小时34分钟……

我们定义一个结构体，存储一块牌，如果一个坐标上有点，就记录为1，否则记录为0。支持项各个方向平移（如果会出格，就返回不能做，否则返回操作成功）、顺时针旋转、逆时针旋转操作，当然还要封装加法（把骨牌拼接起来，其实就是相同坐标的点记录的数相加，如果相加后和为0，就说明这里本来就没有点，如果为1就说明刚好有一个牌上有，如果大于1就说明有多个牌子上面有这个点，当然，只有当3块牌都记起来之后和为1才能说明这种摆法可能合法）、等于号（骨牌完全相同，用于判断拼完之后是不是和满牌相同）。

在dfs中，我们不难证明先旋转（遍历旋转次数，去时顺时针，回时逆时针），在平移（反方向的平移互相作为返回操作）是不会有问题的，当然要注意平移可以项各种方向平移多次。

最终大体流程是这样：使用dfs，遍历三个牌的操作，如果最后拼起来是满牌就说明可以达成目的，直接标记最终答案为“可行”，并一路退出回到主程序，否则继续往下遍历。遍历操做时，先考虑旋转，再考虑平移。最后输出Yes/No即可。

时间复杂度不好算，这里不展开描述，但是数据量都是4、16这类数，估计也没啥事。

#include<bits/stdc++.h>
using namespace std;
struct Info{
    int num[4][4];
    Info operator+(Info ot){
        Info ret={};
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                ret.num[i][j]=num[i][j]+ot.num[i][j];
            }
        }
        return ret;
    }
    //拼接
    bool operator==(Info ot){
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                if(num[i][j]!=ot.num[i][j]){
                    return false;
                }
            }
        }
        return true;
    }
    //判等
    bool down(){
        for(int i=0;i<4;i++){
            if(num[3][i]==1){
                return false;
            }
        }
        for(int i=3;i>=1;i--){
            for(int j=0;j<4;j++){
                num[i][j]=num[i-1][j];
            }
        }
        for(int i=0;i<4;i++){
            num[0][i]=0;
        }
        return true;
    }
    //下移
    bool left(){
        for(int i=0;i<4;i++){
            if(num[i][0]==1){
                return false;
            }
        }
        for(int i=0;i<=2;i++){
            for(int j=0;j<4;j++){
                num[j][i]=num[j][i+1];
            }
        }
        for(int i=0;i<4;i++){
            num[i][3]=0;
        }
        return true;
    }
    //左移
    bool right(){
        for(int i=0;i<4;i++){
            if(num[i][3]==1){
                return false;
            }
        }
        for(int i=3;i>=1;i--){
            for(int j=0;j<4;j++){
                num[j][i]=num[j][i-1];
            }
        }
        for(int i=0;i<4;i++){
            num[i][0]=0;
        }
        return true;
    }
    //右移
    bool up(){
        for(int i=0;i<4;i++){
            if(num[0][i]==1){
                return false;
            }
        }
        for(int i=0;i<=2;i++){
            for(int j=0;j<4;j++){
                num[i][j]=num[i+1][j];
            }
        }
        for(int i=0;i<4;i++){
            num[3][i]=0;
        }
        return true;
    }
    //上移
    void spina(){
        Info ret={};
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                ret.num[i][j]=num[3-j][i];
            }
        }
        memcpy(num,ret.num,sizeof(num));
        return;
    }
    //顺时针旋转
    void spinb(){
        Info ret={};
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                ret.num[i][j]=num[j][3-i];
            }
        }
        memcpy(num,ret.num,sizeof(num));
        return;
    }
    //逆时针旋转
};
Info inf[10]={};
bool ans=false;
inline void dfs(int d);
//深度优先搜索用到函数
inline void tmovew(int d);
//遍历旋转，用完后返回原始状态
inline void tmovex(int d);
//遍历横移，用完后返回原始状态
inline void tmovey(int d);
//遍历竖移，用完后返回原始状态
int main(){
    inf[4]={{{1,1,1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1}}};
    //满牌
    for(int i=0;i<4;i++){
        string str="";
        cin>>str;
        for(int j=0;j<4;j++){
            if(str[j]=='#'){
                inf[1].num[i][j]=1;
            }
        }
    }
    for(int i=0;i<4;i++){
        string str="";
        cin>>str;
        for(int j=0;j<4;j++){
            if(str[j]=='#'){
                inf[2].num[i][j]=1;
            }
        }
    }
    for(int i=0;i<4;i++){
        string str="";
        cin>>str;
        for(int j=0;j<4;j++){
            if(str[j]=='#'){
                inf[3].num[i][j]=1;
            }
        }
    }
    //输入，并处理成Info格式
    dfs(1);
    //dfs
    if(ans==false){
        printf("No\n");
    }else{
        printf("Yes\n");
    }
    //根据答案输出
    return 0;
}
inline void dfs(int d){
    if(d==4){
        //3个骨牌遍历完成
        if(inf[1]+inf[2]+inf[3]==inf[4]){
            ans=true;
            //若相加为满牌，就说明答案可行，直接记录答案为“Yes”，或者说true
        }
        return;
        //递归出口
    }
    if(ans==true){
        return;
        //已经找到答案，无需继续遍历
    }
    tmovew(d);
    //开始遍历旋转
    return;
}
inline void tmovew(int d){
    for(int i=0;i<=3;i++){
        for(int j=1;j<=i;j++){
            inf[d].spina();
        }
        //顺时针旋转相应次
        tmovex(d);
        //往下遍历横移
        for(int j=1;j<=i;j++){
            inf[d].spinb();
        }
        //逆时针转回去（回溯）
    }
    return;
}
inline void tmovex(int d){
    for(int i=0;i<=4;i++){
        int sum=0;
        //尽最大可能地往相应方向移动i次，sum记录实际上操作成功的次数，后面所有的sum都同理
        for(int j=1;j<=i;j++){
            if(inf[d].left()==true){
                sum++;
            }
        }
        //往左移动
        tmovey(d);
        //往下遍历竖移
        for(int j=1;j<=sum;j++){
            inf[d].right();
        }
        //往右移动，也就是回溯
    }
    for(int i=0;i<=4;i++){
        int sum=0;
        for(int j=1;j<=i;j++){
            if(inf[d].right()==true){
                sum++;
            }
        }
        //往右移动
        tmovey(d);
        //往下遍历竖移
        for(int j=1;j<=sum;j++){
            inf[d].left();
        }
        //往左移动，也就是回溯
    }
    return;
}
inline void tmovey(int d){
    for(int i=0;i<=4;i++){
        int sum=0;
        for(int j=1;j<=i;j++){
            if(inf[d].down()==true){
                sum++;
            }
        }
        //往下移动
        dfs(d+1);
        //往下递归
        for(int j=1;j<=sum;j++){
            inf[d].up();
        }
        //往上移动，也就是回溯
    }
    for(int i=0;i<=4;i++){
        int sum=0;
        for(int j=1;j<=i;j++){
            if(inf[d].up()==true){
                sum++;
            }
        }
        //往上移动
        dfs(d+1);
        //往下递归
        for(int j=1;j<=sum;j++){
            inf[d].down();
        }
        //往下移动，也就是回溯
    }
    return;
}