题目传送门 大致思路 将数组升序排序,对每一个长度分别计算能构成的不同三角形: 等腰,等边另外算 三边都不相同的三角形:利用"三指针",说是三指针,其实感觉是双指针,两个指针在当前长度之前滑动,当前指针在计算时是不动的 Code 1234567891011121314151617181920212223void solve(){ int n; cin>>n; vector<pair<int,int>> a(n); for(int i=0;i<n;i++) cin>>a[i].fir
题目传送门 大致思路 x 满足$(x-a)\%(x-b)==0$ 设$x-b=t$ 则$x=t+b$ 那么$(t+b-a)\%t==0$成立 ,即$(b-a)\%t==0$成立 先查找b-a的所有约数,然后判断约数 t 是否满足 $l≦t+b≦r$ Code 123456789101112131415161718192021222324vector<int> bzd(int n) { vector<int> res; for (int i = 1; i*i<
题目传送门 大致思路 可以发现"gcd"只有六种排列,一旦确定某种排列之后,每一步要走到的字母就确定了 记dp[i][j]为到(i,j)格有几种路径 $$dp[i][j]=dp[i][j-1]+dp[i-1][j] $$做六次dp,累加即可 Code 12345678910111213141516171819202122232425262728293031void solve() { int n,ans=0; cin >> n; int k=(2*n-1)/3; vector<string > a(n
题目传送门 大致思路 依据值来修改,那么我们可以声明一个结构体:包含值和索引 结构体存储原来的索引,然后将结构体根据值来升序排序 每次修改时利用二分查找修改区间,用差分数组记录修改 所有修改结束之后,还原原数组,用ans数组存储答案 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051struct num{ int val; int index;};bool cmp(const struct num &a , cons
前言 本文两道题目均来自fjnu第29届低年级程序设计大赛: 热身赛D 正赛F 热身赛D 大致思路 $(1≤k)$ 很明显,所有数&上$0$都会变成0 ,就只会有一种元素,肯定满足且最小(非负整数) 仔细观察一下,可以发现按位异或和按位或并不会改变元素种类个数 Code 12345678910111213141516void solve() { int n,k; cin >> n >> k; set<string> s; for(int i=0;i<n;i++) { string
题目传送门 大致思路 可以看到所有氨基酸所占的列都是一样的,打表记录所有氨基酸,注意处理空行和头尾特殊氨基酸,具体细节在代码注释里 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111
题目传送门 大致思路 观察到$(1≤a_i≤10^9)$这一数据范围内的最小公倍数顶多 30 个 $(10^9<2^{30})$ 于是我们可以暴力枚举所有区间,顶多枚举 30 次区间,判断是否该区间存在区间的最小公倍数,更新答案 递归实现好操作一点 Code 1234567891011121314151617181920212223242526272829303132const int N = 100721;int ans=0;vector<int> a(N);int lcm(int x,int y) { return (x*y)/__gcd(x,y);
题目传送门 大致思路 声明一个建筑结构体: {$time$ 表示抢修需要的时间 , $limit$表示截止时间} 按截止时间升序排序,确保当前处理的一定是"最紧急"的: 注: $curr$ 示当前花费了多少时间 搞一个最大堆,表示当前计划抢修的建筑中,花费时间最长的 如果$time+curr≤limit$,直接入堆 否则,如果 $time$ 小于堆顶的花费时间,那么进行替换 这是一定不会超过 $limit$ 的 ,为什么? 前面处理的截止时间肯定不会比 $limit$ 宽松,但是却花费时间更多,这样替换, $curr$ 肯定不会超过 $limit$ 最终堆的大小就为
题目传送门 大致思路 将边按权重升序排序,然后根据边两边的节点是否连通判断是否将该边加入(用到并查集) Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445int father[5721];int find(int x){ if(x!=father[x]) father[x]=find(father[x]); return father[x];}bool uoionset(int a,int b){ a=find(a); b=find(b)
题目传送门 大致思路 肯定不能计算所有排列的逆序对, $100!$ 肯定超时 发现n排列的k个逆序对可以由 n-1 排列计算得来: 记dp[i][j]为i排列,有j个逆序对的排列个数 假设n-1排列为 ******** 那么插入一个n: ********n ,逆序对个数也就是n-1排列原本有的逆序对个数 再比如 *******n* ,逆序对个数也就是n-1排列原本有的逆序对个数 + 1 以此类推,便有 $$dp[i][j]=\sum_{k=1}^{i-1}dp[i-1][j-k](0≤j-k) $$另外注意初始化 Code 12345678910111213void
