洛谷10月月赛Round 3题解

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

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$

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

代码…懒得写了

 

model-paper.com 说:
2023年4月19日 16:46

While Modelpapers strives to provide better service in various ways and does not sell or give away your personal information other than what you want to make public, there are instances in which your mail may be model-paper.com exposed to the public. We are very aware of email spam and make every effort to protect every email.


登录 *


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