头像

贺谦

NPU




离线:7小时前



贺谦
17天前

define _CRT_SECURE_NO_WARNINGS

// #pragma comment(linker, “/stack:200000000”)
// #pragma GCC optimize(“Ofast”)
// #pragma GCC optimize(3)
// #pragma GCC target(“sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native”)
// #pragma GCC target(“sse3”,”sse2”,”sse”)
// #pragma GCC target(“avx”,”sse4”,”sse4.1”,”sse4.2”,”ssse3”)
// #pragma GCC target(“f16c”)
// #pragma GCC optimize(“inline”,”fast-math”,”unroll-loops”,”no-stack-protector”)
// #pragma GCC diagnostic error “-fwhole-program”
// #pragma GCC diagnostic error “-fcse-skip-blocks”
// #pragma GCC diagnostic error “-funsafe-loop-optimizations”
// #pragma GCC diagnostic error “-std=c++14”

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

// 时间够不要用unordered_map,unordered_set

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

typedef pair[HTML_REMOVED] PII;
typedef pair[HTML_REMOVED]> PIII;

typedef pair[HTML_REMOVED] PLI;
typedef pair[HTML_REMOVED] PUI;

typedef vector[HTML_REMOVED] VI;
typedef vector[HTML_REMOVED] VVI;

typedef vector[HTML_REMOVED] VL;
typedef vector[HTML_REMOVED] VPII;

typedef pair[HTML_REMOVED] PLL;
typedef vector[HTML_REMOVED] VPLL;

typedef priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> minheap;
typedef priority_queue[HTML_REMOVED] maxheap;

typedef priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> pi_minheap;
typedef priority_queue[HTML_REMOVED] pi_maxheap;

typedef priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> pii_minheap;
typedef priority_queue[HTML_REMOVED] pii_maxheap;

// 常用操作的简写

define PB push_back

define PF push_front

define se second

define fi first

define sz(x) ((int)x.size())

define fr(x) freopen(x,”r”, stdin)

define fw(x) freopen(x,”w”, stdout)

define REP(x, l, u) for (int x = l; x <= u; x ++)

define RREP(x, u, l) for (int x = u; x >= l; x –)

define sqr(x) (x * x)

// 给静态数组设值

define setZE(x) memset(x, 0, sizeof x)

define setMAX(x) memset(x, 0x3f, sizeof x)

define setMIN(x) memset(x, -0x3f, sizeof x)

// lowbit操作,树状数组

define lowbit(x) ((x)&(-(x)))

// 直接输出x的二进制表示中的1的个数

define bitcnt(x) (__builtin_popcountll(x))

// 方格问题中的方位
int dx4[4] = { 0, 0, -1, 1 };
int dy4[4] = { -1, 1, 0, 0 };
int dx8[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy8[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };

LL MOD_F(LL a, LL M)
{
a %= M;
return a < 0 ? a + M : a;
}

/
* 数学板子
/
// 最大公约数
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}

// 快速幂
LL qmi(LL a, LL b, LL mod)
{
if (!b) return 1;
LL tmp = qmi(a, b >> 1, mod);
tmp = (tmp * tmp) % mod;
if (b & 1) tmp *= a;
return tmp % mod;
}

/
* 输出输出优化
/
void IO()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}

/
* 并查集函数
* 使用的时候需要先根据打下定义好fa数组
/
int UFfind(int f[], int a)
{
return a == f[a] ? f[a] : f[a] = UFfind(f, f[a]);
}

void UFinit(int f[], int n)
{
REP(i, 1, n) f[i] = i;
}

// 常用的取模
const int mN = 1e2 + 10;
const int N = 1e6 + 10;
constexpr int MOD = 1e9 + 7;

/******
* 代码开始


*/

//#define kickstart

define niuke

// #define custom
// #define multiTask
// #define duipai

/
* 数据初始定义
/

ifdef kickstart

int T;
int l, r, n, m;
int res;
int f[N];

endif

ifdef niuke

int n, x;
string s;

stack[HTML_REMOVED] stk, cache;

endif

// 每个测试数据的方法
void solve()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s;
if (s == “add”)
{
cin >> x;
stk.push(x);
}
else if (s == “poll”)
{
if (stk.empty()) cout << -1 << endl;
while (stk.size())
{
cache.push(stk.top());
stk.pop();
}

        cache.pop();

        while (cache.size())
        {
            stk.push(cache.top());
            cache.pop();
        }
    }
    else
    {
        if (stk.empty()) cout << -1 << endl;
        while (stk.size())
        {
            cache.push(stk.top());
            stk.pop();
        }

        int res = cache.top();

        while (cache.size())
        {
            stk.push(cache.top());
            cache.pop();
        }

        cout << res << endl;
    }
}

}

int main()
{
IO();

ifdef kickstart

// scanf("%d", &T);
cin >> T;

for (int cas = 1; cas <= T; cas ++)
{
    solve();
    cout << "Case #" << cas << ": " << res << endl;
}

return 0;

else

solve();

return 0;

}

endif

ifdef duipai

int main()
{
for (int T = 0; T < 10000; ++T)
{
system(“./random > ./data.in”);
double st = clock();
system(“./sol < ./data.in > ./data.ans”);
double et = clock();
system(“./bf < ./data.in > ./data.out”);
if (system(“diff ./data.out ./ data.ans”))
{
puts(“Wrong Answer\n”);
return 0;
}
else
{
printf(“Accepted, 测试点 #%d, 用时 %.0lfms\n”, T, et - st);
}
}
return 0;
}

endif




贺谦
1个月前

思路

  • C++ 11,VS2019
  • 使用了unique_lock,条件变量
  • 条件变量的wait(), notify_one()
  • wait()中使用了lambda表达式

代码

#include <iostream>
#include <vector>
#include <thread>
#include <list>
#include <mutex>

using namespace std;

bool flag = true;

class A
{
public:

    void print1()
    {
        while (true)
        {
            std::unique_lock<std::mutex> lock1(print_mutex);
            data_var.wait(lock1, [] {return flag; });
            cout << "thread: " << std::this_thread::get_id() << " print: " << "A" << endl;

            flag = false;
            data_var.notify_one();
        }
    }

    void print2()
    {
        while (true)
        {
            std::this_thread::sleep_for(std::chrono::seconds(1));

            std::unique_lock<std::mutex> lock2(print_mutex);

            data_var.wait(lock2, [] {return !flag; });
            cout << "thread: " << std::this_thread::get_id() << " print: " << "B" << endl;

            flag = true;
            data_var.notify_one();
        }
    }

private:

    std::mutex print_mutex;
    std::condition_variable data_var;
};


int main()
{
    A myobj_a;

    std::thread print1(&A::print1, &myobj_a);
    std::thread print2(&A::print2, &myobj_a);

    print1.join();
    print2.join();

    return 0;
}



贺谦
1个月前
class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        if (n <= 0) return 0;
        vector<int> A;
        while (n) A.push_back(n % 10), n /= 10;
        reverse(A.begin(), A.end());

        int res = 0;
        for (int i = 0; i < A.size(); i ++ )
        {
            int abc = 0, d = A[i], efg = 0, p = 1;

            for (int j = 0; j < i; j ++ ) abc = abc * 10 + A[j];
            for (int j = i + 1; j < A.size(); j ++ )
            {
                efg = efg * 10 + A[j];
                p = p * 10;
            }

            if (d == 0) res += abc * p;
            else if (d == 1) res += abc * p + efg + 1;
            else res += (abc + 1) * p;
        }

        return res;
    }
};



贺谦
2个月前

不修改数组找出重复的数字


二分模板1

(二分模板1) $O(nlogn)$

这道题不管是将区间划分为[l, mid], [mid + 1, r]
还是划分为[l, mid - 1], [mid, r]都可以的。

C++ 代码

class Solution {
public:
    bool go(int r, int mid, vector<int>& A)
    {
        int res = 0;
        for (auto x : A)
            if (x >= mid && x <= r)
                res ++;
        return res > r - mid + 1;
    }

    int duplicateInArray(vector<int>& A) {
        int n = A.size();
        int l = 1, r = n - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (go(r, mid, A)) l = mid;
            else r = mid - 1;
        }

        return l;
    }
};

模板2

C++ 代码

class Solution {
public:
    bool go(int l, int mid, vector<int>& A)
    {
        int res = 0;
        for (auto x : A)
            if (x >= l && x <= mid)
                res ++;
        return res > mid - l + 1;
    }

    int duplicateInArray(vector<int>& A) {
        int n = A.size();
        int l = 1, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (go(l, mid, A)) r = mid;
            else l = mid + 1;
        }

        return l;
    }
};


活动打卡代码 AcWing 620. 安全区

贺谦
2个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 3010;

typedef long long LL;

int T;
int R, c, k;
int l, r;
int g[N][N], f[N][N];

int main()
{
    cin >> T;
    for (int cas = 1; cas <= T; cas ++ )
    {
        memset(g, 0, sizeof g);
        memset(f, 0, sizeof f);

        cin >> R >> c >> k;
        while (k --)
        {
            cin >> l >> r;
            g[l][r] = 1;
        }

        LL res = 0;
        for (int i = 1; i <= R; i ++ )
            for (int j = 1; j <= c; j ++ )
            {
                if (g[i - 1][j - 1]) f[i][j] = 0;
                else
                {
                    f[i][j] = min(f[i - 1][j - 1],
                        min(f[i - 1][j], f[i][j - 1])) + 1;
                }

                res += f[i][j];
            }

        printf("Case #%d: %lld\n", cas, res);
    }

    return 0;
}


活动打卡代码 AcWing 595. 夏洛克和括号

贺谦
2个月前
#include <iostream>

using namespace std;

typedef long long LL;

int T;
int l, r;

int main()
{
    cin >> T;
    for (int cas = 1; cas <= T; cas ++ )
    {
        cin >> l >> r;
        int k = min(l, r); 
        int res = (LL)k * (k + 1) / 2;

        printf("Case #%d: %d\n", cas, res);
    }

    return 0;
}


活动打卡代码 AcWing 1158. H指数

贺谦
2个月前
#include <iostream>
#include <queue>

using namespace std;

const int N = 1e5 + 10;

int T;
int n;
int a[N];

int main()
{
    cin >> T;
    for (int cas = 1; cas <= T; cas ++ )
    {
        printf("Case #%d: ", cas);

        cin >> n;
        priority_queue<int, vector<int>, greater<int>> heap;

        int res = 0;
        for (int i = 0; i < n; i ++ )
        {
            cin >> a[i];
            if (a[i] > res) heap.push(a[i]);
            while (heap.size() && heap.top() <= res) heap.pop();
            if (heap.size() > res) res ++;

            printf("%d ", res);
        }

        cout << endl;
    }

    return 0;
}


活动打卡代码 AcWing 1769. H 指数 II

贺谦
2个月前
class Solution {
public:
    int hIndex(vector<int>& A) {
        int n = A.size();
        int l = 0, r = n; 
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (A[n - mid] >= mid) l = mid;
            else r = mid - 1;
        }

        return r;
    }
};

class Solution {
public:

    bool go(int x, vector<int>& A)
    {
        int res;
        for (int h = A.size(); h >= 0; h -- )
            if (A[A.size() - h] >= h)
            {
                res = h;
                break;
            }

        return x <= res;
    }

    int hIndex(vector<int>& A) {
        int n = A.size();
        int l = 0, r = -2e9;
        for (auto x : A) r = max(r, x);

        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (go(mid, A)) l = mid;
            else r = mid - 1;
        }

        return r;
    }
};


活动打卡代码 AcWing 1768. H 指数

贺谦
2个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];

    sort(a, a + n);

    for (int h = n; h >= 0; h -- )
        if (a[n - h] >= h)
        {
            cout << h << endl;
            break;
        }

    return 0;
}


活动打卡代码 AcWing 80. 骰子的点数

贺谦
2个月前
class Solution {
public:
    vector<int> numberOfDice(int n) {
        vector<int> res;
        vector<vector<int>> f(n + 1, vector<int>(n * 6 + 1));

        f[0][0] = 1;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= i * 6; j ++ )
                for (int k = 1; k <= min(6, j); k ++ )
                    f[i][j] += f[i - 1][j - k];

        for (int i = n; i <= n * 6; i ++ )
            res.push_back(f[n][i]);

        return res;
    }
};