上午
考试
第一题
给你一个初始序列，和两个操作：操作1可以使得(i)与(i+2)两个数交换位置，操作2是相邻的数可以交换位置
问：这个序列最少用多少次操作2可是使序列单调递增？
你考虑，操作1的性质：使得(i)与(i+2)两个数交换位置，不就是奇偶性相同的位置吗？而操作2的性质：相邻的数可以交换位置，不就是奇偶性不同的数吗？
把原序列排序之后，对于为排序的序列，我们考虑当前这个数的下标与排完序之后的下标，如果发现他们奇偶性相同，也就是说，可以经过若干次操作1可以变换到那个位置
如果发现奇偶性不同，说明肯定是经过了一次操作1，因此计数器叠加
注意细节：这样统计是真实答案的二倍，因为：假如当前在(i)，你发现这个数排完序之后在(j)（(i < j)），且(i,j)的奇偶性不同，这时你计数器累加，但是到了(j)那个位置，你的计数器还会叠加，也就是说，你的计数器对于同一种情况增加了两次
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
const int N = 2e5+66;
int n, res;
int a[N], b[N];
inline int thestars() {
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
b[i] = a[i];
}
sort(b+1, b+n+1);
for (int i = 1; i <= n; ++ i) {
int pos = lower_bound(b+1, b+n+1, a[i]) - b;
if ((pos&1) != (i&1)) ++ res;
}
cout << (res/2);
return 0;
}
int youngore = thestars();
signed main() {;}
第二题
有(10^8)条横向道路与竖向道理，相邻的道路之间相差(100m)，从左到右第(i)条纵向街道和从下到上第(j)条横向街道之间的交点描述为((i,j))，在某些交点上建有以交点为圆心，半径是 (10) 米的喷泉，行走时不能穿过喷泉。
问你要从((x_1,x_2))走到((x_2,y_2))最短要走多少？
Sample Input
1 1 6 5
3
3 2
5 3
2 4
Sample Output
891.415926535897938
有(10^8)条横向道路与竖向道理，相邻的道路之间相差(100m)，从左到右第(i)条纵向街道和从下到上第(j)条横向街道之间的交点描述为((i,j))，在某些交点上建有以交点为圆心，半径是 (10) 米的喷泉，行走时不能穿过喷泉。
问你要从((X_1,Y_2))走到((X_2,Y_2))最短要走多少？
由于所有的喷泉横纵坐标都相等，所以显然走尽可能多的喷泉可以是路径更短，
对于一个喷泉可以短(20-dfrac 1 4* 2pi r)
至此问题完成转化：最长上升子序列问题
不妨设(X_1<X_2,Y_1<Y_2)，仅当(X_1<x_i<X_2,Y_1<y_i<Y_2)时候，统计这个点对答案的影响
并把所有点按照横坐标排序，求(y_i)以(Y_1)为开始，(Y_2)终止的最长上升子序列
对于正常的(dp)做法，过不去的，需要用(nlog_n)的做法，我想，下文会提到的吧
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
const int N = 3e5+66;
int n, ans, f[N];
int sx, sy, tx, ty;
struct node{int x, y;}a[N];
inline int cmp(node s, node t){
if (s.x == t.x) return s.y > t.y;
if (sy < ty) return s.x < t.x;
return s.x > t.x;
}
inline int thestars() {
cin >> sx >> sy >> tx >> ty >> n;
if (tx < sx) swap(sx, tx), swap(sy, ty);
for (int i = 1; i <= n; ++ i) cin >> a[i].x >> a[i].y;
sort(a+1, a+n+1, cmp);
double mhd = tx - sx + abs(ty - sy);
f[0] = -0x7fffffff;
for (int i = 1; i <= n; ++ i) {
if (a[i].x > max(sx, tx) || a[i].x < min(sx, tx) || a[i].y > max(sy, ty) || a[i].y < min(sy, ty)) continue;
if (a[i].y > f[ans]) f[++ ans] = a[i].y;
else if (a[i].y < f[ans]) {
int pos = lower_bound(f+1, f+ans+1, a[i].y) - f;
f[pos] = a[i].y;
}
}
printf ("%.15lf", 100*mhd-ans*(20-5*M_PI));
return 0;
}
int youngore = thestars();
signed main() {;}
第三题
显然，三分图有以下性质：
- 同一集合内，没有连边
- 不存在一个点向同一个集合连两条边
发现上面的性质好像只涉及到两个集合啊，因此答案呼之欲出：(calc(A,B)*calc(A,C)*calc(B,C))
状态：设(f[i][j])表示一个集合有(i)个点，另一个集合有(j)个点的时候，炼成的三分图的个数
转移：(f[i][j] = f[i][j-1]+f[i-1][j-1]*i)
考虑第二个集合的最后一个点，他可能有什么情况，
第一种，不连边，继承上一次的
第二种，连边，则有(i)种连边方式，若练了某条边，则第一个集合对应的点就不能连其他边了，方案数为：(i*f[i-1][j-1])
结果：(f[a][b]*f[b][c]*f[a][c])
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;
const int N = 3e3+66, mod = 998244353, M = 2000;
int t, a, b, c;
int f[N][N];
inline int thestars() {
cin >> t;
for (int i = 1; i <= 3000; ++ i) {
f[i][1] = i+1;
for (int j = 2; j <= i; ++ j)
f[i][j] = (f[i][j - 1] + i*f[i - 1][j - 1]%mod)%mod;
}
for (int i = 1; i <= 3000; ++ i)
for (int j = 1; j < i; ++ j)
f[j][i] = f[i][j];
while(t --> 0) {
int a, b, c;
cin >> a >> b >> c;
cout << f[a][b]*f[a][c]%mod*f[b][c]%mod << '
';
}
return 0;
}
int youngore = thestars();
signed main() {;}
下午
讲dp！！！
我们来通过通过几道例题来体会一下什么是dp
01背包
将n件有着各自体积和价值的物品装入一个容积为m的背包中，求最大的总价值
状态：(f[i][j])表示前(i)件物品放入背包为(j)的背包中所能获得的最大总价值
转移：(f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]))
结果：(f[n][m])
最长不下降子序列
给出一个长度为n 的序列，求最长的子序列，满足这些元素依次不减
状态：设(f[i])表示以(i)为结尾的最长不下降子序列的最长长度
转移：(f[i] = max(f[j]+1))其中(a[j]<a[i])
结果：(max(f[i]))
上面是(O(n^2))做法，还有一种(O(nlogn))的做法：
状态：设(f[i])表示长度为(i)的的最长不下降子序列的最后一个元素的最小值
举个例子：
有序列(a[] = {8,2,3,5,7,6,4})，所以可得：
(f[0] = 0,f[1] = 2, f[2] = 3, f[3]=5,f[4]=7)(第一遍扫)
遇到(6)考虑更新(f[4])，遇到(4)考虑更新(f[3])
至于为什么是logn的，因为每次是二分查找（(lower)_(bound)是log的）
再次考虑(dp)的牛逼之处： 需要有易于表示的状态，能够列出的转移，便于计算的结果
要把式子推出来再去写代码
下面有几道一般dp，没什么特点，就是难
渡河问题
状态：(f[i])表示将前(i)头牛运到对岸的时间
转移：(f[i] = min(f[j]+2*M+sum[i-j]))其中(sum)为前缀和
结果：(f[n])
解题
给出贪心的(Hack)数据：
50 5
40 10
10 40
10 5
10 3
10 2
状态：(f[i][j])表示处理(1)到(j)的题，最后一次选择了(i)到(j)的最短月数
转移：(f[i][j] = min(f[k][i-1]+1/2))其中剩下的钱足够就是(+1)否则是(+2)
结果：(min(f[i][p])+1)
晚上
没时间写了啊，**白某飞主任