Save the position of each character in the corresponding vector, and then select the smallest value each time.
That way, all strings can be generated. The complexity is $$$\Theta(n|c|^2)$$$, we can also use the priority queue do it in $$$\Theta(n|c|\log|c|)$$$.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
const int MOD=998244353;
void Delta() {
string s,answer;cin >> s;
vector<vector<int>> Q(26,vector<int>{});
for(int i=0;i<(int)s.size();++i)
Q[s[i]-'a'].push_back(i);
for(int i=0;i<26;++i)
reverse(Q[i].begin(),Q[i].end());
while(true) {
bool flag=true;
for(int i=0;i<26;++i)
if(!Q[i].empty()) flag=false;
if(flag) break;
vector<bool> Flag(26,false);
string temp;
for(int j=0;j<26;++j) {
int mnidx=-1,mnvalue=2147483647;
for(int i=0;i<26;++i)
if(!Flag[i]&&!Q[i].empty()&&Q[i].end()[-1]<mnvalue) {
mnvalue=Q[i].end()[-1];
mnidx=i;
}
if(mnidx==-1) break;
Q[mnidx].pop_back();
temp.push_back(s[mnvalue]);
Flag[mnidx]=true;
}
answer=temp;
}
cout << answer << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) Delta();
}
Using Greed to solve this problem.
If two points are on a straight line, they can be directly reached through the line. This must be the shortest.
Otherwise, we hope to follow as many curves as possible. Because the arc of a unit is $$$\frac{\pi}{2}$$$, it can replace the effect of $$$2$$$ straight lines.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const long double pi=3.141592653589793238462643383279L;
void Delta() {
long double x1,y1,x2,y2,answer;
cin >> x1 >> y1 >> x2 >> y2;
if((x1==0&&x2==0)||(y1==0&&y2==0))
answer=abs(x1+y1-x2-y2);
else {
x1=abs(x1);y1=abs(y1);x2=abs(x2);y2=abs(y2);
answer=pi/2*min(x1+y1,x2+y2)+max(x1+y1,x2+y2)-min(x1+y1,x2+y2);
}
if(abs(answer)>100000000) cout << (int)answer << endl;
else cout << fixed << setprecision(20) << answer << endl;
}
signed main() {
cin.tie(0);
int T;cin >> T;
while(T--) Delta();
}
Another problem of greed.
Let's first consider the situation of the last position. Obviously, the last position can only be modified by manipulating the entire string.
Therefore, we first change the last position, and then change the last two positions until all strings are the same.
For each position, there are some strings that are either $$$0$$$ or $$$1$$$. Each time we select fewer strings to change. Because the answer only requires comparing the strings, modifying more or fewer will not affect subsequent operations.
To facilitate the calculation of flipping, flip tags can be used for maintenance. It's $$$\Theta(nm)$$$
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define int long long
const int MOD=998244353;
string a[100001];
bool flip[100001];
void Delta() {
int n,m,answer=0;
cin >> n >> m;
for(int i=1;i<=n;++i) {
cin >> a[i];
flip[i]=false;
}
for(int i=m-1;i>=0;--i) {
vector<int> c[2];
for(int j=1;j<=n;++j)
c[(a[j][i]-'0')^flip[j]].push_back(j);
for(int j:(c[0].size()>c[1].size()?c[1]:c[0])) {
answer++;
flip[j]^=true;
}
}
cout << answer << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin >> T;
while(T--) Delta();
}
For this problem we can use binary serach to solve it.
Firstly, if there is a square of size $$$x$$$, then there must also be a square of size $$$x-1$$$, so we can use binary serach.
To verify the existence of a square of size $$$x$$$, we use a sliding window for maintenance. In a sliding window, we place all soldiers in their positions. If there is an adjacent position difference greater than $$$x$$$, then we can place a square of size x at this position.
For calculating sliding windows, we can use multiset for maintenance. Use one multiset to maintain all soldier positions and query adjacent soldiers, while another multiset is used to maintain all adjacent differences and find the maximum value.
That way, we can make single modifications in $$$\Theta(\log n)$$$, The total complexity is $$$\Theta(n\log^2n)$$$.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
long long isqrt(int x){long long a=x,b=(x+1)/2;while(a>b){a=b;b=(b+x/b)/2;}return a;}
const int MOD=998244353;
int n,a[50001];
void ins(multiset<int> &P,multiset<int> &Q,int x) {
auto itr=Q.insert(x),nxt=next(itr,1),pre=prev(itr,1);
P.erase(P.lower_bound(*nxt-*pre-1));
P.insert(*itr-*pre-1);
P.insert(*nxt-*itr-1);
}
void del(multiset<int> &P,multiset<int> &Q,int x) {
auto itr=Q.lower_bound(x),nxt=next(itr,1),pre=prev(itr,1);
P.insert(*nxt-*pre-1);
P.erase(P.lower_bound(*itr-*pre-1));
P.erase(P.lower_bound(*nxt-*itr-1));
Q.erase(itr);
}
bool check(int x) {
int answer=0;
multiset<int> Q={0,n+1},P={n};
for(int i=1;i<=x;++i) ins(P,Q,a[i]);
answer=max(answer,*P.rbegin());
for(int i=x+1;i<=n;++i) {
ins(P,Q,a[i]);
del(P,Q,a[i-x]);
answer=max(answer,*P.rbegin());
}
return answer>=x;
}
void Delta() {
cin >> n;
for(int i=1;i<=n;++i) cin >> a[i];
int l=1,r=n,m,s=0;
while(l<=r) {
m=(l+r)/2;
if(check(m)) {
l=m+1;s=m;
} else r=m-1;
}
cout << s << endl;
if(s==isqrt(n-1)) cout << "NO" << endl;
else cout << "YES" << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
Delta();
}
Interesting problem.
First, this $$$69$$$ is not special, so we first subtract all of $$$a_i$$$ from $$$69$$$ and then turn the problem into at most $$$0$$$.
Consider, if we already know a sequence, how do we decide whether it can become $$$0$$$? For some prefix and suffix operations, we can translate this into the sum of an ascending sequence and a descending sequence.
Here is a greedy observation. Because a falling sequence cannot rise again once it has fallen, and can fall at any time, we want the value of the falling sequence to be as large as possible. The same goes for an ascending sequence, the smaller the better.
So we would set the first value of the ascending sequence to $$$0$$$ and the first value of the descending sequence to $$$a_1$$$. (assuming $$$a_1$$$ is the first number to become $$$0$$$)
It is easy to find that the sum of the ascending and descending sequences must equal the last number taken, and that each number taken must degrade the sequence value. So there is monotonicity here.
Since $$$n$$$ is small and $$$a_i$$$ is large, you can set the dp state to "$$$x$$$ numbers are taken from $$$1$$$ to $$$i$$$ and last is $$$a_i$$$, and the minimum value of the ascending sequence at that point is $$$dp_{i,x}$$$".
For the initial value we have $$$dp_{i,1}=0$$$, and the transfer has $$$dp_{i,x}=\text{min}_{j<i\text{ and }dp_{j,x-1}\le a_i}(\max(0,a_i-a_j)+dp_{j,x-1})$$$. It's $$$\Theta(n^3)$$$, not fast enough, so it needs optimization.
First, $$$a_i$$$ is discretized, and then stored $$$\min dp_j$$$ and $$$\min dp_j-a_j$$$ with segment tree. The values of max in dp transitions are classified and then calculated separately. Then the total complexity is $$$\Theta(n^2\log n)$$$.
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
struct node {int mndp,mndpa;};
node merge(node a,node b) {return {min(a.mndp,b.mndp),min(a.mndpa,b.mndpa)};}
template <class T> class segment {
private:
int id(int l,int r){return (l+r)|(l!=r);}
void change(int l,int r,int x,T &y){if(l==r){seg[id(l,r)]=y;return;}int mid=(l+r)/2;if(x<=mid)change(l,mid,x,y);else change(mid+1,r,x,y);seg[id(l,r)]=merge(seg[id(l,mid)],seg[id(mid+1,r)]);}
T query(int L,int R,int l,int r){if(l<=L&&R<=r)return seg[id(L,R)];int mid=(L+R)/2;if(l<=mid&&r>mid)return merge(query(L,mid,l,r),query(mid+1,R,l,r));if(l<=mid)return query(L,mid,l,r);return query(mid+1,R,l,r);}
public:
vector<T> seg;int siz;
segment(int n){siz=n;seg.resize(2*n+4);}
void change(int x,T y){change(1,siz,x,y);}
T query(int l,int r){return query(1,siz,l,r);}
};
const int MOD=998244353;
int n,a[2001],b[2001],dp[2001][2001],answer;
void Delta() {
cin >> n;vector<int> Q;
for(int i=1;i<=n;++i) {
cin >> a[i];a[i]-=69;
Q.push_back(a[i]);
}
Q.push_back(-2147483647);sort(Q.begin(),Q.end());
Q.resize(unique(Q.begin(),Q.end())-Q.begin());
for(int i=1;i<=n;++i) {
dp[i][1]=0;
b[i]=lower_bound(Q.begin(),Q.end(),a[i])-Q.begin();
}
for(int x=2;x<=n;++x) {
segment<node> P(n);
for(int i=1;i<=n;++i) dp[i][x]=2147483647;
for(auto &i:P.seg) i={2147483647,2147483647};
for(int i=1;i<=n;++i) {
dp[i][x]=min(dp[i][x],P.query(b[i],n).mndp);
dp[i][x]=min((long long)dp[i][x],(long long)P.query(1,b[i]).mndpa+a[i]);
P.change(b[i],{dp[i][x-1],dp[i][x-1]-a[i]});
}
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(dp[i][j]<=a[i])
answer=max(answer,j);
cout << answer << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
Delta();
}
