noip模拟题 小奇2 by hzwer[DP][路径压缩][分类讨论][位运算]

本文主要是介绍noip模拟题 小奇2 by hzwer[DP][路径压缩][分类讨论][位运算]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这么颓下去，迟早要完。

这套题只考了2h,感觉还不错，T2做过类似的所以A了，T1和T3基本上也没什么大问题，关键就是要深入挖掘问题特质，学会分类讨论（很多题都可以剪掉大量的枝，比如T1,小奇1的T3,noip2015 day1 T3,都是需要有这种分类意识的。
T1：
题意：在坐标轴上有一些点有收益，问从0开始，每次只能向前跳4（0+4=4）步或7（0+7=7）步，最大收益是。
数据范围：
对于20%的数据n=1，m<=10^5
对于40%的数据n<=15，m<=10^5
对于60%的数据m<=10^5
对于100%的数据n<=10^5，m<=10^9，1<=ai<=10^4，1<=bi<=m
分析：
感觉这道题是数据分斥（还是什么，不知道叫什么）的典型例子，黄学长这两套题出的还是不错的。
20%n=1，只用看能不能去就行了。
60%的数据，m比较小，可以f[i]表示i这个位置的最大值，那么然后去找-4，-7的最大值就可以了。
100%，经过分析发现，>=18的情况是一定可以走到的！那么就可以18以内用数组存能不能走，18以外都可以走，在走的时候更新18以内的最大值就可以了！
下面是碎碎念可以不看：
关键就是发现>=18的那个性质，这个要求我们多手算找规律啊。
按理说发现>=18以后一百分算法应该顺理成章不过我居然没发现，还是没养成这种意识。
而且考这套题的时候太zz了，因为我的算法应该是40分，我想了很久后面那20分怎么拿，结果拿到解题报告才想起来，枚举m的话时间复杂度线性……

60分程序：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define long long ll
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define each(i,n) for(int i=1;i<=n;i++)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "mining"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e5+5;
int n,m,ans,f[Maxn];
struct node
{int a,b;
}a[Maxn];
bool cmp(node x,node y)
{return x.a<y.a;
}
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
void init()
{n=read();m=read();each(i,n){a[i].b=read();a[i].a=read();}sort(a+1,a+n+1,cmp);
}
int boo[20]={1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,0,1,1};
int check(int cur,int pre)
{if(cur-pre>=18)return 1;return boo[cur-pre];
}
void work()
{for(int i=1;i<=n;i++){int j=i-1;int flg=1;for(;j>=0;j--)if(check(a[i].a,a[j].a))f[i]=max(f[j]+a[i].b,f[i]);ans=max(ans,f[i]);}printf("%d",ans);
}
void debug()
{//
}
int main()
{freopen("hop.in","r",stdin);freopen("hop.out","w",stdout);init();work();//debug();return 0;
}

100分：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define long long ll
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define each(i,n) for(int i=1;i<=n;i++)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "mining"
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e5+5;
int n,m,ans,maxn,f[Maxn];
struct node
{int a,b;
}a[Maxn];
bool cmp(node x,node y)
{return x.a<y.a;
}
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
void init()
{n=read();m=read();each(i,n){a[i].b=read();a[i].a=read();}sort(a+1,a+n+1,cmp);
}
int boo[20]={1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,0,1,1};
int check(int cur,int pre)
{if(cur-pre>=18)return 1;return boo[cur-pre];
}
void work()
{for(int i=1;i<=n;i++){int j=i-1;for(;j>=max(0,i-17);j--)if(check(a[i].a,a[j].a))f[i]=max(f[j]+a[i].b,f[i]);if(i>18)maxn=max(maxn,f[i-18]);if(check(a[i].a,0))f[i]=max(f[i],maxn+a[i].b);ans=max(ans,f[i]);}printf("%d",ans);
}
void debug()
{//
}
int main()
{freopen("hop.in","r",stdin);freopen("hop.out","w",stdout);init();work();//debug();return 0;
}

T2:
题意：从带权矩阵左上角走到右下角（只能向下或向右走），求$(n+m-1)*Σ_{i=1}^{n+m-1}(Ai-Aavg)^2$的最小值.
分析：首先呢我们可以证明对于一个序列，若平均值错误，V值一定更小（具体怎么证？考虑一个长度为2的序列，把它拆开，看一下，这不是均值不等式吗）。
然后，你看这权值范围<=30，一看就可以做奇怪的事。根据最小精度枚举平均值情况就可以了。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define long long ll
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define each(i,n) for(int i=1,i<=n;i++)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC ""
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=305;
int t,n,m,lim,limi,ans,a[Maxn][Maxn],f[Maxn][Maxn];
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
void init()
{n=read();m=read();lim=n+m-1;for(int i=2;i<=n;i++)f[i][0]=inf;for(int j=2;j<=m;j++)f[0][j]=inf;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=read()*lim;limi=lim*30;ans=2e9;
}
void work()
{for(int i=lim;i<=limi;i++){for(int j=1;j<=n;j++)for(int k=1;k<=m;k++)f[j][k]=min(f[j][k-1],f[j-1][k])+(a[j][k]-i)*(a[j][k]-i);ans=min(ans,f[n][m]);}printf("%d\n",ans/lim);
}
void debug()
{//
}
int main()
{freopen("matrix.in","r",stdin);freopen("matrix.out","w",stdout);t=read();for(int i=1;i<=t;i++){init();work();}//debug();return 0;
}

T3:
题意：对于一棵树，对于每个点，求其他点到这个点的距离分别异或一值的和。
分析：
其实吧，多法图你就会发现，这个东西，其实可以通过统计最后几位的01来解决。具体的实现就是，用处理0那种情况（也就是两次dfs记两个数组）的方法，再同时处理个01就可以了，然而我当初太天真，写了个暴力。
碎碎念：多fa图。
暴力：（好像m!=0处理有错WA了一组，求大神指点。）

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<ctime>
#define inf 2e8
#define modd 1e9+7
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define each(i,n) for(int i=1;i<=n;i++)
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC ""
//for(int i=1;i<=n;i++)
//(double) (ll) LL (int)
//(double)clock()/CLOCKS_PER_SEC
using namespace std;
const int Maxn=1e5+5;
int n,m,a,b,ans,roa[Maxn],g[Maxn],son[Maxn];
int f[Maxn],fr[Maxn],tov[2*Maxn],des[2*Maxn],wor[2*Maxn];
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
void addedge(int cur)
{a=read();b=read();wor[2*cur]=wor[2*cur-1]=read();tov[2*cur-1]=fr[a];fr[a]=2*cur-1;des[2*cur-1]=b;tov[2*cur]=fr[b];fr[b]=2*cur;des[2*cur]=a;
}
void dfs(int u,int fath,long long dis)
{if(dis)ans+=dis^m;for(int i=fr[u];i;i=tov[i])if(des[i]!=fath)dfs(des[i],u,dis+(long long)wor[i]);
}
void dfs2(int u,int fath)
{for(int i=fr[u];i;i=tov[i])if(des[i]!=fath){dfs2(des[i],u);roa[des[i]]=wor[i];son[u]+=1+son[des[i]];f[u]+=f[des[i]]+wor[i]*(son[des[i]]+1);}
}
void dfs3(int u,int fath)
{g[u]=f[fath]-f[u]+g[fath]+roa[u]*(n-son[u]*2-2);for(int i=fr[u];i;i=tov[i])if(des[i]!=fath)dfs3(des[i],u);
}
void init()
{n=read();m=read();for(int i=1;i<n;i++)addedge(i);
}
void work()
{if(m){for(int i=1;i<=n;i++){ans=0;dfs(i,0,0LL);printf("%d\n",ans);}}else{dfs2(1,0);f[0]=f[1];dfs3(1,0);for(int i=1;i<=n;i++)printf("%d\n",f[i]+g[i]);}
}
void debug()
{//
}
int main()
{freopen("tree1.in","r",stdin);freopen("tree1.out","w",stdout);init();work();//debug();return 0;
}

这篇关于noip模拟题 小奇2 by hzwer[DP][路径压缩][分类讨论][位运算]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---