A
讨论三种情况，不换/全换成0/全换成1 ,取一个花费最小值
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 20;
int n, c0, c1, h;
char str[N];
int main()
{
int T;
scanf("%d", &T);
while(T -- )
{
scanf("%d%d%d%d%s", &n, &c0, &c1, &h, str);
int a = 0, b = 0;
for(int i = 0; i < n; ++ i)
if(str[i] == '0') a ++;
else b ++;
int res = 1e9;
res = min(res, n * c0 + h * b);
res = min(res, n * c1 + h * a);
res = min(res, c0 * a + c1 * b);
printf("%d
", res);
}
return 0;
}
B
排序之后，从(n imes k - dfrac{n}{2})开始取，每隔(dfrac{n}{2})取一个，取(k)个即可
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1000 + 20;
int n, k, a[N * N];
int main()
{
int T;
scanf("%d", &T);
while(T -- )
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n * k; ++ i) scanf("%d", &a[i]);
sort(a + 1, a + n * k + 1);
LL res = 0;
for(int i = n * k - n / 2, j = 1; j <= k; i -= n / 2 + 1, ++ j)
res += a[i];
printf("%lld
", res);
}
return 0;
}
C1/C2
按行处理，处理前(n - 2)行，最后(2)行按列处理，处理到(m - 2)列，最后(4)个格子讨论即可.
#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 5;
int n, m;
int a[N][N];
struct zt
{
int a, b, c, d, e, f;
};
vector<zt> vec;
int main()
{
int T;
scanf("%d",&T);
while(T --)
{
vec.clear();
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
scanf("%1d", &a[i][j]);
for(int i = 1; i <= n - 2; ++ i)
for(int j = 1; j <= m; ++ j)
if(a[i][j])
{
vec.push_back((zt){i, j, i + 1, j, i + 1, j < m ? j + 1 : j - 1});
a[i][j] ^= 1; a[i + 1][j] ^= 1; a[i + 1][j < m ? j + 1 : j - 1] ^= 1;
}
for(int j = 1; j <= m - 2; ++ j)
for(int i = n - 1; i <= n; ++ i)
if(a[i][j])
{
vec.push_back((zt){i, j, i, j + 1, i < n ? i + 1 : i - 1, j + 1});
a[i][j] ^= 1; a[i][j + 1] ^= 1; a[i < n ? i + 1 : i - 1][j + 1] ^= 1;
}
int num = a[n - 1][m - 1] + a[n - 1][m] + a[n][m - 1] + a[n][m];
if(num == 1)
{
if(a[n][m])
{
vec.push_back((zt){n, m, n, m - 1, n - 1, m - 1});
vec.push_back((zt){n, m, n, m - 1, n - 1, m});
vec.push_back((zt){n, m, n - 1, m, n - 1, m - 1});
}
if(a[n - 1][m])
{
vec.push_back((zt){n - 1, m, n - 1, m - 1, n, m - 1});
vec.push_back((zt){n - 1, m, n - 1, m - 1, n, m});
vec.push_back((zt){n - 1, m, n, m, n, m - 1});
}
if(a[n][m - 1])
{
vec.push_back((zt){n, m - 1, n - 1, m - 1, n - 1, m});
vec.push_back((zt){n, m - 1, n - 1, m - 1, n, m});
vec.push_back((zt){n, m - 1, n, m, n - 1, m});
}
if(a[n - 1][m - 1])
{
vec.push_back((zt){n - 1, m - 1, n, m - 1, n, m});
vec.push_back((zt){n - 1, m - 1, n, m - 1, n - 1, m});
vec.push_back((zt){n - 1, m - 1, n - 1, m, n, m});
}
}
if(num == 2)
{
if(a[n - 1][m - 1] && a[n - 1][m])
{
vec.push_back((zt){n - 1, m - 1, n, m - 1, n, m});
vec.push_back((zt){n, m - 1, n, m, n - 1, m});
}
if(a[n][m - 1] && a[n][m])
{
vec.push_back((zt){n, m - 1, n - 1, m - 1, n - 1, m});
vec.push_back((zt){n, m, n - 1, m, n - 1, m - 1});
}
if(a[n - 1][m - 1] && a[n][m - 1])
{
vec.push_back((zt){n - 1, m - 1, n - 1, m, n, m});
vec.push_back((zt){n, m - 1, n - 1, m, n, m});
}
if(a[n - 1][m] && a[n][m])
{
vec.push_back((zt){n - 1, m, n - 1, m - 1, n, m - 1});
vec.push_back((zt){n, m, n, m - 1, n - 1, m - 1});
}
if(a[n - 1][m - 1] && a[n][m])
{
vec.push_back((zt){n - 1, m - 1, n - 1, m, n, m - 1});
vec.push_back((zt){n, m, n - 1, m, n, m - 1});
}
if(a[n][m - 1] && a[n - 1][m])
{
vec.push_back((zt){n - 1, m, n - 1, m - 1, n, m});
vec.push_back((zt){n, m - 1, n - 1, m - 1, n, m});
}
}
if(num == 3)
{
vector<int> tmp;
if(a[n][m]) tmp.push_back(n), tmp.push_back(m);
if(a[n - 1][m - 1]) tmp.push_back(n - 1), tmp.push_back(m - 1);
if(a[n - 1][m]) tmp.push_back(n - 1), tmp.push_back(m);
if(a[n][m - 1]) tmp.push_back(n), tmp.push_back(m - 1);
vec.push_back((zt){tmp[0], tmp[1], tmp[2], tmp[3], tmp[4], tmp[5]});
}
if(num == 4)
{
vec.push_back((zt){n - 1, m - 1, n - 1, m, n, m - 1});
vec.push_back((zt){n, m, n, m - 1, n - 1, m - 1});
vec.push_back((zt){n, m, n, m - 1, n - 1, m});
vec.push_back((zt){n, m, n - 1, m, n - 1, m - 1});
}
printf("%d
", vec.size());
for(int i = 0; i < vec.size(); ++ i)
printf("%d %d %d %d %d %d
", vec[i].a, vec[i].b, vec[i].c, vec[i].d, vec[i].e, vec[i].f);
}
return 0;
}
E
线段树，维护一个min和max和区间和，利用单调不增的性质进行修改和查询
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, m, w[N];
struct Node
{
int l, r;
LL maxv, minv, sum, lazy;
}tr[N * 4];
void pushup(int u)
{
tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
tr[u].minv = min(tr[u << 1].minv, tr[u << 1 | 1].minv);
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if(root.lazy)
{
left.maxv = right.maxv = root.lazy;
left.minv = right.minv = root.lazy;
left.sum = (left.r - left.l + 1) * root.lazy;
right.sum = (right.r - right.l + 1) * root.lazy;
left.lazy = right.lazy = root.lazy;
root.lazy = 0;
}
}
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, r, w[r], w[r], w[r], 0};
else
{
tr[u] = {l, r, 0, 0, 0, 0};
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int v)
{
if(tr[u].minv >= v) return;
if(tr[u].l >= l && tr[u].r <= r && tr[u].maxv < v)
{
tr[u].lazy = v;
tr[u].minv = tr[u].maxv = v;
tr[u].sum = (LL)(tr[u].r - tr[u].l + 1) * v;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, v);
if(r > mid) modify(u << 1 | 1, l, r, v);
pushup(u);
}
}
int query(int u, int l, int r, int &v)
{
if(tr[u].minv > v) return 0;
if(tr[u].l >= l && tr[u].r <= r && tr[u].sum <= v)
{
v -= tr[u].sum;
return tr[u].r - tr[u].l + 1;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if(l <= mid) res = query(u << 1, l, r, v);
if(r > mid) res += query(u << 1 | 1, l, r, v);
return res;
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
build(1, 1, n);
while(m -- )
{
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if(op == 1) modify(1, 1, x, y);
else printf("%d
", query(1, x, n, y));
}
return 0;
}
2020.11.19