10.11NOIP模拟题(3)

/*

可以看出，对于一段区间[L,R]如果统计了答案

若a[L]<a[R],那么当右端点往左移时答案不会更优，a[R]>a[L]同理

所以两个指针分别从头尾往中间扫那边小移哪边即可。

*/

#include<bits/stdc++.h>

#define N 1000007

#define ll long long

using namespace std;

ll a[N];

ll n,m,ans,cnt;

int main()

{

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

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

    scanf("%lld",&n);

    for(int i=;i<=n;i++) scanf("%lld",&a[i]);

    int L=,R=n;

    while(L<=R)

    {

        ll res=(R-L+)*min(a[L],a[R]);

        ans=max(ans,res);

        if(a[L]>=a[R]) R--;

        else L++;

    }

    cout<<ans<<endl;

    return ;

}

/*

发现算来算去所有数的二进制1的个数和位置不会变。

两个数and 或 or只是把他们的二进制位的1聚拢到一个数上。

若两个数为a，b，假设他们进行一次操作后变为(a+x),(b-x),则a>b

那么(a+x)^2+(b-x)^2=a^2+b^2+2x(x+a-b)>a^2+b^2

说明这种“聚拢”操作后平方和会变大

所以把所有数的二进制位1统计下来后尽可能的对分给一个数即可。

*/

#include<bits/stdc++.h>

#define mod 998244353

#define N 10005

using namespace std;

int n,x;

int cnt[N];

int main()

{

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

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

    scanf("%d",&n);

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

    {

        scanf("%d",&x);

        for (int j=;j<;j++) if (x & (<<j)) cnt[j]++;

    }

    unsigned long long ans=;

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

    {

        x=;

        for(int j=;j<;j++) if (cnt[j]) x |=(<<j),cnt[j]--;

        ans+=(unsigned long long)(x)*x%mod;;

    }

    cout<<ans%mod;

    return ;

}

#include<bits/stdc++.h>

#define N 30

#define ll long long

#define mod 1000000007

#define opt 99999

using namespace std;

int n,m,k,lim;

ll ans;

int dx[]={,,,-};

int dy[]={,-,,};

int vis[N][N],f[N][N];

inline ll read()

{

    int x=,f=;char c=getchar();

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

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

bool can(int x,int y)

{

    if(vis[x][y]==-) return false;

    for(int i=max(,y-);i<=min(y+,m);i++)

      if(vis[x][i]>=opt) return false;

    for(int i=max(,x-);i<=min(n,x+);i++)

      if(vis[i][y]>=opt) return false;

    if(vis[x-][y-]>=opt || vis[x-][y+]>=opt) return false;

    if(vis[x+][y+]>=opt || vis[x+][y-]>=opt) return false;

    return true;

}

void update(int x,int y)

{

    vis[x][y]=opt;

    for(int i=max(,y-);i<=min(y+,m);i++)

      if(vis[x][i]!=-)vis[x][i]++;

    for(int i=max(,x-);i<=min(n,x+);i++)

      if(vis[i][y]!=-)vis[i][y]++;

    if(x- && y- && vis[x-][y-]!=-) vis[x-][y-]++;

    if(x- && y+<=m && vis[x-][y+]!=-) vis[x-][y+]++;

    if(x+<=n && y- && vis[x+][y-]!=-) vis[x+][y-]++;

    if(x+<=n && y+<=m && vis[x+][y+]!=-) vis[x+][y+]++;

}

void _update(int x,int y)

{

    vis[x][y]=;

    for(int i=max(,y-);i<=min(y+,m);i++)

      if(vis[x][i]>)vis[x][i]--;

    for(int i=max(,x-);i<=min(n,x+);i++)

      if(vis[i][y]>)vis[i][y]--;

    if(vis[x-][y-]>)vis[x-][y-]--;

    if(vis[x-][y+]>)vis[x-][y+]--;

    if(vis[x+][y-]>)vis[x+][y-]--;

    if(vis[x+][y+]>)vis[x+][y+]--;

    f[x][y]=;

}

void dfs(int x,int y,int L)

{

    if(L==)

    {

        ans++;ans%=mod;

        return;

    }

    for(int xx=x;xx<=n;xx++) for(int yy=;yy<=m;yy++)

    {

        if(f[xx][yy]) continue;

        if(vis[xx][yy]<opt && can(xx,yy) && !f[xx][yy])

        {

            update(xx,yy);

            f[xx][yy]=;

            dfs(xx,yy,L-);

            _update(xx,yy);//dfs(xx,yy,L);

        }

    }

}

int main()

{

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

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

    int x,y;ans=;

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

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

    {

        x=read();y=read();

        vis[x][y]=-;

    }

    lim=n*m-k;

    while(lim--)

    {

        memset(f,,sizeof f);

        f[][]=;

        dfs(,,lim);

    }

    ans%=mod;cout<<ans<<endl;

    return ;

}

没调出来的dfs

#include <cstdio>

#include <cstring>

#include <vector>

const int MAXN = ;

const int MOD = 1e9 + ;

int m;

inline unsigned int getBit(int i) {

    return 1u << i;

}

inline bool isValidLine(unsigned int s) {

    return !((s & (s << )) || (s & (s << )));

}

inline bool isValidTwoLines(unsigned int a, unsigned int b) {

    return !((a & (b << )) || (a & (b >> )) || (a & b));

}

inline bool isValidThreeLines(unsigned int a, unsigned int b, unsigned int c) {

    return !(a & c) && isValidTwoLines(a, b)/* && isValidTwoLines(b, c)*/;

}

int main() {

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

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

    int n, k;

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

    unsigned int ban[n + ];

    memset(ban, , sizeof(ban));

    while (k--) {

        int i, j;

        scanf("%d %d", &i, &j);

        ban[i] |=  << (j - );

    }

    std::vector<unsigned int> validStates;

    unsigned int maxS =  << m;

    for (int i = ; i < maxS; i++) {

        if (isValidLine(i)) {

            validStates.push_back(i);

        }

    }

    // f[i][state of line i - 1][state of line i] = count

    long long f[n + ][validStates.size()][validStates.size()];

    memset(f, , sizeof(f));

    for (int a = ; a < (int)validStates.size(); a++) f[][][a] = ;

    long long ans = ;

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

        for (int c = ; c < (int)validStates.size(); c++) {

            if (ban[i] & validStates[c]) continue;

            for (int b = ; b < (i <=  ?  : (int)validStates.size()); b++) {

                if (!isValidTwoLines(validStates[b], validStates[c])) continue;

                if (ban[i - ] & validStates[b]) continue;

                for (int a = ; a < (i <=  ?  : (int)validStates.size()); a++) {

                    if (!isValidThreeLines(validStates[a], validStates[b], validStates[c])) continue;

                    if (a && (ban[i - ] & validStates[a])) continue;

                    (f[i][b][c] += f[i - ][a][b]) %= MOD;

                }

                if (i == n) (ans += f[i][b][c]) %= MOD;

            }

        }

    }

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

}

std

暂时放弃先做完互不侵犯king再来写这道题

巴特西

10.11NOIP模拟题(3)

最新文章

热门文章