ARC075
在省选前一天听说正式选手线画到省二，有了别的女选手，慌的一批，然后刷了一个ARC来稍微找回一点代码感觉
最后还是挂分了，不开心
果然水平退化老年加重啊
C - Bugged
直接做一个dp，找最大值时不找整十的位置即可
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N;
int s[105];
int dp[100005];
void Solve() {
read(N);
dp[0] = 1;
for(int i = 1 ; i <= N ; ++i) {
read(s[i]);
for(int j = 100000 ; j >= 1 ; --j) {
if(j >= s[i]) dp[j] = dp[j] | dp[j - s[i]];
}
}
for(int j = 100000 ; j >= 0 ; --j) {
if(j && j % 10 == 0) continue;
if(dp[j]) {out(j);enter;return;}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
D - Widespread
二分操作次数，相当于每个数集体减去(mid * B)，然后分配(mid)个(A - B)给还未减到0的数
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N;
int64 B,A;
int64 h[MAXN];
void Solve() {
read(N);read(A);read(B);
for(int i = 1 ; i <= N ; ++i) {
read(h[i]);
}
sort(h + 1,h + N + 1);
int64 L = 0,R = 1000000000;
while(L < R) {
int64 mid = (L + R) >> 1;
int64 rem = 0;
for(int i = 1 ; i <= N ; ++i) {
if(h[i] - mid * B > 0) rem += (h[i] - mid * B - 1) / (A - B) + 1;
}
if(rem <= mid) R = mid;
else L = mid + 1;
}
out(L);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
E - Meaningful Mean
每个数都减去K，合法区间即为和大于0的区间
记成前缀和转化成二维偏序的问题
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 200005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,K,tr[MAXN];
int64 a[MAXN],sum[MAXN],val[MAXN];
int lowbit(int x) {return x & (-x);}
void Insert(int x,int v) {
while(x <= N + 1) {
tr[x] += v;
x += lowbit(x);
}
}
int Query(int x) {
int res = 0;
while(x > 0) {
res += tr[x];
x -= lowbit(x);
}
return res;
}
void Solve() {
read(N);read(K);
for(int i = 1 ; i <= N ; ++i) {
read(a[i]);
sum[i] = sum[i - 1] + a[i] - K;
val[i] = sum[i];
}
val[N + 1] = 0;
sort(val + 1,val + N + 2);
int t = lower_bound(val + 1,val + N + 2,sum[0]) - val;
Insert(t,1);
int64 res = 0;
for(int i = 1 ; i <= N ; ++i) {
t = lower_bound(val + 1,val + N + 2,sum[i]) - val;
res += Query(t);
Insert(t,1);
}
out(res);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}
F - Mirrored
如果长度固定为L，每个数位上的数是(b_{i})那么相当于
(rev(N) - N = sum_{i = 0}^{L - 1} (10^{L - i - 1} - 10^{i})b_{i})
然后对称的位置可以合并一下
(rev(N) - N = sum_{i = 0}^{L / 2}(10^{L - i - 1} - 10^{i})(b_{i} - b_{L - i - 1}))
然后我们就相当于对于(0-lfloor frac{L}{2} floor)中的每一个(10^{L - i - 1} - 10^{i})乘上一个(-9)到(9)，组合出来的值是D，然后乘上这种方案的搭配数
然后发现对于一个
(10^{L - i - 1} - 10^{i} > sum_{j = i + 1}^{L / 2} (10^{L - j - 1} - 10^{j}) * 9)
就是当前第i位决定完了，但和D差了大于(10^{L - i - 1} - 10^{i})的时候，我们是无论如何也恢复不了的
所以当D确定时，合法的填法最多只有两个
对于固定的长度(L),最大是(2L_{D})也就是D的十进制长度的二倍，最小是(L_{D})
是二倍的原因是D是正数，我们如果要操作D必然要有在D大小以内的数加减，然后超过(2L_{D})能加减的最小的数也超过了D，我们无法得到一个D
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define MAXN 200005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int64 D;
int Len(int64 D) {
int res = 0;
while(D) {
res++;
D /= 10;
}
return res;
}
int64 pw[20];
int64 v[20],d[20];
int up;
int64 dfs(int64 rem,int dep) {
if(dep == up) return !rem;
int64 t = rem / v[dep];
int64 res = 0;
if(abs(t - 1) <= 9 && abs(rem - (t - 1) * v[dep]) < v[dep]) {
int c = 0;
if(t - 1 >= 0 && !dep) c = 1;
res += (d[t - 1 + 9] - c) * dfs(rem - (t - 1) * v[dep],dep + 1);
}
if(abs(t) <= 9 && abs(rem - t * v[dep]) < v[dep]) {
int c = 0;
if(t >= 0 && !dep) c = 1;
res += (d[t + 9] - c) * dfs(rem - t * v[dep],dep + 1);
}
if(abs(t + 1) <= 9 && abs(rem - (t + 1) * v[dep]) < v[dep]) {
int c = 0;
if(t + 1 >= 0 && !dep) c = 1;
res += (d[t + 1 + 9] - c) * dfs(rem - (t + 1) * v[dep],dep + 1);
}
return res;
}
void Solve() {
read(D);
int Ld = Len(D);
int64 ans = 0;
pw[0] = 1;
for(int i = 1 ; i <= 18 ; ++i) pw[i] = pw[i - 1] * 10;
for(int i = 0 ; i <= 9 ; ++i) {
for(int j = 0 ; j <= 9 ; ++j) {
d[i - j + 9]++;
}
}
for(int i = Ld ; i <= 2 * Ld ; ++i) {
for(int j = 0 ; j <= i / 2 ; ++j) v[j] = pw[i - j - 1] - pw[j];
up = i / 2;
int64 tmp = dfs(D,0);
if(i & 1) tmp *= d[0 + 9];
ans += tmp;
}
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}