d2 - Domino (hard version)
定义多米诺骨牌是一个 \(1\times 2\) 的小矩形 . 给定 \(n,m,k\)，求是否可以将一个 \(n\times m\) 的方格（ \(n\) 行 \(m\) 列）用多米诺密铺（不重不漏地铺满），其中横向的多米诺有 \(k\) 个。若可以，则给出任意一种构造方案。
输出方案时，输出一个由小写字母组成的 \(n\times m\) 的字母矩阵，两个相邻的单元格拥有相同的字母表明这两个单元格由一个多米诺覆盖，否则不算。
\(1\leq t\leq 10\)
\(1\leq n,m\leq 100,\ 0\leq k\leq \frac{nm}{2},\ n\cdot m\) 是偶数
暑假比赛时想了很久都没有想出来，现在来看，为什么有点一眼 ...
可以将矩形分类解决，题目中要求要不重不漏地铺满 .
-
\(n\) 是奇数，\(m\) 是偶数 .
那么，第一行都必须要铺横向的 . 要铺 \(\frac{m}{2}\) 个 . 所以，如果 \(k<\frac{m}{2}\) 的可以判断无解了 . 接下来，因为纵向的要占据偶数行，所以，横向的必须两两铺，才能保证最后纵向的能不重不漏地铺满 . 如果 \(k-\frac{m}{2}\) 不是偶数的也可以判断无解了 . 剩下的暴力模拟，先放第一行，再把横向的放完，剩下放纵向的 .
-
\(n\) 是偶数，\(m\) 是奇数 .
第一列必须用纵向的铺 . 所以，如果 \(k<\frac{n(m-1)}{2}\) 或者 \(k\) 是奇数的是无解的 ，否则有解 . 接着，先放第一列的纵向，再两个两个放横向的 . 剩下放纵向的 .
-
\(n\) 是偶数，\(m\) 是奇数 .
\(k\) 是奇数的是无解的，否则有解 . 先两个两个放横向的，剩下的放纵向的 .
最后用字母表示也不是很难 . 要判断一下，不能用这两个格子四周的格子 .
时间复杂度 : \(\mathrm O(tnm)\)
空间复杂度 : \(O(nm)\)
code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
int res=0;
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return res;
}
inline void print(int res){
if(res==0){
putchar('0');
return;
}
int a[10],len=0;
while(res>0){
a[len++]=res%10;
res/=10;
}
for(int i=len-1;i>=0;i--)
putchar(a[i]+'0');
}
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
int t;
int n,m,k;
int cnt=0;
int a[110][110];
char ans[110][110];
bool used[30];
void check(int x,int y){
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx<0||nx>n||ny<0||ny>m)continue;
if(ans[nx][ny]!=-1)used[ans[nx][ny]-'a']=true;
}
}
void output(){
memset(ans,-1,sizeof(ans));
for(int i=0;i<n;i++)for(int j=0;j<m;j++){
if(ans[i][j]!=-1)continue;
if(j+1<m&&a[i][j]==a[i][j+1]){
memset(used,0,sizeof(used));
check(i,j);
check(i,j+1);
char c;
for(int l=0;l<26;l++){
if(!used[l]){
c=l;
break;
}
}
ans[i][j]=ans[i][j+1]='a'+c;
}
if(i+1<n&&a[i][j]==a[i+1][j]){
memset(used,0,sizeof(used));
check(i,j);
check(i+1,j);
char c;
for(int l=0;l<26;l++){
if(!used[l]){
c=l;
break;
}
}
ans[i][j]=ans[i+1][j]='a'+c;
}
}
puts("YES");
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)putchar(ans[i][j]);
putchar('\n');
}
}
void solve1(){
if(k<m/2||(k-m/2)%2!=0){
puts("NO");
return;
}
for(int i=0;i<m/2;i++){
a[0][i<<1]=a[0][i<<1|1]=cnt++;
}
k-=m/2;
for(int i=0;i<m/2;i++){
for(int j=1;j<n;j++){
if(k==0)break;
a[j][i<<1]=a[j][i<<1|1]=cnt++;
// cout<<j<<","<<(i<<1)<<" "<<j<<","<<(i<<1|1)<<endl;
k--;
}
}
for(int i=1;i<n;i+=2)for(int j=0;j<m;j++){
if(a[i][j]==-1&&a[i+1][j]==-1){
a[i][j]=a[i+1][j]=cnt++;
}
}
output();
}
void solve2(){
if(k>n*(m-1)/2||k%2!=0){
puts("NO");
return;
}
for(int i=0;i<n/2;i++){
a[i<<1][0]=a[i<<1|1][0]=cnt++;
}
for(int i=1;i<m;i+=2){
for(int j=0;j<n;j++){
if(k==0)break;
k--;
a[j][i]=a[j][i+1]=cnt++;
}
}
for(int i=0;i<n;i+=2){
for(int j=0;j<m;j++){
if(a[i][j]==-1&&a[i+1][j]==-1){
a[i][j]=a[i+1][j]=cnt++;
}
}
}
output();
}
void solve3(){
if(k%2!=0){
puts("NO");
return;
}
for(int i=0;i<m;i+=2){
for(int j=0;j<n;j++){
if(k==0)break;
k--;
a[j][i]=a[j][i+1]=cnt++;
}
}
for(int i=0;i<n;i+=2){
for(int j=0;j<m;j++){
if(a[i][j]==-1&&a[i+1][j]==-1){
a[i][j]=a[i+1][j]=cnt++;
}
}
}
output();
}
void solve(){
n=read();m=read();k=read();
cnt=0;
memset(a,-1,sizeof(a));
if(n&1)solve1();
else if(m&1)solve2();
else solve3();
}
int main(){
t=read();
while(t--){
solve();
}
return 0;
}
/*inline? ll or int? size? min max?*/
e - Fixed Points
一个整数序列 \(a1,a2,...,a_n\) ，一次操作，可以删除一个数，然后该数右侧的数向左移动一个单位。对于一个长度为 \(n\) 的整数序列 \(b_i\) ，求最少需要删除几个数后，会有至少 \(k\) 个 \(i\) 满足 \(b_i=i\) 。
\(1\leq t\leq 100\)
\(1\leq k\leq n\leq 2000,\ 1\leq a_i\leq n,\ \sum n\leq 2000\)
看到 \(2\cdot 10^3\) 的范围，就想到应该是 \(\mathrm O(n^2)\) 的做法 .
考虑这样一个 \(dp\) ，
\(f(i,j)\) 代表到了第 \(i\) 个数，一共删除了 \(j\) 个数最多有多少个 \(i\) 满足 \(b_i=i\) .
转移方程为 :
-
删掉当前这个数
\(f(i,j)\rightarrow f(i+1,j+1)\)
-
保留当前这个数
-
如果 \(a_{i+1}=i+1-j\) ，\(f(i,j)+1\rightarrow f(i+1,j)\)
即 \(a_{i+1}\) 对应着 \(b_{i+1-j}\) .
-
否则， \(f(i,j)\rightarrow f(i+1,j)\)
-
最后从小到大枚举 \(f(n-1,i)\) ，找到第一个 \(f(n-1,i)\geq k\) 的 \(i\) 即为答案 .
时间复杂度 : \(\mathrm O(n^2)\)
空间复杂度 : \(\mathrm O(n^2)\)
code
#include<bits/stdc++.h>
using namespace std;
int t;
int n,k;
int a[2010];
int dp[2010][2010];
inline void upd(int &x,int y){
x=max(x,y);
}
void solve(){
cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)a[i]--;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
dp[i][j]=0;
}
}
dp[0][0]=(a[0]==0);
dp[0][1]=0;
for(int i=0;i+1<n;i++){
for(int j=0;j<=i+1;j++){
upd(dp[i+1][j],dp[i][j]+(a[i+1]==i+1-j));
upd(dp[i+1][j+1],dp[i][j]);
}
}
int ans=-1;
for(int i=0;i<=n;i++){
if(dp[n-1][i]>=k){
ans=i;
break;
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
solve();
}
return 0;
}
/*inline? ll or int? size? min max?*/
f - Equidistant Vertices
给定一棵有 \(n\) 个点的树，要求选出 \(k\) 个点，使得这 \(k\) 个点两两距离相同。答案模 \(10^9+7\) 。
\(1\leq t\leq 10\)
\(2\leq k\leq n\leq 100\)
设选出的 \(k\) 个点为黑点，其他的为白点 .
考虑这 \(k\) 个距离两两相同的点的排布，在树的一条链上，必定至多有两个点为黑点 .
所以，枚举根节点 \(r\) ，设剩下的 \(k\) 个点到这个点距离相同 . 所有的情况都可以归结到这个样子 .
观察可得，这 \(k\) 个节点必定存在与不同的子树中 . 否则，在同一个子树的节点之间的距离会比到其他节点的距离要小 .
接着枚举 \(k\) 个点到 \(r\) 的距离 \(d\) ，通过 \(dfs\) 求出每个子树距离 \(r\) 距离为 \(d\) 的节点个数 .
因为每个节点最多选 \(1\) 个，所以可以用一个背包求出 .
用 \(f(i,j)\) 表示到了第 \(i\) 个子树，选了 \(j\) 个黑点的方案数 .
用 \(cnt(i)\) 表示第 \(i\) 个子树中距离 \(r\) 距离为 \(d\) 的节点个数 .
\(f(i,j)=f(i-1,j-1)\times cnt(i)+f(i-1,j)\)
枚举根 \(\mathrm O(n)\)，枚举距离 \(\mathrm O(n)\) ，\(dfs\) \(\mathrm O(n)\) 之后背包 \(\mathrm O(n^2)\) .
时间复杂度 : \(\mathrm O(n^4)\)
空间复杂度 : \(\mathrm O(n^2)\)
其实只跑了 31ms ，因为仔细想想，没有什么数据能使这个跑满，一般都远远跑不满 .
code
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int t;
int n,k;
vector<int>g[110];
int dep[110],dp[110][110];
inline void upd(int &x,int y){
x=(x+y)%mod;
}
void dfs(int x,int fa,int d,int &cnt){
if(dep[x]==d)cnt++;
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i];
if(to==fa)continue;
dep[to]=dep[x]+1;
dfs(to,x,d,cnt);
}
}
void solve(){
cin>>n>>k;
for(int i=0;i<n;i++)g[i].clear();
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
u--;v--;
g[u].push_back(v);
g[v].push_back(u);
}
if(k==2){
cout<<1ll*n*(n-1)/2%mod<<endl;
return;
}
int ans=0;
for(int r=0;r<n;r++)for(int d=1;d<=n;d++){
if((int)g[r].size()<k)continue;
dp[0][0]=1;
for(int i=0;i<(int)g[r].size();i++){
int cnt=0;
dep[g[r][i]]=1;
dfs(g[r][i],r,d,cnt);
for(int j=0;j<=i+1;j++)dp[i+1][j]=0;
for(int j=0;j<=i;j++){
if(cnt>0)upd(dp[i+1][j+1],1ll*dp[i][j]*cnt%mod);
upd(dp[i+1][j],dp[i][j]);
}
}
cout<<endl;
upd(ans,dp[(int)g[r].size()][k]);
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
solve();
}
return 0;
}
/*inline? ll or int? size? min max?*/