noip72
脚本宝典收集整理的这篇文章主要介绍了noip72，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
T1
考场想法：一眼sb状压dp，然而dp能力过弱，于是直接 (next_PErmutation) 了，再看了看，发现最后答案不是 (max{a_{i}}) ，就是 (max{a_{i}}+1) ，算代价的话， (b) 的代价是不变的，就是 (sum_{i=1}^{n-1}2^{i-1}-1) ，然而还是不知道如何压，于是40pts跑路了。
正解：
就是状压dp...
40pts： (next_permutatoin) 即可。
80pts：
考虑状压dp，设 (f_{i,j}) 表示当前所选集合 (i) ，所求出集合能搞出来 (a) 的最大值为 (j) 的方案数， (g_{i,j}) 表示当前状态所有方案的总代价。
转移的话，去枚举当前集合里没有加进来的 (a_{j}) ，然后去枚举当前集合能凑出来的最大值 (k)，是的，直接枚举即可，按照题目说的过程去模拟即可，即如果新加进来的 (a_{i}==k) ，那么就由 (f_{i,k}) 转移到 (f_{i|(1<<j-1),k+1}) ,否则转移到 (f_{i,max(a_{j},k)}) 即可。
这样的话能拿到 (a_{i}le n) 的那档分。
100pts：
发现80pts的状态定义属实冗余，考虑换一个。
发现合并的时候， (a) 最多只会+1。
所以对于集合 (S) ，就满足 (max_{iin S}{a_{i}}le ale max_{iin S}{a_{i}}+|S|-1)
所以只需要记录 (a) 相对于 (max_{iin S}{a_{i}}) 增加了多少即可。
然而事实上，第二维只用0/1即可。
Code
#include<cstdio>
#include<cctype>
#include<algorIThm>
#define re register
#define MAX 4000003
#define int long long
#define scanf oma=scanf
using std::next_permutation;
const int N = 20;
const int mod = 1e9+7;
int oma;
namespace some
{
struct stream
{
template<typename type>inline stream &operator >>(type &s)
{
bool w=0; s=0; char ch=getchar();
while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
return s=w?-s:s,*this;
}
}cin;
int n,mul,a[N];
//int biao[MAX][20],cnt,id[MAX],tot;
#define debug(s) debug((char*)s)
auto debug = [](char* s) { PRintf("%sn",s); };
auto max = [](int a,int b) -> int { return a>b?a:b; };
}using namespace some;
namespace simple
{
int p[N];
int xam,cost;
auto solve = []() -> void
{
for(re int i=1; i<=n; i++)
{ p[i] = i; }
int pa,pb,pc;
do
{
pa = a[p[1]],pb = pc = 0/*,++cnt*/;
for(re int i=2; i<=n; i++)
{
if(pa!=a[p[i]])
{ pa = max(pa,a[p[i]]); }
else
{ pa++; }
pc += (mul*pa%mod+pb)%mod,pb = 2*pb+1;
}
//for(re int i=1; i<=n; i++) { biao[cnt][i] = p[i]; /*printf("%d ",p[i]);*/ }
//printf("n%d %dn",pa,xam);
if(pa>xam)
{
xam = pa,cost = pc;
//id[tot = 1] = cnt;
}
else if(pa==xam)
{ /*id[++tot] = cnt,*/cost = (cost+pc)%mod; }
}while(next_permutation(p+1,p+1+n));
//printf("%dn",xam);
/*for(re int i=1; i<=tot; i++)
{
for(re int j=1; j<=n; j++)
{ printf("%d ",biao[id[i]][j]); }
printf("n");
}*/
printf("%lld %lldn",xam,cost);
};
};
namespace suBTask
{
int xam,add;
int f[1<<N][N],g[1<<N][N];
auto task = []() -> void
{
xam = a[n];
for(re int i=1; i<=n-1; i++)
{ xam = max(a[i],xam),(add += (1<<i-1)-1) %= mod; }
//printf("%lldn",add);
int sta = (1<<n)-1;
for(re int i=1; i<=n; i++)
{ f[1<<(i-1)][a[i]] = 1; }
for(re int i=1; i<sta; i++)
{
for(re int j=1; j<=n; j++)
{
if(!((i>>j-1)&1))
{
for(re int k=1; k<=xam+1; k++)
{
if(k==a[j])
{
(f[i|(1<<j-1)][k+1] += f[i][k]) %= mod;
(g[i|(1<<j-1)][k+1] += (g[i][k]+mul*(k+1)%mod*f[i][k]%mod)%mod) %= mod;
}
else
{
(f[i|(1<<j-1)][max(a[j],k)] += f[i][k]) %= mod;
(g[i|(1<<j-1)][max(a[j],k)] += (g[i][k]+mul*max(a[j],k)%mod*f[i][k]%mod)%mod) %= mod;
}
}
}
}
}
if(f[sta][xam+1])
{
printf("1: cnt=%lld mul=%lldn",f[sta][xam+1],g[sta][xam+1]);
printf("%lld %lldn",xam+1,((g[sta][xam+1]+add*f[sta][xam+1]%mod)%mod)%mod);
}
else
{
printf("2: cnt=%lld mul=%lldn",f[sta][xam],g[sta][xam]);
printf("%lld %lldn",xam,((g[sta][xam]+add*f[sta][xam]%mod)%mod)%mod);
}
};
};
namespace right
{
int ans,add,xam[1<<N];
int f[1<<N][2],g[1<<N][2];
auto solve = []() -> void
{
ans = a[n];
for(re int i=1; i<n; i++)
{ ans = max(ans,a[i]); (add += (1<<i-1)-1) %= mod; }
int sta = (1<<n)-1;
for(re int i=1; i<=n; i++)
{ f[1<<(i-1)][0] = 1; }
for(re int i=1; i<=sta; i++)
{
for(re int j=1; j<=n; j++)
{ if((i>>j-1)&1){ xam[i] = max(xam[i],a[j]); } }
}
for(re int i=1,w; i<sta; i++)
{
//printf("sta=%lld xam=%lldn",i,xam);
for(re int k=0; k<=1; k++)
{
if(!f[i][k])
{ continue ; }
for(re int j=1; j<=n; j++)
{
if(!((i>>j-1)&1))
{
w = k+xam[i]==a[j]?a[j]+1:max(a[j],k+xam[i]);
(f[i|(1<<j-1)][w-xam[i|(1<<j-1)]] += f[i][k]) %= mod;
(g[i|(1<<j-1)][w-xam[i|(1<<j-1)]] += (g[i][k]+mul*w%mod*f[i][k]%mod)%mod) %= mod;
}
}
}
}
if(f[sta][1])
{
//printf("1: cnt=%lld mul=%lldn",f[sta][1],g[sta][1]);
printf("%lld %lldn",ans+1,(g[sta][1]+add*f[sta][1]%mod)%mod);
}
else
{
//printf("2: cnt=%lld mul=%lldn",f[sta][0],g[sta][0]);
printf("%lld %lldn",ans,(g[sta][0]+add*f[sta][0]%mod)%mod);
}
};
};
namespace OMA
{
auto main = []() -> signed
{
//freopen("my.out","w",stdout);
freopen("repair.in","r",stdin); freopen("repair.out","w",stdout);
cin >> n >> mul;
for(re int i=1; i<=n; i++)
{ cin >> a[i]; }
//if(n<=10) { simple::solve(); }
//else { subtask::task(); }
right::solve();
return 0;
};
}
signed main()
{ return OMA::main(); }
T2
考场想法： 参考noip71，这题目名应该没有骗我，于是开场先写这道，发现只会 (O(nqLOG v)) 于是死了，准备40pts跑路，发现部分分可做，于是又去写了 (w,hle 2000) 的点，然后想写光速幂，不会，试图自己造出光速幂，想到根号处理后，发现不会了，于是爬了。
有59pts，考后再交了一遍，就有71pts，再交就47pts....
正解：
T3
考场想法：上来先冲二分，很快就冲出来了，然而假了，大样例跑的飞快，就是不对。于是放弃二分，短暂沉思之后，糊了个hash暴力匹配，再次短暂的沉思，想了kmp，然而忘记了，又想了想，kmp每次处理是 (O(len)) ，不如我直接hash暴力匹配+玄学剪枝。再次沉思，想写个ac自动机，然而不知道如何用ac自动机写这道题，于是再写了俩子任务跑路了。
因为数据过氵，所以拿了95pts。
那5pts是因为 (n=10) 的点，开的记录数组初始值是0，这样如果两个串匹配答案是0的话，下一次还会计算，所以死了，赛后 (memset) 成-1就过了。
hash暴力匹配+玄学剪枝就可以草过去。
当然你也可以选择分块草过去
正解：
就是ac自动机，但不会。
所以粘一下
T4
考场想法：不会，只有搜。
10pts。
赛后输出1有45pts....
正解：
脚本宝典总结
以上是脚本宝典为你收集整理的noip72全部内容，希望文章能够帮你解决noip72所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
- clion结合vcpkg以及GTest的使用 2022-07-07
- EGF 2022-06-06
- ExtJS 布局-Column布局（Column layout） 2022-06-05
- 颜色之ARGB与RGB、RGBA的区别与介绍 2022-04-15
- rgba中的a是什么意思 CSS之RGBA颜色指南 2022-04-15
- rootfs -根文件系统制作 2022-07-07
- 网页简单布局之结构与表现原则分享 2022-04-15
- 小项目中怎么防止Vue的闪现画面效果 2022-04-15
- 隐藏 Web 中的元素方法及优缺点教程详解 2022-04-15
- 告别硬编码让你的前端表格自动计算的实例代码 2022-04-15