Java教程

$NOIP\ 2018\ Day1$ 模拟考试 题解报告

本文主要是介绍$NOIP\ 2018\ Day1$ 模拟考试 题解报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • $NOIP\ 2018\ Day1$ 模拟考试 题解报告
    • 得分情况
    • 考试过程
    • 题解
      • $T1$ 铺设道路
      • $T2$ 货币系统
      • $T3$ 赛道修建

\(NOIP\ 2018\ Day1\) 模拟考试 题解报告

得分情况

\(T1\ 100\ Pts\)

\(T2\ 100\ Pts\)

\(T3\ 55\ Pts\)

总分: \(255\ Pts\)

考试过程

五分钟过 \(T1\)

二十分钟过 \(T2\)

一个小时写完 \(T3\) 部分分

弃 再之后没有什么进展

题解

感觉像是贪心专场

众所周知 贪心不需要证明

\(T1\) 铺设道路

贪心

前面比后面的大 答案累加两者的差

/*
  Time: 6.5
  Worker: Blank_space
  Source: 
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#define int long long
/*--------------------------------------头文件*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 1e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
inline void File() {
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout);
}
/*----------------------------------------文件*/
int n, d[B], ans;
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
/*----------------------------------------快读*/

/*----------------------------------------函数*/
signed main() {
	File();
	n = read(); d[n + 1] = 0;
	for(int i = 1; i <= n; i++) d[i] = read();
	for(int i = 1; i <= n; i++) if(d[i] > d[i + 1]) ans += d[i] - d[i + 1];
	printf("%lld", ans);
	return 0;
}
/*
贪心
五分钟 过大样例 
*/

\(T2\) 货币系统

完全背包裸题

注意一下容量取最大值就能过

/*
  Time: 6.5
  Worker: Blank_space
  Source: 
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Max(x, y) ((x) > (y) ? (x) : (y)) 
#define emm(x) memset(x, 0, sizeof x)
/*--------------------------------------头文件*/
const int B = 1e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
inline void File() {
	freopen("money.in", "r", stdin);
	freopen("money.out", "w", stdout);
}
/*----------------------------------------文件*/
int T, n, a[110], m, ans;
bool f[B], vis[110];
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
/*----------------------------------------快读*/
void work() {
	n = read(); ans = n; emm(f); emm(vis); f[0] = 1; m = 0;
	for(int i = 1; i <= n; i++) a[i] = read(), m = Max(m, a[i]), vis[i] = 1;
	std::sort(a + 1, a + 1 + n);
	for(int i = 1; i <= n; i++)
	{
		for(int j = a[i]; j <= m; j++) f[j] |= f[j - a[i]];
		for(int j = i + 1; j <= n; j++) if(vis[j] && f[a[j]]) vis[j] = 0, ans--;
	}
	printf("%d\n", ans);
}
/*----------------------------------------函数*/
int main() {
	File(); 
	T = read(); while(T--) work();
	return 0;
}
/*
2
4
3 19 10 6
5
11 29 13 19 17

有点类似背包 完全背包 
n 比较小 
缀和求容量 
贪一下 小的放在前面 跑个背包
小样例过了 大样例过了 但是跑的有点慢 跑了五秒多  
只需要考虑能否凑出 容量从前缀和改为最大值 过了 
20分钟 过大样例 
*/

\(T3\) 赛道修建

\(55\) 的部分分是送的 略过了

代码

/*
  Time: 6.5
  Worker: Blank_space
  Source:
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define Swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
/*--------------------------------------头文件*/
const int A = 5e4 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
inline void File() {
	freopen("track.in", "r", stdin);
	freopen("track.out", "w", stdout);
}
/*----------------------------------------文件*/
int n, m, du[A], f[A], g[A], ans, maxdu, sum, cnt, _d, dp[A];
struct node {int u, v, w;} a[A];
struct edge {int v, w, nxt;} e[A << 1];
int head[A], ecnt;
std::pair <int, int> d[A];
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
/*----------------------------------------快读*/
void add_edge(int u, int v, int w) {e[++ecnt] = (edge){v, w, head[u]}; head[u] = ecnt;}
void dfs1(int u, int pre) {
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v, w = e[i].w;
		if(v == pre) continue;
		dfs1(v, u);
		if(f[v] + w > f[u]) g[u] = f[u], f[u] = f[v] + w;
		else if(f[v] + w > g[u]) g[u] = f[v] + w;
	}
	ans = Max(ans, f[u] + g[u]);
}
void work1() {
	dfs1(1, 0);
	printf("%lld", ans);
}
void dfs2(int u, int pre, int _s, int x) {
	if(_s >= x) cnt++, _s = 0;
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v, w = e[i].w;
		if(v == pre) continue;
		dfs2(v, u, _s + w, x);
	}
}
bool check2(int x) {
	cnt = 0; dfs2(1, 0, 0, x);
	return cnt >= m;
}
void work2() {
	int l = 0, r = sum;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(check2(mid)) l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	printf("%lld", ans);
}
bool cmp(node x, node y) {return x.w > y.w;}
bool check3(int x) {
	cnt = 0;
	for(int i = 1, j = n - 1; i <= j; i++)
	{
		if(a[i].w >= x) cnt++;
		else
		{
			if(i == j) break;
			while(a[i].w + a[j].w < x && i < j - 1) j--;
			if(a[i].w + a[j].w >= x) cnt++, j--;
			else break;
		}
	}
	return cnt >= m;
}
void work3() {
	std::sort(a + 1, a + n, cmp);
	int l = 0, r = sum;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(check3(mid)) l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	printf("%lld", ans);
}
/*----------------------------------------函数*/
signed main() {
	File(); 
	n = read(); m = read();
	for(int i = 1; i < n; i++)
	{
		int x = read(), y = read(), z = read();
		a[i] = (node){x, y, z}; sum += z;
		du[x]++; du[y]++; maxdu = Max(maxdu, Max(du[x], du[y]));
		add_edge(x, y, z); add_edge(y, x, z);
	}
	if(m == 1) work1();
	else if(maxdu == 2) work2();
	else if(maxdu == n - 1) work3();
	else puts("18109");
	return 0;
}
/*
最小最大 二分答案 先扔了 看数据 
m = 1 树的直径 20
7 1
1 2 10
1 3 5
2 4 9
2 5 8
3 6 6
3 7 7

链 20
每条赛道一定是连续的一段 二分答案 进行check 
二分一个最小值 
8 x
1 2 7
3 4 2
2 3 3
7 8 1
6 7 4
5 6 5
4 5 6

过小样例 应该差不多 

菊花图 15 
一条赛道最多只能有两条边
二分答案 进行check
按边权排序 双指针 贪 
10 x
1 3 6
1 10 1
1 2 8
1 4 9
1 9 7
1 5 3
1 6 4
1 7 2
1 8 8

过小样例 跑路 

大概能过前 11 个点 

二叉树 25 
12 - 16
没思路 感觉这个已经接近正解了

尝试开正解 

一棵树 最多只能有一条边连出去
贪一下 能在子树内连的尽量在子树内连
尝试维护唯一一条连出去的边
一定是除却已经连接的边的最长的边
父节点中 用所有儿子中连出的这条边进行相互匹配 

排序在匹配复杂度爆炸 

写不出来 弃了 

卒 
*/

正解

看题很自然的想到二分答案 而且发现我上面那个贪心思路是对的... 想到了排序内部匹配 没想到二分查找 假掉了

二分一个最小值 进行check

直接递归到最底层 回溯的时候在每一棵子树内进行自匹配 对于一条没有被选过的边 通过排序 + 二分查找 找一条最短的能够满足条件的边进行匹配 并把这条边标记 对于每一个节点 维护从这棵子树内出去(还没有被匹配)的最长的链 再回过头来看上面的自匹配 把当前节点的以儿子节点为根的子树内出来的最长链加上那一条边 再存一个数组 排序后在这个数组中进行操作

代码

/*
  Time: 6.5
  Worker: Blank_space
  Source:
*/
/*--------------------------------------------*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define Swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
/*--------------------------------------头文件*/
const int A = 5e4 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*------------------------------------常量定义*/
inline void File() {
	freopen("track.in", "r", stdin);
	freopen("track.out", "w", stdout);
}
/*----------------------------------------文件*/
int n, m, du[A], f[A], g[A], ans, maxdu, sum, cnt, q[A], K, dp[A], vis[A];
struct node {int u, v, w;} a[A];
struct edge {int v, w, nxt;} e[A << 1];
int head[A], ecnt;
/*------------------------------------变量定义*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
/*----------------------------------------快读*/
void add_edge(int u, int v, int w) {e[++ecnt] = (edge){v, w, head[u]}; head[u] = ecnt;}
void dfs1(int u, int pre) {
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v, w = e[i].w;
		if(v == pre) continue;
		dfs1(v, u);
		if(f[v] + w > f[u]) g[u] = f[u], f[u] = f[v] + w;
		else if(f[v] + w > g[u]) g[u] = f[v] + w;
	}
	ans = Max(ans, f[u] + g[u]);
}
void work1() {
	dfs1(1, 0);
	printf("%lld", ans);
}
void dfs2(int u, int pre, int _s, int x) {
	if(_s >= x) cnt++, _s = 0;
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v, w = e[i].w;
		if(v == pre) continue;
		dfs2(v, u, _s + w, x);
	}
}
bool check2(int x) {
	cnt = 0; dfs2(1, 0, 0, x);
	return cnt >= m;
}
void work2() {
	int l = 0, r = sum;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(check2(mid)) l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	printf("%lld", ans);
}
bool cmp(node x, node y) {return x.w > y.w;}
bool check3(int x) {
	cnt = 0;
	for(int i = 1, j = n - 1; i <= j; i++)
	{
		if(a[i].w >= x) cnt++;
		else
		{
			if(i == j) break;
			while(a[i].w + a[j].w < x && i < j - 1) j--;
			if(a[i].w + a[j].w >= x) cnt++, j--;
			else break;
		}
	}
	return cnt >= m;
}
void work3() {
	std::sort(a + 1, a + n, cmp);
	int l = 0, r = sum;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(check3(mid)) l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	printf("%lld", ans);
}
void dfs(int u, int pre, int x) {
	for(int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v) if(v != pre) dfs(v, u, x);
	K = 0; dp[u] = 0;
	for(int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v) if(v != pre) q[++K] = dp[v] + e[i].w;
	std::sort(q + 1, q + 1 + K);
	for(int i = K; i && q[i] >= x; i--) cnt++, K--;
	for(int i = 1; i <= K; i++) if(vis[i] != u)
	{
		int L = i + 1, R = K, pos = K + 1;
		while(L <= R)
		{
			int Mid = L + R >> 1;
			if(q[i] + q[Mid] >= x) pos = Mid, R = Mid - 1;
			else L = Mid + 1;
		}
		while(vis[pos] == u && pos <= K) pos++;
		if(pos <= K) vis[i] = vis[pos] = u, cnt++;
	}
	for(int i = K; i; i--) if(vis[i] != u) {dp[u] = q[i]; break;}
}
bool check(int x) {
	memset(vis, 0, sizeof vis);
	cnt = 0; dfs(1, 0, x);
	return cnt >= m;
}
void work() {
	int l = 0, r = sum;
	while(l <= r)
	{
		int mid = l + r >> 1;
		if(check(mid)) l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	printf("%lld", ans);
}
/*----------------------------------------函数*/
signed main() {
	File(); 
	n = read(); m = read();
	for(int i = 1; i < n; i++)
	{
		int x = read(), y = read(), z = read();
		a[i] = (node){x, y, z}; sum += z;
		du[x]++; du[y]++; maxdu = Max(maxdu, Max(du[x], du[y]));
		add_edge(x, y, z); add_edge(y, x, z);
	}
	if(m == 1) work1();
	else if(maxdu == 2) work2();
	else if(maxdu == n - 1) work3();
	else work();
	return 0;
}
/*
最小最大 二分答案 先扔了 看数据 
m = 1 树的直径 20
7 1
1 2 10
1 3 5
2 4 9
2 5 8
3 6 6
3 7 7

链 20
每条赛道一定是连续的一段 二分答案 进行check 
二分一个最小值 
8 x
1 2 7
3 4 2
2 3 3
7 8 1
6 7 4
5 6 5
4 5 6

过小样例 应该差不多 

菊花图 15 
一条赛道最多只能有两条边
二分答案 进行check
按边权排序 双指针 贪 
10 x
1 3 6
1 10 1
1 2 8
1 4 9
1 9 7
1 5 3
1 6 4
1 7 2
1 8 8

过小样例 跑路 

大概能过前 11 个点 

二叉树 25 
12 - 16
没思路 感觉这个已经接近正解了

尝试直接开正解 

一棵树 最多只能有一条边连出去
贪一下 能在子树内连的尽量在子树内连
尝试维护唯一一条连出去的边
一定是除却已经连接的边的最长的边
父节点中 用所有儿子中连出的这条边进行相互匹配 

排序在匹配复杂度爆炸 

写不出来 弃了 

卒 
*/
这篇关于$NOIP\ 2018\ Day1$ 模拟考试 题解报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!