WorldCloud Pytorch jdbc foreach controller Font Awesome vue网站模板 vue循环数组 后台管理界面模板 ddos压力测试 html好看的字体样式 monkey安装 bootstrap居中对齐 docker创建容器 python安装教程 python环境设置 python中def的用法 python时间戳 python函数内定义函数 java中substring java集合遍历 java文件路径 java中scanner用法 php网络编程 网络电视软件下载 脚本软件 shutil 神龙kms js判断字符串相等 cg模宝 din字体下载 dnf武极刷图加点 疯狂java讲义 3d看图软件 ps水平翻转快捷键 视频后期处理软件 文明6万神殿 网络电子书 点状字体 lol特效盒子
当前位置: 首页 > 学习教程  > 编程语言

模拟+并查集做最短路

2020/8/11 19:24:21 文章标签:

【基础】聪明的小地鼠
Description
在学校里的试验田里面,种了n个大萝卜,小地鼠又非常的喜欢吃萝卜。它呢,就会出来偷偷的从试验田中偷萝卜。大萝卜都是种在一排地里面,认真的管理员,按照萝卜的位置早早的给萝卜编了号。希望能增加管理,保证产量。谁知道,小地鼠也有了自己的偷萝卜策略。 同样,在这个地里呢,正好也有n只小地鼠,这些小地鼠,他们都是按照顺序出来偷萝卜。小地鼠们根据自己的出场顺序编好号,然后开始根据自己的编号开始偷萝卜。因为,小地鼠的老大(即1号老鼠),很胖,所以他决定多偷萝卜了,而只是拿了1号萝卜,把剩余的萝卜交给他的小弟们。当然,他为了让管理员还能够有点收入,好以后继续种萝卜,就给小弟们,下达了一个命令。即每个地鼠只能拿自己编号倍数的大萝卜,但是不能拿与自己编号相同的萝卜。这样就能稍微给管理员留下一些萝卜了。可怜的管理员,你能告诉他,他最后能够剩下的大萝卜编号。

Input
有一个正整数n,代表大萝卜的个数(即地鼠的个数),(5 < n <= 1000)

Output
有若干个,代表侥幸存活下来的萝卜的编号。由小到大输出且两个编号间用两个空格隔开。

Sample Input
10
Sample Output
2 3 5 7

#include<bits/stdc++.h>
using namespace std;
bool ss(int x);
int a[1001];
int main()
{
    int n,i,gs=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        if(ss(i))
        {
            gs++;
            a[gs]=i;
        }
    }
    for(i=1;i<gs;i++)
    {
        printf("%d  ",a[i]);
    }
    cout<<a[gs]<<endl;
    return 0;
}
bool ss(int x)
{
    int i;
    if(x==2)
    {
        return true;
    }
    if(x<3)
    {
        return false;
    }
    for(i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
        {
            return false;
        }
    }
    return true;
}

【基础】喝醉的狱卒
Description
在一所监狱里有一条长长的走廊,沿着走廊排列着n个牢房,编号为1到n。每个牢房有一个囚犯,而且牢房的门都是锁着的。 一天晚上,狱卒很无聊,于是他就玩起了一个人的游戏。第一轮,他喝了一口威士忌,然后沿着走廊,将所有牢房的门打开。第二轮,他又喝了一口威士忌,然后又沿着走廊,将所有编号为2的倍数的牢房锁上。第三轮,他再喝一口威士忌,再沿着走廊,视察所有编号为3的倍数的牢房,如果牢房是锁着的,他就把它打开;如果牢房是开着的,他就把它锁上。他如此玩了n轮后,喝下最后一口威士忌,醉倒了。 当他醉倒后,一些犯人发现他们的牢房开着而且狱卒已经无能为力,他们立刻逃跑了。 给出牢房的数目n,请你确认最多有可能有多少犯人逃出了监狱?

Input
仅一行,为一个正整数n,n<=10000。

Output
仅一行,一个整数,为最多逃跑的犯人数

Sample Input
5
Sample Output
2

#include<bits/stdc++.h>
using namespace std;
bool bj[10001];
int main()
{
    int n,i,j,ans;
    cin>>n;
    ans=0;
    for(i=1;i<=n;i++)
    {
        bj[i]=true;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(j%i==0)
            {
                if(!bj[j])
                {
                    bj[j]=true;
                }
                else
                {
                    bj[j]=false;
                }
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(!bj[i])
        {
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

求数位上的数字
Description
给出二个整数N和K,求出N 的K次方的结果中的十位数和个位数的数字。

Input
二个整数N, K(2≤N,K≤100000000 )。

Output
二个数字(分别表示N 的K次方结果中的十位数和个位数的数字,用一个空格分隔)。

Sample Input
3 6
Sample Output
2 9

#include<bits/stdc++.h>
using namespace std;
long long ksm(long long yuans,long long mi);
int main()
{
    long long n,k;
    cin>>n>>k;
    cout<<ksm(n,k)/10<<' '<<ksm(n,k)%10<<endl;
	return 0;
}
long long ksm(long long yuans,long long mi)
{
    long long ans,t;
    ans=1;
    t=yuans;
    while(mi!=0)
    {
        if(mi%2==1)
        {
            ans=ans*t%100;;
        }
        t=t*t%100;
        mi/=2;
    }
    return ans;
}

猴子吃桃
Description
为庆祝今年桃子丰收,猴村的猴子们举办了一次有趣的换桃子吃的游戏。n 只猴子(编号为1到n )从左向右站成一排,每只猴子手上捧着某种口味的一个桃子(桃子的口味用一个小写字母表示,最多26种口味),但是猴子手上的桃子可能不是自己喜欢吃的口味。
换桃过程共进行m 轮,第i (1≤i ≤m )轮交换给出三个整数L i ,R i (1≤L i ≤R i ≤n )和C i ,表示第i 轮交换共进行C i 遍,每一遍从第L i 只猴子开始依次向右边的猴子传递自己手上的桃子,即第L i 只猴子传递给第L i +1只猴子,……,第R i - 1只猴子传递给第R i 只猴子,第R i 只猴子的桃子传递给第L i 只猴子。
请编程计算依次经过m 轮传递后,有多少只猴子手上桃子的口味是与自己喜欢的口味相同?。
Input
输入共m+4行。
第1行一个整数n ,表示猴子的数目。
第2行n 个小写字母,依次表示第1只猴子到第n 只猴子手上捧着的桃子口味。
第3行n 个小写字母,依次表示第1只猴子到第n 只猴子喜欢吃的桃子口味。
第4行一个整数m ,表示共进行m 轮交换操作。
接下来m 行,第i+4行三个整数L i ,R i 和C i ,表示第i 轮交换共进行C i 遍,每一遍从第L i 只猴子开始依次向右边的猴子传递桃子,第R i 只猴子的桃子传递给第L i 只猴子。
Output
输出一行,一个整数,表示依次经过m 轮交换后,手上桃子的口味与自己喜欢的口味相同的猴子数量。
Sample Input
7
cbcbacb
ababaca
2
1 3 1
4 7 2
Sample Output
1
Hint
【样例解释】

输入中有 7 只猴子,手上捧着的桃子口味从左到右依次为“cbcbacb”,喜欢吃的桃子口 味依次为“ababaca”,共进行两轮交换。

第一轮进行一遍交换,交换发生在第 1 只猴子到第 3 只猴子之间,一遍交换后的结果为 “ccbbacb”。

第二轮进行两遍交换,交换发生在第 4 只猴子到第 7 只猴子之间,第一遍交换后的结果 为“ccbbbac”,第二遍交换后的结果为“ccbcbba”。 经过两轮交换后,发现只有 1 只(第 7 只)猴子手上桃子的口味与自己喜欢的口味相同

【数据范围】

30%的数据,1≤n≤100,0≤m≤100,1 ≤Ci≤1000。

100%的数据,1≤n≤10000,0≤m≤1000,1≤Li≤Ri≤n,1 ≤Ci≤106。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a,b,c,i,j,k,ll;
    string s,t,s3="";
    cin>>n;
    cin>>s;
    getchar();
    cin>>t;
    getchar();
    cin>>m;
    s=' '+s;
    t=' '+t;
    s3.resize(n+1,' ');
    for(k=1;k<=m;k++)
    {
        scanf("%d%d%d",&a,&b,&c);
        ll=b-a+1;
        c%=ll;
        for(j=a;j<=b;j++)
        {
            s3[(j+c-a)%ll+a]=s[j];
        }
        for(j=a;j<=b;j++)
        {
            s[j]=s3[j];
        }
    }
    int gs=0;
    for(i=1;i<=n;i++)
    {
        if(s[i]==t[i])
        {
            gs++;
        }
    }
    cout<<gs<<endl;
    return 0;
}

最短路径2
Description
N个城市,标号从0到N-1,M条道路,第K条道路(K从0开始)的长度为2^K,求编号为0的城市到其他城市的最短距离。

Input
第一行两个正整数N(2<=N<=100)M(M<=500),表示有N个城市,M条道路,
接下来M行两个整数,表示相连的两个城市的编号。

Output
N-1行,表示0号城市到其他城市的最短路,如果无法到达,输出-1,数值太大的以MOD 100000 的结果输出。

Sample Input
4 3
0 1
1 2
2 0
Sample Output
1
3
-1

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3fffffff
#define MOD 100000
int p[101],ranks[101],d[101][101];
int Findid(int i);
void Union(int a,int b);
int Pow(long long x,long long y);
int main()
{
    int i,j,n,a,b,k,dist,aaa,m,bbb;
    while(cin>>n>>m)
    {
        for(i=0;i<100;i++)
        {
            d[i][i]=0;
            ranks[i]=1;
            p[i]=i;
        }

        for(k=0;k<m;k++)
        {
            scanf("%d%d",&a,&b);

            aaa=Findid(a);
            bbb=Findid(b);
            if(aaa==bbb)
            {
                continue;
            }
            dist=Pow(2,k);
            for(i=0;i<n;i++)
            {
                if(Findid(i)!=aaa)
                {
                    continue;
                }
                for(j=0;j<n;j++)
                {
                    if(Findid(j)!=bbb)
                    {
                        continue;
                    }
                    d[i][j]=(d[i][a]+d[b][j]+dist)%MOD;
                    d[j][i]=d[i][j];
                }
            }
            Union(a,b);
        }
        aaa=Findid(0);
        for(i=1;i<n;i++)
        {
            if(aaa==Findid(i))
            {
                printf("%d\n",d[0][i]);
            }
            else
            {
                printf("%d\n",-1);
            }
        }
    }
    return 0;
}
int Findid(int i)
{
    if(i!=p[i])
    {
        p[i]=Findid(p[i]);
    }
    return p[i];
}
void Union(int a,int b)
{
    int x,y;
    x=Findid(a);
    y=Findid(b);
    if(x==y)
    {
        return;
    }
    if(ranks[a]>=ranks[b])
    {
        p[y]=x;
        ranks[x]+=y;
    }
    else
    {
        p[x]=y;
        ranks[y]+=x;
    }
}
int Pow(long long x,long long y)
{
    int ans;
    long long t;
    ans=1;
    t=x;
    while(y!=0)
    {
        if(y%2==1)
        {
            ans=ans*t%MOD;;
        }
        t=t*t%MOD;
        y/=2;
    }
    return ans;
}

【基础】喜羊羊运动会——队列训练
Description
运动会开幕式时要举行入场仪式,届时每个代表队的精神风貌如何将给观众留下深刻的第一印象。为此,喜羊羊带领N只羊开始了艰苦的队列训练:立正、稍息、走正步……这些都是必修课。为了便于管理,喜羊羊还给每个队员都编了个学号,分别为1-N。 在训练之余,为了缓解大家的紧张情绪,同时考察一下队员们的应变能力,喜羊羊带着大家玩起了游戏: ①首先N只羊( 1 <= N <= 200000000 )按学号从小到大(即1…N)依次排成一列横队。 如N为6时,排成这样—— 1 2 3 4 5 6 ②然后喜羊羊报一个数K(1 <= K <= N ),表示从左数过来的第K只羊到第N只羊排到队伍的最左端。 如报的K为3,表示第3只羊到第6只羊排到最左端,重新排列后的队伍为:3 4 5 6 1 2 ③最后喜羊羊报一个数S(1 <= S <= N ),表示重新排列后从左数过来的第S只羊出列,求出列的这只羊的学号是多少? 如报的S为4,则输出6。

Input
一行,三个空格隔开的整数N K S(1 <= K,S <= N <= 200000000 )。

Output
一行,一个整数,表示出列的那只羊的学号。

Sample Input
6 3 4
Sample Output
6
Hint
对于50%的数据,n <= 180。 对于100%的数据,n <= 200000000。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,s,ans;
    cin>>n>>k>>s;
    if(n-k+1>=s)
    {
        ans=s+k-1;
    }
    else
    {
        ans=s-(n-k+1);
    }
    cout<<ans<<endl;
	return 0;
}

【基础】夏令营旗手
Description
2010 年“信息与未来”小学生夏令营将在常州市局前街小学进行,该校的何老师得知本校营员小明同学被营委会选为夏令营的小旗手,就准备到他家去通知他。由于他不是本班的学生,所以何老师不知道小明家住在什么地方。只从其他同学那里得知,小明住在未来小区一幢不超过100层的高楼中,但在哪一层不清楚。但其他同学提供了三条有用的信息: 1) 小明家的楼层号是一个素数; 2) 该楼层号化为二进制数后,其中1的个数是偶数; 3) 满足以上二个条件中,楼层号最大的一个。 请编写程序,输出满足条件1)、2)的楼层个数总数及小明家的楼层号。

Input

Output
一行:一个空格隔开的两个整数,即楼层个数总数和小明家的楼层号。

#include<bits/stdc++.h>
using namespace std;
bool ss(int x);
int main()
{
    int i,x,gs,lc,gs1;
    bool bj;
    bj=false;
    gs1=0;
    for(i=100;i>=1;i--)
    {
        if(ss(i)&&!bj)
        {
            x=i;
            gs=0;
            while(x!=0)
            {
                if(x%2!=0)
                {
                    gs++;
                }
                x/=2;
            }
            if(gs%2==0)
            {
                bj=true;
                lc=i;
            }
        }
        if(ss(i))
        {
            x=i;
            gs=0;
            while(x!=0)
            {
                if(x%2!=0)
                {
                    gs++;
                }
                x/=2;
            }
            if(gs%2==0)
            {
                gs1++;
            }
        }
    }
    cout<<gs1<<' '<<lc<<endl;
    return 0;
}
bool ss(int x)
{
    int i;
    if(x==2)
    {
        return true;
    }
    if(x<3)
    {
        return false;
    }
    for(i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
        {
            return false;
        }
    }
    return true;
}

【基础】计算表达式
Description
表达式的形式如:3+56-4 其中, 运算数为一位整数,运算符为 +、-、 三种,且运算符没有优先级的区分,一律自左向右计算。 如上例的计算过程为:3+56-4=86-4=48-4=44

Input
一行,即表达式字符串(长度小于100)

Output
一个整数,即表达式的计算结果(结果在-20000至20000之间)

Sample Input
3+5*6-4
Sample Output
44

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    int a,i,dq,hm;
    cin>>s;
    a=s.size();
    dq=s[0]-'0';
    for(i=1;i<a;i++)
    {
        if(s[i]=='+')
        {
            hm=s[i+1]-'0';
            dq+=hm;
        }
        if(s[i]=='-')
        {
            hm=s[i+1]-'0';
            dq-=hm;
        }
        if(s[i]=='*')
        {
            hm=s[i+1]-'0';
            dq*=hm;
        }
    }
    cout<<dq<<endl;
    return 0;
}

本文链接: http://www.dtmao.cc/news_show_100125.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?