#数位dp
A
题意
- 两个字符串a，b，最终要将b添加到a上面
- 给定操作序列：如果是V就把b的当前位加入到a的开头，如果是D就加入到末尾
思路
- 模拟即可
代码
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void solve(){
int n,m;
string a,b;
cin >> n;
cin >> a;
cin >> m;
cin >> b;
string op;
cin >> op;
for(int i=0;i<op.size();i++){
if(op[i]=='V'){
a=b[i]+a;
}else{
a=a+b[i];
}
}
cout << a << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
B
题意
- 给定n，输出所有x使得n=x+y，y=x*(10^k)
思路
- 发现x+y其实就是11x，101x，1001x……，验证即可
代码
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void solve(){
long long n;
cin >> n;
long long cnt=1;
vector<long long> ans;
for(int i=0;i<=18;i++){
cnt*=10;
if(n%(cnt+1)==0){
ans.push_back(n/(cnt+1));
}
}
cout << ans.size() << endl;
if(ans.size()){
sort(ans.begin(),ans.end());
for(auto i:ans){
cout << i <<' ';
}
cout << endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
C1
题意
- 物品按
打包成堆，大小为
- 刚好凑够n个物品，买最少堆，最少的代价是多少
思路
- 三进制拆分
- 表打大一点
代码
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
long long qpow(long long a,long long b){
if(b<0) return 0;
long long ans=1;
while(b){
if(b&1){
ans*=a;
}
a*=a;
b>>=1;
}
return ans;
}
vector<long long> tb;
void solve(){
long long n;
cin >> n;
long long ans=0;
int cnt=0;
while(n>0){
ans+=(n%3)*tb[cnt];
n=n/3;
cnt++;
}
cout << ans << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
tb.push_back(3);
for(int i=1;qpow(3,i+1)+i*qpow(3,i-1)<2e18;i++){
tb.push_back(qpow(3,i+1)+i*qpow(3,i-1));
}
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
C2
题意
- 题意同上一题，改为凑够n个物品，最多k堆，最少代价
思路
- 先三进制拆分看要多少堆，如果现在已经超过k堆直接就寄了
- 余量的堆数可以给高位退位，如果手动一次次退位会T
- 需要一次性处理，记得开longlong，max_take不开会WA
代码
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
long long qpow(long long a,long long b){
if(b<0) return 0;
long long ans=1;
while(b){
if(b&1){
ans*=a;
}
a*=a;
b>>=1;
}
return ans;
}
vector<long long> tb;
void solve(){
long long n,k;
cin >> n >> k;
long long ans=0;
int cnt=0,sum=0;
vector<long long> tot(50);
while(n>0){
tot[cnt]+=n%3;
sum+=n%3;
n=n/3;
cnt++;
}
for(int i=31;i>=1;i--){
if(tot[i]==0) continue;
long long max_take=min(tot[i],(k-sum)/2);
if(max_take>0){
tot[i]-=max_take;
tot[i-1]+=3*max_take;
sum+=2*max_take;
}
// while(tot[i]>0 && sum+2 <= k){
// tot[i]--;
// tot[i-1]+=3;
// sum+=2;
// }
}
for(int i=0;i<tb.size();i++){
ans+=(tot[i]*tb[i]);
}
cout << (sum>k?-1:ans) << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
tb.push_back(3);
for(int i=1;qpow(3,i+1)+i*qpow(3,i-1)<2e18;i++){
tb.push_back(qpow(3,i+1)+i*qpow(3,i-1));
}
// for(int i=0;i<=10;i++){
// cout << tb[i] << endl;
// }
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
D
题意
- 无限长序列，从1开始不断向后延伸123456789101112
- 求到第k位的时候的和
思路
- 数位dp板子改一改就行
- 算一下最后到哪个数，残缺的部分暴力补全（常数时间）
- 前面完整的部分直接数位dp算
代码
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
/**
* f[i]表示i位数1~9出现的次数
* g[i]表示i位数占的位置
* f[i]=f[i-1]*10+10^(i-1)
* g[i]=i*9*10^(i-1)
*/
ull qpow(ull a,ull b){
if(b<0) return 0;
ull ans=1;
while(b){
if(b&1){
ans*=a;
}
a*=a;
b>>=1;
}
return ans;
}
ull ful[20],mi[20],g[20];
ull deal(ull n){
ull tmp=n;
int len=0;
ull a[20]={0};
ull ans[10]={0};
while(n) {
a[++len]=n%10;
n/=10;
}
for(int i=len;i>=1;i--) {
for (int j=1;j<10;j++) ans[j]+=ful[i-1]*a[i];
for (int j=1;j<a[i];j++) ans[j]+=mi[i-1];
tmp-=mi[i-1]*a[i];
ans[a[i]]+=tmp+1;
}
ull res=0;
for(int i=1;i<=9;i++) res+=i*ans[i];
return res;
}
void solve(){
ull k;
cin >> k;
int cnt;
for(cnt=1;k>=g[cnt];cnt++){
k-=g[cnt];
}
ull zheng=k/cnt;
ull can=k%cnt;
ull lst=qpow(10,cnt-1)+zheng-1;
ull ans=deal(lst);
string bas=to_string(qpow(10,cnt-1)+zheng);
for(int i=0;i<can;i++){
ans+=bas[i]-'0';
}
cout << ans << endl;
}
int main(){
mi[0]=1;
for(int i=1;i<=18;i++){
ful[i]=ful[i-1]*10+mi[i-1];
mi[i]=10*mi[i-1];
g[i]=9*i*mi[i-1];
// cout << i << ' ' << ful[i] << ' ' << g[i] << endl;
}
int T;
cin >> T;
while(T--){
solve();
}
return 0;
}
E
题意
- 两个序列，分别有n个元素和m个元素
- q次选择每次要选出最大的z个元素，且n中最多选x个，m中最多选y个，回答z个元素和
思路
- 朴素思考，要选出z个远足使得价值最大，肯定先考虑选最大的z个，但是最大的z个中可能某一个序列拿多了
- 如果某个序列拿多了，那最后的状态一定是这个序列拿上限k个，另一个序列拿z-k个
- 如果两个序列都没拿多，那直接输出最大的z个
- 对于获取若干个和，需要在
完成，所以两个序列分别排序维护前缀和，再额外维护一个所有元素的降序排序前缀和
代码
#include<bits/stdc++.h>
using namespace std;
using ll=unsigned long long;
#define pii pair<ll,ll>
bool cmp(pii a,pii b){
return a.first>b.first;
}
ll a[202020];
ll b[202020];
pii c[404040];
void solve(){
int cnt=0;
int n,m,q;
cin >> n >> m >> q ;
for(int i=1;i<=n;i++){
cin >> a[i];
c[++cnt]={a[i],1};
}
for(int i=1;i<=m;i++){
cin >> b[i] ;
c[++cnt]={b[i],0};
}
sort(a+1,a+n+1,greater());
sort(b+1,b+m+1,greater());
sort(c+1,c+cnt+1,cmp);
for(int i=1;i<=cnt;i++){
c[i].first+=c[i-1].first;
c[i].second+=c[i-1].second;
}
for(int i=1;i<=n;i++) a[i]+=a[i-1];
for(int i=1;i<=m;i++) b[i]+=b[i-1];
for(int i=0;i<q;i++){
int x,y,z;
cin >> x >> y >> z;
if(c[z].second>x){
cout << a[x]+b[z-x] << endl;
}else if(z-c[z].second>y){
cout << a[z-y]+b[y] << endl;
}else{
cout << c[z].first << endl;
}
}
}
int main(){
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
京公网安备 11010502036488号