day11 悄悄关注
河北大学程序设计训练营
Day11 每日一题讲解题目
7-4 悄悄关注 (25分)
新浪微博上有个“悄悄关注”,一个用户悄悄关注的人,不出现在这个用户的关注列表上,但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探,根据某人的关注列表和其对其他用户的点赞情况,扒出有可能被其悄悄关注的人。
输入格式:输入首先在第一行给出某用户的关注列表,格式如下:
1人数N 用户1 用户2 …… 用户N
其中N是不超过5000的正整数,每个用户i(i=1, …, N)是被其关注的用户的ID,是长度为4位的由数字和英文字母组成的字符串,各项间以空格分隔。
之后给出该用户点赞的信息:首先给出一个不超过10000的正整数M,随后M行,每行给出一个被其点赞的用户ID和对该用户的点赞次数(不超过1000),以空格分隔。注意:用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户,在点赞信息中也没有重复用户。
输出格式:我们认为被该用户点赞次数大于其点赞平均数、且不在其关注列表上的人,很可能是其悄悄关注的人。根据这个假设,请你按用户ID字母序的升序输出可能是其悄悄关注的人,每行1 ...
day10 Swan学院社团招新
河北大学程序设计训练营[TOC]
day10 Swan学院社团招新Swan学院社团招新,招新宣讲会分散在不同时间段,大一新生小花花想知道自己最多能完整的参加多少个招新宣讲会(参加一个招新宣讲会的时候不能中断或离开)。【问题说明】这个问题是对几个相互竞争的招新宣讲会活动进行调度,它们都要求以独占的方式使用某一公共资源(小花花)。调度的目标是找出一个最大的相互兼容的活动集合。 活动选择问题就是要选择出一个由互相兼容的问题组成的最大子集合。【温馨提示】应先将所有的活动按照结束时间升序排列,然后再选择可能的时间组合,并求出最大的组合数,使用qsort()排序函数是一个不错的选择。qsort 的函数原型是: void qsort(voidbase,size_t num,size_t width,int(__cdeclcompare)(const void,const void)); 功 能: 使用快速排序例程进行排序;头文件:stdlib.h; 参数: 1 待排序数组首地址;2 数组中待排序元素数量;3 各元素的占用空间大小;4 指向函数的指针,用于确定排序的顺序
输入格式:第一行为n,表示有n ...
day09 程序存储问题
河北大学程序设计训练营
day09 程序存储问题题目描述:设有n个程序{1,2,…,n}要存放在长度为L的磁带上。程序i存放在磁带上的长度是li,1≤i≤n。 程序存储问题要求确定这n个程序在磁带上的一个存储方案, 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度,计算磁带上最多可以存储的程序数。
输入格式:第一行是2个正整数,分别表示文件个数n和磁带的长度L。接下来的1行中,有n个正整数,表示程序存放在磁带上的长度。
输出格式:输出最多可以存储的程序数。
输入样例:在这里给出一组输入。例如:
6 50
2 3 13 8 80 20
输出样例:在这里给出相应的输出。例如:
5
解题思路:在特定大小的磁带上存下尽可能多的程序,所以依次放入最小文件即可。
关键点:对程序大小的排序
参考答案:12345678910111213141516171819202122232425262728293031323334353637#include <bits/stdc++.h>using namespace std;int main() { ...
day08 二分查找
河北大学程序设计训练营[TOC]
day08 二分查找利用二分查找找出所给出的数在数组中的下标
输入格式:第一行输入n和m表示数组有n个数据,m表示要对m个数进行查找
输出格式:所有输出在一行完成,行末没有多余空格和多余回车。
输入样例:1235 51 2 3 4 51 2 3 4 5
输出样例:10 1 2 3 4
题目注意 注意时间限制50ms 所以能使用 cin 和 cout 会超时 或者关闭同步也可以ios::sync_with_stdio(false); //取消cin和stdin的同步。
可以使用vector动态数组存储 如果使用数组 要开大一点 不然会 溢出发生 段错误。
二分查找的前提是数据有序 题目没有给出 但是我们默认他们是排序的。
123456789101112131415161718192021#include<iostream>using namespace std;int num[1000005];int binarySearch(int begin,int end,int target){ while(begi ...
day05 C++ 引用&与传值 结构体 sort排序
河北大学程序设计训练营[TOC]
C++ 引用 & 与传值的区别
c++ & 被称为引用符号(函数参数列表使用)
c语言 & 被称为取地址运算符
函数传参 int a 是传递a的值 进行函数运算
使用引用变量 int &a 是直接对变量本身进行操作
## 引用& 例子
引用12345678void func(int &a) {// 传⼊入的是n的引⽤用,相当于直接对n进⾏行行了了操作,只不不过在func函数中换了了个名 字叫a a = 99; } int main() { int n = 0; func(n); // n由0变成了99}
传值12345678void func(int a) { // 传入的是0这个值,并不会改变main函数中n的值 a = 99; } int main() { int n = 0; func(n);// 并不会改变n的值,n还是0 }
C++ structc++ 和 c 语言一样,但是 c+ ...
day04 c++ stack queue
河北大学程序设计训练营[TOC]
stack称为栈(或者堆栈),堆栈是一个不容忽视的概念。堆栈都是一种数据项按序排列的数据结构,只能在一端( 称为栈顶(top) )对数据项进行插入和删除.
特点: 先进后出
头文件1#include <stack>
增加元素1push() 在栈顶增加元素
删除元素1pop() 移除栈顶元素
返回栈中元素数目1size()
返回栈顶元素1top()
判断是否为空1empty()
练习1234567891011121314151617#include<iostream>#include<string>#include<stack>using namespace std;int main(){ stack<int> s; int n = 10; while(n--){ s.push(n); } while(s.size()!=0){ cout << s.top() << ","; s.pop(); ...
day03 c++ set map
河北大学程序设计训练营
内容目录[TOC]
setset是集合,set不存在重复的元素,会按照从小到大进行排序
set集合中没有重复的元素
set中的元素都是排好序的
头文件引入1#include<set>
增加元素1insert()--在集合中插入元素
循环遍历12iterator begin()--指向第一个元素的位置iterator end()--指向最后一个元素的下一个位置
123for(set<int>::iterator it; it != s.end(); it++){ cout << *it << endl;}
查询数目1size()--集合中元素的数目
删除数据1erase()--删除集合中的元素
1void clear()--删除所有的数据
查找数据1find()--查找值对应的位置
注意
如果元素存在那么返回其对应的位置
否则 ...
day02 c++ vector string
河北大学程序设计训练营
前言:
STL是Standard Template Library的简称 中文名标准模板库
STL可分为:
容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。
vector(Vector)是一个封装了动态大小数组的顺序容器。
1.初始化(构造函数)
123vector():创建一个空vectorvector(int nSize):创建一个vector,元素个数为nSize vector(int nSize,const t& t):创建一个vector,元素个数为nSize,且值均为t
2.增加元素
1void push_back(const T& x):向量尾部增加一个元素X
3.删除函数
1void pop_back();删除向量中最后一个元素
4.循环遍历
1234iterator begin():返回向量头指针,指向第一个元素iterator end():返回向量尾指针,指向向量最后一个元素的下 ...
day26 动态规划 斐波那契数列
已知斐波那契数列 Fn =Fn−1+Fn−2 (n>=3), F1=1,F2=1求解该数列的第n项,结果对998244353取模。
输入格式:
输入一个正整数n (1<=n<=10000000)。
输出格式:
输出一个数,数列的第n项
输入样例1:
1
输出样例1:
1
输入样例2:
3
输出样例2:
2
思路: 我刚开始用的普通递归但有一个测试点过不了,出现的问题就是,因为递归不停反复运算导致数据量太大。后来考虑了优化递归就是开一维数组保存了递归结果,但是还是处理不了太大的数据,测试点5无法通过。普通递归代码:
12345int Fib(int n){ if(n == 1 || n == 2) return 1; else return Fib(n-1) % 998244353 + Fib(n-2) % 998244353;}
初步优化递归代码:
123456789101112131415161718192021222324#include <iostream>#include <c ...
day01 c++ 入门 helloworld
河北大学程序设计训练营-day01
C++入门第一步C++环境安装安装DEVC++做演示
其他开发工具推荐: CodeBlocks、vscode、SublimeText
第一个==hello world==程序12345678#include<iostream>using namespace std;int main(){ cout << "hello world !" << endl;}
基本语法程序C++的基本类型和C语言无异
数值类型
整型: (短整型)short 、(整型)int 、(长整型) long
浮点类型: (单精度类型)float (双精度类型) double
字符类型:
字符类型 : char
12345678910111213141516171819202122232425262728293031323334353637#include<iostream>using namespace std;int main(){ //数字型 short short_num = ...