题目详情 - L2-039 清点代码库 (pintia.cn)

思路：

1. 因为map可以存stl容器，我们可以用vector存每一行信息，再用map存储每一行产生的vector，记录其出现次数
2. map存vector时也会自动按vector大小比较，给每一种输出按小到大排序。
3. 那么我们最后只需要按map顺序用vector<pair<int,vector<int>>>ans存储map的每一个vector及其次数即可，然后再排序。
4. （注意，把出现次数改为负的才可以用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)

思路：

1. 我们想到每次只改一个点，那么我们可以记录所有点到起点与终点的距离，然后维护区间最小即可
2. 所以首先跑两遍堆优化dijksta
3. 因为只维护区间一个数据，所以可以用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)

思路：

1. 他搞得好像花里胡哨，但是因为M只有100，我不仅可以暴力O（n^2)，甚至可以暴力O（n^3)
2. 所以，我们直接用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;
}