Liuyz.

3879

Tequila
Sundae
o张雨霏o

Magic_Zq

yxc
2016070111

FoceIess
Wegoon

RyanMoriarty
RiceShower

ヅ天使ぺ嫙嵂

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;
}


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;
}


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;
}


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 代表没染过色
{
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;
}
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天前

### 记得用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;
}


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;
}


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;
{
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;
}
cout << bfs(1) << endl;
return 0;
}


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;
{
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;
}
dfs(1);
cout << ans << endl;
return 0;
}


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;
}