A - A - ?UPC
题意
给定字符串\(s\)，输出\(s\)首个字符与\(UPC\)组成的字符串
思路
模拟
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve()
{
string s;
cin >> s;
cout << s[0] << "UPC" << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
B - Heavy Snake
题意
有\(n\)条蛇，最初第\(i\)条蛇的长度为\(L_i\)、厚度为\(T_i\)。定义第\(i\)条蛇的重量为\(T_i×L_i\)。对于满足\(1≤k≤D\)的每个整数\(k\)，求每条蛇的长度增加\(k\)时最重的蛇的重量
思路
自定义排序
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
bool cmp(pii& a, pii& b)
{
return a.first * a.second > b.first * b.second;
}
void solve()
{
int n, k;
cin >> n >> k;
vector<pii> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i].first >> v[i].second;
}
for (int i = 1; i <= k; i++)
{
for (int j = 0; j < n; j++)
{
v[j].second++;
}
sort(v.begin(), v.end(), cmp);
cout << v[0].first * v[0].second << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
C - Various Kagamimochi
题意
\(n\)个年糕，第\(i\)个年糕大小为\(a_i\)，按升序输入。对于两个年糕\(i,j\)，当且仅当\(a_i\le a_j\)时可以将\(i\)叠在\(j\)上组成一个年糕。问两两叠加一共能组成多少不同的年糕
思路
由于是升序输入，对于每个年糕，只需要二分找第一个不小于自己大小两倍的年糕的位置累加即可。
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 1e6 + 5;
void solve()
{
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
int ans = 0;
for (int i = 0; i < n; i++)
{
auto p = lower_bound(v.begin(), v.end(), 2 * v[i]);
if (p != v.end())
{
ans += n - (p - v.begin());
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
D - Coming of Age Celebration
题意
有\(n\)个未成年人，第\(i\)个人有\(a_i\)个宝石，并在第\(i\)年成年。当有人成年时，有宝石的成年人会每人会给刚成年的人\(1\)个宝石。求\(n\)年后每人各有多少宝石。
思路
"在第\(i\)年成年"就只用按编号往后推，第\(i\)成年时前\(i-1\)个人都要给他石头(如果有的话)；第\(i\)个人要给后\(n-i\)每人一个石头
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
#define lc p << 1
#define rc p << 1 | 1
const int mxn = 5e5 + 5;
int n;
int t[mxn];
struct tree
{
int l, r, sum, lazy;
}tr[4 * mxn];
int a[mxn];
inline void pushup(int p)
{
tr[p].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(int p)
{
tr[lc].sum += tr[p].lazy * (tr[lc].r - tr[lc].l + 1);
tr[lc].lazy += tr[p].lazy;
tr[rc].sum += tr[p].lazy * (tr[rc].r - tr[rc].l + 1);
tr[rc].lazy += tr[p].lazy;
tr[p].lazy = 0;
}
void build(int p, int l, int r)
{
tr[p].l = l;
tr[p].r = r;
tr[p].lazy = 0;
if (l == r)
{
tr[p].sum = a[l];
return;
}
int mid = l + r >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
pushup(p);
}
void update(int p, int l, int r, int k)
{
if (tr[p].l >= l && tr[p].r <= r) // 查询区间覆盖当前区间
{
tr[p].sum += (tr[p].r - tr[p].l + 1) * k;
tr[p].lazy += k;
return;
}
int mid = tr[p].l + tr[p].r >> 1;
pushdown(p);
if (l <= mid)
{
update(lc, l, r, k);
}
if (r > mid)
{
update(rc, l, r, k);
}
pushup(p);
}
int query(int p, int l, int r)
{
if (tr[p].l >= l && tr[p].r <= r) // 查询区间覆盖当前区间
{
return tr[p].sum;
}
int mid = tr[p].l + tr[p].r >> 1;
pushdown(p);
int res = 0;
// 有交集
if (l <= mid)
{
res += query(lc, l, r);
}
if (r > mid)
{
res += query(rc, l, r);
}
return res;
}
void solve()
{
cin >> n;
vector<int> v(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> v[i];
}
build(1, 1, n);
for (int i = 1; i <= n; i++)
{
int t = query(1, i, i); // 自己收到的
// 给后面的发，直到没有
update(1, i + 1, min(i + v[i] + t, n), 1);
v[i] = max(0LL, v[i] + t - n + i);
}
for (int i = 1; i <= n; i++)
{
cout << v[i] << " ";
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
E - Simultaneous Kagamimochi
题意
同\(C\)，最后求最多同时能制作多少年糕
思路
像\(C\)一样二分选尽量小的根自己组合\(WA\)了很多点，应该不能这么做。
考虑二分答案，最少\(0\)个，最多\(n/2\)个，选择最前与最后的区间配对(小对小，大对大)。
代码
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mxn = 5e5 + 5;
int n;
int a[mxn];
bool check(int x)
{
for (int i = 0; i < x; i++)
{
if (a[i] * 2 > a[n - x + i])
{
return false;
}
}
return true;
}
void solve()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int l = 0, r = n / 2, ans = 0;
while (l <= r)
{
int mid = l + r >> 1;
if (check(mid))
{
l = mid + 1;
ans = mid;
}
else
{
r = mid - 1;
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
while (T--)
{
solve();
}
return 0;
}
F -
题意
思路
代码
点击查看代码
G -
题意
思路
代码
点击查看代码