【题解】NOIP普及组2019

用了大概一个晚自习来做这四道题,顺便复习一下以前学过的知识。

A. 数字游戏

签到题。。。

#include <iostream>
using namespace std;
string s;
int ans;
int main() {
cin >> s;
for (int i = 0; i < s.size(); i++)
if (s[i] == '1')
ans++;
cout << ans;
}

B.公交换乘

按题意模拟即可。

    若type==0,累加花费,从优先队列中压入二元组(x,y),x表示花费,y表示时间。
    若type==1,首先去掉超时的项。然后一直top,直到q.top().x>=x。将之前top的又push回去(不包括当前选择的项)。
    输出ans。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

struct node {
int x, y;
friend bool operator<(node a, node b) { return a.y > b.y; }
node() {}
node(int X, int Y) { x = X, y = Y; }
};

int n, ans, tot;
priority_queue<node> q;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
if (!x) {
ans += y;
q.push(node(y, z));
} else {
bool flag = 0;
queue<node> p;
while (q.size() && z - q.top().y > 45) q.pop();
while (q.size()) {
node t = q.top();
q.pop();
if (t.x >= y) {
flag = 1;
break;
}
p.push(t);
}
if (!flag)
ans += y;
while (p.size()) {
q.push(p.front());
p.pop();
}
}
}
printf("%d", ans);
}

C.纪念品

本题笔者并没有做出来。。。

分析:
正解是背包。
背包问题最重要的是弄清楚价值和背包容量。首先理解题意,假如要记录所有当前已买纪念品,显然是不可能的。

所以,当天买的纪念品,第二天必须全部卖掉。为什么呢?假设你在第i天买了t个物品j,价值是price[i][j],第二天则变成了price[i+1][j]。此时保留这t个纪念品,等价于先以price[i+1][j]卖掉,再以price[i+1][j]买回来,手中的钱不变。

结论:在第i天,拥有纪念品和拥有它的价值是一样的。

就好像炒股,只不过没有了买入卖出的手续费。

所以,背包就是第i天的钱数,买物品j的价值就是price[i+1][j]-price[i][j](这里的价值是买它所获得的利润),j的体积就是price[i][j].

dp[k]=max(dp[k],dp[kprice[i][j]]+price[i+1][j]price[i][j]) dp[k]=max(dp[k],dp[k-price[i][j]]+price[i+1][j]-price[i][j])

dp[k]=max(dp[k],dp[k−price[i][j]]+price[i+1][j]−price[i][j])

我们把每天都额外加上前一天的ans元钱能获得的最大利润,重复t天,就得到了答案。

#include<bits/stdc++.h>
using namespace std;
const int N=105;
const int M=10005;

int t,n,m,cost[N][N],dp[M],ans;

int main() {
scanf("%d%d%d",&t,&n,&m);
for(int i=1;i<=t;i++)
for(int j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
ans=m;
for(int i=1;i<t;i++) {
memset(dp,0,sizeof(dp));
for(int j=1;j<=n;j++) {
for(int k=cost[i][j];k<=ans;k++) {
dp[k]=max(dp[k],dp[k-cost[i][j]]+cost[i+1][j]-cost[i][j]);
}
}
ans+=dp[ans];
}
printf("%d",ans);
}

这道题也不是特别难(码量不大),但一定要弄明白每个量的含义,以及容量、价值和体积。

说白了就是忘了背包怎么做了

D.加工零件

感觉比上一道好想点。

分析:
本题的关键在于:你不能照搬L(L<=1e9),假如从(a,l)开始搜索,一直搜到(1,0),一定会超时。

一句话题意:问是否有从1到a的长度为L的路径。

自然而然想到最短路。因为路径可逆,所以选择1为起点。假设dis[a]>L,显然不可能;若dis[a]<=L,我们选择分析奇偶性。因为从a到a一定存在长度为2的路径。

然后拆点:

for(int i=1,x,y;i<=m;i++) {
//奇偶性相同的连边
scanf("%d%d",&x,&y);
son[x].push_back(y+n);
son[y+n].push_back(x);
son[y].push_back(x+n);
son[x+n].push_back(y);
}

注意光判断奇偶性还不行,必须当最短路<=L才行。假设有两个非常远的点,那么L太小是一定传递不过去的。

ac代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;

int n,m,q,dis[N];
vector<int> son[N];

void dijkstra() {
memset(dis,0x3f,sizeof(dis));
queue<int> q;
q.push(1);
dis[1]=0;
while(q.size()) {
int x=q.front();q.pop();
for(int i=0;i<son[x].size();i++) {
int y=son[x][i];
if(dis[x]+1<dis[y]) {
dis[y]=dis[x]+1;
q.push(y);
}
}
}
}

int main() {
scanf("%d%d%d",&n,&m,&q);
for(int i=1,x,y;i<=m;i++) {
scanf("%d%d",&x,&y);
son[x].push_back(y+n);
son[y+n].push_back(x);
son[y].push_back(x+n);
son[x+n].push_back(y);
}

dijkstra();

for(int i=1;i<=q;i++) {
int x,y;
scanf("%d%d",&x,&y);
//若y为奇数,则应该找x+n到1的路径长度
if((y%2==0&&dis[x]<=y)||(y%2==1&&dis[x+n]<=y))
printf("Yes\n");
else printf("No\n");
}
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【题解】NOIP普及组2019

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【题解】NOIP普及组2019
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏