ARC158
A
\(ARC159C\)的超级弱化版??
每次操作相当于一个\(+2\)一个\(-2\)
#include<bits/stdc++.h>
using namespace std;
long long Abs(long long x)
{
return x>0?x:-x;
}
int T;
long long a,b,c;
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%lld %lld %lld",&a,&b,&c);
long long Sum=(a+b+c);
if(Sum%3)
{
printf("-1\n");
continue;
}
else
{
long long g=Sum/3;
long long Na=0;
if(Abs(a-g)&1)
{
printf("-1\n");
continue;
}
else
{
Na=max(Na,Abs(a-g)/2);
}
if(Abs(b-g)&1)
{
printf("-1\n");
continue;
}
else
{
Na=max(Na,Abs(b-g)/2);
}
if(Abs(c-g)&1)
{
printf("-1\n");
continue;
}
else
{
Na=max(Na,Abs(c-g)/2);
}
printf("%lld\n",Na);
}
}
}
B
\(\dfrac{x+y+z}{xyz}=\dfrac{1}{xy}+\dfrac{1}{xz}+\dfrac{1}{yz}\)
不难发现取三个\(\dfrac{1}{x}\)最大/最小的数即可
有负数的话直接把前面\(3\)个和后面\(3\)个拉出了暴力即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n;
int a[MAXN];
double v[MAXN];
double V[16];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
v[i]=(1.0/a[i]);
}
sort(v+1,v+1+n);
int Cnt=0;
for(int i=1;i<=3;i++)
{
V[++Cnt]=v[i];
}
for(int i=n-2;i<=n;i++)
{
if(i>3)
{
V[++Cnt]=v[i];
}
}
double Maxi=-1e15;
double Mini=1e15;
for(int i=1;i<=Cnt;i++)
{
for(int j=i+1;j<=Cnt;j++)
{
for(int k=j+1;k<=Cnt;k++)
{
double R=((V[i]*V[j]+V[j]*V[k]+V[i]*V[k]));
Maxi=max(Maxi,R);
Mini=min(Mini,R);
}
}
}
printf("%.15lf\n",Mini);
printf("%.15lf\n",Maxi);
}
C
考虑对\(f(X)\)求和然后减去进位的次数\(\times9\)
然后枚举在哪进的位\(i\),对于\(a,b\),只要\(a\bmod 10^i+b\bmod 10^i>10^i\)则会进位,这里直接双指针扫一下或者二分即可
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
int n;
long long A[MAXN];
long long B[MAXN];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
long long Res=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&A[i]);
long long Mul=1;
for(int j=1;j<=15;j++)
{
Res+=((A[i]/Mul)%10)*n*2;
Mul*=10;
}
}
long long Mul=1;
for(int s=1;s<=15;s++)
{
Mul*=10;
for(int i=1;i<=n;i++)
{
B[i]=(A[i]%Mul);
}
sort(B+1,B+1+n);
for(int i=1;i<=n;i++)
{
long long Rest=(Mul-B[i]);
int l=1;
int r=n;
int Key=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(B[mid]>=Rest)
{
Key=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
if(Key!=-1)
{
Res-=(9ll*(n-Key+1));
}
}
}
printf("%lld\n",Res);
}
D
抽象题
注意到等式左边比右边次数大一,把分别设为\(F(x,y,z),G(x,y,z)\)
我们对于任意的\(x,y,z\),如果存在\(t\)满足\(F(x,y,z)=G(x,y,z)t\bmod p\)
则\(F(\frac{x}{t},\frac{y}{t},\frac{z}{t})=G(\frac{x}{t},\frac{y}{t},\frac{z}{t})\)
然后我们就可以随机一组\((x,y,z)\)只要\(F,G\)均不为\(0\)即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int T;
int n;
int p;
int F(int x,int y,int z)
{
int t1=((long long)x+y+z)%p;
int t2=((long long)Pow(x,n,p)+Pow(y,n,p)+Pow(z,n,p))%p;
int t3=((long long)Pow(x,2*n,p)+Pow(y,2*n,p)+Pow(z,2*n,p))%p;
t1=((long long)t1*t2)%p;
t1=((long long)t1*t3)%p;
return t1;
}
int G(int x,int y,int z)
{
return ((long long)Pow(x,3*n,p)+Pow(y,3*n,p)+Pow(z,3*n,p))%p;
}
mt19937 NIU(time(0));
signed main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%lld",&T);
while(T--)
{
scanf("%lld %lld",&n,&p);
while(1)
{
int x=((rand())%(p-1))+1;
int y=((rand())%(p-1))+1;
int z=((rand())%(p-1))+1;
int f=F(x,y,z);
int g=G(x,y,z);
if(x==y||y==z||x==z)
{
continue;
}
if(f&&g)
{
int t=((long long)g*inv(f,p))%p;
int X=((long long)x*t)%p;
int Y=((long long)y*t)%p;
int Z=((long long)z*t)%p;
if(Z<Y)
{
swap(Z,Y);
}
if(Y<X)
{
swap(X,Y);
}
if(Z<Y)
{
swap(Z,Y);
}
printf("%lld %lld %lld\n",X,Y,Z);
break;
}
}
}
}
E
想到分治就好做了（虽然我一直在\(dp\)的方向想
对于\([L,R]\)计算跨越\(mid\)的贡献
考虑路径由\((mid,0),(mid+1,0)\)或\((mid,1),(mid+1,1)\)拼接起来,我们可以直接计算每个点到这四个点的最短距离,然后分类讨论一下他的路径是由哪个点拼接起来的就行了
// LUOGU_RID: 122332688
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=4e5+5;
int n;
int a[MAXN][2];
int Res=0;
long long A[MAXN][2];
long long B[MAXN][2];
vector<pair<long long,pair<int,int> > >V1,V2;
int Sur[MAXN*2];
int Pre[MAXN*2];
void solve(int l,int r)
{
if(l==r)
{
Res=((long long)Res+(3ll*(a[l][0]+a[l][1]))%MOD)%MOD;
return;
}
int mid=(l+r)>>1;
solve(l,mid);
solve(mid+1,r);
for(int i=l;i<=r;i++)
{
A[i][0]=A[i][1]=B[i][0]=B[i][1]=1e15;
}
A[mid][0]=a[mid][0];
A[mid][1]=a[mid][0]+a[mid][1];
for(int i=mid-1;i>=l;i--)
{
long long t0=A[i+1][0]+a[i][0];
long long t1=A[i+1][1]+a[i][1];
A[i][0]=min(t0,t1+a[i][0]);
A[i][1]=min(t1,t0+a[i][1]);
}
B[mid][0]=a[mid][0]+a[mid][1];
B[mid][1]=a[mid][1];
for(int i=mid-1;i>=l;i--)
{
long long t0=B[i+1][0]+a[i][0];
long long t1=B[i+1][1]+a[i][1];
B[i][0]=min(t0,t1+a[i][0]);
B[i][1]=min(t1,t0+a[i][1]);
}
A[mid+1][0]=a[mid+1][0];
A[mid+1][1]=a[mid+1][0]+a[mid+1][1];
for(int i=mid+2;i<=r;i++)
{
long long t0=A[i-1][0]+a[i][0];
long long t1=A[i-1][1]+a[i][1];
A[i][0]=min(t0,t1+a[i][0]);
A[i][1]=min(t1,t0+a[i][1]);
}
B[mid+1][0]=a[mid+1][0]+a[mid+1][1];
B[mid+1][1]=a[mid+1][1];
for(int i=mid+2;i<=r;i++)
{
long long t0=B[i-1][0]+a[i][0];
long long t1=B[i-1][1]+a[i][1];
B[i][0]=min(t0,t1+a[i][0]);
B[i][1]=min(t1,t0+a[i][1]);
}
V1.clear();
V2.clear();
for(int i=l;i<=mid;i++)
{
V1.push_back(make_pair(A[i][0]-B[i][0],make_pair(i,0)));
V1.push_back(make_pair(A[i][1]-B[i][1],make_pair(i,1)));
}
for(int i=mid+1;i<=r;i++)
{
V2.push_back(make_pair(B[i][0]-A[i][0],make_pair(i,0)));
V2.push_back(make_pair(B[i][1]-A[i][1],make_pair(i,1)));
}
sort(V1.begin(),V1.end());
sort(V2.begin(),V2.end());
int Pi=0;
Pre[0]=(B[V2[0].second.first][V2[0].second.second])%MOD;
for(int i=1;i<V2.size();i++)
{
Pre[i]=((long long)Pre[i-1]+(B[V2[i].second.first][V2[i].second.second]%MOD))%MOD;
}
Sur[V2.size()]=0;
for(int i=V2.size()-1;i>=0;i--)
{
Sur[i]=((long long)Sur[i+1]+(A[V2[i].second.first][V2[i].second.second]%MOD))%MOD;
}
for(int i=0;i<V1.size();i++)
{
while((Pi<V2.size())&&(V2[Pi].first<V1[i].first))
{
++Pi;
}
int To=0;
To=((long long)To+(Sur[Pi]))%MOD;
To=((long long)To+(((long long)A[V1[i].second.first][V1[i].second.second]%MOD)*(V2.size()-Pi))%MOD)%MOD;
if(Pi)
{
To=((long long)To+(Pre[Pi-1]))%MOD;
To=((long long)To+(((long long)B[V1[i].second.first][V1[i].second.second]%MOD)*(Pi))%MOD)%MOD;
}
Res=((long long)Res+(2ll*To)%MOD)%MOD;
//printf("%d %d %d %d??\n",V1[i].second.first,V1[i].second.second,To,Pi);
}
}
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<=1;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[j][i]);
}
}
solve(1,n);
printf("%d\n",Res);
}