模拟考试"/>
2018.7.19模拟考试
我的运气真的有够差...代码没能提交到评测姬上去...虽然就算提交了也是爆零
T1 题意简述：合并数列相邻项（也可不合并）使得数列单调不减并使项数最多。求原项数与合并后项
数的差。
0<n<=5000，0<a[i]<=2147483647
解题思路：首先考虑贪心，显然错误（如：5 1 7 7 8）。
考虑dp。dp[i]表示数列前i个数合并后最多的项数，lst[i]表示以数列第i项结尾的需合
并区间的数值和。
考虑递推式，发现分两种情况。（枚举k）
1.a[k]>=lst[i] dp[k]=dp[i]+1,lst[k]=a[k],k++；
2.a[k]<lst[i] lst[i]+=a[k],k++。直至满足情况一。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
ll n,dp[5001],sum[5001],a[5001],lst[5001];
int main()
{freopen("tower.in","r",stdin);freopen("tower.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];dp[1]=1;lst[1]=a[1];for(ll i=2;i<=n;i++)for(ll j=i-1;j>=0;j--)if(sum[i]-sum[j]>=lst[j]){dp[i]=dp[j]+1;lst[i]=sum[i]-sum[j];break;}printf("%lld\n",n-dp[n]);return 0;
}
T2 题意简述：在n天里共有m项工作和p节课程，每项工作可以无限做，每节课程只能上一次。对于每一
项工作有2个参数，即所需时长和等级要求。只有达到了等级要求才能做这项工作。每项
工作的报酬相等。对于每一节课程有3个参数，即开始时间，所需时长和上完课程后等级
会变为何值。初始人物等级为1，求在n天内最多得到多少报酬。
n≤10000，m≤10000，p≤100，
fin[i]≤10000，chg[i]≤100，need[i]≤100，tim[i]≤10000
解题思路：显然dp。dp[i][j]表示第i天，等级为j所能得到的最多报酬。
考虑递推式，发现分3种情况。
1.划水一天。（这不就是我吗）dp[i][j]=max(dp[i][j],dp[i-1][j]);
2.工作一天。dp[i][j]=max(dp{i][j],dp[i-tim[k]][j]);(j>=need[k])
3.从这一天起开始上课。dp[fin[k]][chg[k]]=max(dp[fin[k]][chg[k]],dp[i-1][j])。
还有一些细节和优化。
1.考虑工作，发现等级要求高且所需时长长的工作可以直接舍去。
2.第3项递推式的j要从1枚举到100，取max后与上课后的收益比较。
3.看见-1了吗。没错那里就是我倒下的地方。
注意若从第i天开始上课，收益只能计算前i-1天的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int n,ans,cls,wrk,dp[10001][101],minlen[101];
struct uio{int sta,fin,len,chg;
}cla[101];
struct oiu{int len,lvl;
}wor[10001];
bool cmp(oiu x,oiu y) {return x.lvl<y.lvl;}
bool cmp1(uio x,uio y) {return x.sta<y.sta;}
int main()
{freopen("wrk.in","r",stdin);freopen("wrk.out","w",stdout);scanf("%d%d%d",&n,&cls,&wrk);for(int i=1;i<=cls;i++){scanf("%d%d%d",&cla[i].sta,&cla[i].len,&cla[i].chg);cla[i].fin=cla[i].sta+cla[i].len;}for(int i=1;i<=wrk;i++)scanf("%d%d",&wor[i].lvl,&wor[i].len);sort(wor+1,wor+1+wrk,cmp);sort(cla+1,cla+1+cls,cmp1);for(int i=1;i<=100;i++){int j=1,mn=INF;while(j<=wrk&&wor[j].lvl<=i)mn=min(mn,wor[j].len),j++;minlen[i]=mn;}memset(dp,0xc0,sizeof(dp));dp[0][1]=0;for(int i=1;i<=n;i++){int mx=-INF,cnt=1;for(int j=1;j>=100;j++)mx=max(mx,dp[i-1][j]);while(i==cla[cnt].sta&&cnt<=wrk)dp[cla[cnt].fin][cla[cnt].chg]=max(dp[cla[cnt].fin][cla[cnt].chg],mx),cnt++;for(int j=1;j<=100;j++){if(i-minlen[j]>=0)dp[i][j]=max(dp[i][j],dp[i-minlen[j]][j]+1);dp[i][j]=max(dp[i][j],dp[i-1][j]);}}for(int j=1;j<=100;j++)ans=max(ans,dp[n][j]);printf("%d\n",ans);return 0;
}
T3 题意简述：对于一个有n个点，m条边且至多有一个点度数>2的图，任选k个点，使图上任意一点到这
k个点中的任意一点的最大距离最小。求这个最大距离。
1≤n≤2000，n-1<=m<=n*(n-1)/2
解题思路：对于min(max(...,...))或max(min(...,...))的题目，考虑二分答案。
对于度数全部小于等于2的图，其只有可能是一条链或一个环。
若有且仅有一个点度数大于2，那么这个图将类似菊花图，这个点暂且称为花心。
花心所拥有的性质为：花心为任意一条链或一个环的一部分。
记录所有点的度数，若无花心则直接输出答案。ans=ceil((n-k)/(2*k))。
若有花心，考虑哪个点与花心距离最小。由于n仅有2000，枚举即可。
bfs求出所枚举点到花心的距离。若距离大于二分答案，直接跳过，否则继续。
将与所枚举点距离小于二分答案的点都打上标记。剩余的点必会构成若干条链。
dfs求出每条链的长度后按照情况一计算答案即可。ans=sigma(ans[i])+1。
注意一开始枚举的那个点也要算。最后取min看符不符合k即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int n,m,k,cnt,len,root,d[2001],head[2001];
int dep[2001],vis[2001];
struct uio{int nxt,to;
}edge[200001];
int ceil_int(int x,int y) {return x/y+(x%y>0);}
void add(int x,int y)
{edge[++cnt].nxt=head[x];edge[cnt].to=y;head[x]=cnt;
}
void bfs(int x)
{memset(dep,-1,sizeof(dep));queue<int> que;while(!que.empty()) que.pop();que.push(x);dep[x]=0;while(!que.empty()){int now=que.front();que.pop();for(int i=head[now];i;i=edge[i].nxt){int y=edge[i].to;if(dep[y]==-1)dep[y]=dep[now]+1,que.push(y);}}
}
int dfs(int x)
{vis[x]=1,len++;for(int i=head[x];i;i=edge[i].nxt)if(!vis[edge[i].to]) dfs(edge[i].to);
}
int chk(int x)
{int tmp=INF;for(int i=1;i<=n;i++){bfs(i);int num=0;if(dep[root]>x) continue;memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)if(dep[i]<=x) vis[i]=1;for(int i=1;i<=n;i++)if(!vis[i]){len=0;dfs(i);num+=ceil_int(len,2*x+1);}tmp=min(tmp,num+1);}return tmp;
}
int main()
{freopen("holes.in","r",stdin);freopen("holes.out","w",stdout);scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);d[u]++,d[v]++;add(u,v),add(v,u);}for(int i=1;i<=n;i++)if(d[i]>2) {root=i;break;}if(!root) {printf("%d",ceil_int(n-k,2*k));return 0;}int l=1,r=n,ans=INF;while(l<=r){int mid=(l+r)>>1;if(chk(mid)<=k) ans=min(ans,mid),r=mid-1;else l=mid+1;}printf("%d\n",ans);return 0;
}
转载于:.html
更多推荐
2018.7.19模拟考试
发布评论