2022天梯赛补题

题目详情 - L2-041 插松枝 (pintia.cn)

思路：模拟

1. 背包就是个栈，开个stack解决
2. 流程思路是，每次取推进器前，尽可能拿背包的，背包拿到不可以时，跳出
3. 拿推进器时判断：
   1. 如果背包装得下，装入背包。往下继续
   2. 装不下，判断能不能插，不可以，换树枝。重新检查

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;//double 型memset最大127，最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N =1e3 + 10;int a[N];
vector<int>ans[N];
stack<int>b;
int main()
{int n,m,k;cin>>n>>m>>k;for (int i=1; i<=n; ++i)cin>>a[i];int maxn=INF,p=1;for (int i=1; i<=n; ++i){while ((int)b.size()>0)//先拿背包{if (maxn>=b.top()){ans[p].push_back(b.top());maxn=b.top();b.pop();if ((int)ans[p].size()==k){p++,maxn=INF;}}else break;}if ((int)b.size()==m){if (a[i]<=maxn)//能插就插入{ans[p].push_back(a[i]);maxn=a[i];if ((int)ans[p].size()==k){p++,maxn=INF;}}else//不行，i保持下一次还是这里，换树枝{p++,maxn=INF,i--;}}else if ((int)b.size()<m)//背包有空间直接放{b.push(a[i]);}}while ((int)b.size()>0){if (maxn>=b.top()){ans[p].push_back(b.top());maxn=b.top();b.pop();if ((int)ans[p].size()==k){p++,maxn=INF;}}else{p++,maxn=INF;}}for (int i=1; i<=p; ++i)for (int j=0; j<(int)ans[i].size(); ++j){cout<<ans[i][j];if (j==(int)ans[i].size()-1)cout<<endl;else cout<<' ';}return 0;
}

题目详情 - L2-043 龙龙送外卖 (pintia.cn)

思路：画图模拟，dfs

1. 假设我们需要到达上图蓝色点，显然绿色边都需要遍历。
2. 因为每次点与点转移，所以一条路径走2次且最多两次，我们保证最优是这条路径走过一次来回就不会再走。
3. 当然，我们到达最后一个点时，不需要回去（或者去其他点），那么我们在最深处不回去，不用走两遍的边显然是最多，为最优解。

我们设起点深度为0

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;//double 型memset最大127，最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 1e5 + 10;int dep[N],head[N],f[N];
int num;
bool vis[N];//每条边，只走一次
struct node
{int next,to;
} edge[N];void add(int u,int v)
{edge[++num].next=head[u];edge[num].to=v;head[u]=num;
}void dfs(int u,int fa)//建立深度
{dep[u]=dep[fa]+1;for (int i=head[u]; i; i=edge[i].next){int v=edge[i].to;if (v!=fa)dfs(v,u);}
}int main()
{int n,m,st,x;cin>>n>>m;for (int i=1; i<=n; ++i){cin>>x;f[i]=x;if (x==-1)st=i;add(x,i);}dep[0]=-1;dfs(st,0);int maxn=0;//记录走过点的最深层ll ans=0;//ans记录至少需要走的边数*2vis[st]=1;//从起点出发肯定是访问过while (m--){cin>>x;maxn=max(maxn,dep[x]);while (!vis[x]){ans+=2;vis[x]=1;x=f[x];}cout<<ans-maxn<<endl;}
}

题目详情 - L2-044 大众情人 (pintia.cn)

思路：最短路

1. 因为需要建立所有人之间的最短路，又因为数据是,之间floyd就可最短路径三大算法——1，弗洛伊德算法floyd
2. 注意：题目要求所有异性，所以不认识也要算，距离无穷大

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;//double 型memset最大127，最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 5e2 + 10;int dis[N][N];
bool sex[N];//标记性别，0为男，1为女int main()
{int n,k,x,d;char c;cin>>n;memset(dis,0x3f,sizeof(dis));//初始无穷大for (int i=1; i<=n; ++i){cin>>c>>k;if (c=='F')sex[i]=1;else sex[i]=0;while (k--){cin>>x>>c>>d;dis[i][x]=min(d,dis[i][x]);}}//floydfor (int k=1; k<=n; ++k)for (int i=1; i<=n; ++i)for (int j=1; j<=n; ++j)if (i!=j)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);vector<int>f,m;int fd=INF,md=INF;//大众情人的离他最远异性距离for (int i=1; i<=n; ++i){int maxn=0;//记录离i最远的异性for (int j=1; j<=n; ++j){if (sex[i]^sex[j]) //异或为真，性别不同{maxn=max(maxn,dis[j][i]);//j到i的距离（不是i到j，是其他人对i）}}if (sex[i])//女性{if (maxn<fd){fd=maxn;f.clear();f.push_back(i);}else if (maxn==fd)f.push_back(i);}else{if (maxn<md){md=maxn;m.clear();m.push_back(i);}else if (maxn==md)m.push_back(i);}}for (int i=0; i<(int)f.size(); ++i){cout<<f[i];if (i==(int)f.size()-1)cout<<endl;else cout<<' ';}for (int i=0; i<(int)m.size(); ++i){cout<<m[i];if (i==(int)m.size()-1)cout<<endl;else cout<<' ';}return 0;
}

题目详情 - L3-031 千手观音 (pintia.cn)

思路：拓扑排序

拓扑排序

1. 每次如果前后两个字符串位数相同，比较第一个不同的位置
2. 注意：题目的字典序最小是基于你所有确定的排完序后再确定的，所以我们必须建立小值到大值的边，而不是反过来。这样拓扑时，是不断确定最小位的，而为确定的位置也始终是从能不能放在低位考虑，而不是上来就因为入度0放最高位。
3. 按照字典序升序排，那么我们需要建立小点到大点的边，然后跑最小堆。
4. 不能反过来建反向边跑最大堆，这样你就不能保证是尽量让值小的排前面的前提下建字典序。如存在d->a,c如果最小堆答案是c.d.a,如果反向最大堆，写出来是d.a.c（因为一开始入度0只有a与c）
5. 因为我们只需要查找，所以开无序map比较快，map有可能寄。

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;//double 型memset最大127，最小128
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 1e5 + 10;unordered_map<string,int>mp;
string back[N];
int in[N];
int head[N],num;
struct node
{int next,to;
} edge[N];
void add(int u,int v)
{edge[++num].next=head[u];edge[num].to=v;head[u]=num;
}int main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n,cnt=0;cin>>n;string s,tmp;vector<string>b;while (n--){vector<string>a;cin>>s;s+='.';int len=0;//记录片段长度for (int i=0; i<(int)s.size(); ++i){if (s[i]=='.'){tmp=s.substr(i-len,len);if (!mp[tmp])mp[tmp]=++cnt,back[cnt]=tmp;a.push_back(tmp);len=0;}else len++;}if ((int)a.size()==(int)b.size()) //如果前后字符串相同{for (int j=0; j<(int)a.size(); ++j){if (a[j]!=b[j]){add(mp[b[j]],mp[a[j]]);in[mp[a[j]]]++;break;}}}b=a;}vector<string>ans;priority_queue< pair<string,int>,vector< pair<string,int> >,greater<pair<string,int> > >q;for (int i=1; i<=cnt; ++i)if (!in[i])q.push({back[i],i});while (!q.empty()){auto u=q.top();q.pop();ans.push_back(u.first);for (int i=head[u.second]; i; i=edge[i].next){int v=edge[i].to;if (--in[v]==0)q.push({back[v],v});}}for (int i=0; i<(int)ans.size(); ++i){cout<<ans[i];if (i==(int)ans.size()-1)cout<<endl;else cout<<'.';}return 0;
}

题目详情 - L3-032 关于深度优先搜索和逆序对的题应该不会很难吧这件事 (pintia.cn)

 思路：

1. 假设u>v,我们讨论他们在树上的位置
   1. 如果u是v的祖先，显然他们构成一对逆序对，那么在所有dfs序里面他们都能有贡献，为dfs序排列数
   2. 如果u是v儿子，那么他们永远不构成逆序对，那么在所有dfs序里面他们都没有贡献
   3. 其他情况，那么在到达u与v的lca时，如果从lca先去u，那么u与v构成逆序对，否则不行。所以他的贡献是1/2dfs序的排列数。
2. 显然，计算出每个点的祖先比他大的数量与儿子比他大的数量就能得到结果。然而，复杂度是O（),所以我们可以在遍历树的时候，用树状数组维护当前树上深入路径时，比当前点u大的数量，那么他们就是贡献1的祖先，还有比u小的点的数量，显然u是比他们大的值且是他们的儿子，永远构成不了贡献。树状数组
3. dfs序数量显然是每个点儿子排列的乘积

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define int ll//全部开成ll
const int N = 3e5 + 10;
const int mod=1e9+7;
int n,num;
int t[N],head[N],dp[N],pre[N];
int cnt1,cnt2;//分别记录一直有贡献的逆序对数量与一直没贡献的逆序对数量
struct node
{int next,to;
} edge[N<<1];void add(int u,int v)
{edge[++num].next=head[u];edge[num].to=v;head[u]=num;
}void updateadd(int x,int k)
{for (int i=x; i<=n; i+=i&-i)t[i]=(t[i]+k)%mod;
}ll ask(int x)
{ll ans=0;for (int i=x; i; i-=i&-i)ans=(ans+t[i])%mod;return ans;
}ll fastpower(ll base,ll power)
{ll ans=1;while (power){if (power&1)ans=ans*base%mod;power>>=1;base=base*base%mod;}return ans;
}void dfs(int u,int fa)
{dp[u]=1;int cnt=0;//记录亲儿子数量for (int i=head[u]; i; i=edge[i].next){int v=edge[i].to;if (v!=fa){cnt++;cnt1=(cnt1+ask(n)-ask(v)+mod)%mod;//有减法的取模记得加mod保证正数cnt2=(cnt2+ask(v-1))%mod;updateadd(v,1);//把当前点加入树状数组后继续深入dfs(v,u);updateadd(v,-1);//出来后从树状树状删除dp[u]=dp[u]*dp[v]%mod;}}dp[u]=dp[u]*pre[cnt]%mod;//dp为组合数
}int32_t main()
{int r,x,y;cin>>n>>r;pre[0]=1;for (int i=1; i<=n; ++i)pre[i]=pre[i-1]*i%mod; //预处理排列数for (int i=1; i<n; ++i){cin>>x>>y;add(x,y),add(y,x);}updateadd(r,1);//显然根节点一直在树状数组dfs(r,0);int num=(n*(n-1)%mod*fastpower(2,mod-2)%mod-cnt2+mod)%mod;//贡献为1/2的点,即n*(n-1)/2-cnt2,当然是包括cnt1的，但是只算了cnt1一半的贡献，后面cnt1还有自己算另一半ll ans=(num*dp[r]%mod*fastpower(2,mod-2)%mod+cnt1*dp[r]%mod*fastpower(2,mod-2)%mod)%mod;cout<<ans<<endl;return 0;
}