洛谷刷题7.25

P1102 A-B 数对 - 洛谷

 该题可用尺取法，二分法。也可用map比较省事，nlogn的复杂度可以接受

#include#define ll long longusing namespace std;mapq; ll n,c,arr[200005],ans=0;int main(){cin>>n>>c;for(int i=1;i>arr[i];q[arr[i]]++;}for(int i=1;i<=n;i++){if(q.find(arr[i]+c)!=q.end()) ans+=q[arr[i]+c];}cout<<ans; return 0;}

P1462 通往奥格瑞玛的道路 - 洛谷

 二分+dijsktra求最短路

#include#define ll long longusing namespace std;struct bian{ll u,l;bool operator<(const bian &s1)const{return s1.l<l;}};ll n,m,k,f[10005],a,b,c,s[10005],d[10005];bool vis[10005];vectorarr[10005];bool check(ll x){memset(d,0x3f,sizeof(d));memset(vis,false,sizeof(vis));d[1]=0;priority_queuer; if(f[1]<=x) r.push(bian{1,0});while(!r.empty()){a=r.top().u;if(!vis[a]){vis[a]=true;for(auto it:arr[a]){if(f[it.u]d[a]+it.l){d[it.u]=d[a]+it.l;r.push(bian{it.u,d[it.u]});}}}}r.pop();}if(d[n]>n>>m>>k;for(int i=1;i>f[i];s[i]=f[i];}sort(s+1,s+1+n);for(int i=0;i>a>>b>>c;arr[a].push_back(bian{b,c});arr[b].push_back(bian{a,c});}int l=0,r=n+1;while(l+1<r){int mid=(l+r)/2;if(check(s[mid])) r=mid;else l=mid;}if(r==n+1) cout<<\"AFK\";else cout<<s[r]; return 0;}

 P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G - 洛谷

 依旧二分答案

#include#define ll long longusing namespace std;ll n,m,arr[100005],sum;bool check(ll x){ll now=arr[1];sum=1;for(int i=2;i=x){sum++;now=arr[i];}if(sum>=m) return true;}return false;} int main(){cin>>n>>m;for(int i=1;i>arr[i];}sort(arr+1,arr+1+n);ll l=0,r=1e9;while(l+1<r){ll mid=(l+r)/2;if(check(mid)) l=mid;else r=mid;}cout<<l; return 0;}

P1419 寻找段落 - 洛谷

 二分答案+优先队列优化动态规划

#include#define ll long longusing namespace std;ll n,s,t,a[100005];double b[100005],sum[100005];dequeq;void put(int x){while(!q.empty()&&sum[q.back()]>=sum[x]){q.pop_back();}q.push_back(x);}void out(int x){while(!q.empty()&&q.front()<x){q.pop_front();}}bool check(double x){sum[0]=0;for(int i=1;i<=n;i++){b[i]=a[i]-x;sum[i]=sum[i-1]+b[i];}q.clear();int now=0;for(int i=1;i<=n;i++){while(now=0) return true; }}return false;} int main(){cin>>n>>s>>t;for(int i=1;i>a[i];double l=-1e4-1,r=1e4+1;while(l+0.0001<r){double mid=(l+r)/2;if(check(mid)) l=mid;else r=mid;}cout<<fixed<<setprecision(3)<<l; return 0;}

P3382 三分 - 洛谷

 可用求导+二分解决

#include#define ll long longusing namespace std;int n;double l,r,a[15];double f(double x){double ans=0,temp=1;for(int i=n+1;i>=1;i--){ans+=a[i]*temp;temp*=x;}return ans;}double dao(double x){return 1000000*(f(x+0.000001)-f(x));}int main(){cin>>n>>l>>r;for(int i=1;i>a[i];}while(l+0.0000010) l=mid;else r=mid;}cout<<fixed<<setprecision(5)<<l; return 0;}

P1883 【模板】三分 | 函数 - 洛谷

 直接模板

#include #include #include #include using namespace std;int n, t;double a[10005], b[10005], c[10005];double f(double x) { double ans = a[1] * x * x + b[1] * x + c[1]; for (int i = 2; i  ans) ans = val; } return ans;}void work() { cin >> n; for (int i = 1; i > a[i] >> b[i] >> c[i]; } double l = 0.0, r = 1000.0; while (r - l > 1e-10) { double m1 = l + (r - l) / 3.0; double m2 = r - (r - l) / 3.0; if (f(m1) > f(m2)) l = m1; else r = m2; } double ans = f((l + r) / 2); if (fabs(ans) > t; while (t--) { work(); } return 0;}