1
前置cheese
排序不等式
设(a_1leq a_2leq ...leq a_n,b_1leq b_2leq ...leq b_n)，则
其中(d_1,d_2,...,d_n)是任意一个排列
取等条件：(a_1=a_2=a_3=...=a_n)或(b_1=b_2=b_3=...=b_n)
证明
用(P(n))表示命题：(sumlimits_{i=1}^na_ib_{n-i+1}leq sumlimits_{i=1}^na_ib_{d_i}leqsumlimits_{i=1}^na_ib_i)
显然(P(1),P(2))成立
假设(P(n))成立，试图证明(P(n+1))成立
则：
那么有
即
我们把右边的(n+1)和(d_1,d_2,...,d_n)中任何一个交换，也可以不动，所以给原来的(n!)全排列乘上了(n+1)的方案数，那么就变成了((n+1)!)，于是
同理有
即
我们把右边的(n+1)和(d_1,d_2,...,d_n)中任何一个交换，也可以不动，所以给原来的(n!)全排列乘上了(n+1)的方案数，那么就变成了((n+1)!)，于是
则(P(n))成立，(P(n+1))成立
solution
最小值是一个正序一个倒序，最大值是两个都正序（期望10分）
每次修改的时候二分修改的数字，每次找到修改的下标位置，修改数值，最终对答案的贡献仅仅是对当前位置的对应项。啥意思？
观察(
ho(Vpm 1))或者((
hopm 1)V)，仅仅是贡献了修改过的(
ho_{operatorname{change}})或者(V_{operatorname{change}})
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 300005;
int n, m, a[N], b[N], p[N], q[N];
LL ans1, ans2;
void solve(int * a, int * b, int w, int del)
{
if (del == 1)
{
int p = upper_bound(a + 1, a + n + 1, w) - a - 1;
a[p]++;
ans1 += b[n - p + 1]; ans2 += b[p];
}
else
{
int p = lower_bound(a + 1, a + n + 1, w) - a;
a[p]--;
ans1 -= b[n - p + 1]; ans2 -= b[p];
}
}
int main()
{
freopen("chemist.in", "r", stdin);
freopen("chemist.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), p[i] = a[i];
for (int i = 1; i <= n; i++) scanf("%d", &b[i]), q[i] = b[i];
sort(a + 1, a + n + 1); sort(b + 1, b + n + 1);//p,q原数组 a,b排序数组
for (int i = 1; i <= n; i++) ans1 += (LL)a[i] * b[n - i + 1], ans2 += (LL)a[i] * b[i];
printf("%lld %lld
", ans1, ans2);
while (m--)
{
int ty, x, del; scanf("%d%d%d", &ty, &x, &del);
if (ty == 1) solve(a, b, p[x], del), p[x] += del;
else solve(b, a, q[x], del), q[x] += del;
printf("%lld %lld
", ans1, ans2);
}
return 0;
}
2
哭了。最想拿分的一个题，没想充分。
两个点相撞并反向，相当于互相穿过，且相对位置不变！！！！这意味着所有点的编号实质上是相对不动的。那这也太好做了吧。
先求出所有颜神最终所在的位置集合。初始状态坐标最小的颜神编号为 1。在行走过程中，若有一
个颜神从 0 走到 (L − 1)，那么坐标最小的颜神的编号就会加 1。若有一个颜神从 (L − 1) 走到 0，坐标最
小的颜神的编号就会减 1。这样就可以得到最终位置的坐标最小的是哪一个颜神了。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N=100005;
int n,L,T,a[N],b[N];
int main()
{
freopen("invert.in", "r", stdin);
freopen("invert.out", "w", stdout);
scanf("%d%d%d",&n,&L,&T);
int s=1;
for (int i=1;i<=n;i++)
{
int x,w;scanf("%d%d",&x,&w);
if (w==1)
{
a[i]=(x+T)%L;
if (T>=L-x) (s-=(T-L+x)/L+1)%=n;
}
else
{
a[i]=((x-T)%L+L)%L;
if (T>=x+1) (s+=(T-x-1)/L+1)%=n;
}
}
s=(s%n+n-1)%n+1;
sort(a+1,a+n+1);
for (int i=1;i<=n;i++) b[(s+i-2)%n+1]=a[i];
for (int i=1;i<=n;i++) printf("%d
",b[i]);
return 0;
}
3
solution
(nle 80)
从左侧出发，令(F_{i,j,k})表示当前所在的一侧还剩(i)个点，另一侧有(j)个点，位于当前侧的第(k)个点的方案数。
若下一步走到另一侧，则(F_{i,j,k})转移到(F_{i,j-1,k}(1le l le j))。
若下一步走到同一侧，则(F_{i,j,k})转移到(F_{i-1,j,k-1})和(F_{i-1,j,k})。最后(F_{1,0,1} imes 2)即为答案。
复杂度(O(n))。
正解
注意到每次都是在某一侧走过编号连续的一段，然后将这一段删掉，再走到另一侧。若某次走了长度为(L)的一段，枚举起点(k)，方案数为
可以先求出某一侧走了若干段的方案数，然后把两侧合并。令(G_{i,j})表示走了(i)段，经过了(j)个点的方案数。枚举第一段经过的点数(k)，由于可以任意选择连续的(k)个点，因此转移为
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
typedef long long LL;
const int N=4005;
int n,f[N][N], MOD;
void solve()
{
f[0][0]=1;
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j++)
f[i][j]=(f[i][j-1]*2%MOD+(LL)f[i-1][j-1]*j%MOD)%MOD;
int ans=0;
for (int i=1;i<=n;i++)
{
(ans+=(LL)f[i][n]*f[i][n]%MOD)%=MOD;
(ans+=(LL)f[i][n]*f[i-1][n]%MOD)%=MOD;
}
printf("%d
",ans*2%MOD);
}
int main()
{
freopen("walk.in", "r", stdin);
freopen("walk.out", "w", stdout);
scanf("%d%d",&n, &MOD);
solve();
return 0;
}