首页 > 代码库 > noip模拟赛#15
noip模拟赛#15
#15
T1：a[i]>=a[i/2]。输出a的最大字典序
=>可以发现这是二叉树的情况那么就先预处理出每个点有多少个儿子然后递归处理就可以了。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){
if(c==‘-‘) f=-1;c=getchar();
}
while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();
return x;
}
const int nmax=1e5+5;
const int inf=0x7f7f7f7f;
int a[nmax],son[nmax],ans[nmax],n;
void dfs(int x,int l,int r){
if(x>n) return ;ans[x]=a[l];
dfs(x*2,r-son[x*2]+1,r);dfs(x*2+1,l+1,l+son[x*2+1]);
}
int main(){
freopen("lazy.in","r",stdin);
freopen("lazy.out","w",stdout);
n=read();rep(i,1,n) a[i]=read();sort(a+1,a+n+1);
dwn(i,n,1) son[i]=son[i*2]+son[i*2+1]+1;
//rep(i,1,n) printf("%d ",son[i]);printf("\n");
dfs(1,1,n);
rep(i,1,n) printf("%d ",ans[i]);printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}
/*
7
1 2 3 4 5 6 7
6
1 2 3 4 5 6
*/
T2：n:5e4,k=7 k维空间求曼哈顿距离的最远点对。
=>二维的情况下是O(N2K)的显然不行，然后我们可以根据2维的情况推广到k维的情况。复杂度是O(nk2^k)的。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){
if(c==‘-‘) f=-1;c=getchar();
}
while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();
return x*f;
}
const int nmax=5e4+5;
const int maxn=8;
const ll inf=1e17;
int a[nmax][maxn];bool vis[maxn];
int main(){
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
int n=read(),k=read();rep(i,1,n) rep(j,1,k) a[i][j]=read();
int all=(1<<k)-1;ll u,v,d,tmp,temp,cnt,ans=0;
rep(i,0,all){
u=inf;v=-inf;
clr(vis,0);for(int eo=i,et=1;eo;eo>>=1,++et) vis[et]=eo&1;
//printf("%d\n",i);
//rep(j,1,k) printf("%d",vis[j]);printf("\n");
rep(j,1,n){
temp=0;
rep(t,1,k) temp+=vis[t]?a[j][t]:-a[j][t];
u=min(u,temp);v=max(v,temp);
//printf("%d ",temp);
}
//printf("()\n");
ans=max(ans,v-u);
}
printf("%lld\n",ans);
fclose(stdin);fclose(stdout);
return 0;
}
T3：n个数可以取出k个宽度为d的块。求最大值。取出后数的权值为0。
=>完全没有思路。。。正解好像是单调队列+dp？妈呀先留坑吧。。
=>发现一个奇怪的状态就是早操前想题总是可以很快的想出来。。。然后我就发现这道题不是傻叉单调队列和前缀和优化dp么。。。不要总是以为第三题不可做！
=>然后写了个暴力跑了跑造造数据跑了跑。。。嗯交。A了三个点。。。
=>于是我不服。。。想了想可能的原因：代码应该是不会写错的，那么应该就是题看错了。果然我没考虑右边界的情况。。。TAT
=>一定要看清楚题一定要看清楚题一定要看清楚题一定要看清楚题一定要看清楚题一定要看清楚提！
嗯扔代码：
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){
if(c==‘-‘) f=-1;c=getchar();
}
while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();
return x*f;
}
const int nmax=12330;
const int maxn=505;
const int inf=0x7f7f7f7f;
int dp[maxn][nmax],t[nmax],a[nmax],q[nmax];
int main(){
freopen("bowling.in","r",stdin);
freopen("bowling.out","w",stdout);
int T=read();
rep(_T,1,T){
int n=read(),k=read(),w=read();
rep(i,1,n) a[i]=read()+a[i-1];
rep(i,n+1,n+w) a[i]=a[n];n+=w;
rep(i,1,n) dp[1][i]=a[i]-a[max(i-w,0)];
rep(i,1,n) t[i]=max(t[i-1],dp[1][i]);
rep(i,2,k){
int l=1,r=0;
rep(j,1,n) {
dp[i][j]=-inf;
if(j>=w) dp[i][j]=max(dp[i][j],t[j-w]+a[j]-a[j-w]);
if(l<=r&&q[l]<=j-w) ++l;
while(l<=r&&dp[i-1][j]-a[j]>=dp[i-1][q[r]]-a[q[r]]) --r;
q[++r]=j;
dp[i][j]=max(dp[i][j],dp[i-1][q[l]]+a[j]-a[q[l]]);
}
rep(j,1,n) t[j]=max(t[j-1],dp[i][j]);
}
int ans=-inf;
rep(i,0,n) ans=max(ans,dp[k][i]);
printf("%d\n",ans);
}
fclose(stdin);fclose(stdout);
return 0;
}
noip模拟赛#15
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。