2019CSP
题意描述
小 K 同学向小 P 同学发送了一个长度为 8 的 01 字符串来玩数字游戏，小 P 同学想 要知道字符串中究竟有多少个 1。
注意：01 字符串为每一个字符是 0 或者 1 的字符串，如“101”（不含双引号）为一 个长度为 3 的 01 字符串。
解题思路
签到题。
代码示例
#include<bits/stdc++.h> using namespace std; string str; int cnt = 0; int main(){cin >> str;for(int i = 0;str[i];i++) if(str[i] == '1') cnt++;cout << cnt << endl;return 0; }
cpp
12345678910 B.公车换乘题意描述
著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交 车的优惠方案：在搭乘一次地铁后可以获得一张优惠票，有效期为 45 分钟，在有效期内可以 消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。在有效期内指 开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟，即：tbus−tsubway≤45t_{bus} - t_{subway} ≤ 45tbus−tsubway≤45。
搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优 惠票搭乘公交车。搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满 足条件，则优先消耗获得最早的优惠票。
现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗？
解题思路
一道模拟题，显而易见需要按照时间升序，因为如果超过45分钟就无效了。基于此应该想到可以利用优先队列（或类似）的数据结构来维护，每次坐公交，在所有价值大于本次票价的优惠券中优先使用过期时间最早的（不用就过期了！），价值最低的优惠券。一旦票过期了，就删掉，但是如果票只是价值不够，那可能后面还会有用，所以还要压回去。
代码示例
#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; typedef long long ll; struct Node{int ty;ll t,price;bool operator < (const Node& rhs) const{if(t == rhs.t) return price > rhs.price;return t > rhs.t;} }rd[N]; int n; priority_queue<Node> q; stack<Node> s; void solve(){sort(rd+1,rd+1+n);ll res = 0;for(int i = n;i >= 1;i--){if(!rd[i].ty){res += rd[i].price, q.push(rd[i]);continue;}bool flag = true;while(q.size()){Node x = q.top(); q.pop();if(rd[i].t - x.t > 45) continue;if(x.price < rd[i].price){s.push(x); continue;}flag = false; break;}if(flag) res += rd[i].price;while(s.size()) q.push(s.top()), s.pop();}printf("%lldn",res); } int main(){scanf("%d",&n);for(int i = 1;i <= n;i++)scanf("%d%d%d",&rd[i].ty,&rd[i].price,&rd[i].t);solve();return 0; }
cpp
1234567891011121314151617181920212223242526272829303132333435363738394041424344 C.纪念品题意描述
小伟突然获得一种超能力，他知道未来 T 天 N 种纪念品每天的价格。某个纪念品 的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。
每天，小伟可以进行以下两种交易无限次：
任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；卖出持有的任意一个纪念品，以当日价格换回金币。
每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。
T 天之后，小伟的超能力消失。因此他一定会在第 T 天卖出所有纪念品换回金币。
小伟现在有 M 枚金币，他想要在超能力消失后拥有尽可能多的金币。
解题思路
本题思路可以根据数据范围来想。这是一道动态规划题。
刚开始想到的是建立一张全图，但是后来发现节点数量不是 N 而是 NT ，并且总价值也不一定只能走一条路。
后来发现可以用动态规划解决，首先设 f[x]: 第x天能够赚到最多多少钱。那么显然f[1] = m，并且 f 是递增的。重点在于状态转移，f[ i ] 肯定是由 f[ 1~i-1 ] 推出来的，因为单独一个 f[i-1] 无法表示所有状态。
假设当前处于状态 j （j < i），那么将第 j 天物品的价格看作花费，第 i 天的物品价格看作价值，这就是一个完全背包问题，背包容量是当天的金币数 f[j] 。
于是我们两层循环O(T^2)来计算 f[i] ，而每次计算需要O(MN) 做完全背包，但是实际测试效率还行，可能是数据太弱了。
代码示例
#include<bits/stdc++.h> using namespace std; const int N = 1e2+10; const int M = 1e4+10; int t,n,m; int val[N][N]; int f[N];//第 x 天最多有多少钱 int tmp[M],mx; void solve(){f[1] = m;for(int day = 2;day <= t;day++){for(int i = 1;i < day;i++){memset(tmp,0,sizeof tmp); mx = m;for(int j = 1;j <= n;j++){for(int v = val[i][j]; v <= f[i];v++){tmp[v] = max(tmp[v-val[i][j]]+val[day][j],tmp[v]);mx = max(mx,tmp[v]+f[i]-v);}}f[day] = max(f[day],mx);}f[day] = max(f[day],f[day-1]);}//for(int i = 1;i <= t;i++) printf("%dn",f[i]);printf("%dn",f[t]); } 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",&val[i][j]);solve();return 0; }
cpp
123456789101112131415161718192021222324252627282930313233 D.加工零件题意描述
凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很 神奇。工厂里有 位工人，工人们从 1∼编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。
如果 号工人想生产一个被加工到第 (>1) 阶段的零件，则所有与 号工人 有传送带直接相连的工人，都需要生产一个被加工到第 −1 阶段的零件（但 号工 人自己无需生产第 −1 阶段的零件）。
如果 号工人想生产一个被加工到第 1 阶段的零件，则所有与 号工人有传送 带直接相连的工人，都需要为 号工人提供一个原材料。
轩轩是 1 号工人。现在给出 张工单，第 张工单表示编号为 的工人想生产 一个第 阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来！
解题思路
经过推导可以发现，如果 a 号节点到 1 号节点（以下只用编号简写）之间存在一条小于 L 的路径，且它们的差为偶数（包括0），那么 1 就要提供原材料。
但是问题在于 1 到 a 之间可能不止一条路径，而 L 也不一定是奇或者偶，于是我们需要保存 a 到 1 的最短奇路径与最短偶路径。
在图论中，如果边权为1，那么求奇偶最短路径的好方法就是用分层图来做，具体做法是建立双层图，如果从起点不在同一层，则路径一定是奇，否则一定为偶；这样做的好处是不用额外的辅助代码，只要在建图时多加两条边就行了。
代码示例
#include<bits/stdc++.h> using namespace std; const int N = 2e5+10; const int M = 2*N; typedef long long ll; int n,m,q; int head[N],edge[M],ver[M],nex[M] ,tot = 1; void addEdge(int x,int y,int z){ver[++tot] = y; edge[tot] = z;nex[tot] = head[x]; head[x] = tot; } int getInt(){int res = 0;bool neg = false;char c = getchar();while(c != '-' && (c < '0' || c > '9')) c = getchar();if(c == '-') neg = true, c = getchar();while(c >= '0' && c <= '9') res = res*10+c-'0',c = getchar();return neg?-res:res; } queue<int> que; int dis[N],vis[N]; bool solve(int a,int l){if(dis[a] <= l && !((dis[a]&1) ^ (l&1))) return true;if(dis[a+n] <= l && !((dis[a+n]&1) ^ (l&1))) return true;return false; } void SPFA(int s){que.push(s);memset(dis,0x3f,sizeof dis);dis[s] = 0;while(que.size()){int x = que.front(); que.pop();vis[x] = false;for(int i = head[x];i ;i = nex[i]){int y = ver[i], z = edge[i];if(dis[y] > dis[x]+z){dis[y] = dis[x]+z;if(!vis[y]) que.push(y),vis[y] = true;}}} } int main(){n = getInt(); m = getInt(); q = getInt();for(int i = 1,x,y;i <= m;i++){x = getInt(); y = getInt();addEdge(x,y+n,1); addEdge(y+n,x,1);addEdge(x+n,y,1); addEdge(y,x+n,1);}SPFA(1);//for(int i = 1;i <= n<<1;i++) cout << dis[i] << endl;for(int i = 1,a,l;i <= q;i++){a = getInt(); l = getInt();if(solve(a,l)) puts("Yes");else puts("No");}return 0; }
cpp
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859相关知识
网址: 2019CSP https://m.mcbbbk.com/newsview1337668.html
| 上一篇: JavaScript 逻辑或 |
下一篇: 上海火车托运宠物狗 |
