Codeforces Round #768 (Div. 1)（A-C)

Problem - 1630A - Codeforces

AC代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define lowbit(x) ((x) & -(x))
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector vi;
typedef vector vll;
typedef vector vc;
template T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template T lcm(T a, T b) { return a / gcd(a, b) * b; }
template
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template 
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}

const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
void solve() {
	int n, k;
	cin >> n >> k;
	if (k == 0) {
		for (int i = 0; i < n / 2; i++) {
			cout << i << " " << n - i - 1 << endl;
		}
	}
	else if (k < n - 1) {
		cout << k << " " << n - 1 << endl;
		cout << n - 1 - k << " " << 0 << endl;
		for (int i = 1; i < n / 2; i++) {
			if (i != k && i != n - k - 1) {
				cout << i << " " << n - i - 1 << endl;
			}
		}
	}
	else if (n == 4) {
		cout << -1 << endl;
	}
	else {
		cout << n - 2 << " " << n - 1 << endl;
		cout << 1 << " " << 3 << endl;
		cout << n - 4 << " " << 0 << endl;
		for (int i = 2; i < n / 2; i++) {
			if (i != 3) {
				cout << i << " " << n - i - 1 << endl;
			}
		}
	}
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}

Problem - 1630B - Codeforces

AC代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define lowbit(x) ((x) & -(x))
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector vi;
typedef vector vll;
typedef vector vc;
typedef long long ll;
template T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template T lcm(T a, T b) { return a / gcd(a, b) * b; }
template
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template 
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}
//计算几何
//向量
//struct Point {
//	double x, y;
//	Point operator - (Point a) {//向量加法
//		return { x - a.x,y - a.y };
//	}
//	Point operator + (Point a) {//向量减法
//		return { x + a.x,y + a.y };
//	}
//	double operator * (Point a) {//点乘
//		return x * a.x + y * a.y;
//	}
//	double operator % (Point a) {//叉乘
//		return x * a.y - y * a.x;
//	}
//	bool operator == (Point a) {//两点是否重合
//		return !sgn(x - a.x) && !sgn(y - a.y);
//	}
//	long double len() {//返回向量的模
//		return hypot(x, y);
//	}
//	Point rot(long double arg) {//向量旋转
//		long double Cos = cos(arg), Sin = sin(arg);
//		return { x * Cos - y * Sin,x * Sin + y * Cos };
//	}
//};
//直线 or 射线
//struct Line {
//	Line() {}
//	Line (Point s,Point e): s(s),e(s){}
//	Point s, e;
//};

void solve() {
	int n, k;
	cin >> n >> k;
	vector a(n);
	for (int j = 0; j < n; j++) {
		cin >> a[j];
		a[j]--;
	}
	vector cnt(n, 0);
	for (int j = 0; j < n; j++) {
		cnt[a[j]]++;
	}
	int x = 0, y = n;
	int R = 0;
	int sum = 0;
	for (int L = 0; L < n; L++) {
		while (R < n && sum - (n - sum) < k) {
			sum += cnt[R];
			R++;
		}
		if (sum - (n - sum) >= k) {
			if (y - x > R - L) {
				x = L;
				y = R;
			}
		}
		sum -= cnt[L];
	}
	vector S(n + 1, 0);
	for (int j = 0; j < n; j++) {
		S[j + 1] = S[j];
		if (x <= a[j] && a[j] < y) {
			S[j + 1]++;
		}
		else {
			S[j + 1]--;
		}
	}
	vector p(k + 1, -1);
	for (int j = 0; j <= n; j++) {
		if (0 <= S[j] && S[j] <= k) {
			if (p[S[j]] == -1) {
				p[S[j]] = j;
			}
		}
	}
	p[k] = n;
	cout << x + 1 << ' ' << y << "n";
	for (int j = 0; j < k; j++) {
		cout << p[j] + 1 << ' ' << p[j + 1] << "n";
	}
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}

Problem - 1630C - Codeforces

用普通数组能过，用vector过不了，很怪

AC代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl 'n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector vi;
typedef vector vll;
typedef vector vc;
typedef long long ll;
template T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template T lcm(T a, T b) { return a / gcd(a, b) * b; }
template
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template 
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}
int a[200010], pos[200010], dp[200010];
void solve() {
	int n;
	cin >> n;
	memset(dp, 0x3f, sizeof(dp));
	// vector a(200010);
	// vector pos(200010);
	// vector dp(200010, 0x3f);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pos[a[i]] = i;
	}
	dp[0] = 0;
	int cur = pos[a[1]];
	for (int i = 1; i <= n; i++) {
		dp[i] = min(dp[i - 1] + 1, dp[i]);
		cur = max(cur, pos[a[i]]);
		dp[cur] = min(dp[i] + 1, dp[cur]);
	}
	cout << n - dp[n] << endl;
    return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	// cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}

Codeforces Round #768 (Div. 1)（A-C)

C/C++/C#相关栏目本月热门文章