C.Beautiful Triple Pairs
题意 ：优美组的定义是一共三对有且只有一对对应的数字不相同，求有多少个优美三元组
思路 ：对于只有三对，而且只有一对不同，首先看前面遍历过的三元组会对后面的三元组产生影响，若是不记录前面对后面三元组的次数，那么我们要进行两次循环 O(n^2 ) 会寄的，因此我们会想到记录前面出现的次数。但是三元组有两个位子相同，一个位子不同，
a = {1，2，3} ; b = {1，100，3} 。假设我们第二个位子不同，这两个三元组出现的次数要归到一块去，但是有一个位子是不同的对于数据的范围我在归类时候选择了将不同的位子数变成0， 即 {1，0，3} 。 因此我们可以计算前面出现的次数了。可以选择用map存数出现的次数。
在计算位置时候记得去重，因为会出现同样的三元组，但是这两个三元组不是答案。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
const int N = 3e5 + 10;
int a[N];
// 12 13 23
void solve()
{
int n; cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
map<vector<int>, int> mp;
vector<vector<int>> q;
long long ans = 0;
for (int i = 1; i <= n - 2; i++)
{
ans += mp[{a[i], 0, a[i + 2]}];
ans -= mp[{a[i], a[i + 1], a[i + 2]}];
ans += mp[{a[i], a[i + 1], 0}];
ans -= mp[{a[i], a[i + 1], a[i + 2]}];
ans += mp[{0, a[i + 1], a[i + 2]}];
ans -= mp[{a[i], a[i + 1], a[i + 2]}];
mp[{a[i], 0, a[i + 2]}]++;
mp[{a[i], a[i + 1], 0}]++;
mp[{0, a[i + 1], a[i + 2]}] ++;
mp[{a[i], a[i + 1], a[i + 2]}]++;
}
cout << ans << "\n";
}
int main()
{
int t = 1; cin >> t;
while (t--)
{
solve();
}
}
E. Money Buys Happiness
题意 ：给你 n 个月，每个月可以用 c[i] 钱 买 h[i] 的幸福，并且每个月最多买一次。每个月可以得到 x 块钱，但是这 x 块钱不能在这个月花掉，只能在下个月以及下个月之后用，计算最后买到的幸福最大值。
思路 ：dp[i][j] 再第 i 个月 拥有 j 幸福所花的钱是最少是多少。
注意 ： 不可以直接用 1e5 来遍历幸福对应的值，会 T 在 test 14（亲身经历）。用滚动数组来优化小下。
什么时候能转移呢，只有当 dp[j] + v[i] <= m * (i - 1) 才可以进行转移
转移方程
dp[j + w[i]] = min(dp[j + w[i]],dp[j] + v[i]);
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;
int v[N], w[N];
long long dp[N * 2]; // 第 i 个 价值 累计起来的总花费
void solve()
{
int n;
long long m; cin >> n >> m;
int sum = 0;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i],sum += w[i];
for (int i = 1; i <= N; i++)
dp[i] = 0x3f3f3f3f3f3f3f;
dp[0] = 0;
for (int i = 1; i <= n; i++) // 商品
{
for (int j = sum ; j >= 0 ; j --)
{
if (m * (i - 1) >= dp[j] + v[i])
{
dp[j + w[i]] = min(dp[j + w[i]],dp[j] + v[i]);
}
}
}
long long ans = 0;
for (long long j = sum ; j >= 0 ; j --)
if (dp[j] != 0x3f3f3f3f3f3f3f)
ans = max(ans, j);
cout << ans << "\n";
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int t; cin >> t;
while (t--)
{
solve();
}
}
F. Cutting Game
题意 ： 给定a * b 的范围格子，每次可以进行一次操作砍掉前 i 行/列 或者 后 i 行/列，俩人轮班操作，最后输出所得到有价值点的个数。
思路 ：
删除前 i 行，一个一个找太麻烦，并且还会找到许多没用的点，因此我们可以想到找满足所有在 x 小于当前位置的点。即对横坐标排序
但是我们又发现，当我们删除 i 列时候，我们会发现还需要对纵坐标进行排序。
所以我们要用两个set来进行插入，一个排x，一个排y。
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;
int v[N], w[N];
int cnt[N];
void solve()
{
cnt[0] = 0; cnt[1] = 0;
int n, m, a, b; cin >> a >> b >> n >> m;
set<pair<int, int>> s1,s2;
for (int i = 1; i <= n; i++)
{
int x, y; cin >> x >> y;
s1.insert({ x,y });
s2.insert({ y,x });
}
int u = 1, d = a, l = 1, r = b;
int cur = 0;
for (int i = 1; i <= m; i++)
{
char c; int x; cin >> c >> x;
if (c == 'U')
{
while (!s1.empty() && s1.begin()->first <= u + x - 1)
{
auto t = *s1.begin();
s1.erase({t});
s2.erase({t.second,t.first});
cnt[cur] ++;
}
u += x;
}
if (c == 'D')
{
while (!s1.empty() && prev(s1.end())->first + x > d)
{
auto t = *prev(s1.end());
s1.erase(t);
s2.erase({t.second, t.first});
cnt[cur] ++;
}
d -= x;
}
if (c == 'L')
{
while(!s2.empty() && s2.begin()->first <= l + x - 1)
{
auto t = *s2.begin();
s2.erase(t);
s1.erase({ t.second, t.first });
cnt[cur] ++;
}
l += x;
}
if (c == 'R')
{
while (!s2.empty() && prev(s2.end())->first > r - x)
{
auto t = *prev(s2.end());
s2.erase(t);
s1.erase({ t.second, t.first });
cnt[cur] ++;
}
r -= x;
}
cur ^= 1;
}
cout << cnt[0] << " " << cnt[1] << "\n";
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int t; cin >> t;
while (t--)
{
solve();
}
}
G. Money Buys Less Happiness Now
题意 ：给你n个数代表每个月可以花费a[i]的钱买1点幸福值，每过个月会给你x块钱，但是新得到得钱在当月没法花，求最后买到的幸福值最大是多少。
思路 : 在买当前的幸福时候，如果买不起，那么我可以在之前买的幸福中挑选出最大的，和当前的价格对比，如果当前的价格低，那么我们可以进行反悔购买，从而买当前的幸福，并且省钱了。
维护买到幸福的代价。用优先对列来维护。
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
using namespace std;
using LL = long long;
const int N = 2e5 + 10;
int a[N];
void solve()
{
int n; cin >> n;
long long x; cin >> x;
priority_queue<int> q;
for (int i = 1; i <= n; i++) cin >> a[i];
long long sum = 0;
for (int i = 1; i <= n; i++)
{
if (sum >= a[i])
{
q.push(a[i]);
sum -= a[i];
}
else
{
if (!q.empty() && q.top() > a[i] && q.top() + sum >= a[i])
{
sum += q.top() - a[i];
q.pop();
q.push(a[i]);
}
}
sum += x;
}
cout << q.size() << "\n";
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int t; cin >> t;
while (t--)
{
solve();
}
}