[CF1579]G. Minimal Coverage

[CF1579]G. Minimal Coverage

目录

• 题目
• 思路
• 代码
• 附赠其他几题的代码
  • A
  • B
  • C
  • D
  • E1
  • E2
  • F

题目

大概就是给定(n)个正整数(a_1ldots a_n),让你确定一个(b_1ldots b_n(forall iin{1,2,3,ldots n},b_iin{-1,1})),得到一个(sum),(sum_i=sum^i_{j=1}a_icdot b_i),使得(max^n_{i=1}sum_i-min^n_{j=1}sum_j)((sum)的极差)最大,求最大值.

思路

​ 设(f_{i,j})表示放了前(i)个线段,第(i)条线段的结尾处到左边界的距离为(j)时,右边界到左边界的距离为(f_{i,j}).左右边界分别指前(i)条线段曾到达的最左端和最右端,如放了([0,6],[4,6])时,左右边界分别为(0,6).

​ 考虑转移(从(i)顺推到(i+1)):

1. 线段向左放
   1. 如果超出了原来的左边界,则右边界相对左边界的距离增加(a_{i+1}-j),故:
      if(j <= a[i + 1]) f[i + 1][0] = min(f[i + 1][0] , f[i][j] + a[i + 1] - j);
   2. 否则,相对距离不变:
      else f[i + 1][j - a[i + 1]] = min(f[i + 1][j - a[i + 1]] , f[i][j]);
2. 线段向右放,很简单.
   f[i + 1][j + a[i + 1]] = min(f[i + 1][j + a[i + 1]] , max(f[i][j] , j + a[i + 1]) );

代码

#include <iostream>
#include <cstdio>
using namespace std;

template <class T>
T read() {
	T re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' ,c = getchar();
	return negt ? -re : re;
}

const int N = 10010;
const int maxA = 1010;
int n;
int a[N];
int f[N][maxA * 2];

void solve() {
	n = read<int>();
	for(int i = 1 ; i <= n ; i++)
		a[i] = read<int>();
	for(int i = 0 ; i <= n ; i++)
		for(int j = 0 ; j <= 2 * 1000 ; j++)
			f[i][j] = 0x3ffffff;
	
	f[1][a[1]] = a[1];
	for(int i = 1 ; i < n ; i++) {
		for(int j = 0 ; j <= 2 * 1000 ; j++) {
			if(j <= a[i + 1])
				f[i + 1][0] = min(f[i + 1][0] , f[i][j] + a[i + 1] - j);   
			else
				f[i + 1][j - a[i + 1]] = min(f[i + 1][j - a[i + 1]] , f[i][j]);
			
			f[i + 1][j + a[i + 1]] = min(f[i + 1][j + a[i + 1]] , max(f[i][j] , j + a[i + 1])  );
			
		}
	}
	
	int ans = 0x3ffffff;
	for(int j = 0 ; j <= 2 * 1000 ; j++)
		ans = min(ans , f[n][j]);
	printf("%d
" , ans);
}
int main() {
	int T = read<int>();
	while(T--) {
		solve();
	}
	return 0;
}

附赠其他几题的代码

A

#include <iostream>
#include <cstdio>
using namespace std;

template <class T>
T read() {
	T re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' ,c = getchar();
	return negt ? -re : re;
}

void solve() {
	char c = getchar();
	while(!(c == 'A' || c == 'B' || c == 'C'))
		c = getchar();
		
	int a = 0 , b = 0 , cc = 0;
	while(c == 'A' || c == 'B' || c == 'C') {
		
		if(c == 'A')	++a;
		else if(c == 'B')++b;
		else if(c == 'C')++cc;
		c = getchar();
	}
	puts(b == a + cc ? "YES" :"NO");
}
int main() {
	int T = read<int>();
	while(T--) {
		solve();
	}
	return 0;
}

B

#include <iostream>
#include <cstdio>
using namespace std;

template <class T>
T read() {
	T re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' ,c = getchar();
	return negt ? -re : re;
}

const int N = 1010;
int n;
int a[N];
int l[N] , r[N] , d[N];
void solve() {
	n = read<int>();
	int k = 0;
	for(int i = 0 ; i < n ; i++)
		a[i] = read<int>();
	for(int i = 0 ; i < n ; i++) {
		int id = i;
		for(int j = i + 1 ; j < n ; j++)
			if(a[j] < a[id])
				id = j;
		if(id != i) {
			++k;
			l[k] = i;
			r[k] = id;
			d[k] = id - i;
			
			int tmp = a[id];
			for(int j = id ; j > i ; j--) {
				a[j] = a[j - 1];
			}
			a[i] = tmp;
		}
	} 
	printf("%d
" , k);
	for(int i = 1 ; i <= k ; i++)
		printf("%d %d %d
" , l[i] + 1 , r[i] + 1 , d[i]);
}
int main() {
	int T = read<int>();
	while(T--) {
		solve();
	}
	return 0;
}

C

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

template <class T>
T read() {
	T re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' ,c = getchar();
	return negt ? -re : re;
}

const int N = 110;
int n , m , d;
char a[N][N];
bool tag[N][N];
bool solve() {
	memset(tag , 0 , sizeof(tag));
	for(int i = n ; i > 0 ; i--)
		for(int j = 1 ; j <= m ; j++) {
			if(a[i][j] == '*') {
				bool tmp = tag[i][j];
				bool flag = true;
//				tag[i][j] = true;
				int k = 0;
				for(; i - k >= 0 && j - k >= 0 && j + k <= m ; k++) {
					if(!(a[i - k][j - k] == '*' && a[i - k][j + k] == '*'))
						break;
				}
				if(k - 1 < d) {
					if(tmp == false)
						return false;
				} else {
					k = 0;
					for(; i - k >= 0 && j - k >= 0 && j + k <= m ; k++) {
						if(a[i - k][j - k] == '*' && a[i - k][j + k] == '*')
							tag[i - k][j - k] = tag[i - k][j + k] = 1;
						else
							break;
					}
				}
			}
		}
	return true;
}
int main() {
//	int T = read<int>();
	int T;
	T = read<int>();
	while(T--) {
		n = read<int>() , m = read<int>() , d = read<int>();
		for(int i = 1 ; i <= n ; i++)
			for(int j = 1 ; j <= m ; j++) {
				a[i][j] = getchar();
				while(a[i][j] != '.' && a[i][j] != '*')
					a[i][j] = getchar();
			}
		if(solve())
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}

D

#include <iostream>
#include <cstdio>
#include <map>
#include <queue>
using namespace std;

template <class T>
T read() {
	T re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' ,c = getchar();
	return negt ? -re : re;
}

const int N = 200010;
priority_queue<pair<int,int> > q;
vector <pair <int,int> > ans;
int n;
int a[N]; 
void solve() {
	ans.clear();
	while(q.size())
		q.pop();
	n = read<int>();
	for(int i = 1 ; i <= n ; i++) {
		a[i] = read<int>();
		if(a[i] != 0)
			q.push(make_pair(a[i] , i));
	}
	while(q.size() > 1) {
		pair<int,int> a = q.top();	q.pop();
		pair<int,int> b = q.top();	q.pop();
		while(b.first >= (q.top()).first && a.first >= (q.top()).first) {
			ans.push_back(make_pair(a.second , b.second));
			--a.first , --b.first;//最多执行sigma a_i次,不会超时
		}
		if(a.first > 0)
			q.push(a);
		if(b.first > 0)
			q.push(b);
	}
	printf("%d
" , (int)ans.size());
	for(int i = 0 ; i < (int)ans.size() ; i++)
		printf("%d %d
" , ans[i].first , ans[i].second);
}
int main() {
	int T = read<int>();
	while(T--) {
		solve();
	}
	return 0;
}

E1

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

template <class T>
T read() {
	T re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' ,c = getchar();
	return negt ? -re : re;
}

const int N = 400010;
int n;
int a[N];
int st[N * 2][30];

int query(int l , int r) {
	int k = log(r - l + 1) / log(2);
	return a[st[l][k]] < a[st[r - (1 << k) + 1][k]] ? st[l][k] : st[r - (1 << k) + 1][k];
}
void divi(int l , int r) {
	if(l == r) {
		printf("%d " , a[l]);
		return ;
	}
	int mid = query(l , r);
	printf("%d " , a[mid]);
	if(l != mid)
		divi(l , mid - 1);
	for(int i = mid + 1 ; i <= r ; i++)
		printf("%d " , a[i]);
}
void solve() {
	n = read<int>();
	for(int i = 1 ; i <= n ; i++)
		a[i] = read<int>();
	a[0] = 2147483647;

	for(int i = 1 ; i <= n ; i++)
		st[i][0] = i;
	for(int j = 1 ; (1 << j) <= n ; j++)
		for(int i = 1 ; i <= n ; i++)
			st[i][j] =
			    a[st[i][j - 1]] < a[st[i + (1 << j - 1)][j - 1]] ?
			    st[i][j-1] : st[i + (1 << j - 1)][j - 1];

	divi(1 , n);
	putchar('
');
	
	for(int i = 1 ; i <= n ; i++)
		st[i][0] = 0;
	for(int j = 1 ; (1 << j) <= n ; j++)
		for(int i = 1 ; i + (1 << j -1 ) <= n ; i++)
			st[i][j] = 0;
}
int main() {
	int T = read<int>();
	while(T--) {
		solve();
	}
	return 0;
}

E2

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 200010;

template <class T>
T read() {
	T re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' ,c = getchar();
	return negt ? -re : re;
}
void discretize(int* begin , int *end) {
	static int tmp[N];
	int n = 0;
	for(int* i = begin ; i != end ; i++)
		tmp[n++] = *i;
	sort(tmp , tmp + n);
	n = unique(tmp , tmp + n) - tmp;
	for(int* i = begin ; i != end ; i++) {
		*i = upper_bound(tmp , tmp + n , *i) - tmp;
	}
}

typedef long long lint;
int n;
int a[N];

class TreeArray {
	private :
		int siz;
		int a[N];
		int lowbit(int x) {
			return x & (-x);
		}
	public :
		void clear() {
			for(int i = 0 ; i <= siz ; i++)
				a[i] = 0;
		}
		void init(int siz_) {
			clear();
			siz = siz_;
		}
		void update(int pos , int dat) {
			for( ; pos <= siz ; pos += lowbit(pos))
				a[pos] += dat;
		}
		lint GetSum(int pos) {
			lint sum = 0;
			for( ; pos ; pos -= lowbit(pos))
				sum += a[pos];
			return sum;
		}
		lint GetSum(int l , int r) {
			return GetSum(r) - GetSum(l - 1);
		}
}tr;
void solve() {
	n = read<int>();
	for(int i = 1 ; i <= n ; i++)
		a[i] = read<int>();
	discretize(a + 1 , a + n + 1);
	
	tr.init(n);
	lint ans = 0;
	for(int i = 1 ; i <= n ; i++) {
		ans += min(tr.GetSum(1 , a[i] - 1) , tr.GetSum(a[i] + 1 , n));
		tr.update(a[i] , 1);
	}
	printf("%lld
" , ans);
}
int main() {
//	solve();
	int T = read<int>();
	while(T--) {
		solve();
	}
	return 0;
}

F

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

template <class T>
T read() {
	T re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' ,c = getchar();
	return negt ? -re : re;
}

const int N = 1000010;
int n , d;
int a[N];
int calc[N];
queue <int> q;
void solve() {
	n = read<int>() , d = read<int>();
	for(int i = 0 ; i < n ; i++)
		calc[i] = -1;
	for(int i = 0 ; i < n ; i++) {
		a[i] = read<int>();
		if(a[i] == 0)
			q.push(i) , calc[i] = 0;
	}
	while(q.size()) {
		int u = q.front();
		q.pop();
		int v = (u + d) % n;
		if(a[v] == 1)
			a[v] = 0 , calc[v] = calc[u] + 1 , q.push(v);
	}
	int maxn = 0;
	for(int i = 0 ; i < n ; i++) {
		if(calc[i] == -1) {
			puts("-1");
			return ;
		}
		if(maxn < calc[i])
			maxn = calc[i];
	}
	printf("%d
" , maxn);
}
int main() {
	int T = read<int>();
	while(T--) {
		solve();
	}
	return 0;
}