当前位置：首页 > news >正文

周赛6（28）

news 来源：原创 2024/4/28 3:59:49

天梯座位模拟

一开始用最原始最复杂的方法模拟了一个小时才做完：

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include <bits/stdc++.h>
#include<algorithm>

using namespace std;


int main()
{

  int a[200][20][20]={0};
  int n;
  cin>>n;
  int team[200];
  for(int i=0;i<n;i++)
      cin>>team[i];
int n3=1;

      //printf("aaa\n");
            for(int i=0;i<n;i++)
 {
     for(int j=0;j<team[i];j++)
     {
         for(int k=0;k<10;k++)
            a[i][j][k]=1;
     }

 }


 int max1=*max_element(team,team+n);
           //cout<<max1<<endl;
 int c=0;
 
 for(int i=0;i<max1;i++)
 {
     for(int j=0;j<10;j++)
     {
         for(int k=0;k<n;k++)
            if(a[k][i][j]==1) a[k][i][j]=++c;
     }
 }


int p=max_element(team,team+n)-team; //cout<<p<<endl;
  team[p]=0;
  int max2=*max_element(team,team+n-1);
  team[p]=max1;
   int x=max1-max2;
//cout<<x<<endl;
int n1;
if(x>1) n1=0;
else  n1=1;


for(int i=x;i>0;i--)
{
    for(int k=0;k<10;k++)
    {
a[p][max1-i][k]+=n1;n1++;}
}
 int case1=1;


   for(int i=0;i<n;i++)
 {   cout<<'#'<<case1++<<endl;
     for(int j=0;j<team[i];j++)
     {     int first=1;
         for(int k=0;k<10;k++)
            if(first){cout<<a[i][j][k];first=0;}else {cout<<' '<<a[i][j][k];}
            if(j!=team[i]-1||i!=n-1)cout<<endl;
     }

     }
return 0;
}

View Code

现在十五分钟

#include<cstdio>
#include<map>
#include<set>
#include<vector>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;

struct school
{
   vector<int>a;
   int num;
    int f;
} s[105];


int main()
{

     int sum=0;
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
       int x;cin>>x;
       s[i].num+=10*x;sum+=10*x;
        s[i].f=1;
    }
    int d=1;int len=1;
    while(sum--)
    {

        for(int i=1;i<=n;i++)
        {
            if(s[i].a.size()!=s[i].num)
            {
                s[i].a.push_back(d);if(len==n)d+=2;else d++;
            }

            if(s[i].a.size()==s[i].num&&s[i].f==1){len++;s[i].f=0;}

        }


    }

    int case1=1;
    for(int i=1;i<=n;i++)
    {
        printf("#%d\n",case1++);
           int first=1;
        for(int j=0;j<s[i].a.size();j++)
        {

            if(first){first=0;printf("%d",s[i].a[j]);}
            else printf(" %d",s[i].a[j]);
            if((j+1)%10==0){first=1;cout<<endl;}



        }



    }



    return 0;
}

View Code

小字辈

用的是数组模拟

只是骗了一点分数然后超时了应该用向量的这样可以说不定就过了

#include <bits/stdc++.h>


using namespace std;



int main()
{

int n;
cin>>n;
int b[100000];
int a[100][100];int zu;
for(int i=1;i<=n;i++)
{
    cin>>b[i];if(b[i]==-1) zu=i;

}

int left=n-1;


a[1][1]=zu;int n1=1;int c;
int i;
for(i=1;left>0;i++)
{    //cout<<n1<<endl<<endl;
   // for(int k=1;k<=n1;k++)
    // printf("%d ",a[i][k]);
    //cout<<endl;c=0;
    c=0;
     for(int k=1;k<=n1;k++)
     {


     for(int j=1;j<=n;j++)
        {

            if(b[j]==a[i][k]){a[i+1][++c]=j;left--;if(left==0)break;}

        }
     }
      n1=c;

}


int first=1;
printf("%d\n",i);
for(int j=1;j<=n1;j++)
   {
       if(first) {first=0;printf("%d",a[i][j]);}
       else printf(" %d",a[i][j]);

   }






 return 0;
}

View Code

DFS 注意 vector<int>level(n+1) 是先开下标到n+1 不然后面直接调用 level[x]会越界因为没有push_back进来开一个数组同样可行要是数组开到全局每次得清零要是开到里面会造成不必要的内存浪费还是vector好

#include<iostream>
#include<vector>
using namespace std;
struct TNode
{
    int father;
    vector<int>child;
}List[100000];
int maxb = 1;
void dfs(vector<int>&l, int b, int s)
{
    if (!(List[s].child.size()))
        return;
    for (int i = 0; i < List[s].child.size(); i++)
    {
        l[List[s].child[i]] = b;
        if (b > maxb)
            maxb = b;
        dfs(l, b + 1, List[s].child[i]);
    }
    return;
}
int main()
{
    int n;
    cin >> n;
    int root;
    vector<int>level(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> List[i].father;
        if (List[i].father == -1)//万恶之源！！！！！！！！！
        {
            root = i;
            continue;
        }
        List[List[i].father].child.push_back(i);
    }
    level[root] = 1;
    dfs(level, 2, root);
    int flag = 1;
    cout << maxb << endl;
    for (int i = 1; i <= n; i++)
    {
        if (level[i] == maxb)
        {
            if (flag)
            {
                cout << i;
                flag = 0;
            }
            else
                cout << " " << i;
        }
    }
    return 0;
}

View Code

BFS(还不会) BFS的内存消耗比DFS小很多

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
struct TNode
{
    int father;
    vector<int>child;
}List[100000];
int maxb = 1;
void cxbl(vector<int>&l, int s)
{
    deque<int>dl;
    dl.push_back(s);
    while (dl.size())
    {
        int a = dl.front();
        dl.pop_front();
        for (int i = 0; i < List[a].child.size(); i++)
        {
            l[List[a].child[i]] = l[a] + 1;
            if (l[a] + 1 > maxb)
                maxb = l[a] + 1;
            dl.push_back(List[a].child[i]);
        }
    }
    return;
}
int main()
{
    int n;
    cin >> n;
    int root;
    vector<int>level(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> List[i].father;
        if (List[i].father == -1)//万恶之源！！！！！！！！！
        {
            root = i;
            continue;
        }
        List[List[i].father].child.push_back(i);
    }
    level[root] = 1;
    cxbl(level, root);
    int flag = 1;
    cout << maxb << endl;
    for (int i = 1; i <= n; i++)
    {
        if (level[i] == maxb)
        {
            if (flag)
            {
                cout << i;
                flag = 0;
            }
            else
                cout << " " << i;
        }
    }
    return 0;
}