洛谷刷题7.24

P1087 [NOIP 2004 普及组] FBI 树 - 洛谷

简单的二叉树遍历

#include#define ll long longusing namespace std;int n;char show(string s){if(s.find(\'1\')==string::npos) return \'B\';if(s.find(\'0\')==string::npos) return \'I\';return \'F\';}void dfs(string s){if(s.length()==1){cout<<show(s);return;}dfs(s.substr(0,s.length()/2));dfs(s.substr(s.length()/2));cout<>n>>s;dfs(s); return 0;}

P1030 [NOIP 2001 普及组] 求先序排列 - 洛谷

已知中序后序遍历求先序遍历，第一步先由后序遍历的最后一个字母决定根，再在中序遍历里面确定左右子树，再递归左右子树。

#include#define ll long longusing namespace std;void dfs(string mid,string behind){char root=behind[behind.length()-1];int l=mid.find(root);int r=mid.length()-l-1;cout<>mid>>behind;dfs(mid,behind); return 0;}

P1305 新二叉树 - 洛谷

依旧二叉树遍历

#include#define ll long longusing namespace std;int flag=(int)(\'*\');int l[1000],r[1000];void dfs(int root){cout<>n;cin>>s;int root=(int)s[0];l[root]=(int)s[1];r[root]=(int)s[2];n--;while(n--){cin>>s;int temp=(int)s[0];l[temp]=(int)s[1];r[temp]=(int)s[2];}dfs(root); return 0;}

P3378 【模板】堆 - 洛谷

用STL容器priority_queue实现小顶堆

#include#define ll long longusing namespace std;int n,k;unsigned int a;priority_queue<unsigned int,vector,greater>q; int main() {cin>>n;while(n--){cin>>k;if(k==1){cin>>a;q.push(a);}else if(k==2) cout<<q.top()<<endl;else q.pop();} return 0;}

P1090 [NOIP 2004 提高组] 合并果子 - 洛谷

 依旧小顶堆+贪心

#include#define ll long longusing namespace std;int n;ll a,ans=0,k1,k2;priority_queue<ll,vector,greater>q; int main() {cin>>n;for(int i=0;i>a;q.push(a);}for(int i=1;i<n;i++){k1=q.top();q.pop();k2=q.top();q.pop();ans+=k1+k2;q.push(k1+k2);}cout<<ans; return 0;}

P2085 最小函数值 - 洛谷

依旧用堆，注意及时break防止超时

#include#define ll long longusing namespace std;ll n,m,a,b,c;priority_queueq; int main() {cin>>n>>m;while(n--){cin>>a>>b>>c;for(ll i=1;i<=m;i++){if(q.size()<m) q.push(a*i*i+b*i+c);else{if(a*i*i+b*i+c<q.top()){q.pop();q.push(a*i*i+b*i+c);}else break;}}}vectorans;while(!q.empty()){ans.push_back(q.top());q.pop();}sort(ans.begin(),ans.end());for(auto it:ans){cout<<it<<\" \";} return 0;}

P1229 遍历问题 - 洛谷

思维题，什么情况会出现前序后序遍历一样而树不一样的情况，就是当这个节点只有一个子节点，这个子节点是左右都不影响。

#include#define ll long longusing namespace std;string a,b;int main() {cin>>a>>b;ll ans=1;int n=a.length();for(int i=0;i<n-1;i++)for(int j=0;j<n-1;j++)if(a[i]==b[j+1]&&a[i+1]==b[j]) ans*=2;cout<<ans; return 0;}

P3957 [NOIP 2017 普及组] 跳房子 - 洛谷

 二分答案，check时用单调队列优化的动态规划。

#include#define ll long longusing namespace std;struct point{ll x,s;}arr[500005];ll n,d,k,dp[500005];dequeq;void put(ll x){while(!q.empty()&&dp[q.back()]<=dp[x]){q.pop_back();}q.push_back(x);}void out(ll x){while(!q.empty()&&arr[q.front()].x<x){q.pop_front();}}bool check(ll b){ll l=max(1ll,d-b),r=d+b,now=0;memset(dp,-0x3f,sizeof(dp));q.clear();dp[0]=0;for(int i=1;i<=n;i++){while(arr[now].x=k) return true;}return false;}int main(){cin>>n>>d>>k;arr[0].s=0,arr[0].x=0;for(int i=1;i>arr[i].x>>arr[i].s;ll l=-1,r=1e9;while(l+1<r){ll mid=(l+r)/2;if(check(mid)) r=mid;else l=mid;}if(r==1e9) cout<<-1;else cout<<r; return 0;}