2018.10.17考试总结

2018.10.17考试总结

1、咒语

(curse.pas/c/cpp)
###【题目描述】
亮亮梦到自己来到了魔法城堡, 但一扇巨大的石门阻拦了他通向城堡内的路。正当他沮丧之际,突然发现门上有一处机关,机关上有一张很长的纸条。亮亮拿起纸条的一端,只见上面写着打开机关的方法: “打开机关需要念动符咒,咒语是一串长为 L 的由 0 和 1 组成的字符串。在这张长纸条上列了 n 个长为 L 的字符串,正确的咒语即是在纷繁的 2^L 种字符串中,与这些纸条上的字符串相异度之和最小,并且在满足这一条件下,0 的个数最多的字符串。两个字符串的相异度定义为对应位置不相等的字符对的个数。如‘011’和‘001’的相异度为 1,因为它们有且只有第二个位置上的字符不相等。 ”亮亮拉起纸条,只觉得纸条似乎永远也拉不完。这上面有着数以万计的字符串,而每一个字符串的长度也或百或千,以人力看来是无法得到正确的咒语。你能帮帮他,让他得以进入魔法城堡,一窥其中的奥秘吗?
###【输入格式】
第一行为一个数字 N 。
接下来的 N 行, 每行为一个长为 L 的 01 字符串。 数据保证 N 个字符串等长。
###【输出格式】
只有一行,是一个长为 L 的字符串 S,即为正确的咒语。
###【样例输入】
4
01011
01001
01101
10111
###【样例输出】
01001
###【数据规模】
对于 20%的数据,N<=5;
对于 60%的数据,N<=100;
对于 100%的数据,1<=N<=1000,1<=L<=1000。

简单题,见下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[1010][1010];
int n,k0,k1;
int main()
{
    freopen("curse.in","r",stdin);
    freopen("curse.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf(" %s",s[i]);
    int len=strlen(s[1]);
    for(int i=0;i<len;++i)
    {
        k0=0,k1=0;
        for(int j=1;j<=n;++j)
        {
            if(s[j][i]=='1')k1++;
            else k0++;
        }
        if(k0>=k1)printf("0");
        else printf("1");
    }
    return 0;
}

2、神光

(light.pas/c/cpp)
###【题目描述】
亮亮成功地念出了咒语,石门缓缓地自动移开,一道道绚丽的神光从城堡内激射而出。亮亮好奇而又兴奋地走入了城堡中,迎面有一座极长的魔法阵。魔法阵可以看作一条直线,它被均匀地分成了 1 000 000 000 个位置,一个位置可以看成是一个格子。有些位置上筑有法坛,一共 N 座。亮亮只有破了眼前的魔法阵,才能继续前进,而欲破法阵,必须毁掉所有的法坛。亮亮身前有两根法杖:一根颜色血红,能发红色神光,光芒可以笼罩连续 L个位置并摧毁这 L 个位置上所有的法坛,最多使用 R 次;另一根颜色碧绿,能发绿色神光,光芒可以笼罩连续 2L 个位置,并摧毁这 2L 个位置上所有的法坛,最多使用 G 次。法杖的神奇之处在于,L 的值必须由亮亮事先设定好,并且一经设定,便无法更改。亮亮需要在规定的次数下摧毁所有法坛,并且使得 L 最小。
###【输入格式】
第一行三个整数 N, R, G。
第 i (2<=i<=n+1) 行一个整数 ,表示第 i 座法坛的位置。
###【输出格式】
只有一个整数,表示 L 的最小值。
###【样例输入】
3 1 1
22
1
7
###【样例输出】
4
###【样例解释】
亮亮将 L 设为 4,并用红色神光笼罩 21-24 位置,用绿色神光笼罩 1-8 位置。
###【数据规模】
对于 50%的数据,N <= 100;
对于 100%的数据,1 <= N <= 2000,1 <= R, G,<= 1,000,000,000。

二分加dp
1.R+G>=N时 输出1
2.先把从小到大排序,然后二分枚举L的长度,对于每一个L,先预处理在b[i]表示第i点使用红法杖最远到达的点和c[i]表示第i点使用绿法杖最远到达的点,f[i][j]表示使用i个红法杖和使用j个绿法杖所能到达的最远点,可得f[i][j]=max(b[f[i-1][j]+1],c[f[i][j-1]+1])。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,r,g,a[2010],b[2010],c[2010],f[2010][2010];
bool ss(int L)
{
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j)
        {
            if(a[j]-a[i]+1<=L)b[i]=j;
            if(a[j]-a[i]+1<=L*2)c[i]=j;
        }
    b[n+1]=c[n+1]=n;
    for(int i=0;i<=r;++i)
        for(int j=0;j<=g;++j)
        {
            if(i!=0)f[i][j]=max(f[i][j],b[f[i-1][j]+1]);
            if(j!=0)f[i][j]=max(f[i][j],c[f[i][j-1]+1]);
        }
    if(f[r][g]==n)return 1;
    return 0;
}
int main()
{
    freopen("light.in","r",stdin);
    freopen("light.out","w",stdout);
    scanf("%d%d%d",&n,&r,&g);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    if(r+g>=n)
    {
        printf("1\n");
        return 0;
    }
    sort(a+1,a+1+n);
    a[0]=0;
    int ll=1,rr=a[n]-a[1]+1,ans;
    while(ll<=rr)
    {
        int mid=(ll+rr)>>1;
        if(ss(mid))rr=mid-1,ans=mid;
        else ll=mid+1;
    }
    printf("%d",ans);
    return 0;
}

3、迷宫

(maze.pas/c/cpp)
###【题目描述】
破了魔法阵后,亮亮进入了一座迷宫。这座迷宫叫做“梦境迷宫” ,亮亮只有走出这座迷宫,才能从睡梦中醒来。
梦境迷宫可以用无向图来表示。它共有 n 个点和 m 条双向道路,每条道路都有边权,表示通过这条道路所需的时间,且每条道路可以多次经过。亮亮位于一号点,而出口则是 n 号点。原本,亮亮该找到一条最短路,快速冲出迷宫,然而,梦境迷宫的特殊之处在于,如果沿着最短路到达出口,亮亮就会永远陷入梦境。因此,亮亮必须寻找一条次短路。次短路的长度须严格大于最短路(可以有多条)的长度,同时又不大于所有除最短路外的道路的长度。你的任务,就是编写一个程序,帮助亮亮找到通向出口的次短路。
###【输入格式】
第一行有两个整数 n、m,表示迷宫内共有 n 个点,m 条边。
接下来 m 行,每行三个整数 x、y、z,表示结点 x 和 y 之间连有一条边权为z 的无向边。
###【输出格式】
一个整数,表示次短路的长度。
###【样例输入】
4 4
1 2 2
2 4 4
2 3 3
3 4 4
###【样例输出】
9
###【样例解释】
最短路:1 -> 2 -> 4 (长度为 2+4=6)
次短路:1 -> 2 -> 3 -> 4 (长度为 2+3+4=9)
###【数据规模】
对于 100%的数据,1 <= n <= 5000,1 <= m <= 100,000。
对于 100%的数据,1 <= z <= 5000,z 表示无向边的边长。

严格次短路,从点1和点n,分别求一个最短路,枚举每一条边,求点1和点n到该路径两端的最短距离,每次进行比较比最短路长且比其他路径短的距离长度。

90分(不知道为啥分这么高的,求最短路,枚举最短路径上每一条路消失,再求最短路)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
struct Edge
{
    int u,v,w,nxt;
}e[200010];
int head[200010],tot,n,m,dis[5010],vis[5010],hee[5010],haa[5010],hhh=0x7fffffff;;
void add(int u,int v,int w)
{
    e[++tot].u=u;
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
int spfa()
{
    queue<int>q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w)
            {
                dis[v]=dis[u]+e[i].w;
                hee[v]=i;
                haa[v]=u;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return dis[n];
}
int spfa2()
{
    queue<int>q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w)
            {
                dis[v]=dis[u]+e[i].w;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return dis[n];
}
signed main()
{
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    cin>>n>>m;
    for(int i=1,u,v,w;i<=m;++i)
    {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
        hhh=min(hhh,w);
    }
    hhh*=2;
    int k=spfa();
    int zd=0x3f3f3f3f;
    int v=n,sd;
    while(v!=1)
    {
        sd=hee[v];
        int cc=e[sd].w;
        e[sd].w=0x3f3f3f3f;
        zd=min(spfa2(),zd);
        e[sd].w=cc;
        v=haa[v];
    }
    if(zd==k)zd+=hhh;
    cout<<zd<<"\n";
    return 0;
}

正解

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=5010;
const int INF=0x3f3f3f3f;
struct Edge
{
    int v,w,nxt;
}e[200100];
int dis1[N],dis2[N],n,m,tot,head[N];
bool vis[N];
void add(int u,int v,int w)
{
    e[++tot].v=v;
    e[tot].w=w;
    e[tot].nxt=head[u];
    head[u]=tot;
}
void spfa(int s,int *dis)
{
    queue<int>q;
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w)
            {
                dis[v]=dis[u]+e[i].w;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    scanf("%d%d",&n,&m);
    memset(dis1,0x3f,sizeof(dis1));
    memset(dis2,0x3f,sizeof(dis2));
    for(int i=1,u,v,w;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    spfa(1,dis1);
    spfa(n,dis2);
    int ans=INF,tmp;
    for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=e[j].nxt)
        {
            tmp=dis1[i]+dis2[e[j].v]+e[j].w;
            if(tmp>dis1[n]&&ans>tmp) ans=tmp;
        }
    printf("%d\n",ans);
    return 0;
}
全部评论

相关推荐

避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务