A. Buy the String
思路:改为0 改为1 和一个都不改时
输出最小即可
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
typedef long long LL;
char str[1010];
int main(){
int T;
cin>>T;
while(T--){
int n,c0,c1,h;
scanf("%d%d%d%d",&n,&c0,&c1,&h);
scanf("%s",str+1);
int n1=0,n0=0;
for(int i=1;i<=n;i++){
if(str[i]=='1'){
n1++;
}else n0++;
}
cout<<min({c0*n0+c1*n1,c1*n+h*n0,c0*n+h*n1})<<endl;
}
return 0;
}
B. Sum of Medians
题意:拆分分成多个数列 使得中位数之和最大
思路:首先进行排序 然后我们从后面看要使得中位数最大
必然多使用后面的数 然而有钥匙的他拆出来是中位数
那么比他大的必然要有n/2个
所以我们从后往前推即可每次向前推n/2+1个
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
typedef long long LL;
int a[N];
int main(){
int T;
cin>>T;
while(T--){
memset(a,0,sizeof a);
int n,k;
cin>>n>>k;
for(int i=1;i<=n*k;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n*k);
LL sum=0;
for(int i=n*k-(n/2),cnt=1;cnt<=k;cnt++,i-=n/2+1){
sum+=a[i];
}
cout<<sum<<endl;
}
return 0;
}
C1. Binary Table (Easy Version)
C2. Binary Table (Hard Version)
2题题意相同 仅在数据规模上减少了 然而就是这个数据规模导致一个比另一个难很多 如果没有掌握方法 那么会是一道很难很长的大模拟题
手上推可以知道 任意4个都能进行如下转换
所以4个全部变为0最多4次
通过后3步我们发现 修改一个点会进行如下几个操作而对别的点没有影响
于是有
所以我们以4个点为块 进行统计操作最终最多操作4次
而因为出现奇数行或者奇数列 所以我们在这个操作前将奇数行
奇数行全部向上转移
奇数列想左转移 其中最后4点进行统计操作对图中进行修改可以省略
但是中途调参 所以加上了
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e3+10;
char g[N][N];
struct Node{
int x1,y1,x2,y2,x3,y3;
};
int main(){
int T;
cin>>T;
while(T--){
vector<Node>ans;
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",g[i]+1);
if(n&1)//奇数行
{
for(int i=1;i<=m;i++)//最后一列全部转换到上边
if(g[n][i]=='1'){
if(i>1){
g[n][i]^=1;
g[n-1][i-1]^=1;
g[n-1][i]^=1;
ans.push_back({n,i,n-1,i,n-1,i-1});
}
else{
g[n][i]^=1;
g[n-1][i+1]^=1;
g[n-1][i]^=1;
ans.push_back({n,i,n-1,i,n-1,i+1});
}
}
}
if(m&1)//奇数列
{
for(int i=1;i<=n;i++)//最后一列全部转换到左边边
if(g[i][m]=='1'){
if(i>1){
g[i][m]^=1;
g[i-1][m-1]^=1;
g[i][m-1]^=1;
ans.push_back({i,m,i,m-1,i-1,m-1});
}
else{
g[i][m]^=1;
g[i+1][m-1]^=1;
g[i][m-1]^=1;
ans.push_back({i,m,i,m-1,i+1,m-1});
}
}
}
for(int i=1;i<=n;i+=2){
for(int j=1;j<=m;j+=2){
int a=0,b=0,c=0,d=0;
if(g[i][j]=='1')a^=1,b^=1,d^=1;
if(g[i+1][j]=='1')a^=1,c^=1,d^=1;
if(g[i][j+1]=='1')a^=1,b^=1,c^=1;
if(g[i+1][j+1]=='1')b^=1,c^=1,d^=1;
if(a){
ans.push_back({i,j,i,j+1,i+1,j});
g[i][j]^=1;
g[i][j+1]^=1;
g[i+1][j]^=1;
}
if(b){
ans.push_back({i,j,i,j+1,i+1,j+1});
g[i][j]^=1;
g[i][j+1]^=1;
g[i+1][j+1]^=1;
}
if(c){
ans.push_back({i,j+1,i+1,j,i+1,j+1});
g[i+1][j]^=1;
g[i][j+1]^=1;
g[i+1][j+1]^=1;
}
if(d){
ans.push_back({i,j,i+1,j,i+1,j+1});
g[i][j]^=1;
g[i+1][j]^=1;
g[i+1][j+1]^=1;
}
}
}
/*for(int i=1;i<=n;i++)
cout<<g[i]+1<<endl;*/
cout<<ans.size()<<endl;
for(Node t:ans){
cout<<t.x1<<" "<<t.y1<<" "<<t.x2<<" "<<t.y2<<" "<<t.x3<<" "<<t.y3<<endl;
}
}
}