洛谷刷题7.24

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

简单的二叉树遍历

#include<bits/stdc++.h>
#define ll long long
using 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<<show(s);
}
int main() {
string s;
cin>>n>>s;
dfs(s);return 0;
}

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

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

#include<bits/stdc++.h>
#define ll long long
using 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<<root;if(l) dfs(mid.substr(0,l),behind.substr(0,l));if(r) dfs(mid.substr(l+1),behind.substr(l,r));
}
int main() {
string mid,behind;
cin>>mid>>behind;
dfs(mid,behind);return 0;
}

P1305 新二叉树 - 洛谷

依旧二叉树遍历

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int flag=(int)('*');
int l[1000],r[1000];
void dfs(int root){cout<<(char)root;if(l[root]!=flag) dfs(l[root]);if(r[root]!=flag) dfs(r[root]);
}
int main() {
int n;
string s;
cin>>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<bits/stdc++.h>
#define ll long long
using namespace std;
int n,k;
unsigned int a;
priority_queue<unsigned int,vector<unsigned int>,greater<unsigned int>>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<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll a,ans=0,k1,k2;
priority_queue<ll,vector<ll>,greater<ll>>q; 
int main() {
cin>>n;
for(int i=0;i<n;i++){cin>>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<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a,b,c;
priority_queue<ll>q; 
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;}}
}
vector<ll>ans;
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<bits/stdc++.h>
#define ll long long
using 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<bits/stdc++.h>
#define ll long long
using namespace std;
struct point{ll x,s;
}arr[500005];
ll n,d,k,dp[500005];
deque<ll>q;
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<=arr[i].x-l){put(now++);}out(arr[i].x-r);if(!q.empty()) dp[i]=dp[q.front()]+arr[i].s;if(dp[i]>=k) return true;}return false;
}
int main(){
cin>>n>>d>>k;
arr[0].s=0,arr[0].x=0;
for(int i=1;i<=n;i++)cin>>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;
}