差亿点过三题
A题，考虑将相同的字母压缩，要也即要压缩后的字符数为奇数，考虑修改则需要修改开头或者结尾。
这时考虑到修改一位便可，于是只需
B题,先求出k在二进制下最高位1的位置，然后按等比数列求和求出如果就模拟，否则就除k算。
不开long long见祖宗。![菜鸡]()
C题,考虑到，先预处理出十的幂与各幂次之间允许的次数
A:
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
| LL t;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>t;
f(sb,1,t){
string s;
cin>>s;
vector<pii> v;
char last=s[0];
int cnt=0;
for(auto it:s){
if(it!=last){
v.pb(mp(last,cnt));
last=it;
cnt=1;
}
else cnt+=1;
}
v.pb(mp(last,cnt));
if(v.size()&1)
cout<<s<<"\n";
else {
if(s[0]=='a') s[0]='b';
else s[0]='a';
cout<<s<<"\n";
}
}
return 0;
}
|
B:
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
41
42
43
44
45
46
47
48
49
50
51
52
| LL quikpower(int b)
{
LL ans = 1, base = 2;
while (b > 0)
{
if (b & 1)
{
ans *= base;
}
base *= base;
b >>= 1;
}
return ans;
}
LL t;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
f(ab, 1, t)
{
LL n, k, bas = 1, cnt = 0;
cin >> n >> k;
n -= 1;
LL sb = k;
while (sb > 0)
{
sb>>=1;
cnt += 1;
}
LL ma=quikpower(cnt)-1;
if (n <ma)
{
cnt=0;
while (n > 0)
{
cnt += 1;
n -= bas;
bas *= 2;
}
}
else if(n>ma)
{
n-=ma;
cnt+=(n/k+(n%k?1:0));
}
cout << cnt << "\n";
}
return 0;
}
|
C:
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
| LL t,n,k;
LL a[11]={1};
LL b[11]={0};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
f(i,1,9){
a[i]=a[i-1]*10;
b[i]=b[i-1]*10+9;
}
cin>>t;
f(sb,1,t){
cin>>n>>k;
k+=1;
vi v;
LL ans=0;
f(i,1,n){
LL temp;
cin>>temp;
v.pb(temp);
}
auto it=v.begin();
it++;
while(it!=v.end()&&k>0){
LL mid=min(k,b[(*it)-(*(it-1))]);
ans+=mid*a[(*(it-1))];
k-=mid;
it++;
}
if(k>0){
ans+=k*a[(*(it-1))];
}
cout<<ans<<"\n";
}
return 0;
}
|
