首页 > 其他分享 >集训题单

集训题单

时间：2023-10-20 17:23:10浏览次数：53

标签：fr return int double ++ ans 集训题单

P1323 删数问题

题目传送门

贪心+模拟

这个模拟的话就是前面加数的地方，本来以为到 \(3e4\) 的时候这个数很大，但是我打表打出来看了一下，发现不大，只有几万还是几十万，所以完全可以存的下的。

他要求最小的，所以用一个优先队列来维护就可以了，然后我们就求出了一列数字，然后考虑贪心维护，如果说这个数比他后面一个数更小的话，那么显然删掉他会让数更大，所以说这个时候就可以遍历几遍，然后如果这个数比他后面的数小的话就把这个数删掉，然后记录一个现在删了多少数字，到了题目要求的数量之后直接退出就可以了。

然后这里我是用 \(vector\) 来做的，也是肥肠的方便啊！

点击查看代码

int main() {
	priority_queue<int,vector<int>,greater<int> > q;
	q.push(1);
	int n = fr(), m = fr();
	for (int i = 1; i <= n; i ++) {
		auto t = q.top();
		q.pop();
		fw(t);
		q.push(t * 2 + 1);
		q.push(t * 4 + 5);
		stack<int> s;
		while (t) {
			s.push(t % 10);
			t /= 10;
		}
		while (s.size()) {
			w.push_back(s.top());
			s.pop();
		}
	}
	ch;
	while (m --) {
		auto u = w.begin();
		auto v = u;
		v ++;
		bool flag = false;
		while (v != w.end()) {
			if (*v > *u) {
				w.erase(u);
				flag = true;
				break;
			}
			v ++, u ++;
		}
		if (!flag) w.pop_back(); 
	}
	for (auto i : w) {
		fw(i);
	}
	return 0;
}

P3551 USU-Take-out

题目传送门

因为数据保证有解，所以就直接找就可以了，不需要判断有没有解。

根据题目可以知道，最后消除的肯定是一段连在一起的方块，所以说我们可以从后面的操作往前面找，这个可以用一个栈来找。

在输入的时候就把这个方块存到栈里面，并且按照栈的下标（手写栈）来记录到现在为止有多少个黑色，最后再输出的时候记得要 \(sort\) 一下，并且是从后往前输出（）。

点击查看代码

int main() {
	n = fr(), k = fr();
	scanf("%s",(c + 1));
	for (int i = 1; i <= n; i ++) {
		if (c[i] == 'c') w[i] = true;
		else w[i] = false;
		s[++ top] = i;
		cnt[top] = cnt[top - 1] + w[i];
		while (top >= k + 1 && cnt[top - k - 1] + 1 == cnt[top]) {
			int u = top - k - 1;
			++ idx;
			while (top > u) {
				ans[idx].push_back(s[top]);
				top --;
			}
			top = u;
		}
	}
	for (int i = idx; i; i --) {
		sort(ans[i].begin(),ans[i].end());
		for (auto j : ans[i]) {
			fw(j),kg;
		}
		ch;
	}
	return 0;
}

P4824 Censoring S

题目传送门

这个题目是 \(kmp\) 和栈，\(kmp\) 显然就是字符匹配用的，所以一开始先对 \(T\) 弄一遍 \(kmp\)，然后再遍历一遍 \(S\) ，因为题目中说每一次遇到就要删掉，所以当 \(T\) 在字符串 \(S\) 种匹配好了之后，就把这些弹出去，并回溯到弹完之后的匹配状态就好了。

点击查看代码

char s[N], k[N];
int w[N],h[N];
vector<int> ans;

int main() {
	scanf("%s%s", (s + 1), (k + 1));
	int len = strlen(k + 1);
	for (int i = 2, j = 0; i <= len; i ++) {
		while (j && k[i] != k[j + 1]) j = w[j];
		if (k[i] == k[j + 1]) j ++;
		w[i] = j;
	}
	stack<int> stk;
	stk.push(0);
	int leng = strlen(s + 1);
	for (int i = 1, j = 0; i <= leng; i ++) {
		while (j && s[i] != k[j + 1]) j = w[j];
		if (s[i] == k[j + 1]) j ++;
		h[i] = j;
		stk.push(i);
		if (j == len) {
			int cnt = len;
			while (cnt --) {
				stk.pop();
			}
			j = h[stk.top()];
		}
	}
	while (stk.size()) {
		ans.push_back(stk.top());
		stk.pop();
	}
	reverse(ans.begin(),ans.end());
	for (auto i : ans) {
		if (i == 0) continue;
		cout << s[i];
	}
	return 0;
}

P5835 Meetings S

题目传送门

二分

首先观察一下两头牛发生碰撞，可以发现如果两个牛相撞的话其实就是相当于两头牛交换速度，那么也就是说如果一开始 \(A\) 在 \(B\) 的左边，那么 \(A\) 不管怎么碰撞都一直保持在 \(B\) 的左边，这也就是说从一开始到结束牛的序列的顺序都是固定的。

考虑到这一点之后，就可以知道，如果说有一个牛按照初速度和初始位置到达牛棚的话，如果是到了左边的牛棚的话，那么就说明初始位置在左边的牛到了牛棚，所以就可以简便计算了。

有了这一性质之后，就可以二分时间了，因为这个时间和牛到达牛棚的重量的关系是一个单调的函数，所以说我们可以在这里求出什么时候到达牛棚的牛是总重量的一半。

求出这个时间之后，就可以进一步求相遇次数了。对于相遇次数，可以按照左右顺序遍历过去，然后把往左走到的先存到一个数组里面，然后在遍历向右走的，因为时间和速度都是已知的，所以可以找到最右边的相遇的牛，然后这其中的牛都是会相遇的，把它算到答案里面，最后输出便可以了。

点击查看代码

struct node{
	int w,x,d;
	int idx;
	bool operator < (const node t) const {
		return x < t.x;
	}
};

bool check(int tt) {
	lwl wei = 0;
	int en = n,be = 1;
	for (int i = 1; i <= n; i ++) {
		if (w[i].d == 1 && w[i].x + tt >= L) {
			wei += w[en].w;
			en --;
		} else if (w[i].d == -1 && w[i].x - tt <= 0) {
			wei += w[be].w;
			be ++;
		}
	}
	return wei * 2 >= sum;
}

int main() {
	n = fr(), L = fr();
	for (int i = 1; i <= n; i ++) {
		int a = fr(), b = fr(), c = fr();
		w[i] = {a, b, c, 0};
		sum += w[i].w;
	}
	sort(w + 1,w + 1 + n);
	int l = 0,r = L;
	int t = r;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) t = mid,r = mid - 1;
		else l = mid + 1;
	}
	int idx = 0;
	lwl ans = 0;
	for (int i = 1; i <= n; i ++) {
		if (w[i].d == -1) {
			int l = 1, r = idx;
			while (l <= r) {
				int mid = (l + r) >> 1;
				if (w[i].x - t <= h[mid] + t) r = mid - 1;
				else l = mid + 1;
			}
			ans += idx - (r + 1) + 1;
		} else h[++ idx] = w[i].x;
	}
	fw(ans);
	return 0;
}

P9209 不灭不死鸟之尾

题目传送门

这个题目就是单纯的贪心，而且很明显是每次都把车停在两边，然后每次根据输入的数据判断停在哪边就可以了，肥肠的简单啊。

点击查看代码

int n;
lwl l[N], r[N], w[N];

int main() {
	n = fr();
	lwl ans = 0;
	for (int i = 1; i <= n; i ++) w[i] = fr();
	for (int i = 1; i <= n; i ++) l[i] = fr();
	for (int i = 1; i <= n; i ++) r[i] = fr();
	for (int i = 1; i <= n; i ++) {
		ans = (ans + w[i] - max(l[i],r[i]) * (n - i));
	}
	fw(ans);
	return 0;
}

Progressions Covering

题目传送门

贪心

因为很明显，每一次加的越多越好，所以说就从后往前遍历，然后每一次都尽量给当前位加最大值直到当前位达到所需的数量，然后记录一下加到前面位的数量，然后到了前面所剩的数字比 \(k\) 小的时候就换一个数加。

点击查看代码

int n,k;
lwl w[N], h[N];

lwl get(int l,int r) {
	return h[l] - h[r + 1];
}

int main() {
	n = fr(), k = fr();
	for (int i = 1; i <= n; i ++) {
		w[i] = fr();
	}
	lwl ans = 0;
	lwl qwq = 0;
	for (int i = n; i; i --) {
		w[i] -= qwq;
		lwl a = min(k,i);
		lwl t = max(0ll,w[i] / a);
		h[i] = h[i + 1];
		if (w[i] > 0) {
			if (w[i] % a) t ++;
			ans += t;
			h[i] += t;
		}
		qwq = qwq - get(i + 1, i + k - 1) + t * (a - 1);
	}
	fw(ans);
	return 0;
}

P3253 删除物品

题目传送门

观察一下，可以发现这个栈的这个操作也就是说明该不管怎么移动，如果不考虑删除的话，把两个栈拼在一起的话两个数的位置关系是不会改变的，而且两个数中间的数也是不变的。

所以说可以用先将两个栈顶对着顶拼在一起，然后建一棵线段树，每一次查询当前位置到下一个比他小的优先级的点之间还有多少剩下的点。

这个询问和删除都可以用线段树来维护，一开始就是把每个点的全都赋值成 \(1\) ，删除的话就把那个点的权值改成 \(0\) ，查询的话就是查询这个区间的权值和，再把每一次查询的结果相加便是答案。

点击查看代码

struct node{
	int l,r;
	int w;
}tr[N << 2];

int n;
int n1[3];
int s[3][N];
pii w[N];

bool cmp(pii a,pii b) {
	if (a.fi < b.fi) return false;
	return true;
}

void push_up(int idx) {
	tr[idx].w = tr[il].w + tr[ir].w;
}

void build(int l,int r,int idx) {
	L = l, R = r;
	if (l == r) {
		if (w[l].fi != inf) tr[idx].w = 1;
		return ;
	}
	int mid = (L + R) >> 1;
	build(l,mid,il);
	build(mid + 1,r,ir);
	push_up(idx);
}

void modify(int idx,int pos,int x) {
	if (L == pos && R == pos) {
		tr[idx].w = x;
		return ;
	}
	int mid = (L + R) >> 1;
	if (mid >= pos) modify(il,pos,x);
	else modify(ir,pos,x);
	push_up(idx);
}

int query(int idx,int l,int r) {
	if (L >= l && R <= r) {
		return tr[idx].w;
	}
	int mid = (L + R) >> 1;
	int ans = 0;
	if (mid >= l) ans += query(il,l,r);
	if (mid < r) ans += query(ir,l,r);
	return ans;
}

int main() {
	n1[1] = fr(),n1[2] = fr();
	for (int i = 1; i <= 2; i ++) {
		for (int j = 1; j <= n1[i]; j ++) {
			s[i][j] = fr();
		}
	}
	int idx = 0;
	n = n1[1] + n1[2] + 1;
	for (int i = n1[2]; i; i --) {
		idx ++;
		w[idx] = {s[2][i],idx};
	}
	++ idx;
	w[idx] = {inf,idx};
	for (int i = 1; i <= n1[1]; i ++) {
		++ idx;
		w[idx] = {s[1][i],idx};
	}
	build(1,n,1);
	sort(w + 1,w + 1 + n,cmp);
	int ne = w[1].se;
	lwl ans = 0;
	for (int i = 2; i <= n; i ++) {
		modify(1,w[i].se,0);
		ans += query(1,min(ne,w[i].se),max(ne,w[i].se));
		ne = w[i].se;
	}
	fw(ans);
	return 0;
}

P3668 [USACO17OPEN] Modern A

题目传送门

一开始看题目的时候把题目意思看错了，所以一直想不通为什么会有无解的情况，后面老师讲解了一下，才发现是每一种颜色在所有的轮次都只能用一次，这样就会有无解的情况了。

然后问题可以转化为一个括号序列匹配的问题，就按照括号序列匹配的方法把每一个单位的序列的层数求出来，注意这里的无色要判断一下。

处理完每一个单位的层数之后，再从后往前遍历一遍所有单位，在每一次遇到颜色之后，就记录一下这个颜色所对应的层数，如果之后的再遍历到这个颜色但是层数和之前所记录的不同，那么就说明是无解的情况。

点击查看代码

int n,emp;
int col[N];
int l[N], r[N];
int w[N], h[N];

int main() {
	n = fr();
	for (int i = 1; i <= n; i ++) col[i] = fr();
	for (int i = 1; i <= n; i ++) {
		if (!col[i]) {
			emp = i;
			continue;
		}
		if (!l[col[i]]) l[col[i]] = i;
		else if (l[col[i]] < emp) {
			wj;
			return 0;
		}
	}
	for (int i = n; i; i --) {
		if (!r[col[i]]) r[col[i]] = i;
		if (col[i] == 0) r[col[i]] = 0;
	}
	for (int i = 1; i <= n; i ++) {
		if (l[col[i]] == i) w[i] ++;
		if (r[col[i]] == i) w[i + 1] --;
		w[i] += w[i - 1];
	}
	int ans = 0;
	for (int i = 1; i <= n; i ++) {
		if (!h[col[i]]) h[col[i]] = w[i];
		else if (h[col[i]] != w[i]) {
			wj;
			return 0;
		}
		ans = max(ans,w[i]);
	}
	fw(ans);
	return 0;
}

P4109 定价

题目传送门

贪心

易知数后面的零越多越好，那就枚举一下数后面有多少个零，因为给定范围，所以就在 \(l\) 上面操作，然后如果 \(l\) 的值大于了 \(r\) ，就结束。

然后 \(5\) 的地方要特判一下，其它地方直接加就可以了。

点击查看代码

lwl ten[N];

int main() {
	ten[0] = 1;
	int T = fr();
	while (T --) {
		int mn = inf, ans = 0;
		int l = fr(), r = fr();
		while (l <= r) {
			int t = l,qwq = 1;
			while (t % 10 == 0) {
				t /= 10;
				qwq *= 10;
			}
			int res = 0,h = 5;
			if (t % 10 == 5) res --;
			else if (t % 10 < 5) h = 5 - t % 10;
			else h = 10 - t % 10;
			int a = 0;
			while (t) {
				t /= 10;
				a ++;
			}
			res += a * 2;
			if (mn > res) {
				mn = res;
				ans = l;
			}
			l += qwq * h;
		}
		fw(ans);
		ch;
	}
	return 0;
}

6033 合并果子加强版

题目传送门

普通版用哈夫曼树就可以过了，但是这一题的数据范围比较大，没有办法用哈夫曼树。

观察到这一题的数据范围比较小，所以可以先用桶排序给输入排一个序，然后再开两个队列模拟单调队列。第一个队列就是没有合并过的果子，第二个队列是合并过后的果子。

每一次在两个队列里面取出最小值，再合并，和哈夫曼树达到的效果是一样的。

点击查看代码

int n;
int cnt[M];
queue<lwl> q,tmp;

lwl get() {
	lwl t = linf;
	if (q.size()) {
		t = min(t,q.front());
	}
	if (tmp.size()) {
		t = min(t,tmp.front());
	}
	if (q.size() && t == q.front()) {
		q.pop();
		return t;
	}
	if (tmp.size() && t == tmp.front()) tmp.pop();
	return t;
}

int main() {
	n = fr();
	for (int i = 1; i <= n; i ++) {
		int t = fr();
		cnt[t] ++;
	}
	for (int i = 1; i <= M - 5; i ++) {
		while (cnt[i]) {
			q.push(i);
			cnt[i] --;
		}
	}
	lwl ans = 0;
	for (int i = 1; i < n; i ++) {
		lwl x = get();
		lwl y = get();
		ans += (x + y);
		tmp.push(x + y);
	}
	fw(ans);
	return 0;
}

P61499 Triangles S

题目传送门

这个题目主要是要考虑该怎么样去重，那么我们充分发挥人类智慧，每一次只考虑直角顶点在左上角的点，具体做法就是每一次做完之后就把整个坐标系旋转九十度（换一个排序函数）

在每一次做的过程中，记录下竖着的间隔和和横着的间隔和，因为他的边必须是平行于坐标轴的，所以记录纵坐标间隔的和的时候是按照横坐标归类记录的，记录横坐标间隔的和的时候是按照纵坐标归类记录的。

然后因为我用的是 \(vector\) ，所以一开始要清零并且在里面推进去一个 \(0\) ，防止后面访问越界以至于 \(RE\) 。

点击查看代码

bool cmp1(pii a,pii b) {
	if (a.fi == b.fi) return a.se > b.se;
	return a.fi < b.fi;
}

bool cmp2(pii a,pii b) {
	if (a.fi == b.fi) return a.se < b.se;
	return a.fi > b.fi;
}

bool cmp3(pii a,pii b) {
	if (a.fi == b.fi) return a.se > b.se;
	return a.fi > b.fi;
}

void get() {
	memset(sumx,0,sizeof sumx);
	memset(sumy,0,sizeof sumy);
	memset(cntx,0,sizeof cntx);
	memset(cnty,0,sizeof cnty);
	for (int i = 0; i < N; i ++) {
		posx[i].clear();
		posx[i].push_back(0);
		posy[i].clear();
		posy[i].push_back(0);
	}
	for (int i = 1; i <= n; i ++) {
		lwl x = w[i].fi,y = w[i].se;
		sumx[x] = (sumx[x] + cntx[x] * abs(posy[x].back() - y)) % mod;
		cntx[x] ++;
		posy[x].push_back(y);
		sumy[y] = (sumy[y] + cnty[y] * abs(posx[y].back() - x)) % mod;
		cnty[y] ++;
		posx[y].push_back(x);
		ans = (ans + sumx[x] * sumy[y]) % mod;
	}
}

int main() {
	freopen("qwq.in","r",stdin);
	n = fr();
	for (int i = 1; i <= n; i ++) {
		w[i].fi = fr() + qwq;
		w[i].se = fr() + qwq;
	}
	sort(w + 1,w + 1 + n);
	get();
	sort(w + 1,w + 1 + n,cmp1);
	get();
	sort(w + 1,w + 1 + n,cmp2);
	get();
	sort(w + 1,w + 1 + n,cmp3);
	get();
	fw(ans);
	return 0;
}

P7517 数对

题目传送带

直接桶排序加模拟就可以了。然后算的时候要把自己给去掉。

点击查看代码

int main() {
	n = fr();
	int maxn = 0;
	for (int i = 1; i <= n; i ++) {
		w[i] = fr();
		maxn = max(w[i],maxn);
		cnt[w[i]] ++;
	}
	lwl ans = 0;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= w[i] / j; j ++) {
			if (w[i] % j) continue;
			ans += (lwl)cnt[j] - (j == w[i]);
			if (j != w[i] / j)
				ans += cnt[w[i] / j] - (w[i] / j == w[i]);
		}
	}
	fw(ans);
	return 0;
}

P8365 吃

题目传送门

很明显的，一开始应该把所有 \(a = 1\) 的全部吃掉，然后把他的 \(b\) 值算到当前体重上面来。

然后就是乘法了，稍微考虑一下就可以知道后面 \(a > 1\) 的点最多有一个选 \(b\) 加上去的，那么就按照这个排一个序，然后在选或者不选之中选一个最大值。

注意的是直到在选和不选中选一个比较大，都不要取模，不然这里比较大小的时候会有问题。后面乘法的时候再取模。

点击查看代码

int n;
pii w[N];
pdi tmp[N];

bool cmp(pdi a,pdi b) {
	return a.fi > b.fi;
}

int main() {
	n = fr();
	for (int i = 1; i <= n; i ++) w[i].fi = fr();
	for (int i = 1; i <= n; i ++) w[i].se = fr();
	sort(w + 1, w + 1 + n);
	lwl ans = 1;
	int i;
	for (i = 1; i <= n; i ++) {
		if (w[i].fi > 1) break;
		ans = ans + w[i].se;
	}
	int idx = 0;
	for (; i <= n; i ++) {
		tmp[++ idx] = {1.0 * (ans + w[i].se) / w[i].fi,i};
	}
	sort(tmp + 1,tmp + 1 + idx,cmp);
	bool flag = false;
	if (tmp[1].fi > ans) {
		ans += w[tmp[1].se].se;
		flag = true;
	}
	for (int i = 1 + flag; i <= idx; i ++) {
		ans = ans * w[tmp[i].se].fi % mod;
	}
	fw(ans);
	return 0;
}

P4653 Sure Bet

题目传送门

这个题意转化一下其实就是：

\[\max(\min(suma,sumb) - cnta - cntb) \]

可能最小收益最大，所以说要让两个种类的价值的差尽可能小，才能保证最小收益最大。

然后就是一个个推，然后模拟这个做法，每一次推完之后取一个 \(max\) 就可以了。

点击查看代码

typedef pair<double,double> pdd;

int n;
pdd w[N];
double a[N],b[N];
bool flag[N];

bool cmp(double a,double b) {
	return a > b;
}

int main() {
	int n = fr();
	for (int i = 1; i <= n; i ++) {
		cin >> w[i].fi >> w[i].se;
		a[i] = w[i].fi, b[i] = w[i].se;
	}
	sort(a + 1, a + 1 + n, cmp);
	sort(b + 1, b + 1 + n, cmp);
	double suma = 0, sumb = 0;
	double ans = 0;
	for (int cnta = 0, cntb = 0; ; ) {
		if (suma > sumb) {
			cntb ++;
			if (cntb > n) break;
			sumb += b[cntb];
		} else {
			cnta ++;
			if (cnta > n) break;
			suma += a[cnta];
		}
		ans = max(ans,min(suma,sumb) - cnta - cntb);
	}
	printf("%.4lf",ans);
	return 0;
}

P5426 Balancing Inversions G

题目传送门

如果直接移动两个相邻的但是不跨过 \(A\) 和 \(B\) 之间的数的时候，最多减少一个逆序对，所以一开始的初始值就是确定的了，然后再考虑交换两个序列拼接的地方的，这个地方直接暴力枚举就可以了。

点击查看代码

int n;
int a[N],b[N];
int suma[N],sumb[N];

int get1(int l,int r) {
	return suma[r] - suma[l - 1];
}

int get2(int l,int r) {
	return sumb[l] - sumb[r + 1];
}

int main() {
	n = fr();
	lwl w1 = 0,w2 = 0;
	lwl o1 = 0,o2 = 0;
	for (int i = 1; i <= n; i ++) {
		a[i] = fr();
		if (a[i]) o1 ++;
		else w1 += o1;
		suma[i] = suma[i - 1] + a[i];
	}

	for (int i = 1; i <= n; i ++) {
		b[i] = fr();
		if (b[i]) o2 ++;
		else w2 += o2;
	}
	for (int i = n; i; i --)
		sumb[i] = sumb[i + 1] + 1 - b[i];
	if (w1 == w2) {
		wj;
		return 0;
	}
	lwl ans = abs(w1 - w2);
	int l = n, r = 1;
	lwl t = 0;
	lwl tmp1 = w1,tmp2 = w2;
	while (1) {
		while (l >= 1 && a[l]) l --;
		while (r <= n && (!b[r])) r ++;
		if (l < 1 || r > n) break;
		t += n + r - l;
		tmp1 -= suma[l];
		tmp2 -= sumb[r];
		ans = min(ans,abs(tmp1 - tmp2) + t);
		l --, r ++;
	}
	t = 0;
	l = n, r = 1;
	tmp1 = w1, tmp2 = w2;
	while (1) {
		while (l >= 1 && (!a[l])) l --;
		while (r <= n && b[r]) r ++;
		if (l < 1 || r > n) break;
		t += n + r - l;
		tmp1 += suma[l - 1] - (n - l);
		tmp2 += sumb[r + 1] - (r - 1);
		ans = min(ans,abs(tmp1 - tmp2) + t);
		l --, r ++;
	}
	fw(ans);
	return 0;
}

P7789 Sirni

题目传送门

这个题目我写的时候卡常卡了好久，但是他们都一遍过了，这导致我很愤怒啊。

首先考虑暴力，给每两个点都建一个边，然后跑最小生成树，边的数量是 \(O(n^2)\) ，大概可以过前面三十分？不知道，没有写，看数据范围大概是这个样子的。

接下来考虑优化建边，观察一个数 \(x\) ，设两个数是 \(y = kx + b\) ， \(z = kx + t\) ，\(k \in Z,b < t\) ，然后考虑这三个连到一起的代价。

\[\begin{cases} x-y,y-z => b \\ x-z,y-z => 2 \times t - b \\ x-y,x-z => b + t\end{cases} \]

可以看出来连 \(x,y\) 是最佳的，所以说连边的时候就枚举 \(x\) 的倍数然后找大于等于倍数的第一个数连边（这里如果 \(k = 1\) 的话，要跳过他本身）

然后直接跑最小生成树就可以了。

还有要注意的一点就是数组不要开的和点的数量一样，要开大一些。

点击查看代码

int n;
int w[N],h[10000005], siz[10000005];
int mx;
vector<pii> e[10000005];

int find(int x) {
	if (h[x] != x) h[x] = find(h[x]);
	return h[x];
}

void hb(int a,int b) {
	if (siz[a] > siz[b]) swap(a,b);
	siz[b] += siz[a];
	h[a] = b;
}

int main() {
	n = fr();
	for (int i = 1; i <= n; i ++) {
		w[i] = fr();
		if (w[i] == 1) {
			wj;
			return 0;
		}
		mx = max(w[i],mx);
	}
	sort(w + 1, w + 1 + n);
	n = unique(w + 1,w + 1 + n) - w - 1;
	int idx = 0;
	// x
	// y = kx + t
	// z = kx + b (b > t)
	// x -> z -- b  y -> z -- b - t ==> 2 * b - t
	// x -> y -- t  y -> z -- b - t ==> b √
	// x -> z -- b  x -> y -- t     ==> b + t
	for (int j = 1; j < n; j ++) {
		int i = w[j];
		int t = i;
		while (t <= mx) {
			auto to = lower_bound(w + 1, w + 1 + n,t) - w;
			if (i == t) to ++;
			if (to > n) break;
			int qwq = w[to];
			if (qwq - qwq % i != t) {
				t = qwq - qwq % i;
				continue;
			}
			e[qwq % i].emplace_back(make_pair(i,qwq));
			idx ++;
			t += i;
		}
	}
	for (int i = 1; i <= mx; i ++) {
		h[i] = i;
		siz[i] = 1;
	}
	lwl ans = 0;
	for (int i = 0; i < mx; i ++) {
		for (auto j : e[i]) {
			int a = j.fi, b = j.se;
			if (find(a) != find(b)) {
				ans += i;
				hb(h[a],h[b]);
			}
		}
	}
	fw(ans);
	return 0;
}

Centroids

题目传送门

换根 \(dp\) 。

很明显的是，如果删之前是重心，那么删了之后他也可以成为树的重心。

而如果说一个节点 \(u\) 的一棵子树有一棵子树大小大于 \(\lfloor \frac{n}{2} \rfloor\) 那么这种子树一定只有一个，那么就考虑将这个子树大于 \(\lfloor \frac{n}{2} \rfloor\) 的部分拼到另一个子树上面去。

于是就记录一下重儿子（也就是最大子树所对应的子节点），再记录一下小于等于 \(\lfloor \frac{n}{2} \rfloor\) 的子树（记录一个次大一个最大）

然后再第一次 \(dfs\) 中处理出来这些，然后再在后面换根的时候再把从根节点到这个点的东西处理出来，处理的东西大概也就是上面那些东西。

点击查看代码

void dfs(int u,int father) {
	siz[u] = 1;
	for (auto v : e[u]) {
		if (v == father) continue;
		dfs(v,u);
		
		siz[u] += siz[v];
		if (siz[son[u]] < siz[v]) son[u] = v;
		// 重儿子
		
		int t;
		if (siz[v] <= n / 2) t = siz[v];
		else t = f[v];
		
		if (t > f[u]) {
			h[u] = f[u]; // 第二大
			f[u] = t; // 第一大
			s[u] = v; // 最大对应的儿子
		} else if (t == f[u]) h[u] = t;
		else if (t > h[u]) h[u] = t;
	}
}

void get(int u,int father) {
	ans[u] = true;
	if (siz[son[u]] > n / 2) {
		ans[u] &= ((siz[son[u]] - f[son[u]]) <= n / 2);
	} else if (n - siz[u] > n / 2) {
		ans[u] &= ((n - siz[u] - w[u]) <= n / 2);
	}
	
	for (auto v : e[u]) {
		if (v == father) continue;
		int t;
		
		if (n - siz[u] <= n / 2) t = n - siz[u];
		else t = w[u]; // 上面最大的
		
		w[v] = t;
		if (v == s[u])
			w[v] = max(w[v], h[u]);
		else w[v] = max(w[v],f[u]);
		get(v,u);
	}
}

int main() {
	n = fr();
	for (int i = 1; i < n; i ++) {
		int a = fr(), b = fr();
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(1,0);
	get(1,0);
	for (int i = 1; i <= n; i ++) {
		fw(ans[i]);
		kg;
	}
	return 0;
}

P7249 移动网络

题目传送门

这个函数有单调性，如果说 \(dis\) 满足这个条件，那么比他小的所有 \(dis\) 都可以满足，所以就可以用二分来解决这个问题。

\(check\) 函数的写法就是找到每一个点所对应的一个区间，如果说这个区间超过了 \(L\)，那么就说明是不行的。

还有一个奇怪的点，我一开始觉得他要特判一下 \(sqrt\) 里面是不是小于零，但是发现像代码里面这样写是可以的，很奇怪哦。

点击查看代码

const double eps = 1e-4;

bool check(double dis) {
	double r = 0;
	for (int i = 1; i <= n; i ++) {
		double t;
		t = sqrt(dis * dis - w[i].se * w[i].se);
		if (w[i].fi - t <= r && w[i].fi + t >= r)
			r = w[i].fi + t;
	}
	return r < L;
}

int main() {
	n = fr(), L = fr();
	for (int i = 1; i <= n; i ++) w[i] = {fr(), fr()};
	double l = 0, r = 1414213562 + 5;
	while (r - l >= eps) {
		double mid = (l + r) / 2;
		if (check(mid)) l = mid;
		else r = mid;
	}
	printf("%.6lf",r);
	return 0;
}

P4040 宅男计划

题目传送门

首先这个活的天数跟买外卖的次数是一个单峰函数，这个后面说贪心的时候可以简要感性理解一下。

于是考虑三分买外卖的次数，定了买外卖的次数 \(cnt\) 之后，可以将除去买外卖的钱数去掉，然后将其均分为 \(cnt\) 份，然后对于每一份进行贪心。贪心的策略就是尽量选便宜的，直到选不了了为止。

将每一次均分的分完后，会有剩下的钱，再考虑将剩下的钱买吃的。因为前面是已经没有办法再买了，所以说剩下的钱是没有办法支撑每一个 \(cnt\) 份里面都多一天的，所以说就尽量选就可以了。具体的就是这里 \(check\) 函数最后的循环。

所以可以发现，这里的 \(cnt\) 越少，每一次均分的钱也就越多，但是他的次数也就越少，也就是最后乘的基数越少，感性理解一下，这个就是一个单峰函数捏。

点击查看代码

bool cmp(pii a, pii b) {
	if (a.fi != b.fi) return a.fi < b.fi;
	return a.se > b.se;
}

lwl check(lwl cnt) {
	lwl val = m - cnt * f;
	lwl per = val / cnt;
	lwl more = val % cnt;
	lwl ans = 0, u = 0;
	for (int i = 1; i <= n; i ++) {
		lwl t = w[i].se - u + 1;
		if (t <= 0) continue;
		if (per >= w[i].fi * t) {
			per -= w[i].fi * t;
			u += t;
		} else if (per >= w[i].fi) {
			lwl tmp = per / w[i].fi;
			u += tmp;
			per -= tmp * w[i].fi;
		} else break;
	}
	more += per * cnt;
	for (int i = 1; i <= n; i ++) {
		if (w[i].se >= u && more >= w[i].fi) {
			lwl tmp = min(more / w[i].fi, cnt);
			ans += tmp;
			more -= w[i].fi * tmp;
		}
	}
	ans += cnt * u;
	return ans;
}

int main() {
	m = fr(), f = fr(), n = fr();
	for (int i = 1; i <= n; i ++) 
		w[i] = {fr(),fr()};
	sort(w + 1,w + 1 + n,cmp);
	lwl l = 1, r = m / f + 1;
	while (l < r) {
		lwl t = (r - l) / 3;
		lwl ml = l + t, mr = r - t;
		if (check(ml) < check(mr)) l = ml + 1;
		else r = mr - 1;
	}
	fw(check(l));
	return 0;
}

P2571 传送带

题目传送门

这个是三分套三分，但是题解的单峰函数证明确实是没有看懂，反正大概意思就是说这个在 \(AB\) 上走的路和总时间是一个单峰函数（同在 \(CD\) 上的），所以就可以三分出在 \(AB\) 上面走哪里，然后对于每一个在 \(AB\) 上的点，再与之对应的求出一个 \(CD\) 上的点。

点击查看代码

const double eps = 1e-6;

double ax,ay,bx,by,cx,cy,dx,dy;
double p,q,r;
double ans = dinf;

double dis(double x1,double y1,double x2,double y2) {
	double dx = x1 - x2;
	double dy = y1 - y2;
	return sqrt(dx * dx + dy * dy);
}

double get(double x1,double y1,double x2,double y2) {
	return dis(x1,y1,x2,y2) / r + dis(x2,y2,dx,dy) / q;
}

double check(double x,double y) {
	double res = dinf;
	double lx = cx, ly = cy, rx = dx, ry = dy;
	while (1) {
		double t = (rx - lx) / 3;
		double mlx = lx + t, mrx = mlx + t;
		t = (ry - ly) / 3;
		double mly = ly + t, mry = mly + t;
		double ml = get(x,y,mlx,mly), mr = get(x,y,mrx,mry);
		res = min(res,min(ml,mr));
		if (ml > mr) lx = mlx, ly = mly;
		else rx = mrx, ry = mry;
		if (fabs(rx - lx) < eps && fabs(ry - ly) < eps)
			break;
	}
	return res + dis(x,y,ax,ay) / p;
}

int main() {
	ax = fr(), ay = fr(), bx = fr(), by = fr();
	cx = fr(), cy = fr(), dx = fr(), dy = fr();
	p = fr(), q = fr(), r = fr();
	double lx = ax, ly = ay, rx = bx, ry = by;
	while (1) {
		double t = (rx - lx) / 3;
		double mlx = lx + t, mrx = mlx + t;
		t = (ry - ly) / 3;
		double mly = ly + t, mry = mly + t;
		double ml = check(mlx,mly), mr = check(mrx,mry);
		ans = min(ans,min(ml,mr));
		if (ml > mr) lx = mlx, ly = mly;
		else rx = mrx, ry = mry;
		if (fabs(rx - lx) < eps && fabs(ry - ly) < eps)
			break;
	}
	printf("%.2lf",ans);
	return 0;
}

P9378 物理实验

题目传送门

很显然的一点是，选取第 \(i\) 个实验肯定比选取后面所有的实验的贡献还要大，所以就从前往后遍历，如果不和前面的冲突就把这个点加到要选的集合里面去。

检查这个数是否能放进去的时候，就考虑如果要选的集合已经固定了的话，那么其实就等价于已有答案集合 \(S\) ，求加入这个元素是否合法。

因为已经有集合 \(S\) 了，所以可以直接暴力找到宇宙射线轰掉的是哪一个实验，然后就可以求出来每一个元素最晚的要完成的时间 \(limit[i]\) ，那么问题就可以转化为找一个序列 \(P\) ，使得 \(\forall i \in S, i < limit[i]\)

这个可以直接暴力判断。

点击查看代码

int n, m;
int w[N], p[N][N];
int lim[N];
bool ans[N], flag[N];
int tmp[N];

bool check() {
	memset(lim,0x3f,sizeof lim);
	memset(flag,0,sizeof flag);
	for (int j = 1; j <= m; j ++) {
		for (int i = 1; i <= n; i ++) {
			if (flag[p[i][j]]) continue;
			int t = p[i][j];
			if (!ans[t]) {
				flag[t] = true;
				break;
			} else lim[t] = min(lim[t],w[j]);
		}
	}
	int idx = 0;
	for (int i = 1; i <= n; i ++) {
		if (ans[i]) tmp[++ idx] = lim[i];
	}
	sort(tmp + 1,tmp + 1 + idx);
	for (int i = 1; i <= idx; i ++) {
		if (i > tmp[i]) return false;
	}
	return true;
}

bool cmp(int a,int b) {
	return lim[a] < lim[b];
}

int main() {
	n = fr(), m = fr();
	for (int i = 1; i <= m; i ++) w[i] = fr();
	for (int i = 1; i <= m; i ++) {
		for (int j = 1; j <= n; j ++)
			p[j][i] = fr();
	}
	for (int i = 1; i <= n; i ++) {
		ans[i] = true;
		if (!check()) ans[i] = false;
	}
	check();
	int idx = 0;
	for (int i = 1; i <= n; i ++) {
		if (ans[i]) w[++ idx] = i;
	}
	sort(w + 1, w + 1 + idx,cmp);
	for (int i = 1; i <= idx; i ++) {
		fw(w[i]);
		kg;
	}
	return 0;
}

6148 Swapity Swapity Swap S

题目传送门

可以发现，模拟一次的复杂度是有的，所以我们可以先模拟一次，找出一个奶牛在一次操作之后所在的位置。

可以观察到，如果说 \(i\) 在一次变化后到了 \(j\) ，\(j\) 变化到了 \(k\) ，那么在下一次变化的时候 \(i\) 就会变化到 \(k\) ，所以我们可以用倍增来处理这个变化，然后算答案的时候就用一种类似于快速幂的写法来计算。

然后我写的时候一开始手写 \(reverse\) 老是写错，所以就直接用的函数。

点击查看代码

void init() {
	for (int i = 1; i <= n; i ++) a[i] = i,ans[0][i] = i;
	for (int i = 1; i <= m; i ++) {
		int l = w[i].fi, r = w[i].se;
		reverse(ans[0] + l, ans[0] + r + 1);
	}
}

void did(int t) {
	memcpy(tmp,a,sizeof a);
	for (int i = 1; i <= n; i ++) {
		a[i] = tmp[ans[t][i]];
	}
}

int main() {
	n = fr(), m = fr(), K = fr();
	for (int i = 1; i <= m; i ++) {
		w[i] = {fr(), fr()};
	}
	init();
	int maxk = log2(K) + 1;
	for (int j = 1; j <= maxk; j ++) {
		for (int i = 1; i <= n; i ++) {
			ans[j][i] = ans[j - 1][ans[j - 1][i]];
		}
	}
	int cnt = 0;
	while (K) {
		if (K & 1) did(cnt);
		cnt ++;
		K >>= 1;
	}
	for (int i = 1; i <= n; i ++) {
		fw(a[i]);
		ch;
	}
	return 0;
}

P7915 回文

题目传送门

因为要求字典序最小，所以说先遍历 \(L\) 的，因为其实如果说确定了这一步走 \(L\) 还是 \(R\) ，就可以确定一个操作序列了。所以就看一看第一步操作 \(L\) 或者第一步操作 \(R\) 可不可以有一个序列，这个判断可以 \(O(n)\) 判断。

点击查看代码

bool get(int t,int L,int R) {
	if (L == 2) ans[1] = true;
	int l = t, r = t, st = 2, en = 2 * n - 1;
	for (int i = 1; i < n; i ++) {
		if (wz[w[L]].se == l - 1) {
			l --, L ++, ans[st ++] = ans[en --] = true;
		} else if (wz[w[L]].se == r + 1) {
			r ++, L ++, ans[st ++] = true,en --;
		} else if (wz[w[R]].fi == l - 1) {
			l --, R --, st ++, ans[en --] = true;
		} else if (wz[w[R]].fi == r + 1) {
			r ++, R --, st ++, en --;
		} else return false;
	}
	ans[2 * n] = true;
	return true;
}

int main(){
	int T = fr();
	while (T --) {
		memset(ans,0,sizeof ans);
		for (int i = 1; i <= n; i ++) wz[i] = {0,0};
		n = fr();
		for (int i = 1; i <= 2 * n; i ++) {
			w[i] = fr();
			if (!wz[w[i]].fi) wz[w[i]].fi = i;
			else {
				wz[w[i]].se = i;
				match[i] = wz[w[i]].fi;
				match[wz[w[i]].fi] = i;
			}
		}
		if (!get(wz[w[1]].se,2,2 * n)) {
			memset(ans,0,sizeof ans);
			if (!get(wz[w[2 * n]].fi,1,2 * n - 1)) {
				wj;
				continue;
			}
		}
		for (int i = 1; i <= 2 * n; i ++) {
			if (ans[i]) cout << "L";
			else cout << "R";
		}
		ch;
	}
	return 0;
}

P8817 假期计划

题目传送门

因为 \(x \le 2500\) ，所以说可以 \(n^2\) 枚举四个节点的中间两个，然后预处理出每个点跟 \(1\) 之间比较大的几个点的贡献，因为后面要枚举 \(i,j\) 两点，而 \(i\) 和 \(1\) 点之间的较大的点会和 \(j\) 的重复，所以就记录比较大的三个点就可以了。

所以大概流程就是：

求出每两个点之间的最短路距离，因为这里的权值一样，所以可以用 \(bfs\) 。
枚举，找出 \(i\) 点和 \(1\) 点之间贡献较大的三个点
枚举四个点的中间两个点，再找到这两个点和 \(1\) 之间贡献较大的点，如果有重复的话就往后推一推。

点击查看代码

void bfs(int st) {
	memset(flag,0,sizeof flag);
	queue<int> q;
	q.push(st);
	dis[st][st] = 0;
	flag[st] = true;
	while (q.size()) {
		int u = q.front();
		q.pop();
		
		for (int &v : e[u]) {
			if (flag[v]) continue;
			dis[st][v] = dis[st][u] + 1;
			q.push(v);
			flag[v] = true;
		}
	}
}

int main() {
	n = fr(), m = fr(), k = fr() + 1;
	for (int i = 2; i <= n; i ++) w[i] = fr();
	while (m --) {
		int a = fr(), b = fr();
		e[a].push_back(b);
		e[b].push_back(a);
	}
	memset(dis,0x3f,sizeof dis);
	for (int i = 1; i <= n; i ++) {
		bfs(i);
	}
	for (int i = 2; i <= n; i ++) {
		for (int j = 2; j <= n; j ++) {
			if (dis[i][j] > k || i == j || dis[j][1] > k)
				continue;
			if (w[j] > w[mx[i][0]]) {
				mx[i][2] = mx[i][1];
				mx[i][1] = mx[i][0];
				mx[i][0] = j;
			} else if (w[j] > w[mx[i][1]]) {
				mx[i][2] = mx[i][1];
				mx[i][1] = j;
			} else {
				mx[i][2] = j;
			}
		}
	}
	lwl ans = -linf;
	for (int i = 2; i <= n; i ++) {
		for (int j = 2; j <= n; j ++) {
			if (i == j || dis[i][j] > k) continue;
			int qwq = 0, awa = 0;
			if (mx[i][qwq] == j) qwq = 1;
			if (mx[j][awa] == i) awa = 1;
			if (mx[i][qwq] == mx[j][awa]) {
				int t1 = qwq + 1, t2 = awa + 1;
				if (mx[i][t1] == j) t1 ++;
				if (mx[j][t2] == i) t2 ++;
				if (w[mx[i][t1]] > w[mx[j][t2]]) {
					qwq = t1;
				} else awa = t2;
			}
			if (mx[j][awa] == 0 || mx[i][qwq] == 0) continue;
			ans = max(ans,w[mx[j][awa]] + w[mx[i][qwq]] + w[i] + w[j]);
		}
	}
	fw(ans);
	return 0;
}

P9019 Tractor Paths P

题目传送门

第一问很明显可以用倍增直接解决掉，至于第二问的话就用向右的特殊点数量减去向左的特殊点数量。

第一问答案求出来之后再求第二问，因为这个地方第二问求的时候 \(v\) 也要一起往前面跳，不然会有问题（Richard_H 因为这个只过了样例，后面输出的都是负数）

点击查看代码

int h[N][25],f[N][25];
int hh[N][25],ff[N][25];
// 左         右
// 左特殊点   右特殊点

void init() {
	int la = 0;
	for (int i = 1; i <= (n << 1); i ++) {
		if (!type[i]) {
			h[id[i]][0] = la;
			hh[id[i]][0] = sum[la];
		} else la = id[i];
	}
	la = 0;
	for (int i = (n << 1); i; i --) {
		if (type[i]) {
			f[id[i]][0] = la;
			ff[id[i]][0] = sum[la - 1];
		} else la = id[i];
	}
	for (int k = 1; k <= kmax; k ++) {
		for (int i = 1; i <= n; i ++) {
			h[i][k] = h[h[i][k - 1]][k - 1];
			hh[i][k] = hh[h[i][k - 1]][k - 1] + hh[i][k - 1];
			f[i][k] = f[f[i][k - 1]][k - 1];
			ff[i][k] = ff[f[i][k - 1]][k - 1] + ff[i][k - 1];
		}
	}
}

int main() {
	n = fr(), Q = fr();
	kmax = log2(n) + 1;
	scanf("%s", (s + 1));
	int idx = 0;
	queue<int> q;
	for (int i = 1; i <= 2 * n; i ++) {
		if (s[i] == 'L') q.push(i),type[i] = true;
		else {
			w[++ idx] = {q.front(),i};
			id[q.front()] = idx;
			id[i] = idx;
			q.pop();
		}
	}
	scanf("%s", (s + 1));
	for (int i = 1; i <= n; i ++) flag[i] = s[i] - '0';
	for (int i = 1; i <= n; i ++) 
		sum[i] = sum[i - 1] + flag[i];
	init();
	while (Q --) {
		int a = fr(), b = fr();
		int ans1 = 0, ans2 = flag[a] + flag[b];
		int u = a;
		for (int k = kmax; k >= 0; k --) {
			if (h[u][k] < b) {
				ans1 += (1 << k);
				u = h[u][k];
			}
		}
		u = a;
		int v = b;
		for (int k = kmax; k >= 0; k --) {
			if (ans1 & (1 << k)) {
				ans2 += hh[u][k] - ff[v][k];
				u = h[u][k], v = f[v][k];
			}
		}
		ans1 ++;
		fw(ans1),kg;
		fw(ans2),ch;
	}
	return 0;
}

P6064 Naptime G

题目传送门

其实如果说他不是一个环，就是一个裸的线性 \(dp\) ，然后因为这一题是一个环，就考虑分类讨论一下，讨论第一个点选或者不选的情况。

代码中第一个循环分类的就是第一个选的情况，这样最后计算答案的时候就是看他如果最后一个选了，就可以把第一个的价值算到总答案里面去，如果说最后一个没有选的话就不算第一个的价值。

然后第二个循环就假装他不是一个环这样子做，也就是没有强制第一个选，最后在答案里面取一个最大值就是最终的结果。

点击查看代码

int main() {
	n = fr(), b = fr();
	for (int i = 1; i <= n; i ++) w[i] = fr();
	for (int i = n; i; i --) sum[i] = sum[i + 1] + w[i];
	int ans = 0;
	memset(dp,-0x3f,sizeof dp);
	dp[1][1][1] = w[1];
	for (int i = 2; i <= n; i ++) {
		int u = i,v = i - 1; 
		for (int j = 1; j <= b; j ++) {
			dp[u][j][0] = max(dp[v][j][0],dp[v][j][1]);
			dp[u][j][1] = max(dp[v][j - 1][0],dp[v][j - 1][1] + w[i]);
		}
	}
	ans = max(ans,max(dp[n][b][1],dp[n][b][0] - w[1]));
	memset(dp,-0x3f,sizeof dp);
	dp[1][0][0] = 0;
	for (int i = 2; i <= n; i ++) {
		int u = i, v = i - 1;
		for (int j = 0; j <= b; j ++) {
			dp[u][j][0] = max(dp[v][j][0],dp[v][j][1]);
			if (j) dp[u][j][1] = max(dp[v][j - 1][0],dp[v][j - 1][1] + w[i]);
		}
	}
	ans = max(ans,max(dp[n][b][0],dp[n][b][1]));
	fw(ans);
	return 0;
}

P8482 Number

题目传送门

贪心 + 高精度（感觉不太多）

首先考虑该怎么样让他的乘积最大，那么显而易见的就是将大的数尽量往高的位置放，并且在这个前提下保证两个数的差尽量小，于是就可以写出下面一开始的贪心求初始值的代码。

其次，题目中说要求输出另外两个数使得这两个数和求出的两个数的乘积相同但是数字数量不一样（其实就是其它两个数），那么首先想到的是 \(1\) 和这两个数的乘积是可以满足的，但是如果这么写的话需要高精度乘法，比较麻烦，所以就考虑有没有其他的数。

观察到题目范围，每一个数字的数量都是 \(\ge 1\) 的，所以说必定有一个数的结尾是 \(0\)，那么我们就可以将这个数除以 \(2\) ，另一个数乘 \(2\) ，这就可以直接模拟解决。

点击查看代码

void twice(int a[],int &lena) {
	int t = 0;
	for (int i = 1; i <= lena; i ++) {
		int tmp = ((a[i] << 1) + t) / 10;
		a[i] = ((a[i] << 1) + t);
		a[i] %= 10;
		t = tmp;
	}
	if (t) a[++ lena] = t;
}

void half(int a[],int &lena) {
	int t = 0;
	for (int i = lena; i; i --) {
		a[i] += t;
		t = (a[i] & 1) * 10;
		a[i] >>= 1;
	}
}

int main() {
	freopen("qwq.in","r",stdin);
	for (int i = 0; i <= 9; i ++) {
		cnt[i] = fr();
	}
	int lena = 0, lenb = 0;
	bool flag = true;
	for (int i = 9; i >= 0; i --) {
		if (lenb > lena) a[++ lena] = i, cnt[i] --;
		if (!flag && cnt[i] && lena != lenb) {
			b[++ lenb] = i;
			cnt[i] --;
		}
		while (cnt[i] >= 2) {
			cnt[i] -= 2;
			a[++ lena] = i;
			b[++ lenb] = i;
		}
		if (cnt[i] && flag) {
			a[++ lena] = i;
			flag = false;
			continue;
		} else if (cnt[i]) {
			b[++ lenb] = i;
		}
	}
	reverse(a + 1, a + 1 + lena);
	reverse(b + 1, b + 1 + lenb);
	if (a[1] == 0) {
		half(a,lena);
		twice(b,lenb);
	} else {
		half(b,lenb);
		twice(a,lena);
	}
	reverse(a + 1, a + 1 + lena);
	reverse(b + 1, b + 1 + lenb);
	for (int i = 1; i <= lena; i ++) {
		fw(a[i]);
	}
	ch;
	for (int i = 1; i <= lenb; i ++) {
		fw(b[i]);
	}
	ch;
	return 0;
}

P7114 字符串匹配

题目传送门

看题解说正解是扩展 \(kmp\) ，但是这一题是可以暴力草过去的，所以果断选择暴力。

暴力的话就是预处理出前缀和后缀的奇数次数，然后枚举前面循环节的长度，再记录一个前缀和算答案。

还有就是多测记得清空。

点击查看代码

lwl get(int l,int r) {
	return w[r] - w[l - 1] * p[r - l + 1];
}

int main() {
	freopen("qwq.in","r",stdin);
	int T = fr();
	while (T --) {
		scanf("%s",s + 1);
		n = strlen(s + 1);
		memset(pre,0,sizeof pre);
		memset(bck,0,sizeof bck);
		memset(cc,0,sizeof cc);
		memset(sum,0,sizeof sum);
		p[0] = 1;
		for (int i = 1; i <= n; i ++) {
			w[i] = w[i - 1] * P + s[i] - 'a' + 1;
			p[i] = p[i - 1] * P;
		}
		for (int i = 1; i <= n; i ++) {
			cc[s[i] - 'a'] ++;
			if (cc[s[i] - 'a'] & 1) pre[i] = pre[i - 1] + 1;
			else pre[i] = pre[i - 1] - 1;
		}
		memset(cc,0,sizeof cc);
		bck[n + 1] = 0;
		for (int i = n; i; i --) {
			cc[s[i] - 'a'] ++;
			if (cc[s[i] - 'a'] & 1) bck[i] = bck[i + 1] + 1;
			else bck[i] = bck[i + 1] - 1;
		}
		lwl ans = 0;
		int j;
		// 枚举循环节
		for (int len = 2; len <= n; len ++) {
			for (int i = pre[len - 1]; i <= 26; i ++) {
				// 奇数次数前缀和
				sum[i] ++;
			}
			lwl t = get(1,len);
			j = len + 1;
			for (; j <= n && get(j - len,j - 1) == t; j += len) {
				ans += sum[bck[j]];
			}
		}
		fw(ans);
		ch;
	}
	return 0;
}

P7077 函数调用

题目传送门

一开始想的是直接模拟，然后只拿到了七十五分的好成绩，后来观察了一下题解，发现需要用到拓扑排序来处理每一个操作的影响，于是乎就改成了拓扑排序。

然后乘法对于加法的影响是从后往前的，所以这里要存一个倒着的边，正好方便了求度数。

点击查看代码

struct node {
	int type;
	lwl v;
	int p,cnt;
	vector<int> g;
}t[N];

void topomul() {
	queue<int> q;
	mul[0] = 1;
	for (int i = 0; i <= m; i ++) {
		d[i] = e1[i].size();
		if (!d[i]) q.push(i);
	}
	while(q.size()) {
		int u = q.front();
		q.pop();
		
		for (auto v : e2[u]) {
			d[v] --;
			if (!d[v]) q.push(v);
			mul[v] = mul[v] * mul[u] % mod;
		}
	}
}

void topoadd() {
	queue<int> q;
	for (int i = 0; i <= m; i ++) {
		d[i] = e2[i].size();
		if (!d[i]) q.push(i);
	}
	add[0] = 1;
	while(q.size()) {
		int u = q.front();
		q.pop();
		
		lwl mull = 1;
		
		int siz = e1[u].size();
		for (int i = siz - 1; i >= 0; i --) {
			int v = e1[u][i];
			d[v] --;
			if (!d[v]) q.push(v);
			add[v] = (add[v] + add[u] * mull % mod) % mod;
			mull = mull * mul[v] % mod;
		}
	}
}

int main() {
	n = fr();
	for (int i = 1; i <= n; i ++) w[i] = fr();
	m = fr();
	for (int i = 1; i <= m; i ++) {
		t[i].type = fr();
		mul[i] = 1;
		if (t[i].type == 1) {
			t[i].p = fr(), t[i].v = fr();
		} else if (t[i].type == 2) {
			t[i].v = fr();
			mul[i] = t[i].v;
		} else {
			t[i].cnt = fr();
			for (int j = 1; j <= t[i].cnt; j ++) {
				int a = fr();
				t[i].g.push_back(a);
				e1[i].push_back(a);
				e2[a].push_back(i);
			}
		}
	}
	Q = fr();
	for (int i = 1; i <= Q; i ++) {
		q[i] = fr();
		e1[0].push_back(q[i]);
		e2[q[i]].push_back(0);
	}
	topomul();
	topoadd();
	for (int i = 1; i <= n; i ++) w[i] = w[i] * mul[0] % mod;
	for (int i = 1; i <= m; i ++) {
		if (t[i].type == 1) {
			w[t[i].p] = (w[t[i].p] + add[i] * t[i].v % mod) % mod;
		}
	}
	for (int i = 1; i <= n; i ++) {
		fw(w[i]);
		kg;
	}
	return 0;
}

4363 一双木棋

状态压缩，然后用 \(map\) 来存储状态（注意这里的 \(map\) 要开 \(long long\)）

一开始写这一题 \(get\) 里面比较大小那里只和 \(y\) 比较，没有算上后面那一串，导致寄了（调的我快自闭了，甚至觉得输入写错了）

点击查看代码

int n,m,idx;
int a[N][N], b[N][N];
lwl en;
map<lwl,int> h;
int dp[200005];

void get(lwl &x,lwl y,int i,int j,bool type) {
	if (type) {
		if (x > y - b[i][j]) x = y - b[i][j];
	} else {
		if (x < y + a[i][j]) x = y + a[i][j];
	}
}

lwl dfs(lwl u,bool op) {
//	cout << u << endl;
	if (u == en) return 0;
	if (h[u]) return dp[h[u]];
	lwl tmp = u, ans = linf;
	if (!op) ans = -linf;
	vector<int> w;
	w.push_back(inf);
	while (tmp) {
		w.push_back(tmp % 11);
		tmp /= 11;
	}
	while ((int)w.size() <= n)
		w.push_back(0);
	tmp = 1;
	for (int i = 1; i <= n; i ++) {
		if (w[i] < min(w[i - 1],m)) {
			lwl tt = dfs(u + tmp,1 - op);
			get(ans,tt,i,w[i] + 1,op);
		}
		tmp *= 11;
	}
	h[u] = ++ idx, dp[idx] = ans;
	return ans;
}

int main(){
	n = fr(), m = fr();
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++)
			a[i][j] = fr();
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++)
			b[i][j] = fr();
	}
	for (int i = 1; i <= n; i ++) {
		en = en * 11 + m;
	}
	lwl ans = dfs(0,0);
	fw(ans);
	return 0;
}

Number With The Given Amount Of Divisors

题目传送门

首先将 \(n\) 分解质因数一下，因为因子个数的式子是：\(\prod (cnt[ap[i]] + 1)\) ，所以说 \(n\) 的因数都是这个的一员或者组成这个一员，所以直接 \(dfs\) 就可以了，再加上最优性剪枝和可行性剪枝（题目中说了最大值不会超过 \(10^{18}\) ）

点击查看代码

lwl ans = linf;
int w[N],ap[N];
lwl zs[N] = {0,2,3,5,7,11,13,17,19,23,29,33,37,41,43,47,53,57};

lwl ksm(lwl a,lwl k) {
	lwl ans = 1;
	while (k) {
		if (k & 1) ans = ans * a;
		a = a * a;
		k >>= 1;
	}
	if (ans <= 0) return linf;
	return ans;
}

void dfs(int u,int i,lwl t,lwl mul) {
	if (ans < t) return ;
	if (!u) {
		if (!zs[i]) return ;
		lwl tmp = t, qwq = ksm(zs[i],mul);
		t = t * qwq;
		if (t < 0) return ;
		if (t / qwq == tmp) ans = min(ans,t);
		return ;
	}
	lwl tmp = t, qwq = ksm(zs[i],mul);
	t = t * qwq;
	if (t < 0) return ;
	if (t / qwq == tmp) dfs(u - 1,i + 1,t,ap[u] - 1);
	if (!mul) dfs(u - 1,i,tmp,ap[u] + mul - 1);
	else dfs(u - 1,i,tmp,ap[u] * (mul + 1) - 1);
}

int main(){
	n = fr();
	for (int i = 2; i <= n; i ++) {
		while (n % i == 0) {
			n /= i;
			ap[++ idx] = i;
		}
	}
	dfs(idx,1,1,0);
	fw(ans);
	return 0;
}

P7297 Telephone G

题目传送门

暴力建边的话只能过前面五个点，考虑优化。

可以用分层图建边的方式，如果这个点的颜色为 \(w[i]\) ，那么就将 \(i\) 向这个点在这个颜色的这一层连一条长度为 \(0\) 的边，如果说 \(flag[j][w[i]]\) 的话，就将 \(i\) 在 \(j\) 这一层的点跟 \(i\) 在第 \(0\) 层的点连一条权值为 \(0\) 的边。

然后每一层的内部相邻的点之间连一条边权为 \(1\) 的边。然后因为这一题的边权只有 \(1\) 和 \(0\) ，所以可以用双端队列跑 \(bfs\) ，但是我用 \(dij\) 再加上 \(O ^ 2\) 也可以过。

点击查看代码

int n, k;
int w[N];
bool flag[K][K];
char s[K];
vector<node> e[N * K];
lwl dis[N * K];
bool vis[N * K];

int get(int j,int i) {
	return i * n + j;
}

void dij() {
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	priority_queue<pii,vector<pii>,greater<pii> > q;
	dis[1] = 0;
	q.push({dis[1],1});
	while (q.size()) {
		auto u = q.top().se;
		q.pop();
		
		if (vis[u]) continue;
		vis[u] = true;
		
		for (auto it : e[u]) {
			int v = it.v, w = it.w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push({dis[v],v});
			}
		}
	}
}

int main() {
	n = fr(), k = fr();
	for (int i = 1; i <= n; i ++) w[i] = fr();
	for (int i = 1; i <= k; i ++) {
		scanf("%s",s + 1);
		for (int j = 1; j <= k; j ++) {
			if (s[j] == '1') flag[i][j] = true;
		}
	}
	for (int i = 1; i < n; i ++) {
		for (int j = 1; j <= k; j ++) {
			e[get(i,j)].push_back({get(i + 1,j), 1});
			e[get(i + 1,j)].push_back({get(i,j), 1});
		}
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= k; j ++) {
			if (flag[j][w[i]])
				e[get(i,j)].push_back({i,0});
			if (w[i] == j)
				e[i].push_back({get(i,j),0});
		}
	}
	dij();
	if (dis[n] >= linf / 2) wj;
	else fw(dis[n]);
	return 0;
}

P7411 Comfortable Cows S

题目传送门

\(BFS\)

点击查看代码

void update(int x,int y) {
	for (int i = 0; i < 4; i ++) {
		if (!flag[x + dx[i]][y + dy[i]]) continue;
		cnt[x][y] ++;
		cnt[x + dx[i]][y + dy[i]] ++;
	}
}

void bfs(int st) {
	queue<pii> q;
	update(w[st].fi,w[st].se);
	if (cnt[w[st].fi][w[st].se] == 3) q.push(w[st]);
	for (int i = 0; i < 4; i ++) {
		int x = w[st].fi + dx[i], y = w[st].se + dy[i];
		if (cnt[x][y] == 3)
			q.push({x,y});
	}
	while (q.size()) {
		int ux = q.front().fi, uy = q.front().se;
		q.pop();
		
		if (cnt[ux][uy] != 3) continue;
		
		for (int i = 0; i < 4; i ++) {
			int vx = dx[i] + ux, vy = dy[i] + uy;
			if (flag[vx][vy]) continue;
			flag[vx][vy] = true;
			ans ++;
			update(vx,vy);
			if (cnt[vx][vy] == 3) q.push({vx,vy});
			for (int j = 0; j < 4; j ++) {
				int xx = vx + dx[j], yy = dy[j] + vy;
				if (cnt[xx][yy] == 3) q.push({xx,yy});
			}
			break;
		}
	}
}

int main() {
	n = fr();
	for (int i = 1; i <= n; i ++) {
		int x = fr() + 1000, y = fr() + 1000;
		w[i] = {x,y};
		if (flag[x][y]) {
			ans --;
			fw(ans);
			ch;
			continue;
		}
		flag[x][y] = true;
		bfs(i);
		fw(ans);
		ch;
	}
	return 0;
}

标签：fr,return,int,double,++,ans,集训,题单
From： https://www.cnblogs.com/jingyu0929/p/17777564.html

相关文章

2023 秋季学期六周集训 Misc方向
by高鹏鸿、密语写在前面，记录和交流是一个很好的习惯，建议可以自己先搭建一个博客用于存储自己的做题记录以及方便交流。还有，对于Misc方向，灵活应对十分重要，一定要善用搜索引擎。还有一点，给大家做的题有些能在网络上搜索到，大家实在实在坐牢很久了再去搜索工具搜索引擎新手......
牛客集训营提高组第二组第一题
题目描述：链接：https://ac.nowcoder.com/acm/contest/65193/A给定正整数n，计算n 个元素的集合{1,2,⋯ ,n}所有非空子集和的乘积取模998 244 353998后的结果。n≤200。解题思路，n小于等于200并且子集所有的取值为n^2级别的，考虑跑背包，f[i]表示子集和为i的方案数，可以算出子集和......
CSP2023 赛前集训总结
2023.09.18T1刘谋题面描述现在，反抗军首领大司马交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及骚猪帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一......
T2【noip赛前20天冲刺集训 day4】正在打模拟赛
@@【noip赛前20天冲刺集训day4】正在打模拟赛@@题目描述给定一棵包含n个点的树，每条边都有权值，同时给定一个整数k。定义一个树上连通块的权值为其中边权之和。你需要求解满足以下条件的树上连通块的权值最大值：这个连通块至多包含一个度数大于k的点。注意，这里的度数指的......
【noip赛前20天冲刺集训 day4】正在出模拟赛
题目描述想象学竞赛网站CodeFancy举办了\(m\)场比赛。你在CodeFancy上关注了\(n\)个账号，编号为\(1\)到\(n\)。你知道这\(n\)个账号分别参加了\(m\)场比赛中的哪些。但是你发现可能存在一个人使用多个账号的情况，你想知道这\(n\)个账号的使用者最少共有多少人。......
动物识别系统python+Django网页界面+TensorFlow算法模型+数据集训练
一、简介动物识别系统。基于Python+TensorFlow+Django网页框架+ResNet50算法模型实现实现步骤如下：收集多种动物的图片数据集，并整理归类然后使用TensorFlow搭建ResNet50算法模型网络对数据集进行多次迭代训练最后得到一个精度较高的H5模型文件基于训练好的模型，使用Django开......
noip赛前20天冲刺集训 day2 ###寻找有向图中的最小疲惫路径###
T1###寻找有向图中的最小疲惫路径###题目描述有一张n个点m条边的有向图，每条边上有一个正整数边权，你要顺着图上的有向边从1号点走到n号点。假设你经过的边边权依次为(w_1,w_2,\dots,w_t)，则你的疲惫程度为\[\f(w)=\max_{i=1}^{t}w_i\timesi\,.\]你需要找到最......
【noip赛前20天冲刺集训 day3】矩阵挑战
NOIP比赛前的冲刺训练-第3天：矩阵挑战问题描述您有一个n×m矩阵，行编号从0到n−1，列编号从0到m−1。最初，第i行第j列的元素是i*m+j。系统支持三种类型的操作：交换两行。交换两列。交换两个特定的元素。任务是确定执行q次操作后矩阵的状态。输入格式为了最小化输......
2023牛客OI赛前集训营-提高组（第二场）B.出租
2023牛客OI赛前集训营-提高组（第二场）B.出租B-出租_2023牛客OI赛前集训营-提高组（第二场）(nowcoder.com)目录2023牛客OI赛前集训营-提高组（第二场）B.出租题目大意思路题目大意在一条路上有\(n\)个栋楼，每栋楼上有\(k\)个房间出租。现在有\(m\)次询问，每次有两个数字\(x,y\)......
2023暑假集训总结
Part120230807~20230816这段时间主要是lyn学长给我们讲课。和上次寒假集训不同，这次lyn学长准备的东西难度非常之大，大部分都是NOI级的数据结构和算法，比如一些高难数论（exCRT、各种定理等等）、一些奇妙的DP优化、一些奇妙的数学期望、网络流、进阶的线段树，很难，感觉自己只......

赞助商

阅读排行