PTA L2一些题目

L2-014 列车调度 - 团体程序设计天梯赛-练习集

样例是怎么来的呢？通过题目我们知道每一条轨道的车牌号必须是依次递减的。那么，我们如果让每条轨道尽可能长就能保证轨道数最少------也就是说，我们要尽可能的找最长降序序列。

但是1e5数据量还是太大了，暴力找会超时。

注意到，找最长降序序列的时候，我们是8-4-2-1、5-3、9-6、7，现在这个数能放那个就放哪个，尽可能往前面找，如果都放不了就新开一个

于是，考虑二分，找现在所有轨道队尾车牌号大于当前车牌号的那条。可以分析出队尾车牌号是单调的

int n,a[N];
vector <int> vec;
void solve()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];int p = lower_bound(vec.begin(),vec.end(),a[i])-vec.begin();if(p==vec.size()) vec.pb(a[i]);else vec[p] = a[i];}cout<<vec.size()<<endl;
}

L2-015 互评成绩 - 团体程序设计天梯赛-练习集

模拟水题，大一在学c的时候就做过（）

int n,k,m;
vector  <double> ans;
void solve()
{cin>>n>>k>>m;for(int i=1;i<=n;i++){vector <double> tmp;for(int j = 0;j<k;j++){double x;cin>>x;tmp.push_back(x);}sort(tmp.begin(),tmp.end());double sum=0;for(int j=1;j<=k-2;j++){sum+=tmp[j];}ans.push_back(sum/(1.0*(k-2)));}sort(ans.begin(),ans.end());for(int i=ans.size()-m;i<ans.size();i++){printf("%.3f",ans[i]);if(i<ans.size()-1) cout<<" ";}
}

L2-016 愿天下有情人都是失散多年的兄妹 - 团体程序设计天梯赛-练习集

看似并查集实则不然，是类似于树求深度

给出两个点后，我们先把其中一个的所有祖先全部找到，然后再找另一个的祖先，如果这个后者的其中一个祖先在前者的祖先中被访问到了，且不超过5步的话，那麽就是有血缘关系的

坑点是要记录一下父母的性别（）

int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
void add(int s,int t){ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;//ed[IDX].w = w;
}
int n;
bool sx[N];
map <int,bool> vis;
bool dfs(int now,int st)
{if(st>5){return 0;}bool f=0;if(vis[now]==1){return 1;}vis[now]=1;for(int i=head[now];i;i=ed[i].ne){int t = ed[i].t;f=dfs(t,st+1);if(f==1) break;}return f;
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){int a,c,d;char b;cin>>a>>b>>c>>d;sx[a] = (b=='M');if(c!=-1) add(a,c),sx[c]=1;//傻逼if(d!=-1) add(a,d);}int q;cin>>q;while(q--){int a,b;vis.clear();cin>>a>>b;if(sx[a]==sx[b]){cout<<"Never Mind"<<endl;continue;}dfs(a,1);if(dfs(b,1)){cout<<"No"<<endl;}else{cout<<"Yes"<<endl;}}
}

L2-017 人以群分 - 团体程序设计天梯赛-练习集

水题，排个序，然后前缀和，左右两部分做差就行

int n,a[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);for(int i=1;i<=n;i++){a[i] += a[i-1];}printf("Outgoing #: %d\n",n/2+n%2);printf("Introverted #: %d\n",n/2);printf("Diff = %d",a[n]-a[n/2]*2);
}

L2-019 悄悄关注 - 团体程序设计天梯赛-练习集

模拟水题

int n,m;
typedef pair<string,int>PSI;
map<string ,int> hs;
PSI a[N];
bool cmp(string a,string b)
{return a<b;
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){string s;cin>>s;hs[s]++;}cin>>m;int ave=0;for(int i=1;i<=m;i++){cin>>a[i].fi>>a[i].se;ave+=a[i].se;}ave/=m;vector<string>ans;for(int i=1;i<=m;i++){if(hs[a[i].fi]==0 && a[i].se>ave){ans.pb(a[i].fi);}}sort(ans.begin(),ans.end(),cmp);if(ans.size()==0){cout<<"Bing Mei You"<<endl;}else{for(auto it : ans){cout<<it<<endl;}}
}

L2-020 功夫传人 - 团体程序设计天梯赛-练习集

建出一棵树，叶子节点的权值要在削减传下来后乘倍数。注意精度

int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
void add(int s,int t){ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;//ed[IDX].w = w;
}
int n;
double k1,r;
double fd[N],wg[N];
void dfs(int now,double v)
{if(fd[now]>0){wg[now] = v*fd[now];return ;}wg[now] = v;for(int i=head[now];i;i=ed[i].ne){int t = ed[i].t;dfs(t,v*(100.0-r)/100.0);}
}
void solve()
{cin>>n>>k1>>r;for(int i=0;i<n;i++){int k;cin>>k;if(k==0){cin>>fd[i];}else{for(int j=1;j<=k;j++){int x;cin>>x;add(i,x);}}}dfs(0,k1);double sum=0;for(int i=0;i<n;i++){if(fd[i]>0){sum+=wg[i];}}printf("%.0f",floor(sum));
}

L2-021 点赞狂魔 - 团体程序设计天梯赛-练习集

模拟

int n,a;
string name[105];
long long sum[105],ave[105];
int srank[105],averank[105];
int cmp1(long long x,long long y)
{if(sum[x]!=sum[y]){return sum[x]>sum[y];}else if(ave[x]!=ave[y]){return ave[x]<ave[y];}
}
set <int> s;
int main()
{int n,k;int i,j;long long total;cin>>n;for(i=1;i<=n;i++){cin>>name[i]>>k;srank[i]=i;averank[i]=i;total=0;for(j=0;j<k;j++){cin>>a;s.insert(a);}sum[i]=s.size();ave[i]=k;s.clear();}sort(srank+1,srank+n+1,cmp1);//sort(averank+1,averank+n+1,cmp1);if(n>=3){for(i=1;i<=2;i++){cout<<name[srank[i]]<<' ';}cout<<name[srank[3]]<<endl;}else{for(i=1;i<=3;i++){if(i<=n)cout<<name[srank[i]]<<' ';else{if(i!=3)cout<<'-'<<' ';}if(i==3){cout<<'-'<<endl;}}}
}

L2-022 重排链表 - 团体程序设计天梯赛-练习集

很有意思的一道题，有了上次的教训我们应在所有结点都输入完后再处理前驱。

使用一个数组记录每个地址在当前链表中的位置，每次插入只需要从两边往中间交换即可，可以证明每次插入不会影响其他节点的相对位置

int n,k1;
int kv[N],ne[N],pre[N];
int p[N];
int cnt ;
void dfs(int now,int idx)//处理前驱
{if(now == -1) return;cnt = max(cnt,idx);pre[ne[now]] = now;p[idx] = now;dfs(ne[now],idx+1);
}
void ist(int a,int b)//b插到a前面
{int ka = p[a];int kb = p[b];if(pre[ka]==-1){k1 = kb;}ne[pre[kb]] = ne[kb];ne[pre[ka]] = kb;pre[ka] = kb;pre[kb] = pre[ka];ne[kb] = ka;
}
void dfs1(int now)输出新链表
{if(now == -1){return ;}//cout<<now<<' '<<kv[now]<<' '<<ne[now]<<endl;printf("%05d %d ",now,kv[now]);if(ne[now]!=-1){printf("%05d\n",ne[now]);}else{printf("-1\n");}dfs1(ne[now]);
}
void solve()
{cin>>k1>>n;for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;kv[a] = b;ne[a] = c;}pre[k1] = -1;dfs(k1,1);int l=1,r=cnt;//cout<<cnt<<endl;while(l<r){//cout<<l<<' '<<r<<endl;//cout<<p[l]<<' '<<p[r]<<endl;ist(l,r);//dfs(k1,1);//dfs1(k1);l++,r--;//cout<<endl;}dfs1(k1);
}

L2-023 图着色问题 - 团体程序设计天梯赛-练习集

使用链式前向星，实际上建单向图就可以，无向图疑似会tle（）。

对于每个方案，遍历每一个点的相邻点，只要有一组有相同颜色就不行

int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
void add(int s,int t){ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;//ed[IDX].w = w;
}
int v,e,k;
int c[N];
void solve()
{cin>>v>>e>>k;for(int i=1;i<=e;i++){int a,b;cin>>a>>b;add(a,b);}int q;cin>>q;set<int>st;while(q--){st.clear();for(int i=1;i<=v;i++) cin>>c[i],st.emplace(c[i]);if(st.size()!=k){cout<<"No"<<endl;continue;}bool f=1;for(int i=1;i<=v;i++){for(int j=head[i];j;j=ed[j].ne){int t=ed[j].t;if(c[i] == c[t]){f=0;break;}}if(f==0) break;}cout<<(f?"Yes":"No")<<endl;}
}

L2-024 部落 - 团体程序设计天梯赛-练习集

？并查集板子

统计人数用个set存就行。每一个圈子的每一个人都只需要与第一个人合并即可

int FA[N];
int _fi(int x){return (FA[x] == x) ? x : FA[x] = _fi(FA[x]);}
void uni(int x, int y){int xx = _fi(x), yy = _fi(y);if (xx != yy) FA[xx] = yy;}
int n;
set<int>st;
int a[N];
void solve()
{for(int i=1;i<=10000;i++){FA[i] = i;}cin>>n;for(int i=1;i<=n;i++){int k;cin>>k;for(int j=1;j<=k;j++){cin>>a[j];uni(a[j],a[1]);st.emplace(a[j]);}}int q,cnt=0;for(int i=1;i<=st.size();i++){if(_fi(i) == i ){cnt++;}}cout<<st.size()<<' '<<cnt<<endl;cin>>q;while(q--){int a,b;cin>>a>>b;if(_fi(a) == _fi(b)){cout<<"Y"<<endl;}else{cout<<"N"<<endl;}}
}

L2-025 分而治之 - 团体程序设计天梯赛-练习集

跟上面图着色问题差不多，这里只需要判断每个还存在的点有没有相邻点即可

int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
void add(int s,int t){ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;//ed[IDX].w = w;
}
int n,m,k;
map <int ,bool> hs;
void solve()
{cin>>n>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;add(a,b);add(b,a);}cin>>k;while(k--){hs.clear();int u;cin>>u;for(int i=1;i<=u;i++){int x;cin>>x;hs[x] = 1;}bool f = 1;for(int i=1;i<=n;i++){if(!hs[i]){for(int j=head[i];j;j=ed[j].ne){int t = ed[j].t;if(!hs[t]){f=0;break;}}if(!f) break;}}cout<<(f?"YES":"NO")<<endl;}
}

L2-026 小字辈 - 团体程序设计天梯赛-练习集

建树求高度

void add(int s,int t)
{ed[++idx].ne = head[s];ed[idx].t = t;head[s] = idx;
}
int n;
int a[N];
int deep=0,dp[N],root;
void dfs(int now,int d)
{dp[now] = d;deep = max(deep,d);for(int i=head[now];i;i=ed[i].ne){int t = ed[i].t;dfs(t,d+1);}
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]==-1){root = i;}elseadd(a[i],i);}dfs(root,1);cout<<deep<<endl;vector <int> ans;for(int i=1;i<=n;i++){if(dp[i] == deep){ans.push_back(i);}}for(int i=0;i<ans.size();i++){cout<<ans[i];if(i<ans.size()-1) cout<<' ';}
}

L2-027 名人堂与代金券 - 团体程序设计天梯赛-练习集

模拟，最后输出的时候注意一下名次就行

int n,g,k;
typedef pair<string,int> PSI;
vector <PSI> vec,ans;
int sum = 0;
bool cmp(PSI x,PSI y)
{if(x.se==y.se){return x.fi<y.fi;}else{return x.se>y.se;}
}
void solve()
{cin>>n>>g>>k;for(int i=1;i<=n;i++){string s;int sc;cin>>s>>sc;vec.pb({s,sc});if(sc>=60 && sc<g) sum+=20;else if(sc>=g) sum+=50;}cout<<sum<<endl;sort(vec.begin(),vec.end(),cmp);int p=1,cnt=1;for(int i=0;i<vec.size();i++){cout<<p<<' '<<vec[i].fi<<' '<<vec[i].se<<endl;cnt++;if(i<vec.size()-1&&vec[i+1].se<vec[i].se) p=cnt;if(p>k) break;}
}

L2-028 秀恩爱分得快 - 团体程序设计天梯赛-练习集

很牛逼的模拟题，光是数据处理就很头疼。用邻接表（？）存一下每两个点之间的亲密度

后面就按题意处理即可

int n,m,a,b;
double mp[1005][1005];
bool sx[N];
int kk[N];
typedef pair<int,double> PID;
vector <PID> va,vb;
bool cmp(PID x,PID y)
{if(abs(x.se-y.se)<1e-9){return x.fi<x.fi;}else{return x.se>y.se;}
}
void solve()
{cin>>n>>m;for(int i=1;i<=m;i++){int k;cin>>k;double add = 1.0/k;for(int j=1;j<=k;j++){string s;cin>>s;int id = abs(stoi(s));kk[j] = id;if(s[0] != '-'){sx[id] = 1;}}for(int j=1;j<=k;j++){for(int jj=j+1;jj<=k;jj++){mp[kk[j]][kk[jj]] += add;mp[kk[jj]][kk[j]] += add;}}}string sa,sb;cin>>sa>>sb;a = abs(stoi(sa));b = abs(stoi(sb));sx[a] = (sa[0]!='-');sx[b] = (sb[0]!='-');double now = mp[a][b];double topa=0,topb=0;for(int i=0;i<n;i++){if(sx[a]!=sx[i]){va.pb({i,mp[a][i]});topa = max(topa,mp[a][i]);}if(sx[b]!=sx[i]){vb.pb({i,mp[b][i]});topb = max(topb,mp[b][i]);}}if(topa == topb && topa == now){if(sx[a]==0)cout<<'-'<<a<<' '<<b<<endl;else{cout<<a<<' '<<"-"<<b<<endl;}return ;}for(int i=0;i<n;i++){if(mp[a][i]==topa && sx[i]!=sx[a]){cout<<(sx[a]?"":"-")<<a<<' '<<(sx[i]?"":"-")<<i<<endl;}}for(int i=0;i<n;i++){if(mp[b][i]==topb && sx[i]!=sx[b]){cout<<(sx[b]?"":"-")<<b<<' '<<(sx[i]?"":"-")<<i<<endl;}}
}

L2-029 特立独行的幸福 - 团体程序设计天梯赛-练习集

写懵了，这里代码看个乐子就行，纯翻译题面。数据量只有1000，直接暴力

int a,b;
map<int,int>hs,pl;
bool prime(int x)
{if(x==1) return 0;for(int i=2;i*i<=x;i++){if(x%i==0){return 0;}}return 1;
}
int fun(int x)
{int res = 0,y=x;while(y){int tmp = y%10;res+=tmp*tmp;y/=10;}return res;
}
void dfs(int x)
{//cout<<x<<endl;int res = x,cnt=1;int y = x;int f = 1;map <int,bool> hss;hss[x] = 1;while(res!=1){//cout<<res<<endl;int tmp = fun(res);cnt++;res = tmp;if(hss[res] == 1){f=0;break;}hss[res] = 1;}if(res==1){pl[x]=--cnt;hs[x]=0x3f3f3f3f;res = x;while(res!=1){int tmp = fun(res);res = tmp;hs[res] = 1;}return ;}if(f==0){hs[x] = -1;res = fun(x);while(hs[res] != -1){hs[res]=-1;int tmp = fun(res);res = tmp;}}
}
void solve()
{cin>>a>>b;int f = 0;for(int i=a;i<=b;i++){//cout<<prime(i)<<endl;if(hs[i] == -1) continue;if(hs[i] == 0x3f3f3f3f){//cout<<i<<' '<<(pl[i]*(prime(i)?2:1))<<endl;//f=1;}else if(hs[i]==0)dfs(i);}for(int i=a;i<=b;i++){if(hs[i] == -1) continue;if(hs[i] == 0x3f3f3f3f){cout<<i<<' '<<(pl[i]*(prime(i)?2:1))<<endl;f=1;}}if(!f) cout<<"SAD"<<endl;
}

L2-031 深入虎穴 - 团体程序设计天梯赛-练习集

建树求高度

int head[N], IDX = 0;struct NODE{int t, ne, w=0;}ed[N];
void add(int s,int t){ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;//ed[IDX].w = w;
}
int n,rd[N];
int ans,ansd=0;
void dfs(int now,int dpp)
{if(dpp>ansd){ansd=dpp;ans = now;}for(int i=head[now];i;i=ed[i].ne){dfs(ed[i].t,dpp+1);}
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){int k;cin>>k;for(int j=1;j<=k;j++){int x;cin>>x;add(i,x);rd[x]++;}}int rt;for(int i=1;i<=n;i++){if(rd[i]==0){rt=i;break;}}dfs(rt,1);cout<<ans<<endl;
}

L2-032 彩虹瓶 - 团体程序设计天梯赛-练习集

用stack模拟就行，栈满了也不要停止输入（）。不要忘记如果栈还有东西就尽量往外拿

int n,m,k;
stack<int> st;
int now;
void solve()
{cin>>n>>m>>k;while(k--){while(!st.empty()){st.pop();}bool f = 0;now = 1;for(int i=1;i<=n;i++){int x;cin>>x;//cout<<now<<endl;if(x == now){now++;while(!st.empty()&&st.top()==now){st.pop();now++;}}else{if(st.size()==m){f=0;continue;}st.push(x);}}while(!st.empty()&&st.top()==now){st.pop();now++;}if(now == n+1) f=1;cout<<((f==1)?"YES":"NO")<<endl;}
}

L2-033 简单计算器 - 团体程序设计天梯赛-练习集

栈入门题

stack <int> s1;
stack <char> s2;
int n;
void solve()
{cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;s1.push(x);}for(int i=1;i<n;i++){char c;cin>>c;s2.push(c);}while(s2.size()){int na,nb;na = s1.top();s1.pop();nb = s1.top();s1.pop();char op = s2.top();s2.pop();if(op=='+'){s1.push(na+nb);}else if(op =='-'){s1.push(nb-na);}else if(op == '*'){s1.push(na*nb);}else{if(na == 0){cout<<"ERROR: "<<nb<<'/'<<na<<endl;return ;}else{s1.push(nb/na);}}}cout<<s1.top()<<endl;
}

L2-035 完全二叉树的层序遍历 - 团体程序设计天梯赛-练习集

建树之后，使用bfs层次遍历就行了

int n,hx[N];
struct TREE
{int v,l,r;
}tr[N];
int hdx;
int build(int idx)
{if(idx>n)return 0;tr[idx].v = hx[hdx];hdx--;tr[idx].r = build(idx*2+1);tr[idx].l = build(idx*2);return idx;
}
vector <int> ans;
void bfs(int rt)
{queue <int> q;q.push(rt);while(!q.empty()){int now = q.front();q.pop();ans.pb(tr[now].v);if(tr[now].l!=0){q.push(tr[now].l);}if(tr[now].r!=0){q.push(tr[now].r);}}
}
void solve()
{cin>>n;for(int i=1;i<=n;i++){cin>>hx[i];}hdx=n;int rt = build(1);bfs(rt);for(int i=0;i<ans.size();i++){cout<<ans[i]<<(i<ans.size()-1?" ":"\n");}
}