Codeforces

A.直接判断每一个数。

#include<bits/stdc++.h>

using namespace std;

int n,a[][];

int main()

{

    ios::sync_with_stdio();

    cin >> n;

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

    {

        for(int j = ;j <= n;j++)   cin >> a[i][j];

    }

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

    {

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

        {

            if(a[i][j] == )    continue;

            int flag = ;

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

            {

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

                {

                    if(a[ii][j]+a[i][jj] == a[i][j])    flag = ;

                }

            }

            if(!flag)

            {

                cout << "No" << endl;

                return ;

            }

        }

    }

    cout << "Yes" << endl;

    return ;

}

B.枚举直线上每一点，x，y坐标分开算，求和公式。

#include<bits/stdc++.h>

using namespace std;

long long m,b;

int main()

{

    ios::sync_with_stdio();

    cin >> m >> b;

    long long ans = ;

    for(int y = ;y <= b;y++)

    {

        long long x = (b-y)*m;

        ans = max(ans,(x+)*(y+)*y/+(y+)*(x+)*x/);

    }

    cout << ans << endl;

    return ;

}

C.模拟栈，每次需要整理的时候，把栈中所有出栈，因为底下的已经有序，不需要再去关注它们。

#include<bits/stdc++.h>

using namespace std;

int n;

stack<int> s;

string ss;

int main()

{

    ios::sync_with_stdio();

    cin >> n;

    int now = ,ans = ;

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

    {

        cin >> ss;

        if(ss == "add")

        {

            int x;

            cin >> x;

            s.push(x);

        }

        else

        {

            if(s.empty())

            {

                now++;

                continue;

            }

            if(now == s.top())

            {

                s.pop();

                now++;

            }

            else

            {

                ans++;

                now++;

                while(!s.empty())   s.pop();

            }

        }

    }

    cout << ans << endl;

    return ;

}

D.直接O(k^2)的最短路，转移的时候若两个点相邻，则dis不用+1，若某一坐标之差≤2，则可以转移dis+1，若终点不lit，设一个(n+1,m+1)的点，最后结果回自动+1。

#include<bits/stdc++.h>

#define INF 0x3f3f3f3f

using namespace std;

int n,m,k,x[],y[],vis[] = {},dis[] = {};

int main()

{

    ios::sync_with_stdio();

    cin >> n >> m >> k;

    int s,t = ;

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

    {

        cin >> x[i] >> y[i];

        if(x[i] ==  && y[i] == )  s = i;

        if(x[i] == n && y[i] == m)  t = i;

    }

    if(!t)

    {

        t = ++k;

        x[k] = n+;

        y[k] = m+;

    }

    memset(dis,0x3f,sizeof(dis));

    dis[s] = ;

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

    {

        int pos = -,minn = INF;

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

        {

            if(!vis[i] && dis[i] < minn)

            {

                pos = i;

                minn = dis[i];

            }

        }

        if(pos == -)  break;

        vis[pos] = ;

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

        {

            if(vis[i])  continue;

            if(abs(x[pos]-x[i])+abs(y[pos]-y[i]) == )  dis[i] = min(dis[i],dis[pos]);

            else if(abs(x[pos]-x[i]) <=  || abs(y[pos]-y[i]) <= ) dis[i] = min(dis[i],dis[pos]+);

        }

    }

    if(dis[t] == INF) cout << - << endl;

    else    cout << dis[t] << endl;

    return ;

}

E.对于每一段，可以dp，矩阵快速幂优化，注意每一段结束和每一段开始的时候，把高于c点的值清零。

#include<bits/stdc++.h>

#define MOD 1000000007

using namespace std;

int n;

long long k;

struct xx

{

    long long m[][];

};

xx mul(xx a,xx b,int len)

{

    xx tmp;

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

    {

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

        {

            tmp.m[i][j] = ;

            for(int k = ;k <= len;k++)  tmp.m[i][j] = (tmp.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;

        }

    }

    return tmp;

}

xx qpower(xx a,long long k,int len)

{

    xx b;

    memset(b.m,,sizeof(b.m));

    for(int i = ;i <= len;i++)  b.m[i][i] = ;

    while(k)

    {

        if(k%) b = mul(a,b,len);

        a = mul(a,a,len);

        k /= ;

    }

    return b;

}

int main()

{

    ios::sync_with_stdio();

    cin >> n >> k;

    xx base,now;

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

    {

        for(int j = max(,i-);j < min(i+,);j++)  base.m[i][j] = ;

    }

    now.m[][] = ;

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

    {

        long long a,b,c;

        cin >> a >> b >> c;

        for(int j = c+;j < ;j++) now.m[j][] = ;

        now = mul(qpower(base,min(b,k)-a,c),now,c);

        for(int j = c+;j < ;j++) now.m[j][] = ;

        if(b >= k)  break;

    }

    cout << now.m[][] << endl;

    return ;

}

巴特西

Codeforces_821

最新文章

热门文章