头像

Liuyz.




离线:9小时前


最近来访(85)
用户头像
例外.
用户头像
Tequila
用户头像
Sundae
用户头像
o张雨霏o
用户头像
冰冷酒
用户头像
穿着校服浪天下.
用户头像
七酱
用户头像
Magic_Zq
用户头像
于于
用户头像
薛定谔的大白猫
用户头像
yxc
用户头像
2016070111
用户头像
流苏_9
用户头像
FoceIess
用户头像
Wegoon
用户头像
学算法就上AcWing
用户头像
RyanMoriarty
用户头像
RiceShower
用户头像
从未看过满天繁星
用户头像
ヅ天使ぺ嫙嵂


Liuyz.
2天前

直接记录出现每个O的左面 有多少个C,右面有多少个W 即可

用前缀和预处理

#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e5 + 10;
char c[N];
int a[N];
int b[N];
int aa[N];
int bb[N];
long long ans;
int main()
{
  cin >> n;
  cin >> c + 1; 
  for (int i = 1; i <= n; i++)
  {
    if (c[i] == 'C')
      a[i]++;
    if (c[i] == 'W')
      b[i]++;
  }
  for (int i = 1; i <= n; i++)
  {
    aa[i] = aa[i - 1] + a[i];
    bb[i] = bb[i - 1] + b[i];
  }
  for (int i = 1; i <= n; i++)
  {
    if (c[i] == 'O')
    {
      ans = ans + (aa[i] * (bb[n] - bb[i - 1]));
    }
  }
  cout << ans << endl;

  return 0;
}


活动打卡代码 AcWing 1884. COW

Liuyz.
2天前
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e5 + 10;
char c[N];
int a[N];
int b[N];
int aa[N];
int bb[N];
long long ans;
int main()
{
  cin >> n;
  cin >> c+1;
  for (int i = 1; i <=n; i++)
  {
    if (c[i] == 'C')
      a[i]++;
    if (c[i] == 'W')
      b[i]++;
  }
  for(int i=1;i<=n;i++)
  {
    aa[i]=aa[i-1]+a[i];
    bb[i]=bb[i-1]+b[i];
  }
  for(int i=1;i<=n;i++)
  {
    if(c[i]=='O')
  {
    ans=ans+(aa[i]*(bb[n]-bb[i-1]));
  }
  }
  cout<<ans<<endl;

  return 0;
}


活动打卡代码 AcWing 1904. 奶牛慢跑

Liuyz.
3天前

后缀最小值

#include <bits/stdc++.h>
using namespace std;
int ans;
int n;
const int N = 1e5 + 10;
int a[N], b[N];
int smin[N];
const int INF=0x3f3f3f3f;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
    }
     smin[n]=INF;
   for(int i=n-1;i>=0;i--) //后缀最小值
   {
       smin[i]=min(smin[i+1],b[i]);
   }
   for(int i=0;i<n;i++)
   {
       if(b[i]<=smin[i+1])
       ans++;
   }

    cout << ans << endl;

    return 0;
}

直接模拟

#include <bits/stdc++.h>
using namespace std;
int ans;
int n;
const int N = 1e5 + 10;
int a[N], b[N];
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
    }
    int min = b[n - 1];
    for (int i = n - 1; i >= 0; i--)
    {
        if (b[i]<=min)
        {
            min = b[i];
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 1913. 公平摄影

Liuyz.
4天前

双指针+前缀和

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector<pii> q;
int ans = 0;
int n;
const int N = 1e6;
int s[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    q.push_back({0, 0});
    for (int i = 0; i < n; i++)
    {
        int p;
        char c;
        cin >> p >> c;
        if (c == 'G')
            q.push_back({p, 1}); //G标记成1
        if (c == 'H')            //H标记成-1
            q.push_back({p, -1});
    }
    sort(q.begin(), q.end());
    for (int i = 1; i <= n; i++) //用双指针找只有一种牛最长序列
    {
        int j = i;
        while (q[j].second == q[i].second)
            j++;
        ans = max(ans, q[j - 1].first - q[i].first);
        i = j - 1;
    }
    for (int i = 1; i <= n; i++) //求前缀和
    {
        s[i] = s[i - 1] + q[i].second;
    }
    unordered_map<int, int> mp;
    for (int i = 0; i <= n; i++)
    {
        if (mp.count(s[i]) == 0)  // 记录第一次前缀和出现的地方
        {                          // 两个位置的前缀和相同 中间的前缀和为0
            mp[s[i]] = i;
        }
        else
        {
            ans = max(ans, q[i].first - q[mp[s[i]] + 1].first);
        }
    }
    cout << ans << endl;
    return 0;
}



Liuyz.
5天前
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1e5 + 10;
int h[N], e[2 * N], ne[2 * N], idx;
int color[N]; //0 代表没染过色
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
bool dfs(int u, int y)
{
    color[u] = y;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!color[j])
        {
            if (!dfs(j, 3 - y))
                return false;
        }
        else if (color[j] == y)
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    int flag = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                flag = 1;
                break;
            }
        }
    }
    if (flag)
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
    return 0;
}



Liuyz.
5天前

最近好多差分的题

个人感觉这题和前两天选温度那题相似

自己总结了一下 涉及到区间问题,以及数量关系,一部分题就可以用差分

这道题,因为题里说,只有一片草地与她的初始位置的距离不超过 K 时,贝茜才能吃到那片草地上的草

假设初始位置是 x ,换句话说,也就是在x-k,x+k 这个区间上任选一点都可以吃到这堆草,所以不妨让这个区间的每个位置都有这堆草,那么此题就转化成了哪一个位置有最多的草,也就是各个区间重叠最多的部分

记得用map 离散化,因为数组下标可能是负数

#include <bits/stdc++.h>
using namespace std;
map<int, int> q; 
int n, k;
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int w, p;
        cin >> w >> p;
        q[p - k] += w;
        q[p + k + 1] -= w;
    }
    int sum = 0, ans = 0;
    for (auto x : q)
    {
        sum += x.second;
        ans = max(sum, ans);
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1922. 懒惰的牛

Liuyz.
5天前

差分

#include <bits/stdc++.h>
using namespace std;
map<int, int> q;
int n, k;
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int w, p;
        cin >> w >> p;
        q[p - k] += w;
        q[p + k + 1] -= w;
    }
    int sum = 0, ans = 0;
    for (auto x : q)
    {
        sum += x.second;
        ans = max(sum, ans);
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 847. 图中点的层次

Liuyz.
5天前
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1e5 + 10;
int e[N], ne[N], idx, h[N];
int dist[N];
bool st[N];
int ans;
queue<int> q;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int bfs(int u)
{
    dist[u] = 0;
    st[u] = true;
    q.push(u);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (!st[j])
            {
                st[j] = true;
                q.push(j);
                dist[j] = dist[t] + 1;
            }
        }
    }
    return dist[n];
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(dist, -1, sizeof dist);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
    }
    cout << bfs(1) << endl;
    return 0;
}


活动打卡代码 AcWing 846. 树的重心

Liuyz.
6天前
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e5 + 10;
bool st[N];
int e[2 * N], ne[2 * N], idx, h[N];
int ans = 0x3f3f3f3f;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int dfs(int u)
{
    int sum = 1, res = 0;
    st[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        }
    }
    res = max(res, n - sum);
    ans = min(res, ans);
    return sum;
}
int main()
{
    cin >> n;
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1934. 贝茜放慢脚步

Liuyz.
6天前

二路归并

#include <bits/stdc++.h>
using namespace std;
int n;
vector<double> sec;
vector<double> dis;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        double x;
        char op;
        cin >> op >> x;
        if (op == 'T')
            sec.push_back(x);
        else
            dis.push_back(x);
    }
    dis.push_back(1000);
    sort(sec.begin(), sec.end());
    sort(dis.begin(), dis.end());
    int i = 0, j = 0;
    double t = 0, s = 0, v = 1; //V为实际速度的倒数,方便更新
    while (i < sec.size() && j < dis.size())
    {
        if (sec[i] - t < (dis[j] - s) * v)
        {
            s += (sec[i] - t) / v;
            t = sec[i];
            i++;
            v++; //减速,倒数加一
        }
        else
        {
            t += (dis[j] - s) * v;
            s = dis[j];
            j++;
            v++;
        }
    }
    while (i < sec.size())
    {
        s += (sec[i] - t) / v;
        t = sec[i];
        i++;
        v++; //减速,倒数加一
    }
    while (j < dis.size())
    {
        t += (dis[j] - s) * v;
        s = dis[j];
        j++;
        v++;
    }
   int ans;
   ans=t+0.5;
   cout<<ans<<endl;
    return 0;
}