2017 济南精英班 Day1

不管怎么掰都是n*m-1

#include<cstdio>

using namespace std;

int main()

{

    freopen("bpmp.in","r",stdin);

    freopen("bpmp.out","w",stdout);

    int n,m;

    scanf("%d%d",&n,&m);

    int ans=(1ll*n*m-)%;

    printf("%d",ans);

}

将行状态压缩，枚举哪些行被折成了一条

枚举时，上一次选取的行 与 这一次选取的行 奇偶性不同，这两行才能折到一起

选取列也要求 上一个选的列与这一个选的列奇偶性不同

dp计算这一条上选哪些列

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,ans;

int a[][],c[];

int dp(int s)

{

    bool f=false;

    memset(c,,sizeof(c));

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

        if(s&(<<i))

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

                c[j]+=a[i][j];

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

        if(c[j]>) { f=true; break; }

    if(!f) return -2e9;

    int c0=,c1=,x;

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

        if(i&) c1=max(c[i]+c0,c1);

        else c0=max(c[i]+c1,c0);

    return max(c1,c0);

}

void dfs(int now,int last,int state)

{

    if(now==n)

    {

        ans=max(ans,dp(state));

        return;

    }

    if(last==- || ((now-last)&)) dfs(now+,now,state|(<<now));

    dfs(now+,last,state);

}

int main()

{

    freopen("cfyw.in","r",stdin);

    freopen("cfyw.out","w",stdout);

    scanf("%d%d",&n,&m);

    ans=-2e9;

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

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

            scanf("%d",&a[i][j]),ans=max(ans,a[i][j]);

    if(ans>) dfs(,-,);

    printf("%d",ans);

}

推公式+除法分块

http://www.cnblogs.com/TheRoadToTheGold/p/6696450.html

#include<cstdio>

#include<algorithm>

#define N 10000001

#define mod 998244353

using namespace std;

int p[],phi[N],cnt;

long long sum[N];

bool vis[N];

void pre(int n)

{

    phi[]=;

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

    {

        if(!vis[i])

        {

            vis[i]=true;

            phi[i]=i-;

            p[++cnt]=i;

        }

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

        {

            if(i*p[j]>n) break;

            vis[i*p[j]]=true;

            if(i%p[j]==)

            {

                phi[i*p[j]]=phi[i]*p[j];

                break;

            }

            else phi[i*p[j]]=phi[i]*(p[j]-);

        }

    }

    for(int i=;i<=n;i++) sum[i]=sum[i-]+phi[i];

}

int main()

{

    freopen("hoip.in","r",stdin);

    freopen("hoip.out","w",stdout);

    int n,m;

    scanf("%d%d",&n,&m);

    pre(min(n,m));

    long long ans=;

    long long j;

    for(long long i=;i<=min(n,m);i=j+)

    {

        j=min(n/(n/i),m/(m/i));

        ans=(ans+(sum[j]-sum[i-])*(n/i)%mod*(m/i)%mod)%mod;

    }

    printf("%I64d",ans);

}