Codeforces Round #349 (Div. 2)

时间：2023-03-09 15:22:50
Codeforces Round #349 (Div. 2)

第一题直接算就行了为了追求手速忘了输出yes导致wa了一发。。。

第二题技巧题，直接sort，然后把最大的和其他的相减就是构成一条直线，为了满足条件就+1

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define MIN(a,b) a<b ? a:b

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f;

ll a[N];

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    ll n,sum=;

    cin>>n;

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

    {

        cin>>a[i];

        sum+=a[i];

    }

    sort(a,a+n);

    cout<<*a[n-]-sum+<<endl;

    return ;

}

B

第三题没来的及写就打另一场去了。。。发现是道dp（我估计写了也写不对）用dp[i][0]表示i到i+2能否截取，dp【i】【1】表示i到i+3能否截取

然后从后向前扫一遍

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cassert>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=,inf=0x3f3f3f;

bool dp[N][];

set<string>ans;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    string s;

    cin>>s;

    for(int i=s.size()-;i>=;i--)

    {

        if(i+==s.size())

        {

            dp[i][]=;

            ans.insert(s.substr(i,));

            continue;

        }

        if(i+==s.size())

        {

            dp[i][]=;

            ans.insert(s.substr(i,));

            continue;

        }

        if(dp[i+][]||(dp[i+][]&&s.substr(i,)!=s.substr(i+,)))

        {

            dp[i][]=;

            ans.insert(s.substr(i,));

        }

        if(dp[i+][]||(dp[i+][]&&s.substr(i,)!=s.substr(i+,)))

        {

            dp[i][]=;

            ans.insert(s.substr(i,));

        }

    }

    cout<<ans.size()<<endl;

    set<string>::iterator it;

    for(it=ans.begin();it!=ans.end();it++)

        cout<<*it<<endl;

    return ;

}

C

D题给一个有向有环图，从中找四个点，每个点之间的距离是最短路，求这四个点距离的最大值

先吧每个点跑一边spfa记录下i到j的最小距离，然后枚举b到c，找点a和点c，使得路径最长，但是直接全部枚举是O（n^4）会爆掉，所以用vector存一下到每个点的最长的3个距离（因为已经枚举了两个点）

然后复杂度就降到O（9n^2）了

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<cassert>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pi acos(-1)

#define ll long long

#define mod 1000000007

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f;

struct edge{

    int to,Next,w;

}e[maxn];

int head[N],cnt;

int n,m;

int d[N],ans[N][N];

void add(int u,int v)

{

    e[cnt].to=v;

    e[cnt].w=;

    e[cnt].Next=head[u];

    head[u]=cnt++;

}

void spfa(int x)

{

    bool vis[N];

    memset(vis,,sizeof vis);

    vis[x]=;

    memset(d,inf,sizeof d);

    d[x]=;

    queue<int>q;

    q.push(x);

    while(!q.empty()){

        int s=q.front();

        q.pop();

        vis[s]=;

        for(int i=head[s];~i;i=e[i].Next)

        {

            int W=e[i].w,To=e[i].to;

            if(d[s]+W<d[To])

            {

                d[To]=d[s]+W;

                if(!vis[To])

                {

                    vis[To]=;

                    q.push(To);

                }

            }

        }

    }

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

        ans[x][i]=min(ans[x][i],d[i]);

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    cin>>n>>m;

    cnt=;

    memset(head,-,sizeof head);

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

    {

        int x,y;

        cin>>x>>y;

        add(x,y);

    }

    memset(ans,inf,sizeof ans);

    for(int i=;i<=n;i++)ans[i][i]=;

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

        spfa(i);

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

    {

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

            cout<<ans[i][j]<<" ";

        cout<<endl;

    }*/

    int cur=,a,b,c,d;

    //求每一个点的最远距离

    vector<pair<int,int> >v1[N],v2[N];

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

    {

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

        {

            if(i==j)continue;

            if(ans[i][j]<inf)v1[i].push_back(make_pair(ans[i][j],j));

            if(ans[j][i]<inf)v2[i].push_back(make_pair(ans[j][i],j));

        }

        sort(v1[i].begin(),v1[i].end());

        reverse(v1[i].begin(),v1[i].end());

        sort(v2[i].begin(),v2[i].end());

        reverse(v2[i].begin(),v2[i].end());

    }

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

    {

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

        {

            if(i==j||ans[i][j]>=inf)continue;

            for(int k=;k<&&k<v2[i].size();k++)//a

            {

                int ccc=v2[i][k].second;

                if(ccc==i||ccc==j)continue;

                for(int l=;l<&&l<v1[j].size();l++)//d

                {

                    int ddd=v1[j][l].second;

                    if(ddd==i||ddd==j||ddd==ccc)continue;

                    if(cur<ans[i][j]+v1[j][l].first+v2[i][k].first)

                    {

                        cur=ans[i][j]+v1[j][l].first+v2[i][k].first;

                        a=ccc,b=i,c=j,d=ddd;

                    }

                }

            }

        }

    }

    //cout<<cur<<endl;

    cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;

    return ;

}

D

E待补

相关文章