L2-1插松枝
赛时一直在用reverse…然后卡n久,其实用栈思想就简单很多了QAQ
#include<bits/stdc++.h>
#define ll long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn = 1e3 + 5;
int a[maxn];
stack<int>b,p;
vector<int>ans[maxn];
int main(){
IOS;
int n, m, k;
cin >> n >> m >> k;
int pos = 0;
for(int i = 1; i <= n; i++)cin >> a[i];
for(int i = n; i >= 1; i--){
p.push(a[i]);
}
//访问堆
while(p.size()){
int u = p.top();
if(b.size() == 0){
int sz = ans[pos].size();
if(sz == k)pos++;
sz = ans[pos].size();
if(sz == 0 || ans[pos][sz - 1] >= u){
ans[pos].push_back(u);
}else{
b.push(u);
}
p.pop();
}else{
//盒子不为空 先访问盒子顶
int now = b.top();
int sz = ans[pos].size();
if(sz == k)pos++;
sz = ans[pos].size();
if(sz == 0){
ans[pos].push_back(now);
b.pop();
}else{
int v = ans[pos][sz - 1];
if(v >= now){
ans[pos].push_back(now);
b.pop();
}else if(v >= u){
ans[pos].push_back(u);
p.pop();
}else{
if(b.size() == m){
pos++;
}else{
b.push(u);
p.pop();
}
}
}
}
}
while(b.size()){
int u = b.top();
int sz = ans[pos].size();
if(sz == k)pos++;
sz = ans[pos].size();
if(sz == 0 || ans[pos][sz - 1] >= u){
ans[pos].push_back(u);
b.pop();
}else{
pos++;
}
}
for(int i = 0; i <= pos; i++){
for(int j = 0; j < ans[i].size(); j++){
if(j)cout << ' ';
cout << ans[i][j];
}
cout << '\n';
}
}
L2-2老板作息表
scanf处理格式就简单很多了,排序即可
#include<bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn = 1e5+ 5;
struct node{
int h,m,s;
int h1,m1,s1;
}a[maxn];
bool cmp(node a, node b){
if(a.h == b.h){
if(a.m == b.m){
return a.s < b.s;
}
return a.m < b.m;
}
return a.h < b.h;
}
int main(){
int n;
sc("%d",&n);
for(int i = 1; i <= n; i++){
sc("%d:%d:%d - %d:%d:%d",&a[i].h,&a[i].m,&a[i].s,&a[i].h1,&a[i].m1,&a[i].s1);
}
sort(a + 1, a + 1 + n, cmp);
int preh = 0, prem = 0,pres = 0;
for(int i = 1;i <= n; i++){
if(preh != a[i].h || prem != a[i].m || pres != a[i].s){
pr("%02d:%02d:%02d - %02d:%02d:%02d\n",preh,prem,pres,a[i].h,a[i].m,a[i].s);
}
preh = a[i].h1,prem = a[i].m1,pres = a[i].s1;
}
if(preh != 23 || prem != 59 || pres != 59){
pr("%02d:%02d:%02d - %02d:%02d:%02d\n",preh,prem,pres,23,59,59);
}
}
L2-3龙龙送外卖
通过模拟样例我们可以发现,最短的路径就是每条路径走两遍,然后减去最长路径,这样我们可以先dfs1得到最长路径的深度,之后在利用dfs2把每条路径进行走两遍,然后减去最大的深度,得到的就是答案
#include<bits/stdc++.h>
#define ll long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
const int maxn = 1e5 + 5;
vector<int>g[maxn];
int dist[maxn],a[maxn],vis[maxn],fa[maxn],root,ans = 0;
void dfs1(int u, int fa){
for(auto v : g[u]){
if(v == fa)continue;
dist[v] = dist[u] + 1;
dfs1(v, u);
}
}
void dfs2(int u){
//重复节点 或者是根节点
if(vis[u] || u == root)return ;
// cout <<"??"<<'\n';
vis[u] = 1;
ans += 2;
dfs2(fa[u]);
}
int main(){
int n,q;
cin >> n >> q;
root = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
if(a[i] == -1)root = i,fa[i]=i;
else{
g[a[i]].push_back(i);
fa[i] = a[i];
}
}
dist[root] = 1;
dfs1(root, -1);
int mx = -1;
while(q--){
int x;
cin >> x;
if(vis[x]){
cout << ans - mx + 1 << '\n';
}else{
mx = max(mx, dist[x]);
dfs2(x);
cout << ans - mx + 1 << '\n';
}
}
}
L2-4大众情人
看到一堆题干,以为没用,结果debug半天一直输出4 5,一定要记住单向边=_=，之后floyd就行
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pr printf
#define sc scanf
using namespace std;
const int maxn = 505;
const int x = 1000000000;
const int INF = 0x3f3f3f3f3f;
int a[maxn];
int mp[maxn][maxn];
int main(){
for(int i = 1; i < maxn; i++){
for(int j = 1; j < maxn; j++){
if(i == j)mp[i][j] = 0;
else
mp[i][j] = 0x3f3f3f3f3f;
}
}
int n;
scanf("%d",&n);
for(int i = 1; i <= n; i++){
char str[3];
scanf("%s",str);
if(str[0] == 'F')a[i] = 0;
else a[i] = 1;
int sz;
scanf("%d",&sz);
for(int j = 1; j <= sz; j++){
int id,d;
scanf("%d:%d",&id,&d);
mp[id][i] = d;
}
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
}
}
}
vector<int>ans;
int res = INF;
for(int i = 1; i <= n; i++){
int mx = -1;
if(a[i] == 0){
for(int j = 1; j <= n; j++){
if(a[i] ^ a[j] == 1){
mx = max(mx, mp[i][j]);
}
}
}
if(mx != -1)
res = min(res, mx);
}
for(int i = 1; i <= n; i++){
int mx = -1;
if(a[i] == 0){
for(int j = 1; j <= n; j++){
if(a[i] ^ a[j] == 1){
mx = max(mx, mp[i][j]);
}
}
}
if(res == mx){
ans.push_back(i);
}
}
sort(ans.begin(), ans.end());
for(int i = 0; i < ans.size(); i++){
cout << ans[i];
if(i != ans.size() - 1)cout << ' ';
else cout << '\n';
}
ans.clear();
res = INF;
for(int i = 1; i <= n; i++){
int mx = -1;
if(a[i] == 1){
for(int j = 1; j <= n; j++){
if(a[i] ^ a[j] == 1){
mx = max(mx, mp[i][j]);
}
}
}
if(mx != -1)
res = min(res, mx);
}
for(int i = 1; i <= n; i++){
int mx = -1;
if(a[i] == 1){
for(int j = 1; j <= n; j++){
if(a[i] ^ a[j] == 1){
mx = max(mx, mp[i][j]);
}
}
}
if(res == mx){
ans.push_back(i);
}
}
sort(ans.begin(), ans.end());
for(int i = 0; i < ans.size(); i++){
cout << ans[i];
if(i != ans.size() - 1)cout << ' ';
else cout << '\n';
}
}
L3-1千手观音
27分代码,就是利用将字符串离散化,然后利用大小关系进行建图,之后利用拓扑排序进行层次遍历,字符串的字典序可以利用priority_queue进行解决,也可以利用结构体内部写operator进行排序,_最后一个超时点望有缘人提点一下,感觉就是map的调用复杂度log(n)大了？maybe
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
map<string,int>sz;
map<int,string>sz1;
vector<int>g[maxn];
vector<string>st[maxn];
int deg[maxn];
int main(){
IOS;
int n;
cin >> n;
int pos = 1;
for(int i = 1; i <= n; i++){
string str,t1 = "", t2 = "";
cin >> str;
for(int j = 0; j < str.size(); j++){
if(str[j] == '.'){
if(sz[t1] == 0){
sz[t1] = pos++,sz1[pos - 1] = t1;
}
st[i].push_back(t1);
t1 = "";
continue;
}
t1 += str[j];
}
if(sz[t1] == 0){
sz[t1] = pos++,sz1[pos - 1] = t1;
}
st[i].push_back(t1);
a[i] = st[i].size();
}
for(int i = 2; i <= n; i++){
if(a[i] == a[i - 1]){
for(int j = 0; j < st[i].size(); j++){
string t1 = st[i][j],t2 = st[i - 1][j];
if(t1 == t2)continue;
else{
int aa = sz[t1],bb = sz[t2];
g[bb].push_back(aa);
deg[aa]++;
break;
}
}
}else{
continue;
}
}
priority_queue< pair<string,int>, vector<pair<string,int> >, greater<pair<string,int> > >q;
for(int i = 1; i < pos; i++){
string now = sz1[i];
if(deg[i] == 0){
q.push(make_pair(now, i));
}
}
int cnt = 0;
while(q.size()){
pair<string,int> p = q.top();
q.pop();
if(cnt != 0)cout << ".";
cout << p.first;
cnt++;
for(int i = 0; i < g[p.second].size(); i++){
int j = g[p.second][i];
if(--deg[j] == 0){
q.push(make_pair(sz1[j], j));
}
}
}
}
经过30分钟的测试emmm,把小常数都改了,结果改了个map换成unordered_map快了3,4倍_
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int N = maxn * 2;
unordered_map<string,int>sz;
int h[N],ne[N],e[N],idx = 0;
vector<string>st[maxn];
int deg[maxn],a[maxn];
string ss[N];
void add(int a, int b, string str){
idx++;
e[idx] = b;
ne[idx] = h[a];
ss[idx] = str;
h[a] = idx;
}
int main(){
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n;
cin >> n;
int pos = 1;
for(int i = 1; i <= n; i++){
string str,t1 = "";
cin >> str;
for(int j = 0; j < str.size(); j++){
if(str[j] == '.'){
if(!sz.count(t1)){
sz[t1] = pos++;
}
st[i].push_back(t1);
t1 = "";
continue;
}
t1 += str[j];
}
if(!sz.count(t1)){
sz[t1] = pos++;
}
st[i].push_back(t1);
a[i] = st[i].size();
}
for(int i = 2; i <= n; i++){
if(a[i] == a[i - 1]){
for(int j = 0; j < st[i].size(); j++){
string t1 = st[i][j],t2 = st[i - 1][j];
if(t1 != t2){
int aa = sz[t1], bb = sz[t2];
add(bb, aa, t1);
deg[aa]++;
break;
}
}
}
}
priority_queue< pair<string,int>, vector<pair<string,int> >, greater<pair<string,int> > >q;
for(auto [u, v] : sz){
if(deg[v] == 0){
q.push(make_pair(u, v));
}
}
int cnt = 0;
while(!q.empty()){
string s = q.top().first;
int x = q.top().second;
q.pop();
if(cnt != 0)cout << ".";
cout << s;
cnt++;
if(cnt == pos - 1)break;
for(int i = h[x]; i; i = ne[i]){
int j = e[i];
if(--deg[j] == 0){
q.push(make_pair(ss[i], j));
}
}
}
}
