题目1 : Numbers
时间限制:8000ms
单点时限:1000ms
内存限制:256MB
描述
给定n个整数常数c[1], c[2], …, c[n]和一个整数k。现在需要给2k个整数变量x[1], x[2], …, x[k], y[1], y[2], …, y[k]赋值，满足
（1）对于所有1 ≤ i ≤ k，都有x[i] ≤ y[i]。
（2）对于所有1 ≤ i ≤ n，都存在至少一个j (1 ≤ j ≤ k)，使得x[j] ≤ c[i] ≤ y[j]。
求出S=(y[1] + y[2] + … + y[k]) - (x[1] + x[2] + … + x[k])的最小值。
输入
第一行两个整数n, k。(1 ≤ n, k ≤ 100000)
接下来n行，每行一个整数c[i]。 (-1000000000 ≤ c[i] ≤ 1000000000)
输出
输出一个整数表示S的最小值。
样例解释
x[1]=-5, y[1]=4,
x[2]=10, y[2]=10.
样例输入
5 2
-5
0
10
4
0
样例输出
9
贪心取最小的n-k个间隔
题目2 : Beautiful Sequence
时间限制:11000ms
单点时限:1000ms
内存限制:256MB
描述
对于一个正整数列a[1], … , a[n] (n ≥ 3)，如果对于所有2 ≤ i ≤ n - 1，都有a[i-1] + a[i+1] ≥ 2 × a[i]，则称这个数列是美丽的。
现在有一个正整数列b[1], …, b[n]，请计算：将b数列均匀随机打乱之后，得到的数列是美丽的概率P。
你只需要输出（P × (n!)）mod 1000000007即可。（显然P × (n!)一定是个整数）
输入
第一行一个整数n。 (3 ≤ n ≤ 60)
接下来n行，每行一个整数b[i]。 (1 ≤ b[i] ≤ 1000000000)
输出
输出（P × (n!)）mod 1000000007。
考虑最后求的数列一定是先递减后不变后递增的
拆成2个数列，dp
f[i][j][k][l] 表示左端的两个数是 i 和 j，右端的是 k 和 l 的方案数
最小值有 k 个重复则乘上 k!。非最小值至多只能有 2 次重复
初始状态为数列均为最小值那个值
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<vector>
#include<set>
#include<string>
#include<queue>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma
#define
#define
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define
ll f[MAXN][MAXN][MAXN][MAXN];
ll a[MAXN],n;
int main()
{
// freopen("B.in","r",stdin);
// freopen(".out","w",stdout);
MEM(f)
n=read();
For(i,n) a[i]=read();
sort(a+1,a+1+n);
int p=a[1],l=0;
ll ans=1;
For(i,n) if (p==a[i]) ans=mul(ans,i),l++;
if (l==n) {
cout<<ans<<endl; return 0;
}
f[l][l][l][l]=1;
Fork(i,l,n-1) {
For(j,i) For(k,i) For(l,i) {
if (!f[i][j][k][l]) continue;
ll p=f[i][j][k][l];
if (a[i+1]-a[i]>=a[i]-a[j]) {
upd(f[i+1][i][k][l],p);
}
if (a[i+1]-a[k]>=a[k]-a[l]) {
upd(f[i+1][k][i][j],p);
}
}
}
ll ans2=0;
For(j,n) For(k,n) For(l,n)
upd(ans2,f[n][j][k][l]);
cout<<mul(ans,ans2)<<endl;
return 0;
}
题目3 : Good 01-Sequence
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
01串指的是只有0,1组成的串。对于一个01串a[1..n]，它的逆序对是指这样的(i,j)，满足1 ≤ i < j ≤ n且a[i] > a[j]。如果一个01串的逆序对数量为奇数，则称它是一个好串。例如，串1010有3个逆序对，它是一个好串；而串0100有2个逆序对，它不是一个好串。
定义这样一个函数f：对于一个01串s，如果s可以写成t1t2…tk的形式（即k个串依次连接），并且所有ti都是好串，那么定义f(s)的值为这样的最小的k；否则，定义f(s)=0。
例如：f(1010)=1，因为1010本身是一个好串。f(101010)=2，因为101010本身不是好串，但它可以拆成101和010。f(110)=0，因为它无法写成若干个好串的连接。
现在有一个长为n的01串s，它共有2n-1个非空子序列（s的子序列是指删去s的若干个数字后（或不删），剩下的数字按原来顺序形成的序列）。你需要计算这些串的f值之和，模1000000007。
例如当s=110时，你需要输出(f(1)+f(1)+f(0)+f(11)+f(10)+f(10)+f(110)) mod 1000000007。
输入
输入一行一个长度为n的01串。(1 ≤ n ≤ 100000)
输出
输出答案模1000000007。
假设 s = t1 · · ·tk，k ≥ 4，其中 ti 都是好串，且 k 取到最小值。则 t1 有奇数个 1，否则
t1t2t3 的逆序对数和 t2t3 的逆序对数的奇偶性不同。所以 t2 有偶数个 0，否则 t1t2 可以合并。
同理，t2 有奇数个 1，t3 有偶数个 0。于是 t1t2t3 的逆序对数为奇数，矛盾。因此最小的 k ≤ 3。
暴力计算不同k出现次数。