首页 > 代码库 > SDUT ACM月赛（被各种取值范围坑的无力吐槽）

SDUT ACM月赛（被各种取值范围坑的无力吐槽）

2024-08-05 16:52:09   224人阅读

神奇的树

题目链接->>>>>>>>猛戳这

看到10^5次方当时就吓哭了，起初想到是不是x，m的奇偶数的关系，好吧我承认我想多了，wa。后来直接一咬牙暴力，水过~

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
    int x,m;
    int flag;
    int cnt;
    while(~scanf("%d %d",&x,&m))
    {
        flag=0;
        cnt=0;
        x=2*x;
        while(x)
        {
            x=x%m;
            x=2*x;
            if(!x)
            {
                flag=1;
                printf("Yes\n");
                break;
            }
            if(cnt>=1000)
               break;
              cnt++;
        }
        //printf("%d\n",cnt);
        if(!flag)
          printf("No\n");
    }
    return 0;
}

这题实在不知道起啥名好了(两种方法)

题目链接->>>>>>>>>点我点我啊

类似划分区间的做法。一开始先把最大值最小值初始化a[0]，然后往后找，要是碰到的数比当前最大数大，最大值和最小值同时指向比当前最大值大的这个数，相当于从前一个区间蹦到了后一个区间。否则的话就一直找最小值。飞哥还给了一种做法看完之后五体投地，惊为天人，其实思路差不多，只不过他是一直维护最大值而已

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
long long a[100000010];
int main()
{
    int n,i;
    long long max,min;
    long long c;
    long long cnt;
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++)
          scanf("%lld",&a[i]);
        min=max=a[0];
        cnt=a[0]-a[1];
        for(i=1;i<n;i++)
        {
            if(max<a[i])
            {
                max=a[i];
                min=a[i];
                if(i!=n-1)
                {
                    c=a[i]-a[i+1];
                    if(cnt<c)
                      cnt=c;
                }
            }
            else if(min>a[i])
            {
                min=a[i];
                c=max-min;
                if(cnt<c)
                 cnt=c;
            }
           //printf("%lld %lld<<<<<",max,min);

        }
        printf("%d\n",cnt);
    }
    return 0;
}

orz飞神

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define inf 999999999
int a[1100000];
int main()
{
    int n, i, j, max1, maxv;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        maxv=-inf;
        max1=a[0];
        for(i=1;i<n;i++)
        {
            maxv=max(maxv,max1-a[i]);
            max1=max(max1,a[i]);
        }
        printf("%d\n",maxv);
    }
    return 0;
}

炸学校（spfa+前向星）

题目链接->>>>>>>>>>点我啊点我啊

这道题其实就是一道最短路的问题，但是裸地最短路有点区别，这个是找起点到终点的最短路但是前提是每个点都得遍历到。其实就是找起点到所有点的最短，终点到所有点的最短，然后找两个和的最大值。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
using namespace std;
#define inf 99999999999
struct node
{
    int v,w;
    int next;
}edge[2000010];
int dis[1010];
int vis[1010];
int head[1010];
int pp[1010];
int p[1010];
int cnt;
int n;

void add(int u,int v,int w)
{
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void SPFA(int s)
{
     int i;
    queue<int>q;
    memset(vis,0,sizeof(vis));
    for(i=0; i<=n; i++)
    {
        dis[i]=inf;
    }
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(dis[v]>dis[u]+edge[i].w)
            {
                dis[v]=dis[u]+edge[i].w;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    int T,m,i,j,k;
    int u,v,w;
    int s,e;
    int max1;
    scanf("%d",&T);
    for(k=1;k<=T;k++)
    {
        max1=-inf;
        scanf("%d %d",&n,&m);
        memset(head,-1,sizeof(head));
        memset(pp,0,sizeof(pp));
        memset(p,0,sizeof(p));
        cnt=0;

        while(m--)
        {

            scanf("%d %d %d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        scanf("%d %d",&s,&e);
        SPFA(s);
        for(i=0;i<n;i++)
        {

            pp[i]=dis[i];
        }
        SPFA(e);
        for(j=0;j<n;j++)
        {

            p[j]=dis[j];
        }
        for(i=0;i<n;i++)
        {
            max1=max(max1,pp[i]+p[i]);
        }
        printf("Case #%d: %d\n",k,max1);
    }
    return 0;
}

你猜我猜不猜你猜不猜

题目链接->>>>>>>>点击打开链接

这个题没啥好说的  找到子串就行。别忘记=1的时候的情况

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
    char str;
    int x;
    int cnt,i;
    while(cin>>str>>x)
    {
        cnt=0;
        if(str=='A')
        {
            if(x==1)
                cout<<"Waysd";
            else if(x==2)
                cout<<"Ncwcbc";
            else if(x>2)
            {
                cout<<"Ncwcbc";
                cnt=x-2;
                for(i=1;i<=cnt;i++)
                    cout<<"ncbcwcbc";
            }
            cout<<endl;
        }
        else if(str=='B')
        {
            if(x==1)
                cout<<"Nc";
            else if(x==2)
                cout<<"Ncwcbcncbc";
            else if(x>2)
            {
                cout<<"Ncwcbcncbc";
                cnt=x-2;
                for(i=1;i<=cnt;i++)
                    cout<<"wcbcncbc";
            }
            cout<<endl;
        }
    }
    return 0;
}

你打我啊（简单数字逻辑）

题目链接->>>>>>>>猛戳我
看看汉语就好了，要不然你真会打死他的。这是一道简单的数字逻辑题，也就是有名的毒酒问题。
1000桶酒编号1-1000的二进制表示法所需要的最大位数为10.  （2的10次方为1024）


            桶1-1000的二进制表示为：


                      1                       00 0000 0001


                      2                       00 0000 0010


                      3                       00 0000 0011


                      ...                      ...


                      100                   11 1110 1000


            老鼠编号1-10可理解为二进制表示中位的概念。如鼠1表示第一位为1，鼠10表示第10位为1.（从右至左）


            鼠1-10的二进制表示为：


                       1                      00 0000 0001


                       2                      00 0000 0010


                       3                      00 0000 0100


                       ...                     ...


                       10                    10 0000 0000


 


             鼠1-10分别喝桶1-1000中与鼠编号相同位为1的酒。 如鼠1喝所有奇数桶，因为奇数桶的第一位都为1。 


             最后统计死鼠的编号。 如鼠3,鼠4,鼠5 死亡，表明桶56（00 0001 1100）有毒。 


然后上代码

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int a[50];
int main()
{
    int n,i;
    memset(a,0,sizeof(a));
    for(i=1;i<=32;i++)
    {
        a[i]=pow(2,i);
    }
    while(~scanf("%d",&n))
    {
        for(i=1;i<=32;i++)
        {
            if(n==a[i])
                printf("%d\n",i);
            else if(n>a[i]&&n<a[i+1])
                printf("%d\n",i+1);
        }

    }
    return 0;
}

让领导先走（拓扑排序）

没啥好说的，裸地拓扑排序，记得不要被数据吓到，坑人的

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int map[2001][2001];
int in[2001];
int ans[2001];
int n,m,i,j,k,u,v;
int topo()
{
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(map[i][j])
                in[j]++;
    for(i=1; i<=n; i++)
    {
        k=1;
        while (in[k])
            k++;
        ans[i]=k;
        in[k]=-1;
        for(j=1; j<=n; j++)
            if(map[k][j])
                in[j]--;
    }
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        memset (map,0,sizeof(map));
        memset (in,0,sizeof(in));
        memset (ans,0,sizeof(ans));
        for(i=1; i<=m; i++)
        {
            scanf("%d %d",&u,&v);
            map[u][v]=1;
        }
        topo();
        for(i=1;i<n;i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
    }
    return 0;
}






SDUT ACM月赛（被各种取值范围坑的无力吐槽）


联系
我们