题目传送门 大致思路 依据值来修改,那么我们可以声明一个结构体:包含值和索引 结构体存储原来的索引,然后将结构体根据值来升序排序 每次修改时利用二分查找修改区间,用差分数组记录修改 所有修改结束之后,还原原数组,用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
题目传送门 大致思路 经典题目,搜索,$a[i]$表示第i行的皇后在第几列 用dfs按行递归,对当前行的每一列做一个尝试,合法就作为答案备选 判断不合法:与先前的皇后在同一列,或在同一条斜线上($|y_1-y_2| == |x_1-x_2|$) Code 1234567891011121314151617181920212223242526272829303132333435363738void dfs(int row) { if (row >8) { cnt++; for (int i = 1; i <
题目传送门 大致思路 求最短路径,想到bfs,但是带有方向限制,可以在队列中加入一些"标签"来限制 同时要注意vis数组并不能只有二维,因为可能不同方向来到同一个位置产生的答案是不一样的,不能到了一次之后,就不再去了,用三维来加一个方向标签 Code 1234567891011121314151617181920212223242526272829303132void solve() { int m,n; cin>>m>>n; vector<vector<int> > a(n+1,vector
比赛传送门 E 记dp[i]为以i为起点的数组有几个好数组,如果i位置开始有一个块,那么可以状态转移(自己的块加上后面原有的好数组)注:k为a[i] $$dp[i]=1+dp[i+k] $$否则 $$dp[i]=0 $$最终答案就是dp数组的总和 接下来的问题就是如何快速判断i位置开始是否有一个块了: 预处理一个数组 s 其中s[i]表示从位置 i 开始，向右连续出现且值与 a[i]相同的元素所能到达的最远下标 从右往左扫描: 如果$a[i]==a[i+1]$ 那么$s[i]=s[i+1]$ 否则$s[i]=i$ 如果$i+k-1
