贪心,每一行从前往后搜就行了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int h,w;
string s;
signed main(){
cin>>h>>w;
for(int i=1;i<=h;++i){
cin>>s;
for(int i=0;i<w;++i){
if(s[i]==s[i+1]&&s[i]=='T'){
s[i]='P';
s[i+1]='C';
i++;
}
}
cout<<s<<endl;
}
return 0;
}
这题肯定是一个辗转相减,为了节省时间,我们用辗转相除。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ans=0;
void gcd(int a,int b){
if(a!=b){
if(a%b){
ans+=a/b;
a=a%b;
gcd(b,a);
}
else ans+=a/b-1;
}
return;
}
signed main(){
int a,b;
cin>>a>>b;
if(a<b) swap(a,b);
gcd(a,b);
cout<<ans<<endl;
return 0;
}
由于数据规模比较大,所以背包一定不行,但 3 sec / 1024 MB
这么宽的时间和空间,就用 set
来存所有可能的结果。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,a;
set<int> s;
signed main(){
cin>>n>>k;
s.insert(0);
for(int i=1;i<=n;++i){
cin>>a;
auto t=s.begin();
for(int j=1;j<=k;++j){
s.insert(*t+a);
t++;
}
}
auto t=s.begin();
for(int i=1;i<=k;++i) t++;
cout<< *t<<"\n";
return 0;
}