洛谷10月月赛Round 3题解

tonyfang posted @ 2016年11月03日 22:32 in 随笔 with tags C++ OI , 205 阅读

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$

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

代码…懒得写了

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter