A. Buy the String
大意：
给定一个01字符串，(c_0)代表购买一个字符0的花费，(c_1)代表购买一个字符1的消费，h代表0和1转换的花费，问购买整个字符串花费最小值
思路：
贪心比较直接购买和转换的价格即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int t, n, c0, c1, h;
string s;
int main(){
cin>>t;
while(t--){
cin >> n >> c0 >> c1 >> h;
cin >> s;
int sum = 0;
if(c0>c1+h){
for (int i = 0; i < s.size();i++){
if(s[i]=='0'){
sum += c1 + h;
}
else{
sum += c1;
}
}
}
else if(c1>c0+h){
for (int i = 0; i < s.size();i++){
if(s[i]=='1'){
sum += c0 + h;
}
else{
sum += c0;
}
}
}
else{
for (int i = 0; i < s.size();i++){
if(s[i]=='1'){
sum += c1;
}
else{
sum += c0;
}
}
}
cout << sum << endl;
}
return 0;
}
B. Sum of Medians
大意：
给定n和k，以及(n*k)个数，问将这些数分成k组，每组n个数，每个组中位数的和最大值为多少
思路：
贪心，排序之后从高到低每隔半个区间长度选取元素即可
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
long long n, t, k, a[N];
int main(){
cin>>t;
while(t--){
cin>>n>>k;
for (int i = 0; i < n * k;i++){
cin >> a[i];
}
sort(a, a + n * k);
double mid = n;
mid = ceil(mid / 2);
long long cnt = 0;
long long sum = 0;
for (int i = (n * k - (n - mid + 1)); cnt<k;i-=(n - mid + 1)){
sum += a[i];
cnt++;
}
cout << sum << endl;
}
return 0;
}
C1&C2. Binary Table
大意：
给定(n*m)的01矩阵，每次可以选择属于一个(2*2)方格里面的三个点，将他们从0变成1，从1变成0，要求给出(n*m)步以内能将矩阵全变为0的方案。
思路：
由于是(n*m)步，所以对于一个点，必须只能一次修改到位，所以先从上到下按行修改，最后对右下角的四个点进行特判即可（不过我写的特判过于复杂）
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int t, n, m;
char b[N][N];
int a[N][N];
vector< pair<int, int> > op;
int main(){
cin>>t;
while(t--){
cin >> n >> m;
op.clear();
int anss = 0;
for (int i = 0; i < n;i++){
for (int j = 0; j < m;j++){
cin >> b[i][j];
if(b[i][j]=='1'){
a[i][j] = 1;
}
else{
a[i][j] = -1;
}
}
}
for (int i = 0; i < n - 2;i++){
for (int j = 0; j < m - 1;j++){
if(a[i][j]==1){
op.push_back({i + 1, j + 1});
op.push_back({i + 1+1, j + 1});
op.push_back({i + 1, j + 1+1});
a[i][j] = -a[i][j];
a[i][j+1] = -a[i][j+1];
a[i+1][j] = -a[i+1][j];
anss++;
}
}
if(a[i][m-1]==1){
op.push_back({i + 1, m-1 + 1});
op.push_back({i + 1+1, m-1 + 1});
op.push_back({i + 1+1, m-1 -1+1});
a[i][m-1] = -a[i][m-1];
a[i+1][m-1] = -a[i+1][m-1];
a[i+1][m-1-1] = -a[i+1][m-1-1];
anss++;
}
}
for (int j = 0; j < m - 2;j++){
if(a[n-2][j]==1){
op.push_back({n - 2 + 1, j + 1});
op.push_back({n - 2 + 1+1, j + 1});
op.push_back({n - 2 + 1, j + 1+1});
anss++;
a[n - 2][j] = -a[n - 2][j];
a[n - 2+1][j] = -a[n - 2+1][j];
a[n - 2][j+1] = -a[n - 2][j+1];
}
if(a[n-1][j]==1){
op.push_back({n - 1 + 1, j + 1});
op.push_back({n - 1 + 1, j + 1+1});
op.push_back({n - 1 + 1-1, j + 1+1});
anss++;
a[n - 1][j] = -a[n - 1][j];
a[n - 1][j+1] = -a[n - 1][j+1];
a[n - 2][j+1] = -a[n - 2][j+1];
}
}
if(a[n-2][m-2]==1&&a[n-1][m-2]==1&&a[n-2][m-1]==1&&a[n-1][m-1]==1){
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==-1&&a[n-1][m-2]==1&&a[n-2][m-1]==1&&a[n-1][m-1]==1){
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==1&&a[n-1][m-2]==-1&&a[n-2][m-1]==1&&a[n-1][m-1]==1){
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==1&&a[n-1][m-2]==1&&a[n-2][m-1]==-1&&a[n-1][m-1]==1){
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==1&&a[n-1][m-2]==1&&a[n-2][m-1]==1&&a[n-1][m-1]==-1){
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==1&&a[n-1][m-2]==-1&&a[n-2][m-1]==-1&&a[n-1][m-1]==1){ //1 0
op.push_back({n - 2 + 1, m - 2 + 1}); //0 1
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==-1&&a[n-1][m-2]==1&&a[n-2][m-1]==1&&a[n-1][m-1]==-1){ //0 1
op.push_back({n - 2 + 1, m - 2 +1}); //1 0
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==1&&a[n-1][m-2]==1&&a[n-2][m-1]==-1&&a[n-1][m-1]==-1){ //1 0
op.push_back({n - 2 + 1, m - 2 + 1}); //1 0
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==-1&&a[n-1][m-2]==-1&&a[n-2][m-1]==1&&a[n-1][m-1]==1){ //0 1
op.push_back({n - 2 + 1, m - 2 + 1}); //0 1
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==1&&a[n-1][m-2]==-1&&a[n-2][m-1]==1&&a[n-1][m-1]==-1){ //1 1
op.push_back({n - 2 + 1, m - 2 + 1}); //0 0
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==-1&&a[n-1][m-2]==1&&a[n-2][m-1]==-1&&a[n-1][m-1]==1){ //0 0
op.push_back({n - 2 + 1, m - 2 + 1}); //1 1
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==1&&a[n-1][m-2]==-1&&a[n-2][m-1]==-1&&a[n-1][m-1]==-1){ //1 0
op.push_back({n - 2 + 1, m - 2 + 1}); //0 0
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==-1&&a[n-1][m-2]==-1&&a[n-2][m-1]==1&&a[n-1][m-1]==-1){ //0 1
op.push_back({n - 2 + 1, m - 2 + 1}); //0 0
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1}); //1 0
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==-1&&a[n-1][m-2]==1&&a[n-2][m-1]==-1&&a[n-1][m-1]==-1){ //0 0
op.push_back({n - 2 + 1+1, m - 2 + 1}); //1 0
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1}); //0 1
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
else if(a[n-2][m-2]==-1&&a[n-1][m-2]==-1&&a[n-2][m-1]==-1&&a[n-1][m-1]==1){ //0 0
op.push_back({n - 2 + 1, m - 2 + 1}); //0 1
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1}); //1 0
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
op.push_back({n - 2 + 1, m - 2 + 1+1});
op.push_back({n - 2 + 1+1, m - 2 + 1});
op.push_back({n - 2 + 1+1, m - 2 + 1+1});
anss++;
}
cout << anss << endl;
int cnt = 0;
for (int i = 0; i < op.size();i++){
cout << op[i].first << ' '<< op[i].second<<' ';
cnt++;
if(cnt==3){
cout << endl;
cnt = 0;
}
}
}
return 0;
}
D. Graph Subset Problem
大意：
给你一个图，从图中找出一个子图：
1.这个子图中每个点的度大于等于k;
2.这个子图是 有k个点，并且是完全图。
符合这两个中的 任意一个即可
思路：
由于第二种图中，每个点的度均为k-1，所以可以先找第二种情况的图，也就是把所有度小于k的点都选出来，如果度小于k-1就直接删掉，如果度正好为k-1就将他的所有相邻的点都加入答案数组，然后暴力判断这个数组里的每一个点是否都有边直接相连，如果是代表找到了第二类子图，直接跳出，否则清空答案数组，然后删掉这个点。最后所有度小于k的点都删掉后，如果还有点，那么一定是第一类子图。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int t,n,m,k,du[N],res[N],cnt,vis[N],flag1,flag2,alive;
vector<int> mp[N];
int main(){
scanf("%d", &t);
while(t--){
scanf("%d%d%d", &n,&m,&k);
alive = n; //还没被删的点数
for (int i = 1; i <= n;i++){
mp[i].clear();
du[i] = 0;
}
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
mp[x].push_back(y);
mp[y].push_back(x);
du[x]++;
du[y]++;
}
if(1ll*k*(k-1)/2>m){
printf("-1
");
continue;
}
queue<int> q;
for (int i = 1; i <= n;i++){
sort(mp[i].begin(), mp[i].end());
if (du[i]<k){
q.push(i);
}
vis[i] = 0;
}
flag2 = 0;
while(!q.empty()){
int now = q.front();
q.pop();
cnt = 0;
if(vis[now]){
continue;
}
if(du[now]==k-1){ //节点度数为k-1,判断是否满足第二种条件
for (int i = 0; i < mp[now].size();i++){
int next = mp[now][i];
if(vis[next]) //被删了
continue;
res[cnt++] = next;
}
flag2 = 1;
for (int i = 0; i < cnt;i++){
for (int j = 0; j < cnt;j++){
if(i==j)
continue;
if (!binary_search(mp[res[i]].begin(),mp[res[i]].end(),res[j])){ //不是完全图
flag2 = 0;
break;
}
}
if(flag2==0){
break;
}
}
}
if(flag2){
res[cnt++] = now;
break;
}
for (int i = 0; i < mp[now].size();i++){ //删掉这个点和它的边
int next = mp[now][i];
if(vis[next])
continue;
du[next]--;
if(du[next]==k-1){
q.push(next);
}
}
vis[now] = 1; //标记已经删过
alive--;
}
if(flag2){
printf("2
");
for (int i = 0; i < cnt;i++){
printf("%d ", res[i]);
}
printf("
");
}
else{
if(alive){
printf("1 %d
",alive);
for (int i = 1; i <= n;i++){
if(!vis[i]){
printf("%d ", i);
}
}
printf("
");
}
else{
printf("-1
");
}
}
}
return 0;
}
E. Greedy Shopping
大意：
给出一个不上升数组
两种操作，1,x,y代表将下标为1到x的元素设为(max(a_i,y))
2,x,y代表从下标为x的元素开始到下标为n的元素为止，遇到小于y的元素就将y减去这个元素，问能够减几次。
思路：
线段树维护区间的最大值、最小值以及区间和即可，对于第二种操作，如果当前区间的最小值也大于y，那么可以直接跳过这个区间，如果当前区间的区间和小于等于y，可以直接减去这个区间。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int const N = 5e5 + 10;
LL lazy[N << 2],k;
int a[N], n, m;
struct node{
LL maxn=0, minn=0,sum=0;
} dat[N << 2];
// 上传标记，每次左右子树建树/区间修改完都需要上传
void pushup(int rt) {
dat[rt].sum = dat[rt << 1].sum + dat[rt << 1 | 1].sum ;
dat[rt].maxn = max(dat[rt << 1].maxn , dat[rt << 1 | 1].maxn );
dat[rt].minn = min(dat[rt << 1].minn , dat[rt << 1 | 1].minn );
}
// 建树
void build(int rt, int l, int r) {
if (l == r) { // 递归到叶节点
dat[rt].sum = a[l];
dat[rt].minn = a[l];
dat[rt].maxn = a[l];
lazy[rt] = 0;
return;
}
// 递归建立左右子树
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
pushup(rt); // 上传
}
// 下传，下传标记，同时改变dat数组
void pushdown(int rt, int l, int r) {
if (lazy[rt]) { // 如果有标记
int mid = (l + r) >> 1;
// 把标记给左右子树
lazy[rt << 1] = lazy[rt];
lazy[rt << 1 | 1] = lazy[rt];
dat[rt << 1].maxn = lazy[rt];
dat[rt << 1 | 1].minn = lazy[rt];
dat[rt << 1].maxn = lazy[rt];
dat[rt << 1 | 1].minn = lazy[rt];
// 改变dat
dat[rt << 1].sum = (mid - l + 1) * lazy[rt];
dat[rt << 1 | 1].sum = (r - mid) * lazy[rt];
// rt标记清空
lazy[rt] = 0;
}
return;
}
// 区间修改: [L, R] += x
void modify(int rt, int l, int r, int L, int R, int x) {
if(dat[rt].minn>x){
return;
}
if (L <= l && r <= R && dat[rt].maxn<=x) { // 如果当前区间被完全包含
dat[rt].sum = 1LL* (r - l + 1) * x; // 修改当前区间的dat值
lazy[rt] = x; // 改变懒标记
dat[rt].maxn = x;
dat[rt].minn = x;
return ;
}
pushdown(rt, l, r); // 下传
// 递归左右子树修改区间
int mid = (l + r) >> 1;
if (L <= mid) modify(rt << 1, l, mid, L, R, x);
if (mid < R) modify(rt << 1 | 1, mid + 1, r, L, R, x);
pushup(rt); // 上传
return;
}
// 区间查询:获得[L, R]的区间和
LL query(int rt, int l, int r, int L, int R) {
if(dat[rt].minn>k){
return 0 ;
}
if (L <= l && r <= R && dat[rt].sum<=k){
k -= dat[rt].sum;
return r - l + 1; // 如果[l, r]被完全包含于[L, R]
}
pushdown(rt, l, r); // 标记下传
// 递归加上左右子树
int mid = (l + r) >> 1;
LL res = 0;
if (L <= mid) res += query(rt << 1, l, mid, L, R);
if (mid < R) res += query(rt << 1 | 1, mid + 1, r, L, R);
return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); // 读入数组
build(1, 1, n); // 建树
for (int i = 1, a, b, x, op; i <= m; ++i) {
scanf("%d", &op);
if (op == 1) {
scanf("%d%d", &a, &b);
modify(1, 1, n, 1, a, b);
}
else {
scanf("%d%d", &a, &k);
printf("%lld
", query(1, 1, n, a, n));
}
}
return 0;
}