CFR626

CFR626 div1

CF1322A Unusual Competitions

请先思考后再展开

选的区间肯定不重,只需操作开始<0到终于=0的区间(理解的话,可以考虑折线图,x轴下方的部分一定能翻转)

code

CF1322B Present

请先思考后再展开

我写复杂了,花40min才过,直接gg

要想好写,除了显然的枚举每个位外,还要注意到如果这一位之和为1而后面进位了,直接算两次没有影响

于是就能单独考虑这一位之和为1、后面进位两种情况,后者2-point即可,这样复杂度也比上面少个log

upd:好像还是复杂了……更简单的思路,直接判两次:$x+y \in [2^t,2^{t+1}) \cup [2^{t+1}+2^t,2^{t+1}+2^{t+1}) $

CF1322C Instant Noodles

请先思考后再展开

众所周知gcd里面的集合,相当于是个加法线性空间之类的东西(0必定在里面,然后可以任意加减法)

那么右边中,能到达这里的左节点集合相同的,这样组成的东西一定是该线性空间的一个基(注意要 删孤立点)

hash判断集合相同即可,$O(n+m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//随机数
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rd(ll l,ll r){return l+rng()%(r-l+1);}
ll c[N],val[N],val2[N];map<ll,ll> hh;
void main()
{
fo(T,1,qread())
{
int n=qread(),m=qread();hh.clear();
fo(i,1,n) c[i]=qread(),val[i]=rd(1,1e17),val2[i]=0;
fo(i,1,m){ int x=qread(),y=qread();val2[y]^=val[x]; }
fo(i,1,n) if(val2[i]>0) hh[val2[i]]+=c[i];
ll ans=0;for(auto in:hh) ans=gcd(ans,in.SE);write2(ans);
}
}

CF1322D Reality Show

题意:n个数,选第i个数的代价为si,要求选出一个可空的不递增子序列,每选一个数li就加入舞台并获得$c_{li}$的收益,然后只要有重复的li就不断执行:合并两个li成一个li+1,并额外获得$c_{此时这个数=li+1}$的收益,最大化收益,$l_i \le m \le 2e3,n \le 2e3,s_i,|c_i| \le 5e3$

请先思考后再展开

首先进位向上选递减会很蛋疼,所以应该翻转序列,将数字i看做$2^i$求和,于是当序列末尾是t时只关心$当前的和=k*2^t+(<2^t)$的k,而$ans=\sum c_i*k_i$,接下来就是常规操作了

$dp_{i,l_i,k+1}=\max dp_{i-1,l_i,k}+C_{l_i}-s_i;dp_{i,j+1, \lfloor k/2 \rfloor }=\max dp_{i,j,k}+\lfloor k/2 \rfloor C_{j+1}$

前面那个就改一行,后面的根据$\sum_i \frac{n}{2^i}=O(n)$,可知总复杂度为$O(n(n+m))$

1
2
3
4
5
6
7
int n=qread(),m=qread();fd(i,n,1) a[i]=qread();fd(i,n,1) s[i]=qread();fo(i,1,n+m) c[i]=qread();
mem(dp,-0x3f);fo(num,1,n+m) dp[num][0]=0;
fo(i,1,n)
{
fd(k,n,0) chmax( dp[a[i]][k+1],dp[a[i]][k]+c[a[i]]-s[i] );
fo(num,a[i],n+m) fo(k,0, num<=a[i]+12?n/bin(num-a[i]):0 ) chmax( dp[num+1][k/2],dp[num][k]+(k/2)*c[num+1] );
}int ans=0;fo(j,0,n+m) chmax(ans,dp[j][0]);write(ans);

CF1322E Median Mountain Range

myhxyx

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