竞赛地址

知乎版本

A. 小Why的方阵

#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<deque> 
#include<queue>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define ll long long
#define inf 2000000009
#define debugging 0
const int maxn = 200010;
const int mod = 1e9+7;

int n, m, k;
int a[2][2];

int p[maxn];
int g[maxn], l[maxn];
int g2[maxn], l2[maxn];


void solve() {
//	scanf("%d%d%d%d", &a[])
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j) {
			scanf("%d", &a[i][j]);
		}
	}
	bool ok = (a[0][0] == a[1][1]) | (a[0][1] == a[1][0]);
	printf("%s\n", ok ? "YES" : "NO");
} 
void debug() {
	
}
int main() {
	int t = 1, cas = 1;
//	scanf("%d", &t);
	while (t--) {
//		debug();
		if(debugging) printf("case :%d\n", cas++); // debug
		solve();
	}
}

B. 小Why的循环置换

实际上就是n-m,形成大小为sz的环,需要sz-1次swap。

所以有m个环,n个数,需要的swap为n-m。

#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<deque> 
#include<queue>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define ll long long
#define inf 2000000009
#define debugging 0
const int maxn = 200010;
const int mod = 1e9+7;

int n, m, k;
int a[2][2];

int p[maxn];
int g[maxn], l[maxn];
int g2[maxn], l2[maxn];


void solve() {
	scanf("%d%d", &n, &m);
	printf("%d\n", n - m);
} 
void debug() {
	
}
int main() {
	int t = 1, cas = 1;
//	scanf("%d", &t);
	while (t--) {
//		debug();
		if(debugging) printf("case :%d\n", cas++); // debug
		solve();
	}
}

C. 小Why的商品归位

模拟,计算这个过程中购物车需要屯放的最大商品数量,除以k即可(向上取整)

可以用优先队列,维护在购物车中的商品的目标货架位置。

#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<deque> 
#include<queue>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define ll long long
#define inf 2000000009
#define debugging 0
const int maxn = 200010;
const int mod = 1e9+7;

int n, m, k;
int x, y;

int p[maxn];
int g[maxn], l[maxn];
int g2[maxn], l2[maxn];


void solve() {
	scanf("%d%d%d", &n, &m, &k);
	vector<pair<int, int> > vp;
	for (int i = 0; i < m; ++i) {
		scanf("%d%d", &x, &y);
		vp.push_back({x, y});
	}
	sort(vp.begin(), vp.end());
	int mx = 0;
	priority_queue<int, vector<int>, greater<int> > q;
	for (int i = 1, j = 0; i <= n; ++i) {
		while (!q.empty() && q.top() <= i) {
			if (debugging) {
				printf("[%d]\n", q.top());
			}
			q.pop();
		}
		while (j < m && vp[j].first <= i) {
			q.push(vp[j].second);
			++j;
		}
		mx = max(mx, (int)q.size());
	}
	printf("%d\n", (mx + k - 1) / k);

} 
void debug() {
	
}
int main() {
	int t = 1, cas = 1;
//	scanf("%d", &t);
	while (t--) {
//		debug();
		if(debugging) printf("case :%d\n", cas++); // debug
		solve();
	}
}