头像

AC-黑白




在线 


最近来访(93)
用户头像
limoalin
用户头像
用户头像
我呼吸了
用户头像
李.嘉图
用户头像
潮鸣
用户头像
封禁用户1
用户头像
茉窈my
用户头像
Hxxj
用户头像
V1
用户头像
幸运_8
用户头像
coolcoder
用户头像
相得益彰
用户头像
奔向未来
用户头像
C++大蒟蒻
用户头像
代码哪有恋爱香
用户头像
QWQ_QAQ_krjt
用户头像
NULL_
用户头像
封禁用户
用户头像
WangJY
用户头像
Finn2009


AC-黑白
39分钟前

说句闲话:STL大法好

class MyCircularDeque {
public:
deque<int>q;
int mxs;
    MyCircularDeque(int k) {
        mxs=k;
        q.clear();
    }

    bool insertFront(int value) {
        if(q.size()==mxs)return false;
        q.push_front(value);
        return true;
    }

    bool insertLast(int value) {
        if(q.size()==mxs)return false;
        q.push_back(value);
        return true;
    }

    bool deleteFront() {
        if(q.empty())return false;
        q.pop_front();
        return true;
    }

    bool deleteLast() {
        if(q.empty())return false;
        q.pop_back();
        return true;
    }

    int getFront() {
        if(q.empty())return -1;
        return q.front();
    }

    int getRear() {
        if(q.empty())return -1;
        return q.back();
    }

    bool isEmpty() {
        return q.empty();
    }

    bool isFull() {
        return q.size()==mxs;
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */


新鲜事 原文

请求y总把离开界面时确认加上,我打着Saber结果退格按得太快Saber没捕捉到,结果就自动投降了。



class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        vector<int>big;
        vector<int>small;
        big.push_back(arr[0]);
        for(int i=1;i<arr.size();++i){
            big.push_back(max(big[big.size()-1],arr[i]));
        }
        small.push_back(arr[arr.size()-1]);
        for(int i=arr.size()-2;i>=0;--i){
            small.push_back(min(small[small.size()-1],arr[i]));
        }
        int ans=1;
        for(int i=0;i<arr.size()-1;++i){
            if(big[i]<=small[arr.size()-i-2])++ans;
        }
        return ans;
    }
};


活动打卡代码 LeetCode 1282. 用户分组

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>>res;
        vector<int>nw(505,-1);
        for(int i=0;i<groupSizes.size();++i){
            if(nw[groupSizes[i]]==-1||res[nw[groupSizes[i]]].size()==groupSizes[i]){
                res.push_back(vector<int>());
                nw[groupSizes[i]]=res.size()-1;
                res[nw[groupSizes[i]]].push_back(i);
            }
            else{
                res[nw[groupSizes[i]]].push_back(i);
            }
        }
        return res;
    }
};


活动打卡代码 AcWing 303. 运输小猫

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010, M = 100010, P = 110;
int n, m, p;
LL d[N], t[N], a[N], s[N];
LL f[P][M];
int q[M];
LL gety(int k, int j)
{
   return f[j - 1][k] + s[k];
}
int main()
{
   scanf("%d%d%d", &n, &m, &p);
   for (int i = 2; i <= n; ++i)
   {
      scanf("%lld", &d[i]);
      d[i] += d[i - 1];
   }
   for (int i = 1; i <= m; ++i)
   {
      int h;
      scanf("%d%lld", &h, &t[i]);
      a[i] = t[i] - d[h];
   }
   sort(a + 1, a + m + 1);
   for (int i = 1; i <= m; ++i)
   {
      s[i] = s[i - 1] + a[i];
   }
   memset(f, 0x3f, sizeof f);
   for (int i = 0; i <= p; ++i)
   {
      f[i][0] = 0;
   }
   for (int j = 1; j <= p; ++j)
   {
      int hh = 0, tt = 0;
      q[0] = 0;
      for (int i = 1; i <= m; ++i)
      {
         while (hh < tt && (gety(q[hh + 1], j) - gety(q[hh], j)) <= a[i] * (q[hh + 1] - q[hh]))
         {
            hh++;
         }
         int k = q[hh];
         f[j][i] = f[j - 1][k] - a[i] * k + s[k] + a[i] * i - s[i];
         while (hh < tt && (gety(q[tt], j) - gety(q[tt - 1], j)) * (i - q[tt]) >= (gety(i, j) - gety(q[tt], j)) * (q[tt] - q[tt - 1]))
         {
            --tt;
         }
         q[++tt] = i;
      }
   }
   printf("%lld", f[p][m]);
   return 0;
}



活动打卡代码 AcWing 3715. 最少交换次数

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 301. 任务安排2

#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
#define LL long long

int n, s;
LL t[N], c[N], f[N];
int q[N];
int main()
{
   cin >> n >> s;
   for (int i = 1; i <= n; ++i)
      cin >> t[i] >> c[i], t[i] += t[i - 1], c[i] += c[i - 1];
   int hh = 0, tt = 0;
   q[0] = 0;
   for (int i = 1; i <= n; ++i)
   {
      int l = hh, r = tt;
      while (l < r )
      {
         int mid = l + r >> 1;
         if (f[q[mid + 1]] - f[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]]))
         {
            r = mid;
         }
         else
         {
            l = mid+1;
         }
      }
      int j = q[r];
      f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
      while (hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[tt]) >= (f[i] - f[q[tt]]) * (c[q[tt]] - c[q[tt - 1]]))
      {
         --tt;
      }
      q[++tt] = i;
   }
   cout << f[n];
   return 0;
}


活动打卡代码 AcWing 302. 任务安排3

#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
#define LL long long

int n, s;
LL t[N], c[N], f[N];
int q[N];
int main()
{
   scanf("%d%d", &n, &s);
   for (int i = 1; i <= n; ++i)
   {
      scanf("%lld%lld", &t[i], &c[i]);
      t[i] += t[i - 1], c[i] += c[i - 1];
   }
   int hh = 0, tt = 0;
   q[0] = 0;
   for (int i = 1; i <= n; ++i)
   {
      int l = hh, r = tt;
      while (l < r)
      {
         int mid = l + r >> 1;
         if (f[q[mid + 1]] - f[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]]))r = mid;
         else l = mid + 1;
      }
      int j = q[r];
      f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
      while (hh < tt && (double)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt - 1]]) >= (double)(f[i] - f[q[tt - 1]]) * (c[q[tt]] - c[q[tt - 1]]))
      {
         --tt;
      }
      q[++tt] = i;
   }
   printf("%lld", f[n]);
   return 0;
}


活动打卡代码 AcWing 300. 任务安排1

#include <cstdio>
#include <cstring>
#define mi2(a, b) (a < b ? a : b)
#define mx2(a, b) (a > b ? a : b)
using namespace std;
long long f[5005],t[5005],c[5005];
int main()
{
   int n,s;
   scanf("%d%d", &n, &s);
   for (int i = 1; i <= n; ++i)scanf("%d%d", &t[i], &c[i]);
   for (int i = 1; i <= n; ++i)t[i] += t[i - 1];
   for (int i = 1; i <= n; ++i)c[i] += c[i - 1];
   memset(f, 0x3f, sizeof f);
   f[0] = 0;
   for (int i = 1; i <= n; ++i)for (int j = 0; j < i; ++j)f[i] = mi2(f[i], f[j] + (c[i] - c[j]) * t[i] + s * (c[n] - c[j]));
   printf("%lld", f[n]);
}


活动打卡代码 AcWing 1091. 理想的正方形

#include <iostream>
#include <cstdio>
using namespace std;
template <class T>
struct deque
{
   struct node
   {
      node *lst;
      node *nt;
      T data;
      node(node *a, node *b, T c) : lst(a), nt(b), data(c) {}
   };
   node *fst;
   node *lst;
   deque()
   {
      lst = fst = new node(nullptr, nullptr, 0);
   }
   void push_back(T x)
   {
      node *us = new node(lst, nullptr, x);
      lst = lst->nt = us;
   }
   void push_front(T x)
   {
      node *us = new node(fst, fst->nt, x);
      fst->nt = fst->nt->lst = us;
   }
   void pop_front()
   {
      if (fst->nt)
      {
         fst = fst->nt;
         delete fst->lst;
         fst->lst=nullptr;
      }
   }
   void pop_back()
   {
      if (lst->lst)
      {
         lst = lst->lst;
         delete lst->nt;
         lst->nt=nullptr;
      }
   }
   T front()
   {
      return empty() ? 0 : fst->nt->data;
   }
   T back()
   {
      return empty() ? 0 : lst->data;
   }
   bool empty()
   {
      return lst == fst;
   }
};
int ori[1005][1005];
int mx[1005][1005];
int mxans[1005][1005];
int mi[1005][1005];
int mians[1005][1005];
int main()
{
   deque<int> q;
   int n, m, x;
   scanf("%d%d%d", &n, &m, &x);
   for (int i = 1; i <= n; ++i)
   {
      for (int j = 1; j <= m; ++j)
      {
         scanf("%d", &ori[i][j]);
      }
   }
   for (int j = 1; j <= n; ++j)
   {
      while (!q.empty())
      {
         q.pop_back();
      }
      for (int i = 1; i <= m; ++i)
      {
         if (!q.empty() && q.front() <= i - x)
         {
            q.pop_front();
         }
         while (!q.empty() && ori[j][q.back()] <= ori[j][i])
         {
            q.pop_back();
         }
         q.push_back(i);
         mx[j][i] = ori[j][q.front()];
      }
      while (!q.empty())
      {
         q.pop_back();
      }
      for (int i = 1; i <= m; ++i)
      {
         if (!q.empty() && q.front() <= i - x)
         {
            q.pop_front();
         }
         while (!q.empty() && ori[j][q.back()] >= ori[j][i])
         {
            q.pop_back();
         }
         q.push_back(i);
         mi[j][i] = ori[j][q.front()];
      }
   }
   for (int j = 1; j <= m; ++j)
   {
      while (!q.empty())
      {
         q.pop_back();
      }
      for (int i = 1; i <= n; ++i)
      {
         if (!q.empty() && q.front() == i - x)
         {
            q.pop_front();
         }
         while (!q.empty() && mx[q.back()][j] <= mx[i][j])
         {
            q.pop_back();
         }
         q.push_back(i);
         mxans[i][j] = mx[q.front()][j];
      }
      while (!q.empty())
      {
         q.pop_back();
      }
      for (int i = 1; i <= n; ++i)
      {
         if (!q.empty() && q.front() == i - x)
         {
            q.pop_front();
         }
         while (!q.empty() && mi[q.back()][j] >= mi[i][j])
         {
            q.pop_back();
         }
         q.push_back(i);
         mians[i][j] = mi[q.front()][j];
      }
   }
   int ans = 0x7fffffff;
   for (int i = x; i <= n; ++i)
   {
      for (int j = x; j <= m; ++j)
      {
         if (mxans[i][j] - mians[i][j] < ans)
         {
            ans = mxans[i][j] - mians[i][j];
         }
      }
   }
   printf("%d", ans);
   return 0;
}