ARC159
A
不知道复制\(k\)遍有什么用,其实都是一样的
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[105][105];
int q;
long long s,t;
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==0)
{
a[i][j]=0x3f3f3f3f;
}
}
}
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][j],a[i][k]+a[k][j]);
}
}
}
scanf("%d",&q);
while(q--)
{
scanf("%lld %lld",&s,&t);
s=((s-1)%n)+1;
t=((t-1)%n)+1;
if(a[s][t]==0x3f3f3f3f)
{
printf("-1\n");
}
else
{
printf("%d\n",a[s][t]);
}
}
}
B
被诈骗了/kk
直觉上直接暴力,但\(T\)了很多点
分析一下,这个\(g\)一定是递增的,因为\(A-B\)不变,因此上一个的\(g=\gcd(A-B,B)\)是一定能保留的
\(C=A-B\)
考虑什么时候\(g\)增大,具体的就是\(dg|B-kg,dg|C\)
这玩意直接枚举\(C\)的因数
由于每次\(g\)至少增大到\(2g\),所以最多\(log\)次
#include<bits/stdc++.h>
using namespace std;
long long A,B;
long long gcd(long long a,long long b)
{
if(b==0)
{
return a;
}
return gcd(b,a%b);
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%lld %lld",&A,&B);
long long Tot=0;
if(A>B)
{
swap(A,B);
}
long long C=B-A;
while((A>=1)&&(B>=1))
{
long long g=gcd(C,B);
long long k=0x3f3f3f3f;
if(B%A==0)
{
Tot++;
//printf("%lld %lld???\n",A,B);
break;
}
for(long long i=1;i*i<=(C/g);i++)
{
if((C/g)%i==0)
{
long long d=i;
long long Rb=(A/g);
if(Rb>d)
{
k=min(k,(Rb%d)?(Rb%d):Rb);
}
d=(C/g)/i;
Rb=(A/g);
if(Rb>d)
{
k=min(k,(Rb%d)?(Rb%d):Rb);
}
}
}
Tot+=k;
A-=k*g;
B-=k*g;
//printf("%lld %lld\n",A,B);
}
printf("%lld\n",Tot);
}
C
又被诈骗了/kk
首先考虑总和一定要为\(n\)的倍数或\(n/2\)的倍数,看\(n\)是不是偶数
如果\(n\)是偶数就随便操作一次让他全部是\(n\)的倍数
设\(g=\dfrac{Sum}{n}\),每次我们选\(a_i<g,a_j>g\)的\((i,j)\),并分别操作\((1,n-1),(2,n)\),这样两者的差减\(2\),给其他数操作\((p,n-p+1)\),相当于整体\(+(n+1)\)但\(i,j\)分别\(+1,-1\)
可以发现这样一定有解
#include<bits/stdc++.h>
using namespace std;
int n;
int a[55];
vector<vector<int> >Ans;
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
int Sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
Sum+=a[i];
}
if((n&1)&&(Sum%n))
{
printf("No");
return 0;
}
if((n%2==0)&&((Sum%(n/2))))
{
printf("No");
return 0;
}
if((n%2==0)&&(Sum%n))
{
vector<int>Tmp;
for(int i=1;i<=n;i++)
{
Sum+=i;
a[i]+=i;
Tmp.push_back(i);
}
Ans.push_back(Tmp);
}
int g=(Sum)/n;
while(1)
{
int pi=-1,pj=-1;
for(int i=1;i<=n;i++)
{
if(a[i]<g)
{
pi=i;
break;
}
}
for(int i=1;i<=n;i++)
{
if(a[i]>g)
{
pj=i;
break;
}
}
if(pi==-1)
{
break;
}
int Now=3;
vector<int>t1,t2;
t1.clear();
t2.clear();
for(int i=1;i<=n;i++)
{
if(i==pi)
{
t2.push_back(n);
t1.push_back(2);
a[i]++;
}
else if(i==pj)
{
t2.push_back(n-1);
t1.push_back(1);
a[i]--;
}
else
{
t1.push_back(Now);
t2.push_back(n-Now+1);
++Now;
}
}
Ans.push_back(t1);
Ans.push_back(t2);
}
printf("Yes\n");
printf("%d\n",(int)Ans.size());
for(int i=0;i<Ans.size();i++)
{
for(int j=0;j<n;j++)
{
printf("%d ",Ans[i][j]);
}
printf("\n");
}
}
D
\(dp_i\)为前\(i\)个区间以\(r_i\)结尾的\(LIS\)
这玩意转移看一下区间有没有交即可
#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
using namespace std;
const int MAXN=2e5+5;
int n;
int l,r;
struct Seg_node{
int lc,rc;
int date;
};
struct Seg{
Seg_node Tree[MAXN*100];
int rt;
int cnt_node;
void Insert(int &p,int l,int r,int k,int x)
{
if(!p)
{
p=++cnt_node;
Tree[p].date=-0x3f3f3f3f;
Tree[p].lc=0;
Tree[p].rc=0;
}
Tree[p].date=max(Tree[p].date,x);
if(l==r)
{
return;
}
int mid=(l+r)>>1;
if(k<=mid)
{
Insert(ls,l,mid,k,x);
}
else
{
Insert(rs,mid+1,r,k,x);
}
}
int Query(int p,int l,int r,int ql,int qr)
{
if(!p)
{
return -0x3f3f3f3f;
}
if(l>=ql&&r<=qr)
{
return Tree[p].date;
}
int mid=(l+r)>>1;
int Res=-0x3f3f3f3f;
if(ql<=mid)
{
Res=max(Res,Query(ls,l,mid,ql,qr));
}
if(qr>mid)
{
Res=max(Res,Query(rs,mid+1,r,ql,qr));
}
return Res;
}
}t1,t2;
int dp[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
dp[0]=0;
t1.Insert(t1.rt,0,1e9,0,0);
int Res=0;
for(int i=1;i<=n;i++)
{
scanf("%d %d",&l,&r);
dp[i]=t1.Query(t1.rt,0,1e9,0,l-1)+(r-l+1);
dp[i]=max(dp[i],t2.Query(t2.rt,0,1e9,l,r)+r);
t1.Insert(t1.rt,0,1e9,r,dp[i]);
t2.Insert(t2.rt,0,1e9,r,dp[i]-r);
Res=max(Res,dp[i]);
}
printf("%d\n",Res);
}
E
这玩意就是建一颗二叉搜索树,树高是\(log\)级别的
考虑\((i,i+1)\)一定有祖先关系,因为如果存在\(lca\not=i,i+1\),一定有\(i<lca<i+1\)
然后统计答案的话就是\([c,d]\)和\(1\)虚树上的点\(\times2\)减去\(c,d\)的深度和,虚树经典结论
然后\([c,d]\)和\(1\)虚树上的点统计类似与线段树,把路径上的点全部加上即可
// LUOGU_RID: 122153078
#include<bits/stdc++.h>
using namespace std;
long long n;
int m;
int q;
int a[105];
int b[105];
long long c,d;
int Get_dep(long long l,long long r,long long p,int dep)
{
if(l==r)
{
return dep;
}
long long mid=((l*a[dep%m]+r*b[dep%m])/(a[dep%m]+b[dep%m]));
if(p==mid)
{
return dep;
}
if(p<mid)
{
return Get_dep(l,mid-1,p,dep+1);
}
else
{
return Get_dep(mid+1,r,p,dep+1);
}
}
long long Get(long long l,long long r,long long ql,long long qr,int dep)
{
if(l>r)
{
return 0;
}
if(r<ql||l>qr)
{
return 0;
}
if(l>=ql&&r<=qr)
{
return (r-l+1);
}
long long mid=((l*a[dep%m]+r*b[dep%m])/(a[dep%m]+b[dep%m]));
long long Res=1;
Res+=Get(l,mid-1,ql,qr,dep+1);
Res+=Get(mid+1,r,ql,qr,dep+1);///
return Res;
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%lld %d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d %d",&a[i],&b[i]);
}
scanf("%d",&q);
while(q--)
{
scanf("%lld %lld",&c,&d);
printf("%lld\n",2*(Get(1,n,c,d,0)-1)-Get_dep(1,n,c,0)-Get_dep(1,n,d,0));
}
}