Codeforces Round #468 (Div. 2, based on Technocup 2018 Final Round)

A、B都是暴力搞一搞。

A：

 #include<bits/stdc++.h>

 #define fi first

 #define se second

 #define mk make_pair

 #define pii pair<int,int>

 #define read(x) scanf("%d",&x)

 #define sread(x) scanf("%s",x)

 #define dread(x) scanf("%lf",&x)

 #define lread(x) scanf("%lld",&x)

 using namespace std;

 typedef long long ll;

 const int inf=0x3f3f3f3f;

 const int INF=0x3f3f3f3f3f3f3f3f;

 const int N=1e6+;

 const int M=;

 ll w[];

 int a,b;

 int main()

 {

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

         w[i]=w[i-]+i;

     read(a);read(b);

     if(a>b)

         swap(a,b);

     ll ans=INF;

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

     {

         ans=min(ans,w[i-a]+w[b-i]);

     }

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

     return ;

 }

 /*

 */

B：

#include<bits/stdc++.h>

#define fi first

#define se second

#define mk make_pair

#define pii pair<int,int>

#define read(x) scanf("%d",&x)

#define sread(x) scanf("%s",x)

#define dread(x) scanf("%lf",&x)

#define lread(x) scanf("%lld",&x)

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const int INF=0x3f3f3f3f3f3f3f3f;

const int N=1e6+;

const int M=;

ll w[];

int n,a,b;

vector<int> v[];

int main()

{

    read(n);

    read(a); read(b);

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

        v[].push_back(i);

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

    {

        if(v[i].size()==)

            break;

        for(int j=;j<v[i].size();j+=)

        {

            if(v[i][j]==a && v[i][j^]==b || v[i][j]==b && v[i][j^]==a)

            {

                printf("%d\n",i+);

                return ;

            }

            if(v[i][j^]==a || v[i][j^]==b)

                v[i+].push_back(v[i][j^]);

            else

                v[i+].push_back(v[i][j]);

        }

    }

    puts("Final!");

}

/*

*/

C题：刚开始没看到给你的数据差值不小于等于2，感觉不会写，看到了啪啦啪啦写完啦。

 #include<bits/stdc++.h>

 #define fi first

 #define se second

 #define mk make_pair

 #define pii pair<int,int>

 #define read(x) scanf("%d",&x)

 #define sread(x) scanf("%s",x)

 #define dread(x) scanf("%lf",&x)

 #define lread(x) scanf("%lld",&x)

 using namespace std;

 typedef long long ll;

 const int inf=0x3f3f3f3f;

 const int INF=0x3f3f3f3f3f3f3f3f;

 const int N=1e6+;

 const int M=;

 int n,a[N],mn,cnt[],ans[];

 int main()

 {

     int mn=inf;

     read(n);

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

         read(a[i]),mn=min(mn,a[i]);

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

         a[i]-=mn;

     int sum=;

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

         cnt[a[i]]++,ans[a[i]]++;

     if(!cnt[] && !cnt[] || cnt[] && !cnt[])

     {

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

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

             printf("%d ",a[i]+mn);

         puts("");

     }

     else

     {

         int ret=min(cnt[],cnt[]);

         int res=(cnt[]/)*;

         //printf("%d %d\n",ret,res);

         if(*ret>=res)

         {

             printf("%d\n",n-*ret);

             ans[]-=ret;

             ans[]-=ret;

             ans[]+=*ret;

         }

         else

         {

             ans[]+=res/;

             ans[]-=res;

             ans[]+=res/;

             printf("%d\n",n-res);

         }

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

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

                 printf("%d ",i+mn);

         puts("");

     }

     return ;

 }

 /*

 */

D题：是我写过最简单的D题，dfs计算一下每个深度的点有多少个，对于每个深度来说如果是奇数个点贡献是1，偶数个贡献是0。

 #include<bits/stdc++.h>

 #define fi first

 #define se second

 #define mk make_pair

 #define pii pair<int,int>

 #define read(x) scanf("%d",&x)

 #define sread(x) scanf("%s",x)

 #define dread(x) scanf("%lf",&x)

 #define lread(x) scanf("%lld",&x)

 using namespace std;

 typedef long long ll;

 const int inf=0x3f3f3f3f;

 const int INF=0x3f3f3f3f3f3f3f3f;

 const int N=1e6+;

 const int M=;

 vector<int> edge[N];

 int n,d[N];

 void dfs(int u,int de)

 {

     d[de]++;

     for(int v:edge[u])

         dfs(v,de+);

 }

 int main()

 {

     read(n);

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

     {

         int fa; read(fa);

         edge[fa].push_back(i);

     }

     dfs(,);

     int ans=;

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

         if(d[i]&)

             ans++;

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

     return ;

 }

 /*

 */

E题：比赛的时候一直看错题，以为是猜对的概率，题目是唯一确定答案的概率，一直调都不对，结果GG啦，其实也很简单，

统计一下点与点之间的情况，对于一种字符来说，第二张要翻开的卡的位置都是一样的，算一下这个概率就好啦。

#include<bits/stdc++.h>

#define fi first

#define se second

#define mk make_pair

#define pii pair<int,int>

#define read(x) scanf("%d",&x)

#define sread(x) scanf("%s",x)

#define dread(x) scanf("%lf",&x)

#define lread(x) scanf("%lld",&x)

using namespace std;

const int N=;

int n,cnt[][][N];

char s[N];

double mp[];

int main()

{

    sread(s+);

    n=strlen(s+);

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

    {

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

        {

            cnt[s[i]-'a'][s[j]-'a'][j-i]++;

            cnt[s[j]-'a'][s[i]-'a'][n-(j-i)]++;

        }

    }

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

    {

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

        {

            int tot=,sum=;

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

            {

                sum+=cnt[i][j][k];

                if(cnt[i][j][k]==)

                    tot++;

            }

            mp[i]=max(mp[i],1.0*tot/sum);

        }

    }

    double ans=;

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

        ans+=mp[s[i]-'a']/n;

    printf("%.12f\n",ans);

    return ;

}

/*

*/

F题：题目大意：给你n条线段覆盖的x轴，范围在1-m之间，有一个人开始询问，每次询问一个点的覆盖次数，问你最多几次之后

还是无法确定是不是有一个点被所有线段覆盖。

思路：这题想了好久。。。刚开始以为是和点被覆盖最大值有关，写了很久发现有问题，我们考虑对于两个点a,b来说，如果有一个

点c在a，b之间，且c < max (a, b) ，那么覆盖a的线段，和覆盖b的线段肯定不完全相同，如果完全相同，肯定有 c>=max(a,b)，矛盾。

所以我们的问题就变成了从里面选出尽可能多的点，使其的覆盖次数满足先增后减，然后就很开心地最长不下降子序列搞一搞就好啦。

 #include<bits/stdc++.h>

 #define fi first

 #define se second

 #define mk make_pair

 #define pii pair<int,int>

 #define read(x) scanf("%d",&x)

 #define sread(x) scanf("%s",x)

 #define dread(x) scanf("%lf",&x)

 #define lread(x) scanf("%lld",&x)

 using namespace std;

 const int N=1e5+;;

 int in[N],out[N],cnt[N],d[N],ans1[N],ans2[N];

 int n,m;

 int main()

 {

     read(n); read(m);

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

     {

         int l,r;

         read(l); read(r);

         in[l]++;

         out[r]++;

     }

     int all=;

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

     {

         all+=in[i];

         cnt[i]=all;

         all-=out[i];

     }

     ans1[]=;

     d[]=cnt[];

     int len=;

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

     {

         if(cnt[i]>=d[len])

         {

             d[++len]=cnt[i];

             ans1[i]=len;

         }

         else

         {

             int j=upper_bound(d+,d+len+,cnt[i])-d;

             ans1[i]=j;

             d[j]=cnt[i];

         }

     }

     ans2[m]=;

     d[]=cnt[m];

     len=;

     for(int i=m-;i>=;i--)

     {

         if(cnt[i]>=d[len])

         {

             d[++len]=cnt[i];

             ans2[i]=len;

         }

         else

         {

             int j=upper_bound(d+,d+len+,cnt[i])-d;

             ans2[i]=j;

             d[j]=cnt[i];

         }

     }

     int ans=;

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

         ans=max(ans,ans1[i]+ans2[i]-);

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

     return ;

 }

 /*

 */

巴特西

Codeforces Round #468 (Div. 2, based on Technocup 2018 Final Round)

最新文章

热门文章