noi2019模拟测试赛(四十七)
2024-08-27 06:43:46
noi2019模拟测试赛(四十七)
T1与运算(and)
题意:
给你一个序列\(a_i\),定义\(f_i=a_1\&a_2\&\cdots\&a_i\),求这个序列的所有排列的\(\Sigma_i f_i\)的最大值。
题解:
dp,记\(dp_i\)表示前面的数与和为\(i\)的最大值,转移要一个超集的东西,fwt搞一搞就行了。
#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define of(i,l,r) for(int i=l;i>=r;i--)
#define fe(i,u) for(int i=head[u];i;i=e[i].next)
#define el putchar('\n')
#define ta putchar(' ')
using namespace std;
typedef long long ll;
inline void open(const char *s)
{
#ifndef ONLINE_JUDGE
char str[20];
sprintf(str,"%s.in",s);
freopen(str,"r",stdin);
// sprintf(str,"%s.out",s);
// freopen(str,"w",stdout);
#endif
}
inline int rd()
{
static int x,f;
x=0;f=1;
char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return f>0?x:-x;
}
const int N=1<<20;
ll n,cnt[N],f[N];
inline void fwt(ll *a,int len)
{
for(int i=2;i<=len;i<<=1)
for(int j=0;j<len;j+=i)
for(int k=0;k<(i>>1);++k)a[j+k]+=a[j+k+(i>>1)];
}
int main()
{
n=rd();fo(i,1,n)++cnt[rd()];
fwt(cnt,N);
fo(i,1,N-1)for(int j=1;j<N;j<<=1)if(i&j)f[i]=max(f[i],f[i^j]+cnt[i]*j);
cout<<f[N-1]<<endl;
return 0;
}
T2 序列(sequence)
题意:
随机生成一个数列:
\(a_0=0\)
\(\forall i>0,a_i\)有\(p_i\)的概率等于\(a_{i-1}+1\),有\(1-p_i\)的概率等于\(0\)。
求\(\Sigma_{i=1}^na^2\)的期望。
题解:
签到推式子题。dp转移就是枚举最后一段连续+1的长度。式子大力差分后可以线性做。代码就不放了。
T3 平均值(average)
题意:
给你一个序列\(a_i\),求:
\[
\Sigma_{l=1}^n\Sigma_{r=l}^n\frac{ mex(a_l,a_l+1,\cdots,a_r)}{r-l+1}
\]
题解:
式子转成:
\[
\Sigma_{i=1}^{max}\Sigma_{l=1}^n\Sigma_{r=l}^n\frac{ [mex(a_l,a_l+1,\cdots,a_r)\ge i]}{r-l+1}
\]
然后就是对于每一个\(l\),求\(r\),贡献是倒数的前缀和。线段树2分+区间覆盖。然后这个区间覆盖要加一个函数,用技巧可以实现。
#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define of(i,l,r) for(int i=l;i>=r;i--)
#define fe(i,u) for(int i=head[u];i;i=e[i].next)
#define el putchar('\n')
#define ta putchar(' ')
using namespace std;
typedef long long ll;
typedef vector<int> vi;
inline void open(const char *s)
{
#ifndef ONLINE_JUDGE
char str[20];
sprintf(str,"%s.in",s);
freopen(str,"r",stdin);
// sprintf(str,"%s.out",s);
// freopen(str,"w",stdout);
#endif
}
namespace IO{
const int N=(1<<26)+10;
char buf[N],*H,*T;
inline char Get()
{
if(H==T)T=(H=buf)+fread(buf,1,N,stdin);
return H==T?-1:*H++;
}
inline int rd()
{
static int x,f;
x=0;f=1;
char ch=Get();
for(;ch<'0'||ch>'9';ch=Get())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=Get())x=x*10+ch-'0';
return f>0?x:-x;
}
}using IO::rd;
const int N=500010,Inf=1000000000,mod=998244353;
int n,m,inv[N],s[N],ss[N],rt;
vi vec[N];
inline int pls(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int mns(int a,int b){return a<b?a-b+mod:a-b;}
inline int mul(int a,int b){return (ll)a*b%mod;}
namespace Seg{
#define lson tr[o].ls,l,mid
#define rson tr[o].rs,mid+1,r
#define qlson lson,L,min(mid,R)
#define qrson rson,max(mid+1,L),R
struct tree{
int ls,rs,mn,sum,ps,tag;
tree(){ls=rs=mn=sum=tag=0;}
}tr[N<<1];int cnt=0;
inline void calc(int o,int d,int l,int r){tr[o].sum=mns(ss[d-l],ss[d-r-1]);tr[o].mn=tr[o].tag=d;}
inline void pushup(int o)
{
tr[o].sum=pls(tr[tr[o].ls].sum,tr[tr[o].rs].sum);
tr[o].mn=min(tr[tr[o].ls].mn,tr[tr[o].rs].mn);
}
inline void pushdown(int o,int l,int mid,int r)
{static int ls,rs;
if(!tr[o].tag)return;
ls=tr[o].ls,rs=tr[o].rs;
calc(ls,tr[o].tag,l,mid);
calc(rs,tr[o].tag,mid+1,r);
tr[o].tag=0;
}
void build(int &o,int l,int r)
{
o=++cnt;if(l==r)return tr[o].ps=s[n-l+1],void();
int mid=(l+r)>>1;build(lson);build(rson);
tr[o].ps=pls(tr[tr[o].ls].ps,tr[tr[o].rs].ps);
}
void modify(int o,int l,int r,int L,int R,int d)
{if(L>R)return;
if(l==L&&r==R)return calc(o,d,l,r);
int mid=(l+r)>>1;pushdown(o,l,mid,r);
if(L<=mid)modify(qlson,d);
if(R>mid)modify(qrson,d);
pushup(o);
}
int qsum(int o,int l,int r,int L,int R)
{if(L>R)return 0;
if(l==L&&r==R)return mns(tr[o].ps,tr[o].sum);
int mid=(l+r)>>1,res=0;pushdown(o,l,mid,r);
if(L<=mid)res=pls(res,qsum(qlson));
if(R>mid)res=pls(res,qsum(qrson));
return res;
}
int query(int o,int l,int r,int L,int R,int d)
{
if(l==r)return tr[o].mn<d?l:l-1;
int mid=(l+r)>>1;pushdown(o,l,mid,r);
if(l==L&&r==R){
if(tr[tr[o].rs].mn<d)return query(qrson,d);
return query(qlson,d);
}
int res=mid;
if(R>mid)res=query(qrson,d);
if(res>mid)return res;
if(L<=mid)res=query(qlson,d);
return res;
}
}
int main()
{open("c");
n=rd();inv[0]=inv[1]=1;
fo(i,1,n){
vec[rd()].push_back(i);
if(i-1)inv[i]=mns(0,mul(mod/i,inv[mod%i]));
}
int ans=0;m=n;
fo(i,1,n)s[i]=pls(s[i-1],inv[i]);
fo(i,1,n)ss[i]=pls(ss[i-1],s[i]);
Seg::build(rt,1,n);
fo(t,0,500000){
if(!vec[t].size())break;
int hh=0;
of(i,vec[t].size()-1,0){
if(++hh==1)m=min(m,vec[t][i]);
int x=Seg::query(rt,1,n,1,m,vec[t][i]);
int ql=i?vec[t][i-1]+1:1;
Seg::modify(rt,1,n,ql,min(m,x),vec[t][i]);
}
if(!hh)break;
ans=pls(ans,Seg::qsum(rt,1,n,1,m));
}
printf("%d\n",ans);
return 0;
}
最新文章
- windows2003 DHCP中批处理绑定IP与MAC
- Codeforces Round #344 (Div. 2)
- MySQL 5.6 my.cnf 参数说明
- Java Web目录
- 常用git 命令
- [Everyday Mathematics]20150105
- 转: Python 运算符与用法
- [Operationg System Labs] 我对 Linux0.00 中 boot.s的理解和注释
- 软件测试学习日志————round 0 An impressed error in my past projects
- jQuery+HTML5声音提示
- 【安装Python环境】之“安装 setuptools ”时出现的问题以及解决办法
- IAM
- mybatis 源码分析一
- 构造一个String类
- git 入门教程之忽略文件
- NOIp2018停课刷题记录
- 设计模式---对象创建模式之构建器模式(Builder)
- 苹果手机marquee显示文字不全,如何解决?
- jvisualvm连接远程应用终于成功,附踩大坑记录!!(一:jstatd方式)
- APP测试重点罗列