2021csp 赛前第八次集训 - 其它算法

• 1 − > 2 1 -> 2 1−>2
  2 − > 6 2 -> 6 2−>6
  …
  n − > ( 2 n − 1 ) ∗ 2 = 2 n + 1 − 2 n -> (2^n-1)*2 = 2^{n+1}-2 n−>(2n−1)∗2=2n+1−2
• n < = 200 ， 答 案 的 最 大 值 是 2 201 − 2 = 2 ∗ 102 4 20 − 2 ， 约 等 于 2 ∗ 1 0 60 − 2 ， 是 一 个 61 位 数 n <= 200，答案的最大值是2^{201}-2 = 2 * 1024^{20} - 2， 约等于2 * 10^{60} - 2，是一个61位数 n<=200，答案的最大值是2201−2=2∗102420−2，约等于2∗1060−2，是一个61位数
• 实 际 上 ， 2 的 次 幂 的 个 位 数 一 定 > = 2 ， 可 以 直 接 用 个 位 数 减 2 实际上，2的次幂的个位数一定>=2，可以直接用个位数减2 实际上，2的次幂的个位数一定>=2，可以直接用个位数减2

#include 
using namespace std;

int n, t, a[100] = {0, 1};

int main() {
//	freopen("hanoi.in", "r", stdin);
//	freopen("hanoi.out", "w", stdout);
	cin >> n;
	
	//t表示进位 
	for (int i = 1; i <= n + 1; i ++) {
		t = 0;			
		for (int j = 1; j <= 61; j ++) {
			t += a[j] * 2;
			a[j] = t % 10;
			t /= 10;
		}
	}
	
	//t表示借位 
	t = 2;
	for (int i = 1; i <= 61; i ++) {
		t = a[i] - t;
		if (t < 0) t = 1, a[i] = t + 10;
		else {
			a[i] = t;
			break;
		}
	}
	
	//去掉前导0 
	for (int i = 61; i >= 1; i --) {
		if (a[i] != 0) {
			t = i;
			break;
		}
	}
	for (int i = t; i >= 1; i --) cout << a[i];

	return 0;
}

• 如 果 1 0 ( k − 1 ) < 2 p < 1 0 k , 则 2 p − 1 是 一 个 k 位 数 如果10^{(k-1)} < 2^p < 10^k, 则2^p-1是一个k位数 如果10(k−1)<2p<10k,则2p−1是一个k位数
• p ∗ l o g 10 ( 2 ) < k < p ∗ l o g 10 ( 2 ) + 1 p*log10(2) < k < p * log10(2) + 1 p∗log10(2)
• 用 暴 力 方 法 ， 时 间 复 杂 度 O ( 500 ∗ P ) ， 超 时 用暴力方法，时间复杂度O(500*P)，超时 用暴力方法，时间复杂度O(500∗P)，超时

#include 
using namespace std;

int p, k, ans[510] = {1}, len = 1;

int main() {
//	freopen("mason.in", "r", stdin);
//	freopen("mason.out", "w", stdout);

	cin >> p;
	k = p * log10(2) + 1;
	cout << k << endl;
	
	for (int i = 1; i <= p; i ++) {
		int t = 0;
		for (int j = 0; j < 500; j ++) {
			t += ans[j] * 2;
			ans[j] = t % 10;
			t = t / 10;
		}
	}

	ans[0] -= 1;	
	for (int i = 499; i >= 0; i --) {
		cout << ans[i];
		if (i % 50 == 0) cout << endl;
	}
	
	return 0;
}

• 用 快 速 幂 算 法 ， 时 间 复 杂 度 O ( 50 0 2 ∗ l o g P ) 用快速幂算法，时间复杂度O(500^2*logP) 用快速幂算法，时间复杂度O(5002∗logP)

#include 
using namespace std;

const int N = 510;
int p, k;
int base[N], ans[N], tmp[N];

//a * b -> c
void mul(int a[], int b[], int c[]) {
	memset(tmp, 0, sizeof(tmp));
	
	for (int i = 0; i < 500; i ++) {
		for (int j = 0; j < 500; j ++) {
			if (i + j < 500) {
				tmp[i + j] += a[i] * b[j];
			}
		}
	}

	int t = 0;
	for (int i = 0; i < 500; i ++) {
		t += tmp[i];
		c[i] = t % 10;
		t = t / 10;
	}
}

int main() {
//	freopen("mason.in", "r", stdin);
//	freopen("mason.out", "w", stdout);

	cin >> p;
	k = p * log10(2) + 1;
	cout << k << endl;

	ans[0] = 1;
	base[0] = 2;
	while (p) {
		if (p & 1) mul(ans, base, ans);
		mul(base, base, base);  
		p >>= 1;
	}

	ans[0] -= 1;
	for (int i = 499; i >= 0; i --) {
		cout << ans[i];
		if (i % 50 == 0) cout << endl;
	}
	
	return 0;
}

#include 
using namespace std;

const int N = 5e4 + 10;
int len, n, m; 
int d[N];

//返回当最短跳跃距离是x时，应该移走的岩石数量 
int check(int x) {
	int res = 0, pos = 0;		//起点 
	for (int i = 1; i <= n; i ++) {
		if (d[i] - pos < x) res ++;
		else pos = d[i];
	}
	return res;
}

int main() {
//	freopen("stone.in", "r", stdin);
//	freopen("stone.out", "w", stdout);

	scanf("%d%d%d", &len, &n, &m);
	for (int i = 1; i <= n; i ++) scanf("%d", &d[i]);
	d[++ n] = len;
	
	int l = 0, r = len, ans;
	while (l <= r) {
		int mid = l + r >> 1;
		if (check(mid) <= m) {
			ans = mid;
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	printf("%dn", ans);

	return 0;
}

#include 
using namespace std;

const int N = 30;
int m, n, k, t, cnt;

struct node{
    int x, y, num;
};
bool operator < (node x, node y) {
    return x.num < y.num;
}
priority_queue , less > q;

int main() {
//	freopen("mason.in", "r", stdin);
//	freopen("mason.out", "w", stdout);

    cin >> m >> n >> k;
    for (int i = 1; i <= m; i ++) {
        for (int j = 1; j <= n; j ++) {
            int p;
            cin >> p;
            node t = {i, j, p};          
            q.push(t);                                      //优先队列堆顶的花生数量最多
        }
    }

    node pre, now;
    for (int i = 1; ; i ++) {
        now = q.top();
        if (i == 1) pre = {0, now.y, 0};                    //从第0行第now.y列出发 

        t += abs(now.x - pre.x) + abs(now.y - pre.y) + 1;   //曼哈顿距离 + 采摘时间 
        if (t + now.x <= k) cnt += now.num;                 //如果来得及回去就采 
        else break;                                         //否则就回去 

        pre = now;
        q.pop();

        if (q.empty()) break;                               //采完了就回去 
    }
    cout << cnt << endl;

    return 0;
}

#include 
#include 
#include 
using namespace std;    

const int N = 1e5 + 10;
int n, s[N], a[N], t[N], h[N];          //路程，疲劳值，total, 往右找 t 值最高的人家的编号

priority_queue < pair > q;    //first：疲劳值，second：i 

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &s[i]);
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        t[i] = a[i] + 2 * s[i];
    }

    int k = n;
    for (int i = n - 1; i >= 0; i --) {
        h[i] = k;                       //第 i 户人家右侧 t 值最高的人家的编号是 h[i] 
        if (t[i] > t[k]) k = i;
    }

    int ans = 0;                        //已经推销了x-1户人家，总疲劳值为 ans
    int lst = 0;                        //已经推销过的人家中最远的一家    
    int l, r;
    for (int x = 1; x <= n; x ++) {
        if (q.size()) l = q.top().second;           //第 x 户人家左侧未推销的人家中疲劳值最大的人家的编号 
        r = h[lst];

        if (q.size() && a[l] < a[r] + 2 * (s[r] - s[lst]) || !q.size()) {
            ans += a[r] + 2 * (s[r] - s[lst]);      //去编号为 r 的人家推销 
            for (int i = lst + 1; i < r; i ++) {    //将左侧的人家加入优先队列 
                q.push({a[i], i});                  
            } 
            lst = r;
        }
        else {                                      //去编号为 l 的人家推销 
            ans += a[l];
            q.pop();
        }
        printf("%dn", ans);
    }

    return 0;
}

• 枚举，70分

#include 
#include 
#include 	
using namespace std;

const int N = 1e5 + 10, M = 1e5 + 10;
int n, m, num[N];
vector  col[M];	//有m种颜色，第 i种颜色的数量为 col[i].size() 

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++) scanf("%d", &num[i]);
	for (int i = 1; i <= n; i ++) {
		int c;
		scanf("%d", &c);		//某种颜色
		col[c].push_back(i);	//将每个格子的编号存储到对应颜色的数组里 
	}

	//编号之和 * 数字之和有可能大于 MAX_INT 
	long long ans = 0;
	for (int i = 1; i <= m; i ++) {					//枚举第 i 种颜色 
		for (int j = 0; j < col[i].size(); j ++ ) {			//枚举编号为 x的格子
			for (int k = j + 1; k < col[i].size(); k ++) {	//枚举编号为 y的格子
				int x = col[i][j];
		 		int z = col[i][k];
				if (x % 2 == z % 2) {
					ans += (long long)(x + z) * (num[x] + num[z]);	
					ans %= 10007;
				}
			}
		}
	}
	printf("%lldn", ans);
	
	return 0;
}

• 枚举，60分

#include 
#include 
#include 
using namespace std;

const int N = 15010, M = 40010;
int n, m;
int x[M], ans[M][5];

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i ++) {
		int a;
		scanf("%d", &x[i]);
	}

	for (int a = 1; a <= m; a ++) {
		for (int b = 1; b <= m; b ++) {
			if (x[b] <= x[a]) continue;
			for (int c = 1; c <= m; c ++) {
				if (x[c] <= x[b]) continue;
				if ((x[b] - x[a]) % 2 == 1) continue;
				if ( 3 * (x[b] - x[a]) >= (x[c] - x[b]) ) continue;
				for (int d = 1; d <= m; d ++) {
					if (x[b] - x[a] == 2 * (x[d] - x[c]) ) {
						ans[a][1] ++;
						ans[b][2] ++;
						ans[c][3] ++;
						ans[d][4] ++;
					}
				}
			}
		}
	}

	for (int i = 1; i <= m; i ++) {
		for (int j = 1; j <= 4; j ++) {
			printf("%d ", ans[i][j]);
		}
		printf("n");
	}
	
	return 0;
}