CSP202203 全部题解

都是些简单题，但我看网上好像没有全题解，写一篇造福大学生。

签到

#include 
#include 
using namespace std;
#define N 100005
int n, k, ans = 0;
bool vis[N];
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> k;
	vis[0] = true;
	for(int i = 1; i <= k; ++i) {
		int x, y;
		cin >> x >> y;
		if(!vis[y]) ++ans;
		vis[x] = true;
	}
	cout << ans;
	return 0; 
} 

签到

#include 
#include 
using namespace std;
#define N 400005
int n, m, k; 
int d[N];
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++i) {
		int t, c;
		cin >> t >> c;
		int left = max(1, t - c + 1);
		++d[left], --d[t + 1];
	}
	for(int i = 1; i <= N - 5; ++i) d[i] += d[i - 1];
	
	for(int i = 1; i <= m; ++i) {
		int q;
		cin >> q;
		cout << d[q + k] << endl;
	}
	return 0;
}

简单模拟

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 3005
int n, m, g;

int f[N], a[N], na[N], pa[N], paa[N];
bool paar[N];

struct node {
	int cnt, l, id; 
	
	bool operator <(const node &x) const {
		return cnt == x.cnt ? id < x.id : cnt < x.cnt;
	}
}nd[N], p[N];

vector < int > seg[N], task[N];
bool used[N], tmp[N];

void nodeFrd(int na) {
	for(int i = 0; i < seg[na].size(); ++i) {
		int u = seg[na][i];
		used[u] = false;
	}
	for(int i = 1; i <= n; ++i) used[i] ^= 1;
} 

void taskFrd(int pa) {
	for(int i = 1; i <= m; ++i) {
		bool flag = false;
		for(int j = 0; j < seg[i].size(); ++j) {
			int u = seg[i][j];
			for(int k = 0; k < task[u].size(); ++k) {
				if(a[task[u][k]] == pa) flag = true;
			}
		}
		if(!flag) {
			for(int j = 0; j < seg[i].size(); ++j) used[seg[i][j]] = false;
		}
	}
}

void taskUFrd(int paa) {
	for(int i = 1; i <= n; ++i) {
		bool flag = true;
		for(int j = 0; j < task[i].size(); ++j) {
			if(a[task[i][j]] == paa) flag = false;
		} 
		if(!flag) used[i] = false;
	}
}

bool check() {
	bool res = false;
	for(int i = 1; i <= n; ++i) res |= used[i];
	return res;
}

int getans() {
	int tot = 0;
	for(int i = 1; i <= n; ++i) if(used[i]) p[++tot] = nd[i];
	sort(p + 1, p + tot + 1);
	return p[1].id;
}



int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> nd[i].l;
		nd[i].id = i;
		seg[nd[i].l].push_back(i);
	}
	cin >> g;
	for(int Tc = 1; Tc <= g; ++Tc) {
		cin >> f[Tc] >> a[Tc] >> na[Tc] >> pa[Tc] >> paa[Tc] >> paar[Tc];
		for(int i = 1; i <= f[Tc]; ++i) {
			fill(used + 1, used + n + 1, true);
			if(na[Tc]) {
				nodeFrd(na[Tc]);
			}
			if(pa[Tc]) {
				taskFrd(pa[Tc]);
			}
			if(paa[Tc]) {
				if(paar[Tc]) {
					taskUFrd(paa[Tc]);
				} else {
					for(int j = 1; j <= n; ++j) tmp[j] = used[j];
					taskUFrd(paa[Tc]);
					if(!check()) {
						for(int j = 1; j <= n; ++j) used[j] = tmp[j];
					}
				}
			}
			if(!check()) cout << 0 << ' ';
			else {
				int ans = getans();
				++nd[ans].cnt;
				task[ans].push_back(Tc);
				cout << ans << ' ';
			}
		}
		cout << endl;
	}
	return 0;
}

简单数据结构。用 set维护边即可。

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define int long long
#define N 200005
#define Prr pair < int, int >
#define fi first
#define se second
int n, m;
int k[N >> 1], l[N >> 1];
int tot1 = 0, u[N], v[N], x[N], y[N], t[N];
int tot2 = 0, num[N];
bool p[N], q[N];

vector < int > e[N], val[N], M[N];

void init() {
	cin >> n >> m;
	for(int i = 1; i <= m; ++i) {
		cin >> k[i];
		for(int j = 1; j <= k[i]; ++j) {
			++tot1;
			cin >> u[tot1] >> v[tot1] >> x[tot1] >> y[tot1];
			t[tot1] = i + y[tot1];
			e[u[tot1]].push_back(v[tot1]);
			e[v[tot1]].push_back(u[tot1]);	
			val[u[tot1]].push_back(0);
			val[v[tot1]].push_back(0);	
		}
		
		cin >> l[i];
		for(int j = 1; j <= l[i]; ++j) cin >> num[++tot2];
		
		cin >> p[i] >> q[i];
	}
}

struct cmp1 {
	bool operator ()(Prr a, Prr b) {
		return a.se == b.se ? a.fi > b.fi : a.se < b.se;
	}
};

set < Prr, cmp1 > Val[N];

int ans[N], cntP = 0, cntQ = 0;
void updPr(int u, int v, int x) {
	if(ans[u] == v && ans[v] == u) cntQ += x;
	else {
		if(ans[ans[u]] == u) cntQ += x;
		if(ans[ans[v]] == v) cntQ += x;
	}
}

void mod(int u, int v, int x) {
	int p = lower_bound(e[u].begin(), e[u].end(), v) - e[u].begin();
	Val[u].erase(make_pair(e[u][p], val[u][p]));
	val[u][p] += x;
	if(val[u][p] > 0) Val[u].insert(make_pair(e[u][p], val[u][p]));
	if(!ans[u]) --cntP;
	ans[u] = !Val[u].empty() ? (*Val[u].rbegin()).fi : 0;
	if(!ans[u]) ++cntP;
}

void upd(int tm) {
	for(int i = 0; i < M[tm].size(); ++i) {
		int p = M[tm][i];
		updPr(u[p], v[p], -1);
		mod(u[p], v[p], -x[p]);
		mod(v[p], u[p], -x[p]);
		updPr(u[p], v[p], 1);
	}
}

void solve() {
	for(int i = 1; i <= n; ++i) sort(e[i].begin(), e[i].end());
	
	cntP = n;
	int pos1 = 0, pos2 = 0;
	for(int i = 1; i <= m; ++i) {
		upd(i);
		for(int j = pos1 + 1; j <= pos1 + k[i]; ++j) {
			updPr(u[j], v[j], -1);
			mod(u[j], v[j], x[j]);
			mod(v[j], u[j], x[j]);
			updPr(u[j], v[j], 1);
			M[t[j]].push_back(j);
		}
		pos1 += k[i];
		for(int j = pos2 + 1; j <= pos2 + l[i]; ++j) {
			cout << ans[num[j]] << endl;
		}
		pos2 += l[i];
		
		if(p[i]) cout << cntP << endl;
		if(q[i]) cout << cntQ << endl;
	}
}
signed main() {
	init();
	solve();
	return 0;
}

简单博弈

#include 
#include 
using namespace std;
#define N 100005
int n, a[N];
bool k;

void subtask1() {
	int res = 0, SIZE = (n >> 1) + 1, ans = 1e9;
	for(int i = 1; i <= n; ++i) {
		res += a[i];
		if(i >= SIZE) res -= a[i - SIZE], ans = min(ans, res);
	}
	cout << ans << endl;
}

bool check(int x) {
	int res = 0, cnt = 0;
	for(int i = 1; i <= n; ++i) {
		res += a[i];
		if(res >= x) res = 0, ++cnt;
	}
	return cnt > n / 2;
}

void subtask2() {
	int l = 1, r = 1e9, mid, ans = 0;
	while(l <= r) {
		mid = l + r >> 1;
		if(check(mid)) l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	
	if((n & 1) ^ k) subtask1();
	else subtask2();

	return 0;
}