test20190714

Posted on | Views:

又被虐了.

$Fable$

  • 每做一次冒泡,对于一个数 $a_i$ ,若 $i$ 之前的位置有比它大的数,那么其中一个一定会跳到它的后面.
  • 则它的位置向前移了一位,比它大的数少了一个.
  • 初始时,若前面比它大的数的个数 $\ge k$ ,则说明每次都能往前移,最后的位置就是初始位置 $-k$ .对于剩下的数,它们最后一定会从小到大把剩余的位置补满.
  • 离散化 + 树状数组处理.

考试情况:大部分时间都在想/写/调这个题.最后 $A$ 了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
int n,k;
typedef pair<int,int> pii;
pii a[MAXN];
int ans[MAXN],tot[MAXN],rk[MAXN];
int bit[MAXN];
#define lowbit(x) x&(-x)
void add(int x,int c)
{
	for(;x<=n;x+=lowbit(x))
		bit[x]+=c;
}
int sum(int x)
{
	int s=0;
	for(;x;x-=lowbit(x))
		s+=bit[x];
	return s;
}
int main()
{
	freopen("fable.in","r",stdin);
	freopen("fable.out","w",stdout);
	n=read(),k=read();
	for(int i=1;i<=n;++i)
		a[i].second=i,a[i].first=read();
	sort(a+1,a+1+n);
	rk[a[1].second]=1;
	for(int i=2;i<=n;++i)
	{
		if(a[i].first==a[i-1].first)
			rk[a[i].second]=rk[a[i-1].second];
		else
			rk[a[i].second]=i;
	}
	for(int i=1;i<=n;++i)
	{
		add(rk[i],1);
		tot[i]=sum(n)-sum(rk[i]);
		if(tot[i]>k)
			ans[i-k]=a[rk[i]].first;
	}
	int pos=1;
	for(int i=1;i<=n;++i)
	{
		if(tot[a[i].second]<=k)
		{
			while(pos<=n && ans[pos])
				++pos;
			ans[pos]=a[i].first;
		}
	}
	for(int i=1;i<=n;++i)
		printf("%d\n",ans[i]);
	return 0;
}

$Fiend$

  • 看到 排列,逆序对 ,考虑构造矩阵,观察其行列式.
  • 构造一个矩阵 $A_{i,j}=[L_i\le j\le R_i]$ ,考虑它的行列式定义:

$$
|A|=\sum_{p\in S_n} sgn(p) \prod_{i=1}^k A_{i,p_i}
$$

  • 对于一种排列 $p$ ,若存在 $L_i\leq p_i\le R_i$ 不成立,则 $A_{i,p_i}=0$ ,对于求和的贡献就是 $0$ .
  • 否则,若逆序对数为偶数,贡献为 $1$ ,逆序对数为奇数,贡献为 $-1$ ,于是只需要判断 $|A|$ 的符号.
  • 直接高斯消元是 $O(n^3)$ 的,可以获得 $70$ 分.由于构造的这个矩阵比较特殊,尝试手动消元.
  • 每一行的 $1$ 都是一段区间,尝试在消元时保持每一行的 $1$ 仍然是一段区间.从小到大枚举 $x$ ,找出所有 $L_i=x$ 的行,找出其中 $R_k$ 最小的那一行 $k$ ,用第 $k$ 行去消其他的 $L_i=x$ 的行.
  • 这些行被消过之后,其中的 $1$ 仍是一段区间,只是左端点变为了 $R_{k+1}$ .维护 $n$ 个集合, $i$ 号集合内存储左端点 $=i$ 的元素,每个元素记录它的行号,右端点.
  • 从小到大枚举 $x$ ,将 $x$ 号集合的元素,除了 $R_k$ ,都放入 $R_{k+1}$ 号集合.用线段树合并实现.

考试情况:构造矩阵的时候不知道怎么就错了,于是感觉不可做,此题爆零.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
typedef pair<int,int> pii;
#define mp make_pair
struct node
{
	int val,pos,h;
	int ls,rs;
	node(int Val=0,int Pos=0)
	{
		ls=rs=h=0;
		val=Val;
		pos=Pos;
	}
}Tree[MAXN<<2];
int merge(int a,int b)
{
	if(!a || !b)
		return a+b;
	if(Tree[a].val>Tree[b].val)
		swap(a,b);
	Tree[a].rs=merge(Tree[a].rs,b);
	if(Tree[Tree[a].ls].h<Tree[Tree[a].rs].h)
		swap(Tree[a].ls,Tree[a].rs);
	Tree[a].h=Tree[Tree[a].rs].h+1;
	return a;
}
int n,rt[MAXN],id[MAXN],tmp[MAXN];
int Calc_Det()
{
	int prod=1;
	for(int i=1;i<=n;++i)
	{
		if(!rt[i])
			return 0;
		node cur=Tree[rt[i]];
		rt[i]=merge(Tree[rt[i]].ls,Tree[rt[i]].rs);
		if(rt[i] && Tree[rt[i]].val==cur.val)
			return 0;
		if(id[cur.pos]!=i)
		{
			prod*=-1;
			int x=tmp[i];
			swap(tmp[id[cur.pos]],tmp[i]);
			swap(id[cur.pos],id[x]);
		}
		if(cur.val<n)
			rt[cur.val+1]=merge(rt[cur.val+1],rt[i]);
	}
	return prod;
}
void solve()
{
	n=read();
	for(int i=1;i<=n;++i)
		rt[i]=0;
	for(int i=1;i<=n;++i)
	{
		int L=read(),R=read();
		Tree[i]=node(R,i);
		id[i]=tmp[i]=i;
		rt[L]=merge(rt[L],i);
	}
	int ans=Calc_Det();
	if(ans<0)
		puts("F");
	else if(ans==0)
		puts("D");
	else
		puts("Y");
}
int main()
{
	freopen("fiend.in","r",stdin);
	freopen("fiend.out","w",stdout);
	int T=read();
	while(T--)
		solve();
	return 0;
}

$Flair$

  • 分成两部分做,记恰好选 $i$ 道菜的概率为 $A_i$ ,浪费掉的钱为 $B_i$ ,答案为 $\sum_{i=0}^n A_i\cdot B_i$.
  • 答案扩大 $100^n$ 倍,所以 $A_i=p^i\cdot (100-p)^{n-i}\cdot {n\choose i}$ .考虑如何计算 $B_i$ .
  • 若将 $c_i$ 从小到大排序,在模 $c_1$ 意义下对金额跑最短路,显然长度不会超过 $c_1$ ,而每一步的权值不超过 $c_2$ ,所以浪费金额在 $c_1\cdot c_2$ 内, $B_i$ 就会以 $c_1$ 为周期循环.
  • 记 $len=c_1\cdot c_2,per=c_1$ .需要计算出 $A_0,A_1,\dots,A_{len-1}$ 与 $D_j=\sum_{i\ge len,i\ mod\ per=j} A_i$ .
  • 于是答案就为 $\sum_{i=0}^{len-1} A_i\cdot B_i+\sum_{j=0}^{per-1} \lceil \frac {n-len+1-j} {per} \rceil \cdot B_j\cdot D_j$ .
  • $D$ 就是多项式 $(px+1-p)^n$ 长度为 $c_1$ 的循环卷积结果再减去 $<len$ 的部分.
  • 使用 $NTT$ 优化这个卷积.但 $P=10^9+7$ ,所以还要用 $MTT$ .(好毒啊)

考试情况:推出了 $B_i$ 的循环性质,但没有联想到循环卷积,于是只得了 $10$ 分暴力分.