AtCoder Regular Contest 159
A - Copy and Paste Graph
图的邻接矩阵为
\[\left(
\begin{matrix}
A & A & \cdots & A \\
A & A & \cdots & A \\
\cdots & \cdots & \cdots & \cdots\\
A & A & \cdots & A
\end{matrix}
\right)
\]
则
\[{\left(
\begin{matrix}
A & A & \cdots & A \\
A & A & \cdots & A \\
\cdots & \cdots & \cdots & \cdots\\
A & A & \cdots & A
\end{matrix}
\right)}^{\infty} =
{\left(
\begin{matrix}
A^{\infty} & A^{\infty} & \cdots & A^{\infty} \\
A^{\infty} & A^{\infty} & \cdots & A^{\infty} \\
\cdots & \cdots & \cdots & \cdots\\
A^{\infty} & A^{\infty} & \cdots & A^{\infty}
\end{matrix}
\right)}
\]
即为图的两点间最短路径矩阵，其中矩阵是在\(\lbrace+,min\rbrace\)下做矩阵乘法。
因此我们只需要用Floyd算法求出\(A^{\infty}\)即可。
时间复杂度\(O(n^3+Q)\)
code：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
const int inf=1e9+7;
int n,k,a[105][105];
signed main() {
scanf("%lld%lld",&n,&k);
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) {
scanf("%lld",&a[i][j]);
if(a[i][j]<=0) {
a[i][j]=inf;
}
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) {
a[i][j]=min(a[i][k]+a[k][j],a[i][j]);
}
int T;cin>>T;
while(T--) {
int s,t;scanf("%lld%lld",&s,&t);
if(a[(s-1)%n+1][(t-1)%n+1]<inf) {
printf("%lld\n",a[(s-1)%n+1][(t-1)%n+1]);
} else {
puts("-1");
}
}
return 0;
}
B - GCD Subtraction
不失一般性，假设\(a>b\)，首先\((a-g，b-g)=(a-b，b-g)\)
所以每次操作都是\(a-b\)和\(b^{'}\)在做\(gcd\)运算，然后把\(b^{'}\)减去得到的\(g_{new}\)得到\(b^{''}\)然后继续重复上述过程。
考虑怎么加速这些操作。
注意到\((a-b，b-g)=g\times(\frac{a-b}{g},\frac{b}{g}-1)\)若\((\frac{a-b}{g},\frac{b}{g}-1)=1\)则下一次运算就会变成\((\frac{a-b}{g},\frac{b}{g}-2)\)。
因此我们可以找到距离\(\frac{b}{g}-1\)最近的与\(\frac{a-b}{g}\)最大公约数不为\(1\)的数，这个可以通过预处理出\(a-b\)的所有质因数来实现，这样就保证了每次模拟都会至少缩小\(\frac{1}{2}\)。
code:
#include<algorithm>
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int gcd(int o,int p) {return (!p)?o:gcd(p,o%p);}
int prime[200005],a[1000005],cnt=0,divid[2005][2],s=0;
signed main() {
for(int i=2;i<=1000000;i++) {
if(!a[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=1000000;j++) {
a[i*prime[j]]=1;
if(i%prime[j]==0) {
break;
}
}
}
int a,b;scanf("%lld%lld",&a,&b);
if((a==1)||(b==1)||(a==b)) {
puts("1");
return 0;
}
int ans=0,x=min(a,b),g=max(a,b)-min(a,b),gg=g;
for(int i=1;i<=cnt;i++) {
if(gg%prime[i]==0) {
divid[++s][0]=prime[i];
divid[s][1]=0;
while(gg%prime[i]==0) {
gg/=prime[i];
divid[s][1]++;
}
}
if(prime[i]*prime[i]>=gg) {
break;
}
}
if(gg>1) {
divid[++s][0]=gg;
divid[s][1]=1;
}
while((x>0)&&(g>0)) {
int yu=0;
for(int i=1;i<=s;i++) {
if(divid[i][1]==0) {
continue;
}
yu=max(yu,x/divid[i][0]*divid[i][0]);
}
ans+=x-yu;
if(yu<1) break;
x=yu;
int g_new=gcd(x,g);
ans++;
x/=g_new;
x--;
g/=g_new;
for(int i=1;i<=s;i++) {
while(g_new%divid[i][0]==0) {
divid[i][1]--;
g_new/=divid[i][0];
}
}
}
cout<<ans<<endl;
return 0;
}
C - Permutation Addition
假设做了k次操作，所有数的和即为\(\sum_{i=1}^{n}A_i+k\times\frac{n\times(n+1)}{2}\)。
注意到若k为偶数，则有解的一个必要条件是\(n\mid\sum_{i=1}^{n}A_i\)，注意到我们如果用连续的两次操作
\(\{1,2,3,\cdots,n\}\)
\(\{n,n-1,n-2,\cdots,1\}\)
那么相当于什么操作都没有做，但如果改成
\(\{1,2,3,\cdots,n\}\)
\(\{n-1,n,n-2,\cdots,1\}\)
就相当于选择两个元素一个减一一个加一，这样一定可以在\(10000\)次以内构造出解。
对于\(k\)为奇数的情况下，我们先随便做一次操作，转化成偶数的情况。
code：
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
int a[55],sum=0,n,ans[10005][55],cnt=0;
void add(int x,int y) {
cnt++;
ans[cnt][x]=2;ans[cnt][y]=1;
int yu=3;
for(int i=1;i<=n;i++) {
if(i==x||i==y) {
continue;
}
ans[cnt][i]=yu++;
}
cnt++;
ans[cnt][x]=n;ans[cnt][y]=n-1;
yu=n-2;
for(int i=1;i<=n;i++) {
if(i==x||i==y) {
continue;
}
ans[cnt][i]=yu--;
}
}
void work() {
int avg=sum/n;
vector<int> mi;
vector<int> ma;
for(int i=1;i<=n;i++) {
if(a[i]<avg) {
mi.push_back(i);
} else if(a[i]>avg) {
ma.push_back(i);
}
}
int p=0;
for(int i=0;i<mi.size();i++) {
while(a[mi[i]]<avg) {
a[mi[i]]++;a[ma[p]]--;
add(mi[i],ma[p]);
if(a[ma[p]]<=avg) p++;
}
}
puts("Yes");
cout<<cnt<<endl;
for(int i=1;i<=cnt;i++) {
for(int j=1;j<n;j++) {
printf("%d ",ans[i][j]);
}
printf("%d\n",ans[i][n]);
}
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum%n==0) {
work();
} else if((sum+n*(n+1)/2)%n==0) {
sum+=n*(n+1)/2;
for(int i=1;i<=n;i++) a[i]+=i;
cnt=1;
for(int i=1;i<=n;i++) ans[cnt][i]=i;
work();
} else {
puts("No");
}
return 0;
}
D - LIS 2
性质1：在最长不下降子序列问题中，对于值相同的元素的\(dp\)值是单调不减的。
性质2：对于加入的一段连续的\([l,r]\)区间，有\(dp_{l+1}=dp_{l}+1,\quad dp_{l+2}=dp_{l+1}+1,\quad \cdots,\quad dp_r=dp_{r-1}+1\)
我们归纳的证明，若\(dp_{l+1} \neq dp_l+1\)则说明\(dp_{l+1} \gt dp_{l}+1\)，而\(dp_{l+1}\)必然从\([l,r]\)之前的某个元素转移而来，假设是\(x\)若\(x<l\)则说明\(dp_x>dp_l\)那么\(dp_l\)就可以通过\(dp_x\)转移而来得到更优秀的答案，这是矛盾的，若\(x=l\)，就会与性质1矛盾。
有了这些性质对，于一个区间，我们只需要记录\(l\)的\(dp\)值即可。\(dp_l\)可能从\(1,2,\cdots,l-1\)转移而来，若是从\(1,2,\cdots,l-2\)转移而来，依据上面的性质，转移点若非右端点则一定可以右移。剩下的就是线段树优化\(dp\)了。
code：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,a[200005],b[600005],seg[3000005],l[200005],r[200005],f[200005],cnt=0,lazy[3000005],tr[600005];
void pushdown(int s) {
seg[s<<1]=max(seg[s<<1],lazy[s]);
seg[s<<1|1]=max(seg[s<<1|1],lazy[s]);
lazy[s<<1]=max(lazy[s<<1],lazy[s]);
lazy[s<<1|1]=max(lazy[s<<1|1],lazy[s]);
lazy[s]=0;
}
void put(int o,int p,int q,int r,int s,int t) {
seg[s]=max(seg[s],t);
if((o==q)&&(p==r)) {
lazy[s]=max(lazy[s],t);
return;
}
int mid=(o+p)>>1;
if(r<=mid) {
put(o,mid,q,r,s<<1,t);
} else if(q>mid) {
put(mid+1,p,q,r,s<<1|1,t);
}else {
put(o,mid,q,mid,s<<1,t);
put(mid+1,p,mid+1,r,s<<1|1,t);
}
}
int get(int o,int p,int q,int s) {
if((o==q)&&(p==q)) {
return seg[s];
}
pushdown(s);
int mid=(o+p)>>1;
if(q<=mid) {
return get(o,mid,q,s<<1);
} else {
return get(mid+1,p,q,s<<1|1);
}
}
void put_tr(int o,int p,int tmp) {
for(int i=o;i<=tmp;i+=(-i)&i) {
tr[i]=max(tr[i],p);
}
}
int get_tr(int o,int tmp) {
int yu=0;
for(int i=o;i;i-=(-i)&i) {
yu=max(yu,tr[i]);
}
return yu;
}
int main() {
memset(tr,0,sizeof(tr));
memset(seg,0,sizeof(seg));
memset(lazy,0,sizeof(lazy));
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d%d",&l[i],&r[i]);
b[++cnt]=l[i];
b[++cnt]=r[i];
b[++cnt]=l[i]-1;
}
sort(b+1,b+cnt+1);
int tmp=unique(b+1,b+cnt+1)-b-1;
int ans=0;
for(int i=1;i<=n;i++) {
int yu=lower_bound(b+1,b+tmp+1,l[i]-1)-b;
int pos=get(1,tmp,yu,1);
if(pos==0) {
f[i]=1;
} else {
f[i]=f[pos]+min(r[pos],l[i]-1)-l[pos]+1;
}
f[i]=max(f[i],get_tr(yu,tmp)+1);
int ll=lower_bound(b+1,b+tmp+1,l[i])-b;
int rr=lower_bound(b+1,b+tmp+1,r[i])-b;
put(1,tmp,ll,rr,1,i);
ans=max(ans,f[i]+r[i]-l[i]);
put_tr(rr,f[i]+r[i]-l[i],tmp);
}
cout<<ans<<endl;
return 0;
}
E - Difference Sum Query
\(m=\lfloor\frac{a_{t mod M}\times l+b_{t mod M}\times r}{a_{t mod M}+b_{t mod M}}\rfloor=l+\lfloor\frac{b_{t mod M}}{a_{t mod M}+b_{t mod M}}\rfloor \times (r-l)\)
这个形式类似于二分，每次取的点构成一棵二叉搜索树。
题目要求的就是\(ans=\sum_{i=c}^{d-1} [二叉搜索树上从i走到i+1的路径长度]\)。
而\(ans\)加上从\(c\)到\(d\)的路径长度其实就是\(c,c+1,\cdots,d\)这些点构成的虚树的边数的两倍。
虚树上的点又由两部分构成，一部分是\(c,c+1,\cdots,d\)另一部是\(c\)到\(d\)路径上不属于\(c,c+1,\cdots,d\)的点。
题目中还有一个条件\(\max\{\frac{a_i}{b_i},\frac{b_i}{a_i}\}\leq2\)这保证了二叉搜索树的高度不超过\(\log_{\frac{3}{2}}n\)。
code：
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int a[1005],b[1005],n,m,l1,l2,x1[105],x2[105];
void work(int *f,int &len,int target) {
len=0;
int l=1,r=n,t=0,mid=l+(r-l)*b[0]/(a[0]+b[0]);
while(mid!=target) {
f[++len]=mid;
if(mid<target) {
l=mid+1;
} else {
r=mid-1;
}
t=(t+1)%m;
mid=l+(r-l)*b[t]/(a[t]+b[t]);
}
f[++len]=mid;
}
signed main() {
scanf("%lld%lld",&n,&m);
for(int i=0;i<m;i++) {
scanf("%lld%lld",&a[i],&b[i]);
}
int T;cin>>T;
while(T--) {
int ai,bi;scanf("%lld%lld",&ai,&bi);
work(x1,l1,ai);
work(x2,l2,bi);
int pos=-1,sum=bi-ai+1;
for(int i=1;i<=min(l1,l2);i++) {
if(x1[i]==x2[i]) {
pos=i;
} else {
break;
}
}
for(int i=pos;i<=l1;i++) {
if(x1[i]<ai||x1[i]>bi) {
sum++;
}
}
for(int i=pos;i<=l2;i++) {
if(x2[i]<ai||x2[i]>bi) {
sum++;
}
}
printf("%lld\n",sum*2-2-(l1-pos)-(l2-pos));
}
return 0;
}
F - Good Division
- 对于一段区间，可以消去变为空的条件是，区间长度为偶数，且区间内不存在超过区间长度一半的数。
- 题目变成求有多少个分割方法满足分割出来的区间长度为偶数且不存在绝对众数。
我们把\(a_{2i-1},a_{2i}\)看成一个\(pair\quad p_i\) - 考虑动态规划，\(dp_i\)表示以\(p_i\)结尾的满足条件的分割数量。答案就是\(dp_n\)。
- 对于一个\(d\)，我们对所有\(d\)出现的位置染色，然后从左往右对每个\(d\)出现的位置找到左边和右边第一个未染色的位置染色，这个可以用并查集在\(O(n\alpha(n))\)内完成。我们观察每个连续的染色段，只有被包含在段内的区间才有可能出现\(d\)是绝对众数的情况。因此我们后续的维护只需要在段内维护即可。
- 所有段的长度之和是\(O(n)\)的。
- 对于一个\(d\)，我们考虑令\(b_{d,i}=1\)，若\(p_i\)中两个数都等于\(d\)；\(b_{d,i}=-1\)，若\(p_i\)中两个数都不等于\(d\)；其他的情况\(b_{d,i}=0\)。那么一段区间有绝对众数\(d\)的充要条件是区间\(b_{d,i}\)的和大于\(0\)。
- 我们记录每个\(d\)的\(b\)的前缀和\(pre_{d,i}=\sum_{j=1}^{i}b_{d,j}\)，因此一段区间\([l,r]\)有绝对众数\(d\)的条件是\(pre_{d,r}>pre_{d,l-1}\)
- 令\(c_{d,i}\)为所有满足\(pre_{d,x}=i\)的\(x\)的\(dp_x\)的总和，维护\(blk_{d,i}=\sum_{j=-\infin}^{i}c_{d,j}\)
- 每次\(pre\)的变化只有\(\pm1\)。我们的转移策略是先令\(dp_i=\sum_{j=1}^{i-1}dp_j\)再减去不满足条件的转移。
- 这样可以做到\(O(n)\)但实际上跑的贼慢(
code：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<map>
using namespace std;
const int mo=998244353;
int n,a[1000005],sum[1000005],dp[500005],fa[1000005],siz[1000005];
int cnt[1000005],tmp[1000005],pre[1000005],len[1000005],wh[1000005];
vector<int> upd[500005];
vector<int> ed[500005];
vector<int> bg[500005];
vector<int> ed_pos[1000005];
vector<int> pos[1000005];
vector<int> blk[1000005];
inline int getfa(int o) {return (fa[o]==o)?o:(fa[o]=getfa(fa[o]));}
void work_left(int p,vector<int> & p_i) {
vector<int> sche;
sche.clear();
for(auto j:pos[p]) {
if(j==1) {
sche.push_back(1);
cnt[1]++;
continue;
}
int ps=getfa(j-1);
fa[j]=ps;siz[ps]++;
if(!cnt[ps]) {
sche.push_back(ps);
}
cnt[ps]++;
if(ps==1) {
continue;
}
if(ps!=j-1) {
fa[ps]=ps-1;siz[ps-1]+=siz[ps];
if(!cnt[ps-1]) {
sche.push_back(ps-1);
}
cnt[ps-1]++;
ps--;
}
if(ps==1) continue;
if(a[ps-1]==p) {
fa[ps]=getfa(ps-1);
siz[getfa(ps-1)]+=siz[ps];
}
}
for(auto j:sche) {
if(fa[j]==j) {
for(int i=j;i<j+siz[j];i++) {
if(!tmp[(i+1)>>1]) {
p_i.push_back((i+1)>>1);
}
tmp[(i+1)>>1]++;
}
}
fa[j]=j;siz[j]=1;
cnt[j]=0;
}
for(auto j:pos[p]) {
fa[j]=j;siz[j]=1;
cnt[j]=0;
}
}
void work_right(int p,vector<int> & p_i) {
vector<int> sche;
sche.clear();
for(auto j:pos[p]) {
if(j==(n<<1)) {
sche.push_back(n<<1);
cnt[n<<1]++;
continue;
}
int ps=getfa(j+1);
fa[j]=ps;siz[ps]++;
if(!cnt[ps]) {
sche.push_back(ps);
}
cnt[ps]++;
if(ps==(n<<1)) {
continue;
}
if(ps!=j+1) {
fa[ps]=ps+1;siz[ps+1]+=siz[ps];
if(!cnt[ps+1]) {
sche.push_back(ps+1);
}
cnt[ps+1]++;
ps++;
}
if(ps==(n<<1)) continue;
if(a[ps+1]==p) {
fa[ps]=getfa(ps+1);
siz[getfa(ps+1)]+=siz[ps];
}
}
for(auto j:sche) {
if(fa[j]==j) {
for(int i=j;i>j-siz[j];i--) {
if(!tmp[(i+1)>>1]) {
p_i.push_back((i+1)>>1);
}
tmp[(i+1)>>1]++;
}
}
fa[j]=j;siz[j]=1;
cnt[j]=0;
}
for(auto j:pos[p]) {
fa[j]=j;siz[j]=1;
cnt[j]=0;
}
}
pair<int,int> get(int num,int beg) {
int x=pre[num];
int mi=1e9+7;
int ma=-mi;
for(int i=beg;i<=ed_pos[num][wh[num]];i++) {
if((a[i<<1]==num)&&(a[(i<<1)-1]==num)) {
x++;
} else if((a[i<<1]!=num)&&(a[(i<<1)-1]!=num)) {
x--;
}
ma=max(ma,x);
mi=min(mi,x);
}
return make_pair(mi,ma);
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n<<1;i++) {
scanf("%d",&a[i]);
pos[a[i]].push_back(i);
fa[i]=i;
siz[i]=1;
}
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=n<<1;i++) {
vector<int> p_i;
work_left(i,p_i);
reverse(pos[i].begin(),pos[i].end());
work_right(i,p_i);
for(int j:p_i) {
upd[j].push_back(i);
if((j==n)||(!tmp[j+1])) {
ed[j].push_back(i);
}
if((j==1)||(!tmp[j-1])) {
bg[j].push_back(i);
}
}
for(int j:p_i) tmp[j]=0;
}
for(int i=1;i<=n;i++) {
for(int j:ed[i]) {
ed_pos[j].push_back(i);
wh[j]=0;
}
}
dp[0]=1;
for(auto i:upd[1]) {
pair<int,int> yu=get(i,1);
yu.first=min(yu.first,0);
len[i]=-yu.first;
for(int j=1;j<=yu.second-yu.first+1;j++) {
blk[i].push_back(0);
}
blk[i][len[i]]++;
}
memset(sum,0,sizeof(0));
memset(pre,0,sizeof(pre));
memset(dp,0,sizeof(dp));
int s=1;
for(int i=1;i<=n;i++) {
if(i>1) {
for(auto j:bg[i]) {
pair<int,int> yu=get(j,i);
len[j]=-yu.first;
for(int k=1;k<=yu.second-yu.first+1;k++) {
blk[j].push_back(0);
}
}
}
for(auto j:upd[i]) {
if((a[i<<1]!=j)&&(a[(i<<1)-1]!=j)) {
pre[j]--;
sum[j]=((sum[j]-blk[j][pre[j]+len[j]])%mo+mo)%mo;
} else if((a[i<<1]==j)&&(a[(i<<1)-1]==j)) {
sum[j]=(sum[j]+blk[j][pre[j]+len[j]])%mo;
pre[j]++;
}
dp[i]=((dp[i]-sum[j])%mo+mo)%mo;
}
dp[i]=(dp[i]+s)%mo;
s=(s+dp[i])%mo;
for(auto j:upd[i]) {
blk[j][pre[j]+len[j]]+=dp[i];
blk[j][pre[j]+len[j]]%=mo;
}
for(auto j:ed[i]) {
sum[j]=0;
blk[j].clear();
wh[j]++;
}
}
cout<<dp[n]<<endl;
return 0;
}
- 题解 简要 AtCoder Regular Contest题解 简要atcoder regular 题解atcoder regular contest 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