Preface
这周六紧张刺激的一日三赛,上午蓝桥杯,晚上ARC之后隔5min就是CF,可谓是手搓键盘到冒烟的一天了
这场其实打的感觉很没水准,B刚开始没想清楚很多边界条件挂了三发,45min左右才过
然后C的构造也不太会,随便写了个暴力也是挂挂挂,只好弃了去写D题了
结果发现D题好像是个不难的线段树优化DP的裸题,赶紧切了稳个排名
最后居然还能进前300我是没想到的,小小地上一波分
A - Copy and Paste Graph
题目看似复杂其实结构一下发现就是个很裸的最短路的说
不难发现如果一个点\(i\)到\(j\)的最短距离是\(dis_{i,j}\),那么它到\(j+n,j+2n\cdots\)的最短距离也是\(dis_{i,j}\)
那么我们只要对原来的\(n\times n\)的图用Floyd跑出最短路即可,然后询问的时候把点都搞到\(n\times n\)范围内即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105,INF=1e9;
int n,m,q,dis[N][N]; long long s,t;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,k; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) for (j=1;j<=n;++j)
if (scanf("%d",&dis[i][j]),!dis[i][j]) dis[i][j]=INF;
for (k=1;k<=n;++k) for (i=1;i<=n;++i) for (j=1;j<=n;++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
for (scanf("%d",&q),i=1;i<=q;++i)
{
scanf("%lld%lld",&s,&t); s=(s-1)%n+1; t=(t-1)%n+1;
printf("%d\n",dis[s][t]!=INF?dis[s][t]:-1);
}
return 0;
}
B - GCD Subtraction
我们先手玩一下这个过程,发现对于一对\(a,b\),设\(g=\gcd(a,b),a'=\frac{a}{g},b'=\frac{b}{g}\),则一次操作后变成了\((a'-1)g,(b'-1)g\)
不难发现外面的这个\(g\)对于答案没有任何影响,因此就转化成了求\(a'-1,b'-1\)的答案
然后我们考虑如果\(g>1\)的话直接暴力做次数也是\(O(\log n)\)级别的,因此可以直接搞,那么现在问题就是处理\(g=1\)的情况
很容易发现此时我们就是要快速计算出使得\(\gcd(a'-1-x,b'-1-x)\ne 1\)的最小的\(x\)
不难想到我们可以枚举某个质数\(p\),如果\(a'-1\equiv b'-1\pmod p\)的话那这个模数就是答案
但直接枚举复杂度是\(O(n)\)的,因此我们考虑如果上述式子成立,则\(p\)一定是\(|a'-b'|\)的某个因子,因此对于\(|a'-b'|\)用根号复杂度的时间枚举质因数即可
但是还要注意一个细节,当\(|a'-b'|=1\)时需要特判直接计算答案,因为此时直到一个数等于\(0\)为止两个数都一定互质
总复杂度大概是\(O(\log n\times \sqrt n)\)的,不过绝对跑不满
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=1000000,INF=1e12;
int a,b,pri[N+5],cnt,ans; bool vis[N+5];
inline void init(CI n)
{
for (RI i=2,j;i<=n;++i)
{
if (!vis[i]) pri[++cnt]=i;
for (j=1;j<=cnt&&i*pri[j]<=n;++j)
if (vis[i*pri[j]]=1,i%pri[j]==0) break;
}
}
inline int gcd(CI n,CI m)
{
return m?gcd(m,n%m):n;
}
inline void solve(int a,int b)
{
if (!a||!b) return; int g=gcd(a,b);
a/=g; --a; b/=g; --b; ++ans;
if (!a||!b) return; if (a==1&&b==1) return (void)(++ans);
if (gcd(a,b)!=1) return solve(a,b);
if (a>b) swap(a,b); int d=a%(b-a);
if (a+1==b) return (void)(ans+=a);
for (RI i=1;i<=cnt&&pri[i]*pri[i]<=b-a;++i)
if ((b-a)%pri[i]==0) d=min(d,a%pri[i]),d=min(d,a%((b-a)/pri[i]));
ans+=d; solve(a-d,b-d);
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
init(N); scanf("%lld%lld",&a,&b); solve(a,b);
return printf("%lld",ans),0;
}
C - Permutation Addition
号称构造题精通结果一筹莫展战俘闪总出列!
比赛的时候大概想到就是每次把\(a_i\)从小到大排序后然后加上\(\{n,n-1,\cdots ,1\}\)如果有解的话肯定是可以跑出答案的,但不能保证次数在\(10000\)以内,写了下试试果然挂了一些点
然后今天一看Editorial发现我就是个弱智,这种套路的构造感觉之前绝对见过类似的
首先考虑设\(sum=\sum_{i=1}^n a_i\),我们考虑每次做一次操作所有数的和\(sum'=sum+k\times \frac{n(n+1)}{2}\ (k\in N)\)
由于所有数要一样因此最后\(sum'\)一定是\(n\)的倍数,又由于\(2\times \frac{n(n+1)}{2}\)是\(n\)的倍数,因此若\(n\nmid sum\and n\nmid sum+\frac{n(n+1)}{2}\)则一定无解
否则我们先找出使得\(d|sum'\)的方案,然后现在考虑怎么让所有数相同
单看一次操作看不出什么,如果我们把连着的两次操作合在一起考虑,不难发现这样对应的一个平均增量就是\(n+1\)
那么我们如果设一个位置下标为\(x\),一个下标为\(y\),设两次操作的序列分别为\(p1,p2\)
则若我们令\(p1_x=1,p1_y=2\)且\(p2_x=n-1,p2_y=n\),然后其它位置都赋上一对和为\(n+1\)的数
那么我们发现我们就实现了一个事实上等价于给任意一个位置\(+1\)的同时并给任意一个位置\(-1\)的操作,利用这个显然可以把所有数都改成一样的
现在来计算一下次数,在做了第一次加数后有\(a_i\le 100\),因此每个数距离平均的偏移量之和是\(\le 100\)的,乘以\(n\)后应该是在\(5000\)次操作左右可以实现题目要求
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
int n,a[N],sum,cnt,p[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,k; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
bool flag=0; if (sum%n)
{
for (flag=1,i=1;i<=n;++i) a[i]+=i,sum+=i;
}
if (sum%n) return puts("No"),0;
int avg=sum/n; for (i=1;i<=n;++i) if (a[i]>avg) cnt+=a[i]-avg;
if (printf("Yes\n%d\n",2*cnt+flag),flag)
{
for (i=1;i<=n;++i) printf("%d%c",i," \n"[i==n]);
}
for (i=1;i<=cnt;++i)
{
int x,y; for (j=1;j<=n;++j) if (a[j]>avg) { x=j; break; }
for (j=1;j<=n;++j) if (a[j]<avg) { y=j; break; }
for (--a[x],++a[y],j=1;j<=n;++j) p[j]=0;
for (p[x]=1,p[y]=2,k=2,j=1;j<=n;++j)
{
if (!p[j]) p[j]=++k;
printf("%d%c",p[j]," \n"[j==n]);
}
for (j=1;j<=n;++j) p[j]=0;
for (p[x]=n-1,p[y]=n,k=n-2,j=1;j<=n;++j)
{
if (!p[j]) p[j]=k--;
printf("%d%c",p[j]," \n"[j==n]);
}
}
return 0;
}
D - LIS 2
还好及时悔悟发现D是个傻逼题,不然这场真要爆炸了
首先我们要观察到一个重要性质,那就是如果答案中包含第\(i\)个区间里的数,那它一定取得了这个区间的一个后缀,即\([x_i,r_i],(x_i\in[l_i,r_i])\)中的所有数都要被选
考虑如果存在一个方案不这么选,比如在第\(i\)个区间选了\([x_i,y_i],(y_i<r_i)\),那么我们不妨把后面一个区间的开头那个数扔掉换成\(y_i+1\),这显然是一定合法的
然后我们如法炮制直到\(y_i=r_i\)答案都不会变劣,因此就证明了上述结论
那现在的问题就是考虑如何维护答案,我们设\(f_i\)为以第\(i\)个区间的结尾\(r_i\)为结尾的LIS长度
当我们做到\(i\)这个区间时,考虑所有\(j<i\)的区间的影响,显然可以分为两类:
- 当\(r_j<l_i\)时,有\(f_i=\max(f_i,f_j+r_i-l_i+1)\)
- 当\(r_j\ge l_i\)时,有\(f_i=\max(f_i,f_j+r_i-r_j)\)
显然我们可以对两种情况分别开线段树维护最值,第一种情况是很trivial的,而第二种情况找合法的\(f_j-r_j\)的最大值即可
总复杂度\(O(n\log n)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,INF=1e9;
int n,l[N],r[N],ans,rst[N<<1],cnt;
class Segment_Tree
{
private:
int mx[N<<3];
#define TN CI now=1,CI l=1,CI r=cnt
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void pushup(CI now)
{
mx[now]=max(mx[now<<1],mx[now<<1|1]);
}
public:
inline void build(TN)
{
mx[now]=-INF; if (l==r) return; int mid=l+r>>1; build(LS); build(RS);
}
inline void updata(CI pos,CI mv,TN)
{
if (l==r) return (void)(mx[now]=max(mx[now],mv)); int mid=l+r>>1;
if (pos<=mid) updata(pos,mv,LS); else updata(pos,mv,RS); pushup(now);
}
inline int query(CI beg,CI end,TN)
{
if (beg>end) return -INF;
if (beg<=l&&r<=end) return mx[now]; int mid=l+r>>1,ret=-INF;
if (beg<=mid) ret=max(ret,query(beg,end,LS));
if (end>mid) ret=max(ret,query(beg,end,RS)); return ret;
}
#undef MX
#undef TN
#undef LS
#undef RS
}A,B;
inline int find(CI x)
{
return lower_bound(rst+1,rst+cnt+1,x)-rst;
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%lld",&n),rst[cnt=1]=0,i=1;i<=n;++i)
scanf("%lld%lld",&l[i],&r[i]),rst[++cnt]=l[i],rst[++cnt]=r[i];
sort(rst+1,rst+cnt+1); cnt=unique(rst+1,rst+cnt+1)-rst-1;
for (A.build(),B.build(),A.updata(find(0),0),B.updata(find(0),0),i=1;i<=n;++i)
{
int ret=max(A.query(1,find(l[i])-1)+r[i]-l[i]+1,B.query(find(l[i]),find(r[i])-1)+r[i]);
ans=max(ans,ret); A.updata(find(r[i]),ret); B.updata(find(r[i]),ret-r[i]);
}
return printf("%lld",ans),0;
}
Postscript
Atcoder终于喜破1500大关,现在一路打下来除了之前那场报名没参加莫名其妙给我掉了200分外都还没掉过分
希望能延续状态继续加油的说
- AtCoder Regular Contest 159atcoder regular contest 159 atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest 167 atcoder regular contest builder beginner atcoder contest 159