本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16840807.html

最后一次j组了，写篇题解纪念一下

A

假如 a=1a=1，ab=1a^b=1

假如 a>1a>1，可以发现当 b>30b>30 时 aba^b 必然大于 10910^9

于是我们可以暴力计算，如果计算的过程中大于 10910^9，输出 -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
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'
||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<=
'9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//#define N
//#define M
//#define mo
int n, m, i, j, k, T;
int a, b; 

signed main()
{
	freopen("pow.in", "r", stdin);
	freopen("pow.out", "w", stdout);
//	srand(time(0));
//	T=read();
//	while(T--) {
//
//	}
	a=read(); b=read(); 
	if(a==1) return printf("1"), 0; 
	for(i=k=1; i<=b; ++i)
	{
		k*=a; 
		if(k>(int)1e9) return printf("-1"), 0; 
	}
	printf("%lld\n", k); 
	return 0; 
}

B

化简式子：

ei×di=(pi−1)(qi−1)+1e_i\times d_i=(p_i-1)(q_i-1)+1

ei×di=piqi−pi−qi+2e_i\times d_i=p_iq_i-p_i-q_i+2

ei×di=ni−pi−qi+2e_i\times d_i=n_i-p_i-q_i+2

所以 p,qp,q 满足以下条件：

  1. pi+qi=ni−ei×di+2p_i+q_i=n_i-e_i\times d_i+2

  2. pi×qi=nip_i\times q_i=n_i

令

qi=m−piq_i=m-p_i，l=pi×qi=pi(m−pi)l=p_i\times q_i=p_i(m-p_i)

和一定，差小积大

image

二分 pip_i，求出当前的 ll

  • l>nl>n，缩小 pip_i
  • l<nl<n，扩大 pip_i

无解就是二分出来不满足条件

点击查看代码 
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 int long long
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'
||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<=
'9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//#define N
//#define M
//#define mo
int n, m, i, j, k, T;
int l, r, e, d, mid; 

signed main()
{
	freopen("decode.in", "r", stdin);
	freopen("decode.out", "w", stdout);
//	srand(time(0));
	T=read();
	while(T--) {
		n=read(); e=read(); d=read(); 
		m=n-e*d+2; 
//		printf("%lld\n", m); 
		if(m<=1) printf("NO\n"); 
		else
		{
			l=1; r=m/2; 
			while(l<r)
			{
				mid=(l+r+1)>>1; 
				if(mid*(m-mid)<=n) l=mid; 
				else r=mid-1; 
			}
			for(i=max(1ll, l-5); i<=min(r+5, m-1); ++i)
				if(i*(m-i)==n) {
					printf("%lld %lld\n", i, m-i); 
					break; 
				}
			if(i>min(r+5, m-1)) printf("NO\n"); 
		}
	}

	return 0;
}

C

1|0&1 ，正常顺序：1|(0&1)

怎么求表达式的值？

  1. 没有括号，没有 & 操作

0|1|1|0|1…

  1. 没有括号（顺带求一类短路）

0|1&0|1&0&1|0…

以 | 分段，分别计算每一段的值，变成第一种情况

  1. 有括号

0|(1&0|1&1)&1|

递归处理括号内的内容

求被短路:

a|b|c|d|e…

此时求二类短路

点击查看代码 
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
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'
||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<=
'9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define N 1000010
//#define M
//#define mo
struct node
{
	int x=0, a=0, b=0; 
}z[N]; 
int n, m, i, j, k, T;
int top; 
char s[N]; 

node calc(int x)
{
	int st=top, m=0; 
	node l, ans;  
	while(s[++k]!=')')
	{
		if(s[k]=='&') 
		{
			if(z[top].x==0) ++z[top].a, m=-1; 
			else m=1; 
		}
		else if(s[k]=='|') continue; 
		else
		{
			if(s[k]=='(') l=calc(k+1); 
			else l.x=s[k]-'0', l.a=l.b=0; 
			if(m==1) 
			{
				z[top].a+=l.a;  
				z[top].b+=l.b; 
				z[top].x&=l.x; 
			}
			else if(m!=-1) z[++top]=l; 
			m=0; 
		}
	}
	for(int i=st+1; i<=top; ++i)
	{
//		printf("%lld\n", z[i].a); 
		if(ans.x) ++ans.b; 
		else ans.x|=z[i].x, ans.a+=z[i].a, ans.b+=z[i].b; 
	}
	top=st; 
//	printf("%lld %lld\n", x, ans.x); 
	return ans; 
}

signed main()
{
	freopen("expr.in", "r", stdin);
	freopen("expr.out", "w", stdout);
//	srand(time(0));
//	T=read();
//	while(T--) {
//
//	}
	scanf("%s", s+1); 
	n=strlen(s+1); s[n+1]=')'; 
	node t=calc(1); 
	printf("%lld\n%lld %lld", t.x, t.a, t.b); 
	return 0;
}

D

先按 xx 坐标排序，再按 yy 坐标排序（保证无后效性）

排好后的点对 (xi,yi)(x_i,y_i) 和 (xj,yj)(x_j, y_j)，假设 i<ji<j，ii 必然不能接在 jj 后面

假如 jj 能接在 ii 后面，它们之间需要 xj−xi+yj−yi−1x_j-x_i+y_j-y_i-1 个过继点

jj 能接在 ii 后面，满足 xj≥xix_j\geq x_i 且 yj≥yiy_j\geq y_i

设 dp(u,i)dp(u,i) 代表以第 uu 个点为结尾，且用了 ii 个过继点的最长子序列

枚举上一个给定点 vv，

dp(u,i)=dp(v,i−(xu−xv+yu−yv−1))+xu−xv+yu−yvdp(u,i)=dp(v,i-(x_u-x_v+y_u-y_v-1))+x_u-x_v+y_u-y_v

最后答案：max⁡dp(u,i)+k−i\max dp(u,i)+k-i

点击查看代码 
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
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'
||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<=
'9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define N 510
#define M 110
//#define mo
struct node
{
	int x, y; 
}a[N]; 
int n, m, i, j, k, T; 
int ans, f[N][M]; 

bool cmp(node x, node y)
{
	if(x.x==y.x) return x.y<y.y; 
	return x.x<y.x; 
}

int calc(int x, int y)
{
	return abs(a[x].x-a[y].x)+abs(a[x].y-a[y].y); 
}

signed main()
{
	freopen("point.in", "r", stdin);
	freopen("point.out", "w", stdout);
//	srand(time(0));
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); ans=m+1; 
	for(i=1; i<=n; ++i) 
		a[i].x=read(), a[i].y=read(); 
	sort(a+1, a+n+1, cmp); 
	for(i=1; i<=n; ++i)
	{
		f[i][0]=1; 
		for(k=0; k<=m; ++k)
		{
			for(j=1; j<i; ++j)
				if(a[i].x>=a[j].x && a[i].y>=a[j].y)
				if(calc(i, j)-1<=k)
					f[i][k]=max(f[i][k], f[j][k-calc(i, j)+1]+calc(i, j)); 
			ans=max(ans, f[i][k]+m-k); 
		}
	}
	printf("%lld", ans); 
	return 0;
}