This Div2 was a hell of a game, but the harvest was great (the remaining two questions of Div1 really couldn't be filled)
"Game link"
A. Two Subsequences
Difficulty: \ (800 \) (sign in question)
Main idea of the title:
Split the string \ (S \) into two substrings \ (A \) and \ (B \), so that the dictionary order of \ (A \) is less than \ (B \).
Idea:
Directly make only the smallest letter in \ (S \) in the \ (A \) string and all remaining characters in \ (B \).
code:
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,t;
char str[N];
int pos;
inline void Read()
{
pos=1;
scanf("%s",str+1);
n=strlen(str+1);
}
inline void Work()
{
for(int i=2;i<=n;i++)
if(str[i]<str[pos]) pos=i;
putchar(str[pos]),putchar(' ');
for(int i=1;i<=n;i++)
if(pos!=i) putchar(str[i]);
putchar('\n');
}
int main()
{
scanf("%d",&t);
while(t--)
{
Read();
Work();
}
return 0;
}
B. Divine Array
Difficulty: \ (1100 \) (thinking problem)
Main idea of the title:
You have a sequence \ (S \). Each transformation will change the number of times in a sequence \ (a_i \) to its occurrence in \ (S \).
Ask the value of position \ (x \) after \ (k \) transformation
Idea:
It can be found that the sequence will be stable after a certain number of times. (the official explanation will be stable if it does not exceed \ (logn \) times). I use \ (n \) times here. Directly take the array simulation and record the value of each position of each transformation.
code:
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int a[N][N],cnt[N];
int n,T,q;
inline void Read()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i][0]);
}
inline void Work()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cnt[j]=0;
for(int j=1;j<=n;j++)
cnt[a[j][i-1]]++;
for(int j=1;j<=n;j++)
a[j][i]=cnt[a[j][i-1]];
}
scanf("%d",&q);
while(q--)
{
static int x,k;
scanf("%d%d",&x,&k);
printf("%d\n",a[x][min(k,n)]);
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
Read();
Work();
}
return 0;
}
C. Array Elimination
Difficulty: \ (1300 \) (thinking problem)
Main idea of the title:
You have a sequence \ (S \) you can select \ (k \) values in the sequence at a time and subtract their bitwise AND. Please find all \ (k \) that can delete the sequence.
Idea:
We can decompose each number into bits under binary, and count the number of each \ (1 \) respectively. It can be proved that if we take the number of \ (k \) that is \ (1 \) in a bit, we can reduce the number of that person \ (k \), so \ (k \) must be a factor of the number of occurrences of that person. Therefore, we can directly enumerate the value \ (k\in[1,n] \) of \ (k \) to see if it is the divisor of all numbers.
code:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,S=30;
int t,n;
int a[N],cnt[S];
inline void Read()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
}
inline void Work()
{
for(int i=0;i<30;i++) cnt[i]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<30;j++)
if(a[i]>>j&1) cnt[j]++;
for(int i=1;i<=n;i++)
{
bool flag=true;
for(int j=0;j<30;j++)
if(cnt[j]%i!=0)
{
flag=false;
break;
}
if(flag) printf("%d ",i);
}
putchar('\n');
}
int main()
{
scanf("%d",&t);
while(t--)
{
Read();
Work();
}
return 0;
}
D. Frog Traveler
Difficulty: \ (1900 \) (underworld question)
Main idea of the title:
You are a frog. You can jump \ (h\in[0,a_i] \) meters at the bottom of the well at the beginning. If you reach the position of \ (J \), you will fall \ (b_j \) meters. How many times do you have to jump at least to reach the position outside the well (\ (0 \).
Idea:
You can consider the method of optimizing the drawing of the line segment tree (see the code), establish a virtual point \ (i+n \) for each point, establish an edge with a weight of \ (0 \) from each point to its virtual point, and connect each virtual point \ (i+n \) to an edge with a weight of \ (i-b_i \). For \ (I \) an edge with a weight of \ (1 \) from \ (I \) to \ ([i + 1, I + a_, I] \).
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+10,M=N<<5;
int n,m;
int a[N],b[N];
int h[M],e[M],ne[M],w[M],idx;
int dis[M],pre[M];
bool vis[M];
inline void Add(int a,int b,int c)
{
e[++idx]=b;
ne[idx]=h[a];
h[a]=idx;
w[idx]=c;
}
namespace SegmentTree
{
struct node
{
int id;
#define id(x) unit[(x)].id
}unit[M];
int cnt;
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1|1)
#define mid (l+r>>1)
void Build(int k,int l,int r)
{
if(l==r) return (void)(id(k)=l+n+1);
id(k)=++cnt;
Build(lson(k),l,mid),Build(rson(k),mid+1,r);
Add(id(k),id(lson(k)),0),Add(id(k),id(rson(k)),0);
}
void Update(int k,int l,int r,int L,int R,int st)
{
if(L<=l&&R>=r) return Add(st,id(k),1);
if(L<=mid) Update(lson(k),l,mid,L,R,st);
if(R>mid) Update(rson(k),mid+1,r,L,R,st);
}
}
using namespace SegmentTree;
deque<int> q;
inline void Bfs()
{
memset(dis,0X3f,sizeof(dis));
dis[n]=0,q.push_back(n);
while(q.size())
{
auto t=q.front();q.pop_front();
if(vis[t]) continue;
vis[t]=true;
for(int i=h[t];i;i=ne[i])
{
int j=e[i];
if(dis[j]>dis[t]+w[i])
{
dis[j]=dis[t]+w[i];
if(w[i]) q.push_back(j);
else q.push_front(j);
pre[j]=t;
}
}
}
}
inline void Read()
{
scanf("%d",&n);
cnt=2*n+1;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
}
vector<int> path;
inline void Work()
{
for(int i=0;i<=n;i++) Add(i+n+1,i+b[i],0);
Build(1,0,n);
for(int i=1;i<=n;i++)
Update(1,0,n,i-a[i],i,i);
Bfs();
printf("%d\n",dis[0]==0X3f3f3f3f ? -1 : dis[0]);
if(dis[0]!=0X3f3f3f3f)
{
int now=0;
while(now!=n)
{
if(n+1<=now&&now<=2*n+1) path.push_back(now-n-1);
now=pre[now];
}
reverse(path.begin(),path.end());
for(auto x : path)
printf("%d ",x);
putchar('\n');
}
}
int main()
{
Read();
Work();
return 0;
}
E. Optimal Insertion
Difficulty: \ (2300 \) (Yangjian question)
Main idea of the title:
You have A sequence \ (A \) and A sequence \ (B \). You should insert each element in the sequence \ (B \) anywhere in \ (A \) to minimize the reverse logarithm of the new sequence.
Idea:
It is easy to see A conclusion that after sorting the \ (B \) sequence, the answer to insert the \ (A \) sequence according to the relative position is the smallest, ((each element in \ (B \) will only contribute to the original elements of \ (A \) and will not contribute to its own elements). Then divide and conquer insertion can be considered. Insert \ (b_{mid} \) in the divide and conquer interval each time, find the position with the least contribution, and divide and conquer into two intervals after insertion. Note: multiple numbers can be inserted in one position!!!.
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,m,T;
int a[N],b[N],pos[N];
int suml[N],sumr[N];
vector<int> newa,nums;
void Solve(int lb,int rb,int la,int ra)
{
if(lb>rb) return;
int mid=lb+rb>>1;
suml[la-1]=0;
for(int i=la;i<=ra;i++)
{
suml[i]=sumr[i]=0;
if(a[i]>b[mid]) suml[i]++;
if(a[i]<b[mid]) sumr[i]++;
}
for(int i=la+1;i<=ra;i++) suml[i]+=suml[i-1];
for(int i=ra-1;i>=la;i--) sumr[i]+=sumr[i+1];
pos[mid]=la;
for(int i=la+1;i<=ra;i++)
if(suml[i-1]+sumr[i]<suml[pos[mid]-1]+sumr[pos[mid]])
pos[mid]=i;
Solve(lb,mid-1,la,pos[mid]),Solve(mid+1,rb,pos[mid],ra);
}
namespace BIT
{
int unit[N<<1],siz;
#define lowbit(x) ((x)&-(x))
inline void Clear(int x)
{
siz=x;
for(int i=1;i<=siz;i++) unit[i]=0;
}
inline void Add(int x,int val)
{
for(x;x<=siz;x+=lowbit(x)) unit[x]+=val;
}
inline int Query(int x)
{
int res=0;
for(x;x;x-=lowbit(x)) res+=unit[x];
return res;
}
}
using namespace BIT;
inline void Read()
{
scanf("%d%d",&n,&m);
nums.clear(),newa.clear();
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
nums.push_back(a[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&b[i]);
nums.push_back(b[i]);
}
}
inline void Work()
{
sort(b+1,b+m+1);
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
for(int i=1;i<=n;i++) a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
for(int i=1;i<=m;i++) b[i]=lower_bound(nums.begin(),nums.end(),b[i])-nums.begin()+1;
Solve(1,m,1,n+1);
int now=m;
for(int i=n+1;i>=0;i--)
{
if(i!=n+1&&i!=0) newa.push_back(a[i]);
while(now&&pos[now]==i) newa.push_back(b[now--]);
}
ll ans=0;
Clear(nums.size());
for(auto x : newa)
{
ans+=Query(x-1);
Add(x,1);
}
printf("%lld\n",ans);
}
int main()
{
scanf("%d",&T);
while(T--)
{
Read();
Work();
}
return 0;
}
F. Difficult Mountain
Difficulty: \ (2700 \) (hell greedy question)
Main idea of the title:
For a mountain, there is an initial \ (d \), there are \ (n \) people ready to climb the mountain, and there are two attributes \ (\ {s_i,a_i \} \) for each person. For each person \ (s_i \geq d \), they can climb the mountain and change \ (d \) to \ (max(d,a_i) \).
How many people can climb the mountain at most.
Idea:
Exclude the person whose initial \ (s_i \) is less than \ (d \). Greedy idea: sort according to \ (max(a_i,s_i) \) and then simulate statistics in order.
Proof: for classified discussion, if you now consider the \ (I \) person, if \ (s_i\geq a_i \), then \ (s_i\geq d \), this person can be selected and must be selected. If there is a person behind \ (max(a_j,s_j)=a_j \) and \ (s_j < a_i \) cannot be selected because of him, if this person must be selected, at least delete \ (I \) and because there must be $a_ j > a_ I $the answer will only get worse.
If \ (a_i > s_i \) and \ (I \) is selected, the same can be proved. If \ (I \) is not selected, it can be ignored.
code:
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,d,idx;
struct PII
{
int s,a;
inline bool operator<(const PII &t) const
{
if(max(a,s)!=max(t.a,t.s)) return max(a,s)<max(t.a,t.s);
return s<t.s;
}
}que[N];
inline void Read()
{
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)
{
static int s,a;
scanf("%d%d",&s,&a);
if(s<d) continue;
que[++idx]={s,a};
}
}
inline void Work()
{
sort(que+1,que+idx+1);
int ans=0;
for(int i=1;i<=idx;i++)
if(que[i].s>=d)
d=max(d,que[i].a),ans++;
printf("%d\n",ans);
}
int main()
{
Read();
Work();
return 0;
}