本文主要是介绍8.21 补题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
六题
C 16进制世界
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
这是一个16进制的世界，比如522的16进制是20A。
在5月22日那天，有人送给Bob一些月饼，每个月饼有饱食度和幸福度两个属性。
现在Bob有n个月饼，对于每个月饼iii，饱食度为vi，幸福度为wi。
Bob现在有m饱食度，意味着他吃的月饼的饱食度之和不大于m。
但是由于Bob身处16进制的世界，他吃的月饼的幸福度之和必须是16的倍数。
请帮Bob算一下他最多吃的月饼的数量。
输入描述:
第一行输入两个整数n, m接下来n行分别输入vi, wi表示第i个月饼的饱食度和幸福度。输入数据保证1≤n⋅m≤105。
输出描述:
一个整数，表示Bob最多能吃的月饼数量
示例1
输入
2 5 2 16 3 15
输出
1
思路
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int dp[100005][16];//dp[k1][k2]表示当前月饼数 k2表示 mod 16的值
signed main() {cin >> n >> m;vector<int> m1(n);vector<int> m2(n);for (int i = 0; i < n; ++i) {cin >> m1[i] >> m2[i];}memset(dp, -1, sizeof(dp));dp[0][0] = 0;for (int i=0;i<n;i++) {int v = m1[i];int w = m2[i];for (int j = m; j >= v; --j) { for (int k = 0; k < 16; ++k) { //遍历0--15 各个位置的dpif (dp[j - v][k] != -1) { int h = (k + w) % 16;//现在跟上一个比较 上一个要加一个dp[j][h] = max(dp[j][h], dp[j - v][k] + 1);}}}}int res = 0;for (int j = 0; j <= m; ++j) {res = max(res, dp[j][0]);//找到 k2为0也就是mod 16=0 的数的max月饼数}cout << res << endl;return 0;
}
G 等公交车
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
小G和朋友约好了时间出去玩，他选择坐公交车去找对方。
早早的便来到了公交站牌处开始了等公交车，但公交车却迟迟不来，终于在他濒临爆发的时候，公交车终于缓缓开来。开心的和朋友会合后，他们便开始了一天的玩乐。回到家后，小G还是对于等公交车耿耿于怀，现已知每天都会发出m辆公交车，在手机上它可以查出这m辆公交车的发车时刻第ti 分钟，并且他还知道所有的站点信息，总共有n个公交车站点，第 i 个站点距离发车点的距离为di 米。已知公交车的速度为1米/分钟，发车点和所有的站点都在一条直线上, 每次公交车从发车点出发后，依次经过每个站点。他想知道能否设计一个程序，当每次一个乘客在某个时刻时到达某个站点时，可以直接告诉他需要等待的时间？
输入描述:
第一行两个个正整数,表示n，m. 第二行n个正整数，表示n个站点距离发车点的距离di.(数据保证di递增) 第三行m个正整数，表示m辆公交车的发车时刻ti.（数据保证ti递增） 第四行一个正整数Q,表示接下来的询问个数。
接下来Q行，每行两个正整数t,x，表示该乘客在时刻t时来到了x号站点。
对于100%的数据，1≤n,m,q≤105,1≤li，ti≤2×109
输出描述:
Q行,每行一个整数表示需要等待的时间，若该乘客任何公交车都无法乘上，请输出`TNT`
示例1
输入
2 3 2 4 1 3 5 5 3 1 4 1 5 1 8 2 10 2
输出
0 1 0 1 TNT
思路
二分查找
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,d[100005],t[100005],q;
signed main() {cin>>n>>m;for(int i=1;i<=n;i++){cin>>d[i];}for(int i=1;i<=m;i++){cin>>t[i];}cin>>q;int y=0;while(q--){int tt,x;cin>>tt>>x;int nt=tt-d[x];auto y=lower_bound(t+1,t+m+1,nt);if(y==m+1+t){cout<<"TNT"<<endl;}else cout<<*y-nt<<endl;}return 0;
}
H 24点
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
在扑克牌中有种玩法叫做24点，目标是用给定的四张牌通过基本的数学运算（加、减、乘、除）得到24。24点的玩法规则如下：
1. 准备一副扑克牌，去掉大小王，使用 `A,2,3,4,5,6,7,8,9,10,J,Q,K` 分别表示 `1,2,3,4,5,6,7,8,9,10,11,12,13`。每种各四张，共52张牌。
2. 每次从这些牌中任意取出四张牌。
3. 使用这四张牌的数字，通过加法、减法、乘法和除法运算，最终得到24。（除法是正常的数学除法，即有可能出现除不尽的情况，比如 1÷3=1/3
4. 每张牌只能使用一次，可以任意调换数字的顺序，可以使用任意的括号来改变运算顺序。
5. 玩家需要找到至少一种解决方案。如果无法用四张牌得到24点，则说明没有解。
现在需要你判断某种情况下是否有解。
输入描述:
第一行一个正整数 T (1≤T≤1000)，表示数据的组数。接下来 T 行，每行四个字符串，表示取出的四张牌的点数，输入的扑克牌点数只会出现 `A,2,3,4,5,6,7,8,9,10,J,Q,K`。
输出描述:
输出一行一个字符串，如果有解输出 `YES`，无解输出 `NO`
示例1
输入
5 8 2 2 A 5 J 10 4 9 K A A A 10 10 A 10 8 9 7
输出
YES YES YES NO YES
思路
暴搜 先处理两个数再处理两个数的加减乘除与另外两个数进行计算
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t;
vector<double>b;
string a[5];
int tos(string c){if(c=="A")return 1;if(c=="J")return 11;if(c=="Q")return 12;if(c=="K")return 13;return stoll(c);
}
bool dfs(vector<double>&b){int n=b.size();if(n==1&&fabs(b[0] - 24.0) < 1e-6)return 1;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i!=j){vector<double>nb;for(int k=0;k<n;k++){if(i!=k&&j!=k){nb.push_back(b[k]);//剩下的两个数加入新数组 }}for(int op=1;op<=4;op++){double res=0;//计算原来选定的两个的数 if(op==1){res=b[i]+b[j];}if(op==2){res=b[i]-b[j];}if(op==3){res=b[i]*b[j];}if(op==4){if(b[j]!=0){res=b[i]/b[j];}}nb.push_back(res);if(dfs(nb))return 1;nb.pop_back();}}}}return 0;
}
signed main() {cin>>t;while(t--){b.clear();for(int i=0;i<4;i++){cin>>a[i];b.push_back(tos(a[i]));}if(dfs(b))cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}
I 正义从不打背身
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
*"正义之枪从不打背身"*。小x最近迷上了无畏契约，钟爱"正义"这把武器。可他使用该武器有一条原则：不击杀（打不中）背对自己的敌人。小x实力强大，对于所有直面自己的敌人都能一击毙命。
在一次游戏中。小x面前有nnn个点位，从左往右序依次为1,2,3,……，n每个点位上都有一个敌人。
每个敌人 要么正面朝向小x,要么背面朝向小x。
小x实力强大，打算强迫这n个敌人玩m轮小游戏之后再对每个人开枪。
游戏规则如下：
在第iii轮小游戏中，依次执行以下所有操作：
* 序号为[1,i]的点位上的敌人位置改变。改变规则为: 从1,2,3,……，i 变为i，i−1,……,3,2,1(原来位于i号位置的敌人更换到1号位置，位于i-1号位置的敌人更换到2号位置……）
* 序号为[1,i]的点位上的敌人原地旋转180°。
所有小游戏过后，小x想知道。目前在每个点位的敌人是否被击败。
输入描述:
第一行输入两个整数 n,m接下来一行输入一个仅由'P'和‘B'组成的字符串s。si=′P′表示第i个点位的敌人当前正面对小x。si=′B′表示第i个点位的敌人当前正背对小x。对于所有数据保证：1≤m≤n≤2×106。∣s∣=n
输出描述:
输出一行n个整数。对于第i个数，如果目前位于第i个点位的敌人被击败则输出1，否则输出0。
示例1
输入
3 3 PPP
输出
0 0 1
思路
找规律 6 4 2 1 3 5
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[2000005];
map<int,char>mp;
deque<int> dq;
char ss[2000005], ss1[2000005];
signed main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> ss[i];}for (int i = 1; i <= m; i++) {if ((m - i + 1) % 2 == 1) {if (ss[i] == 'P') ss[i] = 'B';else ss[i] = 'P';}}int x = m;for (int i = 1; i <= (m + 1) / 2; i++) {ss1[i] = ss[x];x -= 2;}if (m % 2 == 0) x = 1;else x = 2;for (int i = (m + 1) / 2 + 1; i <= m; i++) {ss1[i] = ss[x];x += 2;}for (int i = 1; i <= m; i++) {if (ss1[i] == 'P') cout << 1 << " ";else cout << 0 << " ";}for (int i = m + 1; i <= n; i++) {if (ss[i] == 'P') cout << 1 << " ";else cout << 0 << " ";}return 0;
}
K BanG Dream! It's MyGO!!!!!
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
在“BanG Dream! It's MyGO!!!”的世界里，各个乐团的演出和排练场地像星星一样被连接在一起，形成了一张美丽的网络图。每个乐团都有自己独特的演出场地和练习室，这些地点通过各种路径互相连接，组成了一张复杂的图谱。
koala作为一名热爱音乐的乐团忠实粉丝，突然有了一个灵感。他想为最喜欢的乐团设计一个独特的徽章，这个徽章需要从网络图中找出一些特别的图案来代表乐团， 比如选三条边连接到一起， 具体来说，他对以下三种图案感兴趣：
三角形：由三条边构成的连通子图，这是一种经典的图案。
三芒星：四个点形成的图案，一个点连向其他三个点。
闪电折线：一种特别的折线，由四个点按顺序连接， 即一条链。
koala想知道有多少种情况满足，你能帮帮他吗？
输入描述:
第一行包合两个整数 n,m(1≤n≤105,1≤m≤2∗105)，依次表示无向图的点数和边数; 接下来 m 行，每行两个整數u,v(1≤u,v≤n1≤u,v≤n1≤u,v≤n)，表示一条边(u,v)
题目保证无重边、自环
输出描述:
输出包含一个整数，表示你的答案
示例1
输入
5 5 1 2 1 3 2 3 2 4 3 5
输出
8
说明
满足条件的导出子图的边集分别为: (1,2),(1,3),(2,3) (1,2),(2,3),(2,4) (1,3),(2,3),(3,5) (1,2),(1,3),(2,4) (1,2),(1,3),(3,5) (2,4),(2,3),(3,5) (1,3),(2,3),(2,4) (1,2),(2,3),(3,5)
备注:
给定一个无向图，你需要给出三条边的导出子图是连通的情况数量。
思路
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,deg[100005],u[200005],v[200005],cnt1,cnt2,cnt3;
vector<int> ve[100005];
bool vis[100005];
struct edge{int v,nex;
}e[200005];
void sjx(){//u,v,w三角形 for(int u=1;u<=n;u++){for(auto i:ve[u]){vis[i]=1;}for(auto i:ve[u]){for(auto j:ve[i]){if(vis[j])cnt1++;}}for(auto i:ve[u]){vis[i]=0;}}
}
signed main() {cin>>n>>m;for(int i=1;i<=m;i++){cin>>u[i]>>v[i];deg[u[i]]++;deg[v[i]]++;}for(int i=1;i<=m;i++){cnt3+=1ll*(deg[u[i]]-1)*(deg[v[i]]-1);if(deg[u[i]]>deg[v[i]] || (deg[u[i]]==deg[v[i]] && u[i]>v[i]))swap(u[i],v[i]);ve[u[i]].push_back(v[i]);}for(int i=1;i<=n;i++)cnt2+=1ll*deg[i]*(deg[i]-1)*(deg[i]-2)/6;sjx();cnt3-=3*cnt1;cout<<cnt1+cnt2+cnt3;return 0;
}
L koala的程序
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
koala设计了一个程序，首先他写了一个暴力算法，但是在他写完之后受到电脑病毒的影响而失忆。好在他的源代码和题面数据范围保留了下来（数据范围在输入描述中已经给出），但是现在仍然无法通过这个题目。由于电脑病毒的影响，题面已经消失，现在他希望你基于源代码做出优化来解决这道题。
C++代码：
#include <bits/stdc++.h>
using namespace std;// 链表结构体定义
typedef struct node {int id;struct node *next;
} *pNode, Node;// 循环链表头节点
pNode head;// 按顺序删除的前n-1个节点的id构成的列表
vector<int> ans;int main() {// n个节点，判断值kint n, k;cin >> n >> k;// 构造包含n个节点的循环链表head = (pNode)malloc(sizeof(Node));pNode now = head;for (int i = 1; i <= n; ++i) {pNode a = (pNode)malloc(sizeof(Node));a->id = i;now->next = a;now = now->next;}now->next = head->next;// pc为计数器int pc = 0;now = head;// 当前节点的上一个节点pNode last = nullptr;// 程序执行到链表只剩下最后一个节点为止while (n > 1) {pc++;last = now;now = now->next;// 当计数器pc = k时从循环链表中删除当前节点，并把被删除的节点的id添加到答案列表ans中if (pc == k) {last->next = now->next;n--;pc = 0;ans.push_back(now->id);}}// 输出最终答案for (auto id : ans) {cout << id << ' ';}return 0;
}
输入描述:
一行包合两个整数 n,k(2≤n≤3∗105,1≤k≤3∗105)
输出描述:
根据题意输出答案
示例1
输入
10 3
输出
3 6 9 2 7 1 8 5 10
思路
使用树状数组来处理节点的插入和删除操作
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5 + 10;
int n, m, maxx;
int bit[maxn];
int lowbit(int x)
{return x & -x;
}
void add(int pos, int x)
{for (int i = pos; i <= maxx; i += lowbit(i))bit[i] += x;
}
int finds(int k)
{int ans = 0; int now = 0; for (int i = 30; i >= 0; i--) {ans += (1 << i);if (ans > maxx || now + bit[ans] >= k) {ans -= (1 << i);} else {now += bit[ans];}}return ans + 1;
}
signed main()
{cin >> n >> m;maxx = n;for (int i = 1; i <= n; i++)bit[i] = lowbit(i);int now = 1;while (n > 1) {now = (now - 1 + m - 1) % n + 1;int ans = finds(now);add(ans, -1);cout << ans << ' ';n--;}return 0;
}这篇关于8.21 补题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
