20191022考试总结

20191022考试总结

九月 05, 2021

Xorarray

Description

xor——异或，和 and 与or 一样，是一种重要的逻辑运算，他的运算规律是 0 xor 0 = 0，1 xor 1 = 0，1 xor 0 = 1，0 xor 1 = 1

两个整数之间的异或是将两个整数转化成二进制，对他们的每一位分别进行 xor 操作，例：6(110) xor 13(1101) = 11(1011)

现在我们要介绍一种新的操作——数组异或，将两个相同大小（假设都为n）的数组A、B异或成一个新数组C，则新数组必满足:
$$
C[k]=\sum_i^{k}\sum_j^{k}\ A[i]\bigoplus B[i]
$$

现在给你数组大小n，和两个数组A,B

求他们的异或数组C

由于最终答案可能过大，你需要对C的每个元素对$1e9+7$取模

Input

一共3行。

第一行一个正整数N。

接下来两行每行N个正整数，表示数组A、B。

Output

一共1行，N个正整数，表示数组C。

Analysis

我，我mod少打了一个0，直接就爆0了,$qwq$,太惨了。

这一道题目的核心在于，因为对于每一个$C[k]$的值，考虑将所有的$A[i]$,$B[i]$中每一位中的0的个数,1的个数计算出来，每一位A的0的个数和B的1的个数，B的0的个数和A的1的个数相乘，然后加起来，这样就可以得到这一位上面异或所产生的总的1的个数是多少，而这里面的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
#include<bits/stdc++.h>
using namespace std;

#define LL long long

const int maxn=100005;
const LL mod=1000000007;
LL A[maxn],B[maxn],C[maxn],N;
LL cntA[40][2],cntB[40][2];
 
template<typename t>inline void read(t &x);
void solve(); 

int main(){
	freopen("xorarray.in","r",stdin);
	freopen("xorarray.out","w",stdout);
	read(N);
	solve();
	fclose(stdin);
	fclose(stdout);
	return 0;
}

template<typename t>inline void read(t &x){
	x=0;int sign=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')sign=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
	x*=sign;
}

void solve(){
	for(int i=1;i<=N;i++)read(A[i]);
	for(int i=1;i<=N;i++)read(B[i]);
	for(int i=1;i<=N;i++){
		LL now;
		for(int j=0;j<=31;j++){
			cntA[j][(A[i]>>j)&1]++;
			cntB[j][(B[i]>>j)&1]++;
			now=(cntA[j][0]*cntB[j][1]+cntB[j][0]*cntA[j][1])%mod;
			(now<<=j)%=mod;
			(C[i]+=now)%=mod;
		}
		cout<<C[i]<<" ";
	}
}

Road

Description

给出一个 N 个点的有向图，每个点的出度恰好为一。

现在希望给这 N 条边重定向，求图中不出现环的方案数（对$1e9$+7取模）。

Input

第一行一个正整数 N。

第二行 N 个正整数 $X_i$，表示存在一条有向边 i 指向 $X_i$。

Output

一行，一个整数 Ans，表示定向后不出现环的方案数。

Analysis

这一道题目，思路其实很简单，首先这个原图里面肯定是存在环的，如果说要让这个环不再是环的话，那么只需要让环里面任意条边反向就可以了，但是不可以全部反向或不反向。考虑强连通分量缩点来得到每一个环的点的个数是多少(以下记作size)

  • 若是缩点之后，$size>1$,那么让这里面的边反过来的方案数就有
    $$
    \C_{size}^1+\C_{size}^2+……+\C_{size}^{size-2}+\C_{size}^{size-1}
    $$

根据所学过的排列组合的知识，可以化简为$2^{size}-2$

  • 若是缩点之后，$size=1$,那么这一条边反不反向都是可以的，直接乘个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
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
#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define maxn 100005

const int mod=(int)1e9+7;
int N,tot=0,dfst=0,CntBlocks=0;
int head[maxn],to[maxn<<1],nxt[maxn<<1];
int low[maxn],dfn[maxn],Belong[maxn];
int stk[maxn],Blocksize[maxn];

void add(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
void tarjan(int u); 
LL qkpow(LL p); 

int main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	scanf("%d",&N);int t;
	for(int i=1;i<=N;i++)scanf("%d",&t),add(i,t);
	for(int i=1;i<=N;i++)if(!dfn[i])tarjan(i);
	LL ans=1;
	for(int i=1;i<=CntBlocks;i++){
		if(Blocksize[i]==1){
			(ans*=2)%=mod;
		}
		else{
			LL t=qkpow(Blocksize[i]);
			ans=(ans*t)%mod;
		}
	}
	cout<<ans;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

void tarjan(int u){
	stk[++stk[0]]=u;
	low[u]=dfn[u]=++dfst;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!Belong[v])
			low[u]=min(low[u],dfn[v]);
	} 
	if(low[u]==dfn[u]){
		CntBlocks++;
		while(stk[stk[0]]!=u){
			Belong[stk[stk[0]]]=CntBlocks;
			Blocksize[CntBlocks]++;
			stk[0]--;
		}
		Belong[u]=CntBlocks;
		Blocksize[CntBlocks]++;
		stk[0]--;
	}
}

LL qkpow(LL p){
	LL res=1;
	LL now=2;
	while(p){
		if(p&1)res=(res*now)%mod;
		(now*=now)%=mod;
		p>>=1;
	}
	return res-2;
}

Detective

Description

小W最近沉迷一个侦探游戏，在这个游戏中会不断出现命案，而小W作为主角，需要不断地收集各种关键证据，只有当所有的关键证据都被找到，你才能驳倒所有人错误的判断，找出真正的凶手。

一共有N个关键证据以及M条信息，每条信息如下所示 : 如果你已经掌握了证据 i ，那么你可以通过 k 个时间的搜索和推理得到证据 j ，同样的，如果你掌握了证据 j 你也可以通过 k 个时间得到证据 j 。

游戏开始时玩家通过初步观察现场已经得到了证据1，于此同时，每个玩家在游戏开始阶段时都能获得一个特殊技能来加快游戏进度，增加趣味性。小 W 选了一个他以前从来没用过的技能 : 好运。这是一个被动技能，系统会在游戏开始时选定一对证据（a，b）当小W发现其中一个证据的时候，他会很好运地立即获得另外一个证据（不计入时间）。

但是这个技能是完全随机的，小W完全不知道进入游戏后系统会挑选哪一对证据，他希望你能帮助他算出他花在本轮游戏上的时间的期望值，这样他心里能有点B数。

提供的信息保证 : i不会等于j，每个k值都互不相同，N个证据都能被得到。

Input

一共M+1行。

第一行两个正整数N,M，表示证据数量和信息数量。

接下来M行，每行三个数字i,j,k表示一个信息

Output

一共1行，1个整数（期望值是实数，但这里请直接保留0位小数输出）

Analysis

​ 如果说没有这个讨厌的被动技能的话，那么也就不会有这该死的期望了，那么也就是一个最小生成树就好了。

​ 但这是不可能的，这辈子都不可能的。

​ 首先来想一想，找到所有的证据之后，形成的那一张图，应当是一棵树，没有错吧，这一个神奇的被动技能，能都把其中一条边替换为0，这样的话通过枚举点对，我们就可以很轻松的得到错误的解法了

​ 换一个思路，考虑在$Kruscal$制造这一棵树的时候来进行统计，每当我们选择一条边的时候，那么它所连接的两棵子树内所有的边，是不是都比它小，那么此时替换它为0的话，无疑就会使最划算的，也就是符合要求的。此时替换会减少的值为这一条边的权值乘以旁边的两棵子树的大小再来除以选择它的概率。那么答案就等于
$$
Ans=W-\sum\frac{2dsize(u)size(v)}{N(N-1)}
$$
其中W是最小生成树的值，d是选择的边的权值，size(u),size(v)是选择的时候两棵子树的大小

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
#include<bits/stdc++.h>
using namespace std;

#define maxn 20005
#define db double

int N,M;
int fa[maxn],size[maxn];
struct edge{
	int u;
	int v;
	int d;
	
	bool operator <(const edge &cmp)const{
		return d<cmp.d; 
	}
}E[maxn*5];

void Kruscal();
int Seek(int x);
void Union(int x,int y); 

int main(){
	freopen("detective.in","r",stdin);
	freopen("detective.out","w",stdout);
	ios::sync_with_stdio(false); 
	cin>>N>>M; 
	for(int i=1;i<=M;i++){
		int u,v,d;cin>>u>>v>>d;
		E[i]=(edge){u,v,d};
	}
	sort(E+1,E+1+M);
	Kruscal();
	fclose(stdin);
	fclose(stdout);
	return 0;
} 

int Seek(int x){
	if(x!=fa[x])return fa[x]=Seek(fa[x]);
	return fa[x];
}

void Union(int x,int y){
	fa[x]=y;
	size[y]=size[y]+size[x];
}

void Kruscal(){
	for(int i=1;i<=N;i++)fa[i]=i,size[i]=1;
	int cnt=0;
	db off=0;
	long long ans=0;
	for(int i=1;i<=M;i++){
		int u=E[i].u;
		int v=E[i].v;
		int d=E[i].d;
		int fu=Seek(u);
		int fv=Seek(v);
		if(fu!=fv){
			cnt++;
			ans+=d;
			off+=((2*(double)d*(double)size[fu]*(double)size[fv])/(double)(N*(N-1)+0.0));
			Union(fu,fv); 
		} 
		if(cnt==N-1)break;
	}
	printf("%.2lf",ans-off);
}
  1. 1. Xorarray
    1. 1.1. Description
    2. 1.2. Input
    3. 1.3. Output
    4. 1.4. Analysis
  2. 2. Road
    1. 2.1. Description
    2. 2.2. Input
    3. 2.3. Output
    4. 2.4. Analysis
  3. 3. Detective
    1. 3.1. Description
    2. 3.2. Input
    3. 3.3. Output
    4. 3.4. Analysis