Codeforces Round #684 (Div. 2) 题解
日期： 2020-11-20 分类： 跨站数据测试 333次阅读
题目链接：Codeforces Round #684 (Div. 2)
A. Buy the String
贪心
int main()
{
int t;
cin >> t;
while(t--)
{
int n,c0,c1,h;
cin >> n >> c0 >> c1 >> h;
string s; cin >> s;
int ans=0;
if(c0>c1)
{
if(h+c1<c0)
{
for(int i=0;i<s.length();i++)
{
if(s[i]=='0') ans+=(h+c1);
else ans+=c1;
}
}
else{
for(int i=0;i<s.length();i++)
{
if(s[i]=='1') ans+=c1;
else ans+=c0;
}
}
}
else {
if(h+c0<c1)
{
for(int i=0;i<s.length();i++)
{
if(s[i]=='1') ans+=(h+c0);
else ans+=c0;
}
}
else {
for(int i=0;i<s.length();i++)
{
if(s[i]=='1') ans+=c1;
else ans+=c0;
}
}
}
cout << ans << endl;
}
}
B. Sum of Medians
贪心，排序数组后，每个分好数组的前一半都用小的填补，剩下的按照数组序列一行一行补齐即可。
ll a[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,k; scanf("%d%d",&n,&k);
for(int i=1;i<=n*k;i++) scanf("%lld",&a[i]);
sort(a+1,a+1+n*k);
ll ans=0;
for(int i=k*(ceil(n*1.0/2)-1)+1;i<=n*k;i+=n-ceil(n*1.0/2)+1)
{
ans+=a[i];
}
printf("%lld\n",ans);
}
}
C1. Binary Table (Easy Version)
C1和C2的不同在于操作数的限制。
简单版本里，我们不难发现任何一个2*2矩阵都可以被转化为全0矩阵，所以枚举给出矩阵里的所有2*2矩阵即可，可以证明操作数最大为3nm。
本人的暴力真的很暴力。。。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std;
//extern "C"{void *__dso_handle=0;}
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define lowbit(x) x&-x
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1e2+10;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
char g[maxn][maxn];
struct Node
{
int x1,x2,x3,y1,y2,y3;
Node(int x1,int y1,int x2,int y2,int x3,int y3):x1(x1),y1(y1),x2(x2),y2(y2),x3(x3),y3(y3) {}
};
vector<Node> fin;
int main()
{
int t;
cin >> t;
while(t--)
{
fin.clear();
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",g[i]+1);
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m-1;j++)
{
int cnt=0;
if(g[i][j]=='1') cnt++;
if(g[i][j+1]=='1') cnt++;
if(g[i+1][j]=='1') cnt++;
if(g[i+1][j+1]=='1') cnt++;
if(cnt==1)
{
if(g[i][j]=='1')
{
fin.push_back(Node(i,j,i,j+1,i+1,j));
fin.push_back(Node(i,j,i,j+1,i+1,j+1));
fin.push_back(Node(i,j,i+1,j,i+1,j+1));
}
if(g[i][j+1]=='1')
{
fin.push_back(Node(i,j,i,j+1,i+1,j+1));
fin.push_back(Node(i,j+1,i+1,j,i+1,j+1));
fin.push_back(Node(i,j,i,j+1,i+1,j));
}
if(g[i+1][j]=='1')
{
fin.push_back(Node(i,j,i+1,j,i+1,j+1));
fin.push_back(Node(i,j+1,i+1,j,i+1,j+1));
fin.push_back(Node(i,j,i,j+1,i+1,j));
}
if(g[i+1][j+1]=='1')
{
fin.push_back(Node(i,j+1,i+1,j,i+1,j+1));
fin.push_back(Node(i,j,i,j+1,i+1,j+1));
fin.push_back(Node(i,j,i+1,j,i+1,j+1));
}
}
if(cnt==2)
{
if(g[i][j]=='1' && g[i][j+1]=='1')
{
fin.push_back(Node(i,j,i+1,j,i+1,j+1));
fin.push_back(Node(i,j+1,i+1,j,i+1,j+1));
}
if(g[i][j]=='1' && g[i+1][j+1]=='1')
{
fin.push_back(Node(i,j+1,i+1,j,i+1,j+1));
fin.push_back(Node(i,j,i,j+1,i+1,j));
}
if(g[i][j]=='1' && g[i+1][j]=='1')
{
fin.push_back(Node(i,j,i,j+1,i+1,j+1));
fin.push_back(Node(i,j+1,i+1,j,i+1,j+1));
}
if(g[i][j+1]=='1' && g[i+1][j]=='1')
{
fin.push_back(Node(i,j,i+1,j,i+1,j+1));
fin.push_back(Node(i,j,i,j+1,i+1,j+1));
}
if(g[i][j+1]=='1' && g[i+1][j+1]=='1')
{
fin.push_back(Node(i,j,i,j+1,i+1,j));
fin.push_back(Node(i,j,i+1,j,i+1,j+1));
}
if(g[i+1][j]=='1' && g[i+1][j+1]=='1')
{
fin.push_back(Node(i,j,i,j+1,i+1,j));
fin.push_back(Node(i,j,i,j+1,i+1,j+1));
}
}
if(cnt==3)
{
if(g[i][j]=='0')
{
fin.push_back(Node(i,j+1,i+1,j,i+1,j+1));
}
if(g[i][j+1]=='0')
{
fin.push_back(Node(i,j,i+1,j,i+1,j+1));
}
if(g[i+1][j]=='0')
{
fin.push_back(Node(i,j,i,j+1,i+1,j+1));
}
if(g[i+1][j+1]=='0')
{
fin.push_back(Node(i,j,i,j+1,i+1,j));
}
}
if(cnt==4)
{
fin.push_back(Node(i,j,i,j+1,i+1,j+1));
fin.push_back(Node(i,j,i+1,j,i+1,j+1));
fin.push_back(Node(i,j,i,j+1,i+1,j));
fin.push_back(Node(i,j+1,i+1,j,i+1,j+1));
}
g[i][j]=g[i][j+1]=g[i+1][j]=g[i+1][j+1]='0';
}
printf("%lu\n",fin.size());
for(int i=0;i<fin.size();i++)
{
printf("%d %d %d %d %d %d\n",fin[i].x1,fin[i].y1,fin[i].x2,fin[i].y2,fin[i].x3,fin[i].y3);
}
}
}
C2.Binary Table (Hard Version)
还在debug中。。
E.Greedy Shopping
很裸的一棵线段树，但是有些优化做不好很容易T，我一开始没有维护最小值这个点导致线段树更新和查询没有剪枝，T了，最后用最小值把许多不必要的情况剪枝才过。
线段树需要维护三个点，最大值、最小值以及区间和。
操作1就是区间覆盖
操作2就区间查询
虽然很基础但是在比赛时间内写出来还是得多多练习。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
using namespace std;
//extern "C"{void *__dso_handle=0;}
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define lowbit(x) x&-x
const double PI=acos(-1.0);
const double eps=1e-6;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=2e5+10;
const int maxm=100+10;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll a[maxn];
ll addv[maxn<<2];
struct Tree
{
ll summ,maxx,minn;
}tree[maxn<<2];
void pushup(int p)
{
tree[p].summ=tree[p*2].summ+tree[p*2+1].summ;
tree[p].maxx=max(tree[p*2].maxx,tree[p*2+1].maxx);
tree[p].minn=min(tree[p*2].minn,tree[p*2+1].minn);
}
void build(int l,int r,int p)
{
if(l==r) { tree[p].summ=tree[p].maxx=tree[p].minn=a[l]; addv[p]=0; return ; }
int mid=(l+r)>>1;
build(l, mid, p*2);
build(mid+1, r, p*2+1);
pushup(p);
}
void pushdown(int p,int l,int r)
{
if(addv[p])
{
int mid=(l+r)/2;
tree[p*2].summ=addv[p]*(mid-l+1);
tree[p*2+1].summ=addv[p]*(r-mid);
tree[p*2].maxx=tree[p*2+1].maxx=addv[p];
tree[p*2].minn=tree[p*2+1].minn=addv[p];
addv[p*2]=addv[p*2+1]=addv[p];
addv[p]=0;
}
}
void update(int l,int r,int p,int ql,int qr,ll num)
{
if(ql>qr) return ;
if(tree[p].minn>=num) return ;
if(ql<=l && qr>=r && tree[p].maxx<num)
{
tree[p].summ=num*(r-l+1);
addv[p]=tree[p].maxx=tree[p].minn=num;
return ;
}
pushdown(p,l,r);
int mid=(l+r)>>1;
if(ql<=mid) update(l,mid,p*2,ql,qr,num);
if(qr>mid) update(mid+1,r,p*2+1,ql,qr,num);
pushup(p);
}
int num=0;
int query(int l,int r,int p,int ql,int qr)
{
if(tree[p].minn>num) return 0;
if(ql<=l && qr>=r && tree[p].summ<=num)
{
num-=tree[p].summ;
return (r-l+1);
}
pushdown(p,l,r);
int mid=(l+r)/2;
int ans=0;
if(ql<=mid) ans+=query(l,mid,p*2,ql,qr);
if(qr>mid) ans+=query(mid+1,r,p*2+1,ql,qr);
pushup(p);
return ans;
}
int main()
{
ll n,q;
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,n,1);
while (q--) {
int opt,x;
ll y; scanf("%d",&opt);
if(opt==1)
{
scanf("%d%lld",&x,&y);
update(1,n,1,1,x,y);
}
else
{
int sta;
scanf("%d%d",&sta,&num);
printf("%d\n",query(1,n,1,sta,n));
}
}
}
除特别声明，本站所有文章均为原创，如需转载请以超级链接形式注明出处：SmartCat's Blog
标签：cf
上一篇： 硬件项目如何避免改版？
精华推荐