本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-12-04 14:02:00

以此篇题解纪念我第一次参加 NOIP，并通过此题。

思路

这道题如果做过 CSP-S2022 T1，就可以想到枚举一个点，并快速求出其他点的位置。

本题我赛时先想到了一个暴力做法，然后发现可以优化。

所以先来说说暴力。

暴力做法 1

暴力枚举所有点的坐标，复杂度 $O(n^3m^3)$。

暴力做法 2

可以发现，做法 1 进行了大量不必要的枚举。

以较为简单的 C 形举例。

当左上和左下端点被枚举之后，显然，另外两个端点选择的方案数就分别是左上端点和左下端点能向右伸展的长度（即向右伸展多少个点不会遇到土坑）。

所以可以用 $O(nm)$ 的时间预处理出每个点向右能伸展的长度，然后和做法 1 一样，枚举左上和左下端点，计算方案数。

另外对于 F 形，做法也差不多。

其实就是在 C 形的左下端点下方增加了一个点，只需要再用 $O(nm)$ 的时间预处理每个点能向下伸展的长度。

现在复杂度 $O(n^2m)$。

本做法同时求出来了每个点作为左下端点时的方案数（向右伸展的方案数和向下伸展的方案数），下面的做法会用到。

可通过做法

考虑怎样把枚举左下端点的复杂度也砍了。

还是以 C 形举例，F 形类似。

由题意可知左上端点和左下端点之间不能有土坑，也就是说左下端点只可能出现在从左上端点开始向下的一段连续区间内。

而这段连续区间就是左上端点最长能向下伸展而不遇到土坑的区间，每个点对应的这样的一段连续区间已经在做法 2 中的预处理求出来了。

而总方案数就是这段连续区间内每个点作为左下端点方案数的总和。

对每列，把每个点作为左下端点的方案数做前缀和，枚举了左上端点后就能 $O(1)$ 查询左下端点的方案数总和了。

时间复杂度 $O(nm)$。

关于坑

记录一下，大概有这些错，能过大样例：

1. 没看见多测。
2. 前缀和写反或者忘写（这个比较离谱，大样例精心构造能过）。
3. 模数打错。
4. 数组忘清空。
5. 忘乘 c 或 f。

Code

\/*
NOIP rp++
*\/
#include <bits\/stdc++.h>
using namespace std;
namespace mychengxu
{
	typedef long long ll;
	const ll mod=998244353;
	const int maxn=1e3+5;
	int T,id;
	char a[maxn][maxn];
	int n,m,c,f;
	int hang_len[maxn][maxn];
    \/\/ i 行 j 列，可以向右延伸多长
	int lie_len[maxn][maxn];
    \/\/ i 行 j 列，可以向下延伸多长
	void dfs_hang(int i,int j)
	{
		if(a[i][j]=='1')return;
		hang_len[i][j]=1;
		if(j==m)return;
		dfs_hang(i,j+1);
		hang_len[i][j]=hang_len[i][j+1]+1;
	}
	void dfs_lie(int i,int j)
	{
		if(a[i][j]=='1')return;
		lie_len[i][j]=1;
		if(i==n)return;
		dfs_lie(i+1,j);
		lie_len[i][j]=lie_len[i+1][j]+1;
	}
	ll prefix_hengxiang[maxn][maxn];
    \/\/ (i,j): 第 i 列 从上到下前 j 个点作为左下端点总和 (C 形)
	ll prefix_hengxiang_calcdw[maxn][maxn];
    \/\/ (i,j): 第 i 列 从上到下前 j 个点作为左下端点总和 (F 形)

    void main()
	{
		freopen("plant.in","r",stdin);
		freopen("plant.out","w",stdout);
		scanf("%d%d",&T,&id);
		while(T--)
		{
			memset(hang_len,0,sizeof(hang_len));
			memset(lie_len,0,sizeof(lie_len));
			scanf("%d%d%d%d",&n,&m,&c,&f);
			for(int i=1;i<=n;i++)
			{
				scanf("%s",a[i]+1);
			}
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=m;j++)
				{
					if(a[i][j]=='0')
					{
						if(!hang_len[i][j])
						{
							dfs_hang(i,j);
						}
					}
				}
			}	
			for(int j=1;j<=m;j++)
			{
				for(int i=1;i<=n;i++)
				{
					if(a[i][j]=='0')
					{
						if(!lie_len[i][j])
						{
							dfs_lie(i,j);
						}
					}		
				}
			}
			for(int i=1;i<=m;i++)
			{\/\/ 第 i 列
				for(int j=1;j<=n;j++)
				{
					prefix_hengxiang[j][i]=prefix_hengxiang[j-1][i]+(ll)(hang_len[j][i]-1);
					prefix_hengxiang[j][i]%=mod;
				}
			}
			for(int i=1;i<=m;i++)
			{\/\/ 第 i 列
				for(int j=1;j<=n;j++)
				{
					prefix_hengxiang_calcdw[j][i]=prefix_hengxiang_calcdw[j-1][i]+(ll)(hang_len[j][i]-1)*ll(lie_len[j][i]-1);
					prefix_hengxiang_calcdw[j][i]%=mod;
				}
			}
			\/\/ C
			ll ans_c=0;
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=m;j++)
				{\/\/ 枚举左上角
					if(a[i][j]=='1')continue;
					ll col1=hang_len[i][j]-1;
					\/\/ (i,j) 向右长度
					int dwpos=i+lie_len[i][j]-1;\/\/ (i,j) 向下延伸长度
					if(dwpos<=i+1)continue;
					ll col2=(prefix_hengxiang[dwpos][j]-prefix_hengxiang[i+1][j]);
					ans_c+=col1*col2%mod;
					ans_c%=mod;
				}
			}
			\/\/ F
			ll ans_f=0;
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=m;j++)
				{
					if(a[i][j]=='1')continue;
					ll col1=hang_len[i][j]-1;
					int dwpos=i+lie_len[i][j]-1;
					if(dwpos<=i+1)continue;
					ll col2=(prefix_hengxiang_calcdw[dwpos][j]-prefix_hengxiang_calcdw[i+1][j]);
					ans_f+=col1*col2%mod;
					ans_f%=mod;
				}
			}
			printf("%lld %lld\n",ans_c*(ll)c,ans_f*(ll)f);
		}
	}
}
int main()
{
	mychengxu::main();
	return 0;
}  

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-12-31 12:10:02

A

显然，每次选择最小的 $a_i$ 进行替换最优。
所以对 $a$ 维护一个小根堆，每次操作取出堆顶，替换掉在扔回堆里就行了。

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
const int maxn=105;
int a[maxn],b[maxn];
int n,m;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        FOR(i,1,n)scanf("%d",&a[i]);
        FOR(i,1,m)scanf("%d",&b[i]);
        sort(a+1,a+n+1);
        priority_queue<int,vector<int>,greater<int> > que;
        FOR(i,1,n)
        {
            que.push(a[i]);
        }
        FOR(i,1,m)
        {
            int u=que.top();
            que.pop();
            u=b[i];
            que.push(u);
        }
        ll ans=0;
        while(!que.empty())
        {
            ans+=que.top();
            que.pop();
        }
        printf("%lld\n",ans);
    }
    return 0;
}

B

思路大概是，可以发现，对于 $n \ge 2$，代价至少是 $n+1$。
想想怎样构造才能使 $c_i$ 不超过 $n+1$。
一个常见的思路是，最大的数配最小的数，次大配次小，$\cdots \cdots$
也就是 $n,1,n-1,2,n-2,3,\cdots\cdots$。

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
const int maxn=2e5+5;
int t;
int n,k;
int ans[maxn];
bool vis[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        int l=1,r=n;
        while(l<r)
        {
            printf("%d %d ",r,l);
            l++;
            r--;
        }
        if(l==r)
        {
            printf("%d\n",l);
        }
        else printf("\n")
;    }
    return 0;
}

C

待填坑

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-12-31 14:13:03

在未达到紫名橙名，没有 Coach mode 的情况下，没有权限查看题目数据。

但是，这一定不包括自己的。

所以，我就用一个奇技淫巧让他变成自己的。

点开比赛页面，看右边的 Clone contest，点进去，确认克隆比赛，然后这个比赛就被复制了一份，复制出来的这份自己就有权限修改，访问。

结束。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-01-14 14:25:10

CF1353E

• Difficulty: $\color{purple}\text{1900}$
• sol1:
  可以枚举最后一个灯的所在位置，进行 dp。
  设 $dp_i$ 表示最后一个灯在位置 $i$，且只考虑前 $i$ 个位置的最优解。
  显然，对于转移，一种情况是前面全是 $0$，只有这一位是 $1$；另一种情况，是位置 $i-k$ 为 $1$，$i-k+1$ 到 $i-1$ 都是 $0$，从$dp_{i-k}$ 转移过来。
  复杂度 $O(n)$
  提交记录
• sol2
  这些灯可以存在的位置模 $k$ 同余。
  所以可以用 $O(k)$ 的时间枚举灯可选的位置。
  由题目可知，除了选出了的一些相邻的模 $k$ 同余的位置是 $1$，其余位置都得是 $0$。
  也就是说选出了一个位置使其为 $1$，如果原来就是 $1$，可以少改变一次，如果原来是 $0$，就要多变一次。
  现在就是选出一些连续的模 $k$ 同余的位置使得最终改变的次数最小。
  成经典贪心题了。
  复杂度 $O(k \cdot \frac{n}{k}) = O(n)$
  提交记录
  然后发现和第一份做法都是 93ms，复杂度一样常数也一样。。。。。

CF1403C

• Difficulty: $\color{black}\text{3}\color{red}\text{200}$
• sol:

CF3A

• Difficulty: $\color{gray}\text{1000}$
• sol:
  本质上就是可以一次操作中可以改变单个坐标一次，也可以横纵坐标一起改一次。
  贪心是很显然的。
  提交记录

CF1396C

• Difficulty: $\color{orange}\text{2300}$
• sol:
  设 $dp_i$ 表示解决完前 $i$ 关的最小代价。
  对于每一关，显然都分两种情况：一次解决所有怪；解决所有的小怪后，逃跑，再回来打死 Boss。
  想一下，移动路线必然是从 $1$ 到 $n$（最后一步可能还有个 $n$ 到 $n-1$）。
  对于一次解决所有怪（即不逃跑再回来打）的情况，从 $dp_{i-1}$ 转移。
  对于需要逃跑一次的情况，最优的方法是移动到相邻的关卡，相邻两关互相横跳再继续往后走（总体上是向后走的，一些关卡因为要打两遍，为了减少时间消耗只往前走一个关卡，然后回来继续向后走）。
  所以这种情况也从 $dp_{i-1}$ 转移。
  注意走到了 $i-1$ 再回来， $i-1$ 和 $i$ 这样下来都能打两遍，也就是说还可以从 $dp_{i-2}$ 转移过来，计算 $i-1$ 和 $i$ 打两遍的代价。
  总体说完了，一些细节要处理。
  注意如果是 $n-1$ 和 $n$ 互相横跳的话，由于不存在没访问过的点了，$n$ 可以直接解决所有怪然后跳到 $n-1$，不再回去，这个要特判。
  复杂度 $O(n)$。
  提交记录

ABC176F

• Difficulty: $\color{red}\text{2912}$
• sol:

ZOJ2113

• Difficulty: Unknown
• sol:

CF498E

• Difficulty: $\color{red}\text{2700}$
• hint: 矩阵乘法
• sol:

ABC144F

• Difficulty: $\color{orange}\text{2189}$
• sol:

CF8E

• Difficulty: $\color{red}\text{2600}$
• sol:

CF1140E

• Difficulty: $\color{orange}\text{2200}$
• sol:
  显然只需要分别计算每段连续 $-1$ 的方案数，然后乘起来就行了。
  进行一些模拟发现，每段连续 $-1$ 的方案数和左右两边的值没有关系，有关系的是左右两边的值是否相等。
  可以 dp 预处理长度为 $i$ 的连续 $-1$ 段的方案数。
  $dp_{i,0}$ 表示长度为 $i$ 且左右两边的定值不相等的 $-1$ 连续段。
  $dp_{i,1}$ 表示长度为 $i$ 且左右两边的定值相等的 $-1$ 连续段。
  把 dp 状态对应的图画出来（如 $dp_{i,0}$ 对应 $a,-1,-1,\cdots,-1,b$），就能列出转移方程，即：
  $dp_{i,1} = dp_{i-1,0} \cdot (k-1)$
  $dp_{i,0} = dp_{i-1,0} \cdot (k-2) + dp_{i-1,1}$
  复杂度 $O(n)$。
  提交记录

CF1782E

• Difficulty: $\color{orange}\text{2300}$
• sol:

vjudge Kattis-tetris

• Difficulty: unknown
• sol:

CF1699E

• Difficulty: $\color{red}\text{2600}$
• sol:

acmicpc.net 12610

• Difficulty: unknown
• translation：
  题意：
  一年有 $N$ 天，其中有 $T$ 场比赛。
  每一场比赛分为很多轮，且每一轮都分布在比赛开始后的第 $\cdots$ （不知道）天。
  这些比赛的开始时间随机分布在一年中的一些天。
  设一年中一天同时有 $S$ 轮，那么这一天所带来的快乐值贡献为 $S^2$。
  求这一年快乐值期望总和（如果某些轮到了下一年，不算）
  输入格式：
  第一行有一个整数 $C$，代表有 $C$ 组数据。
  每组数据第一行是两个整数 $N,T$。
  接下来 $T$ 行，第 $i$ 行描述第 $i$ 场比赛。
  每行第一个整数 $m$，代表这场比赛有 $m$ 轮，接下来是 $d_2,d_3,d_4,\cdots,d_m$，$d_i$ 代表第 $i$ 轮在比赛开始之后的第 $d_i$ 天进行（第一轮都是在比赛开始的第一天进行，所以没给出）
  输出格式：
  每组数据输出一行，每行输出一个最简形式的带分数，代表答案（具体看原文）。
• sol:

POJ3623

• Difficulty：unknown
• hint: 贪心利用后缀数组优化
• sol:

CF295D

• Difficulty: $\color{red}\text{2400}$
• sol:

CF533D

• Difficulty: $\color{black}\text{3}\color{red}\text{000}$
• sol:

CF1418D

• Difficulty: $\color{orange}\text{2100}$
• sol:
  首先，如果点数小于等于 $2$，不用进行操作。
  否则，画图可知，答案为最大坐标减最小坐标，再减去（相邻两个点位置差的最大值）。
  加上了括号方便断句。
  最大坐标和最小坐标用 set 维护就行了，接下来要想的是如何维护相邻两个点位置差的最大值。
• sol.1
  用 multiset 维护相邻两个点位置差的最大值。
  考虑插入删除操作的影响到底是什么。
  对于插入，设插入在位置 $x$，$x$ 左边最近的点为 $l$，$x$ 右边最近的点为 $r$，相当于删除区间 $[l,r]$ 的影响，加入区间 $[l,x],[x,r]$ 的影响。那只需要在 multiset 里面删掉一个 $r-l$，加入一个 $x-l$ 和一个 $r-x$。
  对于删除，和插入差不多，只不过反过来了。
  一个技巧：如果不想分类讨论，可以先插入两个点，分别是 $+ \infty$ 和 $- \infty$。
  复杂度 $O((n+q) \log n)$。
  提交记录
• sol.2
  用线段树维护相邻两个点位置差的最大值。
  $[1,10^9]$ 的坐标范围，先离散化。
  合并区间的时候，就是左子区间的答案，右子区间的答案，和（右子区间最靠左的点的坐标）减去（左子区间最靠右的点的坐标） 取 max 作为当前区间的答案。
  所以线段树需要维护三个值，即当前区间答案，当前区间最靠左的点的坐标，当前区间最靠右的点的坐标。
  复杂度 $O((n+q) \log n)$。
  提交记录

Luogu P4066

• Difficulty: $\color{purple}\text{省选/NOI}$
• sol:

CF1520G

• Difficulty: $\color{orange}\text{2200}$
• sol:
  一定只使用一次传送门。
  证明：设使用两次或以上的传送门能达最优效果，第一次使用传送门的起点为 $s$，最后一次使用传送门的终点为 $t$，显然直接从 $s$ 到 $t$ 更优。
  现在分两种情况统计答案，第一种是不使用传送门，第二种使用一次传送门。
  第一种很简单，第二种也只需要找出走的距离和跳的代价总和最小的两个点就行了。
  复杂度 $O(nm)$。
  我不知道开了 Ofast 为啥还跑这么慢，提交记录。

POJ1151

• Difficulty: unknown
• sol:

CF845E

• Difficulty: $\color{red}\text{2400}$
• sol:
  二分答案，然后离散化所有矩形，看空隙之间距离就行了。
  离散化的时候要把矩阵四个顶点旁边的点也加入离散化，否则空隙可能会被离散化凭空消失掉。
  Codeforces 提交记录
  这样复杂度 $O(k^2 log_{n})$，是最劣解。
  为了优化复杂度，可以采用扫描线。
  扫描线题解

CF1635F

• Difficulty: $\color{red}\text{2800}$
• sol:

CF1284D

• Difficulty: $\color{orange}\text{2100}$
• sol:
  本质上是问是否不存在两个会议，使得在一个会议场不发生冲突，另一个发生冲突。
  一个简单的套路就是对每个会议分配一个随机权值，然后对每个会议，在两个会场分别记录与其不发生冲突的会议的权值的异或和，看两个会场所得结果是否一样就行了。
  计算不发生冲突的会议的权值的异或和，前后缀异或和预处理就行了。
  这样是复杂度是 O(值域) 的，过不去。
  考虑实际上只关心区间端点的相对大小，可以离散化。
  复杂度是离散化的 $O(n \log n)$。
  提交记录

CF1132F

• Difficulty: $\color{purple}\text{2000}$
• sol:
  我不会比洛谷题解说得清楚。

acmicpc8081

• Difficulty: unknown
• sol:

CF ACM sguru442

• Difficulty: unknown
• sol:

CF482C

• Difficulty: $\color{red}\text{2600}$
• sol:

https://coursera.cs.princeton.edu/algs4/assignments/baseball/specification.php

• Difficulty: unknown
• sol:

UVA1086

• Difficulty: unknown
• sol:

ABC210F

• Difficulty: $\color{orange}\text{2632}$
• sol:

HDU-3062

• Difficulty: unknown
• sol:

POJ-3281

• Difficulty: unknown
• sol:

POJ-1149

• Difficulty: unknown
• sol:

POJ-2391

• Difficulty: unknown
• sol:

CF1009G

• Difficulty: $\color{red}\text{2400}$
• sol:
  贪心思想。
  从前到后枚举每一位的字母。
  优先保证前面的小。
  当一位枚举了一个字母之后，可以通过网络流判断后面位是否存在合法方案。
  关于网络流：
  搞成二分图的形式，左部点是位置，右部点是 $6$ 个字母。
  右部点向超级汇点连权值为该点在原串中出现次数的边。
  当然这不是真正的二分图，可以这样转化成二分图：把每种字母拆成该字母在原串中出现次数个点。
  然后枚举右部点 $6$ 个字母的子集，hall 定理判定即可。
  提交记录

ARC076F

• Difficulty: $\color{red}\text{2819}$
• sol:
  只考虑一个段点限制，然后贪心得计算右端点。

CF808F

• Difficulty: $\color{red}\text{2400}$
• sol:
  二分等级。
  质数除了 $2$ 都是一奇一偶组成的，而 $2 = 1+1$，也就是说只能有一个 $1$。
  把 $1$ 处理掉之后形成了一个以奇偶分类的二分图，超级源点向左部点连权值为能量的边，右部点向超级汇点连权值为能量的边，然后求最小割。
  CF 提交记录

loj3379 【CSP-S2020 儒略日】

• Difficulty: $\color{green}\text{普及+/提高}$
• sol:

CF Gym100722

这个 gym 比较特殊，可以查看他人代码，只有看数据需要 Coach Mode。
在 UVA/SPOJ/BZOJ 有原题。

• Difficulty: unknown
• B:
  把集合编上号，模拟。
• D:
  最小斯坦纳树。
• E:
  排序，然后 dp。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-01-30 17:15:04

这个傻逼赛前还想着能不能切两题进 Gold。
然而被结果泼了一盆冰水。

比赛过程

开局看 T1。
读了一遍题，发现原题面可以用一个有向图表示出来。
我认为一种字母变为另一种字母，就是建一条有向边。
如果某个点出度 $\ge 2$，或者所有连通子图都是环且所有字母都出现过，无解。
我手动模拟了一些数据，发现对于每个连通子图，如果是链，对答案的贡献为 size，如果是环，则还有破环为链的代价，贡献为 size+1。
想好了就立刻开写，用了 0.5 h 写完并一发过了样例。
最后检查了一遍，提交。
结果 0 分。
我这下开始怀疑我的做法，再检查了几遍，果然找出了不少 sb 错。
我还造了一百多组特殊性质的样例，全部通过。
提交。
还是 0 分，特殊性质也 WA 了。
这下我傻了。
看着只剩下 1h，再调不出来就要爆零，我只好弃掉 T1，去看 T2。
想了一会 T2，想出来了一个做法，就是预处理答案，然后每次修改 $O(n)$ 处理。
看着时间不太够用，就以我最快的手速 20 分钟写完暴力+非暴力总共一百七八十行的代码，并一发过样例。
提交暴力，暴力分拿到。
提交非暴力，一分没有。
我又傻了，接下来的 40 分钟，我一直在找各种错，找出了一堆 sb 错，如变量名打错，修改部分写反，等等。
最后也没调出来，倒是去 T3 骗了点分。

寄了。

solution

比赛没有结束

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-02-22 17:34:28

Day -5 to Day 0

复习。

Day1

第一个语文，文常一堆不会的。
看到作文傻眼了，但还是最后 5min 写完了。

第二个 zz。
题自我感觉比较水，全是板子题。
45min 写完。

中午和 ybx 颓了一会（自创了一种棋，下了一会）。

下午生物，历史，都是最后 1s 写完，大概就是刚落笔就打铃。

Day1 总结：依托答辩。

Day2

第一个数学。
看着题很水，就一路切过去。

不知不觉，由于没把握好时间，到 T27 的时候已经只剩下 40min 了。

然后 T27 的第 2 问，由于没有手动计算，只是用眼看，结果 30min 看不出来。

这时还剩 10min，我面临两个选择：

1. 放弃剩下的 4pts，去检查。
2. 赌一把，切掉剩下 4pts。

最终我选择了第 2 种。

已经没有时间让我来观察了，必须尽快推算。
结果手推了 8min，成功绝杀。

自信认为 All killed。

剩下也没啥时间检查了，摆。

考完和 whk 第一 wyx 对答案，发现前面犯了好几个 sb 错，例如忘画坐标系，漏写结论，等等。

为没有检查付出了惨痛代价，如果不去抢那个 AK，我就是 116。现在虽然把最后一题绝杀了，反倒不如去检查分多。

做题速度还是太慢了。

和后面的人聊了一会，他说这次有一堆原题，包括最后的 T27，他都见过，所以 45min 就做完了。

我心里问候了一会出题人，搁这学 FJOI 干啥，对于我这个考前几乎没有任何数学刷题的人........

接下来考地理。
考试考完感觉依托答辩，但是对完答案自我感觉良好（指 30 道选择题只挂了一个）

考英语。
试卷里有一堆课本里没有的单词，语法，如 rating 啥的。
考得依托答辩。

Day2 总结：依托答辩

总结：

依托答辩。
考完试过不了多久就是 SDOI 了，自认为靠着 noip 成绩，大概率能去正式参赛，rp++。

UPD:

10th。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-02-23 19:40:29

上周末 HB 发了个某大学的 46 页英文算法文档。
快累死了，记录一下大体感觉在说什么。
文档链接

2023.2.22

P2 ~ P4 大概讲了个利润最大化问题。
大概就是给出总共生产多少件，每种产品的利润（2 种），每种产品数量限制，求利润最大多少。
书上以各产品数量为坐标，图画出来，用爬山算法解了（在一个多面体上执行爬山算法）。

2023.2.23

P5 ~ P7 增加限制，变为多维问题。
P7 底部讲了一个这样的问题

Next we turn to a miniaturized version of the kind of problem a network service provider might face

翻译： 接下来我们转向这类题目的一个简化版本，即 CCF 收钱的时候可能会面临的选择。

具体内容如下
假设 CCF 正在管理一个网络，要在一些用户之间建立连接（所有要建立的连接给定），每个连接有 $3$ 种方式建立，各要圈不同数目的钱，求最多能圈多少钱。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-02-24 20:17:24

A 题比较水，但是由于细节错误 0.5h 才调过样例，提交 AC。
B 题迅速解决了列的贡献统计，被行卡了。
C 题瞎写了个贪心没过样例。
看了下榜，光荣垫底。

A

枚举 $a,c$，随着 $c$ 向后移顺便计算对 $b,d$ 取值数量的影响（就是从上一状态转移过来）。
需要注意这题略微卡空间，我是把 int 换成 short 才过的。
提交记录

B

C

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-02-26 00:37:48

比赛经历

看 A 题，明显如果满足了第一个前缀，后面的都能满足，用了 8min 想完写完提交 AC。
B 题更水，明显看要修改的段是否连续，6min 想完写完提交 AC。

赛后得知 performance一度 CM（1900+），可惜后来由于 C 题 sb 错耽误实现掉了下去。

C 题，正好刚刚 vp 了的另一场的 C 题和这道题有相同的思路，即通过上一个的答案进行转移。

本题设 $dp_i$ 为第 $i$ 个与前面所有的的答案之和。
转移显然。
写起来比较麻烦，最后我由于少写一个 -1，盯到 比赛结束前 10min 才发现，然后 AC。

检查了一下前面的。
比赛结束。

Sol

• D

• E

• F

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-02-27 14:02:55

题外话

本题解作者赛时由于漏了一个 -1，调了 1h，导致的分数损失约为 350，排名损失约为 600，最后还是把小号送上了 Specialist。

题解

为了方便表示，设 $f(i,j)$ 为 $A_i$ 与 $A_j$ 不同元素总数。

解法一

暴力计算 $\sum_{i=1}^{n} \sum_{j=0}^{i-1} f(i,j)$。
复杂度 $O(n^3)$。

解法二

想想有没有什么优化。

可以看到每次生成新序列，只从上一个序列修改一个数字，那就启发我们每个序列的答案可以从上一个序列转移，现在把它表示出来：设 $dp_i$ 为 $\sum_{j=0}^{i-1} f(i,j)$。

设本次修改得到的序列为 $A_i$，现在分类讨论一下。

1. 如果本次修改的元素，新值等于旧值，即没有改变原序列，那么 $\sum_{j=0}^{i-2} f(i,j) = dp_{i-1}$，而 $f(i,j-1)$ 显然等于 $n$，即 $dp_i = dp_{i-1} + n$。
2. 如果本次修改的元素，新值不等于旧值，即改变了原序列，这时我们可以先假设本次修改没有改变原序列，先使用情况 $1$ 的答案，然后再根据修改的元素调整答案。我们可以先减去被改掉的旧值的贡献，再加上新值的贡献。而这个东西怎么计算呢，显然只需要分别统计对于所有的 $0 \le j \le i-1$，有多少个 $A_j$ 没有旧值，有多少个 $A_j$ 没有新值。

至此，做法基本确定。

但是问题来了，怎么快速统计每个元素没有出现在多少个序列里，它可以转化为快速统计每个元素出现在了多少个序列里。

由于没有后效性，即对于每个 $dp_i$，只有 $0$ 到 $i-1$ 会进行转移，所以这个统计数值也可以动态转移。

显然不能每增加一个序列就去修改所有的元素出现次数，我们发现修改操作每次只是让一个元素消失，让另一个元素出现，我们可以让它自己改。

也就是设 $start_i$ 表示第 $i$ 种元素在第几个序列开始出现，如果为 $-1$ 代表没出现过；$end_i$ 表示第 $i$ 种元素在第几个序列最后一次出现，如果为 $-1$ 代表一直到现在还没有消失。

第 $i$ 种元素总出现次数即 $end_i - start_i + 1$。

修改的时候，如果是让某元素消失，直接标记上 $end = i-1$ 就行了。

如果是让某元素出现，那分讨一下。

1. 之前没出现过，标记上 $start = i$，$end = -1$。
2. 之前出现过，那还得计算之前的贡献，然后再算上现在的贡献，同时因为从现在开始这个元素又重新出现了，$end$ 必须等于 $-1$，而为了使答案正确，我么可以让 $start = i-(end - start + 1) +1 - 1 = i-(end-start+1)$，形象地理解，这是把之前这个元素出现区间般过来，然后把右端点删掉。

CF 提交记录