T20200825

Posted on Edited on In Word count in article: 1.1k Reading time ≈ 4 mins.
大东辰的测试

T1 运动(move)

给你两个字符串，其中第二个字符串为环状字符串，问将第二个字符串转几次（初始状态就是\(0\)次）可以使\(A, B\)串有最大匹配

30分做法

暴力。。。

100分做法

\(KMP\)求\(A\)串在\(B\)串中的最大匹配，就是个\(O(n)\)的了

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

using namespace std;

const int Maxn = 2e6 + 10;
char A[Maxn], B[Maxn];
int N, Fail[Maxn], Len, Pos;

int main()
{
	scanf ("%d", &N);
	scanf ("%s %s", A + 1, B + 1);
	for (int i = 2; i <= N; ++i)
	{
		int j = Fail[i - 1];
		while (j && A[j + 1] != A[i]) j = Fail[j];
		if (A[j + 1] == A[i]) Fail[i] = j + 1;
	}
	copy (B + 1, B + N + 1, B + N + 1);
	N <<= 1;
	for (int i(1), j(0); i <= N; ++i)
	{
		while (j && A[j + 1] != B[i]) j = Fail[j];
		if (A[j + 1] == B[i]) ++j;
        //j表示当前匹配长度
		if (j > Len) Pos = i - j + 1, Len = j;//Pos就是当前匹配的起点
	}
	printf ("%d\n", Pos - 1);//就完了
}

T2 烹饪(cook)

给你一串数字\(1\sim n\), 然后有\(m\)个条件形如\(a, b\)表示\(a\)在\(b\)前出现

求问满足这\(m\)个条件且小的数字尽量靠前

暴力挂了，直接上100分做法

100分做法

倒叙、反向建边的拓扑

我们然大的数尽可能靠后，这是为啥呢

自己造几组数据，你就会发现这貌似是正确的？

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

using namespace std;

const int Maxn = 1e5 + 10;
int T, N, M, Cur, Tot, X, Y;
int D[Maxn], Ans[Maxn];
int Head[Maxn], E[Maxn], Next[Maxn];
priority_queue <int> Q;

inline int Read()
{
	int X(0);
	char O(getchar());
	while (O < '0' || O > '9') O = getchar();
	for (; O >= '0' && O <= '9'; O = getchar()) X =(X << 1) + (X << 3) + (O ^ 48);
	return X;
}

inline void AddEge(int U, int V)
{
	Next[++Cur] = Head[U];
	Head[U] = Cur;
	E[Cur] = V;
}

int main()
{
	scanf ("%d", &T);
	while (T--)
	{
		scanf ("%d %d", &N, &M);
		Cur = Tot = 0;
		memset (Head, 0, sizeof(Head));
		memset (D, 0, sizeof(D));
		while (M--)
		{
			scanf ("%d %d", &X, &Y);
			AddEge(Y, X);
			D[X]++;
		}
		for (int i = 1; i <= N; ++i) if (!D[i]) Q.push(i);
		while (!Q.empty())
		{
			int X = Q.top();
			Q.pop();
			Ans[++Tot] = X;
			for (int i = Head[X]; i; i = Next[i])
			{
				D[E[i]]--;
				if (!D[E[i]]) Q.push(E[i]);
			}
		}
		if (Tot == N) 
		{
			for (int i = N; i; --i) printf ("%d ", Ans[i]);
			puts("");
		}
		else puts("impossible");
	}
}

T3 方块(block)

鸽了鸽了，不会做。。。

先贴个\(std\)，会者自会

这不是我写的

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
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#define Hash(a,b,c) Ha[a][b][c]
using namespace std;
typedef long long LL;
const int N=105,mod=1e9+7;
LL n;
int t=0,a[N],Min[1<<12],ID[1<<12],Ha[5][5][5];
struct Mat{
    int v[N][N];
    Mat(){}
    Mat(int x){
        memset(v,0,sizeof v);
        for (int i=1;i<=t;i++)
            v[i][i]=x;
    }
}M(0);
Mat operator * (Mat A,Mat B){
    Mat C(0);
    for (int i=1;i<=t;i++)
        for (int j=1;j<=t;j++)
            for (int k=1;k<=t;k++)
                C.v[i][j]=(1LL*A.v[i][k]*B.v[k][j]+C.v[i][j])%mod;
    return C;
}
Mat Pow(Mat x,LL y){
    Mat ans(1);
    for (;y;y>>=1,x=x*x)
        if (y&1LL)
            ans=ans*x;
    return ans;
}
void SwapD(int &v,int i,int j){
    if (((v>>i)^(v>>j))&1)
        v^=(1<<i)^(1<<j);
}
int checkWB(int s){
    int ans=0;
    for (int i=1;i<=2;i++)
        for (int j=1;j<=2;j++)
            for (int k=1;k<=3;k++)
                if (s>>Hash(i,j,k)&1)
                    if ((i+j+k)&1)
                        ans++;
                    else
                        ans--;
    return ans==0;
}
int calc(int s){
    int res=s;
    for (int t=0;t<4;t++){
        int v=s;
        if (t&1)
            for (int j=1;j<=2;j++)
                for (int k=1;k<=3;k++)
                    SwapD(v,Hash(1,j,k),Hash(2,j,k));
        if (t>>1)
            for (int i=1;i<=2;i++)
                for (int j=1;j<=2;j++)
                    SwapD(v,Hash(i,j,1),Hash(i,j,3));
        for (int d=0;d<4;d++,res=min(res,v))
            for (int i=1;i<=3;i++){
                SwapD(v,Hash(1,1,i),Hash(1,2,i));
                SwapD(v,Hash(1,2,i),Hash(2,2,i));
                SwapD(v,Hash(2,2,i),Hash(2,1,i));
            }
    }
    return res;
}
int dx[6]={ 0, 0, 0, 0, 1,-1},_x[6];
int dy[6]={ 0, 0, 1,-1, 0, 0},_y[6];
int dz[6]={ 1,-1, 0, 0, 0, 0},_z[6];
void GetXYZ(){
    int cnt=0;
    for (int i=1;i<=2;i++)
        for (int j=1;j<=2;j++)
            for (int k=1;k<=3;k++)
                if ((i+j+k)&1)
                    cnt++,_x[cnt]=i,_y[cnt]=j,_z[cnt]=k;
}
void GetM(int S,int v,int t){
    if (t>6){
        M.v[S][ID[Min[v]]]++;
        return;
    }
    GetM(S,v,t+1);
    int x=_x[t],y=_y[t],z=_z[t],xx,yy,zz;
    if (v>>Hash(x,y,z)&1)
        return;
    for (int i=0;i<6;i++){
        xx=x+dx[i],yy=y+dy[i],zz=z+dz[i];
        if ((1<=xx&&xx<=2&&1<=yy&&yy<=2&&1<=zz&&zz<=3)&&(~v>>Hash(xx,yy,zz)&1))
            GetM(S,v^(1<<Hash(x,y,z))^(1<<Hash(xx,yy,zz)),t+1);
    }
}
int main(){
	freopen("block.in","r",stdin),freopen("block.out","w",stdout);
    int sz=1<<12;
    for (int i=1;i<=2;i++)
        for (int j=1;j<=2;j++)
            for (int k=1;k<=3;k++)
                Ha[i][j][k]=(i-1)*6+(j-1)*3+k-1;
    for (int i=0;i<sz;i++)
        if (checkWB(i))
            if ((Min[i]=calc(i))==i)
                a[++t]=i,ID[i]=t;
    GetXYZ();
    for (int i=1;i<=t;i++)
        GetM(i,a[i]^(sz-1),1);
    scanf("%lld",&n);
    M=Pow(M,n);
    printf("%d",M.v[ID[Min[sz-1]]][ID[Min[sz-1]]]);
    return 0;
}