Codeforces Round 966 (Div. 3)(A,B,C,D,E,F)

A. Primary Task

签到

void solve()
{string s;cin>>s;bool bl=true;if(s.size()<=2)bl=false;else{if(s.substr(0,2)=="10"){if(s[2]=='0')bl=false;else if(s[2]=='1'&&s.size()<=3)bl=false;	}else bl=false;}if(bl)cout<<"YES\n";else cout<<"NO\n";return ;
}

B. Seating in a Bus

签到

#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
int q[N],a[N];
void solve()
{cin>>n;_rep(i,0,n+1)a[i]=0;_rep(i,1,n)cin>>q[i];_rep(i,1,n){if(i==1)a[q[i]]=1;else if(!a[q[i]-1]&&!a[q[i]+1]){cout<<"NO\n";return;}a[q[i]]=1;}cout<<"YES\n";return;
}

C. Numeric String Template

签到

题意是字符串和数组必须一一对应,注意要开两个map避免一个数字对应多个字母

#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
int q[N];
void solve()
{cin>>n;_rep(i,0,n-1)cin>>q[i];cin>>m;while(m--){string s;cin>>s;map<int,int>mp,has;if(s.size()!=n)cout<<"NO\n";else{bool bl=false;_for(i,s.size()){if(!mp.count(s[i])){if(!has.count(q[i]))mp[s[i]]=q[i],has[q[i]]=s[i];else {cout<<"NO\n";bl=true;break;}}else if(mp[s[i]]!=q[i]){cout<<"NO\n";bl=true;break;}}if(!bl)cout<<"YES\n";}}return ;
}

D. Right Left Wrong

题意,给定长度为n的数组和一个长度为n的LR序列,每次选择L***R都可以获取L~R之间的所有数字的和,但是每个L,R只能用一次,问能得到的最大值是多少

可以发现,无论怎么选择区间,如果两个区间不是相互包含的关系,那么就有更优的解,那就是选两个区间最左边没使用过的L和两个区间最右边没使用过的R,这样可以保证答案最大

举例说明:

第一行不如第二行(第二行多出来两个没有选择的”RL“)

第二行不如第三行(第三行选择最左L和最右R就可以包括第二行的所有情况)

第四行和第三行等价(相交也可以转化为包含的关系)

综上所述,只需要贪心 寻找从1~n 每个L的最右边没使用过的R就可以了,然后用前缀和把每一次的分数加上

#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
int q[N],qian[N];
void solve()
{cin>>n;vector<int>v;_rep(i,1,n)cin>>q[i],qian[i]=q[i]+qian[i-1];string s;cin>>s;s=" "+s;_rep(i,1,n)if(s[i]=='R')v.pb(i);int now=v.size()-1,res=0;_rep(i,1,n){if(s[i]=='L'){if(now>=0&&v[now]>i)res+=qian[v[now]]-qian[i-1],now--;else break;}}cout<<res<<'\n';return ;
}

E. Photoshoot for Gorillas

题意抽象出来就是W个大猩猩每一只高度为a[i],然后在一个n*m的矩阵的格子里面,每次划定一个k*k的正方形,奇观度的值加上正方形内部所有大猩猩的高度,在划定完所有不同位置的k*k正方形后为了使得奇观度最大,大猩猩应该如何放置

思路:一些格子被重复算了,那么重复次数越多的格子放的大猩猩高度尽可能高就能使答案最大,那么就把所有的格子倍率,也就是重复次数算出来,然后把格子倍率和大猩猩高度分别排序就能计算出最后答案

然后就是计算格子倍率的问题,现在只考虑列的重复次数样例如下

这个位置列被重复算的次数最多是2,那么也就是说,列重复的次数取决于这个点到左右两端的距离的最小值,也就是x=min(j,m-j+1),同时重复次数显然不能超过k,所以x=min(min(j,m-j+1),k);

但是还有一个问题,假设这个点到左端点的距离取到最小值,但是此时小正方形右边可能会超出矩形的范围怎么办

那么还要加一个约束条件,假设此时的小正方形的最左边为y,那么就有y+k-1<=m,也就是y<=(m-k+1)

所以最后计算列重复的次数的公式为:x=min(min(j,m-j+1),min(k,m-k+1));

与行重复次数相乘就是某一个点的重复次数

代码实现

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m,k,cn;
int q[N];
void solve()
{cin>>n>>m>>k;cin>>cn;_rep(i,1,cn)cin>>q[i];sort(q+1,q+1+cn,greater<int>());vector<int>now;_rep(i,1,n)_rep(j,1,m)now.pb(min(min(i,n-i+1),min(k,n-k+1))*min(min(j,m-j+1),min(k,m-k+1)));sort(all(now),greater<int>());int res=0;_rep(i,0,cn-1){
//		cout<<q[i+1]<<" "<<now[i]<<endl;res+=q[i+1]*now[i];}cout<<res<<'\n';return ;
}
signed main()
{IOS;int T=1;cin>>T;while(T--)solve();return 0;
}

F. Color Rows and Columns

题意:

针对每一个小矩形（a*b）,每次涂色都选择当前边最短的那条(假设为a),然后使用a次操作获得一分

然后未涂色的矩形又是一个新的小矩形,直到最后一步1*1的矩形,可以用1次操作获得2分,这样操作1为最优的操作

那每个小矩形要操作几次？要从每个小矩形上得到多少分才是最优解？感觉贪心不能解决这个问题,于是用DP

由于要至少得到V分,那么不妨设V为体积

假设f[i]:得分为i的时候操作次数最少为f[i]

那么每一个小矩形显然要选择一种得分v来对应相应的最小操作数为w

显然每一个小矩形都可以计算出几组{v,w}然后选择其中的一组

那么用一个分组背包就可以解决这个问题

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)//
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
int a[N],b[N];
struct aa
{int v,w;
};
int f[10010];
void solve()
{cin>>n>>m;memset(f,0x3f,(m+1)*8);f[0]=0;_rep(i,1,n){int a,b,w=0,v=0;cin>>a>>b;vector<aa>q;if(a>b)swap(a,b);while(b>a){b--;w+=a,v++;q.pb({v,w});}if(a==b&&a==1)q.pb({v+2,w+1});else{_pre(i,a,1){w+=i,v++;q.pb({v,w});if(i==a)continue;w+=i,v++;if(i!=1)q.pb({v,w});else q.pb({v+1,w});}}
//		for(auto i:q)cout<<i.v<<" "<<i.w<<endl;for(int j=m;j>=0;j--)for(int k=0;k<q.size();k++)
//				if(q[k].v<=j)f[j]=min(f[j],f[max(j-q[k].v,0ll)]+q[k].w);}if(f[m]!=0x3f3f3f3f3f3f3f3f)cout<<f[m]<<'\n';else cout<<"-1\n";return ;
}
signed main()
{IOS;int T=1;cin>>T;while(T--)solve();return 0;
}