杭电多校第一场（DI）

D - Distinct Sub-palindromes （签到）

 传送门

题意：长度为 n 且含有最少回文子串的不同字符串

是我理解力太差了？是

思路：（1）n <= 3，最少回文子串的个数就是 n ，答案是26 ^ n

          （2）n > 3，最少回文子串的个数是3，构造成这样子：abcabcabc......，答案就是26 * 25 * 24

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;

int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int ans;
        if(n == 1) ans = 26;
        else if(n == 2) ans = 26 * 26;
        else if(n == 3) ans = 26 * 26 * 26;
        else ans = 26 * 25 * 24;
        printf("%d\n", ans);
    }
    return 0;
}

I - Leading Robots（思维 + 单调栈）

题意：

有 n 个机器人赛跑，给出每个机器人的起始横坐标和加速度，同一时间开始向x轴正方向跑，跑道无穷长，问有多少个机器人在赛跑过程中领先过所有机器人

思路：

先排序，第一关键字是位置从大到小，第二关键字是加速度从大到小，由于位置落后的机器人只有在加速度大于前方的机器人时才有可能超越，所以只有加速度 > 当前最大加速度的机器人才需要入栈，入栈之前判断是这个机器人先追上上上个领先的机器人还是上一个机器人先追上上上个领先的机器人，如果是前者，说明在上个机器人追上上上个之前，该机器人已经追上了它，也就是它没有领先过，pop出栈。最后在栈里的元素还要去重才是答案。

emm说几个坑点吧，

（1）在判断时间的时候除法改用乘法，int相乘还可能爆掉，long long保险些

（2）机器人b和位置靠后的机器人c同时追上领先的机器人a时也是非法的，下一瞬间加速度大的机器人，也就是机器人c，会超越其他两个机器人从而领先，所以b从未领先过，pop掉，所以在judge里加了等号

用map记录的，没加快读也过了，看大佬们有不用map的，也搬来了，在后边

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 5e4 + 7;

struct node {
    ll a, p;
    bool operator < (const node &x)const {
        if(p != x.p) return p > x.p;
        else return a > x.a;
    }
}s[N], st[N];

bool judge(node x, node y, node z) {
    return (z.p - x.p) * (y.a - z.a) <= (z.p - y.p) * (x.a - z.a);    //同时追上也要pop掉前一个
}

int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        map<node, int>mp;
        for(int i = 1; i <= n; ++i) {
            scanf("%lld%lld", &s[i].p, &s[i].a);
            mp[s[i]]++;
        }
        sort(s + 1, s + n + 1);
        int top = 0;
        st[++top] = s[1];
        for(int i = 2; i <= n; ++i) {
            if(st[top].a >= s[i].a) continue;    //加速度 <= 当前最大加速度 不可能追上
            while(top > 1 && judge(s[i], st[top], st[top - 1]))
                top--;
            st[++top] = s[i];
        }
        int ans = 0;
        for(int i = 1; i <= top; ++i)
            if(mp[st[i]] == 1) ans++;
        printf("%d\n", ans);
        mp.clear();
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 1e5 + 7;

inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-') f = -1;
        ch=getchar();
    }
    while(isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch=getchar();
    }
    return x * f;
}

inline void write(ll x)
{
    if(x < 0) x = -x, putchar('-');
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

struct node {
    ll a, p, id;
}s[N], st[N], ss[N];

bool vis[N];

bool cmp(node x, node y) {
    if(x.p != y.p) return x.p > y.p;
    else return x.a > y.a;
}

bool judge(node x, node y, node z) {
    return (z.p - x.p) * (y.a - z.a) <= (z.p - y.p) * (x.a - z.a);
}

int main() {
    ll t, n;
    t = read();
    while(t--) {
        n = read();
        for(ll i = 1; i <= n; ++i) {
            ss[i].p = read(), ss[i].a = read();
            ss[i].id = i;
            vis[i] = 0;
        }
        sort(ss + 1, ss + n + 1, cmp);
        int cnt = 0;
        s[++cnt] = ss[1];
        ll maxx = ss[1].a;
        for(int i = 2; i <= n; ++i) {
            if(ss[i].a == ss[i - 1].a && ss[i].p == ss[i - 1].p) {
                vis[ss[i].id] = 1;
                vis[ss[i - 1].id] = 1;
            }
            if(ss[i].a > maxx) {
                s[++cnt] = ss[i];
                maxx = ss[i].a;
            }
        }
        ll top = 0;
        for(int i = 1; i <= cnt; ++i) {
            while(top > 1 && judge(s[i], st[top - 1], st[top - 2]))
                top--;
            st[top++] = s[i];
        }
        ll ans = 0;
        for(ll i = 0; i < top; ++i)
            if(!vis[st[i].id]) ans++;
        write(ans), printf("\n");
    }
    return 0;
}