T1:math
Description:
基本思路:
这是一道很水的题,考场AC
原式展开后有若干类似a[i]*rand()%k的项(这里由于那个式子未知,我们直接认为是rand)
如果我们取足够多的数(我取得是b=(1~1000),k取得13×14,a取得11,10,13,7,21)将这个式子计算若干次,就会发现:
得到的结果是从0开始的以GCD(a,k)为公差的等差数列,最后一项小于k
其实很好理解,a=x1×gcd(a,k),k=x2×gcd(a,k),若干倍的a模k的结果一定是若干倍的gcd(a,k)又由于
倍数随机,所以gcd的所有倍数(小于k)一定能取到
由此拓展,将原来的sigma看作是x倍的gcd(ai(i=1~n),k),那么上述性质仍成立
那么这道题就可解了
代码:
#include<bits/stdc++.h>
using namespace std;
namespace STD
{
#define ll long long
#define rr register
#define min(x,y) x<y?x:y
#define max(x,y) x>y?x:y
const int RANGE=1e9;
const int SIZEN=5e5+4;
const int SIZEK=1e6+4;
int n,k,x;
int a[SIZEN],gcd[SIZEN];
int GCD(rr int x,rr int y)
{
if(!y) return x;
return GCD(y,x%y);
}
int read()
{
rr int x_read=0,y_read=1;
rr char c_read=getchar();
while(c_read<'0'||c_read>'9')
{
if(c_read=='-') y_read=-1;
c_read=getchar();
}
while(c_read<='9'&&c_read>='0')
{
x_read=x_read*10+(c_read^48);
c_read=getchar();
}
return x_read*y_read;
}
};
using namespace STD;
int main()
{
n=read(),k=read();
for(rr int i=1;i<=n;i++) a[i]=read(),gcd[i]=GCD(a[i],k);
x=GCD(gcd[1],gcd[2]);
for(rr int i=3;i<=n;i++)
x=GCD(x,gcd[i]);
printf("%d\n0",k/x);
for(rr int i=1;i<k/x;i++)
printf(" %d",i*x);
}
T2:biology
Description:
基本思路:
DP
这个我考场上想到了,但没打出来。
我们可以发现,路线只要求a严格递增,而不关心坐标。
所以我们可以直接将信息存在struct里,然后按a升序排序
定义c[i]为以第i个点为路线的终点时答案的最大值
原式里有绝对值,不好维护,我们可以将绝对值拆开维护
即将|i-i’||j-j’|拆为i-i’ i’-i j-j’ j’-j然后维护c[i-1]+i’-j’与c[i-1]-i’+j’与c[i-1]+i’+j’与c[i-1]-i’-j’即可
这个我们可以用四个变量维护。
上代码:
#include<bits/stdc++.h>
using namespace std;
namespace STD
{
#define ll long long
#define rr register
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define inf INT_MAX
const int SIZE=2e3;
int n,m;
ll ans=-inf;
ll t1=-inf,t2=-inf,t3=-inf,t4=-inf;
struct dot{int x,y,a,b;}x[SIZE*SIZE+2];
bool operator<(const dot a_,const dot b_){return a_.a<b_.a;}
ll c[SIZE*SIZE+3];
int read()
{
rr int x_read=0,y_read=1;
rr char c_read=getchar();
while(c_read<'0'||c_read>'9')
{
if(c_read=='-') y_read=-1;
c_read=getchar();
}
while(c_read<='9'&&c_read>='0')
{
x_read=(x_read*10)+(c_read^48);
c_read=getchar();
}
return x_read*y_read;
}
};
using namespace STD;
int main()
{
n=read(),m=read();
int cnt=0;
for(rr int i=1;i<=n;i++)
for(rr int j=1;j<=m;j++)
{
x[++cnt].a=read();
x[cnt].a=x[cnt].a?x[cnt].a:inf;
//一个小技巧:将值为0的a附为inf,这样在排序时就会将它排在最后
x[cnt].x=j,x[cnt].y=i;
c[cnt]=-inf;
}
cnt=0;
for(rr int i=1;i<=n;i++)
for(rr int j=1;j<=m;j++)
x[++cnt].b=read();
sort(x+1,x+1+m*n);
int st=n*m;
while(x[st].a==inf) st--;
int en=st;
while(x[st].a==x[en].a) c[st]=x[st].b,st--;
for(rr int i=st;i;i--)
{
if(x[i].a!=x[i+1].a)
{
rr int j=i+1;
while(x[j].a==x[i+1].a)
{
t1=max(t1,c[j]-x[j].x-x[j].y);
t2=max(t2,c[j]+x[j].x-x[j].y);
t3=max(t3,c[j]-x[j].x+x[j].y);
t4=max(t4,c[j]+x[j].x+x[j].y);
//这里一开始用的是二维树状数组
//然后在对应的区间范围里找值,会TLE
//其实直接用变量即可,因为式子里是绝对值,答案一定是非负
//即使我下标维护的不是对应下标,由错误产生的答案不是最优解
//在取最优解时会将它排除掉
//因而不影响正确性
j++;
}
}
c[i]=max(c[i],t1+x[i].x+x[i].y);
c[i]=max(c[i],t2-x[i].x+x[i].y);
c[i]=max(c[i],t3+x[i].x-x[i].y);
c[i]=max(c[i],t4-x[i].x-x[i].y);
c[i]+=x[i].b;
}
for(rr int i=1;i<=n*m;i++)
{
if(x[i].a!=x[1].a) break;
ans=max(ans,c[i]);
}
printf("%lld\n",ans);
}