题意给出一个长度为n的数组和q次询问，每次询问求区间[l,r]的数组的元素和。思路数据范围n和q都是1e6，数组元素<=1e9，暴力的做法会超时，考虑用前缀和优化。在输入的时候维护sum数组，要注意用long long / int64 ，对于每次询问直接输出sum[r] - sum[l-1]即可。C++代码 #include <iostream> using namespace std; const int maxn = 1e6+10; int main() { long long n,q,l,r,x,sum[maxn]; cin>>n>...

题意给出一个长度为n的字符串，请构造一个数组，具体要求如下：当这一位是1时，要求 a[i]=i 当这一位是0是，要求 a[i]!=i尽可能多的满足要求思路先把所有字符串里是0的位置填上a[i]=i，并且记录下字符串里1的位置的数值tmp。再填字符串里是1的位置的时候，可以考虑每一个元素都等于tmp数组的下一个元素，这样可以尽量满足a[i] != i Go代码 package main import "fmt" func main() { var n int var s string fmt.Scan(&n, &s) //第i个表示第i个小朋友的位...

题意构造一个长度为2*n的合法括号序列，最大的嵌套深度是r。思路考虑先把最大嵌套深度的合法括号构造出来，即放r个左括号，再放r个右括号，最后用单个括号补全到2n的长度Go代码 package main import "fmt" func main() { var n, r int fmt.Scan(&n, &r) for i := 0; i < r; i++ { fmt.Print("(") } for i := 0; i < r; i++ { fmt.Print(")") } f...

题意给出一个数组，有2种操作，把第i个位置的数变为x，求前i个位置的数里等于x的数有多少个？思路考虑数据范围，n和q都只有200，直接暴力维护就可以。对于操作1，把数组idx-1的值变为x；对于操作2，从0遍历到idx-1，如果当前数等于x，答案加1。是idx-1的原因是数组下标从0开始。扩展：本质是一个单点修改区间查询的问题，如果n,q <=1e5，可以考虑用数据结构维护Go代码 package main import ( "fmt" ) func main() { var n, q, op, idx, x int fmt.Scan(&n, &am...

题意求从0到9999满足每个数位各不相同的第k大的数，如果一个数不足5位，补全前导零使其超过5位思路从9999倒序遍历，判断当前的数是否满足条件，满足的话k=k-1，当k=0的时候当前数就是答案。要注意输出的是一个五位的数，需要补前导零代码 package main import ( "fmt" "strconv" ) func check(x int) (string,bool) { s := strconv.Itoa(x) for len(s) < 5 { s = "0" + s ...

题意小红拿到了一个正整数，她每次可以删除其中一个数位，但必须保证每次删除后，该正整数都是3的倍数且大于0。小红想知道，自己最多可以进行多少次这样的删除操作？思路先说一个错误的思路，先计算出正整数的数位和，然后从头遍历字符串，如果删除这位后满足条件，就删除。这样无法得到最优解。正解是根据数位和sum % 3 的值以及所有的数位里%3 的值的个数来讨论的，其实就是个思维题，但是边界条件太多了！假设正整数的每一个数位%3等于1的个数为cnt1，数位%3等于2的个数为cnt2，数位%3等于0的个数为cnt0题目要求删除后这个正整数是3的倍数，就说明删除后的sum%3一定为0如果sum%3一开始就是0的...

题意最多可以做一次操作，这次操作会把数组里的任意一个元素改为任意值，求出现次数最多元素的最多出现次数思路要使得出现次数最多的元素出现的次数尽可能的多，首先要找到最多的出现次数，这里用哈希表维护了每个元素的出现次数，取最大值为ans最后判断如果ans不等于n的话，说明可以做一次操作使得某个元素变为该值，出现次数+1Go代码 package main import ( "fmt" ) func max(a,b int) int { if a > b { return a } return b } func main()...

题意给出一个矩阵，#表示1，.表示0，每4位看作二进制，求十进制思路直接模拟即可，这里是先把矩阵转化为只有0和1的数组，然后从头开始遍历，每次取4位按照1 2 4 8 的数位求出十进制数字的值Go代码 package main import ( "fmt" "math" ) func main() { var n int fmt.Scan(&n) var s string tmp := make([]int,0,n) for i := 0; i < int(math.Pow(2,float...

题意每次操作可以给数组里的某个元素除以2，向下取整，问最少需要多少次操作可以使得所有元素相等思路感觉这个题的数据范围应该没有很强，算是水过去了枚举了a[i]所以可以变成的值，其中mp[x]表示可以变成x的数的个数，cnt[x]表示变成x全部所需要的操作数。最后在所有mp[x]=n的值里，取一个cnt[x]的最小值Go代码 package main import ( "fmt" "math" "sort" ) func min(a,b int) int { if a < b { return a ...

题意给出一个长度为n的字符串和q次询问，每次询问把区间[l,r]的字母各重复一次，插入到原字母的后面。思路模拟即可，每次循环都把s字符串遍历一遍，假设字符串tmp为新的字符串，先将当前字符加到tmp里，如果说当前下标在区间[l-1,r-1]里，就重复加一次。[l-1,r-1]的原因是数组的下标从0开始Go代码 package main import ( "fmt" ) func main() { var n,q,l,r int fmt.Scan(&n,&q) var s string fmt.Scan(&...

题意每次可以把一个字符变成两个字母表中比它小一位的字符希望最终可以生成 xx 个'a'，求长度最短的初始字符串 思路1个b可以变为2个a，1个c可以变为2个b也就是4个a，1个d可以变成2个c=4个b=8个a可以观察出，数量的规律是2的次方题目要求长度最短，所以从z开始倒序遍历，看能否使用当前的字符来构造字符串Go代码 package main import ( "fmt" ) func main() { var x int fmt.Scan(&x) //最后生成x个a //b => 2a //c => 2b => 4a //d...

题意构造一个长度为n的排列使得排列里的每一项都满足a[i]+i都不是质数 思路又是这种思维构造题，想不出来就会很难，核心点就是对于>=4的数，2x一定不是质数，所以只需要更改前3项就可以 Go代码 package main import ( "fmt" ) func main() { var n int fmt.Scan(&n) if n < 3 { fmt.Println(-1) } else { fmt.Print("3 2 1") for i := 4; i <= n; i ++ { ...

题意给出整数a，把a翻转得到b，求a+b的值思路可以理解为分离整数，模拟一下就可以 初始化b为0，每次让b=b*10+a%10，然后a=a/10注意要提前保存下a变量Go代码 package main import ( "fmt" ) func main() { a := 0 _, _ = fmt.Scan(&a) tmp,b := a,0 for tmp > 0 { b = b * 10 + tmp % 10 tmp = tmp / 10 } fmt.Println(a + b) }

题意1e5次询问，每次循环都需要判断输入的数x是否至少存在一个偶数因子其中x<=1e9思路最朴素的思想，对于每一个输入的数x，都从2开始，每次累加2，判断当前遍历到的偶数是否为x的因子。但是1e5*sqrt(1e9)的时间复杂度有点逆天考虑一个性质就是，偶数肯定能被2整除，所以如果一个数有偶数因子，这个数一定可以被2整除，问题转化为x能否被2整除Go代码%2 也可以用&1来判断 但是位运算也没有更快 package main import ( "fmt" ) func main() { var T,x int fmt.Scan(...