[题解|总结|分析] 2021年度训练联盟热身训练赛第七场

目录 按AC先后顺序

Problem A: Adolescent Architecture(排序+思维)

题意

输入

给你n个(正方体积木或者圆住积木),
让你一层放一个 下面n行 一个string表示(正方体or圆柱体),
一个int表示该方块的半径or边长

条件限制:

摆出来的积木形状必须是塔的形状
允许轮廓相交

输出

如果不可行输出 impossible
否则 从上到下输出 string 和 int

思路分析

因为是塔 所以我们需要对这个数组进行排序
如果遇到了圆柱体 那么我们就分两种情况判断
一种是 圆柱体+ 正方体
一种是 圆柱体+圆柱体

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
double q2 = 1.414;
const int N = 110;
int n;
struct node
{
    double a;
    int op;
} num[N];
bool cmp(node x,node y )
{
    if(x.a==y.a)
        return x.op<y.op;
    return x.a<y.a;
}
int main()
{
    cin>>n;

    double  x;
    string s;
    for(int i=1; i<=n; i++)
    {
        cin>>s;
        cin>>x;
        if(s == "cube")
        {
            num[i].a = x;
            num[i].op = 1;
        }
        else
        {
            num[i].a = x*2;
            num[i].op = 0;
        }
    }

    sort(num+1,num+1+n,cmp);
    for(int i = n;i>=2;i -- )
    {
        if(num[i].op == 0 && num[i-1].op == 1)
        {
            double pd = num[i-1].a *q2 ;

            if(pd>num[i].a)
            {
                cout<<"impossible";
                return 0;
            }
        }
        if(num[i].op ==0 && num[i-1].op == 0)
        {
            if(num[i].a >num[i-1].a)
            {
                cout<<"impossible";
                return 0;
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(num[i].op == 1)
        {
            cout<<"cube"<< " "<<num[i].a<<endl;
        }
        else
        {
            cout<<"cylinder"<<" "<<(int)num[i].a/2<<endl;
        }
    }
    return 0;
}

总结

这题还是A慢了, 1个半小时才A出来
主要还是单词认不出来,影响到了思路分析,(圆柱体cylinder 正方体cube)

Problem F: Flip Flow(模拟)

输入

给你一个沙漏,沙漏中有 s个沙子(一个沙子代表1s),问从t时间开始计时 沙子什么时候漏完
t s n ,n表示在什么时间 沙漏反转
沙漏在0s的状态还未开始漏

输出

输出从t开始之后多久漏完

思路分析

直接走模拟即可

总结

emm 签到题,但是英语量也挺多的,还真卡在A题 都没跑这道题了

code:

#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    int t,s,n;
    cin>>t>>s>>n;
    int a[1005];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int up,down;
    down=s;
    int k=1;
    for(int i=1;i<=t;i++)
    {
        if(up>0)
        {
            up--;
            down++;
        }
        if(i==a[k])
        {
            swap(up,down);
            k++;
        }
    }
    int ans=up;
    cout<<up<<endl;
    return 0;
}

(*牛逼)Problem M: Mixtape Management(构造+思维)

输入

给你一个 n 表示p的全排列的长度
下面p(1~n)

条件限制:

输出的数需要满足字典序
且第i个数 要是 第p[i]个小的数

输出:

输出满足条件的序列

思路分析

这题想了挺久,一开始我还把正确思路的方向给否定了
因为需要构造字典序,所以我们贪心地想 1 12 123 1234 12345 这种如何满足第二条件
经过贪心的再贪心,发现我们只需要在 第一个小的数的位数上多添几个0即可
这样就满足了p[i]个小的数

总结

第一次碰到这种构造题,有点自乱阵脚的感觉,但是和队友讨论之后,加上自己的思考发现还是愚人自愚了

code:

const int N  = 110;
int p[N];
int n;
struct node
{
    string s;
}ans[N];
int main()
{
    cin>>n;
    int maxn = 0 ;
    int idx = 0;
    for(int i=1; i<=n; i++)
    {
        cin>>p[i];
        maxn = max(p[i],maxn);
        if(p[i] == 1)
        idx = i;
    }
    for(int i=1;i<=n;i++)
    {
        int id = 0;
        for(int j=1;j<=i%10;j++)
        {
            ans[i].s+=('0'+j);
            id++;
        }
        for(int j=1;j<=(idx+(p[i]-id));j++)
        ans[i].s+='0';
    }
    for(int i=1;i<=n;i++)
    cout<<ans[i].s<<" ";
    return 0;
}

Problem L: Lexicographical Lecturing(水题,暴力+优化)

输入

输入n(那个字符串),m(每个字符串的长度)
下面n行按照字典序给出的字符串
问所有字符串的公共最小不相等子串

输出

输出子串的L和R

思路分析:

分析数据范围 n<=500, m<=2e4(210^4)
暴力做法 n
m 也就是10^7 有点玄乎但是没关系,我们分两边来搞即可

总结

题目一定要放大来看,不要一半题目一半IDE界面,搞得我把2e4看成2e5想了挺久的算法

code:

int main()
{
    read(n),read(m);
    for(int i=1; i<=n; i++)
        cin>>s[i];

    int idx = 0;
    for(int i=0; i<=m; i++)
    {
        bool flag  = false;
        for(int j = 1; j<=n; j++)
        {
            if(s[1][i]!=s[j][i])
            {
                idx = i;
                flag  =true;
                break;
            }
        }
        if(flag)
            break;
    }
    int r = 0;
    for(int i=m-1; i>=0; i++)
    {
        bool flag  = false;
        for(int j = 1; j<=n; j++)
        {
            if(s[1][i]!=s[j][i])
            {
                r = i;
                flag  =true;
                break;
            }
        }
        if(flag)
            break;
    }
    cout<<idx+1<<" "<<r+1;
    return 0;
}

Problem K: Knightly Knowledge(离散+贪心)

输入

给你一个n和m ,
n表示教堂的数量,m表示石碑是数量
下面n行输入教堂的x y
下面m行输入教堂的x y

条件:

对于每个石碑所在的X和Y 都会有一个直线
如果一个教堂被两个直线所经过 那么这个教堂被称为强大教堂
只允许你放置一个石碑

输出

放置的石碑的x和y
输出最大能变成的强化教堂数量

思路分析:

因为我们的坐标存在负数 所以我们需要用map来处理
然后我们贪心的找 只有一条直线经过的教堂
最后我们枚举一下最大值即可

总结:

做题要想清楚什么是可以通过某些量直接变化过来的
因为没有搞懂石碑的x和y到底怎么来 所以想了挺久
但是最后发现我们只需要通过两个直线的交线就可以确定石碑的xy了所以就没必要考虑怎么来的了

code

int n,m;
map<int,int> mx;
map<int,int> my;
map<int,int> sx;
map<int,int> sy;
int main()
{
    cin>>n>>m;
    int ans = m;
    while(n -- )
    {
        int x,y;
        cin>>x>>y;
        mx[x] ++;
        my[y] ++;

    }
    while(m -- )
    {
        int x,y;
        cin>>x>>y;
        if(mx[x]<2 && my[y]<2)
        {
            sx[x] ++;
            sy[y] ++;
        }
    }
    map<int,int>::iterator it;
    map<int,int>::iterator it2;
    int maxn = 0;
    int ansx,ansy;

    for(it=sx.begin(); it!=sx.end(); it++)
    {
        for(it2=sy.begin(); it2!=sy.end(); it2++)
        {
            if(mx[it->first] >=1 &&my[it2->first]>=1)
            {
                int sum  =sx[it->first]+ sy[it2->first];
                if(maxn < sum)
                {
                    maxn = sum;
                    ansx = it->first;
                    ansy = it2->first;
                }
            }
        }
    }

    cout<<ansx<<" "<<ansy<<endl;
    cout<<maxn;
    return 0;
}
上一篇:20201005 漆黑列车载运数个谎言,金色丝线将瞬间一分为二,神在夏至祭降下了神谕


下一篇:Running Median