昨天只有3题，D题太难写了呜呜呜
A题上来写错WA了一发
B题开始写的二分，但是一直WA，前几天写二分写傻了，后面发现直接模拟不就完了吗？
C题直接秒了，从低位往高位放，看看能不能够到下一个位置。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const int N=105;
ll b[15],n,k,a[N],ans,z;
int main() {
// freopen("data.in","r",stdin);
b[0]=1;
fo(i,1,15) b[i]=b[i-1]*10ll;
int T;
scanf("%d",&T);
while (T--){
scanf("%lld %lld",&n,&k);
fo(i,1,n) scanf("%lld",&a[i]);
ans=0;
fo(i,1,n) {
if (i==n) {
ans+=(k+1)*b[a[i]];
break;
}
z=b[a[i+1]-a[i]]-1;
if (z<=k) {
ans+=z*b[a[i]];
k-=z;
}
else{
ans+=(k+1)*b[a[i]];
k=0;
break;
}
}
printf("%lld\n",ans);
}
return 0;
}
D是真的不好写，vp的时候还想错了一些地方
首先是注意到第一列，第一列是肯定处于左边的，因此第一列最大值所在行必然为R，最小值所在行必然为B
最后一列类似
我们先考虑左边的矩阵，从左往右处理，假如为已经确定为R的数中，最小值为a
确定为B的数中，最大值为b，那么假设处理到第i列，所有前缀最大值大于a的行都应该是R，前缀最小值小于b的行都应该是B。同时需要更新a，b，我们可以开一个堆来维护，因为它可能更新很多次，不能够直接顺序循环。
右边处理类似，注意判断是否冲突
最后是合并的时候，一样的也是开个堆来更新
最后那些没有确定的行就全部填一样的就行。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const int N=5e5+5;
int n,m,x;
vector<int> v[N];
vector<int> l[N],r[N];
vector<int> mnl[N],mxl[N],mnr[N],mxr[N];
int mn[N],mx[N];
bool p[N],q[N];
int cmx,cmn,o,w;
int ans[N];
struct node1{
int mn,mx,id;
};
struct node2{
int mn,mx,id;
};
bool operator < (const node1 &a,const node1 &b){
return a.mx<b.mx;
}
bool operator < (const node2 &a,const node2 &b){
return a.mn>b.mn;
}
priority_queue<node1> xx;
priority_queue<node2> yy;
void P(int x){
if (x==1) printf("B");
else printf("R");
}
void get(int &a,int &b,int i){
a=-10; b=1e9;
fo(j,0,n-1) {
a=max(a,v[i][j]);
b=min(b,v[i][j]);
}
}
void work(vector<int> l[], bool *bz,vector<int> lmn[],vector<int> lmx[]) {
int a,b;
fo(i,1,m) l[i].clear(), lmn[i].clear(), lmx[i].clear();
bool flag=1;
get(cmx,cmn,1);
if (cmn == cmx) return;
bz[1]=1;
fo(i,0,n-1) {
mn[i]=mx[i]=v[1][i];
lmn[1].push_back(mn[i]);
lmx[1].push_back(mx[i]);
if (v[1][i]==cmn) l[1].push_back(1);
else{
if (v[1][i]==cmx) l[1].push_back(2);
else l[1].push_back(0);
}
}
a=cmx;
b=cmn;
fo(i,2,m-1) {
fo(j,0,n-1){
l[i].push_back(l[i-1][j]);
mn[j]=min(mn[j], v[i][j]);
mx[j]=max(mx[j], v[i][j]);
lmn[i].push_back(mn[j]);
lmx[i].push_back(mx[j]);
}
while (!xx.empty()) xx.pop();
while (!yy.empty()) yy.pop();
fo(j,0,n-1) {
xx.push((node1){mn[j],mx[j]});
yy.push((node2){mn[j],mx[j]});
}
while (!xx.empty()) {
auto k=xx.top();
o=k.mn; w=k.mx; xx.pop();
if (a<=w) a=min(a,o);
else break;
}
while (!yy.empty()) {
auto k=yy.top();
o=k.mn; w=k.mx; yy.pop();
if (b>=o) b=max(b,w);
else break;
}
fo(j,0,n-1) {
if (mx[j]>=a && mn[j]<=b) flag=0;
}
if (!flag) return;
if (a<=b) return;
bz[i]=1;
fo(j,0,n-1) {
if (mx[j]>=a) l[i][j]=2;
if (mn[j]<=b) l[i][j]=1;
}
}
}
bool check(int k){
memset(ans,0,sizeof(ans));
int al=1e9,ar=-10;
fo(i,0,n-1) {
if (l[k][i]==2 || r[k][i]==2) {
al=min(al, mnl[k][i]);
ar=max(ar, mxr[k][i]);
}
}
while (!xx.empty()) xx.pop();
while (!yy.empty()) yy.pop();
fo(i,0,n-1) {
xx.push((node1){mnl[k][i],mxl[k][i],i});
yy.push((node2){mnr[k][i],mxr[k][i],i});
}
while (!xx.empty() || !yy.empty()) {
if (!xx.empty() && xx.top().mx >=al) {
auto k1=xx.top();
al=min(al, mnl[k][k1.id]);
ar=max(ar, mxr[k][k1.id]);
xx.pop();
}
else{
if (!yy.empty() && yy.top(). mn <=ar) {
auto k1=yy.top();
al=min(al, mnl[k][k1.id]);
ar=max(ar, mxr[k][k1.id]);
yy.pop();
}
else{
break;
}
}
}
int bl=-10,br=1e9;
fo(i,0,n-1) {
if (l[k][i]==1 || r[k][i]==1) {
bl=max(bl, mxl[k][i]);
br=min(br, mnr[k][i]);
}
}
while (!xx.empty()) xx.pop();
while (!yy.empty()) yy.pop();
fo(i,0,n-1) {
xx.push((node1){mnr[k][i],mxr[k][i],i});
yy.push((node2){mnl[k][i],mxl[k][i],i});
}
while (!xx.empty() || !yy.empty()) {
if (!xx.empty() && xx.top().mx >=br) {
auto k1=xx.top();
bl=max(bl, mxl[k][k1.id]);
br=min(br, mnr[k][k1.id]);
xx.pop();
}
else{
if (!yy.empty() && yy.top(). mn <=bl) {
auto k1=yy.top();
bl=max(bl, mxl[k][k1.id]);
br=min(br, mnr[k][k1.id]);
yy.pop();
}
else{
break;
}
}
}
if (al<=bl && ar>=br) return 0;
fo(i,0,n-1) {
if (mxl[k][i] >=al) ans[i]=2;
if (mnr[k][i] <=ar) ans[i]=2;
if (mnl[k][i] <=bl) ans[i]=1;
if (mxr[k][i] >=br) ans[i]=1;
}
A;
fo(i,0,n-1) P(max(ans[i],1));
printf(" %d\n",k);
return 1;
}
int main() {
// freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while (T--){
scanf("%d %d",&n,&m);
fo(i,1,m) v[i].clear();
fo(i,1,m) p[i]=q[i]=0;
fo(i,1,n) {
fo(j,1,m) {
scanf("%d",&x);
v[j].push_back(x);
}
}
work(l,p,mnl,mxl);
fo(i,1,m/2) swap(v[i],v[m-i+1]);
work(r,q,mnr,mxr);
fo(i,1,m/2) {
swap(q[i],q[m-i]);
swap(r[i],r[m-i]);
swap(mnr[i],mnr[m-i]);
swap(mxr[i],mxr[m-i]);
}
fo(i,1,m-1) {
if (!q[i]) continue;
fo(j,0,n-1) if (r[i][j]) r[i][j]=3-r[i][j];
}
int t=0;
bool pd;
fo(i,1,m-1) {
if (p[i] && q[i]){
pd=1;
fo(j,0,n-1){
if (l[i][j] && r[i][j] && l[i][j]!=r[i][j]) pd=0;
}
if (!pd) continue;
if (check(i)) {
t=i;
break;
}
}
}
if (!t) {
B;
}
}
return 0;
}
//1
//4 2
//9 14
//12 3
//3 8
//13 13
题解貌似很短，有空看看。
- Educational Codeforces Round 116educational codeforces round 116 educational codeforces round rated educational codeforces round 151 construction educational codeforces round cf-educational educational codeforces round educational codeforces round 147 educational codeforces round 158 educational codeforces contest round educational codeforces monsters round educational codeforces balance round