《算法竞赛进阶指南》 0x08 课后习题

飞行员兄弟
直接暴力枚举 2^16…

#include <bits/stdc++.h>
using namespace std;

vector<int> yh[20];
void init() {
	for(int i = 1; i <= 16; i ++ ) {
		yh[i].push_back(i);
		int t = i;
		while(-- t > ((i - 1) / 4 )* 4) yh[i].push_back(t);
		t = i;
		while(++ t <= ((i - 1) / 4 + 1) * 4 ) yh[i].push_back(t);
		t = i;
		while( (t -= 4) >= ((i % 4) == 0? i % 4 + 1 : i % 4)) yh[i].push_back(t);
		t = i;
		while( (t += 4) <= 16) yh[i].push_back(t);
	}
}
int mp;

int main() {
	init();
	string s;
	for(int i = 1; i <= 4; i ++ ) {
		cin >> s;
		for(int j = 0; j < 4; j ++ ) {
			if(s[j] == '+') mp += (1 << ((i - 1) * 4 + j + 1)) ;
		}
	}
	for(int i = 0; i <= (1 << 17); i += 2) {
		int cd = mp;
		for(int j = 1; j <= 16 ; j ++ ) {
			if(i >> j & 1){
				for(int z = 0; z < yh[j].size(); z ++ ) {
					cd ^= (1 << yh[j][z]);
				}
			}
		}
		int flag = 0;
		for(int j = 1; j <= 16; j ++ ) {
			if((cd >> j) & 1){
				flag = 1;
				break;
			}
		}
		if(!flag) {
			int rs=0;
			for(int j = 1; j <=16; j ++ ){
				if(i >> j & 1) rs ++;
			}
			cout << rs << endl;
			for(int j = 1; j <= 16; j ++ ) {
				if((i >> j) & 1){
					cout << ((j - 1) / 4) + 1 << " " << (j % 4 == 0 ? 4 : j % 4) << endl;
				}
			}
			break;
		}
	}
	return 0;
}

占扑DIY
模拟题。。。直接膜

#include <bits/stdc++.h>
using namespace std;

deque<int> lo[20];
int up[20];

void ends() {
	int rs= 0;
	for(int i = 1; i <=12 ; i++ ){
		if(up[i] == 4) rs ++ ;
	}
	cout << rs << endl;
}

void dfs(int x, int ml) {
// cout << x << " " << ml << endl;
	if(x == 13) {
		ml--;
		if(ml == 0) {
			ends();
			return ;
		}
		int to = lo[13].front();
		up[to]++;
		lo[13].pop_front();
		dfs(to, ml);
	}else{
		int to = lo[x].back();
		up[to]++;
		lo[x].pop_back();
		dfs(to, ml);
	}
}

int main() {
	string s;
	for(int i = 1; i <= 13; i ++ ) {
		for(int k = 1; k <= 4; k ++ ) {
			cin >> s;
			int t;
			if(s[0] >= '0' && s[0] <='9') {
				t = (s[0] == '0') ? 10 : s[0] - '0';
				lo[i].push_back(t);
			} else {
				if(s[0] == 'A') t = 1;
				else if(s[0] == 'J') t = 11;
				else if(s[0] == 'Q') t = 12;
				else t = 13;
				lo[i].push_back(t);
			}
		}
	}
	dfs(13, 5);
	return 0;
}

Fractal
分形题找到下标关系直接打表

#include <bits/stdc++.h>
using namespace std;
char mp[3000][3000];

void cpy(int n,int x,int y) {
	for(int i = 1; i <= n ; i++ ) {
		for(int j = 1; j <= n ; j++ ) {
			mp[x + i][y + j] = mp[i][j];
		}
	}
}

void init() {
	for(int k = 1; k <= 7; k ++) {
		cpy(pow(3,k-1), 2*pow(3,k-1) , 0);
		cpy(pow(3,k-1), 0, 2*pow(3,k-1));
		cpy(pow(3,k-1), 2*pow(3,k-1), 2*pow(3,k-1));
		cpy(pow(3,k-1), pow(3,k-1), pow(3,k-1));
	}
}

int main() {
	for(int i = 1; i<3000;i++){
		for(int j = 1 ;j < 3000 ; j++ ){
			mp[i][j] = ' ';
		}
	}
	mp[1][1] = 'X';
	init();
	int n;
	while(cin >> n,n!=-1){
		n -- ;
		for(int i = 1; i <= pow(3,n); i ++ ) {
			for(int j = 1; j <= pow(3,n); j ++ ) {
				printf("%c",  mp[i][j]);
			}puts("");
		}
		printf("-\n");
	}
	return 0;
}

Raid
点分治最近点对

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

struct node {
	double x, y;
	int type;
	bool operator < (const node &a)const {
		return x < a.x || (x == a.x && y < a.y);
	}
} p[N], tmp[N];

double dist(node a, node b) {
	if(a.type == b.type) return 1e9;
	double dx = a.x - b.x, dy = a.y - b.y;
	return sqrt(dx * dx + dy * dy);
}

double get_ans(int l, int r) {
	if(l >= r) return 1e9;
	int mid = l + r >> 1;
	double mid_x = p[mid].x;
	double d = min(get_ans(l, mid), get_ans(mid + 1, r));
	{
		int i = l;
		int j = mid + 1;
		for(int k = l; k <= r; k ++ ) {
			if(j > r|| (i <= mid && p[i].y <= p[j].y))
				tmp[k] = p[i ++];
			else
				tmp[k] = p[j ++];
		}
		for(int k = l; k <= r; k ++ ) 
			p[k] = tmp[k];
	}
	int k = 0;
	for(int i = l; i <= r; i ++ ) {
		if(p[i].x >= mid_x - d && p[i].x <=mid_x + d)
			tmp[++ k] = p[i];
	}

	for(int i = 1; i <= k; i ++ ) {
		for(int j = i - 1; j > 0; j -- ) {
			if(tmp[i].y - tmp[j].y >= d) break;
			d = min(d, dist(tmp[i], tmp[j]));
		}
	}
	return d;
}

int main() {
	int n;
	int cas ;
	cin >> cas;
	while( cas -- ) {
		cin >> n;
		for(int i = 1; i <= n; i ++ ) {
			cin >> p[i].x >> p[i].y;
			p[i].type = 1;
		}
		for(int i = n + 1; i <= n * 2; i ++ ) {
			cin >> p[i].x >> p[i].y;
			p[i].type = 2;
		}
		sort(p + 1, p + 1 + (n << 1));
		printf("%.3lf\n",get_ans(1, (n << 1) ));
	}
	return 0;
}

防线
奇数加偶数是奇数
这样我们前缀和二分第一个奇数点就好了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5 + 10;
int n;

struct node{
    int s,e,d;
}seg[N];

ll get_sum(int x) {
    ll res = 0;
    for(int i = 1; i <= n; i++ ){
        if(seg[i].s <= x)
        res += ((min(seg[i].e,x) - seg[i].s)/seg[i].d + 1) ;
    }
    return res;
}

int main(){
    int cas ;
    cin >> cas;
    while(cas -- ) {
        scanf("%d", &n);
        int l = 0, r = 0;
        for(int i = 1; i <= n; i ++ ) {
            cin >> seg[i].s >> seg[i].e >> seg[i].d;
            r = max(r, seg[i].s);
        }
        while(l < r){
            int mid = l + r >> 1;
            if(get_sum(mid) & 1) r = mid;
            else l = mid + 1;
        }
        
        int sum = get_sum(l) - get_sum(l - 1);
        
        if(sum & 1) cout << l << ' ' << sum << endl;
        else cout << "There's no weakness." << endl;
    }
    return 0;
}

赶牛入圈
离散化后面二分 r 注意正方形r 和离散化后面数据关系

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;

struct node {
	int x, y;
} cow[maxn];

int sum[maxn][maxn];
int vec[maxn << 1];

int cnt;
int C, n;

bool chk(int len) {
	for (int x1 = 1, x2 = 1; x2 <= cnt; x2 ++ ) {
		while (vec[x2] - vec[x1] + 1> len) x1 ++ ;
		for (int y1 = 1, y2 = 1; y2 <= cnt; y2 ++ ) {
			while (vec[y2] - vec[y1]  + 1> len ) y1 ++ ;
			if (sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] >= C)
				return true;
		}
	}
	return false;
}


int getid(int x) {
	int l = 1, r = cnt;
	while(l < r) {
		int mid = l + r >> 1;
		if(vec[mid] >= x) r = mid;
		else l = mid + 1;
	}
	return l;
}

int main() {
	cin >> C >> n;
	cnt = 0;
	vec[0] = 0;
	for(int i = 1, x, y; i <= n; i ++ ) {
		cin >> x >> y;
		cow[i] = node {x, y};
		vec[++ cnt] = x;
		vec[++ cnt] = y;
	}
	sort(vec + 1, vec + 1 + cnt);
	cnt = unique(vec + 1, vec + 1 + cnt) - vec - 1;

	for(int i = 1; i <= n ; i ++ ) {
		int rx = getid(cow[i].x);
		int ry = getid(cow[i].y);
		sum [rx][ry] ++ ;
	}
	for(int i = 1; i <= cnt; i ++ ) {
		for(int j = 1; j <= cnt; j ++ ) {
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}
	int l = 1, r = 10000;
	while(l < r) {
		int mid = l + r >> 1;
		if(chk(mid)) r = mid;
		else l = mid + 1;
	}
	cout << r << endl;
	return 0;
}

环形均分纸牌

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

int a[maxn], s[maxn];

signed main() {
	int n;
	cin >> n;
	int sum =0;
	for(int i = 1; i <= n; i ++ ) {
		cin >> a[i];
		sum += a[i];
	}
	int avg = sum / n;

	for(int i = 1; i <= n; i ++ ) {
		s[i] = s[i-1]+(a[i] - avg);
	} 
	sort(s + 1,s + 1 + n);
	int mid = s[(1 + n) >> 1];

	int ans = 0;
	for(int i = 1; i <= n; i ++ ) {
		ans += abs(s[i] - mid);
	}
	cout << ans << endl;
	return 0;
}

士兵
h 每个减 i 其实减的只要连续就行目的一样为了让他们连续差一

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e4 + 5;
int l[maxn], h[maxn];

int main(){
    int n;
    cin >> n;
    for(int i = 1, x, y; i <= n; i ++ ) {
        cin >> x >> y;
        h[i] = x;
        l[i] = y;
    } 
    sort(l + 1, l + 1 + n);
    sort(h + 1, h + 1 + n);
    int midl = l[(n + 1) / 2];
    for(int i = 1; i <= n; i ++ ) h[i] -= i; // 这里主要是要变成相对位置刚好连续差1 在排序
    sort(h + 1, h + 1 + n); // zhongwei shu 
    int midh = h[1 + n >> 1];
    int ans = 0;
    for(int i = 1; i <= n ; i++){
        ans += abs(l[i] - midl);
        ans += abs(h[i] - midh);
    } 
    cout << ans << endl;
    return 0;
}

数位转换
模拟找余数和这个进制要几个不断放进去

#include <bits/stdc++.h>
using namespace std;

string s1, s2;
int a, b;
const int maxn = 1e4;
int a1[maxn], b1[maxn];

int main(){
    int cas;
    cin >> cas;
    while(cas -- ) {
        cin >> a >> b;
        cin >> s1;
        int len = s1.size();
        for(int i = 0; i < len; i ++ ) {
            if(s1[i] >= '0' && s1[i] <= '9') a1[i + 1] = s1[len - i - 1] - '0';
            else if(s1[i] >= 'A' && s1[i] <= 'Z') a1[i + 1] = s1[len - i - 1] - 'A' + 10;
            else a1[i + 1] = s1[len - i - 1] - 'a' + 36;
        }
        int k = 0;
        while(len) {
            int r = 0;
            for(int i = len; i >= 1; i -- ) {
                a1[i] += r * a;
                r = a1[i] % b;
                a1[i] = a1[i] / b;
            }
            b1[++k] = r;
            while(len > 0 && a1[len] == 0) len --;
        }
        cout << a << " " << s1 << endl << b << " ";
        for(int i = k; i > 0; i --) {
            if(b1[i] >= 0 && b1[i] <= 9)    cout << b1[i];
            else if(b1[i] >= 10 && b1[i] <= 35) cout << char(b1[i] - 10 + 'A');
            else cout << char(b1[i] - 36 + 'a');
        }cout << endl << endl;
        
    }
    return 0;
}

耍杂技的牛
邻项扰动这里是w 和 s 的和排序

#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 5;

struct node{
    int w,s;
    bool operator < (const node & a) const {
        return w + s < a.w + a.s;
    }
}a[N];

int main(){
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i ++ ) {
        cin >> a[i].w >> a[i].s;
    }
    
    
    sort(a + 1, a + 1 + n);
    int ans = -1e9,res = 0;
    for(int i = 1; i <= n; i ++ ) {
        ans = max (ans, res - a[i].s);
        res += a[i].w;
    }
    cout << ans << endl;
    return 0;
}

最大的和
如之前题到的生存周期不过这里是二维的
我们先处理竖着的前缀和之后我们找 i行到j行枚举k 找最大的last max（0， last）就可以除去前某个矩阵小于0的情况

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e2 + 5;

int s[N][N]; 

int main() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= n; j ++ ) {
			cin >> s[i][j];
			s[i][j] += s[i - 1][j]; 
		}
	}
	
	int ans = -0x3f3f3f3f;
	
	for(int i = 1; i <= n; i ++ ) {
		for(int j = i; j <= n; j ++ ) {
			int last = 0;
			for(int k = 1; k <= n; k ++ ) {
				last = max(last, 0) + s[j][k] - s[i - 1][k];
				ans = max(ans, last);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

任务待续 orz。。再想想