大佬教程收集整理的这篇文章主要介绍了noip30，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
一眼看，觉得是个状压，然而又觉得不太行，去打暴力了，然而暴力都打挂的我biss。
正解：
还是暴力，考虑 (meet ; in ; the ; middlE)
显然对于每个数，只有三种状态，
用当前的和，加减当前的数可以表示。
搜索 ([1,mid]) 时，记录每种 (sum) 是选择了那些所组合出来的，0，1表示选还是没选，用 (bitset) 来记录状态。
搜索 ([mid+1,n]) 时，每求出了一个 (sum) ，就需要前边那一半出现 (-sum) 的方案来得到总的方案数，显然 (-sum) 的方案数跟 (sum) 的方案数是等价的。
用的 (unordered_map) 里边套了个 (bitset)，下标是 (int) 类型的，表示组合出 (sum) 所选的数。
#include<bitset>
#include<cstdio>
#include<algorithm>
#include<unordered_map>
#define re register
using std::sort;
using std::bitset;
using std::unordered_map;
const int MAX = 1<<11;
namespace OMA
{
int n,m[21],mid,ans;
bitset<MAX>jud[MAX],tmp;
unordered_map<int,bitset<MAX> >vis;
inline void dfsl(int p,int sum,int opt)
{
if(p==mid+1)
{ vis[sum].set(opt); return ; }
dfsl(p+1,sum,opt),dfsl(p+1,sum+m[p],opt|1<<p),dfsl(p+1,sum-m[p],opt|1<<p);
}
inline void dfsr(int p,int sum,int opt)
{
if(p==n+1)
{
if(vis[sum].count())
{ tmp = vis[sum]&(~jud[opt]),ans += tmp.count(),jud[opt] |= tmp; }
return ;
}
dfsr(p+1,sum,opt),dfsr(p+1,sum+m[p],opt|(1<<(p-(mid+1)))),dfsr(p+1,sum-m[p],opt|(1<<(p-(mid+1))));
}
signed main()
{
scanf("%d",&n),mid = n/2;
for(rE int i=1; i<=n; i++)
{ scanf("%d",&m[i]); }
sort(m+1,m+1+n),dfsl(1,0,0),dfsr(mid+1,0,0);
printf("%dn",ans-1);
return 0;
}
}
signed main()
{ return OMA::main(); }
然后发现这份代码在本机编译会CE，因为用了(unordered_map) ，
以下内容摘自oi-wiki，
在 C++11 之前，无序关联式容器属于 C++ 的 TR1 扩展。所以，如果编译器不支持 C++11，在使用时需要在头文件的名称中加入 tr1/ 前缀，并且使用 std::tr1 命名空间。如 #include <unordered_map> 需要改成 #include <tr1/unordered_map>；std::unordered_map 需要改为 std::tr1::unordered_map（如果使用 using namespace std;，则为 tr1::unordered_map）。
但其实直接在终端里开c++11就可以了
(next_;permutation) 可以氵20pts，然而我不会拼 (permutation) biss。
正解：
是个dp，考虑排列p中的每个数怎样才能被移动到该到的地方。 这显然是一些相邻的交换的顺序关系，即形如“q中i在i+1前 (or) 后”的限制。 问题转化为一个大小为n-1的排列，某些地方限定了相邻两数的大小关系，求方案数。 直接简单DP即可，f[i][j]表示前i个数，第i个数在前i个数中是第j小的。前缀和优化。
(O(n^2))
同样是暴力，有的人a了，有的人wa了。
正解：
暴力
好吧，其实应该算是二分答案，枚举x，计算当前的质量，二分最大值，上界为当前的质量和，判断当前最大值为 (mid) 时所分的背包数是否满足 (le k)， 同时注意，若当前的质量中有一个大于 (mid) ，那显然，当前 (mid) 肯定不满足条件，直接break即可。
然后发现，这个T了，只有40pts，考虑如何去优化。
题解说不难发现，二分前，先判断一下是否比当前答案要优，不是直接conTinue，然后就A了。
至于题解里提到的，随机枚举顺序，好像并没有什么大的作用，或者说，我写假了？？？QAQ
#include<cstdio>
#include<climits>
#include<algorithm>
#define MAX 10010
#define re register
#define INF INT_MAX
using std::random_shuffle;
namespace OMA
{
inlinE int read()
{
int s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
return s*w;
}
int sum[MAX],ans=INF;
int n,p,k,a[MAX],b[MAX],x[MAX];
inline bool check(int now)
{
int res = 0,cnt = 1;
for(rE int i=1; i<=n; i++)
{
if(b[i]>now)
{ return false; }
if(res+b[i]>now)
{ res = 0,cnt++; }
res += b[i];
}
return cnt<=k;
}
inlinE int min(int a,int b)
{ return a<b?a:b; }
signed main()
{
n = read(),p = read(),k = read();
for(rE int i=1; i<=n; i++)
{ a[i] = read(); }
for(rE int i=0; i<=p-1; i++)
{ x[i+1] = i; }
random_shuffle(x+1,x+1+p);
for(rE int i=1; i<=p; i++)
{
int res,l = 0,r = 0;
for(rE int j=1; j<=n; j++)
{ r += (b[j] = (a[j]+x[i])%p); }
if(!check(ans))
{ conTinue ; }
while(l<=r)
{
int mid = (l+r)>>1;
if(check(mid))
{ r = mid-1,res = mid; }
else
{ l = mid+1; }
}
//printf("res=%dn",res);
ans = min(ans,res);
}
printf("%dn",ans);
return 0;
}
}
signed main()
{ return OMA::main(); }
反思总结：
一些STL的东西还是要会的，骗分或者打正解的时候可能会用到，不能不会，比如 (next_premutation) 。
不能瞧不起暴力，但也不能直接硬怼暴力，万一加个减枝就过了呢。
注意心态问题，不能自暴自弃。
以上是大佬教程为你收集整理的noip30全部内容，希望文章能够帮你解决noip30所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。