T20200826

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

T1 砍树(tree)

树型\(Dp\)吧，水水过

注意开\(long\;long\)

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

using namespace std;

typedef long long ll;
const int Maxn = 1e5 + 10;
ll N, X, U, V, Cur;
ll Sum[Maxn], Ans[Maxn];
int Head[Maxn], E[Maxn << 1], Next[Maxn << 1];

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

void DFS(int U, int F)
{
	Ans[U] = Sum[U];
	for (int i = Head[U]; i; i = Next[i])
	{
		if (E[i] == F) continue;
		DFS(E[i], U);
		Sum[U] += Ans[E[i]];//Sum表示以U为根的最大答案
	}
	Ans[U] = max(-X, Sum[U]);//如果-X比Sum[U]大，这个节点就可以直接砍掉了
}

int main()
{
	scanf ("%lld %lld", &N, &X);
	for (int i = 1; i <= N; ++i) scanf ("%lld", Sum + i);
	for (int i = 1; i < N; ++i)
	{
		scanf ("%lld %lld", &U, &V);
		AddEdge(U, V), AddEdge(V, U); 
	}
	DFS(1, 1);
	printf ("%lld\n", Ans[1]);
}

T2 异或(xor)

求在\(1\sim n\)范围内满足方程\(x\otimes2x=3x\)的解的个数

做法1

我们发现当\(x\;\&\;2x=0\)时，\(x\)就是方程的一个解

简言之，就是在\(x\;\&\;(x<<1)=0\)时， \(x\)就是方程的一个解

这就非常显然了吧

我们可以统计二进制下\(1\sim n\)中，任意两个\(1\)都不相邻的树的个数

用\(f(cnt,up,last)\)表示在第\(cnt\)位，是否到达峰值，上一位为\(last\)的方案数

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

using namespace std;

typedef long long ll;
ll T, N, F[70][2][2];
int Num[70];

ll DFS(int Cnt, int Up, bool Jud)
{
	if (Cnt == 0) return 1;
	if (F[Cnt][Up][Jud] != -1) return F[Cnt][Up][Jud];
	ll Ans(0), Lim;
	if (Jud) Lim = 0;
	else if (Up) Lim = Num[Cnt];
	else Lim = 1;
	for (int i = 0; i <= Lim; ++i) Ans += DFS(Cnt - 1, Up && i == Num[Cnt], i == 1);
	return F[Cnt][Up][Jud] = Ans;
}

int main()
{
	scanf ("%lld", &T);
	while (T--)
	{
		scanf ("%lld", &N);
		ll Temp = N, Cnt(0);
		while (Temp) Num[++Cnt] = Temp & 1, Temp >>= 1;
		memset(F, -1, sizeof F);
		printf ("%lld\n", DFS(Cnt, 1, 0) - 1); 
	}
}

做法2

先打个表

1
2
3
4
5
6
7
8
9
10
11
1: 1
2: 2
4: 3
8: 5
16: 8
32: 13
64: 21
128: 34
256: 55
512: 89
1024: 144

然后发先在\(2^k\)范围内的数确实挺像斐波那契数列的

那么先预处理出最高位为\(1\)的所有数的答案，然后去加上下一个\(1\)的位置的答案

如果某两个\(1\)相邻，那么先加上我们得到的答案然后\(-1\)，\(break\)掉， 就可以了

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

using namespace std;

typedef long long ll;
ll T, N, Feb[70] = {1, 2};

int main()
{
    for (int i = 2; i <= 65; ++i) Feb[i] = Feb[i - 1] + Feb[i - 2];
    scanf ("%lld", &T);
    while (T--)
    {
        ll Res(0), Cnt(0);
        scanf ("%lld", &N);
        for (int i = 60; i >= 0; --i)
            if ((N >> i) & 1)
            {
                Res += Feb[i];
                if ((N >> (i + 1)) & 1){--Res; break;}
            }
        printf ("%lld\n", Res);
    }
}

这是\(SYK\)巨佬一直在讲的，打表找规律是个好方法的体现啊

T3 等式(equ)

先给出两个式子： \[ \sum_{i=1}^na_ix_i=S\\ \sum_{i=1}^nb_ix_i=T \] 求\(\{x\}\), \(x\)为非负实数，使其在满足上述两个式子的情况下使\(\sum_{i=1}^nc_ix_i\)最大

求\(\sum_{i=1}^nc_ix_i\)， 输出五位浮点数，若无解，输出\(\text{“impossible”}\)

15分做法

那就是对\(n=1\)或者\(n=2\)的数据直接解方程

考场上的丢人代码

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

using namespace std;

int N, M, S, T;
double Ans;
int A[5], B[5], C[5];
double X[5];

bool N1()
{
	if (S * B[1] != T * A[1]) return 1;
	Ans = double(S) / double(A[1]) * double (C[1]);
	return 0;
}

bool N2()
{
	int D = A[2] * B[1], E = B[2] * A[1], F = S * B[1], G = T * A[1];
	if ((D - E == 0) && (G - G != 0)) return 1;
	X[2] = double(F - G) / double(D - E);
	X[1] = (double (S) - A[2] * X[2]) / A[1];
	Ans = C[1] * X[1] + C[2] * X[2];
	if (X[1] < 0 || X[2] < 0) return 1;
	return 0;
}

int main()
{
	scanf ("%d %d", &N, &M);
	for (int i = 1; i <= N; ++i) scanf ("%d %d %d", A + i, B + i, C + i);
	while (M--)
	{
		scanf ("%d %d", &S, &T);
		bool Flag;
		if (N == 1) Flag = N1();
		else if (N == 2) Flag = N2();
		if (Flag) puts("impossible");
		else printf ("%.5lf\n", Ans);
	}
}

30分做法

根据\(XZC\)巨佬的结论，答案只与其中最多两个\(x_i\)的值有关，那么剩下的就是一个暴力了

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

using namespace std;

const int N = 1e5+100;

const double eps = 1e-6;

#define LL int 

LL read()
{
	LL x = 0,f = 0;char ch = getchar();
	while(!isdigit(ch)) {if(ch=='-')f=1;ch = getchar();}
	while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
	return f ?-x:x;
}

struct Point
{
	LL x,y,c;
	Point() {x=0;y=0;c=0;}
	Point(int _x,int _y,int _c = 0) {x=_x;y=_y;c=_c;}
	Point operator + (const Point a)const {return Point(a.x+x,a.y+y);}
}v[N],P;

LL cross(Point a,Point b) 
{
	return a.x * b.y - a.y * b.x;
} 

LL n,m;

bool cmp(Point a,Point b) 
{
	return a.c / 1.0 * sqrt(a.x * a.x + a.y * a.y) > b.c / 1.0 * sqrt(b.x * b.x + b.y * b.y);
}

double limit1 = 1e18,limit2 = 0.0;

int main()
{

	n = read(), m = read();
	for(int i = 1;i <= n;i++) v[i].x = read(), v[i].y = read(), v[i].c = read();
	v[0].x = 0, v[0].y = 0, v[0].c = 0;
	for(int i = 1;i <= n;i++) {
		limit1 = min(limit1, atan2(v[i].y, v[i].x));
		limit2 = max(limit2, atan2(v[i].y, v[i].x));
	}	
	while(m--)
    {
		int s = read(), t = read();
		P.x = s;P.y = t;P.c = 0;
		double K = atan2(P.y,P.x);
		if(K < limit1 || K > limit2) {
			puts("impossible");
			continue;
		}
		else {
			double ans = 0.0;
			for(int i = 1; i < n; i++) {
				if(P.x * v[i].y == v[i].x * P.y){
					ans = max((double)P.x / v[i].x * v[i].c, ans);
				}
				for(int j = i + 1; j <= n; j++)
				{
					if(i == j) continue;
					double X2 = 1.0 * cross(v[i],P) / (double)cross(v[i], v[j]);
					double X1 = (1.0 * P.x - X2 * v[j].x) / v[i].x;
					if(X1 <= 0.0 || X2 <= 0.0) continue;
					ans = max(ans, X2 * v[j].c + X1 * v[i].c);
				}
			}
			printf("%.5lf\n", ans);
		}
	}
}

100分

对偶线性规划

平面半交

二分答案

鸽他！！