清華データ構造(上)PA 1&PA 2

範囲のクエリー
清華OJはstlを使ってはいけません.まず、快速列を書いて配列を並べ替えます.そして二分割して<=yのランクの最大の数、もう二分割>=xのランクの最小の数を出します.

#include 
using namespace std;
const int N = 5*1e5+10;
int a[N], m, n;
int l, r, mid, x, y, rt;

void quick_sort(int l, int r){
     
	if(l >= r) return;
	int i = l-1, j = r+1, x = a[l+r>>1];
	while(i < j){
     
		while(a[++i] < x);
		while(a[--j] > x);
		if(i < j) swap(a[i], a[j]);
	}
	quick_sort(l, j), quick_sort(j+1, r);
}

int main(){
     
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i ++){
     
		scanf("%d", &a[i]);
	}
	quick_sort(0, n-1);
	while(m --){
     
		scanf("%d %d", &x, &y);
		l = 0, r = n-1;
		while(l < r){
     
			mid = l + r + 1>> 1;
			if(a[mid] <= y) l = mid;
			else r = mid-1;
		}
		if(a[r] <= y) rt = r;
		else {
     
			puts("0");
			continue;
		}
		
		l = 0, r = rt;
		while(l < r){
     
			mid = l + r >> 1;
			if(a[mid] >= x) r = mid;
			else l = mid + 1;
		}
		if(a[l] >= x) printf("%d
", rt-l+1);
		else puts("0");
	}
	return 0;
} 

エマ
ベクトルシミュレーションもできます.この問題はみんなに双方向表を実現させたいです.

#include 
#include 
const int N = 2e4+10;
int n;
char str[N];
char tmp[N];
 
char* zuma_delete(char *ss, int pos){
     
	int len = strlen(ss);
	int front, back;
	front = back = pos;
	char c = ss[pos];
	int count = 1;
 
	while (--front >= 0 && ss[front] == c) count++;
	while (++back < len && ss[back] == c) count++;
		
	if (count >= 3){
     
		strcpy(tmp, ss + back);
		strcpy(ss + front + 1, tmp);
		return zuma_delete(ss, front);
	}
	else return ss;
}

void insert(int pos, char c){
     
	strcpy(tmp, str + pos);
	str[pos] = c;
	strcpy(str + pos + 1, tmp);
}
 
int main(){
     	
	fgets(str, N, stdin);
	str[strlen(str)-1] = '\0';
	scanf("%d", &n);
 
	while (n--){
     
		int pos;
		char c;
 
		scanf("%d %c", &pos, &c);
		insert(pos, c);
		
		char *p = zuma_delete(str, pos);
		if (strlen(p) == 0) puts("-");
		else printf("%s
", p);
	}

	return 0;
}

灯台
並べ替えは逆順で計算されます.

#include
#include
#include
using namespace std;
const int N = 4e6+10;

int n, x, y;
typedef long long LL;
LL ans;

struct Node{
     
	int x, y;
}alls[N], tmp[N];

void quick_sort(int l, int r){
     
	if(l >= r) return ;
	int i = l-1, j = r+1, p = alls[l+r>>1].x;
	while(i < j){
     
		while(alls[++ i].x < p) ;
		while(alls[-- j].x > p) ;
		if(i < j) swap(alls[i], alls[j]);
	}
	quick_sort(l, j), quick_sort(j+1, r);
}

void merge_sort(int l, int r){
     
	if(l >= r) return ;
	int mid = l + r >> 1;
	merge_sort(l, mid), merge_sort(mid+1, r);
	int i = l, j = mid+1, k = l;
	while(i <= mid && j <= r){
     
		if(alls[i].y < alls[j].y) ans += r-j+1, tmp[k++].y = alls[i++].y;
		else tmp[k++].y = alls[j++].y;
	}
	while(i <= mid) tmp[k++].y = alls[i++].y;
	while(j <= r) tmp[k++].y = alls[j++].y;
	for(int i = l; i <= r; i ++) alls[i].y = tmp[i].y;
//	for(int i = l; i <= r; i ++) {
     
//		alls[i].y = tmp[i].y;
//		printf("%d ", alls[i].y);
//	}
//	puts("");
}

int main(){
     
	scanf("%d", &n);
	for(int i = 0; i < n; i ++)
		scanf("%d %d", &alls[i].x, &alls[i].y);
	quick_sort(0, n-1);
	//for(int i = 0; i < n; i ++) printf("%d %d
", alls[i].x, alls[i].y); 
	//puts("");
	merge_sort(0, n-1);
	//for(int i = 0; i < n; i ++) printf("%d ", alls[i].y); 
	//puts("");
	printf("%lld", ans);
	return 0;
}

列車の配車
一つのシーケンスがスタック混洗であるかどうかを判断します.

#include
const int N = 1600005;
int a[N];

int main(){
     
	int m, n;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	int stk[m], tt = -1, j = 1;
	for(int i = 1; i <= n; i ++){
     
		stk[++ tt] = i;
		if(tt >= m) break;
		while(tt >= 0 && stk[tt] == a[j]) -- tt, j ++; 
	}
	if(tt > 0) puts("No");
	else{
     
		tt = -1, j = 1;
		for(int i = 1; i <= n; i ++){
     
			stk[++ tt] = i;
			puts("push");
			while(tt >= 0 && stk[tt] == a[j]) {
     
				-- tt, j ++; 
				puts("pop");
			}
		}
	} 
	return 0;
}

真二叉樹の再構成
前の順序と後の順序は真の二叉の木を唯一確定することができます.

#include 
using namespace std;

const int N = 4e6 + 5;
int pre[N], post[N], in[N];
int pos[N], n;

struct TreeNode{
     
	int val;
	TreeNode* left, *right;
	TreeNode(int v): val(v), left(nullptr), right(nullptr){
     }
};


TreeNode* dfs(int l1, int r1, int l2, int r2){
     
	if(l1 > r1) return NULL;
	auto root = new TreeNode(pre[l1]);
	if(l1 == r1) return root;
	int k = pos[pre[l1+1]];
	root->left = dfs(l1+1, l1+1+k-l2, l2, k);
	root->right = dfs(l1+2+k-l2, r1, k+1, r2-1);
	return root;
}

void inorder(TreeNode* root){
     
	if(!root) return ;
	inorder(root->left);
	printf("%d ", root->val);
	inorder(root->right);
}

int main(){
     
	scanf("%d", &n);
	for(int i = 0; i < n; i ++)
		scanf("%d", &pre[i]);
	for(int i = 0; i < n; i ++)
		scanf("%d", &post[i]), pos[post[i]] = i;

	auto root = dfs(0, n-1, 0, n-1);
	inorder(root);
	return 0;
}

旅行商
位相の順序によって、方向図を遍歴します.頂点が一つのチームに入る時、必ずこの頂点に到達できるすべてのパスを通って、中から一番長いのを選びます.

#include 
#include 
const int N = 1e6+5;
int h[N], e[N], ne[N], idx;
int d[N], num[N];
int q[N], hh, tt;
int x, y, n, m;

void add(int x, int y){
     
	e[idx] = y;
	ne[idx] = h[x];
	h[x] = idx ++;
	d[y] ++;
}

int topsort(){
     
	for(int i = 1; i <= n; i ++)
		if(!d[i]) q[tt++] = i, num[i] = 1;
	while(hh < tt){
     
		int t = q[hh++];
		for(int i = h[t]; i != -1; i = ne[i]){
     
			int j = e[i];
			num[j] = num[j] > num[t]+1 ? num[j] : num[t] + 1;
			if(-- d[j] == 0) q[tt++] = j;
		}
	}
}

int main(){
     
	memset(h, -1, sizeof h);
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i ++){
     
		scanf("%d %d", &x, &y);
		add(x, y);
	}
	topsort();
	
	int ans = 0;
	for(int i = 1; i <= n; i ++)
		ans = ans > num[i] ? ans : num[i];
	printf("%d", ans);
	return 0;	
}