NOIP2018 全国热身赛(无法完结!)

A. array

发现那个操作一可以毁灭地球呢

所以说我们直接在全局开两个标记即可

然后相当于查询一个单点值和等差数列求和

$a_1*n+n*(n-1)/2*d$

d是公差,a_1是首相

B. computer

发现直接求出最小生成树,然后在上面以1为根dfs即可

code:



#include<bits/stdc++.h>
using namespace std;
const int MAXN = 6e5 + 7;
int n, m;
struct rec {
	int x, y;
} e[MAXN];
int ans[MAXN], f[MAXN];
int home[MAXN], nxt[MAXN], to[MAXN], ccnt, id[MAXN];

inline void ct(int x, int y, int z) {
	ccnt++;
	id[ccnt] = z;
	to[ccnt] = y;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
}

inline int getf(int x) {
	return f[x] == x ? x : f[x] = getf(f[x]);
}

inline void dfs(int u, int F) {
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		ans[v] = max(ans[u], id[i]);
		dfs(v, u);
	}
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)f[i] = i;
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &e[i].x, &e[i].y);
		if(getf(e[i].x) != getf(e[i].y)) {
			f[getf(e[i].x)] = getf(e[i].y);
			ct(e[i].x, e[i].y, i);
			ct(e[i].y, e[i].x, i);
		}
	}
	for(int i = 1; i <= n; ++i)ans[i] = 1e9;
	ans[1] = 0;
	dfs(1, 0);
	for(int i = 1; i <= n; ++i)printf("%d\n", ans[i]);
	return 0;
}

A ball

维护这几个操作其实非常简单

推,相当于第一个数删除,然后除了最后一个数外所有数-1并移动到前一个位置,然后最后一个数变成 $P-x$

除非都堆在墙上连续了

不推,放球,我们可以随便开一个数据结构支持动态插入的,就做完了

$f_{i,j,0/1}$ 表示前i个数,我们用了j次交换操作的最小前缀和,j次交换操作的最大前缀和

转移考虑是否使用,以及使用几次???完蛋了!

并没有,你会发现这个相当于我们把后面的一段移动到前面,也就是说我们按照前面的345|123这样求出逆序对即是交换前后的代价

然后我们组合求答案的时候也一样,拼一下即可???

不对,如果我们相邻很近就会自闭,下面是题解

$f(i, a, b, c)$ 表示考虑前 $i$ 个，换进了 $a$ 个，换出了 $b$ 个，当前的位置是 $c(0/1/2)$ 的答案。其中 $0$ 是在选择的区间之前， $1$ 是在选择的区间之中， $2$ 是之后。每次 $O(1)$ 讨论一下当前位置的数的情况。

分类讨论超级恶心的好吧.....我真的服了

set维护所有黑白端点,按dfn序排序

然后会发现一段会导致这个区间公共LCA的siz成为一种颜色的贡献

然后都有了之后就能直接统计了,总的减去这些非灰就是灰的数量

http://csp.ac/problem/3

NOIP2019的模拟赛题....

考虑设计动态规划解决这个问题

$f_{i}$ 表示前i个字符的变为美丽串最小代价

转移枚举一个j,将j+1~i分为一段,进行转移

要预处理每个区间的最小代价

这个预处理发现如果我们固定了回文中心很好做

枚举一个回文中心i,然后左右向两边扩展即可,如果两边字符不同则用取 $min{w_i,w_j}$

时间复杂度 $O(n^2)$

http://csp.ac/problem/4

乐色计数题

一个子序列是好的,当且仅当排序后,从前到后每个数都小于他前面所有数的前缀和+1

而你发现这个值域只有5000,所以 $f_{i,j}$ 表示前i个数选出一些数前缀和为j的方案数

转移的时候,如果 $a_i$ 能放入就放入决策一下即可qwq,时间复杂度 $O(n^2)$

code:


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 7;
const int P = 1e9 + 7;
int n, a[MAXN], f[MAXN][MAXN], mx;

inline void add(int &x, int y) {
	x += y;
	if(x >= P)x -= P;
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		mx = max(mx, a[i]);
	}
	sort(a + 1, a + n + 1);
	f[0][0] = 1;//前0个数凑0
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j <= mx; ++j) {
			if(f[i][j]) {
				add(f[i + 1][j], f[i][j]);//不选
				if(j + 1 >= a[i + 1])
					add(f[i + 1][min(j + a[i + 1], mx)], f[i][j]);
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= mx; ++i)add(ans, f[n][i]);
	printf("%d\n", ans);
	return 0;
}

放爆竹(T2-2)
http://csp.ac/problem/10

每个串复制到最长串之后,再复制一倍即可

好像如果我们两个串如果能匹配超过原来的两倍,那没有理由之后不能再匹配下去,所以说这个东西直接建立Trie树即可

上界是 $a+b-gcd$ 而且取不到

证明?

于是乎做完了

pyy整队(T3-2)
http://csp.ac/problem/11

直接线段树即可,但是实现起来其实更想用set

但是这个后缀最大值并不好查询,所以还是线段树吧

硬查的话可以考虑二分一个值,然后从我们目标位置向后找后继?不行

线段树实现的时候就开三倍下标,然后每个都记录的是这个位置上的人,修改直接挪点空间即可,最后把所有人都查一遍

不难发现,我们一定是让最长连续的一段固定其他同学向他们靠拢而已

http://csp.ac/problem/12

sb构造,之前还吐槽毒瘤

排序,按照字符串从短到长贪心使用:a,b,c,d.......aa,ab,ac,ad......

这个具体的可以在字典树上建26^3个节点,然后bfs/se

夏晓光(loveJY)的博客

ARC杂题选讲P3