题目详情 - L2-039 清点代码库 (pintia.cn)
思路：
- 因为map可以存stl容器，我们可以用vector存每一行信息，再用map存储每一行产生的vector，记录其出现次数
- map存vector时也会自动按vector大小比较，给每一种输出按小到大排序。
- 那么我们最后只需要按map顺序用vector<pair<int,vector<int>>>ans存储map的每一个vector及其次数即可，然后再排序。
- （注意，把出现次数改为负的才可以用less<pair>排序，不可以不改就使用greater<pair>来排序，会打乱map原本排好的按小到大顺序，否则就自定义排序也可以）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
const int N = 2e5 + 10;
map<vector<int>,int>mp;
vector<pair<int,vector<int>>>ans;
void mysolve()
{
int n,m,x;
cin>>n>>m;
for(int i=1; i<=n; ++i)
{
vector<int>tmp;
for(int j=1; j<=m; ++j)cin>>x,tmp.push_back(x);
mp[tmp]++;
}
for(auto &k:mp)ans.push_back({-k.second,k.first});
sort(ans.begin(),ans.end());
cout<<ans.size()<<endl;
for(auto k:ans)
{
cout<<-k.first;
for(auto v:k.second)cout<<" "<<v;
cout<<endl;
}
}
int32_t main()
{
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll t=1;
//cin >> t;
while (t--)
{
mysolve();
}
system("pause");
return 0;
}题目详情 - L3-028 森森旅游 (pintia.cn)
思路：
- 我们想到每次只改一个点，那么我们可以记录所有点到起点与终点的距离，然后维护区间最小即可
- 所以首先跑两遍堆优化dijksta
- 因为只维护区间一个数据，所以可以用multiset存储值，就不需要使用线段树或者树状数组了
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define int long long
typedef pair<int, int> pii;
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N =2e5+10;
struct node
{
int v,c,d;
};
vector<node>edge1[N],edge2[N];
int b[N];
int n,m,q;
void dijksta(int st,vector<int>&dis,bool fl)//正反dijksta
{
dis[st]=0;
priority_queue<pii,vector<pii>,greater<pii>>q;
q.push({dis[st],st});
if(!fl)
while(!q.empty())
{
int u=q.top().second;
q.pop();
for(node k:edge1[u])
{
if(dis[k.v]>dis[u]+k.c)
{
dis[k.v]=dis[u]+k.c;
q.push({dis[k.v],k.v});
}
}
}
else
{
while(!q.empty())
{
int u=q.top().second;
q.pop();
for(node k:edge2[u])
{
if(dis[k.v]>dis[u]+k.d)
{
dis[k.v]=dis[u]+k.d;
q.push({dis[k.v],k.v});
}
}
}
}
}
void mysolve()
{
cin>>n>>m>>q;
int x,y,c,d;
vector<int>dis1(n+1,llINF),dis2(n+1,llINF);
for(int i=1; i<=m; ++i)cin>>x>>y>>c>>d,edge1[x].push_back({y,c,d}),edge2[y].push_back({x,c,d});
dijksta(1,dis1,0),dijksta(n,dis2,1);
multiset<ll>st;
for(int i=1; i<=n; ++i)
{
cin>>b[i];
if(dis1[i]!=llINF&&dis2[i]!=llINF)st.insert(dis1[i]+(dis2[i]+b[i]-1)/b[i]);//注意dis为llINF时，是不存在这种走法的，此时强行更新会污染数据，所以必须都可以走才更新
}
while(q--)
{
cin>>x>>y;
if(dis1[x]!=llINF&&dis2[x]!=llINF)//注意边要可以走
{
st.erase(st.find(dis1[x]+(dis2[x]+b[x]-1)/b[x]));
b[x]=y;
st.insert(dis1[x]+(dis2[x]+b[x]-1)/b[x]);
}
cout<<*st.begin()<<endl;
}
}
int32_t main()
{
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll t=1;
//cin >> t;
while (t--)
{
mysolve();
}
system("pause");
return 0;
}题目详情 - L3-029 还原文件 (pintia.cn)
思路：
- 他搞得好像花里胡哨，但是因为M只有100，我不仅可以暴力O（n^2)，甚至可以暴力O（n^3)
- 所以，我们直接用string存每一行数据，然后dfs匹配即可（必须dfs，因为我可能有多个片段开头一点是相同的，你总不能说他们各自的位置可以随便放吧）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define endll endl<<endl
const int N = 12000;
string s[N];
bool vis[N];
string b;
vector<int>ans;
bool flag;
int m,k;
void dfs(int num,int p)
{
if(num==m)//如果能m段匹配完，说明是正确答案，不用再dfs了
{
flag=1;
return;
}
if(flag)return;
for(int j=1; j<=m; ++j)
{
if(!vis[j])
{
int len=(int)s[j].size();
if(b.substr(p+1,len)==s[j])
{
vis[j]=1;
int tmp=p;
ans.push_back(j);
for(int x=p+len; x>=0; --x)if(b[x]==' ')
{
tmp=x;
break;
}
dfs(num+1,tmp);
if(flag)return;
ans.pop_back();
vis[j]=0;
}
}
}
}
void mysolve()
{
int n;
cin>>n;
getchar();
getline(cin,b);
b=' '+b;
int p=0;
cin>>m;
for(int i=1; i<=m; ++i)
{
cin>>k;
getchar();
getline(cin,s[i]);
}
dfs(0,p);
for(int i=0; i<(int)ans.size(); ++i)
{
if(i!=0)cout<<" ";
cout<<ans[i];
}
}
int32_t main()
{
// std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll t=1;
//cin >> t;
while (t--)
{
mysolve();
}
system("pause");
return 0;
}文章来源地址https://www.toymoban.com/news/detail-413994.html
文章来源：https://www.toymoban.com/news/detail-413994.html
到了这里，关于2021天梯赛补题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
