T20200831

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

T1 教师节的问候

那么就是说，我们有一个矩阵 \[ \begin{vmatrix} 0&a_1+a_2&a_1+a_3&\cdots&a_1+a_n \\a_2+a_1&0&a_2+a_3&\cdots&a_2+a_n \\a_3+a_1&a_3+a_2&0&\cdots&a_3+a_n \\\vdots&\vdots&\vdots&\ddots&\vdots \\a_n+a_1&a_n+a_2&a_n+a_3&\cdots&0 \end{vmatrix} \] 康康最前面两行，我们发现从第三项开始\(a_1-a_2=(a_1+a_3)-(a_2+a_3)\)

那么就有了\(a_1+a_2=x\)和\(a_1-a_2=y\)

那么\(a_1\)和\(a_2\)就都可以解出来了

那么所有的元素都可以解出来了

但是要注意的是，当n = 2时可以乱搞的

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1005;
int N, S[Maxn][Maxn], A[Maxn];

int main()
{
	scanf ("%d", &N);
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			scanf("%d", S[i] + j), S[i][0] += S[i][j];
	if (N == 2) return printf ("2 %d", S[1][2] - 2), 0;
	A[1] = (S[1][2] + (S[1][0] - S[2][0]) / (N - 2)) / 2;
	for (int i = 2; i <= N; ++i) A[i] = S[i][i - 1] - A[i - 1];
	for (int i = 1; i <= N; ++i) printf ("%d ", A[i]);
}

T2 追逐闹剧

这个就是正反一边最短路，还只能用\(\text{SPFA}\)

对于加油点扩展的话，离开加油点时，我们就可以把他的\(\text{dis}\)设为\(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
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
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e5 + 5;
int N, M, C, P, U, V, L;
int Head[Maxn], Next[Maxn], E[Maxn], W[Maxn], Cur;
int Bead[Maxn], Bext[Maxn], B[Maxn];
int Dist[Maxn], Bist[Maxn], Ans(-1);
bool Vis[Maxn], Plus[Maxn];

inline void AddEdge(int U, int V, int L)
{
	Next[++Cur] = Head[U], Head[U] = Cur;
	E[Cur] = V, W[Cur] = L;
	
	Bext[Cur] = Bead[V], Bead[V] = Cur;
	B[Cur] = U;
}

inline void SPFA(int S)
{
	memset (Dist, 0x3f, sizeof Dist);
	memset (Vis, 0, sizeof Vis);
	Dist[S] = 0;
	queue <int> Q;
	Q.push(S);
	while (!Q.empty())
	{
		int Now = Q.front();
		Vis[Now] = 0;
		Q.pop();
		if (Plus[Now]) Dist[Now] = 0;
		for (int i = Head[Now]; i; i = Next[i])
		{
			if (Dist[E[i]] <= Dist[Now] + W[i]) continue;
			if (Dist[Now] + W[i] > C) continue;
			Dist[E[i]] = Dist[Now] + W[i];
			if (!Vis[E[i]]) Q.push(E[i]), Vis[E[i]] = 1;
		}
	}
}

inline void BSPFA(int S)
{
	memset (Bist, 0x3f, sizeof Bist);
	memset (Vis, 0, sizeof Vis);
	Bist[S] = 0;
	queue <int> Q;
	Q.push(S);
	while (!Q.empty())
	{
		int Now = Q.front();
		Vis[Now] = 0;
		Q.pop();
		if (Plus[Now]) Bist[Now] = 0;
		for (int i = Bead[Now]; i; i = Bext[i])
		{
			if (Bist[B[i]] <= Bist[Now] + W[i]) continue;
			if (Bist[Now] + W[i] > C) continue;
			Bist[B[i]] = Bist[Now] + W[i];
			if (!Vis[B[i]]) Q.push(B[i]), Vis[B[i]] = 1;
		}
	}
}

int main()
{
	scanf ("%d %d %d", &N, &M, &C);
	while (M--)
	{
		scanf ("%d %d %d", &U, &V, &L);
		AddEdge(U, V, L);
	}	
	scanf ("%d", &P);
	while (P--)
	{
		scanf ("%d", &U);
		Plus[U] = 1;
	}
	scanf ("%d", &P);
	SPFA(1), BSPFA(N);
	if (Dist[N] == 0x3f3f3f3f) return puts("-1") & 0; 
	while (P--)
	{
		scanf ("%d %d", &U, &L);
		if (Plus[U]) Ans = max(Ans, C * L);
		else Ans = max(Ans, L * (C - Dist[U] - Bist[U]));
	}
	printf ("%d\n", Ans);
}

T3 chase

就是用总的减去不合法的

不合法的就是达不到\(2048\)的

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

using namespace std;

typedef long long ll;
const int Maxn = 1e5 + 10, Mod = 998244353;
int N, Temp, T[20] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
ll Fac[Maxn] = {1}, Inv[Maxn], C[Maxn] = {1}, F[Maxn], Cnt[Maxn];
bool Vis[Maxn];

inline ll Pow(ll X, int Y)
{
	ll Ans(1);
	while (Y)
	{
		if (Y & 1) Ans = Ans * X % Mod;
		X = X * X % Mod;
		Y >>= 1;
	}
	return Ans;
}

int main()
{	
	scanf ("%d", &N);
	for (int i(0); T[i]; ++i) Vis[T[i]] = 1;
	for (int i = 1; i <= 100000; ++i) Fac[i] = Fac[i - 1] * i % Mod;
	Inv[100000] = Pow(Fac[100000], Mod - 2);
	for (int i = 99999; i >= 0; --i) Inv[i] = Inv[i + 1] * (i + 1) % Mod;
	for (int i = 1; i <= N; ++i) 
	{
		scanf ("%d", &Temp);
		if (!Vis[Temp]) Temp = 0;
		Cnt[Temp]++;
	}
	F[0] = 1;
	for (int i = 2047; i >= 1; --i)
		if (Cnt[i])
		{
			int j = Cnt[i];
			if (2048 / i < j) j = 2048 / i;
			for (; j >= 0; --j) C[j] = Fac[Cnt[i]] * Inv[Cnt[i] - j] % Mod * Inv[j] % Mod;
			for (j = 2047; j >= 0; --j)
				if (F[j])
				{
					for (int k = 1; k <= Cnt[i]; ++k)
					{
						int L = j + i * k;
						if (L >= 2048) break;
						F[L] = (F[L] + F[j] * C[k]) % Mod;
					}
				}
					
		}
	ll Ans = Pow(2, N);
	for (int i = 0; i < 2048; ++i) Ans = (Ans - F[i] * Pow(2, Cnt[0]) % Mod + Mod) % Mod;
	printf ("%lld\n", Ans);
}