#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n;
int a[N];
int main()
{
//freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) printf("%d%c",a[i]*(i&1?1:-1),i==n?'\n':' ');
}
//fclose(stdin);
return 0;
}
We just sort the array and set $$$a_i:=-a_i$$$ for all even $$$i$$$.
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t --> 0) {
string s;
int k;
cin >> s >> k;
int n = (int)s.length();
int mn = n - k;
for (int i = n - k - 1; i >= 0; i--) {
if (s[i] > s[i + k]) {
mn = i;
}
}
string ans = s.substr(0, mn) + s.substr(mn + k);
cout << ans << '\n';
}
return 0;
}
Coming soon...
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n,k,ans;
int p[N],d[N],pre[N];
int dp[N][2];
int main()
{
//freopen("test.in","r",stdin);
T=1;
//scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
for(int i=1;i<=n;i++) scanf("%d",&d[i]);
ans=0;
pre[0]=k;
for(int i=1;i<=n;i++)
{
if((d[i]&&pre[i-1]>=1900)||((!d[i])&&pre[i-1]<=2100)) pre[i]=(p[i]-pre[i-1])/4+pre[i-1];
else pre[i]=pre[i-1];
}
ans=max(pre[n-1],pre[n]);
for(int i=0;i<=4000;i++) dp[i][(n+1)&1]=i;
for(int i=n;i>=2;i--)
{
for(int j=0;j<=4000;j++)
{
if((d[i]&&j>=1900)||((!d[i])&&j<=2100)) dp[j][i&1]=dp[(p[i]-j)/4+j][(i+1)&1];
else dp[j][i&1]=dp[j][(i+1)&1];
}
ans=max(ans,dp[pre[i-2]][i&1]);
}
/*for(int i=0;i<=4000;i++) dp[n+1][i]=i;
for(int i=n;i;i--)
{
for(int j=0;j<=4000;j++)
{
if((d[i]&&j>=1900)||((!d[i])&&j<=2100)) dp[i][j]=dp[i+1][(p[i]-j)/4+j];
else dp[i][j]=dp[i+1][j];
}
}
ans=dp[1][k];kk=k;
for(int i=1;i<=n;i++)
{
ans=max(ans,(int)dp[i+1][k]);
if((d[i]&&k>=1900)||((!d[i])&&k<=2100)) k=(p[i]-k)/4+k;
}*/
printf("%d\n",k-ans);
}
//fclose(stdin);
return 0;
}
The key to solving the problem is to notice that $$$k$$$ is small ($$$k \leq 4000$$$).The intended solution is $$$O(nk)$$$.
We note $$$dp_{i,j}$$$ as the final rating when current score is $$$j$$$, participating in the $$$i, i+1,...,n_{th}$$$ contest.
We can enumerate the skipped contest and update the answer with the $$$dp$$$ array.
To avoid exceeding the memory limit, you need to use a scrolling array.
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int MOD = 1e9 + 7;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
vector<int> fac(2222222);
fac[0] = 1;
for (int i = 1; i <= 2000000; i++) {
fac[i] = (fac[i - 1] * i) % MOD;
}
auto binpow = [&](int x, int y) {
int res = 1;
while (y > 0) {
if (y & 1) (res *= x) %= MOD;
(x *= x) %= MOD;
y >>= 1;
}
return res;
};
vector<int> inv(2222222);
inv[2000000] = binpow(fac[2000000], MOD - 2);
for (int i = 1999999; i >= 0; i--) {
inv[i] = (inv[i + 1] * (i + 1)) % MOD;
}
auto comb = [&](int n, int r) {
if (n < r) {
cout << "hi\n";
exit(0);
}
return fac[n] * inv[r] % MOD * inv[n - r] % MOD;
};
int t;
cin >> t;
while (t --> 0) {
int n, m;
cin >> n >> m;
// general case: a1 + a2 + a3 + .. + an = m -> C(m - 1, n - 1)
int ans = comb(m - 1, n - 1);
if (n - 1 <= m - (m + 1) / 2) {
ans -= n * comb(m - (m + 1) / 2 - 1 + 1, n - 1 - 1 + 1);
}
ans %= MOD;
ans += MOD;
ans %= MOD;
cout << ans << '\n';
}
return 0;
}
As we all know,the sum of the two sides of a triangle is greater than the third side.Similarly,we can infer condition $$$3$$$ is equviant to $$$max(a_i)< \lceil m/2 \rceil$$$.
What's the number of arrays satisfying the following condition?
1.All $$$a_i$$$ are positive integers;
2.$$$\Sigma a_i=m$$$.
The answer is $$$C^{m-1}_{n-1}$$$.It's a classic problem.
$$$C^i_j+C^{i-1}_j+...+C^j_j=C^{i+1}_{j+1}$$$.
We find it's easier to calculate bad arrays.When $$$max(a_i)=\lceil m/2 \rceil,\lceil m/2 \rceil+1,...$$$,$$$a$$$ is a bad array.
The total of bad array is $$$n*(C^{m-\lceil m/2 \rceil}_{n-2}+C^{m- \lceil m/2 \rceil-1}_{n-2}+...)=n*C^{\lfloor m/2 \rfloor}_{n-1}$$$.
The final answer is $$$C^{m-1}_{n-1}-n*C^{\lfloor m/2 \rfloor}_{n-1}$$$
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int INFF = 1e18;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t --> 0) {
int n, m, s;
cin >> n >> m >> s;
set<pair<int, int>> st;
st.insert({s, 0});
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
vector<pair<int, int>> del;
int mnl = INFF, mnr = INFF;
for (auto it = st.lower_bound({l, 0}); it != st.end(); it++) {
if (it->fi > r) break;
if (l - 1 >= 1) {
mnl = min(mnl, it->se + it->fi - l + 1);
}
if (r + 1 <= n) {
mnr = min(mnr, it->se + r + 1 - it->fi);
}
del.push_back(*it);
}
for (auto p : del) st.erase(p);
auto it = st.lower_bound({l - 1, 0});
if (it != st.end() && it->fi == l - 1) {
mnl = min(mnl, it->se);
st.erase(it);
}
auto it2 = st.lower_bound({r + 1, 0});
if (it2 != st.end() && it2->fi == r + 1) {
mnr = min(mnr, it2->se);
st.erase(it2);
}
if (l - 1 >= 1) {
st.insert({l - 1, mnl});
}
if (r + 1 <= n) {
st.insert({r + 1, mnr});
}
}
int ans = INFF;
for (auto [pos, cost] : st) {
ans = min(ans, cost);
}
cout << ans << '\n';
}
return 0;
}
The original idea of this problem is using segment tree, hence the $$$n \leq 2\cdot 10^5$$$ constraint. However, this problem can be solved easier by using std::set.
For this problem, we can do DP to solve the problem.
Define $$$dp_i$$$ after the $$$j$$$-th attack as minimum energy needed to avoid the first $$$j$$$ attacks and we ended up at tile $$$i$$$. If we try updating all $$$n$$$ indices for each attack (by doing $$$dp_i=\min (dp_i,dp_j+|dp_j-dp_i|)$$$ for all $$$1 \leq j \leq n$$$), that will cost $$$O(n)$$$ transition, which means the complexity will be $$$O(n^2m)$$$ per test case. Since it's too slow, we need some observation.
Observation. For the $$$k$$$-th attack, we only need to update two DP indices each attack and it's optimal to do $$$dp_i=\min (dp_i,dp_j+|dp_j-dp_i|)$$$ where $$$i=l_k-1$$$ or $$$i=r_k+1$$$ (if those two indices actually exist inside the range $$$[1,n]$$$) and $$$l_k \leq j \leq r_k$$$
Proof. Assume that everytime the boss attacks, it is sometimes optimal for us to move if we didn't stand inside the incoming lazer previously. So, assume at some point, we went to the right $$$y$$$ tiles as the "optimal" route. Then, there are three cases for the next attack:
The current optimal route involves going to the left by $$$x$$$ tiles $$$(x > y)$$$. In this case, the current optimal is not the same as the previous optimal, since we could've just not move in previous turn and then move to the left by $$$x-y$$$ tiles.
The current optimal route involves going to the left by $$$x$$$ tiles $$$(0 < x \leq y)$$$. In this case, the current optimal is also not the same as the previous optimal, since we could've just not move in previous turn and then move to the right by $$$y-x$$$ tiles.
The current optimal route involves going to the right by $$$x$$$ tiles $$$(x \geq 0)$$$. In this case, there is an alternative solution, where we could've just not move in previous turn and then move to the right by $$$x+y$$$ tiles. It'll result with the same energy spent.
So, it is optimal to do nothing if we don't stand inside the lazer.
If we do stand inside the lazer (assume it's the $$$j$$$-th lazer), it is optimal to go to either $$$l_j-1$$$ or $$$r_j+1$$$, since with the same idea as above, one of these tiles are either the most optimal solution, or one of the most optimal solution (think of it like a waterfall :]).
Now, with this in mind, we can implement this in $$$O(n\sum_{i=1}^n (r_i-li))$$$ per test case. Since it's still too slow, we can optimize it again. Notice that for each attack, we're only interested from the updates that actually give paths, not the one getting blocked by the lazer. So, we will try to implement this using C++ std::set. First, create the set $$$route$$$ which stores all previously updated $$$dp$$$ indices that give paths (since we update the tiles that will get hit by the lazer for each attack to $$$INF$$$ again after updating $$$dp{li-1}$$$ and $$$dp{r_i+1}$$$). Set $$$dp_i=INF$$$ for all $$$1 \leq i \leq n,i \neq s$$$, $$$dp_s=0$$$, and . Then, do the following for the j-th attack:
Find all the element $$$k$$$ in $$$route$$$ such that $$$l_j \leq k \leq rj$$$.
For each of the element satisfying the constraint above, update $$$dp{lj-1}$$$ to $$$\min(dp{l_j-1},dp_k+k-lj+1)$$$ and $$$dp{rj+1}$$$ to $$$\min(dp{r_j+1},dp_k+r_j+1-k)$$$
Set all $$$dp_k$$$ to $$$INF$$$, remove all elements satisfying the constraint above, and then add $$$l_j-1$$$ and $$$r_j+1$$$ to $$$route$$$
The time complexity of this would be $$$O(m\log m)$$$ with $$$O(n)$$$ initializer and $$$O(n)$$$ finding optimal of each $$$dp$$$ index for each test case.
To optimize this even further, notice that after all the $$$m$$$ attacks, every index outside the $$$route$$$ would have the value of $$$INF$$$, so we only need to check the minimum from all $$$dp$$$ with indices inside $$$route$$$ (which is $$$O(m)$$$) and only to reset those indices as well for the next test case (which is also $$$O(m)$$$).
Once again, beware of the fact that $$$l_i-1$$$ or $$$r_i+1$$$ might be out of the arena range.
Time complexity: $$$O(m\log m)$$$
Bonus: Solve the problem if $$$n \leq 10^9$$$
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int MOD = 1e9 + 7;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
vector<bool> ok(22222, 0);
auto conv = [&](int x) {
int res = 0;
while (x > 0) {
int y = x % 10;
res += y * y;
x /= 10;
}
return res;
};
for (int i = 1; i <= 16200; i++) {
int x = i;
set<int> vis;
while (!vis.count(x)) {
vis.insert(x);
int y = conv(x);
if (x == y) {
ok[i] = 1;
}
x = y;
}
}
vector<vector<int>> dp(222, vector<int>(22222)); // digit - sum
dp[0][0] = 1;
for (int i = 1; i <= 200; i++) {
for (int j = 0; j < 20000; j++) {
for (int k = 0; k <= 9; k++) {
dp[i][j + k * k] += dp[i - 1][j];
dp[i][j + k * k] %= MOD;
}
}
}
int t;
cin >> t;
while (t --> 0) {
string l, r;
cin >> l >> r;
auto calc = [&](string s, bool on) {
int res = 0;
int n = (int)s.length();
int cur = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < s[i] - '0'; j++) {
for (int k = cur + j * j; k <= 16200; k++) {
res += ok[k] * dp[n - i - 1][k - (cur + j * j)];
res %= MOD;
}
}
cur += (s[i] - '0') * (s[i] - '0');
}
if (ok[cur] && on) res += 1;
return res;
};
int ans = calc(r, 1) - calc(l, 0);
ans %= MOD;
ans += MOD;
ans %= MOD;
cout << ans << '\n';
}
return 0;
}
Notice that the biggest number we can obtain after exactly one operation is $$$81 \cdot 200 = 16200$$$.
We can solve the problem with digit DP (or DFS with memorization). Let $$$AN$$$ be the number of happy numbers less than or equal to $$$N$$$. Our answer would then be $$$A{ri} - A{l_i - 1}$$$.
Now we are interested in calculating $$$AN$$$ for some integer $$$N$$$. We do a DFS from the leftmost digit to the rightmost digit. Let $$$f{i, j}$$$ denote the number of happy numbers, less than or equal to $$$N$$$, with the sum of the first $$$i$$$ digits squared equal to $$$j$$$. We can do a DFS from left to right, taking note of whether the current digit sequence is exactly the same as $$$N$$$'s first digits; if not so, we can memorize the answer with $$$f_{i, j}$$$ (to avoid repeated calculations).
It is not hard to see that we are expected to reach every state once, and we can re-use $$$f$$$ over all test cases. Thus, the time complexity is $$$O(DS)$$$, where $$$D \leq 201$$$ is the number of digits and $$$S \leq 16200$$$ is the digit-squared sum.
#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 bk=500;
namespace sumadd {
int tag[bk],pb[bk],pre[bk][bk];
void addib(int l,int r,int id,int v) {
for(int i=0,x=0;i<=bk-1;++i){if(l<=i&&i<=r)x+=v;x+=tag[id];pre[id][i]+=x;}
tag[id]=0;
}
void add(int l,int r,int v) {
if(l/bk==r/bk) {
addib(l%bk,r%bk,l/bk,v);
for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
return;
}
if(l%bk!=0) {addib(l%bk,bk-1,l/bk,v);l+=bk-l%bk;}
if(r%bk!=bk-1) {addib(0,r%bk,r/bk,v);r-=r%bk+1;}
while(l<=r) {tag[l/bk]+=v;l+=bk;}
for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
}
int sum(int l,int r) {
if(l/bk==r/bk) {
return (r-l+1)*tag[l/bk]+pre[l/bk][r%bk]-(l%bk==0?0:pre[l/bk][l%bk-1]);
}
int sum=0;
if(l%bk!=0) {sum+=tag[l/bk]*(bk-l%bk)+pre[l/bk][bk-1]-(l%bk==0?0:pre[l/bk][l%bk-1]);l+=bk-l%bk;}
if(r%bk!=bk-1) {sum+=tag[r/bk]*(r%bk+1)+pre[r/bk][r%bk];r-=r%bk+1;}
sum+=pb[r/bk]-(l==0?0:pb[l/bk-1]);
return sum;
}
void cln() {
for(int i=0;i<bk;++i) {
tag[i]=pb[i]=0;
for(int j=0;j<bk;++j)
pre[i][j]=0;
}
}
}
pair<int,int> ivl[bk][bk];
array<int,4> qry[bk*bk];
int cnt[bk*bk],ans[bk*bk],flag[bk*bk];
vector<int> lp={0};
void Delta() {
int n,m,q;
cin >> n >> m >> q;
for(int i=1,l,r;i<=m;++i) {
cin >> l >> r;
ivl[i/bk][i%bk]={l,r};
lp.push_back(lp.end()[-1]+r-l+1);
}
cerr << endl;
lp.push_back(2147483647);
for(int i=1,o,l,r,v;i<=q;++i) {
cin >> o >> l >> r;
if(o==1) {cin >> v;qry[i]={1,l,r,v};sumadd::add(l,r,v);}
else {
auto il=lower_bound(lp.begin(),lp.end(),l-1),ir=prev(lower_bound(lp.begin(),lp.end(),r+1));
qry[i]={2,il-lp.begin()+1,ir-lp.begin(),0};
if(qry[i][1]==qry[i][2]+2) {
int p=qry[i][2]+1;
auto t=ivl[p/bk][p%bk];
l-=*prev(il);r-=*prev(il);
ans[i]=sumadd::sum(t.first+l-1,t.first+r-1);
flag[i]=true;
continue;
}
if(qry[i][1]==qry[i][2]+1) {
ans[i]=sumadd::sum(ivl[qry[i][2]/bk][qry[i][2]%bk].first+l-*prev(il)-1,ivl[qry[i][2]/bk][qry[i][2]%bk].second);
ans[i]+=sumadd::sum(ivl[qry[i][1]/bk][qry[i][1]%bk].first,ivl[qry[i][1]/bk][qry[i][1]%bk].first+r-*ir-1);
flag[i]=true;
continue;
}
if(il!=lp.begin()) {
int p=qry[i][1]-1;l=*il-l+1;
auto t=ivl[p/bk][p%bk];
ans[i]+=sumadd::sum(t.second+1-l,t.second);
}
if(next(ir)!=lp.end()) {
r-=*ir;
int p=qry[i][2]+1;
auto t=ivl[p/bk][p%bk];
ans[i]+=sumadd::sum(t.first,t.first+r-1);
}
if(flag[i]) ans[i]=-ans[i];
}
}
sumadd::cln();
for(int k=0;k<bk;++k) {
int sum=0;
for(int i=0;i<bk;++i) {
auto t=ivl[k][i];
if(t==pair<int,int>{0,0}) continue;
cnt[t.first]++;
cnt[t.second+1]--;
}
for(int j=1;j<=2;++j)
for(int i=1;i<=n;++i)
cnt[i]+=cnt[i-1];
for(int i=1;i<=q;++i)
if(qry[i][0]==1) {
sum+=qry[i][3]*(cnt[qry[i][2]]-(qry[i][1]==0?0:cnt[qry[i][1]-1]));
}
else
if(!flag[i]&&qry[i][1]<=k*bk&&k*bk+bk-1<=qry[i][2]) ans[i]+=sum;
for(int i=1;i<=n;++i) cnt[i]=0;
}
for(int i=1;i<=q;++i)
if(qry[i][0]==1)
sumadd::add(qry[i][1],qry[i][2],qry[i][3]);
else {
if(flag[i]) continue;
int l=qry[i][1],r=qry[i][2];
if(l>r) continue;
if(l/bk==r/bk&&l%bk!=0&&r%bk!=bk-1) {
for(int j=l;j<=r;++j) {
auto t=ivl[j/bk][j%bk];
ans[i]+=sumadd::sum(t.first,t.second);
}
continue;
}
while(l%bk!=0) {auto t=ivl[l/bk][l%bk];ans[i]+=sumadd::sum(t.first,t.second);l++;}
while(r%bk!=bk-1) {auto t=ivl[r/bk][r%bk];ans[i]+=sumadd::sum(t.first,t.second);r--;}
}
for(int i=1;i<=q;++i)
if(qry[i][0]==2)
cout << ans[i] << ' ';
cout << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
Delta();
}
Consider SQRT decomp for $$$[l_i,r_i]$$$, putting each $$$sqrt(n)$$$ of $$$[l_i,r_i]$$$ into a block, and maintaining the sum of the group, and the number of occurrences in the block in each original array $$$a_i$$$.
Enumerate all blocks, and if a query completely contains an sqrt, then +=sum is added to the result of the query.
If we add, then sum+= the number of times the number * added value. (This can be done with two times perfix sums)
For queries that are not complete blocks, consider direct brute force maintenance of the A-array and query, it has $$$n^{1.5}$$$ query operations and n modification operations, so we can use a partitioned data structure to do $$$O(1)$$$ queries, $$$O(n^{0.5})$$$ modifications.
So, the total complexity is $$$O(n^{1.5})$$$.
