算法基础训练 50 题(一) 模拟

#JC0101. Suffix Three

题目描述

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

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]是否存在。

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个2*2矩阵能否填满m*m的矩阵,并且使得m*m矩阵关于左上到右下的对角线对称。

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

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中有多少符合要求的数。

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的矩阵,给出每行的数字但是行之间的顺序是错的,再给出每列的数字,列与列之间的顺序也是错的。需要根据这些信息还原出原来的矩阵。

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

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中了。

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坐标,那么必定无法经过。

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。

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”串中的起始位置,第三重就是逐个字符比对。

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减一,最后再判断评测机里是否还有没有评测的测试点,如果没有了,就再加入新的题目。

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. 神奇的幻方

题目描述

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

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;
}
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇