紫书第三章-数组与字符串刷题总结

Llf0703 8月 06, 2018

我太菜了，已经沦落到天天刷水题的地步了。由于实在是太水了，我就只总结个别有价值的题。还有动规那一章迟早会总结完的（gugugu~）

例题

3-6 UVa1584-Circular Sequence

我一开始以为就是找到最小的那个然后再决定一下左边走还是右边走，后面才发现竟然只有4个字母，肯定有很多重复，而且还只有顺时针，显然这样不行。

然后做法就跟书上一样了，枚举从每个字母开始的字典序，和当前最优值比较即可。

~~话说这种水题总结来有什么意义，不过要是不总结我例题就没啥总结的了~~

#include<bits/stdc++.h>
using namespace std;

char cir[105];
int n,m,a,b,c;

int main()
{
    scanf("%d",&n);
    while (n--)
    {
        scanf("%s",cir);
        int mnid=0,len=strlen(cir);
        for (int i=0;i<len;i++)
        {
            for (int j=0;j<len;j++)
            {
                if (cir[(i+j)%len]<cir[(mnid+j)%len])
                {
                    mnid=i;
                    break;
                }
                else if (cir[(i+j)%len]>cir[(mnid+j)%len]) break;
            }
        }
        for (int i=0;i<len;i++)
            printf("%c",cir[(mnid+i)%len]);
        printf("\n");
    }
    return 0;
}

习题

3-3 UVa1225-Digit Counting

似乎网上很多人直接暴力就行，我还离线处理排了一遍序，优化了个log。

#include<bits/stdc++.h>
using namespace std;

int n,m,q[25],cnt,ans[10][25],now[10];

struct Query{
    int q,id;
} Q[25];

inline void work(int x)
{
    while (x)
    {
        now[x%10]++;
        x/=10;
    }
}

inline bool cmp(Query x,Query y)
{
    return x.q<y.q;
}

int main()
{
    cin>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>n;
        Q[i].q=n;
        Q[i].id=i;
    }
    sort(Q+1,Q+m+1,cmp);
    int j=1,last=-1;
    for (int i=1;i<=m;i++)
    {
        for (;j<=Q[i].q;j++) work(j);
        for (int k=0;k<=9;k++) ans[k][Q[i].id]=now[k];
    }
    for (int i=1;i<=m;i++)
    {
        for (int j=0;j<=8;j++) cout<<ans[j][i]<<" ";
        cout<<ans[9][i]<<endl;
    }
    return 0;
}

3-5 UVa227-Puzzle

我这道题做法大概是这样：

得到空格最开始位置
按照题意模拟，如果不合法，则标记后直接continue（否则会有多余输入）
因为操作有多行，所以每行都需要getline，读到0以后退出即可

坑点也挺多的，大概如下：

如果用getline的话最后一个字符如果没有是不会看成空格的，我后来直接改成不是字母就为空格
操作有多行
我最开始遇到不合法就直接退出，导致有输入被输到下一次操作
不合法操作除了越界还有操作不是ABLR！！！
这道题格式要求很严，注意多余空格和换行都要过滤掉，如果不想PE的话还可以用uDebug测一下

#include<bits/stdc++.h>
using namespace std;

int n,m,a,b,c,kase;

int main()
{
    for (;;)
    {
        string s[5];
        getline(cin,s[0]);
        int x=0,y=0;
        if (s[0][0]=='Z') break;
        if (kase) cout<<endl;
        printf("Puzzle #%d:\n",++kase);
        for (int i=1;i<5;i++) getline(cin,s[i]);
        for (int i=0;i<5;i++)
        {
            for (int j=0;j<5;j++)
            {
                if (s[i][j]<'A' || s[i][j]>'Z')
                {
                    x=i;
                    y=j;
                    break;
                }
            }
        }
        bool done=0;
        bool can=1;
        for (;;)
        {
            string q;
            getline(cin,q);
            for (int i=0;i<q.length();i++)
            {
                if (q[i]=='0')
                {
                    done=1;
                    break;
                }
                if (!can) continue;
                else if (q[i]=='A')
                {
                    if (x==0) can=0;
                    else
                    {
                        s[x][y]=s[x-1][y];
                        s[x-1][y]=' ';
                        x--;
                    }
                }
                else if (q[i]=='B')
                {
                    if (x==4) can=0;
                    else
                    {
                        s[x][y]=s[x+1][y];
                        s[x+1][y]=' ';
                        x++;
                    }
                }
                else if (q[i]=='L')
                {
                    if (y==0) can=0;
                    else
                    {
                        s[x][y]=s[x][y-1];
                        s[x][y-1]=' ';
                        y--;
                    }
                }
                else if (q[i]=='R')
                {
                    if (y==4) can=0;
                    else
                    {
                        s[x][y]=s[x][y+1];
                        s[x][y+1]=' ';
                        y++;
                    }
                }
                else can=0;
            }
            if (done)
            {
                if (!can) printf("This puzzle has no final configuration.\n");
                else
                {
                    for (int i=0;i<5;i++)
                    {
                        for (int j=0;j<4;j++) cout<<s[i][j]<<" ";
                        cout<<s[i][4];
                        cout<<"\n";
                    }
                }
                break;
            }
        }
    }
    return 0;
}

3-8 UVa202-Repeating Decimals

我最开始发现50位的话double肯定不够用啊，然后到网上一看才发现自己zz了。除的过程就跟竖式除法一样 $n \times 10 / m$ 就行了，其它的枚举循环节即可。

#include<bits/stdc++.h>
using namespace std;

int n,m,a,b,c;
int s[100005],id[100005];

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        memset(s,0,sizeof(s));
        memset(id,0,sizeof(id));
        s[0]=n/m;
        printf("%d/%d = %d.",n,m,s[0]);
        n%=m;
        int cnt=1;
        while (n && !id[n])
        {
            id[n]=cnt;
            s[cnt]=n*10/m;
            n=n*10%m;
            cnt++;
        }
        if (!n)
        {
            for (int i=1;i<cnt;i++) printf("%d",s[i]);
            printf("(0)\n");
        }
        else
        {
            for (int i=1;i<id[n];i++) printf("%d",s[i]);
            printf("(");
            for (int i=id[n];i<=min(cnt-1,50);i++) printf("%d",s[i]);
            if (cnt>50) printf("...");
            printf(")\n");
        }
        printf("   %d",!n ? 1 : cnt-id[n]);
        printf(" = number of digits in repeating cycle\n\n");
    }
    return 0;
}

完了，就酱。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/aoapc-book-3.html