1. Y手上有n盒积木，每个积木有个重量。现在他想从每盒积木中拿一块积木，放在一起，这一堆积木的重量为每块积木的重量和。现在他想知道重量和最小的k种取法的重量分别是多少。（只要任意更换一块积木，就视为一种不同的取法。如果多种取法重量总和一样，我们需要输出多次。） 

$2 \leq n \leq 100, 2 \leq m_i \leq 100$

【题解】随便选几个来dp以下就行了。

# include <bits/stdc++.h>

using namespace std;

int n, K;
int m[110], w[110][110];

int f[110][10010];
//f[i,j]表示前i个，重量为k的方案数 


int main() {
	scanf("%d%d", &n, &K);
	for (int i=1; i<=n; ++i) {
		scanf("%d", &m[i]);
		for (int j=1; j<=m[i]; ++j) scanf("%d", &w[i][j]);
	}
	f[0][0] = 1; 
	for (int i=1; i<=n; ++i)
		for (int k=0; k<=10000; ++k) 
			for (int j=1; j<=m[i]; ++j) 
				if(k-w[i][j]>=0) f[i][k] += f[i-1][k-w[i][j]]; 
	
	for (int k=0; k<=10000 && K; ++k)
		if(f[n][k] > 0)  {
			for (int j=1; j<=f[n][k]; ++j) { 
				printf("%d ", k);
				--K;
				if(K==0) break; 
			}
		} 

	return 0;
}

2.小A打算开始炼NOI元丹（什么鬼），据说吃了可以提高NOI时的成绩。是这么练的。元丹有三种元核，'N','O','I'。现有很多个这样原核，按顺序排成一行。炼元丹时，从左往右分别挑出'N','O','I'三个原核吞下。现在他关心，有几种服用方式……且慢！他觉得服用方式太少，以至于不能成仙。所以他可以通过某个途径，得到'N','O','I'的三种原核中的任意一个，至于哪一种由他决定。然后他将获得这个原核的插入到这一排原核中的任意位置（包括最前最后）。现在你要知道，新的元核序列中能有多少种'N','O','I'的取出方式。子串的字母并不要求连续。

$n \leq 100000$

【题解】很明显枚举O前缀后缀两遍即可。如果加N一定加最前，加I一定加最后，加O枚举一下。

# include <bits/stdc++.h>

using namespace std;

int n;
char str[100010];

typedef long long ll;
int ns[100010], is[100010], tn[100010], ti[100010];
ll ans = 0;

int main() {
	scanf("%d", &n);
	scanf("%s", str+1);
	for (int i=1; i<=n; ++i)
		ns[i]=ns[i-1]+(str[i]=='N'),
		is[i]=is[i-1]+(str[i]=='I');
	// add n
	
	ll tans = 0;
	int lst, nxt;
	for (int i=1; i<=n; ++i) {
		if(str[i] == 'O') {
			lst = ns[i] - ns[0] + 1;
			nxt = is[n] - is[i-1];
			tans += 1ll * lst * nxt;
		}
	}
	if(tans > ans) ans = tans;
	
	// add i
	tans = 0;
	for (int i=1; i<=n; ++i) {
		if(str[i] == 'O') {
			lst = ns[i] - ns[0];
			nxt = is[n] - is[i-1] + 1;
			tans += 1ll * lst * nxt;
		}
	}
	if(tans > ans) ans = tans;

	// add o
	tans = 0;
	ll ttans= 0;
	for (int i=1; i<=n; ++i) {
		lst = ns[i] - ns[0];
		nxt = is[n] - is[i-1];
		if(str[i] == 'O') tans += 1ll * lst * nxt;
		if(1ll * lst * nxt > ttans) ttans = 1ll * nxt * lst;
	}
	tans += ttans;
	if(tans > ans) ans = tans;
	printf("%lld\n", ans);
	return 0;
}

3.博艾市除了有海底高铁连接中国大陆、台湾与日本，市区里也有很成熟的轨道交通系统。我们可以认为博艾地铁系统是一个无向连通图。博艾有N个地铁站，同时有M小段地铁连接两个不同的站。地铁计价方式很简单。从A站到B站，每经过一小段铁路（连接直接相邻的两个点的一条边），就要收取1博艾元。也就是说，从A站到B站，选择的路径不一样，要价也会不同。我们认为凡华中学在1号地铁站。学生们通过地铁通勤，他们当然知道选择最短路来坐车的话，票价最便宜。然而博艾地铁公司经营不善，一直亏损，于是他们打算提价。提价一次就是将一小段铁路原来收费1元改收2元。同一小段的铁路不会多次提价。他们打算提价Q次。学生们知道，如果他们到学校的一条最短路径中的一小段提价了，可以改变路径，使总票价不变。然而随着一条一条的铁路被提价，当居住在某个站附近的学生发现，提价后，没有任何一种方案可以从家到学校的费用和初始费用相等时，就会不满。现在地铁公司希望知道，对于每一次涨价，有多少个站，学生会因为涨价而不满呢？

$n, q \leq 100000$

【题解】时光倒流，每次填边松弛即可。注意到最短路只会被更新一次（？？？）然后就行啦

代码…懒得写了