正睿NOIP赠送附加赛1

T1：math

题目链接：

http://zhengruioi.com/contest/156/problem/471

题解：

先讲讲我的乱搞做法。对于前面70%，我跑了背包。因为背包有后效性...我做了两次，也就是迭代了一下

剩下的30%随机化了一波。就是先把每个数的20以内的倍数暴力的算出来对k取模然后丢到一个大小为k的桶里面去。因为题目就是让你给每个数一个系数，于是我就每次随机两个位置相加判断在模k的意义下是否出现过，如果没有出现过就加入答案中，咳咳重复1e7次即可A掉本题

下面说说题解做法：

$ax+by=z$存在整数解，当且仅当$gcd(a, b)∣z$。

那么，若z可以被凑出，即 $\sum_{i=1}^{n} x_ia_i = z$，当且仅当 $gcd(a_1, a_2,⋯, a_n)∣z$。

因此，答案只能是gcd的整数倍。

但是，这样考虑x有可能是负数，但是在mod k的条件下，我们可以把x调为非负整数。

时间复杂度$O((n + k)logv)$。

乱搞代码

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

#include<vector>

#include<time.h>

using namespace std;

const int N=1e6+;

int n,k;

int a[N],f[N];

inline int read(){

    char ch=getchar();int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

namespace task1

{

    void main()

    {

        for (int i=;i<=n;i++)

        for (int j=;!f[1ll*j*a[i]%k];j++) f[1ll*j*a[i]%k]=;

        for (int i=;i<=n;i++)

        {

            for (int j=;j<=k;j++) f[j]|=f[((j-a[i])%k+k)%k];

            for (int j=;j<=k;j++) f[j]|=f[((j-a[i])%k+k)%k];

        }

        int s=;

        for (int j=;j<k;j++) s+=f[j];

        printf("%d\n",s);

        for (int j=;j<k;j++) if (f[j]) printf("%d ",j);

    }

}

int gcd(int a,int b) {if (!b) return a;else return gcd(b,a%b);}

namespace task2

{

    void main()

    {

        printf("%d\n",k);

        for (int i=;i<k;i++) printf("%d ",i);

    }

}

int main()

{

    n=read();k=read();

    for (int i=;i<=n;i++) a[i]=read()%k;

    for (int i=;i<=n;i++) if (a[i]==||gcd(a[i],k)==) {task2::main();return ;}

    if (n<=) {task1::main();return ;}

    srand(time());

    vector <int> p;

    for (int i=;i<=n;i++)

    {

        for (int j=;j<=;j++)

        {

            int q=1ll*j*a[i]%k;

            if (!f[q])

            {

                p.push_back(q);

                f[q]=;

            }

        }

    }

    for (int i=;i<=1e7;i++)

    {

        int si=p.size();

        int l=rand()%si,r=rand()%si;

        if (!f[(p[l]+p[r])%k])

        {

            p.push_back((p[l]+p[r])%k);

            f[(p[l]+p[r])%k]=;

        }

    }

    int s=;

    for (int j=;j<k;j++) s+=f[j];

    printf("%d\n",s);

    for (int j=;j<k;j++) if (f[j]) printf("%d ",j);

    return ;

}

T2:biology

题目链接：

http://zhengruioi.com/contest/156/problem/472

题解：

我们显然可以把元素按$a$排序，然后宽搜转移。

$f_{x,y}$ 表示当前路径的结尾在$(x,y)$位置的最大吸引度之和。 $f_{x,y} = b_{x,y}+max (f_{z,k} + ∣x −z ∣ + ∣y −k∣, a_{x,y} >a_{z,k} )$

暴力转移时间复杂度最差为$O(n ^2 m^2)$，考虑优化。

坐标转化$(x,y)->(x+y,x-y)$

这样原来的曼哈顿距离$|x-z|+|y-k|$就变成了切比雪夫距离$max(|x-z|,|y-k|)=max(x-z,z-x,y-k,k-y)$

这样坐标是最大值，转移也是最大值，因此可以用4个变量分别记录最大的$f_{z,k}-z,f_{z,k}+z,f_{z,k}-k,f_{z,k}+k$

时间复杂度为排序复杂度$O(nmlognm)$

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

using namespace std;

typedef long long ll;

const int N=2e3+;

const ll inf=1e9;

int n,m,tot;

ll A,B,C,D;

ll b[N][N],dp[N][N];

inline ll read(){

    char ch=getchar();ll s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

struct node{

    int x,y;

    int d;

}s[N*N];

bool operator < (node x,node y) {return x.d<y.d;}

void chkmx(ll &a,ll b) {if (b>a) a=b;}

void calc()

{

    int l=;ll mx=;

    A=-inf;B=-inf;C=-inf;D=-inf;

    while (l<=tot)

    {

        int r=l;

        while (r<tot&&s[r].d==s[r+].d) ++r;

        for (int k=l;k<=r;k++)

        {

            int x=s[k].x,y=s[k].y;

            int i=x+y,j=x-y;

            dp[x][y]=b[x][y];

            chkmx(dp[x][y],b[x][y]+A+i);

            chkmx(dp[x][y],b[x][y]+B-i);

            chkmx(dp[x][y],b[x][y]+C+j);

            chkmx(dp[x][y],b[x][y]+D-j);

            chkmx(mx,dp[x][y]);

        }

        for (int k=l;k<=r;k++)

        {

            int x=s[k].x,y=s[k].y;

            int i=x+y,j=x-y;

            chkmx(A,dp[x][y]-i);

            chkmx(B,dp[x][y]+i);

            chkmx(C,dp[x][y]-j);

            chkmx(D,dp[x][y]+j);

        }

        l=r+;

    }

    printf("%lld\n",mx);

}

int main()

{

    n=read();m=read();

    for (int i=;i<=n;i++)

        for (int j=,x;j<=m;j++)

        {

            x=read();

            if (x) s[++tot]=(node){i,j,x};

        }

    for (int i=;i<=n;i++)

        for (int j=;j<=m;j++) b[i][j]=read();

    sort(s+,s++tot);

    calc();

    return ;

}

巴特西

正睿NOIP赠送附加赛1

T1：math

题目链接：

题解：

T2:biology

题目链接：

题解：

最新文章

热门文章