A. Game 23
time limit per test1 second memory limit per test256 megabytes
Polycarp plays "Game 23". Initially he has a number ?n and his goal is to transform it to ?m. In one move, he can multiply ?n by 22 or multiply ?n by 33. He can perform any number of moves.
Print the number of moves needed to transform ?n to ?m. Print -1 if it is impossible to do so.
It is easy to prove that any way to transform ?n to ?m contains the same number of moves (i.e. number of moves doesn't depend on the way of transformation).Input
The only line of the input contains two integers ?n and ?m (1≤?≤?≤5⋅1081≤n≤m≤5⋅108).Output
Print the number of moves to transform ?n to ?m, or -1 if there is no solution.
120 51840
output
7
input
42 42
output
0
input
48 72
output
-1
Note
In the first example, the possible sequence of moves is: 120→240→720→1440→4320→12960→25920→51840.120→240→720→1440→4320→12960→25920→51840. The are 77 steps in total.
In the second example, no moves are needed. Thus, the answer is 00.
In the third example, it is impossible to transform 4848 to 7272.
签到题水过，但是我还是WA了一发
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(3e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
int n,m;sc2(n,m);
if(m%n){
printf("-1\n");
return 0;
}
m/=n;
int ans=0;
while(m%2==0){
m/=2;
ans++;
}
while(m%3==0){
m/=3;
ans++;
}
if(m!=1){
printf("-1\n");
return 0;
}
printf("%d\n",ans);
return 0;
}
B. Maximal Continuous Rest
time limit per test2 seconds memory limit per test256 megabytes
Each day in Berland consists of ?n hours. Polycarp likes time management. That's why he has a fixed schedule for each day — it is a sequence ?1,?2,…,??a1,a2,…,an (each ??ai is either 00 or 11), where ??=0ai=0 if Polycarp works during the ?i-th hour of the day and ??=1ai=1 if Polycarp rests during the ?i-th hour of the day.
Days go one after another endlessly and Polycarp uses the same schedule for each day.
What is the maximal number of continuous hours during which Polycarp rests? It is guaranteed that there is at least one working hour in a day.Input
The first line contains ?n (1≤?≤2⋅1051≤n≤2⋅105) — number of hours per day.
The second line contains ?n integer numbers ?1,?2,…,??a1,a2,…,an (0≤??≤10≤ai≤1), where ??=0ai=0 if the ?i-th hour in a day is working and ??=1ai=1 if the ?i-th hour is resting. It is guaranteed that ??=0ai=0 for at least one ?i.Output
Print the maximal number of continuous hours during which Polycarp rests. Remember that you should consider that days go one after another endlessly and Polycarp uses the same schedule for each day.
Examples
input
5 1 0 1 0 1
output
2
input
6 0 1 0 1 1 0
output
2
input
7 1 0 1 1 1 0 1
output
3
input
3 0 0 0
output
0
Note
In the first example, the maximal rest starts in last hour and goes to the first hour of the next day.
In the second example, Polycarp has maximal rest from the 44-th to the 55-th hour.
In the third example, Polycarp has maximal rest from the 33-rd to the 55-th hour.
In the fourth example, Polycarp has no rest at all.
注意特判一下最后一天的休息时间就好了
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(2e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
int n;sc(n);
int a[maxn];
int fir=0,firlen=0,pre=-1,maxx=0,cnt=0;
sc(pre);
if(pre) maxx=1,cnt=1,fir=1,firlen=1;
for(int i=1;i<n;++i){
int x;sc(x);
if(x){
cnt++;
if(fir){
firlen++;
}
if(i==n-1){
cnt+=firlen;
maxx=max(maxx,cnt);
}
}
else{
if(fir){
fir=0;
firlen=cnt;
}
maxx=max(maxx,cnt);
cnt=0;
}
}
printf("%d\n",maxx);
return 0;
}
C. Polycarp Restores Permutation
time limit per test2 seconds memory limit per test256 megabytes
An array of integers ?1,?2,…,??p1,p2,…,pn is called a permutation if it contains each number from 11 to ?n exactly once. For example, the following arrays are permutations: [3,1,2][3,1,2], [1][1], [1,2,3,4,5][1,2,3,4,5] and [4,3,1,2][4,3,1,2]. The following arrays are not permutations: [2][2], [1,1][1,1], [2,3,4][2,3,4].
Polycarp invented a really cool permutation ?1,?2,…,??p1,p2,…,pn of length ?n. It is very disappointing, but he forgot this permutation. He only remembers the array ?1,?2,…,??−1q1,q2,…,qn−1 of length ?−1n−1, where ??=??+1−??qi=pi+1−pi.
Given ?n and ?=?1,?2,…,??−1q=q1,q2,…,qn−1, help Polycarp restore the invented permutation.Input
The first line contains the integer ?n (2≤?≤2⋅1052≤n≤2⋅105) — the length of the permutation to restore. The second line contains ?−1n−1 integers ?1,?2,…,??−1q1,q2,…,qn−1 (−?<??<?−n<qi<n).Output
Print the integer -1 if there is no such permutation of length ?n which corresponds to the given array ?q. Otherwise, if it exists, print ?1,?2,…,??p1,p2,…,pn. Print any such permutation if there are many of them.
Examples
input
3 -2 1
output
3 1 2
input
5 1 1 1 1
output
1 2 3 4 5
input
4 -1 2 2
output
-1
令第一个数为t，则之后第二到n个数即为t+输入的n-1个数的前缀和。比赛的时候因为n没有开long long WA了五发，真难受
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(2e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
ll n;scanf("%lld",&n);
int a[maxn];
ll tot=0;
a[0]=0;
for(int i=1;i<n;++i){
sc(a[i]);
a[i]+=a[i-1];
tot+=a[i];
}
ll tem=n*(n+1)/2;
tem-=tot;
tem/=n;
set<int> s;
int flag=0;
for(int i=0;i<n;++i){
s.insert(a[i]+tem);
if(a[i]+tem>n||a[i]+tem<1){
flag=1;
break;
}
}
if(s.size()!=n) flag=1;
if(flag)printf("-1\n");
else{
for(int i=0;i<n;++i){
printf(i==0?"%lld":" %lld",tem+a[i]);
}
}
return 0;
}
D. Colored Boots
time limit per test2 seconds memory limit per test256 megabytes
There are ?n left boots and ?n right boots. Each boot has a color which is denoted as a lowercase Latin letter or a question mark ('?'). Thus, you are given two strings ?l and ?r, both of length ?n. The character ??li stands for the color of the ?i-th left boot and the character ??ri stands for the color of the ?i-th right boot.
A lowercase Latin letter denotes a specific color, but the question mark ('?') denotes an indefinite color. Two specific colors are compatibleif they are exactly the same. An indefinite color is compatible with any (specific or indefinite) color.
For example, the following pairs of colors are compatible: ('f', 'f'), ('?', 'z'), ('a', '?') and ('?', '?'). The following pairs of colors are notcompatible: ('f', 'g') and ('a', 'z').
Compute the maximum number of pairs of boots such that there is one left and one right boot in a pair and their colors are compatible.
Print the maximum number of such pairs and the pairs themselves. A boot can be part of at most one pair.Input
The first line contains ?n (1≤?≤1500001≤n≤150000), denoting the number of boots for each leg (i.e. the number of left boots and the number of right boots).
The second line contains the string ?l of length ?n. It contains only lowercase Latin letters or question marks. The ?i-th character stands for the color of the ?i-th left boot.
The third line contains the string ?r of length ?n. It contains only lowercase Latin letters or question marks. The ?i-th character stands for the color of the ?i-th right boot.Output
Print ?k — the maximum number of compatible left-right pairs of boots, i.e. pairs consisting of one left and one right boot which have compatible colors.
The following ?k lines should contain pairs ??,??aj,bj (1≤??,??≤?1≤aj,bj≤n). The ?j-th of these lines should contain the index ??aj of the left boot in the ?j-th pair and index ??bj of the right boot in the ?j-th pair. All the numbers ??aj should be distinct (unique), all the numbers ??bj should be distinct (unique).
If there are many optimal answers, print any of them.
Examples
input
10
codeforces
dodivthree
output
5
7 8
4 9
2 2
9 10
3 1
input
7
abaca?b
zabbbcc
output
5
6 5
2 3
4 6
7 4
1 2
input
9
bambarbia
hellocode
output
0
input
10
code??????
??????test
output
10
6 2
1 6
7 3
3 5
4 8
9 7
5 1
2 4
10 9
8 10
开52个队列存每个字母在原串中的位置，然后先找相同字母，再从s1中的问号匹配s2中的字母，再用s2中的问号匹配s1中的字母，最后匹配两个串中还剩下的问号。（打比赛的时候用的vector，疯狂tle，赛后改成queue就124ms过了，这。。。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(2e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
map<char,int> m;
FF(i,26) m[i+'a']=i;
m['?']=26;
int n; sc(n);
getchar();
string s1,s2;
getline(cin,s1);
getline(cin,s2);
queue<int> v1[30],v2[30];
FF(i,n){
v1[m[s1[i]]].push(i+1);
v2[m[s2[i]]].push(i+1);
}
int ans1[maxn],ans2[maxn],index=0;
int ans=0;
FF(i,26){
int minx=min(v1[i].size(),v2[i].size());
ans+=minx;
FF(j,minx){
ans1[index]=v1[i].front(); v1[i].pop();
ans2[index++]=v2[i].front(); v2[i].pop();
}
}
if(v1[26].size()){
FF(i,26){
while(v2[i].size()&&v1[26].size()){
ans1[index]=v1[26].front(); v1[26].pop();
ans2[index++]=v2[i].front(); v2[i].pop();
ans++;
}
}
}
if(v2[26].size()){
FF(i,26){
while(v1[i].size()&&v2[26].size()){
ans1[index]=v1[i].front(); v1[i].pop();
ans2[index++]=v2[26].front(); v2[26].pop();
ans++;
}
}
}
if(v1[26].size()&&v2[26].size()){
int minx=min(v1[26].size(),v2[26].size());
ans+=minx;
FF(j,minx){
ans1[index]=v1[26].front(); v1[26].pop();
ans2[index++]=v2[26].front(); v2[26].pop();
}
}
pr(ans);
FF(i,index){
printf("%d %d\n",ans1[i],ans2[i]);
}
return 0;
}
E. Superhero Battle
time limit per test2 seconds memory limit per test256 megabytes
A superhero fights with a monster. The battle consists of rounds, each of which lasts exactly ?n minutes. After a round ends, the next round starts immediately. This is repeated over and over again.
Each round has the same scenario. It is described by a sequence of ?n numbers: ?1,?2,…,??d1,d2,…,dn (−106≤??≤106−106≤di≤106). The ?i-th element means that monster's hp (hit points) changes by the value ??di during the ?i-th minute of each round. Formally, if before the ?i-th minute of a round the monster's hp is ℎh, then after the ?i-th minute it changes to ℎ:=ℎ+??h:=h+di.
The monster's initial hp is ?H. It means that before the battle the monster has ?H hit points. Print the first minute after which the monster dies. The monster dies if its hp is less than or equal to 00. Print -1 if the battle continues infinitely.Input
The first line contains two integers ?H and ?n (1≤?≤10121≤H≤1012, 1≤?≤2⋅1051≤n≤2⋅105). The second line contains the sequence of integers ?1,?2,…,??d1,d2,…,dn (−106≤??≤106−106≤di≤106), where ??di is the value to change monster's hp in the ?i-th minute of a round.Output
Print -1 if the superhero can't kill the monster and the battle will last infinitely. Otherwise, print the positive integer ?k such that ?k is the first minute after which the monster is dead.
Examples
input
1000 6
-100 -200 -300 125 77 -4
output
9
input
1000000000000 5
-1 0 0 0 0
output
4999999999996
input
10 4
-3 -6 5 4
output
-1
贪心，模拟每轮打怪兽的过程，如果打完一轮之后hp小于一轮中最大能打掉的hp则在下一轮中就能打死，否则继续打一轮。-1的情况比较好判断
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(2e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
ll a[maxn]; ll h;
ll n;scanf("%lld%lld",&h,&n);
scanf("%lld",&a[0]);
ll minx=a[0];
rep(i,1,n-1){
scanf("%lld",&a[i]);
a[i]+=a[i-1];
minx=min(minx,a[i]);
}
if(a[n-1]>=0&&h+minx>0){
printf("-1\n");exit(0);
}
ll ans=0;
if(a[n-1]==0||minx+h<=0){
FF(i,n){
if(h+a[i]<=0){
ans=i+1;
break;
}
}
printf("%lld\n",ans);
return 0;
}
ll tem=h+minx;
ll f=tem/(-a[n-1]);
if(tem%(-a[n-1])>0)
f++;
ans+=f*n;
h+=f*a[n-1];
if(h){
FF(i,n){
if(h+a[i]<=0){
ans+=(i+1);
break;
}
}
}
printf("%lld\n",ans);
return 0;
}
F2. Same Sum Blocks (Hard)
time limit per test3 seconds memory limit per test256 megabytes
This problem is given in two editions, which differ exclusively in the constraints on the number ?n.
You are given an array of integers ?[1],?[2],…,?[?].a[1],a[2],…,a[n]. A block is a sequence of contiguous (consecutive) elements ?[?],?[?+1],…,?[?]a[l],a[l+1],…,a[r] (1≤?≤?≤?1≤l≤r≤n). Thus, a block is defined by a pair of indices (?,?)(l,r).
Find a set of blocks (?1,?1),(?2,?2),…,(??,??)(l1,r1),(l2,r2),…,(lk,rk) such that:
- They do not intersect (i.e. they are disjoint). Formally, for each pair of blocks (??,??)(li,ri) and (??,??(lj,rj) where ?≠?i≠j either ??<??ri<lj or ??<??rj<li.
- For each block the sum of its elements is the same. Formally,?[?1]+?[?1+1]+⋯+?[?1]=?[?2]+?[?2+1]+⋯+?[?2]=a[l1]+a[l1+1]+⋯+a[r1]=a[l2]+a[l2+1]+⋯+a[r2]=⋯=⋯=?[??]+?[??+1]+⋯+?[??].a[lk]+a[lk+1]+⋯+a[rk].
- The number of the blocks in the set is maximum. Formally, there does not exist a set of blocks (?′1,?′1),(?′2,?′2),…,(?′?′,?′?′)(l1′,r1′),(l2′,r2′),…,(lk′′,rk′′)satisfying the above two requirements with ?′>?k′>k.
The picture corresponds to the first example. Blue boxes illustrate blocks.
Write a program to find such a set of blocks.Input
The first line contains integer ?n (1≤?≤15001≤n≤1500) — the length of the given array. The second line contains the sequence of elements ?[1],?[2],…,?[?]a[1],a[2],…,a[n] (−105≤??≤105−105≤ai≤105).Output
In the first line print the integer ?k (1≤?≤?1≤k≤n). The following ?k lines should contain blocks, one per line. In each line print a pair of indices ??,??li,ri (1≤??≤??≤?1≤li≤ri≤n) — the bounds of the ?i-th block. You can print blocks in any order. If there are multiple answers, print any of them.
Examples
input
7
4 1 2 2 1 5 3
output
3
7 7
2 3
4 5
input
11
-5 -4 -3 -2 -1 0 1 2 3 4 5
output
2
3 4
1 1
input
4
1 1 1 1
output
4
4 4
1 1
2 2
3 3
练习STL的一道好题啊，贪心算法，首先枚举每两个点之间的距离，存到一个map里，第一维存距离，第二维开一个vector，压入左右坐标，这样存完n*n个距离之后将每个距离的vector按照r升序排列，从前往后找，遇到当前点的l>前一个点的r时，符合条件的区间++，上一个点的r更新。遍历完所有的距离之后就能找到答案；
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(2e3)+100
#define mod int(1e9)+7
using namespace std;
struct node{
int l,r;
};
int cmp(node a,node b){
return a.r<b.r;
}
map<int,vector<node>> mp;
int main(){
int n;sc(n);
int a[1600]; //前缀和
a[0]=0;
rep(i,1,n){
sc(a[i]);
a[i]+=a[i-1];
}
rep(i,1,n){
rep(j,i,n){
mp[a[j]-a[i-1]].pb({i,j});//距离，左右点坐标
}
}
int ans=0;int pos=0;
for(auto it=mp.begin();it!=mp.end();++it){
sort(it->S.begin(),it->S.end(),cmp);//将当前距离的所有坐标按r升序排
int cnt=0;int rr=0;
for(int i=0;i<it->S.size();++i){
if(it->S[i].l>rr){
cnt++;rr=it->S[i].r;
}
}
if(cnt>ans){
ans=cnt;pos=it->F;
}
}
printf("%d\n",ans);
int rr=0;
for(int i=0;i<mp[pos].size();++i){
if(mp[pos][i].l>rr){
printf("%d %d\n",mp[pos][i].l,mp[pos][i].r);
rr=mp[pos][i].r;
}
}
return 0;
}
