wsnの博客

记录学习经历和一点点日常

0%

排位赛题解

发表于 分类于 Valine：
本文字数： 4.7k 阅读时长 ≈ 4 分钟

引言

这篇题解主要写写这几天排位赛做的题目，总结一下。因为会的题实在太少，所以我估计两篇博客就可以写完了……菜鸡哭泣qwq

DAY1

第一天只过了一道题，其中有一道方法思路都对了，但是因为一个很小的错误导致没有A掉，挺可惜的，毕竟好不容易碰到一道会的题目qwq

Distinct Sub-palindromes

题意

有T组测试样例，每组给出一个整数n，求出长度为n的字符串的回文子串数目最少的字符串的数目。

“a”、“aa”、”aaa“都算一个回文字符串。

  • 结果模998244353

思路

这道题也是自闭了很久的题，一开始根据样例，以为直接模998244353就可以了，当成了一个快速幂的板子题。但其实不是qwq。后来认真思考后发现，当n大于3时，三个不相同的字母循环的序列是回文子串数目最少的字符串，例如abcabcabca这种，只有”a”、”b“、”c“三个回文子串，答案是（所以给出的那个让你模的数字就是个坑！！！）；小于等于3的时候是。知道了做法，程序就很简单了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include <utility>
#define eps 1e-10
#define q first
#define a second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAX=50010;
const double pi = acos(-1.0);
typedef long long ll;


int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(n<=3)
        cout<<pow(26,n)<<endl;
        else
        cout<<26*25*24<<endl;
    }
     return 0;
}

Leading Robots

题意

有n个机器人，每个机器人有一个初始位置和一个加速度，有公式v(t)=at，各机器人初始速度为零。当一个机器人是唯一一个第一的时候，我们叫这个机器人为领头机器人，问整个过程中一共出现了多少个领头机器人。

  • 有 T(1≤ T≤50)组测试数据
  • 每组测试数据有N(0 < N≤ 50000)个机器人，每个机器人给出p(位置)和a(加速度)

思路

这道题我看完后第一个想到的就是n条一次直线投影到x轴上，从上往下看最多能看到几条直线。因为我做过，所以我第一个开的就是这个题，但是因为那个小错误死活调不出来，wa了十几发qwq……

这道题的关键是能想到把问题转化成一次直线，即以$t^2$为横坐标，以p为纵坐标，每个机器人的运动等效为一次直线，如图：

1

然后将每个点按位置从大到小排序，位置相同按加速度从大到小排序，然后维护一个单调栈就可以了。

遍历第二个点到第n个点，如果当前结点的加速度大于栈顶结点，则这个机器人一定能追上栈顶机器人，但要判断这个直线会不会栈顶直线盖住，即在栈顶机器人追上前一个机器人top-1（栈顶的第二个机器人）之前，先追上top-1机器人，如图：

2

这样的话，栈顶机器人就不会成为领头机器人，要pop出栈。这样每次选取栈顶前两条直线和新直线判断，直到在栈顶机器人之后追上前一个机器人，如图：

![3][3.png]

最后，由于题目中会给出位置和速度完全一样的机器人，而这两个机器人都不能成为领头机器人，所以要进行去重。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include <utility>
#define eps 1e-10
#define q first
#define a second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAX=50010; 
int c[MAX];//直线栈 
int top=0; 
typedef struct
{
    double q;
    double a;
}node;
map<pii,int>mp;
node b[MAX];//存加速度和位置 
bool cmp(node a,node b)
{
    if(a.q!=b.q)
    return b.q<a.q;
    else
    return b.a<a.a;
}
bool f1(node x,node y,node z)
{
    return (x.q-z.q)*(y.a-x.a)-(x.q-y.q)*(z.a-x.a)<=0;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        mp.clear();
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&b[i].q,&b[i].a);
            pii t;
            t.q=b[i].q;
            t.a=b[i].a;
            mp[t]++;
            //cout<<mp[t]<<endl;

        }
        sort(b,b+n,cmp);//排序 
        //cout<<b[0].q<<endl;
        top=0;
        for(int i=1;i<n;i++)//遍历后n-1条直线 
        {
            if(b[i].a>b[c[top]].a)//如果直线斜率大于栈顶直线，进入判断 
            { 
                 while(top>0&&f1(b[c[top-1]],b[c[top]],b[i]))//如果栈顶两条直线相交的坐标大于t，pop出栈顶直线 
                {
                    top--;
                }
                c[++top]=i;
       
            }
        }
        int ans=top+1;
        for(int i=0;i<=top;i++)
        {
            pii t;
            t.a=b[c[i]].a;
            t.q=b[c[i]].q;
            if(mp[t]>1) ans--;
        }
        printf("%d\n",ans);   
    }
    return 0;
}

DAY2

第二天的比赛极为凄惨的爆零了，三个人开了三个题，最后全都超时了qwq

Lead of Wisdom

题意

有一个游戏，需要玩家搭配装备。每一类装备有四种属性加成a,b,c,d，每类装备只能选择一种，给出装备的种类k，装备数量n，根据公式

求出最大的战斗力是多少

  • 有T组数据，
  • 每组数据有n个装备，k个装备种类，1≤n,k≤50

思路

这道题因为数据都很小，所以我想到的就是直接暴力，但是搜索树他卡了一个数据，就一直超时，特别难受。

这道题暴力不会超时，但是第i类装备数目为0的和数目为1的都不能加入搜索树，否则就会超时qwq

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int N=100;
map<int,int>mp;
struct node
{
    ll a;
    ll b;
    ll c;
    ll d;
}aa[N][N];
int num[N];
ll ans;
int n,k;
int ss[N];
int top;
void find(ll a,ll b,ll c,ll d,int s)
{
    if(s==top)
    {
        ll t=a*b*c*d;
        ans=max(t,ans);
        return;
    }
    for(int i=0;i<num[ss[s]];i++)
    {
        find((a+aa[ss[s]][i].a),(b+aa[ss[s]][i].b),(c+aa[ss[s]][i].c),(d+aa[ss[s]][i].d),s+1);
    }
}



int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        top=0;
        for(int i=0;i<=k;i++)
        num[i]=0;
        mp.clear();
        ll at=100,bt=100,ct=100,dt=100;
        for(int i=0;i<n;i++)
        {
            int t,a1,b,c,d;
            cin>>t>>a1>>b>>c>>d;
            aa[t][num[t]].a=a1;
            aa[t][num[t]].b=b;
            aa[t][num[t]].c=c;
            aa[t][num[t]].d=d;
            num[t]++;
            mp[t]++;
        }
        for(int i=1;i<=k;i++)
        {
            if(mp[i]==1)
            {
                at+=aa[i][0].a;
                bt+=aa[i][0].b;
                ct+=aa[i][0].c;
                dt+=aa[i][0].d;
            }
            else if(mp[i]>1)
            {
                ss[top++]=i;
            }
        }
        ans=100*100*100*100;
        find(at,bt,ct,dt,0);
        printf("%lld\n",ans);
    }
    return 0;
}