2018牛客多校赛第一场

D

题意

给两张简单无向图,点数都是n,G1有m1条边,G2有m2条边, 问G2有多少个子图和G1同构.

$1 \leq n \leq 8$

分析

判断同构的话可以通过枚举点的映射关系,然后判断是否可行. 因为n只有8,所以可以枚举全排列.

然后对于一些自同构的图要进行一些处理(因为会多算), 另一种方法是对选取的边进行哈希,放到一个set里面,最后set的大小就是答案.

代码

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
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 10;
pii G[maxn][maxn];
int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int n, m1, m2;
while (cin >> n >> m1 >> m2) {
set<int> SET;
vector<int> maps(n);
for (int i = 0; i < n; i++) maps[i] = i;
clr(G, 0);
vector<pii> edges(m1);
for (int i = 0, u, v; i < m1; i++) {
cin >> u >> v;
u--,v--;
edges[i] = {u,v};
}
for (int i = 0, u, v; i < m2; i++) {
cin >> u >> v;
u--,v--;
G[u][v] = G[v][u] = {1,i};
}
do {
int hash = 0,u,v;
bool flag = true;
for(auto &e:edges){
u = maps[e.first];
v = maps[e.second];
if(G[u][v].first == 0){
flag = false;
break;
}
int i = G[u][v].second;
hash |= (1 << i);
}
if(!flag) continue;
SET.insert(hash);
} while (next_permutation(maps.begin(), maps.end()));
cout << SET.size() << endl;
}
}

E

题意

给一个长度为n的数列,问去掉m个数之后,不同的序列有多少个?

$1 \leq n \leq 1e5, 1 \leq a_i \leq k, 1 \leq k \leq 10, 1 \leq m \leq 10$

分析

网上看了一圈…大家都只贴了个代码,几个有文字的也只是讲了讲做题时的心路历程..这让我们小白如何是好??

其实看到这题有三个限制,大致就是一个三维的dp,一算$n \times a_i \times m$差不多够复杂度…

$dp[n][i][j]$表示前n个数里删掉i个,剩下的序列里最后一个数是j的种类数。

考虑第i个数删还是不删

不删:$dp[n][i][j] = \sum_{t = 1}^{k} dp[n-1][i][t]$

删:$dp[n][i+1][j] = dp[n-1][i][j]$

要注意的是当$a[n] == a[n-1]$时,这是删或不删其实都是一样的,所以只要算其中一种情况即可。

代码里为什么j从0开始,其实j为0的意思就表示序列为空。

如果理解有误还请大佬指正, 如果有别的做法欢迎一起探讨。

代码

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
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int a[maxn];
ll dp[2][20][20];
int n, m, k;

int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
while (~scanf("%d%d%d", &n, &m, &k)) {
for (int i = 1; i <= n; i++) scanf("%d", a + i);
clr(dp, 0);
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
int u = i & 1;
int v = u ^ 1;
clr(dp[u], 0);
for (int j = 0; j <= m; j++) {
for (int t = 0; t <= k; t++) {
if (t != a[i]) (dp[u][j + 1][t] += dp[v][j][t]) %= mod;
(dp[u][j][a[i]] += dp[v][j][t]) %= mod;
}
}
}
ll ans = 0;
int u = n & 1;
for (int i = 1; i <= k; i++) (ans += dp[u][m][i]) %= mod;
printf("%lld\n", ans);
}
}

J

题意

长度为n的序列,Q个询问(l,r),每次询问$[1,l]\cup [r,n]$ 中有多少不同的数字

$1 \leq n,Q,a_i \leq 1e5$

分析

做法一

将区间再复制一份放到尾部,这样就变成了查询$[r,n+l]$中有多少个不同的数字

然后离线树状数组.

可以发现,对于$[1,n]$的一个区间,只要查询的区间是$[i,n], i\in [1,n]$,那么它就有一个”前缀的性质”.

举例说明, 对于区间$[1,2,2,3,5]$来说,只需要记录每个数字最后一次出现的位置即可,若$a[k]$最后一次出现的位置
是k,那么就在k位置加一. 上述区间得到的结果是$[1,0,1,1,1]$. 那么对于查询$[i,n]$来说,只要用1的总数减去前
i-1个位置中1的个数即可. 当然如果查询的区间右断点不是$n$,那么这个做法不可行.

接下来,我们把查询离线,按右端点从小到大排序,用树状数组来维护即可. 时间复杂度$O(nlog(n))$

做法二

将区间再复制一份放到尾部,这样就变成了查询$[r,n+l]$中有多少个不同的数字

然后主席树,第i个版本维护前i个数中,每个数最后一次出现的位置.(比如某个数最后一次出现的位置是k,那么k位置的value++,这个数上一次最后出现的位置要value–)

这样我再查询区间$[l,r]$有多少不同的数时,只要查询第r个版本时$[l,r]$的和,就是答案.

但是…无情的T了…多交几次也不管用了…可能是写的丑ba

做法三

1e5的话就莫队瞎搞搞… 如果超时的话多交几次也许就过了

代码

做法一

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
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 2e5 + 5;
int a[maxn], last[maxn], first[maxn], bit[maxn];
struct Q {
int l, r, id, ans;
};
Q q[maxn];

inline int lowb(int x) { return x & (-x); }
void update(int p, int x, int n) {
while (p <= n) {
bit[p] += x;
p += lowb(p);
}
}
int query(int p) {
int ret = 0;
while (p > 0) {
ret += bit[p];
p -= lowb(p);
}
return ret;
}
int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int n, m;
while (~scanf("%d%d", &n, &m)) {
for (int i = 1; i <= n; i++) scanf("%d", a + i), a[i + n] = a[i];
n <<= 1;
for (int i = 0; i < m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].l += (n >> 1);
swap(q[i].l, q[i].r);
q[i].id = i;
}
sort(q, q + m, [](const Q& A, const Q& B) { return A.r < B.r; });
clr(last, -1);
clr(bit, 0);
for (int i = 0, k = 1; i < m; i++) {
int l = q[i].l;
int r = q[i].r;
while (k <= r) {
if (last[a[k]] != -1) update(last[a[k]], -1, n);
update(k, 1, n);
last[a[k]] = k;
k++;
}
q[i].ans = query(r) - query(l - 1);
}
sort(q, q + m, [](const Q& A, const Q& B) { return A.id < B.id; });
for (int i = 0; i < m; i++) printf("%d\n", q[i].ans);
}
}

做法三

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
//ybmj
// 如果T了就多交几次
#include<bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e5+5;
int S;
int a[maxn],cnt[maxn];
struct P{
int l,r,id,ans;
bool operator < (const P&A) const{
if(l / S == A.l / S) return r > A.r;
return l / S < A.l / S;
}
};
P b[maxn];

int main(){
// /*
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int n,m;
while(~scanf("%d%d",&n,&m)){
S = sqrt(n); // 如果T了就改几次
clr(cnt,0);
for(int i=0;i<n;i++) {
scanf("%d",a+i);
}
for(int i=0;i<m;i++) scanf("%d%d",&b[i].l,&b[i].r), b[i].id = i;
sort(b,b+m);
int ans = 0;
int l = -1 ,r = n;
for(int i=0;i<m;i++){
int L = b[i].l - 1;
int R = b[i].r - 1;
while(l < L){
l++;
ans += cnt[a[l]] == 0;
cnt[a[l]]++;
}
while(l > L){
cnt[a[l]]--;
ans -= cnt[a[l]] == 0;
l--;
}
while(r < R){
cnt[a[r]]--;
ans -= cnt[a[r]] == 0;
r++;
}
while(r > R){
r--;
ans += cnt[a[r]] == 0;
cnt[a[r]]++;
}
b[i].ans = ans;
}
sort(b,b+m,[](const P&A, const P&B){return A.id < B.id;});
for(int i=0;i<m;i++) printf("%d\n",b[i].ans);
}
}
Thank you for your support!