Educational Codeforces Round 64 (Rated for Div. 2) A，B，C，D，E，F

比赛链接：

https://codeforces.com/contest/1156

A. Inscribed Figures

题意：

给出$n(2\leq n\leq 100)$个数，只含有1，2，3，分别代表圆，高与底相等的三角形，正方形

$a_{i+1}$在$a_{i}$的里面，$a_{i+1}$的面积尽可能的大

求不同的交点个数

分析：

注意正方形里面一个圆，再里面一个三角形的时候，有一个交点重合

ac代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=1e5+10;

const int maxm=200000*2+10;

const int mod=1e9+7;

int num[maxn];

ll ans;

int main()

{

    int n;

    scanf("%d",&n);

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

        scanf("%d",&num[i]);

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

    {

        if(num[i]==1)

        {

            if(num[i-1]==2)ans+=3;

            if(num[i-1]==3)ans+=4;

        }

        if(num[i]==2)

        {

            if(num[i-1]==1)

            {

                if(i-2>=1&&num[i-2]==3)

                    ans+=2;

                else ans+=3;

            }

            if(num[i-1]==3)ans=1e18;

        }

        if(num[i]==3)

        {

            if(num[i-1]==1)ans+=4;

            if(num[i-1]==2)ans=1e18;

        }

    }

    if(ans>=1e17)

        cout<<"Infinite"<<endl;

    else

    {

        cout<<"Finite"<<endl;

        cout<<ans<<endl;

    }

    return 0;

}

B. Ugly Pairs

题意：

给出一个字符串$s(1\leq |s|\leq 100)$，重排它们，让每对相邻的字符在$ascii$表中不相邻

分析：

将$a,c,e,g...$放一个集合，将$b,d,f,h...$放另一个集合，看它们是否能连线在一起

ac代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=100+10;

const int maxm=200000*2+10;

const int mod=1e9+7;

int num[30];

char word[maxn];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        getchar();

        scanf("%s",word);

        int gkd=0;

        for(int i=0;word[i];i++)

            if((int)word[i]%2!=(int)word[0]%2)gkd=1;

        if(gkd==0)

        {

            printf("%s\n",word);

            continue;

        }

        memset(num,0,sizeof(num));

        for(int i=0; word[i]; i++)

            num[word[i]-'a']++;

        int a,b,fla=0;

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

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

                if(i%2==0&&j%2==1&&abs(i-j)!=1&&num[j]&&num[i])

                {

                    a=i,b=j;

                    fla=1;

                }

        if(fla==0)

        {

            printf("No answer\n");

            continue;

        }

        num[a]--;

        num[b]--;

        for(int i=0; i<26; i+=2)

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

                printf("%c",(char)(i+'a'));

        printf("%c%c",(char)(a+'a'),(char)(b+'a'));

        for(int i=1; i<26; i+=2)

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

                printf("%c",(char)(i+'a'));

        printf("\n");

    }

    return 0;

}

C. Match Points

题意：

给出n个数，组成最多的数对，满足$|a_i-a_j|\geq d$

分析：

这题一看就是贪心，但是，我的策略是，用最小的去匹配最小能匹配的，wa

例如：

4 2

1 3 4 7

最优解是$(1,4)(3,7)$

正确匹配方式是，用前面一部分匹配后面一部分，对答案二分即可

ac代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=2e5+10;

const int maxm=200000*2+10;

const int mod=1e9+7;

int n,d,num[maxn];

bool check(int x)

{

   int a=x,b=n;

   for(;a>=1;a--,b--)

    if(num[b]-num[a]<d)return 0;

   return 1;

}

int main()

{

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

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

        scanf("%d",&num[i]);

    sort(num+1,num+1+n);

    int st=0,en=n/2;

    while(st!=en)

    {

        int md=(st+en)/2;

        if(check(md+1))st=md+1;

        else en=md;

    }

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

    return 0;

}

D. 0-1-Tree

题意：

给出一颗节点数为$n$的树，每条边有一个属性0或者1

求出点对$(a,b)$的数量，满足$a$到$b$的最短路线上，经过1之后不经过0

分析：

这样的点对有三种情况

1.$(a,b)$的路径只包含0

2.$(a,b)$的路径只包含1

3.$(a,b)$的路径先全是0，再全是1

对于题目的样例有$ans=5\times 5-5+3\times 3-3+4\times 2=34$

用两个并查集记录0和1的集合和大小。

ac代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=200000+10;

const int maxm=200000*2+10;

const int mod=1e9+7;

int boss[maxn][2];

ll siz[maxn][2],ans;

int ma[maxn][2],n;

int fin0(int x)

{

    if(boss[x][0]==x)

        return x;

    return boss[x][0]=fin0(boss[x][0]);

}

int fin1(int x)

{

    if(boss[x][1]==x)

        return x;

    return boss[x][1]=fin1(boss[x][1]);

}

void uni0(int a,int b)

{

    boss[fin0(a)][0]=fin0(b);

}

void uni1(int a,int b)

{

    boss[fin1(a)][1]=fin1(b);

}

int main()

{

    scanf("%d",&n);

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

        boss[i][0]=boss[i][1]=i;

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

    {

        int a,b,c;

        scanf("%d %d %d",&a,&b,&c);

        ma[a][c]=b;

        ma[b][c]=a;

        if(c==1)

            uni1(a,b);

        else

            uni0(a,b);

    }

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

    {

        siz[fin0(i)][0]++;

        siz[fin1(i)][1]++;

        //cout<<fin1(i)<<endl;

    }

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

    {

        if(boss[i][1]==i)

        {

            //cout<<siz[i][1]<<endl;

            ans+=siz[i][1]*siz[i][1]-siz[i][1];

        }

        if(boss[i][0]==i)

        {

           //cout<<siz[i][0]<<endl;

            ans+=siz[i][0]*siz[i][0]-siz[i][0];

        }

        if(ma[i][0]&&ma[i][1])

        {

            ans+=(siz[fin0(i)][0]-1)*(siz[fin1(i)][1]-1);

             //cout<<i<<" "<<(siz[fin0(i)][0]-1)*(siz[fin1(i)][1]-1)<<endl;

        }

        //cout<<"ans="<<ans<<endl;

    }

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

    return 0;

}

E. Special Segments of Permutation

题意：

给出$n(3 \le n \le 2 \cdot 10^5)$个数，满足$1 \le p_i \le n$，并且每个数只出现一次

计算区间$(l,r)$的数量，满足$p_l + p_r = \max \limits_{i = l}^{r} p_i$

分析：

用单调栈求出以坐标$i$为最大值的最大区间

然后遍历区间左边或者右边的数，看是否能在另一边找到可以匹配的数

遍历左边或者右边，取决于左右区间的大小，不然一定超时

最初我用递归分治去做，ac了，但是，题目的数据很少，我自己造的数据，会栈溢出

ac代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=2e5+10;

const int maxm=200000*2+10;

const int mod=1e9+7;

struct Node

{

    int l,r,x;

}node[maxn];

int sta[maxn],top=-1,n,pos[maxn];

int main()

{

    scanf("%d",&n);

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

    {

        scanf("%d",&node[i].x);

        pos[node[i].x]=i;

        node[i].l=i;

    }

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

    {

         while(top!=-1&&node[i].x>node[sta[top]].x)

         {

             node[sta[top]].r=i-1;

             node[i].l=node[sta[top]].l;

             top--;

         }

         sta[++top]=i;

    }

    while(top!=-1)

        node[sta[top]].r=n,top--;

    int ans=0;

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

    {

        if(i-node[i].l<node[i].r-i)

        {

            for(int j=node[i].l;j<i;j++)

            {

                int x=pos[node[i].x-node[j].x];

                if(x>i&&x<=node[i].r)ans++;

            }

        }

        else

        {

            for(int j=i+1;j<=node[i].r;j++)

            {

                int x=pos[node[i].x-node[j].x];

                if(x>=node[i].l&&x<i)ans++;

            }

        }

    }

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

    return 0;

}

F. Card Bag

题意：

有$n(2 \le n \le 5000)$个卡片在背包里面，每个卡片有一个属性$a_i(1\leq a_i\leq n)$

每次取出一张卡片属性看作$x$，如果上一张有卡片，把上一张卡片属性看作$y$

如果$x=y$，胜利

如果$x<y$，失败

如果$x>y$，游戏继续

求胜利的期望概率

分析：

这题一看就是概率DP

定义$prob[x][y]$为抽出$x$张不重复的卡牌，以$y$作为最后一张的概率

定义$num[x]$为$x$卡牌的数量

那么：

$$prob[x][y]=\frac{num[y]}{n-x+1}\times \sum_{i=1}^{y-1}prob[x-1][i]$$

再枚举所有胜利的情况，抽$x$张牌，以$y$为最后两张的概率

$$ans=ans+prob[x-1][y]\times \frac{num[y]-1}{n-x+1}$$

ac代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=5e3+10;

const int maxm=200000*2+10;

const int mod=998244353;

ll num[maxn];

ll ans,sum[maxn],prob[maxn][maxn],inv[maxn];

ll qpow(ll x,ll y)

{

    ll res=1,k=x;

    while(y)

    {

        if(y&1)res=res*k%mod;

        k=k*k%mod;

        y/=2;

    }

    return res;

}

int main()

{

    int n;

    scanf("%d",&n);

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

        inv[i]=qpow(i,mod-2);

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

    {

        int x;

        scanf("%d",&x);

        num[x]++;

    }

    for(int i=1;i<=n;i++)//prob[x][y]为已经选择了x个数，末尾为y的概率

    {

        prob[1][i]=num[i]*inv[n]%mod;

        for(int len=2;n-len+1>0;len++)

                prob[len][i]=sum[len-1]*num[i]%mod*inv[n-len+1]%mod;

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

            sum[len]=(sum[len]+prob[len][i])%mod;//sum[len]为prob[len][x]的和

    }

    for(int i=1;i<=n;i++)//枚举胜利的所有情况，选择len+1个数，并且以i作为结尾

        if(num[i]>=2)

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

                ans=(ans+prob[len][i]*(num[i]-1)%mod*inv[n-len]%mod)%mod;

    cout<<ans<<endl;

    return 0;

}

总结：

A.没考虑到交点重合的情况，wa了很多发，我应该模拟所有情况的

B.比赛的时候没有思路

C.贪心的策略错了，导致wa了还不知道原因

贪心是最难的算法Orz

E的数据有点少，我可以自己hack我的代码，第一次遇到cf数据有漏洞

栈的深度最大是$5\times 10^{4}$左右，以后要注意

巴特西

Educational Codeforces Round 64 (Rated for Div. 2) A，B，C，D，E，F

比赛链接：

A. Inscribed Figures

B. Ugly Pairs

C. Match Points

D. 0-1-Tree

E. Special Segments of Permutation

F. Card Bag

总结：

最新文章

热门文章