題目詳情 - L2-041 插松枝 (pintia.cn)

思路：模擬

1. 背包就是個棧，開個stack解決
2. 流程思路是，每次取推進器前，盡可能拿背包的，背包拿到不可以時，跳出
3. 拿推進器時判斷：
   1. 如果背包裝得下，裝入背包。往下繼續(xù)
   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. 假設(shè)我們需要到達上圖藍色點，顯然綠色邊都需要遍歷。
2. 因為每次點與點轉(zhuǎn)移，所以一條路徑走2次且最多兩次，我們保證最優(yōu)是這條路徑走過一次來回就不會再走。
3. 當然，我們到達最后一個點時，不需要回去（或者去其他點），那么我們在最深處不回去，不用走兩遍的邊顯然是最多，為最優(yōu)解。

我們設(shè)起點深度為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記錄至少需要走的邊數(shù)*2vis[st]=1;//從起點出發(fā)肯定是訪問過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. 因為需要建立所有人之間的最短路，又因為數(shù)據(jù)是,之間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(luò)，是其他人對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. 每次如果前后兩個字符串位數(shù)相同，比較第一個不同的位置
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 關(guān)于深度優(yōu)先搜索和逆序?qū)Φ念}應(yīng)該不會很難吧這件事 (pintia.cn)

?思路：

1. 假設(shè)u>v,我們討論他們在樹上的位置
   1. 如果u是v的祖先，顯然他們構(gòu)成一對逆序?qū)?#xff0c;那么在所有dfs序里面他們都能有貢獻，為dfs序排列數(shù)
   2. 如果u是v兒子，那么他們永遠不構(gòu)成逆序?qū)?#xff0c;那么在所有dfs序里面他們都沒有貢獻
   3. 其他情況，那么在到達u與v的lca時，如果從lca先去u，那么u與v構(gòu)成逆序?qū)?#xff0c;否則不行。所以他的貢獻是1/2dfs序的排列數(shù)。
2. 顯然，計算出每個點的祖先比他大的數(shù)量與兒子比他大的數(shù)量就能得到結(jié)果。然而，復(fù)雜度是O（),所以我們可以在遍歷樹的時候，用樹狀數(shù)組維護當前樹上深入路徑時，比當前點u大的數(shù)量，那么他們就是貢獻1的祖先，還有比u小的點的數(shù)量，顯然u是比他們大的值且是他們的兒子，永遠構(gòu)成不了貢獻。樹狀數(shù)組
3. dfs序數(shù)量顯然是每個點兒子排列的乘積

#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;//分別記錄一直有貢獻的逆序?qū)?shù)量與一直沒貢獻的逆序?qū)?shù)量
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;//記錄親兒子數(shù)量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保證正數(shù)cnt2=(cnt2+ask(v-1))%mod;updateadd(v,1);//把當前點加入樹狀數(shù)組后繼續(xù)深入dfs(v,u);updateadd(v,-1);//出來后從樹狀樹狀刪除dp[u]=dp[u]*dp[v]%mod;}}dp[u]=dp[u]*pre[cnt]%mod;//dp為組合數(shù)
}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; //預(yù)處理排列數(shù)for (int i=1; i<n; ++i){cin>>x>>y;add(x,y),add(y,x);}updateadd(r,1);//顯然根節(jié)點一直在樹狀數(shù)組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;
}