11.11 NOIP模拟赛题解

不是，今天光棍节，大帝还要打压我，可恶。

该说不说，出的题是真的难，基本上都是数学，还有炒鸡无敌大讨论，感觉智商退化了，虽然本来就没啥智商

来看看比赛题目吧

T1 CF1530E Minimax

原题链接

题目顺序不固定，我把这道题做出来了，就先写这道题。

这道题就是那个炒鸡无敌大讨论，首先把题目全都浏览一遍，发现这道题思路还比较清晰，就先整这道题，结果愣是搞了4h，结果不错，幸亏是对了。

转化题意：

由于字符可以重新排序，所以我们将它抽象成给我们一些字符，我们需要构造一个字符串，使得这个字符串的每一个前缀子串的公共前后缀最小。输出字典序最小的。

首先我们要知道前缀、后缀、真前缀、真后缀的概念：

简单来说，如果给我一个字符串$abbcde$那么它的前缀(不考虑空串)就是：$a、ab、abb、abbc、abbcd、abbcde。$真前缀就是：$a、ab、abb、abbc、abbcd。$

现在知道最基本的一层了，我们来深入思考一下：

应该根据什么分情况

一共有多少种情况

我们首先可以发现，给出的这些字符，它可能只有一种，可能有多种， 每种可能只出现了一次，可能出现了多次，那我们就根据出现种数来分类。

一. 如果只出现了一种字符

直接把原串输出就行

二.如果出现了两种及以上种字符

这种情况可以分为两种小情况

1.如果存在某一种字符出现了一次

根据决策的最优性以及转化的题意，我们可以知道直接将出现一次的字符放在最前面，剩下的字符按照字典序顺序输出就行。

举例：给定$aaabbc$输出$caaabb$

2.如果所有的字符出现次数都大于等于2

我们设出现的最小字符是$a$，出现次数为$cnt$，那么答案肯定是$1$要保证字典序最小，肯定是把$a$放在最前面，但是我们又不难看出来，最前面最多只能放两个$a$

举例：给定$aaabbcc$输出$aababcc$

这种情况还可以分成两种小情况

I.最前面可以放两个$a$

最前面可以放两个连续的$a$，考虑除了这两个$a$以外的$a$，由于这些$a$每个后要么跟一个其他字符，要么将$a$放在最后，所以当且仅当$cnt-1\le len-cnt+1$时，前面可以放两个字符。

II. 最前面只能放一个$a$

我们考虑出现的字符种类数$\le 2$那么我们将字典序最小的放在首位第一个位置，剩下的放在后面，将剩余的字典序最小的放在最后。

举例：给出$aaaaaaabbb$输出$abbbaaaaaa$

如果字符种类较多，就将字典序最小的放在第二小的后面。

这道题就完美的结束了。完结撒花！
★,°:.☆(￣▽￣)/$:.°★ 。

☆*: .｡. o(≧▽≦)o .｡.:*☆

$code$(代码里有注释)

//ASCII标,a:97,0:48,A:65
#include<bits/stdc++.h>
using namespace std;
int t;//测试组数
int a[30];//每个字母出现了多少次
string s;//原始
int main() {
cin >> t;
while (t--) {
int cnt = 0;//出现次数
bool flag = 0;
cin >> s;
memset(a, 0, sizeof(a));//初始化数组
int len = s.size();
//目的是判断是否只有一种(特殊性质B),跟两种
for (int i = 0; i < len; i++) {
if (a[s[i] - 'a' + 1] == 0)cnt++;
a[s[i] - 'a' + 1]++;
}
//特殊性质B
if (cnt == 1) {
cout << s << endl;
continue;
}
for (int i = 1; i <= 26; i++){
//cout<<a[i]<<endl;
if (a[i] == 1) {
//特殊性质A
cout << (char)(i + 'a' - 1);
a[i]--;
for (int i = 1; i <= 26; i++)
for (int j = 1; j <= a[i]; j++)
cout << (char)(i + 'a' - 1);
cout << endl;
flag = 1;
break;
}
}
if (flag)continue;
int x = 1;
while (a[x] == 0)x++;
int y = x + 1;
while (a[y] == 0)y++;
//在前面放两个字典序最小的数的前提条件
//a[i]-1<=len-a[i]+1
if (2 * a[x] <= len + 2) {
//输出两个字典序最小的
cout << (char)(x + 'a' - 1) << (char)(x + 'a' - 1);
a[x] -= 2;
for (int i = 1; i <= a[x]; i++) {
while (a[y] == 0)y++;
//间隙输出，输出一个大的，再输出小的
cout << (char)(y + 'a' - 1);
cout << (char)(x + 'a' - 1);
a[y]--;
}
a[x] = 0;
for (int i = 1; i <= 26; i++)
for (int j = 1; j <= a[i]; j++)
cout << (char)(i + 'a' - 1);
cout << endl;
continue;
}
//不满足前面放两个的条件，把字典序最小的放一个在前面
//如果有两种字母
//所有小的放在大的的后面(除了前一个小的)
if (cnt == 2) {
for (int i = 1; i <= 26; i++)
if (a[i] > 0) {
cout << (char)(i + 'a' - 1);
a[i]--;
for (int j = i + 1; j <= 26; j++)
for (int k = 1; k <= a[j]; k++)
cout << (char)(j + 'a' - 1);
for (int k = 1; k <= a[i]; k++)
cout << (char)(i + 'a' - 1);
cout << endl;
break;
}
continue;
}
cout << (char)(x + 'a' - 1) << (char)(y + 'a' - 1);
a[x]--;
a[y]--;
for (int i = 1; i <= a[x]; i++){
cout << (char)(x + 'a' - 1);
}
a[x] = 0;
y++;
while (a[y] == 0) y++;
cout << (char)(y + 'a' - 1);
a[y]--;
for (int i = 1; i <= 26; i++){
for (int j = 1; j <= a[i]; j++){
cout << (char)(i + 'a' - 1);
}
}
//cout << endl << endl;
}
//cout << endl << endl;
return 0;
}

T2 CF 573D Bear and Cavalry

原题链接

这道题没做，刚开始是想都没想，后来讲完了，又看了题解，才搞明白 。

线段树 and dp

来想想方法：

考虑一个最简单的问题：给定两个长度相同正整数序列$a，b$，要求将$b$序列重新排序，最大化$\sum a_i\times b_i$

这个问题显然只需要将$a，b$分别排序然后一一匹配即可。因为如果 $a<b<c<d$，$ad+bc<ac+bd$。

那么再考虑本题不带修改的情况。多了每一个人不能匹配与他编号相同的马的条件。依然将两个序列排序，我们可以证明对于任意一个人$i$，能和它匹配的马的编号一定在$[i-2,i+2]$内。注意这里是排序后的序列。

因为假设$a_i$匹配了$b_{i+3}$那么在$a_{i+1},a_{i+2},a_{i+3}$中至少可以找到一个元素，交换它和$a_i$所匹配马后依然没有人匹配和它编号相同的马。画一下就很好理解了。

所以我们设$f_i$表示前$i$个人恰好匹配完前$i$匹马的最大权值，那么$f_i$只可能从$f_{i-3},f_{i-2},f_{i-1}$转移而来。

$f_i=\max (f_{i-3}+z_i,f_{i-2}+y_i,f_{i-1}+x_i)$

其中$x_i,y_{,}{z}_i$就是前$1，2，3$对分别匹配的最大贡献，可以暴力枚举所有情况。

观察到每次修改只是单点修，并且询问是全局询问（因为我们排了序后原来编号就是乱序了），而且这个转移是$max$里面套个加法，所以直接上动态 dp 即可。

$\left[\begin{array}{ccc}{f}_{i-3}& f_{i-2}& f_{i-1}\end{array}\right]\left[\begin{array}{ccc}-\infty & -\infty & z_i\\ 0& -\infty & y_i\\ -\infty & 0& x_i\ast \ast \end{array}\right]=\ast \ast \left[\begin{array}{ccc}{f}_{i-2}& f_{i-1}& f_i\end{array}\right]$

$code$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=30010;
const ll Inf=1e18;
int n,m,id[N];

struct node
{
int a,id;
}a[N],b[N];

bool cmp(node x,node y)
{
return x.a<y.a;
}

struct Matrix
{
ll a[4][4];
Matrix() { memset(a,0xcf,sizeof(a)); }

friend Matrix operator *(Matrix a,Matrix b)
{
Matrix c;
for (int i=1;i<=3;i++)
for (int j=1;j<=3;j++)
for (int k=1;k<=3;k++)
c.a[i][j]=max(c.a[i][j],a.a[i][k]+b.a[k][j]);
return c;
}
}mat[N],fad;

struct SegTree
{
Matrix a[N*4];

void update(int x,int l,int r,int k)
{
if (l==r) { a[x]=mat[l]; return; }
int mid=(l+r)>>1;
if (k<=mid) update(x*2,l,mid,k);
else update(x*2+1,mid+1,r,k);
a[x]=a[x*2]*a[x*2+1];
}
}seg;

ll calc(int l,int r)
{
if (l<=0) return -Inf;
int n=r-l+1,c[5]={0,0,0,0,0}; ll ans=-Inf;
for (int i=1;i<=n;i++) c[i]=l+i-1;
do {
ll sum=0;
for (int i=1;i<=n;i++)
{
if (a[l+i-1].id==b[c[i]].id) { sum=-Inf; break; }
sum+=1LL*a[l+i-1].a*b[c[i]].a;
}
ans=max(ans,sum);
} while (next_permutation(c+1,c+1+n));
return ans;
}

void upd(int i)
{
mat[i].a[1][1]=-Inf; mat[i].a[1][2]=-Inf; mat[i].a[1][3]=calc(i-2,i);
mat[i].a[2][1]=0; mat[i].a[2][2]=-Inf; mat[i].a[2][3]=calc(i-1,i);
mat[i].a[3][1]=-Inf; mat[i].a[3][2]=0; mat[i].a[3][3]=calc(i,i);
seg.update(1,1,n,i);
}

int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i].a),a[i].id=i;
for (int i=1;i<=n;i++)
scanf("%d",&b[i].a),b[i].id=i;
sort(a+1,a+1+n,cmp); sort(b+1,b+1+n,cmp);
for (int i=1;i<=n;i++) id[b[i].id]=i;
for (int i=1;i<=n;i++) upd(i);
fad.a[1][3]=0;
while (m--)
{
int x,y;
scanf("%d%d",&x,&y);
swap(b[id[x]].id,b[id[y]].id);
swap(id[x],id[y]);
for (int i=0;i<=2;i++)
{
if (id[x]+i<=n) upd(id[x]+i);
if (id[y]+i<=n) upd(id[y]+i);
}
printf("%lld\n",(fad*seg.a[1]).a[1][3]);
}
return 0;
}

T3 P9675 [ICPC2022 Jinan R] Shortest Path

原题链接

感性理解，当$k$很大时，$1\to n$经过恰好$k$条边的最短路会在一条权值很小的边上来回移动。考虑将这种猜想转化为严格的结论。

当$k>4n$时，若$1\to n$经过恰好$k$条边的最短路$P_k$存在，则$P_k$总可以形如先从$1$走小于$2n$条边到达某个点$u$，在$u$的某条临边$(u,v)$上来回不断直到剩余步数小于$2n$，然后从$u$走到$n$

对于$k\le 4n$时，直接求答案。

对$k>4n$，枚举每条边考虑贡献：预处理从$1$和$n$走$0\le k\le 4n+1$步到$u$的最短路权值，可以对每个点1$u$求出从$1$到$n$中途经过$u$且恰好走$4n$和$4n+1$步的最短路权值$F_{4n}(u)$和$F_{4n+1}(u)$。

于是，边$(u,v)$对$k>4n$的答案的贡献为：

$\{\begin{array}{ll}{F}_{4n}(u)+(k-4n)w(u,v),& 2\mid k\\ F_{4n+1}(u)+(k-4n-1)w(u,v),& 2\nmid k\end{array}$

分成$k$ 是奇数或偶数两种情况之后，答案来自每条边的贡献关于$k$是一个等差数列，于是答案关于$k$可表示为若干等差数列的$min$。

将李超树替换成暴力，虽然理论复杂度变劣，但因为复杂度实际上是关于段数的，而段数一看就很难卡满，所以效率相差不大，而且非常好写。

$code$

#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int mod = 998244353;
void addt(int &x, int y) {
x += y, x >= mod && (x -= mod);
}
int add(int x, int y) {
return x += y, x >= mod && (x -= mod), x;
}
constexpr int N = 2e3 + 5;
int n, m, x, ans;
ll f[N << 2][N], g[N << 2][N], F[N], G[N];
vector<pii> e[N];

void solve() {
cin >> n >> m >> x, ans = 0;
for (int i = 1; i <= n; i++) e[i].clear();
for (int i = 1; i <= m; i++) {
int a, b, w;
cin >> a >> b >> w;
e[a].push_back({b, w});
e[b].push_back({a, w});
}
for (int i = 0; i <= n * 4 + 1; i++) {
for (int j = 0; j <= n; j++) {
f[i][j] = g[i][j] = 2e18;
F[j] = G[j] = 2e18;
}
}
f[0][1] = g[0][n] = 0;
for (int i = 0; i <= n * 4; i++) {
for (int j = 1; j <= n; j++) {
for (pii _ : e[j]) {
int it = _.first, w = _.second;
f[i + 1][it] = min(f[i + 1][it], f[i][j] + w);
g[i + 1][it] = min(g[i + 1][it], g[i][j] + w);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n * 4 + 1; j++) {
if (j <= n * 4) F[i] = min(F[i], f[j][i] + g[n * 4 - j][i]);
G[i] = min(G[i], f[j][i] + g[n * 4 + 1 - j][i]);
}
}

vector<pll> odd, even;
for (int i = 1; i <= n; i++) {
for (pii _ : e[i]) {
if (i > _.first) continue;
int w = _.second;
if (F[i] <= 1e18) even.push_back({w, F[i] - 4ll * n * w});
if (G[i] <= 1e18) odd.push_back({w, G[i] - (4ll * n + 1) * w});
}
}
for (int i = 1; i <= x && i <= n * 4; i++) {
if (f[i][n] <= 1e18) addt(ans, f[i][n] % mod);
}
if (x <= n * 4) {
cout << ans << endl;
return;
}

if (!odd.empty()) {
auto calc = [&](int k) {
k = k * 2 + 1;
ll ans = LONG_LONG_MAX;
for (pll it : odd) ans = min(ans, it.first * k + it.second);
return ans;
};
int c = n * 2, lim = x - 1 >> 1;
while (c <= lim) {
ll v = calc(c);
if (c == lim) {
addt(ans, v % mod);
break;
}
int l = c + 1, r = lim;
ll d = calc(c + 1) - v;
while (l < r) {
int mid = l + r + 2 >> 1;
if (calc(mid) == v + d * (mid - c)) l = mid;
else r = mid - 1;
}
addt(ans, v % mod * (l - c + 1) % mod);
addt(ans, 1ll * (l - c + 1) * (l - c) / 2 % mod * d % mod);
c = l + 1;
}
}

if (!even.empty()) {
auto calc = [&](int k) {
k = k * 2;
ll ans = LONG_LONG_MAX;
for (pll it : even) ans = min(ans, it.first * k + it.second);
return ans;
};

int c = n * 2 + 1, lim = x >> 1;
while (c <= lim) {
ll v = calc(c);
if (c == lim) {
addt(ans, v % mod);
break;
}
int l = c + 1, r = lim;
ll d = calc(c + 1) - v;
while (l < r) {
int mid = l + r + 2 >> 1;
if (calc(mid) == v + d * (mid - c)) l = mid;
else r = mid - 1;
}
addt(ans, v % mod * (l - c + 1) % mod);
addt(ans, 1ll * (l - c + 1) * (l - c) / 2 % mod * d % mod);
c = l + 1;
}
}
cout << ans << endl;
}
signed main() {
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}

T4 期望

关键的是我们要求出期望的式子：

$\frac{{\sum }_{i=1}^n{\sum }_{j=i+1}^n{a}_i{a}_j}{C_n^2}$

因为每一队$(i,j)$有$\frac{1}{2\times C_n^2}$的概率被选出来，贡献为$a_i{a}_j$

可以用dp，设$f(i,j)$表示前$i$个数，选出$j$个区间，状态转移方程就是

$(f_{i,j}=\max (f_{i-1,j},f_{i-k,j-1}+val(i-k+1,i))$

这是暴力做法，会超时。

我们可以把式子化简一下。设$S_i$表示前缀和，$S_i^{‘}$表示平方的前缀和。

则$\begin{array}{rl}\frac{{\sum }_{i=1}^n{\sum }_{j=i+1}^n{a}_i{a}_j}{C_n^2}& =\frac{\frac{{\sum }_{i=1}^n{\sum }_{j=1}^n{a}_i{a}_j-{\sum }_{i=1}^n{a}_i^2}{2}}{C_n^2}\\ & =\frac{S_n^2-S_n^{\prime }}{n(n-1)}\end{array}$

这样就结束了。

总结

大帝出的题还是很难的，幸亏我是把第二题做出来了，要是4小时看一道题还没做出来就寄了。大帝非得在光棍节给我当头一棒，生气捏～(　TロT)σ，数学知识真的是烤得太全面啦，什么幂和，拉格朗日插值全都出来了。

原文地址：https://blog.csdn.net/xiebohang/article/details/143699817

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！