2025牛客多校第十场K题解：神奇集合、逛商场、好感度、矩阵如何解答？
摘要：I.矩阵 数学 #贪心 #构造 题目 思路 首先考虑有数最受条件的约束，因此尝试令数(x)沿着某方向前进(x)后回到原地： [begin{align} (x+x+1)%n-1&
I.矩阵
数学 #贪心 #构造
题目
思路
首先考虑有数最受条件的约束，因此尝试令数\(x\)沿着某方向前进\(x\)后回到原地：
\[\begin{align}
(x+x+1)\%n-1&=x\\ \\
(2x+1)\%n&=x+1\\ \\
2x+1&\equiv x+1\mod n\\ \\
x&\equiv 0\mod n
\end{align}
\]
则有\(x\)为\(n\)的因数
因此，当\(x\)为\(n\)的因数时，\(x\)无法在\(n\)方向上进行移动，\(m\)方向同理
因此，\(x=lcm(n,m)\)时，\(x\)一定无法移动
因此\(lcm(n,m)\)必须为最后一个填入的数字，可以利用这一点进行\(YES/NO\)的判断
接下来通过观察贪心地进行填空：
尝试将一列填满后再填下一列
尝试每填完一个数就变换一次移动方向，比如这次在列方向上向下移动，下一次列方向上的移动就向上，这样可以保证移动后不会踩到已经被填过的格子
代码实现
代码由\(phaethon 90\)书写
#include<iostream>
#include<vector>
using namespace std;
#define ll long long
#define endl '\n'
ll gcd(ll a,ll b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
void eachT()
{
ll n,m;
cin>>n>>m;
if(n/gcd(n,m)*m<n*m)
{
cout<<"NO\n";
return;
}
vector<vector<int>>mp(n+1,vector<int>(m+1,0));
int i=0,j=0,cnt=0;
int dirn=1,dirm=1;
mp[0][0] = ++cnt;
while(cnt<n*m)
{
if(cnt%n==0)
{
j = (j+cnt%m*dirm+m*m)%m;
mp[i][j] = ++cnt;
dirm *= -1;
}
else
{
i = (i+cnt%n*dirn+n*n)%n;
mp[i][j] = ++cnt;
dirn *= -1;
}
}
cout<<"YES\n";
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<mp[i][j]<<' ';
}
cout<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t=1;
// cin>>t;
while(t--) eachT();
return 0;
}
E. 老师与好感度
dp #线性dp
题目
思路
由于\(0\leq a_{i}\leq 100\)，很容易想到要枚举最后出现的\(m\)个数，考虑\(m=2\)的情况，即枚举两个目标\(tar_{1},tar_{2}\)（\(target\)）
状态表示：
\(dp[i][j]\)表示从\(1\)遍历到\(i\)，第\(i\)个学生的好感度变为\(tar_{j}\)（\(1\leq j\leq 2\)）的最小总天数
状态转移：
\[\begin{align}
&dp[i][j]=\min_{0\leq k\leq[m=2]}\{dp[i][j]\ , \ dp[i-1][k]+ \max\{ tar_{j}-a_{i}-(tar_{k}-a_{i-1})\ ,\ 0 \} \},0\leq j\leq[m=2]\\ \\
&if(tar_{j}-a_{i}<0)dp[i][j]=inf
\end{align}