A
分析
发现一个省只能有两种形态：一种是2*2的正方形，另一种是绕着矩形的最大边界的一整圈
所以，n和m一定均为偶数，且一个省最少有4个市，否则就得是12个了围一圈的情况，k最小的话就全部按照一圈一圈的围绕
那么有限制
m
a
x
{
n
,
m
}
2
≤
k
≤
n
m
4
且
k
≠
n
m
4
?
1
\frac{max\{n,m\}}{2} \le k \le \frac{nm}{4} 且 k \ne \frac{nm}{4}-1
2max{n,m}?≤k≤4nm?且k?=4nm??1，且当n=m时，
k
≠
m
a
x
{
n
,
m
}
2
+
1
k \ne \frac{max\{n,m\}}{2}+1
k?=2max{n,m}?+1至少多两个
有了以上的判定条件，我们可以每次选择对于当前的矩形选择绕外周一圈/填上两行/填左两列，然后递归解决剩下的子矩形即可
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int T;
vector <int> a[maxn];
bool ok(int n,int m,int k)
{
if(n&1 || m&1) return false;
if(k<max(n,m)/2 || k>m*n/4 || k==m*n/4-1) return false;
if(n==m && k==n/2+1) return false;
return true;
}
void solve(int l,int r,int u,int d,int k)
{
if(l>r || u>d) return;
if(ok(d-u-1,r-l-1,k-1))
{
for(int i=l;i<=r;i++) a[u][i]=a[d][i]=k;
for(int i=u;i<=d;i++) a[i][l]=a[i][r]=k;
solve(l+1,r-1,u+1,d-1,k-1);
return;
}
if(ok(d-u-1,r-l+1,k-(r-l+1)/2))
{
for(int i=l;i<=r;i++) a[u][i]=a[u+1][i]=k-(i-l)/2;
solve(l,r,u+2,d,k-(r-l+1)/2);
return;
}
if(ok(d-u+1,r-l-1,k-(d-u+1)/2))
{
for(int i=u;i<=d;i++) a[i][l]=a[i][l+1]=k-(i-u)/2;
solve(l+2,r,u,d,k-(d-u+1)/2);
}
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&T);
while(T--)
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
if(!ok(n,m,k))
{
printf("NO\n");
continue;
}
printf("YES\n");
for(int i=1;i<=n;i++) a[i].resize(m+1);
solve(1,m,1,n,k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) printf("%d ",a[i][j]);
printf("\n");
}
}
return 0;
}
B
分析
对于每次询问，先二分答案，然后利用主席树去模拟，时间复杂度上界
O
(
q
n
l
o
g
3
n
)
O(qnlog^3n)
O(qnlog3n)
但是由于十分不满，竟然能有85pts，甚至调到5s的话能过。。
暴力代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e5+5;
int a[maxn],c[maxn],cnt;
ll sum[maxn];
int n,q,ql,qr;
ll k;
int rt[maxn],tot;
struct seg
{
int ls,rs,v;
ll tot;
}tr[maxn<<5];
#define lson tr[u].ls
#define rson tr[u].rs
void insert(int &u,int lst,int l,int r,int pos)
{
u=++tot;
tr[u]=tr[lst];
tr[u].v++; tr[u].tot+=c[pos];
if(l==r)
return;
int mid=l+r>>1;
if(pos<=mid) insert(tr[u].ls,tr[lst].ls,l,mid,pos);
else insert(tr[u].rs,tr[lst].rs,mid+1,r,pos);
}
int kth(int u,int v,int l,int r,int siz)
{
if(l==r) return c[l];
int mid=l+r>>1;
if(tr[tr[v].ls].v-tr[tr[u].ls].v>=siz) return kth(tr[u].ls,tr[v].ls,l,mid,siz);
return kth(tr[u].rs,tr[v].rs,mid+1,r,siz-(tr[tr[v].ls].v-tr[tr[u].ls].v));
}
ll query(int u,int v,int l,int r,int L,int R)
{
if(!u && !v) return 0;
if(l>=L && r<=R) return tr[v].tot-tr[u].tot;
int mid=l+r>>1;
ll ans=0;
if(L<=mid) ans+=query(tr[u].ls,tr[v].ls,l,mid,L,R);
if(mid<R) ans+=query(tr[u].rs,tr[v].rs,mid+1,r,L,R);
return ans;
}
ll ask(ll L,ll R)
{
L=max(1ll,L); R=min(1000000000ll,R);
if(L>R) return 0;
L=lower_bound(c+1,c+cnt+1,L)-c;
R=upper_bound(c+1,c+cnt+1,R)-c-1;
return query(rt[ql-1],rt[qr],1,cnt,L,R);
}
bool check(int mid)
{
ll val=kth(rt[ql-1],rt[qr],1,cnt,mid),lst=-1;
ll init=val;
while(val<sum[qr]-sum[ql-1])
{
ll tmp=val;
val+=ask(lst-k+1,val-k)-(lst-k+1<=init && init<=val-k)*init;
lst=tmp;
if(tmp==val) return false;
}
return true;
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
c[++cnt]=a[i];
sum[i]=sum[i-1]+a[i];
}
sort(c+1,c+cnt+1);
cnt=unique(c+1,c+cnt+1)-c-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+cnt+1,a[i])-c,insert(rt[i],rt[i-1],1,cnt,a[i]);
for(int i=1;i<=q;i++)
{
scanf("%d%d%lld",&ql,&qr,&k);
int l=1,r=qr-ql+2,ans=qr-ql+2;
while(l<r)
{
int mid=l+r>>1;
if(check(mid)) ans=mid,r=mid;
else l=mid+1;
}
printf("%d\n",qr-ql+2-ans);
}
return 0;
}
来自jiangly的更优秀的解法：
C
分析
O ( n k R 2 ) O(nkR^2) O(nkR2)的暴力dp还是很容易得到30pts的
30pts代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> PIL;
const int maxn=1005;
vector <int> G[maxn];
int n,k;
ll L,R,val[maxn];
int f[1005][51][205],siz[1005],tmp[51][205];
void dfs(int u,int fa)
{
siz[u]=1; f[u][0][val[u]]=1;
for(auto v:G[u])
{
if(v==fa) continue;
dfs(v,u);
for(int i=0;i<=min(k,siz[u]);i++)
for(int j=0;j<=R;j++)
{
tmp[i][j]=f[u][i][j];
f[u][i][j]=0;
}
for(int i=0;i<=min(k,siz[u]);i++)
for(int j=0;j<=R;j++) if(tmp[i][j])
{
//不删
for(int I=0;I<=min(k-i,siz[v]);I++)
for(int J=0;J<=R-j;J++) if(f[v][I][J]) f[u][I+i][J+j]=1;
//删除
for(int I=0;I<=min(k-i-1,siz[v]);I++)
for(int J=L;J<=R;J++) if(f[v][I][J]) f[u][I+i+1][j]=1;
}
siz[u]+=siz[v];
}
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int T; scanf("%d",&T);
while(T--)
{
scanf("%d%d%lld%lld",&n,&k,&L,&R);
for(int i=1;i<=n;i++) G[i].clear(),scanf("%lld",&val[i]);
int x,y;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1;i<=n;i++)
for(int j=0;j<=k;j++)
for(int t=0;t<=R;t++)
f[i][j][t]=0;
dfs(1,0);
for(int i=0;i<=k;i++)
{
int flag=0;
for(int j=L;j<=R;j++) if(f[1][i][j]) flag=1;
printf("%1d",flag);
}
printf("\n");
}
return 0;
}
发现第三部分分的r-l较小，发现我们dp 的第三维只需要记录l-r之间的，所以可以用vector去维护可行的第三维的值，这样每个点就只有 k ? ( r ? l ) k*(r-l) k?(r?l)个状态要记录，总时间复杂度 O ( n k 2 ( r ? l ) 2 ) O(nk^2(r-l)^2) O(nk2(r?l)2)
50pts代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> PIL;
const int maxn=1005;
vector <int> G[maxn];
int n,k;
ll L,R,val[maxn];
int siz[maxn];
vector <ll> f[maxn][51],tmp[51];
ll gs[maxn];
void dfs(int u,int fa)
{
siz[u]=1;
for(int i=0;i<=k;i++)
f[u][i].clear();
f[u][0].push_back(val[u]);
for(auto v:G[u])
{
if(v==fa) continue;
dfs(v,u);
for(int i=0;i<=k;i++) tmp[i].clear();
for(int i=0;i<=min(k,siz[u]);i++)
for(int j=0;j<=min(k-i,siz[v]);j++)
for(ll I:f[u][i]) for(ll J:f[v][j])
{
if(I+J<=R) tmp[i+j].push_back(I+J);
if(J>=L && J<=R && i<k) tmp[i+j+1].push_back(I);
}
siz[u]+=siz[v];
for(int i=0;i<=min(k,siz[u]);i++)
{
sort(tmp[i].begin(),tmp[i].end());
int cnt=0;
for(ll t:tmp[i]) gs[++cnt]=t;
cnt=unique(gs+1,gs+cnt+1)-gs-1;
f[u][i].clear();
for(int j=1;j<=cnt;j++) f[u][i].push_back(gs[j]);
}
}
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int T; scanf("%d",&T);
while(T--)
{
scanf("%d%d%lld%lld",&n,&k,&L,&R);
for(int i=1;i<=n;i++) G[i].clear(),scanf("%lld",&val[i]);
int x,y;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1,0);
for(int i=0;i<=k;i++)
{
int flag=0;
for(ll t:f[1][i]) if(t>=L && t<=R) flag=1;
printf("%1d",flag);
}
printf("\n");
}
return 0;
}
继续分析发现
100pts代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> PIL;
const int maxn=1005;
vector <int> G[maxn];
int n,k;
ll L,R,val[maxn];
int siz[maxn];
vector <ll> f[maxn][51],tmp[51],g;
void dfs(int u,int fa)
{
for(int i=0;i<=k;i++)
f[u][i].clear();
f[u][0].push_back(val[u]);
for(auto v:G[u])
{
if(v==fa) continue;
dfs(v,u);
for(int i=k;i>=0;i--)
{
g.clear();
for(int j=0;j<=i;j++)
for(ll I:f[u][i-j]) for(ll J:f[v][j])
if(I+J<=R) g.push_back(I+J);
sort(g.begin(),g.end());
f[u][i].clear();
for(ll v:g)
{
while(f[u][i].size()>1 && v-f[u][i][f[u][i].size()-2]<=R-L)
f[u][i].pop_back();
f[u][i].push_back(v);
}
}
}
for(int i=1;i<=k;i++)
for(ll v:f[u][i-1])
if(v>=L && v<=R)
{
f[u][i].push_back(0);
break;
}
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int T; scanf("%d",&T);
while(T--)
{
scanf("%d%d%lld%lld",&n,&k,&L,&R);
for(int i=1;i<=n;i++) G[i].clear(),scanf("%lld",&val[i]);
int x,y;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1,0);
for(int i=0;i<=k;i++)
{
int flag=0;
for(ll t:f[1][i]) if(t>=L && t<=R) flag=1;
printf("%1d",flag);
}
printf("\n");
}
return 0;
}
