祝大家新年快乐！

虽然是娱乐赛，但这场是5个正经算（gou）法（zao）题，也算是回归了除夕场的初心（2023年第一场除夕赛就是纯算法场）。希望大家玩的开心。

A. 窗花

知识点：构造、模拟
难度：1000

思路： 题目要求寻找一条从 到 的连通路径，且满足以下三个条件：

1. 路径连通：必须是四连通路径。
2. 线条不过粗：任意行或列不能有 3 个或更多连续的 1。这意味着我们在任意一行或一列中，最多只能占据 2 个格子。换句话说，在路径移动过程中，我们不能连续向右走两步（RR），也不能连续向下走两步（DD）。因此，路径必须是 “右、下”交替 进行的（例如 RDRD... 或 DRDR...）。
3. 不过于密集：不能出现 的全 1 区域。由于我们只能交替移动（一步右、一步下），这种单调路径天然不会形成 的方块（拐弯处只有 3 个格子是 1），此条件自动满足。

基于“必须交替移动”的结论：

• 每向右移动一次，列号 ；每向下移动一次，行号 。
• 为了到达 ，我们需要向右移动 次，向下移动 次。
• 由于是交替进行，向右移动的次数与向下移动的次数之差不能超过 1。
• 即 。

结论：

• 如果 ，无法构造，输出 -1。
• 如果 ，可以构造。
  • 若 ，可以 RDRD... 或 DRDR...。
  • 若 （行更多），必须以 D 开头，以 D 结尾（多一次下移），即 DRDR...D。
  • 若 （列更多），必须以 R 开头，以 R 结尾（多一次右移），即 RDRD...R。

直接模拟上述路径并在网格中标记即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int g[1005][1005];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,i,j,x=1,y=1,f;
    cin>>n>>m;
    if(abs(n-m)>1){cout<<-1<<"\n";return 0;}
    g[1][1]=1;f=(m>n);
    while(x<n||y<m){
        if(f)y++;else x++;
        g[x][y]=1;f^=1;
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)cout<<g[i][j];
        cout<<"\n";
    }
}

B. 拜年

知识点：构造、数论（哥德巴赫猜想）
难度：1400

思路1：数论构造（哥德巴赫猜想） 题目要求构造一个 到 的排列，使得相邻元素的差值的绝对值是质数。

1. 特判小数据：

   • ：输出 1。
   • ：无解。
   • ：2 4 1 3。
   • ：1 4 6 3 5 2（ 是偶数中的特殊情况）。

2. 偶数 ：

   • 根据哥德巴赫猜想，存在两个质数 使得 。
   • 对于 ，我们可以找到 的解（即 ）。
   • 构造方法：从 1 开始，每次加 （模 ）。由于 ，这会遍历所有数。
   • 相邻差值：要么是 ，要么是 ，均为质数。

3. 奇数 ：

   • 为奇数，则 为偶数。找到 。
   • 构造方法（分三段）：
     1. 偶数递增：（公差 2，质数）。
     2. 奇数递减：（公差 2，质数）。连接处差值为 。
     3. 偶数递增：（公差 2，质数）。连接处差值为 。

代码1：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int p[200005],v[200005],cnt;
void sieve(){
    for(int i=2;i<200005;i++){
        if(!v[i])p[cnt++]=i;
        for(int j=0;j<cnt&&i*p[j]<200005;j++){
            v[i*p[j]]=1;if(i%p[j]==0)break;
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    sieve();
    int n,i,j;
    while(cin>>n){
        if(n==1){cout<<"1\n";continue;}
        if(n==2||n==3){cout<<"-1\n";continue;}
        if(n==4){cout<<"2 4 1 3\n";continue;}
        if(n==6){cout<<"1 4 6 3 5 2\n";continue;}
        if(n%2==0){
            int P=-1;
            for(i=0;i<cnt;i++){
                if(p[i]>=n/2)break;
                if(!v[n-p[i]]){P=p[i];break;}
            }
            if(P==-1){cout<<"-1\n";continue;}
            int x=1;
            for(i=0;i<n;i++){
                cout<<x<<(i==n-1?"\n":" ");
                x=(x+P-1)%n+1;
            }
        }else{
            int P=-1,Q=-1;
            for(i=0;i<cnt;i++){
                if(p[i]>n)break;
                if(!v[n+1-p[i]]){P=p[i];Q=n+1-p[i];break;}
            }
            if(P==-1){cout<<"-1\n";continue;}
            vector<int> a;
            for(i=2;i<=n-P;i+=2)a.push_back(i);
            for(i=n;i>=1;i-=2)a.push_back(i);
            for(i=1+Q;i<=n-1;i+=2)a.push_back(i);
            for(i=0;i<n;i++)cout<<a[i]<<(i==n-1?"\n":" ");
        }
    }
}

思路2：通用模式构造 对于 的情况，我们可以使用一种通用的“蛇形”构造模式，主要利用公差为 2（质数）的递增和递减序列，并通过末尾的一个固定 5 元素小序列来完成奇偶转换和回环。

核心模式：

1. 第一段：从 （若 为偶数）或 （若 为奇数）开始，以 为步长递增，直到 。
   • 例如 ：。
   • 例如 ：。
   • 这一段通过公差 2 保证相邻差值为质数。
2. 转折段：固定输出 。
   • 连接处：，差值为 5（质数）。
   • 内部差值：，，，。均为质数。
3. 第三段：从 开始，以 为步长递减，直到 。
   • 连接处：，差值为 3（质数）。
   • 内部公差 2。

代码2：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,i;
    while(cin>>n){
        if(n==1)cout<<"1\n";
        else if(n<=3)cout<<"-1\n";
        else if(n==4)cout<<"2 4 1 3\n";
        else if(n==5)cout<<"2 5 3 1 4\n";
        else if(n==6)cout<<"1 3 5 2 4 6\n";
        else{
            for(i=1+(n&1);i<=n-5;i+=2)cout<<i<<" ";
            cout<<n<<" "<<n-2<<" "<<n-4<<" "<<n-1<<" "<<n-3<<" ";
            for(i=n-6;i>=1;i-=2)cout<<i<<(i<=2?"\n":" ");
        }
    }
}

C. 年夜饭

知识点：贪心、数论（GCD）、构造
难度：1200

思路： 题目要求构造一个 的矩阵 ，使得第 行的乘积为 ，第 列的乘积为 。已知 。

这个问题可以转化为对每个质因子分别进行分配。 对于任意一个质数 ，设 中包含 的指数为 ， 中包含 的指数为 。我们需要确定矩阵中每个元素 包含 的指数 ，满足：

且 。

这是一个经典的矩阵填充问题，可以通过贪心策略解决（类似于最大流中的西北角法则或者直接贪心）： 对于当前格子 ，我们尽可能多地放入质因子 ，即令 。 然后更新剩余需求：, 。

将上述针对指数的逻辑推广到数值上，即为： 对于当前格子 ，取 和 的最大公约数，即 。 然后将 分别除以 ，表示这些因子已经被该格子消耗。 由于 ，遍历完整个矩阵后，所有的 都会变为 1，且矩阵满足要求。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[1005],b[1005],c[1005][1005];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,i,j,g;
    while(cin>>n>>m){
        for(i=1;i<=n;i++)cin>>a[i];
        for(j=1;j<=m;j++)cin>>b[j];
        for(i=1;i<=n;i++)for(j=1;j<=m;j++){
            g=gcd(a[i],b[j]);
            c[i][j]=g;a[i]/=g;b[j]/=g;
        }
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++)cout<<c[i][j]<<(j==m?"\n":" ");
        }
    }
}

D. 压岁钱

知识点：动态规划（分组背包）、路径还原
难度：1400

思路： 本题是一个典型的分组背包问题。

• 物品：每个群 可以看作一组物品，或者说对每个群有 种选择（拿 0 个，拿 1 个，...，拿 个）。
• 代价：
  • 拿 个：代价 0。
  • 拿 个：代价 。
• 价值：
  • 拿 个：价值 。
• 限制：总代价不超过 。

我们定义 表示消耗时间恰好为 时能获得的最大金额。 对于每个群 ，我们倒序枚举时间 （从 到 ），然后枚举在该群中选择领取的红包数量 （从 到 ），进行状态转移： 其中 ，。

为了输出具体方案，我们需要记录路径。定义 path[i][j] 表示在考虑前 个群且时间为 时，最优决策选择了多少个红包。 在 DP 转移时，如果更新了 ，则同步更新 path[i][j] = k。如果保持原值（即不选该群，或者选了也不优），则 path[i][j] 默认为 0（注意：由于我们用了 1D 数组优化 DP，path 记录的必须是当前层决策）。

最后，找到 中的最大值及其对应的时间 ，倒序回溯 path 数组即可还原每个群的选择。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,x,y,t,a[105],b[105],dp[2005],p[105][2005];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int i,j,k,mx,bk,w,v;
    cin>>n>>x>>y>>t;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=n;i++)cin>>b[i];
    memset(dp,-1,sizeof(dp));dp[0]=0;
    for(i=1;i<=n;i++)for(j=t;j>=0;j--){
        mx=dp[j];bk=0;
        for(k=1;k<=a[i];k++){
            w=x+k*y;
            if(j>=w&&dp[j-w]!=-1){
                v=dp[j-w]+k*b[i];
                if(v>mx)mx=v,bk=k;
            }
        }
        dp[j]=mx;p[i][j]=bk;
    }
    int ans=-1,ti=0;
    for(j=0;j<=t;j++)if(dp[j]>ans)ans=dp[j],ti=j;
    vector<int> res;
    for(i=n;i>=1;i--){
        k=p[i][ti];res.push_back(k);
        if(k)ti-=(x+k*y);
    }
    reverse(res.begin(),res.end());
    for(i=0;i<n;i++)cout<<res[i]<<(i==n-1?"\n":" ");
}

E. 烟花

知识点：位运算、差分数组、ST表（或线段树）
难度：1700

思路： 题目要求还原数组 ，满足 条区间按位或（Bitwise OR）的约束。 由于位运算中每一位是独立的，我们可以对 0 到 29 每一位分别处理。

1. 构造（贪心策略）：

   • 初始化所有 的所有位为 1。
   • 对于第 位：
     • 如果某个约束 中 的第 位是 0，那么区间 内所有数的第 位 必须 为 0。
     • 利用差分数组标记这些“必须为 0”的区间。
     • 遍历数组，如果位置 被标记为“必须为 0”，则将 的第 位设为 0；否则保持为 1（贪心：尽量设为 1 以满足可能的“至少有一个 1”的约束）。

2. 验证：

   • 上述构造保证了如果 的某位是 0，结果中对应的位一定是 0。
   • 但它不能保证如果 的某位是 1，结果中区间内至少有一个 1（可能因为和其他约束冲突，被迫全设为 0 了）。
   • 因此，我们需要验证构造出的数组是否满足所有约束。
   • 构建 ST 表（Sparse Table）以支持 的区间 OR 查询。
   • 遍历所有约束，检查 query(l, r) == v 是否成立。如果有任意一个不成立，输出 -1。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,l[200005],r[200005],v[200005];
int a[200005],d[200005],f[200005][20];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int i,j,k,x;
    if(!(cin>>n>>m))return 0;
    for(i=1;i<=m;i++)cin>>l[i]>>r[i]>>v[i];
    for(k=0;k<30;k++){
        for(i=0;i<=n+1;i++)d[i]=0;
        for(i=1;i<=m;i++)if(!((v[i]>>k)&1))d[l[i]]++,d[r[i]+1]--;
        x=0;
        for(i=1;i<=n;i++){
            x+=d[i];
            if(!x)a[i]|=(1<<k);
        }
    }
    for(i=1;i<=n;i++)f[i][0]=a[i];
    for(j=1;j<20;j++)for(i=1;i+(1<<j)-1<=n;i++)
        f[i][j]=f[i][j-1]|f[i+(1<<(j-1))][j-1];
    for(i=1;i<=m;i++){
        k=__lg(r[i]-l[i]+1);
        if((f[l[i]][k]|f[r[i]-(1<<k)+1][k])!=v[i]){cout<<-1<<"\n";return 0;}
    }
    for(i=1;i<=n;i++)cout<<a[i]<<(i==n?"\n":" ");
}