admin管理员组

文章数量:815356

2021天梯赛L2题解全集

L2-037 包装机 (25 分)
其实就是个模拟,按照题目意思写下去吧,也不知道为什么比赛的时候一直只能拿20分(用char数组+ int变量模拟栈) 赛后直接用栈写的一发满分就很奇怪。。。主要是题意有点绕,看各位语文如何 了

 char s[110][1100];
ll p[200];
stack<char>sb;
signed main(){
ll n,m,k;
read(n);
read(m);
read(k);
for(int i=1;i<=n;i++){p[i]=1;scanf("%s",s[i]+1);}
ll op;while(scanf("%lld",&op)!=EOF){if(op==-1)break;if(op==0){if(sb.size()==0){continue;}else{printf("%c",sb.top());sb.pop();}continue;}if(p[op]==m+1){continue;}
if(sb.size()==k){printf("%c",sb.top());sb.pop();
}
if(p[op]==m+1){continue;}
else{
sb.push(s[op][p[op]]);p[op]++;}}}

L2-038 病毒溯源 (25 分)
其实就是给了我们一颗树,但是只能由题意的方式单向链接,问字典序最小的最长链。直接建个单向边的,先处理出来最深的点作为根,以根开始搜索,暴力即可。
(( 比赛的时候就挺懵逼,树的直径?然后拿了0鸭蛋

const int N=1e5+7;
ll k=0;
struct pe{
ll next;
ll v;
}a[N];
ll head[N];
void add(ll u,ll v){
a[++k].next=head[u];
a[k].v=v;
head[u]=k;}
ll vis[222222];
ll ma=0;
vector<ll>ans;
vector<ll>rnm;
void dfs(ll rt,ll d){if(d>ma){
ma=d;
ans=rnm;}
else if(d==ma&&rnm<ans){ans=rnm;
}
for(int i=head[rt];i!=0;i=a[i].next){ll v=a[i].v;rnm.push_back(v);dfs(v,d+1);rnm.pop_back();
}}
signed main(){ll n;
read(n);
for(int i=1;i<=n;i++){ll x;read(x);for(int j=1;j<=x;j++){ll r;read(r);r++;add(i,r);vis[r]=1;}
}
ll rt=1;
while(vis[rt])rt++;
ll op=1;
dfs(rt,op);printf("%lld\n",ma);
printf("%lld",rt-1);
for(int i=0;i<ans.size();i++){printf(" %lld",ans[i]-1);}
//为了方便  我已经把题意的点转化为了1--n 
}

L2-039 清点代码库 (25 分)
其实就是给了我们n串数据,题目要我们按照完全相同的数据的数量多少输出,如果数量一样就按数据的字典序递增输出。其实这个题非常简单,利用好STL是非常简单的。比赛的时候没考虑好hash关系没拿到满分QAQ
因为是int范围的数,那么不妨直接给它加上1e10 然后利用每个数位去造一个hash,注意,每个元素的长度要造一样长,不足的直接添0。
Set<pari<int,string>> 可以实现题意的要求
再用map记录对应的编号就OK

 #include<bits/stdc++.h>
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)using namespace std;ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qp(ll a,ll b,ll mod){ll ans=1;if(b==0){return ans%mod;}while(b){if(b%2==1){b--;ans=ans*a%mod;}a=a*a%mod;b=b/2;}return ans%mod;}//快速幂%
ll qpn(ll a,ll b, ll p){ll ans = 1;a%=p;while(b){if(b&1){ans = (ans*a)%p;--b;}a =(a*a)%p;b >>= 1;}return ans%p;}//逆元   (分子*qp(分母,mod-2,mod))%mod;ll a[10011][200];ll cnt=0;
set<pair<ll,string> >s;
map<string,ll>vis;
map<string,ll>pos;
signed main(){ll lcj=1e11;
ll n,m;
read(n);
read(m);
ll ans=0;
for(int i=1;i<=n;i++){string op="";for(int j=1;j<=m;j++){read(a[i][j]);string opp="";//  op+=has[a[i][j]+101] ;ll fu=a[i][j]+lcj;while(opp.size()<12){char x=(fu%10)+'0';opp+=x;fu=fu/10;}  //00000000// while(opp.size()<11){// }reverse(opp.begin(),opp.end());op+=opp;}vis[op]++;pos[op]=i;
}for(auto x:vis){s.insert(mp(-x.second,x.first));}printf("%d\n",s.size());
for(auto x:s){printf("%lld",-x.first);ll ok=pos[x.second];for(int i=1;i<=m;i++){printf(" %lld",a[ok][i]);}
printf("\n");}}

L2-040 哲哲打游戏 (25 分)
emmm这个题就是傻逼题吧,比赛的时候sb的我开的是数组
由于Ki不确定,但总和1e6 所以开vector,其他的按照题意写就OK
有个坑就是,我们要设置存档数组vis[1]=1

 #include<bits/stdc++.h>
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)using namespace std;ll gcd(ll a,ll b){if(a<0)a=-a;if(b<0)b=-b;return b==0?a:gcd(b,a%b);}
template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll qp(ll a,ll b,ll mod){ll ans=1;if(b==0){return ans%mod;}while(b){if(b%2==1){b--;ans=ans*a%mod;}a=a*a%mod;b=b/2;}return ans%mod;}//快速幂%
ll qpn(ll a,ll b, ll p){ll ans = 1;a%=p;while(b){if(b&1){ans = (ans*a)%p;--b;}a =(a*a)%p;b >>= 1;}return ans%p;}//逆元   (分子*qp(分母,mod-2,mod))%mod;vector<ll>v[100010];
ll vis[555555];
signed main(){ll n,m;
read(n);
read(m);
for(int i=1;i<=n;i++){ll num;read(num);v[i].push_back(num);for(int j=1;j<=num;j++){//read(v[i][j]);ll x;read(x);v[i].push_back(x);}}
vis[1]=1;
ll pos=1;
while(m--){ll op,x;read(op);read(x);if(op==0){pos=v[pos][x];continue;}if(op==1){vis[x]=pos;// vis.push_back(pos);printf("%lld\n",pos);}if(op==2){pos=vis[x];}}
printf("%lld",pos);}

。。。再说几句题外话吧,天梯赛我只拿了159分,是团队的坑逼

本文标签: 2021天梯赛L2题解全集