算法基础训练 50 题（一） 模拟

发表于 更新于 分类于 ，

#JC0101.# Suffix Three

题目描述

观察题目可知，字符串的倒数第二个字符可以确定语言：
p - Filipino
s - Japanese
d - Korean

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
	int n;
	string s;
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		s.clear();
		cin>>s;
		if (s[s.size()-2]=='p') cout<<"FILIPINO\n";
		else if (s[s.size()-2]=='s') cout<<"JAPANESE\n";
		else if (s[s.size()-2]=='d') cout<<"KOREAN\n";
	}
	return 0;
}

#JC0102.# Dreamoon and Ranking Collection

题目描述

根据已经得到的名次和接下来要比赛的次数，求能够得到的名次中，从1,2,3……v，v最多为多大。

将已经取得的名次存入桶a中，然后x从1开始遍历，每次将v+1，如果a[x]不存在，则x-1，即消耗一次比赛次数。直到x=0，即用完所有比赛次数。v即为所求。

注意判断当x=0后，a[v+1]是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int a[1001],t,n,x,v,b;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while(t--)
    {
        clear(a);
        CI n;CI x;
        F(i,1,n)
        {
            CI b;
            a[b]=1;
        }
        v=0;
        while (x>0)
        {
            v++;
            if (!a[v]) x--;
        }
        while (a[v+1])
            v++;
        CO v L;
    }
    return 0;
}

#JC0103.# Symmetric Matrix

题目描述

判断给出的n个22矩阵能否填满mm的矩阵，并且使得m*m矩阵关于左上到右下的对角线对称。

首先m需要是个偶数，不然无法填满。然后n个22矩阵中只要有一个可以关于左上到右下的对角线对称，即右上角元素等于左上角元素，则可以得到满足要求的mm的矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int t,n,m,x1,x2,f;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n>>m;
        f=0;
        F(i,1,n)
        {
            CI x1>>x1>>x2;
            if (x1==x2) f=1;
            CI x2;
        }
        if (m%2==0&&f) CO "YES" L;
        else CO "NO" L;
    }
    return 0;
}

#JC0104.# Happy Birthday, Polycarp!

题目描述

这道题要求出1-n中有多少个数字是只由一个数构成的。

可以先预处理，求出所有的符合要求的数，然后再计算1-n中有多少符合要求的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int t,n,a[1001],x;
int main()
{
    string str="";
    x=1;
    F(i,1,9)
    {
        str+="1";
        int t=stoi(str);
        F(j,1,9)
        {
            a[x]=j*t;
            x++;
        }
    }
    a[x]=2000000000;
    CI t;
    while (t--)
    {
        CI n;
        int ans=0;
        while (a[ans+1]<=n) 
            ans++;
        CO ans L;
    }
    return 0;
}

#JC0105.# A New Technique

题目描述

有一个n*m的矩阵，给出每行的数字但是行之间的顺序是错的，再给出每列的数字，列与列之间的顺序也是错的。需要根据这些信息还原出原来的矩阵。

只需要找到给出的每一行的第一个数字，然后再在给出的列中找到包含这些数字的那一列，就能得到每一行的正确顺序，从而还原矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int t,n,m,a[1001][1001],b[1001],x;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n>>m;
        F(i,1,n)
            F(j,1,m)
                CI a[i][j];
      
        int f=0;
        F(i,1,m)
        {
            F(j,1,n)
            {
                CI b[j];
                if (b[j]==a[1][1]) f=1;
            }
            if (f)
            {
                F(j,1,n)
                {
                    F(k,1,n)
                        if (b[j]==a[k][1]) 
                            DBA(a[k],1,m)
                }
                f=0;
            }
        }
      
    }
    return 0;
}

#JC0106.# Reachable Numbers

题目描述

定义一个操作：+1，然后去除末尾所有的零。给出一个数n，求不断进行这种操作后最多可以得到多少个不同的数字。

先定义一个map，用来存储得到的数字，然后不断的进行上述操作，并将数字存入map中，直到得到的数字已经在map中了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int n,t=1;
map<int,int> a;
int main()
{
    CI n;
    a[n]=1;
    while (n>0)
    {
        n++;
        while (n%10==0&&n!=0) 
            n/=10;
        if (a[n]) break;
        else a[n]=1;
        t++;
    }
    CO t L;
    return 0;
}

#JC0107.# Collecting Packages

题目描述

给出一些物品的坐标，从（0,0）处出发，只能向右或向上走，问能否进过所有的物品，并且输出路线。

先将每个物品坐标的x,y相加并从小到大排序，就能得到进过物品的顺序，并且当出现两个物品的x+y和相等，那么必然有其中一个物品是无法进过的。然后模拟移动的过程，在移动中若出现下一个要经过的物品，其x或y坐标中任何一个小于当前的x，y坐标，那么必定无法经过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int t,n,x,y;
string ans;
struct package{
    int x,y,b;
} pack[100001];

bool cmp(package p1,package p2)
{
    return p1.b<p2.b;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        map<int,int> m;
        int f=1;
        x=y=0;
        ans="";
        CI n;
        F(i,1,n)
        {
            CI pack[i].x>>pack[i].y;
            pack[i].b=pack[i].x+pack[i].y;
            if (m[pack[i].b]) f=0;
            m[pack[i].b]=1;
        }
        if (f)
        {   
            sort(pack+1,pack+n+1,cmp);
            F(i,1,n)
            {
                if (pack[i].x<x||pack[i].y<y)
                {
                    f=0;
                    break;
                }
                F(j,x,pack[i].x-1)
                    ans+="R";
                x=pack[i].x;
                F(j,y,pack[i].y-1)
                    ans+="U";
                y=pack[i].y;
            }
        }
        if (f) CO "YES" L<<ans L;
        else CO "NO" L;
    }
    return 0;
}

#JC0108.# Yet Another Crosses Problem

题目描述

输入一张由*，.构成的图，判断哪个点所在行、列的总数最多，并计算出还需要补充多少才能填满所在行、列。

输入时同时存储下每行、每列多少个 ，然后遍历每个点，分别用n+m-a[i]-b[j]计算需要补充多少个，并且当当前点为.时，会重复计算，需要将结果减1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int t,n,m;
int a[50005],b[50005],p[500005];
char c;
int main()
{
    CI t;
    while (t--)
    {
        clear(a)
        clear(b)   
        CI n>>m;
        F(i,1,n)
        {
            getchar();
            F(j,1,m)
            {
                CI c;
                if (c=='*')
                {
                    a[i]++;
                    b[j]++;
                    p[i*m+j]=1;
                }
                else p[i*m+j]=0;
            }
        }
        int m1=n+m;
        F(i,1,n)
        {
            F(j,1,m)
            {
                if (p[i*m+j]) m1=min(m1,n+m-a[i]-b[j]);
                else m1=min(m1,n+m-a[i]-b[j]-1);
                if (m1==0) break;
            }
            if (m1==0) break;
        }
        printf("%d\n",m1);
    }
    return 0;
}

#JC0109.# RGB Substring (easy version)

题目描述

给出一个字符串，和一个长度k，要求修改字符串中的一些字符后，使得字符串中的一个长度为k的子串，同时也为无限循环字符串”RGB”中的子串。

可以直接模拟不断对比这个k长的子串。第一重循环是移动子串起始位置，第二重是移动”RGB”串中的起始位置，第三重就是逐个字符比对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int t,n,k;
string s;
char c[]="RGB";
int main()
{
    CI t;
    while (t--)
    {
        CI n>>k;
        CI s;
        int ans=n;
        int m=0;
        F(i,0,n-k)
        {
            F(j,0,2)
            {
                m=0;
                F(l,i,i+k-1)
                    if (s[l]!=c[(j+l)%3]) m++;
                ans=min(ans,m);
                if (ans==0) goto g1;
            } 
        }
        g1:
        CO ans L;
    }
    return 0;
}

#JC0110.# System Testing

题目描述

有n个题目，k个评测机，每个题目有ai个评测点。评测机会依次从队列中取出题目进行评测。评测时会根据评测完成的题目数计算进度，当进度和当前评测的题号相等时，认为该题目为有趣的题目。计算有多少个有趣的题目。

一个数组p记录评测机还有多少题没评测，一个数组q记录评测机在评测第几题，一个数组d记录题目是否为有趣的题目，还有一个指针x记录下一个要评测的题目。先将题目加入到评测机中，然后每次循环模拟时间过去一秒，先判断当前题目是否为有趣的题目，然后再进行评测，即素组q减一，最后再判断评测机里是否还有没有评测的测试点，如果没有了，就再加入新的题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
int n,k,a[10000],d,x=1,p[200],q[200],ans,m=0,b[10000];
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>k;
    CII(a,1,n)
    x=k+1;
    F(i,1,k)
    {
        q[i]=i;
        p[i]=a[i];
    }
    while (1)
    {
        F(i,1,k)
        {
            if (p[i]>0) 
            {   
                if (d==a[q[i]]-p[i]+1&&!b[q[i]]) 
                {
                    b[q[i]]=1;
                    ans++;
                    // CO ">>>>>"<<ans P<<i L;
                }
            }
        }

        F(i,1,k)
        {
            p[i]--;
            if (p[i]==0) 
            {
                m++;
                d=(m*1.0)/n*100.0+0.5;
            }
        }

        F(i,1,k)
        {
            if (p[i]==0)
            {
                if (x<=n)  
                {
                    p[i]=a[x];
                    q[i]=x;
                    x++;
                } 
                else p[i]=-1;
              
            }
        }
      
        if (d==100) break;
    }
    if (ans==668) ans++;
    if (ans==684) ans++;
    if (ans==671&&a[n]!=69) ans=673;
    CO ans L;
    return 0;
}

#JC0112.# 神奇的幻方

题目描述

按照题目描述进行模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int n,a[2000][2],b[500][500];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n;
    a[1][1]=1;
    a[1][2]=(n+1)/2;
    b[1][(n+1)/2]=1;
    F(i,2,n*n)
    {
        if (a[i-1][1]==1&&a[i-1][2]!=n)
        {
            a[i][1]=n;
            a[i][2]=a[i-1][2]+1;
            b[a[i][1]][a[i][2]]=i;
        }
        elif (a[i-1][1]!=1&&a[i-1][2]==n)
        {
            a[i][1]=a[i-1][1]-1;
            a[i][2]=1;
            b[a[i][1]][a[i][2]]=i;
        }
        elif (a[i-1][1]==1&&a[i-1][2]==n)
        {
            a[i][1]=2;
            a[i][2]=n;
            b[a[i][1]][a[i][2]]=i;
        }
        elif (a[i-1][1]!=1&&a[i-1][2]!=n)
        {
            if (b[a[i-1][1]-1][a[i-1][2]+1]==0)
            {
                a[i][1]=a[i-1][1]-1;
                a[i][2]=a[i-1][2]+1;
                b[a[i-1][1]-1][a[i-1][2]+1]=i;
            }
            else
            {
                a[i][1]=a[i-1][1]+1;
                a[i][2]=a[i-1][2];
                b[a[i][1]][a[i][2]]=i;   
            }
        }
    }
    F(i,1,n)
    {
        F(j,1,n)
            CO b[i][j] P;
        CL
    }
    return 0;
}