挺难的一场。
1.CF1497D Genius
题意
内存限制： 32 M B 32MB 32MB。
n n n 个问题从 1 1 1 到 n n n 编号，第 i i i 个问题给出
c i = 2 i , t a g i , s i c_i=2^i,tag_i,s_i ci=2i,tagi,si。
解决问题 i i i 后，能够解决问题 j j j条件是： I Q < ∣ c i − c j ∣ IQ<|c_i-c_j| IQ<∣ci−cj∣ 且 t a g i ≠ t a g j tag_i\neq tag_j tagi=tagj。
在解决完 i i i 后解决了 j j j，你的 I Q IQ IQ 变为 I Q = ∣ c i − c j ∣ IQ=|c_i-c_j| IQ=∣ci−cj∣，同时获得 ∣ s i − s j ∣ |s_i-s_j| ∣si−sj∣ 分。一开始 I Q = 0 IQ=0 IQ=0，且问题解决的次数和顺序不受限制。
求最高可获得的分数。
t t t 组测试数据， 1 ≤ t ≤ 100 1\le t\le 100 1≤t≤100， 1 ≤ n ≤ 5000 1\le n\le 5000 1≤n≤5000， ∑ n ≤ 5000 \sum n\le 5000 ∑n≤5000， s i ≤ 1 0 9 s_i\le 10^9 si≤109。
思路
我们想要建出一个完全图，二元边权为 ( ∣ c i − c j ∣ , ∣ s i − s j ∣ ) (|c_i-c_j|,|s_i-s_j|) (∣ci−cj∣,∣si−sj∣)，满足题面要求而且分数最大，边和点经过次数不受限制。然后考虑一个 f i f_i fi 表示以 i i i 点为终点的最大分数。因为 I Q IQ IQ 是严格单调递增的，所以边权相同的边至多只会经过一次。
但是不论从空间还是时间，我们都不能开下这个图。于是考虑从那个单调性质入手：
假若从 k → j → i k\to j\to i k→j→i 且 j < i j<i j<i，需要满足 ∣ c k − c j ∣ < ∣ c i − c j ∣ |c_k-c_j|<|c_i-c_j| ∣ck−cj∣<∣ci−cj∣，不难发现 ∀ k < i \forall k<i ∀k<i 均满足上述不等式。
于是考虑从小到大钦定当前最大的 i i i，枚举中转点 j j j；相当于每次加上 1 ↔ i , 2 ↔ i , . . . i − 1 ↔ i 1\leftrightarrow i,2\leftrightarrow i,...i-1\leftrightarrow i 1↔i,2↔i,...i−1↔i 的边。对于边 j ↔ i j\leftrightarrow i j↔i， j j j 有前继状态 k k k，根据上面的结论 k → j → i k\to j\to i k→j→i 的转移必然合法。
if(tag[i]==tag[j])continue;
ll tem=f[i];
f[i]=max(f[i],f[j]+abs(s[i]-s[j]));
f[j]=max(f[j],tem+abs(s[i]-s[j]));
我们需要从 i − 1 i-1 i−1 到 1 1 1 枚举 j j j。为什么不从小到大呢？反证一下，考虑一个 j a < j b j_a<j_b ja<jb，先枚举 j a j_a ja 可能会产生 j a → i j_a\to i ja→i 的转移， f i f_i fi 被更新，此时再枚举 j b j_b jb，就可能出现 j a → i → j b j_a\to i\to j_b ja→i→jb 的转移，由于 c i − c j a > c i − c j b c_i-c_{j_a}>c_i-c_{j_b} ci−cja>ci−cjb，因此这个转移是不合法的。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5003;
ll Q,n,tag[N],s[N];
ll f[N];
int main()
{
freopen("sol.in","r",stdin);
freopen("sol.out","w",stdout);
scanf("%lld",&Q);
while(Q--)
{
scanf("%lld",&n);
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
scanf("%lld",&tag[i]);
for(int i=1;i<=n;i++)
scanf("%lld",&s[i]);
for(int i=1;i<=n;i++)
{
for(int j=i-1;j>=1;j--)
{
if(tag[i]==tag[j])continue;
ll tem=f[i];
f[i]=max(f[i],f[j]+abs(s[i]-s[j]));
f[j]=max(f[j],tem+abs(s[i]-s[j]));
}
}
ll ret=0;
for(int i=1;i<=n;i++)
ret=max(ret,f[i]);
printf("%lld\n",ret);
}
return 0;
}
2.金币
题意
t ≤ 100 t\le 100 t≤100， 2 ≤ n , k ≤ 1 0 12 2\le n,k\le 10^{12} 2≤n,k≤1012。
思路
从第 1 1 1 个开始，每隔 k k k 个删一个，一次操作下来 n ← n − ⌈ n k ⌉ n\leftarrow n-\left\lceil \frac{n}{k} \right\rceil n←n−⌈kn⌉。
设 F ( n , k ) F(n,k) F(n,k) 表示按照题目要求做，删到只剩下一个的操作轮数。那么我们想要找一个最小的 z z z，使得 F ( z , k ) = F ( n , k ) F(z,k)=F(n,k) F(z,k)=F(n,k)。
为什么是这样呢？我们手玩一下：
n = 8 , k = 3 n=8,k=3 n=8,k=3
1 2 3 4 5 6 7 8
2 3 5 6 8
3 5 8
5 8
8
n = 9 , k = 3 n=9,k=3 n=9,k=3
1 2 3 4 5 6 7 8 9
2 3 5 6 8 9
3 5 8 9
5 8
8
在第二种情况，第 3 3 3 步时 9 9 9 被删去，前面的 8 8 8 留下了。而两种情况的 F ( n , k ) F(n,k) F(n,k) 是相同的，也即我们知道了步数 F ( n , k ) F(n,k) F(n,k)，找一个最小的 z z z，从 1 1 1 个开始还原 F ( z , k ) = F ( n , k ) F(z,k)=F(n,k) F(z,k)=F(n,k) 步回去，能还原出完整的 1 ∼ z 1\sim z 1∼z，的最小的 z z z。
我们考虑快速地计算 F ( n , k ) F(n,k) F(n,k) 和实现还原过程。
每一轮都会使 n ← n − ⌈ n k ⌉ n\leftarrow n-\left\lceil \frac{n}{k} \right\rceil n←n−⌈kn⌉，虽然 n n n 的值一直变化，但是也会存在一段变化使得每轮减少的数 ⌈ n k ⌉ \left\lceil \frac{n}{k} \right\rceil ⌈kn⌉ 不变的情况，可以在这里优化：
设 b = ⌈ n k ⌉ b=\left\lceil \frac{n}{k} \right\rceil b=⌈kn⌉，我们求 ⌈ n − x b k ⌉ = ⌈ n k ⌉ = b \left\lceil \frac{n-xb}{k} \right\rceil=\left\lceil \frac{n}{k} \right\rceil=b ⌈kn−xb⌉=⌈kn⌉=b 的最大的 x x x，在接下来的 x x x 轮中减少的数的个数均为 b b b。根据 ⌈ n − x b k ⌉ = ⌊ n − x b + k − 1 k ⌋ \left\lceil \frac{n-xb}{k} \right\rceil=\left\lfloor \frac{n-xb+k-1}{k} \right\rfloor ⌈kn−xb⌉=⌊kn−xb+k−1⌋，得到 x = ⌊ n − b k + k − 1 b ⌋ x=\left\lfloor \frac{n-bk+k-1}{b} \right\rfloor x=⌊bn−bk+k−1⌋。这个步数 x x x 要记得 + 1 +1 +1，使得减少个数减 1 1 1。
ll cur=n,turn=0;
while(cur>0)
{
ll b=Ceil(cur,k);
ll x=(cur-b*k+k-1)/b;
x++;
//最大的x使得ceil(n-xb,k)=b，再多减一个结果为b-1
turn+=x;
cur-=b*x;
}
turn--;//这里计算的turn把最后那1个也删掉了
然后还原回去，还原过程中当前有 z z z 个数，加数时每隔 k − 1 k-1 k−1 个数就加回一个数，于是 z ← z + ⌈ z k − 1 ⌉ z\leftarrow z+\left\lceil \frac{z}{k-1} \right\rceil z←z+⌈k−1z⌉。类似上面的推导过程还原即可。计算 c = ⌈ z k − 1 ⌉ = ⌈ z + y c k − 1 ⌉ c=\left\lceil \frac{z}{k-1} \right\rceil=\left\lceil \frac{z+yc}{k-1} \right\rceil c=⌈k−1z⌉=⌈k−1z+yc⌉ 的 y y y。
while(turn)
{
ll c=Ceil(ans,k-1);
ll y=((k-1)*c-ans)/c;
y++;
// cout<<c<<" "<<y<<endl;
if(turn>=y)
{
turn-=y;
ans+=y*c;
}
else
{
ans+=turn*c;
turn-=turn;
}
}
时间复杂度怎么保证？一个神秘的结论：本质不同的 ⌈ n k ⌉ \left\lceil \frac{n}{k} \right\rceil ⌈kn⌉ 在 n \sqrt{n} n 左右， ⌈ z k − 1 ⌉ \left\lceil \frac{z}{k-1} \right\rceil ⌈k−1z⌉ 同理。证明见这篇博客。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll T;
ll Ceil(ll fz,ll fm)
{
return (fz+fm-1)/fm;
}
int main()
{
freopen("coin.in","r",stdin);
freopen("coin.out","w",stdout);
scanf("%lld",&T);
while(T--)
{
ll n,k;
scanf("%lld%lld",&n,&k);
ll cur=n,turn=0,ans=1;
while(cur>0)
{
ll b=Ceil(cur,k);
ll x=(cur-b*k+k-1)/b;
x++;
//最大的x使得ceil(n-xb,k)=b，再多减一个结果为b-1
turn+=x;
cur-=b*x;
}
// cout<<turn<<" "<<cur<<endl;
turn--;
while(turn)
{
ll c=Ceil(ans,k-1);
ll y=((k-1)*c-ans)/c;
y++;
// cout<<c<<" "<<y<<endl;
if(turn>=y)
{
turn-=y;
ans+=y*c;
}
else
{
ans+=turn*c;
turn-=turn;
}
}
printf("%lld\n",ans);
}
return 0;
}
3.洛谷 P11340 COI 2019 TENIS
题意
1 ≤ N , Q ≤ 1 0 5 1\le N,Q\le 10^5 1≤N,Q≤105。
思路
我们看到样例：
1 2 3 4
2 1 3 4
2 4 3 1
把在 3 3 3 个场地上，前面的点能够赢后面的点的所有关系建单向边：
我们发现这 4 4 4 个点，都可以成为必胜点——因为这些点的关系边拧成了一个 scc，比如对于 4 4 4，赢了 3 3 3 就能依靠 3 3 3 赢 1 , 2 1,2 1,2，从而赢掉所有人。
样例中进行了一次，把场地 3 3 3 的 1 , 2 1,2 1,2 排名调转的操作：
2 3 1 4
那么 3 3 3 个场地排名序列变成：
1 2 3 4
2 1 3 4
2 1 3 4
发现这个图，排名最靠前的 scc 只包含 1 , 2 1,2 1,2，即 3 3 3 永远赢不了 1 , 2 1,2 1,2。
这个排名最靠前的 scc，怎么转化呢？
在第 2 2 2 幅图，如果 3 3 3 想要赢 1 , 2 1,2 1,2，要往 1 1 1 或 2 2 2 连边。也即在 3 3 3 个场地中， 3 3 3 的最靠前排名要小于 1 , 2 1,2 1,2 的三个排名其一。
于是关联到一个结论：一个 scc 可以表示为，存在一个排名 p p p，该 scc 中选手的 3 3 3 个场地的名次，均 ≤ p \le p ≤p。我们要求最靠前的 scc，就是要找到一个最小的 p p p，此时满足所有必胜选手的 3 3 3 个排名均 ≤ p \le p ≤p。
为什么这样是对的？上两段解释了 3 3 3 要怎么样才能赢掉 1 , 2 1,2 1,2， 3 3 3 的最靠前排名要小于 1 , 2 1,2 1,2 的三个排名其一， 3 3 3 的排名 ≤ p \le p ≤p， p p p 就要往后移动，直到包含 3 3 3 的所有排名位置。
考虑维护每个选手 i i i 的 l i , r i l_i,r_i li,ri 表示 3 3 3 个场地中的最靠前的排名和最靠后的排名。把这个找 p p p 的过程具象化：
（其实就是找一个最小的 p p p，使得这个位置上均为选手排名的 r r r）
询问次数来到 Q ≤ 1 0 5 Q\le 10^5 Q≤105，考虑 O ( log n ) O(\log n) O(logn) 的查询，如果想二分的话单调性何在呢？
可以考虑在线段树上操作：考虑每个选手 i i i 的 l i , r i l_i,r_i li,ri，在 [ l i , r i ) [l_i,r_i) [li,ri) 上区间 + 1 +1 +1，特别的在 r i r_i ri 上不操作——这样满足全部都是结束点 r r r 的合法位置 p p p 处的和就为 0 0 0。我们线段树维护最小值和区间加操作，在线段树上二分 p p p：如果左区间存在最小值为 0 0 0 的就往左边搜，否则往右边搜。
更新就 O ( 1 ) O(1) O(1) 更新排名信息以及 O ( log n ) O(\log n) O(logn) 修改区间和。时间复杂度 O ( n log n + q log n ) O(n\log n+q\log n) O(nlogn+qlogn)。代码不会很难打，转化之后思路就很明显了。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const ll N=1e5+9;
ll n,Q;
ll a[4][N],rk[4][N];
ll l[N],r[N];
void findd(ll x)
{
l[x]=min({rk[1][x],rk[2][x],rk[3][x]});
r[x]=max({rk[1][x],rk[2][x],rk[3][x]});
}
struct SegT
{
struct node
{
ll mi,tag;
}T[N<<2];
void pushup(ll u)
{
T[u].mi=min(T[ls].mi,T[rs].mi);
}
void modi(ll u,ll tg)
{
T[u].mi+=tg;
T[u].tag+=tg;
}
void pushdown(ll u,ll l,ll r)
{
modi(ls,T[u].tag);
modi(rs,T[u].tag);
T[u].tag=0;
}
void modify(ll u,ll l,ll r,ll ql,ll qr,ll k)
{
if(qr<l||r<ql)return;
if(ql<=l&&r<=qr)
{
T[u].mi+=k;
T[u].tag+=k;
return;
}
pushdown(u,l,r);
ll mid=(l+r)>>1;
if(ql<=mid)modify(ls,l,mid,ql,qr,k);
if(qr>mid)modify(rs,mid+1,r,ql,qr,k);
pushup(u);
}
ll findpos(ll u,ll l,ll r)
{
if(l==r)return l;
pushdown(u,l,r);
ll mid=(l+r)>>1;
if(T[ls].mi==0)return findpos(ls,l,mid);
return findpos(rs,mid+1,r);
}
}A;
void add(ll x)
{
A.modify(1,1,n,l[x],n,1);
A.modify(1,1,n,r[x],n,-1);
}
void del(ll x)
{
A.modify(1,1,n,l[x],n,-1);
A.modify(1,1,n,r[x],n,1);
}
int main()
{
freopen("go.in","r",stdin);
freopen("go.out","w",stdout);
scanf("%lld%lld",&n,&Q);
for(int st=1;st<=3;st++)
{
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[st][i]);
rk[st][a[st][i]]=i;
}
}
for(int i=1;i<=n;i++)
{
findd(i);
add(i);
}
ll chap=0;
while(Q--)
{
ll op,x,u,v;
scanf("%lld%lld",&op,&x);
if(op==1)
{
if(l[x]<=A.findpos(1,1,n))puts("DA");
else puts("NE");
}
else
{
scanf("%lld%lld",&u,&v);
del(u);
del(v);
swap(rk[x][u],rk[x][v]);
a[x][rk[x][u]]=u,a[x][rk[x][v]]=v;
findd(u);
findd(v);
add(u);
add(v);
}
}
return 0;
}