Algorithms Weekly 10

Posted on | Post modified:

机试康复训练R1:Codeforces Round #690 (Div. 3)

A. Favorite Sequence

题解：构造后的数组其实就是把构造前的数组的奇偶分开，奇数下标在前，偶数下标在后，同时讲偶数下标reverse一下。那么我们直接逆过程即可。时间复杂度$O(n)$

代码：

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
####3 4 5 2 9 1 1
T=int(input())
for test in range(T):
    n=int(input())
    a=input().split()
    for i  in range(n):
        a[i]=int(a[i])
    odd=[]
    even=[]
    for i in range(0,(n+1)//2):
        odd.append(a[i])
    for i in range((n+1)//2,n):
        even.append(a[i])
    even.reverse()
    ans=[]
    i=0
    j=0
    while i<len(odd) and j<len(even):
        ans.append(odd[i])
        ans.append(even[j])
        i+=1
        j+=1
    while(i<len(odd)):
        ans.append(odd[i])
        i+=1
    while(j<len(even)):
        ans.append(even[j])
        j+=1
    for v in ans:
        print(v,end=" ")
    print("")

B. Last Year’s Substring

暴力枚举前后加起来共四位，看看是否能组成2020即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
T=int(input())
for test in range(T):
    n=int(input())
    s=input()
    if(len(s)<4):
        print("No")
    else:
        flag=0
        for i in range(0,5):
            j=4-i
            # print(i,j,s[0:i],s[len(s)-j:len(s)])
            if (s[0:i]+s[len(s)-j:len(s)])=="2020":
                print("YES")
                flag=1
                break
        if flag==0:
            print("NO")

C. Unique Number

二进制枚举从1-9，取满足条件的最小的即可，时间复杂度$O(2^9)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
T=int(input())
dig=[i+1 for i in range(9)]
# print(dig)
for test in range(T):
    x=int(input())
    ans=99999999999
    for i in range(0,1<<9):
        lst=[]
        for j  in range(0,9):
            if (i>>j)&1:
                lst.append(j+1)
        s=0
        for v in lst:
            s+=v
        if s==x:
            tmp=0
            for v in lst:
                tmp=tmp*10+v
            ans=min(ans,tmp)
    if ans == 99999999999:
        print(-1)
    else:
        print(ans)

D. Add to Neighbour and Remove

题目可以简化为将数组划分成若干和相等的区间，答案即为每段的长度减一求和。由于$n \leq 3000$,暴力枚举每段的大小即可。时间复杂度$O(n^2)$

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
T=int(input())
for test in range(T):
    n=int(input())
    ans=n
    x=input().split(" ")
    for i in range(n):
        x[i]=int(x[i])
    con=0
    for i in range(n):
        con+=x[i]
        now_ans=i
        nows=0
        cnt=0
        flag=1
        for j in range(i+1,n):
            if nows!=con and nows+x[j]>con:
                flag=0
                break
            if nows+x[j]<=con:
                nows+=x[j]
                cnt+=1
            if nows==con:
                now_ans+=cnt-1
                nows=0
                cnt=0
        if flag and nows==0:
            ans=min(ans,now_ans)
    print(ans)

E2. Close Tuples (hard version)

考虑将数组$a$排序，那么对于$ a_{i} $, 二分查找最远的 $a_{j}$ 使得 $a_{j}-a_{i}\leq k$ ，那么$a_{i}$的贡献即为$C(j-i,m-1)$,时间复杂度$O(nlog(n))$。 

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
/*
* @author:  codancer
* @createTime:  2021-01-02, 13:02:26
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9+7;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
#define deb(x) cerr<<#x<<" = "<<(x)<<"\n"
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll B) {
	return (ull)rng() % B;
}
const int N = 2e5+10;
ll fact[N],inv[N],factinv[N];
int a[N];
void init(){
    fact[0]=inv[1]=factinv[0]=inv[0]=fact[1]=factinv[1]=1;
    for(int i=2;i<=N;i++){
        fact[i]=(fact[i-1]%mod*i%mod)%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        factinv[i]=factinv[i-1]*inv[i]%mod;
    }
}
ll c(ll n,ll m){
    return fact[n]*factinv[m]%mod*factinv[n-m]%mod;
}
void solve(){
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	rep(i,1,n) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	ll ans=0;
	rep(i,1,n){
		int l=i;
		int r=upper_bound(a+1,a+n+1,a[i]+k)-a-1;//[l,r] is satisfied
		if(r-l>=m-1) ans+=c(r-l,m-1);
		ans%=mod;
	}
	printf("%lld\n", ans);
}
int main(){
	init();
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

F. The Treasure of The Segments

贪心的想，肯定是要找一个区间使得这个区间尽可能地和其他区间相交。枚举这个区间$[l,r]$，对于$r_{i}r$的区间，一定不和$[l,r]$相交，剩余的一定和$[l,r]$相交，二分查找计算个数，更新结果，时间复杂度$O(nlog(n))$。

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
/*
* @author:  codancer
* @createTime:  2021-01-02, 13:36:42
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9+7;
#define pb push_back
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
#define deb(x) cerr<<#x<<" = "<<(x)<<"\n"
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll B) {
	return (ull)rng() % B;
}
const int N = 2e5+100;
int l[N],r[N],n;

void solve(){
	scanf("%d",&n);
	vector<int> L,R;
	rep(i,1,n){
		scanf("%d%d",&l[i],&r[i]);
		L.pb(l[i]);
		R.pb(r[i]);
	}

	sort(L.begin(),L.end());
	sort(R.begin(),R.end());
	int ans=1e9;
	rep(i,1,n){
		int rr=lower_bound(R.begin(),R.end(),l[i])-R.begin();
		int ll=upper_bound(L.begin(),L.end(),r[i])-L.begin();
		// cout<<i<<' '<<rr<<' '<<ll<<endl;
		ans=min(ans,rr+n-ll);
	}
	printf("%d\n", ans);
}
int main(){
	int T;scanf("%d",&T);
	while(T--) solve();
	return 0;
}