CF#555Div3 1157 题解
A Reachable Numbers
题意
求$n$经过多次f函数的变换能够经过的数的个数。
思路
用set或map模拟即可。
代码
//#define Test
#include<bits/stdc++.h>
using namespace std;
const int Nmax=1e6+7;
typedef long long ll;
inline ll f(ll x)
{
x++;
while(x%10==0)
x/=10;
return x;
}
map<ll,int> book;
int main()
{
#ifdef Test
freopen("1.in","r",stdin);
#endif
ll n;
cin>>n;
while(!book[n])
{
book[n]=1;
n=f(n);
}
cout<<book.size()<<endl;
return 0;
}
B Long Number
题意
给一个数字串，可以利用f换连续的一段数字，输出变换后字典序最大的串。
思路
贪心地从左到右枚举，如果当前的数字可以变大则变大，直到遇到会变小的位置停止。
代码
//#define Test
#include<bits/stdc++.h>
using namespace std;
const int Nmax=1e6+7;
typedef long long ll;
char s[Nmax];
int f[27];
int main()
{
#ifdef Test
freopen("1.in","r",stdin);
#endif
int n;
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;i<=9;i++)
cin>>f[i];
int flag=0;
for(int i=1;i<=n;i++)
{
int num=s[i]-'0';
if(!flag && f[num]>num)
{
s[i]=f[num]+'0';
flag=1;
}
else if(flag)
{
if(f[num]<num)
break;
s[i]=f[num]+'0';
}
}
printf("%s\n",s+1);
return 0;
}
C1 Increasing Subsequence (easy version)
题意
每次可以从数列的最左或最右取出一个数字，要求取出的数字严格单调增。保证没有相同数字。
思路
每次选择最小的那个数字即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int Nmax=1e6+7;
typedef long long ll;
int a[Nmax];
vector<char> v;
int ans;
int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
int l=1,r=n;
int last=0;
while(l<=r)
{
if(last<a[l] && last<a[r])
{
if(a[l]<a[r])
{
last=a[l];
l++;
ans++;
v.push_back('L');
}
else
{
last=a[r];
r--;
ans++;
v.push_back('R');
}
}
else if(last<a[l])
{
last=a[l];
l++;
ans++;
v.push_back('L');
}
else if(last<a[r])
{
last=a[r];
r--;
ans++;
v.push_back('R');
}
else
break;
}
cout<<ans<<endl;
for(auto c:v)
cout<<c;
cout<<endl;
return 0;
}
C2 Increasing Subsequence (hard version)
题意
每次可以从数列的最左或最右取出一个数字，要求取出的数字严格单调增。
思路
每次选择最小的那个数字，如果左右的数字相同，则哪一边能选得最多就选哪边。
代码
#include<bits/stdc++.h>
using namespace std;
const int Nmax=1e6+7;
typedef long long ll;
int a[Nmax];
vector<char> v;
int ans;
int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
int l=1,r=n;
int last=0;
while(l<=r)
{
if(last<a[l] && last<a[r])
{
if(a[l]<a[r])
{
last=a[l];
l++;
ans++;
v.push_back('L');
}
else if(a[r]<a[l])
{
last=a[r];
r--;
ans++;
v.push_back('R');
}
else
break;
}
else if(last<a[l])
{
last=a[l];
l++;
ans++;
v.push_back('L');
}
else if(last<a[r])
{
last=a[r];
r--;
ans++;
v.push_back('R');
}
else
break;
}
int lans=0,rans=0;
if(l<=r)
{
if(last<a[l])
{
int llast=last;
int ll=l;
while(ll<=r && llast<a[ll])
{
lans++;
llast=a[ll];
ll++;
}
}
if(last<a[r])
{
int rlast=last;
int rr=r;
while(l<=rr && rlast<a[rr])
{
rans++;
rlast=a[rr];
rr--;
}
}
}
ans+=max(lans,rans);
cout<<ans<<endl;
for(auto c:v)
cout<<c;
if(lans && lans>rans)
for(int k=1; k<=lans; k++)
cout<<"L";
if(rans && lans<=rans)
for(int k=1; k<=rans; k++)
cout<<"R";
cout<<endl;
return 0;
}
D N Problems During K Days
题意
构造一个长度为$k$的序列，使其和为$n$，要求$a_i \le a_i+1 \le 2a_i$且$a_i \ge 0$ 。
思路
先找到一个长度为$k$的等差序列，使其和$sum \le n$，并且$sum > n$，即找到和最大的等差序列。
此后我们从后往前贪心地将$a_i$变为它需要满足的最大值即可构造出答案。
代码
//#define Test
#include<bits/stdc++.h>
using namespace std;
const int Nmax=1e6+7;
typedef long long ll;
int k;
ll n;
ll a[Nmax];
ll sum;
inline int check()
{
ll res=0LL;
for(int i=1; i<=k; i++)
res+=a[i];
if(res==n)
return 1;
return 0;
}
inline int print()
{
cout<<"YES"<<endl;
for(int i=1; i<=k; i++)
printf("%lld%c",a[i],i==k?'\n':' ');
exit(0);
return 0;
}
int main()
{
#ifdef Test
#endif
//freopen("in5.txt","r",stdin);
cin>>n>>k;
for(ll l=max((ll)1,(ll)(2*n/k-k+1)/2-2);; l++)
{
sum=(ll)(l+l+k-1)*k/2;
if(sum<=n && sum+k>n)
{
for(int i=1; i<=k; i++)
a[i]=(ll)(l+i-1);
break;
}
if(sum>n)
return 0*printf("NO\n");
}
if(sum>n)
return 0*printf("NO\n");
ll left=n-sum;
if(left==0)
return 0*print();
for(int i=k; i>=1; i--)
{
ll can;
ll mmax;
if(i==1)
mmax=a[i+1]-1LL;
else
mmax=a[i-1]*2LL;
can=mmax-a[i];
if(can>=left)
{
a[i]+=left;
return 0*print();
}
else
{
left-=can;
a[i]=mmax;
}
}
if(check())
return 0*print();
return 0*printf("NO\n");
}
E Minimum Array
题意
给两个长度为$n$的序列$a,b$，将$b$重新排序后，输出$c_i=(a_i+b_i) \bmod n$，要求$c$的字典序最小。
思路
对于每个$a_i$，找到第一个大于等于$n-a_i$的值就是对应的$b_i$，使用map或multiset维护一下即可。
代码
//#define Test
#include<bits/stdc++.h>
using namespace std;
const int Nmax=1e6+7;
typedef long long ll;
int n;
int a[Nmax],b[Nmax],c[Nmax];
int book[Nmax];
int mod;
map<int,int> mp;
int main()
{
#ifdef Test
freopen("1.in","r",stdin);
#endif
cin>>n;
mod=n;
for(int i=1; i<=n; i++)
cin>>a[i];
for(int i=1; i<=n; i++)
{
cin>>b[i];
mp[b[i]]++;
}
for(int i=1; i<=n; i++)
{
int now=n-a[i];
auto it=mp.lower_bound(now);
if(it==mp.end())
it=mp.begin();
int val=it->first;
mp[val]--;
if(mp[val]==0)
mp.erase(val);
c[i]=(a[i]+val)%n;
}
for(int i=1; i<=n; i++)
printf("%d%c",c[i],i==n?'\n':' ');
return 0;
}
F Maximum Balanced Circle
题意
给一个序列，要求从中选一些数形成新的环形序列，使其相邻两个之间的差值不大于1。
思路
我们考虑这个答案中的最小值，会发现答案序列是先增后降的，并且中间的部分除了顶峰外每个都需要大于等于2，因此我们只需要枚举最小值，不断向上找知道不能往上爬为止即可。
观察到如果最小值$l$可以满足条件，那么$l+1$为最小值的答案不优于$l$的答案，因此可以直接跳过最小值到最大值的部分继续枚举，因为每个点只被枚举了一次，这样时间复杂度是$O(n)$。
有一种特殊情况是上一个序列的顶峰只出现了一次，但是是下一个序列的最小值，并且下一个序列是答案，所以我们不能直接跳过顶峰，下次枚举应该从顶峰开始。
代码
//#define Test
#include<bits/stdc++.h>
using namespace std;
const int Nmax=1e6+7;
typedef long long ll;
int n;
int a[Nmax];
int book[Nmax];
inline int check(int min,int &max)
{
int ans=0;
int x=min;
while(book[x+1]>=2)
{
ans+=book[x+1];
x++;
}
if(book[x+1]==1)
x++,ans++;
max=x;
ans+=book[min];
return ans;
}
vector<int> v;
inline void get(int min,int max)
{
for(int i=min;i<=max;i++)
{
while(book[i]>1)
{
book[i]--;
v.push_back(i);
}
}
for(int i=max;i>=min;i--)
{
if(book[i])
v.push_back(i);
}
}
int vis[Nmax];
int main()
{
#ifdef Test
freopen("1.in","r",stdin);
#endif
cin>>n;
int m=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
m=max(m,a[i]);
book[a[i]]++;
}
int ans=0,ansl,ansr;
for(int i=1;i<=m;i++)
{
if(vis[i] || !book[i])
continue;
int l=i,r=i;
int now=check(l,r);
vis[l]=1;
if(ans<now)
{
ans=now;
ansl=l;
ansr=r;
}
i=r-1;
}
cout<<ans<<endl;
get(ansl,ansr);
for(int i=0;i<ans;i++)
printf("%d%c",v[i],i==ans-1?'\n':' ');
return 0;
}
G Inverse of Rows and Columns
题意
没看
思路
待补
代码
