20200526模拟-rose

rose的场

rose这个逼,题面都要发狗粮,差评

赛况大概是,xld会A、B,挂成135,我和pb会A,lhy会C


并没有把所有题看一遍,而是直接看A,想了1h发现快会做了,那当然是继续(预计比赛难度很大,而会做了某道题,那大概率这题不会是最难的,好像也不难写的样子

大概1.5h的时候确认了没毛病,开始写,3h的时候才过了小拍

3.3h的时候大的拍挂了,然后一路调试,剩下20min的时候过了拍,终于能开始测速

然后发现只有p=2的时候是3.8s,p在$n^{1/3}$时则不到1s,故调了调参(m,当时开了150,改回60),最后两者都压到1.1s

于是4h就干了一题……这是要被送走的节奏啊


不限时做题后,变成100+70+100

NOIAC439 bitset

题意:长度为n的数组,初始都是0,始终自动满足$a_{ij}=a_i \oplus a_j$,q次操作一个素数p,$a_j=1 \oplus a_j$,然后输出此时1的个数,$n,q \le 2e5$(我网站上有离线版)

请先思考后再展开

赛时日志:下列数值都是大概的

可以看做只有$\mu(i) \ne 0$的数,每个数带权,权值就是代表了多少个原本的数,n会大大减少,下面进一步思考

定义大因子为$>n^{1/2}$,最多出现一次
不包含大因子,且$\mu \ne 0$ 的状态数个数为29999
对于每个状态,记录0/1两维表示状态内当前分别有多少个是0、是1(每个数把自己大因子取出来,挂在相应状态里面)

感觉不太行,考虑咋减少点状态

定义大因子为$>n^{1/3}$,最多出现两次
不包含大因子,且$\mu \ne 0$ 的状态数个数为3230
对于每个状态,记录0/1两维表示状态内当前分别有多少个是0、是1(每个数把自己大因子取出来,挂在相应状态里面)

如果反转大质数,枚举n/p内状态数(允许一个大因子,2029),对每个,查表可知从哪个变成哪个
如果反转小质数,枚举倍数的那些状态(1210),修改即可
回答答案是$O(1)$的,我校老爷机开O2的实际速度是1.1s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
bool nop[N];int prn,prm[N],mxp[N];
int V[N][2];bool current[N];
bool tg[N];//无大因子的状态,当前值
vc<int> up[N];
vc<pii> upd[N];
int go[N];
void main()
{
int n=qread(),q=qread(),m=0;while((m+1)*(m+1)*(m+1)<=n) m++;
fo(i,2,n) if(!nop[i]){ prm[++prn]=i,mxp[i]=i;for(int j=i+i;j<=n;j+=i) nop[j]=1,chmax(mxp[j],i); }
fo(i,1,prn)
{
int pp=prm[i];map<int,int> mp;set<int> s;
for(int x=pp;x<=n;x+=pp)
{
int now=x,val=1;bool gg=0;
while(now>1)
{
int d=mxp[now];
int cc=0;while(now%d==0) now/=d,cc++;
if(cc&1) val*=d;if(d==pp and cc>1) gg=1;
}//去除平方因子
if(!gg) mp[val/pp]++;
while(mxp[val]>m) val/=mxp[val];
go[x]=val;if(!gg) s.insert(val);
}
for(auto in:s) up[pp].PB(in);
for(auto in:mp) upd[pp].PB(in);
}
int ans=0;go[1]=1;fo(x,1,n) V[go[x]][0]++;//初始化答案
while(q--)
{
int p=qread();
if(p<=m) for(auto y:up[p]) ans+=V[y][0]-V[y][1],swap(V[y][0],V[y][1]),tg[y]^=1;
else for(auto in:upd[p])
{
int x=in.FR,v=in.SE,s,p2=mxp[x];
if(p2<=m) s=tg[x]^current[p]; else s=tg[x/p2]^current[p]^current[p2],x/=p2;
ans+=(s?-v:v);V[x][s]-=v,V[x][s^1]+=v;
}
write2(ans);current[p]^=1;
}
}

感觉正解好妙啊,记录a的前缀和,发现更新一个位置i的时候,只需要用到$\lfloor i/j \rfloor$,整体来说就是根号个有用的位置,可以始终维护前缀和,那么每次把以前的删掉,把新的加回来,$O(2m \sqrt n)$

1
2
3
4
5
6
7
8
9
10
11
12
int n=qread(),q=qread();for(int i=1,j;i<=n;i=j+1) j=n/(n/i),num.PB(n/i);reverse(all(num));
while(q--)
{
int p=qread();
for(auto i:num)
{
g[i]=f[i];
g[i]-=(tg[p]?i/p-f[i/p]:f[i/p]);
g[i]+=(tg[p]^1?i/p-g[i/p]:g[i/p]);
}
for(auto i:num) f[i]=g[i];tg[p]^=1;write2(f[n]);
}

AGC021F Trinity

请先思考后再展开

第一反应是个70pt的做法(本以为是$O(n*m^2)$能过,然后发现我思考的时候其实旋转了):

考虑确定了每行第一次出现位置构成的长为n的序列后,对答案的贡献(看作该序列的权值)如何计算

发现就是枚举$i=1 \sim m$,在序列中选一个区间,要求包含所有值为i的数,且区间端点不超过i,这样的方案数的乘积(确定序列下,不同i之间独立)

看作是m种颜色的球的带权序列,递增地一次插入一种颜色的所有球,这样是不重不漏的(经典模型),容易得到以下简单dp

1
2
3
4
5
6
7
8
9
10
11
int dp[N][N];int F(int n,int m){ return C(n+m-1,m-1); }//n分成m个可空子集
void main()
{
int m=qread(),n=qread();dp[0][0]=1;PRE();
fo(i,1,n) fo(j,0,m) if(dp[i-1][j])
{
ll dd=dp[i-1][j];add(dp[i][j], dd*(C(j,2)+j+1)%MOD );
fo(pos,1,j+1) add(dp[i][j+1], dd*pos*(1+j-pos+1)%MOD );
fo(p1,1,j+1) fo(p2,p1,j+1) fo(ad,0,m-j-2) add(dp[i][j+ad+2], p1*(1+j-p2+1)*dd%MOD*F(ad,p2-p1+1)%MOD );
} int ans=0;fo(j,0,m) add(ans, dp[n][j]*C(m,j)%MOD );write2(ans);
}//只是用于验证正确性

简单优化后,应该就能变成$O(m*n^2)$,因为得知被正解吊起来打,好像没啥优化空间,就不实现了


看了看题解,发现标算就是进一步优化上面的东西……菜了菜了

我们枚举具体的区间会非常麻烦,因为同时涉及之前的和现在加入的

此时非常妙的一波操作是,考虑区间的开区间形式,这样就只和之前的有关了

于是就变成了$ad>0,dp_{i-1,j} * C_{j+ad+2}^{ad+2} \to dp_{i,j+ad}$,选出来的ad个就是新加入的行,另外两个就是开区间

NTT优化,$O(nlogn)$,code

C

题意:你有$n$个物品,每个物品有一个$[1,K]$之间的颜色$c_i$。同时每个物品也有一个权值$v_i$,你希望选出$x$个物品,满足若颜色$i$中存在物品被选中,那么颜色$i$至少存在$2$个物品被选中,且最大化总权值和。对于$x=1\cdots n$,均求出上述问题的答案,特别的,如果不存在取法,则输出$-1$

请先思考后再展开

将每种颜色内物品降序排序并前缀和,得到若干个凸函数,要做$h_{i+j}=\max f_i+g_j$

根据套路集锦,如果没有选两个这样的限制,可以线性合并

手玩一下样例,发现写成每次+1/2/3好像很有道理的样子(没看懂见代码),拍一拍发现可以通过k=2

多个k的话,分治就好了,只要能保证深度为log,每次是n,总复杂度为$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vc<ll> merg(vc<ll> &f,vc<ll> &g)
{
int n=sz(f)-1,m=sz(g)-1;vc<pll> h(n+m+1,{-1,0});h[0]={0,0};
fo(s,0,n+m) if(h[s].FR>=0)
{
int x=h[s].SE,y=s-x;assert(f[x]>=0 and g[y]>=0);
fo(ad,x==0?2:1,3) if(x+ad<=n and f[x+ad]>=0) chmax(h[s+ad], {h[s].FR+f[x+ad]-f[x],x+ad} );
fo(ad,y==0?2:1,3) if(y+ad<=m and g[y+ad]>=0) chmax(h[s+ad], {h[s].FR+g[y+ad]-g[y],x} );
}
vc<ll> ret(n+m+1);fo(s,0,n+m) ret[s]=h[s].FR;return ret;
}
vc<ll> f[N],h[N];
void solve(int l,int r)
{
if(l==r) return;int mid=(l+r)/2;
solve(l,mid),solve(mid+1,r);h[l]=merg(h[l],h[mid+1]);
}
void main()
{
int n=qread(),k=qread();fo(i,1,n){ int c=qread(),v=qread();f[c].PB(v); }
fo(c,1,k)
{
sort(all(f[c])),reverse(all(f[c]));int m=sz(f[c]);h[c].resize(m+1);
h[c][1]=-1;h[c][2]=f[c][0]+f[c][1];fo(i,3,m) h[c][i]=h[c][i-1]+f[c][i-1];
} solve(1,k);fo(i,1,n) write2(h[1][i]);
}

rose的标算是神仙贪心/模拟费用流,代码好长,不想看了

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/acc26bc8.html
转载请注明出处,谢谢!