NOIP 2018 提高组 真题

D1T1铺设道路

时间限制：$1s$
空间限制：$512MB$

题目描述

春春是一名道路工程师，负责铺设一条长度为 n 的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 $n$ 块首尾相连的区域，一开始，第 $i$ 块区域下陷的深度为 $di$。
春春每天可以选择一段连续区间 $[L,R]$，填充这段区间中的每块区域，让其下陷深度减少 $1$
在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 $0$
春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 $0$。

输入格式

输入文件包含两行，第一行包含一个整数 $n$，表示道路的长度
第二行包含 $n$ 个整数，相邻两数间用一个空格隔开，第 $i$ 个整数为 $di$

输出格式

输出文件仅包含一个整数，即最少需要多少天才能完成任务。

样例数据

input
6   
4 3 2 5 3 5
output
9

样例说明

一种可行的最佳方案是，依次选择： $[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]$

数据规模与约定

对于 $30$% 的数据，$1\le n\le 10$ ；
对于 $70$% 的数据，$1\le n\le 1000$ ；
对于 $100$% 的数据，$1\le n\le 100000,0\le di\le 100001\le n\le 100000,0\le di\le 10000$
单调队列维护即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;int n, ans, tot;
int a[100010], q[100010];inline void init() {
    scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
}inline void work() {
    q[++tot] = a[1];for(int i = 2; i <= n; i++){
    if(a[i] <= q[tot] && tot) ans += q[tot--]-a[i];while(a[i] <= q[tot] && tot) tot--;q[++tot] = a[i];}
}inline void outo() {
    printf("%d", ans+q[tot]);
}
int main() {
    init();work();outo();return 0;
}

D1T2货币系统

时间限制：$1s$
空间限制：$512MB$

题目描述

在网友的国度中共有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a[i]$，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 $n$、面额数组为 $a[1..n]$ 的货币系统记作 $(n,a)$。
在一个完善的货币系统中，每一个非负整数的金额 $x$ 都应该可以被表示出，即对每一个非负整数 $x$，都存在 n 个非负整数 $t[i]$ 满足 $a[i]\times t[i]$ 的和为 $x$。然而， 在网友的国度中，货币系统可能是不完善的，即可能存在金额 $x$ 不能被该货币系统表示出。例如在货币系统 $n=3,a=[2,5,9]$中，金额 $1,3$ 就无法被表示出来。
两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的，当且仅当对于任意非负整数 $x$，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统 $(m,b)$，满足 $(m,b)$ 与原来的货币系统 $(n,a)$ 等价，且 $m$尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 $m$

输入格式

输入文件的第一行包含一个整数 $T$，表示数据的组数。
接下来按照如下格式分别给出 $T$ 组数据。 每组数据的第一行包含一个正整数 $n$
接下来一行包含 $n$ 个由空格隔开的正整数 $a[i]$。

输出格式

输出文件共有 $T$ 行，对于每组数据，输出一行一个正整数，表示所有与 $(n,a)$等价的货币系统 $(m,b)$ 中，最小的 $m$

样例数据

input
2 
4 
3 19 10 6 
5 
11 29 13 19 17
output
2
5

样例说明

在第一组数据中，货币系统 $(2,[3,10])$ 和给出的货币系统 $(n,a)$ 等价，并可以验证不存在 $m＜2$ 的等价的货币系统，因此答案为 $2$。 在第二组数据中，可以验证不存在 $m＜n$的等价的货币系统，因此答案为 $5$。

数据规模与约定

对于 $100$% 的数据，满足 $1\le T\le 20,n,a[i]\ge 1$

由题意可推，b必为a的子集
因为要使b中的元素最少，我们可以想象成b先复制一份a数组，然后再去掉一些并非必要的数即可
什么是并非必要的数呢？如果a集合中的某一个数可以由a集合中另外的数组成，这个数就不是必要的数

#include<bits/stdc++.h>
#define ll long long
using namespace std;int n, a[105], f[25005], ans, T;inline void init() {
    scanf("%d", &n);memset(f, 0, sizeof f);for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);f[a[i]] = 2;//2表示a集合原先存在的数}sort(a+1, a+1+n);
}inline void work() {
    ans = 0;for(int i = 1; i <= a[n]; i++) for(int j = 1; j <= n && f[i]; j++)if(i+a[j] <= a[n]) f[a[j]+i] = 1;//1表示可以拼凑出来的数for(int i = 1; i <= n; i++)if(f[a[i]] == 2) ans++;//原a集合中有多少个数不能被拼凑，就是必要的数
}inline void outo() {
    printf("%d\n", ans);
}
int main() {
    scanf("%d", &T);while(T--) {
    init();work();outo();}return 0;
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 5e3+10;
int n, m, len, dep, xx, yy;
int lin[N], ans[N], res[N];
bool vis[N];
vector<int> vec[N];
struct psx{
    int next, x, y;}e[N<<1];inline void insert(int x, int y) {
    e[++len].next = lin[x];e[len].x = x;e[len].y = y;lin[x] = len;
}inline void init() {
    scanf("%d%d", &n, &m);for(int i = 1, v, u; i <= m; i++) {
    scanf("%d%d", &u, &v);insert(u, v);insert(v, u);vec[v].push_back(u);vec[u].push_back(v);}for(int i = 1; i <= n; i++)sort(vec[i].begin(), vec[i].end());
}inline void dfs1(int x, int fa) {
    if(vis[x]) return;vis[x] = 1;ans[++dep] = x;for(int i = 0; i < vec[x].size(); i++) {
    int y = vec[x][i];if(y == fa) continue;dfs1(y, x);}
}inline void dfs2(int x, int fa) {
    if(vis[x]) return; vis[x] = 1;res[++dep] = x;for(int i = 0; i < vec[x].size(); i++) {
    int y = vec[x][i];if(y == fa) continue;if((y==xx && x==yy) || (y==yy && x==xx)) continue;dfs2(y, x);}
}inline bool check() {
    for(int i = 1; i <= n; i++) {
    if(res[i] < ans[i]) return 1;if(res[i] > ans[i]) return 0;}
}inline void change() {
    for(int i = 1; i <= n; i++)ans[i] = res[i];
}inline void work() {
    if(m == n-1) {
    dep = 0;dfs1(1, 0);return;}//如果是一棵树for(int i = 1; i <= len; i += 2) {
    dep = 0;xx = e[i].x;yy = e[i].y;//记录删去边的信息memset(vis, 0, sizeof vis);dfs2(1, 0);if(dep < n) continue;if(!ans[1]) change();else if(check()) change();//更新答案}//基环树，每次枚举删去其中一条边，选择字典序最小的方案
}inline void outo() {
    for(int i = 1; i <= n; i++)printf("%d ", ans[i]);
}
int main() {
    init();work();outo();return 0;
}

65分部分分

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int mod = 1e9+7;
int n, m;
inline void init() {
    scanf("%d%d",&n,&m);
}
inline int P(int a,int b) {
    int c = 1;while(b){
    if(b&1) c = 1LL*c*a%mod;a = 1LL*a*a%mod;b >>= 1;} return c;
}
inline void work() {
    if(n == 2) {
    printf("%d\n",4LL*P(3,m-1)%mod);return;};if(n == 3)  {
    if(m == 1) puts("8");else if (m == 2) puts("36");else if (m == 3) puts("112");else printf("%d\n",112LL*P(3,m-3)%mod);return;}
}int main() {
    init();work();return 0;
}