PTA L2一些题目

吴旭华  论坛元老 | 2025-3-6 10:25:24 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1018|帖子 1018|积分 3054

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？立即注册

x
L2-014 列车调度 - 团体程序设计天梯赛-训练集
样例是怎么来的呢？通过题目我们知道每一条轨道的车牌号必须是依次递减的。那么，我们如果让每条轨道尽可能长就能包管轨道数最少------也就是说，我们要尽可能的找最长降序序列。
但是1e5数据量还是太大了，暴力找会超时。
注意到，找最长降序序列的时候，我们是8-4-2-1、5-3、9-6、7，现在这个数能放那个就放哪个，尽可能往前面找，如果都放不了就新开一个
于是，思量二分，找现在所有轨道队尾车牌号大于当前车牌号的那条。可以分析出队尾车牌号是单调的
  1. int n,a[N];
  2. vector <int> vec;
  3. void solve()
  4. {
  5.     cin>>n;
  6.     for(int i=1;i<=n;i++)
  7.     {
  8.         cin>>a[i];
  9.         int p = lower_bound(vec.begin(),vec.end(),a[i])-vec.begin();
  10.         if(p==vec.size()) vec.pb(a[i]);
  11.         else vec[p] = a[i];
  12.     }
  13.     cout<<vec.size()<<endl;
  14. }
复制代码
L2-015 互评结果 - 团体程序设计天梯赛-训练集
模仿水题，大一在学c的时候就做过（）
  1. int n,k,m;
  2. vector  <double> ans;
  3. void solve()
  4. {
  5.     cin>>n>>k>>m;
  6.     for(int i=1;i<=n;i++)
  7.     {
  8.         vector <double> tmp;
  9.         for(int j = 0;j<k;j++)
  10.         {
  11.             double x;
  12.             cin>>x;
  13.             tmp.push_back(x);
  14.         }
  15.         sort(tmp.begin(),tmp.end());
  16.         double sum=0;
  17.         for(int j=1;j<=k-2;j++)
  18.         {
  19.             sum+=tmp[j];
  20.         }
  21.         ans.push_back(sum/(1.0*(k-2)));
  22.     }
  23.     sort(ans.begin(),ans.end());
  24.     for(int i=ans.size()-m;i<ans.size();i++)
  25.     {
  26.         printf("%.3f",ans[i]);
  27.         if(i<ans.size()-1) cout<<" ";
  28.     }
  29. }
复制代码
L2-016 愿天下有情人都是失散多年的兄妹 - 团体程序设计天梯赛-训练集
看似并查集实则不然，是类似于树求深度
给出两个点后，我们先把其中一个的所有祖先全部找到，然后再找另一个的祖先，如果这个后者的其中一个祖先在前者的祖先中被访问到了，且不高出5步的话，那麽就是有血缘关系的
坑点是要记录一下父母的性别（）
  1. int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
  2. void add(int s,int t){
  3.     ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;
  4.     //ed[IDX].w = w;
  5. }
  6. int n;
  7. bool sx[N];
  8. map <int,bool> vis;
  9. bool dfs(int now,int st)
  10. {
  11.     if(st>5)
  12.     {
  13.         return 0;
  14.     }
  15.     bool f=0;
  16.     if(vis[now]==1)
  17.     {
  18.         return 1;
  19.     }
  20.     vis[now]=1;
  21.     for(int i=head[now];i;i=ed[i].ne)
  22.     {
  23.         int t = ed[i].t;
  24.         f=dfs(t,st+1);
  25.         if(f==1) break;
  26.     }
  27.     return f;
  28. }
  29. void solve()
  30. {
  31.     cin>>n;
  32.     for(int i=1;i<=n;i++)
  33.     {
  34.         int a,c,d;
  35.         char b;
  36.         cin>>a>>b>>c>>d;
  37.         sx[a] = (b=='M');
  38.         if(c!=-1) add(a,c),sx[c]=1;//傻逼
  39.         if(d!=-1) add(a,d);
  40.     }
  41.     int q;
  42.     cin>>q;
  44.     while(q--)
  45.     {
  46.         int a,b;
  47.         vis.clear();
  48.         cin>>a>>b;
  49.         if(sx[a]==sx[b])
  50.         {
  51.             cout<<"Never Mind"<<endl;
  52.             continue;
  53.         }
  54.         dfs(a,1);
  55.         if(dfs(b,1))
  56.         {
  57.             cout<<"No"<<endl;
  58.         }
  59.         else
  60.         {
  61.             cout<<"Yes"<<endl;
  62.         }
  63.     }
  64. }
复制代码
L2-017 人以群分 - 团体程序设计天梯赛-训练集
水题，排个序，然后前缀和，左右两部分做差就行
  1. int n,a[N];
  2. void solve()
  3. {
  4.     cin>>n;
  5.     for(int i=1;i<=n;i++)
  6.     {
  7.         cin>>a[i];
  8.     }
  9.     sort(a+1,a+n+1);
  10.     for(int i=1;i<=n;i++)
  11.     {
  12.         a[i] += a[i-1];
  13.     }
  14.     printf("Outgoing #: %d\n",n/2+n%2);
  15.     printf("Introverted #: %d\n",n/2);
  16.     printf("Diff = %d",a[n]-a[n/2]*2);
  17. }
复制代码
L2-019 悄悄关注 - 团体程序设计天梯赛-训练集
模仿水题
  1. int n,m;
  2. typedef pair<string,int>PSI;
  3. map<string ,int> hs;
  4. PSI a[N];
  5. bool cmp(string a,string b)
  6. {
  7.     return a<b;
  8. }
  9. void solve()
  10. {
  11.     cin>>n;
  12.     for(int i=1;i<=n;i++){
  13.         string s;
  14.         cin>>s;
  15.         hs[s]++;
  16.     }
  17.     cin>>m;
  18.     int ave=0;
  19.     for(int i=1;i<=m;i++)
  20.     {
  21.         cin>>a[i].fi>>a[i].se;
  22.         ave+=a[i].se;
  23.     }
  24.     ave/=m;
  25.     vector<string>ans;
  26.     for(int i=1;i<=m;i++)
  27.     {
  28.         if(hs[a[i].fi]==0 && a[i].se>ave)
  29.         {
  30.             ans.pb(a[i].fi);
  31.         }
  32.     }
  33.     sort(ans.begin(),ans.end(),cmp);
  34.     if(ans.size()==0)
  35.     {
  36.         cout<<"Bing Mei You"<<endl;
  37.     }
  38.     else
  39.     {
  40.         for(auto it : ans)
  41.         {
  42.             cout<<it<<endl;
  43.         }
  44.     }
  45. }
复制代码
L2-020 功夫传人 - 团体程序设计天梯赛-训练集
建出一棵树，叶子节点的权值要在削减传下来后乘倍数。注意精度
  1. int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
  2. void add(int s,int t){
  3.     ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;
  4.     //ed[IDX].w = w;
  5. }
  6. int n;
  7. double k1,r;
  8. double fd[N],wg[N];
  9. void dfs(int now,double v)
  10. {
  11.     if(fd[now]>0)
  12.     {
  13.         wg[now] = v*fd[now];
  14.         return ;
  15.     }
  16.     wg[now] = v;
  17.     for(int i=head[now];i;i=ed[i].ne)
  18.     {
  19.         int t = ed[i].t;
  20.         dfs(t,v*(100.0-r)/100.0);
  21.     }
  22. }
  23. void solve()
  24. {
  25.     cin>>n>>k1>>r;
  26.     for(int i=0;i<n;i++)
  27.     {
  28.         int k;
  29.         cin>>k;
  30.         if(k==0)
  31.         {
  32.             cin>>fd[i];
  33.         }
  34.         else
  35.         {
  36.             for(int j=1;j<=k;j++)
  37.             {
  38.                 int x;
  39.                 cin>>x;
  40.                 add(i,x);
  41.             }
  42.         }
  43.     }
  45.     dfs(0,k1);
  46.     double sum=0;
  47.     for(int i=0;i<n;i++)
  48.     {
  49.         if(fd[i]>0)
  50.         {
  51.             sum+=wg[i];
  52.         }
  53.     }
  54.     printf("%.0f",floor(sum));
  55. }
复制代码
L2-021 点赞狂魔 - 团体程序设计天梯赛-训练集
模仿
  1. int n,a;
  2. string name[105];
  3. long long sum[105],ave[105];
  4. int srank[105],averank[105];
  5. int cmp1(long long x,long long y)
  6. {
  7.     if(sum[x]!=sum[y])
  8.     {
  9.         return sum[x]>sum[y];
  10.     }
  11.     else if(ave[x]!=ave[y])
  12.     {
  13.         return ave[x]<ave[y];
  14.     }
  15. }
  16. set <int> s;
  17. int main()
  18. {
  19.     int n,k;
  20.     int i,j;
  21.     long long total;
  22.     cin>>n;
  23.     for(i=1;i<=n;i++)
  24.     {
  25.         cin>>name[i]>>k;
  26.         srank[i]=i;averank[i]=i;
  27.         total=0;
  28.         for(j=0;j<k;j++)
  29.         {
  30.             cin>>a;s.insert(a);
  31.         }
  33.         sum[i]=s.size();
  34.         ave[i]=k;
  35.         s.clear();
  36.     }
  37.     sort(srank+1,srank+n+1,cmp1);
  38.     //sort(averank+1,averank+n+1,cmp1);
  39.     if(n>=3)
  40.     {
  41.         for(i=1;i<=2;i++)
  42.         {
  43.             cout<<name[srank[i]]<<' ';
  44.         }
  45.         cout<<name[srank[3]]<<endl;
  46.     }
  47.     else
  48.     {
  49.         for(i=1;i<=3;i++)
  50.         {
  51.             if(i<=n)cout<<name[srank[i]]<<' ';
  52.             else
  53.             {
  54.                 if(i!=3)
  55.                 cout<<'-'<<' ';
  56.             }
  57.             if(i==3)
  58.             {
  59.                 cout<<'-'<<endl;
  60.             }
  61.         }
  62.     }
  63. }
复制代码
L2-022 重排链表 - 团体程序设计天梯赛-训练集
很故意思的一道题，有了前次的教训我们应在所有结点都输入完后再处理惩罚前驱。
使用一个数组记录每个地点在当前链表中的位置，每次插入只需要从双方往中心交换即可，可以证明每次插入不会影响其他节点的相对位置
  1. int n,k1;
  2. int kv[N],ne[N],pre[N];
  3. int p[N];
  4. int cnt ;
  5. void dfs(int now,int idx)//处理前驱
  6. {
  7.     if(now == -1) return;
  8.     cnt = max(cnt,idx);
  9.     pre[ne[now]] = now;
  10.     p[idx] = now;
  11.     dfs(ne[now],idx+1);
  12. }
  13. void ist(int a,int b)//b插到a前面
  14. {
  15.     int ka = p[a];
  16.     int kb = p[b];
  17.     if(pre[ka]==-1)
  18.     {
  19.         k1 = kb;
  20.     }
  21.     ne[pre[kb]] = ne[kb];
  22.     ne[pre[ka]] = kb;
  23.     pre[ka] = kb;
  24.     pre[kb] = pre[ka];
  25.     ne[kb] = ka;
  26. }
  27. void dfs1(int now)输出新链表
  28. {
  29.     if(now == -1)
  30.     {
  31.         return ;
  32.     }
  33.     //cout<<now<<' '<<kv[now]<<' '<<ne[now]<<endl;
  34.     printf("%05d %d ",now,kv[now]);
  35.     if(ne[now]!=-1)
  36.     {
  37.         printf("%05d\n",ne[now]);
  38.     }
  39.     else
  40.     {
  41.         printf("-1\n");
  42.     }
  43.     dfs1(ne[now]);
  44. }
  45. void solve()
  46. {
  47.     cin>>k1>>n;
  48.     for(int i=1;i<=n;i++)
  49.     {
  50.         int a,b,c;
  51.         cin>>a>>b>>c;
  52.         kv[a] = b;
  53.         ne[a] = c;
  54.     }
  55.     pre[k1] = -1;
  56.     dfs(k1,1);
  57.     int l=1,r=cnt;
  58.     //cout<<cnt<<endl;
  59.     while(l<r)
  60.     {
  61.         //cout<<l<<' '<<r<<endl;
  62.         //cout<<p[l]<<' '<<p[r]<<endl;
  63.         ist(l,r);
  64.         //dfs(k1,1);
  65.         //dfs1(k1);
  66.         l++,r--;
  67.         //cout<<endl;
  68.     }
  69.     dfs1(k1);
  70. }
复制代码
L2-023 图着色问题 - 团体程序设计天梯赛-训练集
使用链式前向星，现实上建单向图就可以，无向图疑似会tle（）。
对于每个方案，遍历每一个点的相邻点，只要有一组有相同颜色就不可
  1. int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
  2. void add(int s,int t){
  3.     ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;
  4.     //ed[IDX].w = w;
  5. }
  6. int v,e,k;
  7. int c[N];
  8. void solve()
  9. {
  10.     cin>>v>>e>>k;
  11.     for(int i=1;i<=e;i++)
  12.     {
  13.         int a,b;
  14.         cin>>a>>b;
  15.         add(a,b);
  16.     }
  17.     int q;cin>>q;
  18.     set<int>st;
  19.     while(q--)
  20.     {
  21.         st.clear();
  22.         for(int i=1;i<=v;i++) cin>>c[i],st.emplace(c[i]);
  23.         if(st.size()!=k)
  24.         {
  25.             cout<<"No"<<endl;
  26.             continue;
  27.         }
  28.         bool f=1;
  29.         for(int i=1;i<=v;i++)
  30.         {
  31.             for(int j=head[i];j;j=ed[j].ne)
  32.             {
  33.                 int t=ed[j].t;
  34.                 if(c[i] == c[t])
  35.                 {
  36.                     f=0;
  37.                     break;
  38.                 }
  39.             }
  40.             if(f==0) break;
  41.         }
  42.         cout<<(f?"Yes":"No")<<endl;
  43.     }
  44. }
复制代码
L2-024 部落 - 团体程序设计天梯赛-训练集
？并查集板子
统计人数用个set存就行。每一个圈子的每一个人都只需要与第一个人归并即可
  1. int FA[N];
  2. int _fi(int x){return (FA[x] == x) ? x : FA[x] = _fi(FA[x]);}
  3. void uni(int x, int y){int xx = _fi(x), yy = _fi(y);if (xx != yy) FA[xx] = yy;}
  4. int n;
  5. set<int>st;
  6. int a[N];
  7. void solve()
  8. {
  9.     for(int i=1;i<=10000;i++)
  10.     {
  11.         FA[i] = i;
  12.     }
  13.     cin>>n;
  14.     for(int i=1;i<=n;i++)
  15.     {
  16.         int k;
  17.         cin>>k;
  18.         for(int j=1;j<=k;j++)
  19.         {
  20.             cin>>a[j];
  21.             uni(a[j],a[1]);
  22.             st.emplace(a[j]);
  23.         }
  24.     }
  25.     int q,cnt=0;
  26.     for(int i=1;i<=st.size();i++)
  27.     {
  28.         if(_fi(i) == i )
  29.         {
  30.             cnt++;
  31.         }
  32.     }
  33.     cout<<st.size()<<' '<<cnt<<endl;
  34.     cin>>q;
  35.     while(q--)
  36.     {
  37.         int a,b;
  38.         cin>>a>>b;
  39.         if(_fi(a) == _fi(b))
  40.         {
  41.             cout<<"Y"<<endl;
  42.         }
  43.         else
  44.         {
  45.             cout<<"N"<<endl;
  46.         }
  47.     }
  48. }
复制代码
L2-025 分而治之 - 团体程序设计天梯赛-训练集
跟上面图着色问题差不多，这里只需要判定每个还存在的点有没有相邻点即可
  1. int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
  2. void add(int s,int t){
  3.     ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;
  4.     //ed[IDX].w = w;
  5. }
  6. int n,m,k;
  7. map <int ,bool> hs;
  8. void solve()
  9. {
  10.     cin>>n>>m;
  11.     for(int i=1;i<=m;i++)
  12.     {
  13.         int a,b;
  14.         cin>>a>>b;
  15.         add(a,b);
  16.         add(b,a);
  17.     }
  18.     cin>>k;
  19.     while(k--)
  20.     {
  21.         hs.clear();
  22.         int u;
  23.         cin>>u;
  24.         for(int i=1;i<=u;i++)
  25.         {
  26.             int x;
  27.             cin>>x;
  28.             hs[x] = 1;
  29.         }
  30.         bool f = 1;
  31.         for(int i=1;i<=n;i++)
  32.         {
  33.             if(!hs[i])
  34.             {
  35.                 for(int j=head[i];j;j=ed[j].ne)
  36.                 {
  37.                     int t = ed[j].t;
  38.                     if(!hs[t])
  39.                     {
  40.                         f=0;
  41.                         break;
  42.                     }
  43.                 }
  44.                 if(!f) break;
  45.             }
  46.         }
  47.         cout<<(f?"YES":"NO")<<endl;
  48.     }
  49. }
复制代码
L2-026 小字辈 - 团体程序设计天梯赛-训练集
建树求高度
  1. void add(int s,int t)
  2. {
  3.     ed[++idx].ne = head[s];
  4.     ed[idx].t = t;
  5.     head[s] = idx;
  6. }
  7. int n;
  8. int a[N];
  9. int deep=0,dp[N],root;
  10. void dfs(int now,int d)
  11. {
  12.     dp[now] = d;
  13.     deep = max(deep,d);
  14.     for(int i=head[now];i;i=ed[i].ne)
  15.     {
  16.         int t = ed[i].t;
  17.         dfs(t,d+1);
  18.     }
  19. }
  20. void solve()
  21. {
  22.     cin>>n;
  23.     for(int i=1;i<=n;i++)
  24.     {
  25.         cin>>a[i];
  26.         if(a[i]==-1)
  27.         {
  28.             root = i;
  29.         }
  30.         else
  31.             add(a[i],i);
  32.     }
  33.     dfs(root,1);
  34.     cout<<deep<<endl;
  35.     vector <int> ans;
  36.     for(int i=1;i<=n;i++)
  37.     {
  38.         if(dp[i] == deep)
  39.         {
  40.             ans.push_back(i);
  41.         }
  42.     }
  43.     for(int i=0;i<ans.size();i++)
  44.     {
  45.         cout<<ans[i];
  46.         if(i<ans.size()-1) cout<<' ';
  47.     }
  48. }
复制代码
L2-027 名人堂与代金券 - 团体程序设计天梯赛-训练集
模仿，末了输出的时候注意一下名次就行
  1. int n,g,k;
  2. typedef pair<string,int> PSI;
  3. vector <PSI> vec,ans;
  4. int sum = 0;
  5. bool cmp(PSI x,PSI y)
  6. {
  7.     if(x.se==y.se)
  8.     {
  9.         return x.fi<y.fi;
  10.     }
  11.     else
  12.     {
  13.         return x.se>y.se;
  14.     }
  15. }
  16. void solve()
  17. {
  18.     cin>>n>>g>>k;
  19.     for(int i=1;i<=n;i++)
  20.     {
  21.         string s;
  22.         int sc;
  23.         cin>>s>>sc;
  24.         vec.pb({s,sc});
  25.         if(sc>=60 && sc<g) sum+=20;
  26.         else if(sc>=g) sum+=50;
  27.     }
  28.     cout<<sum<<endl;
  29.     sort(vec.begin(),vec.end(),cmp);
  30.     int p=1,cnt=1;
  31.     for(int i=0;i<vec.size();i++)
  32.     {
  33.         cout<<p<<' '<<vec[i].fi<<' '<<vec[i].se<<endl;
  34.         cnt++;
  35.         if(i<vec.size()-1&&vec[i+1].se<vec[i].se) p=cnt;
  36.         if(p>k) break;
  37.     }
  38. }
复制代码
L2-028 秀恩爱分得快 - 团体程序设计天梯赛-训练集
很牛逼的模仿题，光是数据处理惩罚就很头疼。用毗邻表（？）存一下每两个点之间的亲密度
后面就按题意处理惩罚即可
  1. int n,m,a,b;
  2. double mp[1005][1005];
  3. bool sx[N];
  4. int kk[N];
  5. typedef pair<int,double> PID;
  6. vector <PID> va,vb;
  7. bool cmp(PID x,PID y)
  8. {
  9.     if(abs(x.se-y.se)<1e-9)
  10.     {
  11.         return x.fi<x.fi;
  12.     }
  13.     else
  14.     {
  15.         return x.se>y.se;
  16.     }
  17. }
  18. void solve()
  19. {
  20.     cin>>n>>m;
  21.     for(int i=1;i<=m;i++)
  22.     {
  23.         int k;
  24.         cin>>k;
  25.         double add = 1.0/k;
  26.         for(int j=1;j<=k;j++)
  27.         {
  28.             string s;
  29.             cin>>s;
  30.             int id = abs(stoi(s));
  31.             kk[j] = id;
  32.             if(s[0] != '-')
  33.             {
  34.                 sx[id] = 1;
  35.             }
  36.         }
  37.         for(int j=1;j<=k;j++)
  38.         {
  39.             for(int jj=j+1;jj<=k;jj++)
  40.             {
  41.                 mp[kk[j]][kk[jj]] += add;
  42.                 mp[kk[jj]][kk[j]] += add;
  43.             }
  44.         }
  45.     }
  46.     string sa,sb;
  47.     cin>>sa>>sb;
  48.     a = abs(stoi(sa));
  49.     b = abs(stoi(sb));
  50.     sx[a] = (sa[0]!='-');
  51.     sx[b] = (sb[0]!='-');
  52.     double now = mp[a][b];
  53.     double topa=0,topb=0;
  54.     for(int i=0;i<n;i++)
  55.     {
  56.         if(sx[a]!=sx[i])
  57.         {
  58.             va.pb({i,mp[a][i]});
  59.             topa = max(topa,mp[a][i]);
  60.         }
  61.         if(sx[b]!=sx[i])
  62.         {
  63.             vb.pb({i,mp[b][i]});
  64.             topb = max(topb,mp[b][i]);
  65.         }
  66.     }
  67.     if(topa == topb && topa == now)
  68.     {
  69.         if(sx[a]==0)
  70.         cout<<'-'<<a<<' '<<b<<endl;
  71.         else
  72.         {
  73.             cout<<a<<' '<<"-"<<b<<endl;
  74.         }
  75.         return ;
  76.     }
  77.     for(int i=0;i<n;i++)
  78.     {
  79.         if(mp[a][i]==topa && sx[i]!=sx[a])
  80.         {
  81.             cout<<(sx[a]?"":"-")<<a<<' '<<(sx[i]?"":"-")<<i<<endl;
  82.         }
  83.     }
  84.     for(int i=0;i<n;i++)
  85.     {
  86.         if(mp[b][i]==topb && sx[i]!=sx[b])
  87.         {
  88.             cout<<(sx[b]?"":"-")<<b<<' '<<(sx[i]?"":"-")<<i<<endl;
  89.         }
  90.     }
  91. }
复制代码
L2-029 特立独行的幸福 - 团体程序设计天梯赛-训练集
写懵了，这里代码看个乐子就行，纯翻译题面。数据量只有1000，直接暴力
  1. int a,b;
  2. map<int,int>hs,pl;
  3. bool prime(int x)
  4. {
  5.     if(x==1) return 0;
  6.     for(int i=2;i*i<=x;i++)
  7.     {
  8.         if(x%i==0)
  9.         {
  10.             return 0;
  11.         }
  12.     }
  13.     return 1;
  14. }
  15. int fun(int x)
  16. {
  17.     int res = 0,y=x;
  18.     while(y)
  19.     {
  20.         int tmp = y%10;
  21.         res+=tmp*tmp;
  22.         y/=10;
  23.     }
  24.     return res;
  25. }
  26. void dfs(int x)
  27. {
  28.     //cout<<x<<endl;
  29.     int res = x,cnt=1;
  30.     int y = x;
  31.     int f = 1;
  32.     map <int,bool> hss;
  33.     hss[x] = 1;
  34.     while(res!=1)
  35.     {
  36.         //cout<<res<<endl;
  37.         int tmp = fun(res);
  38.         cnt++;
  39.         res = tmp;
  40.         if(hss[res] == 1)
  41.         {
  42.             f=0;
  43.             break;
  44.         }
  45.         hss[res] = 1;
  46.     }
  47.     if(res==1)
  48.     {
  49.         pl[x]=--cnt;
  50.         hs[x]=0x3f3f3f3f;
  51.         res = x;
  52.         while(res!=1)
  53.         {
  54.             int tmp = fun(res);
  55.             res = tmp;
  56.             hs[res] = 1;
  57.         }
  58.         return ;
  59.     }
  60.     if(f==0)
  61.     {
  62.         hs[x] = -1;
  63.         res = fun(x);
  64.         while(hs[res] != -1)
  65.         {
  66.             hs[res]=-1;
  67.             int tmp = fun(res);
  68.             res = tmp;
  69.         }
  70.     }
  71. }
  72. void solve()
  73. {
  74.     cin>>a>>b;
  75.     int f = 0;
  76.     for(int i=a;i<=b;i++)
  77.     {
  78.         //cout<<prime(i)<<endl;
  79.         if(hs[i] == -1) continue;
  80.         if(hs[i] == 0x3f3f3f3f)
  81.         {
  82.             //cout<<i<<' '<<(pl[i]*(prime(i)?2:1))<<endl;
  83.             //f=1;
  84.         }
  85.         else if(hs[i]==0)
  86.             dfs(i);
  87.     }
  88.     for(int i=a;i<=b;i++)
  89.     {
  90.         if(hs[i] == -1) continue;
  91.         if(hs[i] == 0x3f3f3f3f)
  92.         {
  93.             cout<<i<<' '<<(pl[i]*(prime(i)?2:1))<<endl;
  94.             f=1;
  95.         }
  96.     }
  97.     if(!f) cout<<"SAD"<<endl;
  98. }
复制代码
L2-031 深入虎穴 - 团体程序设计天梯赛-训练集
建树求高度
  1. int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
  2. void add(int s,int t){
  3.     ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;
  4.     //ed[IDX].w = w;
  5. }
  6. int n,rd[N];
  7. int ans,ansd=0;
  8. void dfs(int now,int dpp)
  9. {
  10.     if(dpp>ansd)
  11.     {
  12.         ansd=dpp;
  13.         ans = now;
  14.     }
  15.     for(int i=head[now];i;i=ed[i].ne)
  16.     {
  17.         dfs(ed[i].t,dpp+1);
  18.     }
  19. }
  20. void solve()
  21. {
  22.     cin>>n;
  23.     for(int i=1;i<=n;i++)
  24.     {
  25.         int k;
  26.         cin>>k;
  27.         for(int j=1;j<=k;j++)
  28.         {
  29.             int x;
  30.             cin>>x;
  31.             add(i,x);
  32.             rd[x]++;
  33.         }
  34.     }
  35.     int rt;
  36.     for(int i=1;i<=n;i++)
  37.     {
  38.         if(rd[i]==0)
  39.         {
  40.             rt=i;
  41.             break;
  42.         }
  43.     }
  44.     dfs(rt,1);
  45.     cout<<ans<<endl;
  46. }
复制代码
L2-032 彩虹瓶 - 团体程序设计天梯赛-训练集
用stack模仿就行，栈满了也不要停止输入（）。不要忘记如果栈还有东西就只管往外拿
  1. int n,m,k;
  2. stack<int> st;
  3. int now;
  4. void solve()
  5. {
  6.     cin>>n>>m>>k;
  7.     while(k--)
  8.     {
  9.         while(!st.empty())
  10.         {
  11.             st.pop();
  12.         }
  13.         bool f = 0;
  14.         now = 1;
  15.         for(int i=1;i<=n;i++)
  16.         {
  17.             int x;
  18.             cin>>x;
  19.             //cout<<now<<endl;
  20.             if(x == now)
  21.             {
  22.                 now++;
  23.                 while(!st.empty()&&st.top()==now)
  24.                 {
  25.                     st.pop();
  26.                     now++;
  27.                 }
  28.             }
  29.             else
  30.             {
  31.                 if(st.size()==m)
  32.                 {
  33.                     f=0;
  34.                     continue;
  35.                 }
  36.                 st.push(x);
  37.             }
  38.         }
  39.         while(!st.empty()&&st.top()==now)
  40.         {
  41.             st.pop();
  42.             now++;
  43.         }
  44.         if(now == n+1) f=1;
  45.         cout<<((f==1)?"YES":"NO")<<endl;
  46.     }
  47. }
复制代码
L2-033 简朴计算器 - 团体程序设计天梯赛-训练集
栈入门题
  1. stack <int> s1;
  2. stack <char> s2;
  3. int n;
  4. void solve()
  5. {
  6.     cin>>n;
  7.     for(int i=1;i<=n;i++)
  8.     {
  9.         int x;
  10.         cin>>x;
  11.         s1.push(x);
  12.     }
  13.     for(int i=1;i<n;i++)
  14.     {
  15.         char c;
  16.         cin>>c;
  17.         s2.push(c);
  18.     }
  19.     while(s2.size())
  20.     {
  21.         int na,nb;
  22.         na = s1.top();
  23.         s1.pop();
  24.         nb = s1.top();
  25.         s1.pop();
  26.         char op = s2.top();
  27.         s2.pop();
  28.         if(op=='+')
  29.         {
  30.             s1.push(na+nb);
  31.         }
  32.         else if(op =='-')
  33.         {
  34.             s1.push(nb-na);
  35.         }
  36.         else if(op == '*')
  37.         {
  38.             s1.push(na*nb);
  39.         }
  40.         else
  41.         {
  42.             if(na == 0)
  43.             {
  44.                 cout<<"ERROR: "<<nb<<'/'<<na<<endl;
  45.                 return ;
  46.             }
  47.             else
  48.             {
  49.                 s1.push(nb/na);
  50.             }
  51.         }
  52.     }
  53.     cout<<s1.top()<<endl;
  54. }
复制代码
L2-035 完全二叉树的层序遍历 - 团体程序设计天梯赛-训练集
建树之后，使用bfs条理遍历就行了
  1. int n,hx[N];
  2. struct TREE
  3. {
  4.     int v,l,r;
  5. }tr[N];
  6. int hdx;
  7. int build(int idx)
  8. {
  9.     if(idx>n)
  10.         return 0;
  11.     tr[idx].v = hx[hdx];
  12.     hdx--;
  13.     tr[idx].r = build(idx*2+1);
  14.     tr[idx].l = build(idx*2);
  15.     return idx;
  16. }
  17. vector <int> ans;
  18. void bfs(int rt)
  19. {
  20.     queue <int> q;
  21.     q.push(rt);
  22.     while(!q.empty())
  23.     {
  24.         int now = q.front();
  25.         q.pop();
  26.         ans.pb(tr[now].v);
  27.         if(tr[now].l!=0)
  28.         {
  29.             q.push(tr[now].l);
  30.         }
  31.         if(tr[now].r!=0)
  32.         {
  33.             q.push(tr[now].r);
  34.         }
  35.     }
  36. }
  37. void solve()
  38. {
  39.     cin>>n;
  40.     for(int i=1;i<=n;i++)
  41.     {
  42.         cin>>hx[i];
  43.     }
  44.     hdx=n;
  45.     int rt = build(1);
  46.     bfs(rt);
  47.     for(int i=0;i<ans.size();i++)
  48.     {
  49.         cout<<ans[i]<<(i<ans.size()-1?" ":"\n");
  50.     }
  51. }
复制代码


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

吴旭华

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表