CodeForce刷题表
Day7
题意:
试求：由k的任意次幂求和第k大的数，由于数很大需要取mod = 1e9+7
如：如果n是3，那么这个序列就是 1 (3^0^)，3(3^1^) ，4(3^1^+3^0^) ，9(3^2^) …… 第4大的就是9
思路：
其实可以看出来，这个从小到大的排序，其实可以看出来：k的二进制上是1的x位置就是有3的x次方。
如：k = 3 二进制 0 0 1 1 ，即 3^1^ + 3^0^ = 4 。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 1e9+7;
int main(){
int _;cin>>_;
while(_--) {
ll n,k,res = 0,t=1;
cin>>n>>k;
while(k) {
if(k&1)
res = (res + t) % mod;
t = (t * n) % mod;
k >>= 1;
}
cout<<res<<endl;
}
return 0;
}
|
总结：
幂排序的题也可以进一步转换为二进制来做，二进制牛的一，其实就是用二进制代替了某种序列: 0 0 0 1，0 0 1 0 ， 0 0 1 1 ， 0 1 0 0 ……这种方式的题目可以考虑用二进制来做。
题意：
长度是n的一个字符串，把所有的字符全都变成给定字符ch，可以选择一个数i，让除了i的倍数的数全都变成ch，输出最少选几次就可以全部变成ch，下一行输出选的数是哪几个(由小到大)
思路：
如果最初的字符串就全部为ch，直接输出0
如果2~n的某个数k的倍数全部为ch，输出1，输出 k (这样的话选定这个k，由于k的倍数都是ch不需要改变，其他所有的数都变成ch。实际上len/2以后的数只要有一个是ch，那么就可以完成操作)
如果不满足上面两种情况 ，输出2 ，输出 n-1, n (选n-1 ,除了n-1全都变成ch，选n，把剩下的n-1变成ch)
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 1e9+7;
int n,res,len;
char c;
string s;
bool case1() {
for(int i=0;i<len;i++)
if(s[i]!=c)
return false;
return true;
}
int case2() {
for(int i = 2; i <= n; i++){
bool k = true;
for(int j = 1; j * i <= n; j++)
if(s[j * i - 1] != c)
k = false;
if(k)
return res = i;
}
return 0;
}
int main(){
int _;cin>>_;
while(_--) {
cin>>n>>c>>s;
len = s.size();
if(case1())
cout<<0;
else if(case2())
cout<<1<<endl<<res;
else
cout<<2<<endl<<n-1<<" "<<n;
cout<<endl；
}
return 0;
}
|
总结：
中途需要退出的循环感觉写成函数会比较好。
微信
支付宝