A
这题是很有意思的一个题，思路就是你考虑kt的位置只可能在四个角，因为这种情况下，他的距离才会最远对吧，所以你就暴力找另一个人fengwu的点的位置，然后计算他们之间的距离然后你求一个\(\max\)即可，然后记录一下这些\(\max\)的值，最后排个序就好了。
代码：
# include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5010;
int a[N*N];
int dis(int a,int b,int c,int d)
{
return abs(a-b)+abs(c-d);
}
signed main (){
int n,m;
scanf("%lld%lld",&n,&m);
int tot = 0;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
// int x = (i-1)*(j-1);
// cout << x << endl;
int mx = max(dis(1,i,1,j),max(dis(1,i,m,j),max(dis(n,i,1,j),dis(n,i,m,j))));
a[++tot] = mx;
}
}
sort(a+1,a+tot+1);
for(int i = 1;i <= tot;i++)
{
printf("%lld ",a[i]);
}
return 0;
}
有可能会问，你如何考虑\(k\)这个东西呢，你考虑，我排序的过程就是对\(k\)个进行筛选，筛选过后的结果不会对最大值的最小值产生影响，所以不需要考虑k。
B
好题，这是一个很好很好的题。
\(10pts\):
显然，对于\(10pts\)，这可以直接爆搜全排列，然后暴力计数值。，代码：
# include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5010;
const int mod = 998244353;
int s[N],p[N],vis[N];
int jc[N];
int n;
int f(int n,int p[],int s[])
{
int ret=p[1];
for(int i=2;i<=n;i++)
{
if(s[i-1]==1)ret=max(ret,p[i]);
else ret=min(ret,p[i]);
}
return ret;
}
int ans = 0;
void dfs(int dep)
{
if(dep == n+1)
{
for(int i = 1;i <= n;i++)
{
// cout << p[i] << " ";
}
// if(p[n] == 3) tot++;
// cout << endl;
ans += f(n,p,s);
ans %= mod;
return ;
}
for(int i = 1;i <= n;i++)
{
if(!vis[i])
{
vis[i] = 1;
p[dep] = i;
dfs(dep+1);
vis[i] = 0;
}
}
}
int qpow(int a,int b)
{
int ans = 1;
while(b != 0)
{
if(b & 1)
{
ans = ans*a%mod;
}
a = a*a%mod;
b >>= 1;
}
return ans%mod;
}
int ny(int n)
{
return qpow(n,mod-2);
}
signed main (){
scanf("%lld",&n);
for(int i = 1;i <= n-1;i++)
{
scanf("%lld",&s[i]);
}
jc[0] = 1;
for(int i = 1;i <= n;i++)
{
jc[i] = jc[i-1]*i%mod;
}
int flag = 0;
for(int i = 2;i <= n-1;i++)
{
if(s[i] < s[i-1])
{
flag = 1;
break;
}
}
int cnt = 0;
if(flag == 0)
{
for(int i = 1;i <= n-1;i++)
{
if(s[i] == 1) cnt++;
}
}
if(n <= 10)
{
dfs(1);
// cout << tot << endl;
printf("%lld\n",ans%mod);
}
else
{
if(flag == 0)
{
int res = 0;
if(cnt == 1)
{
res = jc[n-1]*(ny(2)*((n*(n+1)%mod+2)%mod)%mod)%mod;
}
printf("%lld\n",res);
}
}
return 0;
}
\(100pts:\)
你考虑转化问题，你考虑算出他的答案，然后呢你去计算这个数列会产生这个答案的排列方式是多少，最后他对答案产生的贡献就是排列方式\(\times\)答案。
那么你考虑如何计算这个这个排列方式，我们对于每个数都去动态计算这个数列离散化过后的值，什么意思呢，看下面这一组例子：
\[5\; \;\;1 \:\;\;4 \:\;\;2 \:\;\;3 \]一开始放入一个\(5\)，离散化之后的数列是这样的：
\[1 \]接下来放入\(1\)，离散化之后是
\[2 \; \;\;\;1 \]接下来放入\(4\)，\(4\)比\(1\)大，比\(5\)小，所以他是第二小的，离散化后是：
\[3 \; \; \; 1 \; \; \; 2 \]........
最后的结果就是：
\[5 \;\;\; 1 \;\;\; 4 \;\;\; 2 \;\;\; 3 \]你考虑这个跟之前没变的是一样的。
那么我们考虑逐位计算,用\(dp\)去转移。
设定\(dp_{i,j}\)表示表示前\(i\)位，插入这个数字过后得到的答案，显然得到以下转移方程：