头像

松鼠爱葡萄


访客:1588

离线:5小时前



#include <iostream>

using namespace std;

const int N = 110;

int n;
string s[N];

int main()
{
    cin >> n;
//    把回车读取, 再读取每一行
    getchar();
    for (int i = 0; i < n; i ++ ) getline(cin, s[i]);

//    后缀长度为 1
//    后缀长度为 2
//    ... 直到sf.size() == s[0].size() 暴力枚举每一种可能的公共后缀
    for (int k = s[0].size(); k; k -- )
    {
        string sf = s[0].substr(s[0].size() - k);
        bool is_matched = true;

        for (int i = 1; i < n; i ++ )
            if (k > s[i].size() || s[i].substr(s[i].size() - k) != sf)
            {
                is_matched = false;
                break;
            }

        if (is_matched)
        {
            cout << sf << endl;
            return 0;
        }
    }

    puts("nai");

    return 0;
}



#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;

    if (s[0] == '-') cout << '-';

    int k = s.find("E");
//    +1.23400E-03 中 取出 123400
//    并且将会转化成 0.123400
    string a = s[1] + s.substr(3, k - 3);
    int b = stoi(s.substr(k + 1));
//    小数点向左移动一位,缩小十倍,b++
    b ++ ;

//    +1.23400E-03 -> 0.00 123400
    if (b <= 0) a = "0." + string(-b, '0') + a;
//    -1.2E+10 -> -12 000 000 000
    else if (b >= a.size()) a += string(b - a.size(), '0');
//    +1.234E2 -> 123.4
    else a = a.substr(0, b) + '.' + a.substr(b);

    cout << a << endl;

    return 0;
}



#include <iostream>
#include <cstring>

using namespace std;

string change(string a, int n)
{
//    找到小数点的位置,从0开始计数
    int k = a.find(".");
//    如果字符串中没有 ".",在末尾给它加上一位 "."
    if (k == -1) a += '.', k = a.find(".");

//    去除 ".",做成一个新的字符串s
    string s = a.substr(0, k) + a.substr(k + 1);
//    去除前导0
    while (s.size() && s[0] == '0') s = s.substr(1), k -- ;

//    如果字符串为空 代表s="0"
    if (s.empty()) k = 0;
//    字符串长度比要求保留的位数要多, 则进行截取操作
    if (s.size() > n) s = s.substr(0, n);
//    否则 在末尾补0
    else s += string(n - s.size(), '0');

    return "0." + s + "*10^" + to_string(k);
}

int main()
{
    int n;
    string a, b;
    cin >> n >> a >> b;

    a = change(a, n);
    b = change(b, n);

    if (a == b) cout << "YES " << a << endl;
    else cout << "NO " << a << ' ' << b << endl;

    return 0;
}



  1. 已有空余球桌

    a. 该同学是vip,则分配vip球桌

    b. 该同学不是vip,则分配编号最小的球桌

  2. 没有空余球桌,求最早结束时间

    a. 最早结束的是普通球桌,一视同仁

    b. 最早结束的是vip球桌,vip同学先上

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

const int N = 10010, M = 110, INF = 1000000;

int n, k, m;

struct Person  // 球员
{
    int arrive_time, play_time;
    int start_time, waiting_time;

    bool operator< (const Person& t) const  // sort排序
    {
        if (start_time != t.start_time) return start_time < t.start_time;
        return arrive_time < t.arrive_time;
    }

    bool operator> (const Person& t) const  // 优先队列中比较大小
    {
        return arrive_time > t.arrive_time;
    }
};

struct Table  // 球桌
{
    int id;
    int end_time;

    bool operator> (const Table& t) const  // 优先队列中比较大小
    {
        if (end_time != t.end_time) return end_time > t.end_time;
        return id > t.id;
    }
};

bool is_vip_table[M];
int table_cnt[M];

vector<Person> persons;

void assign(priority_queue<Person, vector<Person>, greater<Person>>& ps,
            priority_queue<Table, vector<Table>, greater<Table>>& ts)
{
    auto p = ps.top(); ps.pop();
    auto t = ts.top(); ts.pop();
    p.waiting_time = round((t.end_time - p.arrive_time) / 60.0);
    p.start_time = t.end_time;
    table_cnt[t.id] ++ ;
    persons.push_back(p);
    ts.push({t.id, t.end_time + p.play_time});
}

string get_time(int secs)
{
    char str[20];
    sprintf(str, "%02d:%02d:%02d", secs / 3600, secs % 3600 / 60, secs % 60);
    return str;
}

int main()
{
    cin >> n;

    priority_queue<Person, vector<Person>, greater<Person>> normal_persons;
    priority_queue<Person, vector<Person>, greater<Person>> vip_persons;


    normal_persons.push({INF});
    vip_persons.push({INF});

    for (int i = 0; i < n; i ++ )
    {
        int hour, minute, second;
        int play_time, is_vip;
        scanf("%d:%d:%d %d %d", &hour, &minute, &second, &play_time, &is_vip);

        int secs = hour * 3600 + minute * 60 + second;
        play_time = min(play_time, 120);
        play_time *= 60;

        if (is_vip) vip_persons.push({secs, play_time});
        else normal_persons.push({secs, play_time});
    }

    priority_queue<Table, vector<Table>, greater<Table>> normal_tables;
    priority_queue<Table, vector<Table>, greater<Table>> vip_tables;
    normal_tables.push({-1, INF});
    vip_tables.push({-1, INF});

    cin >> k >> m;
    for (int i = 0; i < m; i ++ )
    {
        int id;
        cin >> id;
        is_vip_table[id] = true;
    }

    for (int i = 1; i <= k; i ++ )
        if (is_vip_table[i]) vip_tables.push({i, 8 * 3600});
        else normal_tables.push({i, 8 * 3600});

    while (normal_persons.size() > 1 || vip_persons.size() > 1)
    {
        auto np = normal_persons.top();
        auto vp = vip_persons.top();
        int arrive_time = min(np.arrive_time, vp.arrive_time);

//        第1种情况 修改成 第2种情况
//        普通球桌结束,把下一一对球友到达时间 赋值给 球桌结束时间
        while (normal_tables.top().end_time < arrive_time)  // O(klogk)
        {
            auto t = normal_tables.top();
            normal_tables.pop();
            t.end_time = arrive_time;
            normal_tables.push(t);
        }
        while (vip_tables.top().end_time < arrive_time)
        {
            auto t = vip_tables.top();
            vip_tables.pop();
            t.end_time = arrive_time;
            vip_tables.push(t);
        }

        auto nt = normal_tables.top();
        auto vt = vip_tables.top();
        int end_time = min(nt.end_time, vt.end_time);

        if (end_time >= 21 * 3600) break;

//        第2种情况, vip球员已经到了,空余的是vip球桌 安排
        if (vp.arrive_time <= end_time && vt.end_time == end_time) assign(vip_persons, vip_tables);

//        正常情况,要么有vip球员无vip球桌,要么有vip球桌无vip球员
//        普通球员先到
        else if (np.arrive_time < vp.arrive_time)
        {
//            vip球桌空闲, 安排普通球员
//            vip球桌空闲,即使 vip球员在等待队列后面,也应该先安排呀 ?
//            难道 np.arrive_time < vp.arrive_time 指的是vip球员还没到球馆,没有进等待队列 ?
            if (nt > vt) assign(normal_persons, vip_tables);
//            普通球桌空闲,安排普通球员,因为普通球员先到
            else assign(normal_persons, normal_tables);
        }
//        vip球员先到
        else
        {
            if (nt > vt) assign(vip_persons, vip_tables);
            else assign(vip_persons, normal_tables);
        }
    }

//    按照开始时间,到达时间排序
    sort(persons.begin(), persons.end());

    for (auto person : persons)
    {
        cout << get_time(person.arrive_time) << ' ' << get_time(person.start_time) << ' ';
        cout << person.waiting_time << endl;
    }

//    PAT平台不能有最后一个空格
    cout << table_cnt[1];
    for (int i = 2; i <= k; i ++ ) cout << ' ' << table_cnt[i];
    cout << endl;
    return 0;
}



遍历数组,然后再遍历每一个窗口

时间复杂度 $ O(nk) $

优化

通过单调性优化。

单调队列2.png

我们观察一个规律,对于3 -1 -3, 当-3存在, 并且寻找滑动窗口内的最小值时,3 -1是无效的, 也就是说,当-3加入队列时,-1删去, 3也删去。

抽象一些,当入队元素小于等于队尾元素, 队尾元素出队。直到入队元素大于队尾元素a[q[tt]] >= a[i], 或者队列为空,则停止删除操作。

while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;

k表示滑动窗口大小, q[N] 存储的是数组下标

需要保证q数组里面存储的元素小于等于k

if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;

当滑动窗口里面的元素个数等于k个的时候才能输出

k=3, 滑动窗口需要有三个元素才能开始输出最值

if (i >= k - 1) printf("%d ", a[q[hh]]);




class Solution {
public:
    string reverseWords(string s) {
        int k=0;
        // __ab_cde___fgh___ => ba_edc_hgf__
        //遍历每一个字符
        for(int i=0;i<s.size();)
        {
            //j指向上一个字符尾巴
            int j=i;
            //去除多余空格
            while(j<s.size() && s[j]==' ') j++;

            if(j==s.size()) break;
            //找到这个单词的开头
            i=j;
            //找到这个单词的尾巴
            while(j<s.size() && s[j]!=' ') j++;
            //翻转这个单词
            reverse(s.begin() +i, s.begin() + j);
            //给每个单词末尾添加一个空格
            if(k) s[k++]=' ';

            while(i<j) s[k++]=s[i++];
        }


        //ba_edc_hgf__ => ba_edc_hgf
        //去除尾巴处多余空格
        s.erase(s.begin()+k , s.end());


        // ba_edc_hgf => fgh_cde_ab
        reverse(s.begin(), s.end());

        return s;
    }
};



一般 ACM 或者笔试题的时间限制是 1 秒或 2 秒。
在这种情况下,C++ 代码中的操作次数控制在 $10^7$ 为最佳。

下面给出在不同数据范围下,代码的时间复杂度和算法该如何选择:

  1. $n \le 30$, 指数级别,

    dfs + 剪枝,数字排列, n皇后问题, 八数码问题

    状态压缩 dp,蒙德里安的梦想, 最短Hamilton路径

  2. $n \le 100$ => $O(n^3)$,

    floyd,

    dp,

  3. $n \le 1000$ => $O(n^2)$,$O(n^2logn)$,

    dp,

    二分,

    朴素版 Dijkstra、朴素版 Prim、Bellman-Ford

  4. $n \le 10000$ => $O(n * \sqrt n)$,

    块状链表、分块、莫队

  5. $n \le 100000$ => $O(nlogn)$

    各种 sort,线段树、树状数组、set/map、heap、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分

  6. $n \le 1000000$ => $O(n)$, 以及常数较小的 $O(nlogn)$ 算法

    hash、双指针扫描、并查集,kmp、AC 自动机,

    常数比较小的 $O(nlogn)$ 的做法:sort、树状数组、heap、dijkstra、spfa

  7. $n \le 10000000$ => $O(n)$,

    双指针扫描、kmp、AC 自动机、线性筛素数

  8. $n \le 10^9$ => $O(\sqrt n)$,

    判断质数

  9. $n \le 10^{18}$ => $O(logn)$,

    最大公约数,快速幂

  10. $n \le 10^{1000}$ => $O((logn)^2)$,

    高精度加减乘除

  11. $n \le 10^{100000}$ => $O(logn \times loglogn)$,

    高精度加减、FFT/NTT


算法时间复杂度分析实例:

一般来说,k重循环,算法时间复杂度就是$n^k$

基础算法
快速排序 归并排序 二分 O(nlogn)
双指针 数组元素目标和 O(n)
数据结构
单链表 栈 (插入 删除操作) O(1)
单调栈 单调队列 O(n)
KMP O(n)
Trie字符串统计 O(n)
并查集 (路径压缩) O(nlogn)
堆排序 O(nlogn)
模拟散列表 O(1)
搜索与图论
排列数字(全排列) O(n*n!)
dfs bfs O(n+m)
Dijkstra O(mlogm)
Bellman_ford O(nm)
spfa O(nm)
Floyd O(n^3)
Prim O(n^2)
Kruskal O(mlogm)
染色法判定二分图 O(mlogm)
匈牙利算法 O(nm)

spfa算法, 匈牙利算法, 最大流算法时间复杂度理论值很大,但是实际运行速度很快

数学知识
试除法判定质数 分解质因数 sqrt(n)
筛质数 nlogn
最大公约数 logn
快速幂 logn

动态规划问题的计算量=状态数量*状态转移的计算量

动态规划
背包问题 k重循环,算法时间复杂度就是$n^k$
最长上升子序列 II nlogn
蒙德里安的梦想 2^
没有上司的舞会 nm

空间复杂度分析

64M

1 Byte = 8 bit

1 KB= 1024 Byte

1 MB=1024*1024 Byte

1 GB=1024 * 1024 * 1024 Byte

int  4 Byte

char 1 Byte

double, long long   6Byte

bool 1 Byte
C++: 为什么bool类型是1 Byte(8 bits)长?

为什么bool类型所需存储空间不是 1 bit, 1 bit就可以覆盖bool类型的值域范围 。

Cpp的数据类型必须就可以通过地址得到的(addressable)。

我们无法通过一位创建一个指针,但是我们可以通过一个自己创建一个指针。

所以, 在Cpp中,Bool类型的大小是一个字节。

64MB=2^26Byte

2^26Byte /4 =2^24 int

=1.6*10^7 int
注意

递归也是需要空间的,递归调用了系统栈,快速排序使用了递归,所以空间复杂度是O(logn)




class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        // 先去除不在0~n-1范围的数,防止下标越界
        for (auto x : nums)
            if (x < 0 || x >= n)
                return -1;
        for (int i = 0; i < n; i ++ ) {
            // 如果没有重复元素,经过这一步操作,0位置将会存储0, i位置将会存储i
            while (nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
            // 如果有重复元素 将会导致 因为有两个相同的数 但是只有一个位置 所以位置和值不能一一对应
            if (nums[i] != i) return nums[i];
        }
        // 找不到重复的数就返回-1 
        return -1;
    }
};



class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        if(array.empty() || array[0].empty()) return false;
        int i=0, j=array[0].size()-1;
        while(i<array.size() && j>=0) {
            if(array[i][j]==target) return true;
            if(array[i][j]> target) j--;
            else i++;
        }
        return false;
    }
};



class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l=1, r=nums.size()-1;
        while(l<r){
            int mid=l+r>>1;
            int s=0;
            for(auto x:nums) s+=x>=l && x<=mid;
            if(s>mid-l+1) r=mid;
            else l=mid+1;
        }
        return r;
    }
};