https://codeforc.es/contest/1355
A. Sequence with Digits 
文章图片
文章图片
当数位中出现0时break
#include
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int main()
{
ll t, n, k;
scanf("%lld", &t);
while(t--)
{
scanf("%lld%lld", &n, &k);
for(ll i = 2;
i <= k;
++i)
{
ll maxx = 0;
ll minn = 9;
ll tmp = n;
while(tmp)
{
maxx = max(maxx, tmp % 10);
minn = min(minn, tmp % 10);
tmp /= 10;
}
n += maxx * minn;
if(minn == 0)
{
break;
}
}
cout< B. Young Explorers
文章图片
文章图片
题意：
给出每个人的无经验值，一个队伍中的人数应 >= 该队中每个人的无经验值，问最多组多少队
【Codeforces Round #643 (Div. 2)】思路：
相同无经验值的人尽量组在一起，剩下的人按无经验值从小到大排个序，cnt记录当前队的人数，当人数 == 当前人的无经验值时，正好组成一个队。
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int main()
{
int t, n, v;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
mapmp;
map::iterator it;
for(int i = 1;
i <= n;
++i)
{
scanf("%d", &v);
mp[v]++;
}
int ans = 0;
vectorvec;
for(it = mp.begin();
it != mp.end();
++it)
{
ans += it -> second / it -> first;
int cnt = it -> second % it -> first;
for(int i = 1;
i <= cnt;
++i)
{
vec.push_back(it -> first);
}
}
int siz = vec.size();
int tmp = 0;
for(int i = 0;
i < siz;
++i)
{
tmp++;
if(vec[i] == tmp)
{
ans++;
tmp = 0;
}
}
cout< C. Count Triangles
文章图片
文章图片
题意：
给出a，b，c，d，令a <= x <= b <= y <= c <= z <= d，问由x，y，z组成的三角形有多少个
思路：
遍历最短边，即 i ~ [a，b]，次短边的范围为[i + b，i + c]，求该区间和最长边可取区间 [c，d] 的交集
分类讨论
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int main()
{
ll a, b, c, d;
while(~scanf("%lld%lld%lld%lld", &a, &b, &c, &d))
{
ll ans = 0;
for(ll i = a;
i <= b;
++i)
{
if(i + b <= c && i + c <= d)
{
ans += i * (i + 1) / 2;
}
else if(i + b <= c && i + c > d)
{
ans += (d - c + 1) * (i + c - d - 1) + (d - c + 2) * (d - c + 1) / 2;
}
else if(i + b > c && i + b <= d && i + c <= d)
{
ans += (i - c + b) * (c - b + 1) + (1 + c - b) * (c - b) / 2;
}
else if(i + b > c && i + b <= d && i + c > d)
{
ans += (i + c - d) * (d - c + 1) + (d - i - b + 1) * (i + b - c) + (1 + d - i - b) * (d - i - b) / 2;
}
else if(i + b > d && i + c > d)
{
ans += (d - c + 1) * (c - b + 1);
}
}
cout << ans << '\n';
}
return 0;
}
D. Game With Array
文章图片
文章图片
#include
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int main()
{
int n, s, k;
while(~scanf("%d%d", &n, &s))
{
if(s < 2 * n)
{
cout<<"NO"<<'\n';
continue;
}
cout<<"YES"<<'\n';
for(int i = 1;
i < n;
++i)
{
cout<<2<<' ';
}
cout< E. Restorer Distance
文章图片
文章图片
文章图片
题意：
有 n 个砖柱，给出每个砖柱的砖数，要求将所有砖柱处理成高度相同的砖柱 ，求总花费最小值
（1）放上一块砖花费A
（2）拿下一块砖花费R
（3）从一个砖柱上移动到另一个砖柱花费M
思路：
砖数和最终花费之间成二次函数关系，三分最终砖柱上有多少块砖，如果A + R > M时直接从一个地方移动到另一个地方
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 5;
ll n, u, d, m, h[N];
ll check(ll num)
{
ll up = 0, down = 0;
for(ll i = 1;
i <= n;
++i)
{
if(h[i] > num)
{
down += h[i] - num;
}
else
{
up += num - h[i];
}
}
ll res = up * u + down * d;
if(u + d > m)
{
ll tmp = min(up, down);
res += m * tmp - (u + d) * tmp;
}
return res;
}int main()
{
while(~scanf("%d%d%d%d", &n, &u, &d, &m))
{
for(ll i = 1;
i <= n;
++i)
{
scanf("%lld", &h[i]);
}
ll l = 0, r = 1e9;
while(l + 10 < r)
{
ll m1 = l + (r - l) / 3;
ll m2 = r - (r - l) / 3;
ll tmp1 = check(m1);
ll tmp2 = check(m2);
if(tmp1 > tmp2)
{
l = m1;
}
else
{
r = m2;
}
}
ll res = inf;
for(ll i = l;
i <= r;
++i)
{
res = min(res, check(i));
}
cout< 
