本文主要是介绍紫书训练 7.12，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://vjudge.net/contest/310440#overview 单调队列+贪心+dp
密码：996996
A - Feel Good
找到每个点以他为最小值向左向右的最大区间，用单调队列即可。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=1e5+5;
int n,a[maxn];
ll sum[maxn];
struct node{int num,l,id;
}s[maxn];
int main(){std::ios::sync_with_stdio(0);cin>>n;rep(i,1,n) cin>>a[i],sum[i]=sum[i-1]+a[i];a[n+1]=-1; node tp;ll ans=-1,al=0,ar=0,top=0;rep(i,1,n+1){if(top==0){tp.num=a[i],tp.l=i,tp.id=i;s[++top]=tp;}else{if(a[i] > s[top].num){tp.num=a[i],tp.l=i,tp.id=i;s[++top]=tp;}else{while(top!=0 && a[i] <= s[top].num){tp=s[top--];ll nn=tp.num*(sum[i-1]-sum[tp.l-1]);if(nn > ans){ans=nn;al=tp.l,ar=i-1;}}tp.num=a[i],tp.id=i;if(top!=0) tp.l=s[top].id+1;else tp.l=1;s[++top]=tp;}}}cout<<ans<<endl;cout<<al<<" "<<ar<<endl; return 0;
}
B - Keep the Customer Satisfied
不是简单贪心，可以后悔的贪心，当出现超过时限时，扔掉一个耗时最长的。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=8e5+5;
int T,n;
struct node {int t,ls;
} a[maxn];
bool cmp(node x,node y) {return x.ls<y.ls;
}
priority_queue<int> q;
int main() {std::ios::sync_with_stdio(0);cin>>T;int TT=T;while(T--) {if(T!=TT-1) cout<<endl;cin>>n;rep(i,1,n) cin>>a[i].t>>a[i].ls;sort(a+1,a+n+1,cmp);int ans=n,np=0;while(!q.empty()) q.pop();rep(i,1,n) {np+=a[i].t;q.push(a[i].t);while(np > a[i].ls) {np-=q.top();q.pop();ans--;}}cout<<ans<<endl;}return 0;
}
C - Cricket Field
并没有什么思路，但是这个点的个数很小，挺有意思的暴力。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=1e2+10;
struct node{int x,y;
}a[maxn];
bool cmp(node x,node y){if(x.x != y.x) return x.x<y.x;return x.y<y.y;
}
int T,n,w,h;
int main(){std::ios::sync_with_stdio(0);cin>>T;int TT=T;while(T--){if(T != TT-1) cout<<endl;cin>>n>>w>>h;rep(i,1,n){cin>>a[i].x>>a[i].y;} a[0]=node{0,0},a[n+1]=node{w,h};sort(a+1,a+n+1,cmp);int ans=-1,ax,ay;for(int i=0;i<=n+1;++i){for(int j=i+1;j<=n+1;++j){int up=max(a[i].y,a[j].y),down=min(a[i].y,a[j].y);int len=up-down,nx=0;for(int k=1;k<=n+1;++k){if(k==n+1 || (down<a[k].y && up>a[k].y)){int tlen=min(len,a[k].x-nx);if(tlen>ans){ans=tlen;ax=nx,ay=down;}nx=a[k].x;}}}}cout<<ax<<" "<<ay<<" "<<ans<<endl;}return 0;
}D - K-Graph Oddity
因为题目没有说不可能的情况，默认有解，搜索涂色即可，但是如果要你判断是否可行，就emmm
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=1e5+5;
int n,m,k,ans[maxn];
vector<int> eg[maxn];
bool vis[maxn];
il void solve(int np){rep(i,1,k) vis[i]=0;for(int i=0;i<SZ(eg[np]);++i){if(ans[eg[np][i]]) vis[ans[eg[np][i]]]=1;}rep(i,1,k){if(!vis[i]){ans[np]=i;break;} }for(int i=0;i<SZ(eg[np]);++i){if(!ans[eg[np][i]]) solve(eg[np][i]);}
}
int main(){std::ios::sync_with_stdio(0);while(cin>>n>>m){int x,y;rep(i,1,m){cin>>x>>y;eg[x].pb(y);eg[y].pb(x);} k=0;rep(i,1,n) k=max(k,SZ(eg[i]));if(k%2==0) k++;solve(1);cout<<k<<endl;rep(i,1,n) cout<<ans[i]<<endl;rep(i,1,n){ans[i]=0,eg[i].clear();}}return 0;
}E - The Tower of Babylon
把一块砖的六种形态全放入数组，反正都是无限用，先进行一次简单的排序，把可能的小于当前砖的都排到见面，方便后面的转移。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=1e3+5;
int n,dp[maxn];
struct node{int x,y,z;
};
vector<node> a;
il bool cmp(node x,node y){return x.x*x.y<y.x*y.y;
}
int main(){std::ios::sync_with_stdio(0);int cnt=0;while(cin>>n && n){int x,y,z;rep(i,1,n){cin>>x>>y>>z;a.pb(node{x,y,z});a.pb(node{x,z,y});a.pb(node{y,x,z});a.pb(node{y,z,x});a.pb(node{z,x,y});a.pb(node{z,y,x});} sort(a.begin(),a.end(),cmp);int ans=-1;for(int i=0;i<SZ(a);++i){dp[i]=a[i].z;for(int j=0;j<i;++j){if(a[i].x>a[j].x && a[i].y>a[j].y){dp[i]=max(dp[i],dp[j]+a[i].z);}}ans=max(ans,dp[i]);}cout<<"Case "<<++cnt<<": maximum height = "<<ans<<endl;ms(dp,0),a.clear();}return 0;
}
F - Tour
想不到啊，太难了，思路可以参考紫薯或者传送门
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=1e3+5;
struct node{int x,y;
}a[maxn];
double dis[maxn][maxn],dp[maxn][maxn];
//dp[i][j] :从i到1 ，1到j的最短距离
il double getdis(int i,int j){return (a[i].x-a[j].x+0.0)*(a[i].x-a[j].x+0.0)+(a[i].y-a[j].y+0.0)*(a[i].y-a[j].y+0.0);
}
int main(){
// std::ios::sync_with_stdio(0);int n;while(cin>>n){rep(i,1,n) cin>>a[i].x>>a[i].y;rep(i,1,n) rep(j,1,n) dis[i][j]=sqrt(getdis(i,j));ms(dp,0x3f);dp[1][1]=0;for(int i=2;i<=n;++i) dp[i][1]=dis[i][1];for(int i=3;i<=n;++i){dp[i][i-1]=inf;for(int j=1;j<=i-2;++j){dp[i][j]=dp[i-1][j]+dis[i-1][i];dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+dis[j][i]); }}dp[n][n]=dp[n][n-1]+dis[n-1][n];printf("%.2lf\n",dp[n][n]);}return 0;
}G - A Spy in the Metro
逆向思维，从后往前想。这样可能更加好想
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int maxn=205;
int n,m,T,dp[maxn][maxn],t[maxn];
// dp[i][j] 在第i个车站j时刻需要等的时间最小值
bool cr[maxn][maxn],cl[maxn][maxn];
int main(){std::ios::sync_with_stdio(0);int cnt=0;while(cin>>n && n){cin>>T;ms(cr,0),ms(cl,0);rep(i,1,n-1) cin>>t[i];cin>>m;int nt;rep(i,1,m){cin>>nt;rep(j,1,n){cr[j][nt]=1,nt+=t[j];}}cin>>m;rep(i,1,m){cin>>nt;drep(j,n,1){cl[j][nt]=1,nt+=t[j-1];}}ms(dp,0x3f);dp[n][T]=0;for(int j=T-1;j>=0;--j){for(int i=1;i<=n;++i){dp[i][j]=dp[i][j+1]+1;if(cl[i][j]) dp[i][j]=min(dp[i][j],dp[i-1][j+t[i-1]]);if(cr[i][j]) dp[i][j]=min(dp[i][j],dp[i+1][j+t[i]]);}}cout<<"Case Number "<<++cnt<<": ";if(dp[1][0] > T) cout<<"impossible"<<endl;else cout<<dp[1][0]<<endl;}return 0;
}
这篇关于紫书训练 7.12的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
