test20191020

发表于

闲扯

辣鸡 $std$ ，辣鸡出题人建议做掉

$T2,T3$ 的复杂度都不对， $n\log n$ 的题数据范围开了 $2\cdot10^6$ ，虽然我电脑不太好，也不至于给它开了 $O_2$ 也跑不过吧？？

题面

$ftp$

$T1$

Solution

首先明确一点，我们每一位都是必须确定的，而且找不到任何方法一次性确定两位及以上。

而确定一位是 $0$ 还是 $1$ 很简单，只需要用 $((2^n-1)\ xor\ 2^k)\&x$ 即可。

因为有 $n$ 位，所以需要 $n$ 个数。

又因为顺序可以乱，所以方案数为排列数，即 $ans=n!$ 。

由于 $n$ 的范围比较大，有 $10^9$ ，所以考虑分段打表。

每 $10^6$ 个数输出一个，每次找到最大的不大于 $n$ 的一个，直接暴力乘即可。

时间复杂度： $O(n-10^6\cdot\lfloor\frac{n}{10^6}\rfloor)$ 。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
const int mod = 1e9+7;
int n,ans,fac[]={...};// 太多了，就不写了
it mul(int x,int y){return 1ll*x*y%mod;}
int main(){
	freopen("rectify.in","r",stdin);
	freopen("rectify.out","w",stdout);
	read(n);
	int k=n/1000000;
	ans=fac[k];
	for(ri i=k*1000000+1;i<=n;++i) ans=mul(ans,i);
	print(ans);
	return 0;
}

$T2$

Solution

我们先按照 $a$ 从大到小排个序。

我们用 $|A|,|B|$ 来表示 $A,B$ 中的最大值。

考虑以 $a_i$ 作为 $|A|$ 时，显然所有的 $k\in[i+1,n]$ 都必须在 $B$ 中。

因为所求为最大值，所以 $|B|$ 至少为 $\max_{j=i+1}^n b_j$ 。

而对于 $k\in[1,i-1]$ ，它们可以任意的放入 $A,B$ 中。

因为我们要最小化 $||A|-|B||$ ，所以我们需要找到距离 $a_i$ 最近的 $b_k,k\in[1,i-1]$ 。

如果 $b_k\geq|B|$ ，那么我们可以用来更新答。

对于每一个 $i$ ，它对应的 $|B|$ 是确定的，所以我们只需要看怎么解决 $b_k$ 。

我们可以发现随着 $a_i$ 的增长， $b_k$ 也是单调不减的，所以我们直接从小往大扫即可。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
const int MAXN = 2e6+5;
int n,ans=INT_MAX,s[MAXN],sz,cnt[MAXN],now,nxt=1,now1,id[MAXN];
struct Node{
	int a,b;
	bool operator <(const Node &t) const{
		return a<t.a;
	}
}node[MAXN];
it min(int x,int y){return x<y?x:y;}
it max(int x,int y){return x>y?x:y;}
it abs(int x){return x<0?-x:x;}
it get_id(int x){return lower_bound(s+1,s+1+sz,x)-s;}
int T[MAXN];
il updata(int pos,int k){for(;pos<=sz;pos+=lowbit(pos)) T[pos]+=k;}
it query(int pos){ri res=0;for(;pos;pos-=lowbit(pos)) res+=T[pos];return res;}
int main(){
	freopen("moderate.in","r",stdin);
	freopen("moderate.out","w",stdout);
	read(n);
	for(ri i=1;i<=n;++i) read(node[i].a),read(node[i].b),s[i]=node[i].b;
	sort(node+1,node+1+n),sort(s+1,s+1+n),sz=unique(s+1,s+1+n)-s-1;
	for(ri i=1;i<=n;++i) id[i]=get_id(node[i].b),++cnt[id[i]];
	now1=sz;
	for(ri i=1;i<=n;++i){
		--cnt[id[i]];
		while(now1&&!cnt[now1]) --now1;
		ri res=INT_MAX;
		if(cnt[now1]) res=abs(node[i].a-s[now1]);
		while(now+1<=sz&&s[now+1]<=node[i].a&&query(now+1)) ++now;
		while(nxt<=sz&&s[nxt]<=node[i].a&&query(nxt)) ++nxt;
		if(s[now]>=s[now1]&&query(now)) res=min(res,abs(node[i].a-s[now]));
		if(s[nxt]>=s[now1]&&query(nxt)) res=min(res,abs(node[i].a-s[nxt]));
		updata(1,1),updata(id[i]+1,-1);
		ans=min(ans,res);
	}
	print(ans);
	return 0;
}

$T3$

看不懂

总结

属于出题人的问题。