Codeforces Round #423 Di v. 2（这可能是我写的最认真的一套题了，接下来会继续的）

能力有限，E题数状数组没学， F题没搜到题解，只能把思维题先过了，每天抽时间学算法，加油。
A：自己模拟一下，如果你是餐厅经理会怎么做就很简单了。

/*If I get TLE , it is good.If I get AC,it's NICE !*/

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e6+10;
const ll mod=1e9+7;
int a[MAXN];
int main(void)
{
    int n,cnt1,cnt2;
    scanf("%d%d%d",&n,&cnt1,&cnt2);
    int cnt3=0;
    int deny=0;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
    {
        if(a[i]==1)
        {
            if(cnt1>=1)
                cnt1--;
            else if(cnt2>=1)
                cnt2--,cnt3++;
            else if(cnt3>=1)
                cnt3--;
            /*else if(cnt2>=1) cnt2--,cnt3++;*/
            else deny++;
        }
        else if(a[i]==2)
        {
            if(cnt2>=1) cnt2--;
            else    deny+=2;
        }
    }
    printf("%d\n",deny);
}

B：这题一开始就想错了，没想到可以往左边和右边或者上边和下边去补形状，一直就是WRONG ANSWER ，看了题解才知道，其实不一定

/*If I get TLE , it is good.If I get AC,it's NICE !*/
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=100000+10;
const ll MOD=1e6+7;
char mp[105][105];
int x[105];
int y[105];
int main(void)
{
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    int m,n;
    int indexx=0,indexy=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%s",mp[i]);
    int cnt=0;
    int maxx=-INF;
    int minx=INF;
    int maxy=-INF;
    int miny=INF;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(mp[i][j]=='B')
            {
                cnt++;
                maxx=max(maxx,i);
                minx=min(minx,i);
                maxy=max(maxy,j);
                miny=min(miny,j);
            }
        }
    }
    if(cnt==0)
    {
        printf("1\n");
        return 0;
    }
    // 用了STL的min_element 坑爹啊，再也不用了
    /*int maxx=*max_element(x,x+indexx); int maxy=*max_element(y,y+indexy); int minx=*min_element(x,x+indexx); int miny=*min_element(y,y+indexy);*/
    //printf("%d--%d--%d--%d--\n",maxx,minx,maxy,miny);
    int dx=maxx-minx+1;
    int dy=maxy-miny+1;
    if(dx>dy)
    {
        if(m>=dx)
            printf("%d\n",dx*dx-cnt);
        else
            printf("-1\n");
    }
    else
    {
        if(n>=dy)
            printf("%d\n",dy*dy-cnt);
        else
            printf("-1\n");
    }
}

C：下面给出对比，官方题解，和我的TLE代码。感觉思路和官方题解基本一样，重点在实现的过程中，官方代码用了 sort 。我的用了个mark，里面还有各种判断。细节决定成败啊，运行时间差这么多，我估计是差在判断的过程里，节省了很多时间。，还有暴露出来的问题有STL 的容器用的不太熟练。

/*If I get TLE , it is good.If I get AC,it's NICE !*/  官方
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e6+10;
const ll mod=1e9+7;
string s[MAXN];
string ans;
vector<pair<int,int> > temp;  // 把字符和节点连接起来
int main(void)
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int q;
        cin >> s[i];
        scanf("%d",&q);
        for(int t=1;t<=q;t++)
        {
            int x;
            scanf("%d",&x);
            temp.push_back(make_pair(x,i));
        }
    }
        sort(temp.begin(),temp.end());// 对x排序
        int index=1;  // 当前应该插入的数组位置
        for(int i=0;i<temp.size();i++)
        {
            int t1=temp[i].first,t2=temp[i].second;// t1存节点，t2存字符数组对应下标
            //对于 t1 和 index 关系，讨论一下
            if(t1>index)
            {
                while(t1>index)
                {
                    ans+='a';
                    index++;
                }
            }
            for(int j=index-t1;j<s[t2].length();j++)
            {
                ans+=s[t2][j];
                index++;
            }
        }
    cout << ans << endl;
}

TLE代码：

/*If I get TLE , it is good.If I get AC,it's NICE !*/
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e7+10;
const ll mod=1e9+7;
char str[MAXN];
char temp[MAXN];
int mark[MAXN]= {0};
int mmax=-1;
int main(void)
{
    int n;
    cin >> n;
    memset(mark,0,sizeof(mark));
    while(n--)
    {
        int t;
        int index=1;
        scanf("%s",temp+1);
        //printf("%s\n",temp+1);
        scanf("%d",&t);
        int len=strlen(temp+1);
        int d=1;
        for(int i=1; i<=t; i++)
        {
            int a;
            scanf("%d",&a);
            if(mark[a]<len)
            {
                mmax=max(mmax,len+a-1);  //str+a temp+1
                int x=a+mark[a];
                for(int i=mark[a]+1;i<=len;i++)
                {
                    str[x++]=temp[i];
                }
                mark[a]=len;
                /*for(int i=1; i<=len; i++) { str[a]=temp[i]; a++; }*/
                /* for(int i=1;i<=10;i++) { printf("%c-",str[i]); } printf("\n");*/
            }
        }
    }
    for(int i=1; i<=mmax; i++)
    {
        if(str[i]<'a' || str[i]>'z')
        {
           printf("a");
        }
        else
            printf("%c",str[i]);
    }
    printf("\n");
}

D：我以为D题会非常难得，涉及算法，其实发现如果题目是6题，前面三四题都是思维题。这题想到简单，想不到做不出来。看到只能连接1条，讲道理会联想的树的叶子节点，然后k确定了，总的n确定了，让你做到两个叶子节点最大值的距离最小化。那么想想就知道（不知道怎么证明）肯定是深度大家均摊，最大值才会最小，接下来找规律输出一下就可以了

Codeforces Round #423 Di v. 2（这可能是我写的最认真的一套题了，接下来会继续的）

全站热榜