#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.
/**
* @the_hyp0cr1t3
* 30.07.2023 20:42
**/
#include <bits/stdc++.h>
template <int P> struct modint {
static int mod_;
int v;
constexpr modint() : v{} {}
constexpr modint(long long u) {
if (u < 0) u = u % get_mod() + get_mod();
if (u >= get_mod()) u %= get_mod();
v = u;
}
constexpr int val() const { return v; }
constexpr static int get_mod() {
if constexpr (P > 0)
return P;
else
return mod_;
}
constexpr static void set_mod(int m) {
mod_ = m;
}
explicit constexpr operator int() const { return v; }
friend constexpr std::istream& operator>>(std::istream& in, modint& m) {
long long u; in >> u;
m = modint(u);
return in;
}
friend constexpr std::ostream& operator<<(std::ostream& os, const modint& m) {
return os << m.v;
}
static int inv(int a, int m) {
int g = m, x = 0, y = 1;
while (a != 0) {
int q = g / a;
g %= a;
std::swap(g, a);
x -= q * y;
std::swap(x, y);
}
return x < 0 ? x + m : x;
}
constexpr static unsigned fast_mod(uint64_t x, unsigned m = get_mod()) {
#if !defined(_WIN32) || defined(_WIN64)
return unsigned(x % m);
#endif // x must be less than 2^32 * m
unsigned x_high = unsigned(x >> 32), x_low = unsigned(x), quot, rem;
asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
return rem;
}
constexpr modint inv() const { return modint(inv(v, get_mod())); }
constexpr modint operator-() const { return modint(v ? get_mod() - v : 0); }
constexpr modint& operator+=(const modint& o) {
v += o.v;
if (v >= get_mod()) v -= get_mod();
return *this;
}
constexpr modint& operator-=(const modint& o) {
v -= o.v;
if (v < 0) v += get_mod();
return *this;
}
constexpr modint& operator*=(const modint& o) {
v = fast_mod(uint64_t(v) * o.v);
return *this;
}
constexpr modint& operator/=(const modint& o) { return *this *= o.inv(); }
friend constexpr modint operator+(const modint& a, const modint& b) {
modint res = a; res += b;
return res;
}
friend constexpr modint operator-(const modint& a, const modint& b) {
modint res = a;
res -= b;
return res;
}
friend constexpr modint operator*(const modint& a, const modint& b) {
modint res = a;
res *= b;
return res;
}
friend constexpr modint operator/(const modint& a, const modint& b) {
modint res = a;
res /= b;
return res;
}
friend constexpr bool operator==(const modint& a, const modint& b) {
return a.val() == b.val();
}
};
template <typename T>
constexpr T expo(T A, long long B) {
T res{1};
while (B) {
if (B & 1) res *= A;
B >>= 1;
A *= A;
}
return res;
}
template <>
int modint<0>::mod_ = 1;
constexpr int mod = 1'000'000'007;
using Z = modint<mod>;
// using Z = double;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int tests;
std::cin >> tests;
while (tests--) {
int n;
std::array<Z, 3> p;
std::cin >> n;
int pmx = -1;
for (int k : {2, 1, 0}) {
std::cin >> p[k];
pmx = std::max(pmx, p[k].val());
p[k] /= 100;
}
if (pmx == 100) {
std::cout << (n == 1 ? 0 : -1) << '\n';
continue;
}
--n;
auto P = p;
std::array<Z, 2> ans{};
std::array<std::vector<std::array<Z, 2>>, 3> dp;
for (int k : {0, 1, 2}) {
dp[k].reserve(n + 1);
dp[k].push_back({0, p[k]});
}
for (int i = 1; i <= n; i++) {
ans = {};
for (int k : {0, 1, 2}) {
for (int j = 0; j < i; j++) {
Z mul = p[(k + 1) % 3] * (i + 1) / (i - j);
for (int t : {0, 1}) {
dp[k][j][t] *= mul;
ans[t] += dp[k][j][t];
}
}
}
ans = {(1 + ans[0]) / ans[1], 1};
for (int k : {0, 1, 2}) {
P[k] *= p[k];
dp[k].push_back({});
for (int t : {0, 1})
dp[k][i][t] = ans[t] * P[k];
}
}
std::cout << ans[0] << '\n';
}
}
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=63;
const ll TMD=0;
const ll INF=2147483647;
int T;
ll n,k,ans;
int dif[N];
ll f[LOGN][LOGN][2];
vector<int> v;
void init()
{
f[0][0][0]=f[1][0][0]=f[1][0][1]=1;
for(int i=2;i<LOGN;i++)
{
for(int j=0;j<i;j++)
{
for(int k=0;k<=1;k++)
{
f[i][j][k]=f[i-1][j][k];
if(j) f[i][j][k]+=f[i-1][j-1][k^1];
}
}
}
}
void DP(int bt)
{
if(bt<0)
{
ans+=(dif[0]==k);
return ;
}
if(v[bt])
{
if(bt==(int)v.size()-1)
{
for(int i=bt;i;i--) ans+=f[i][k][1];
}
else
{
int diff=dif[bt+1]+v[bt+1];
if(k-diff>=0) ans+=f[bt][k-diff][0];
if(k-diff-1>=0) ans+=f[bt][k-diff-1][1];
}
}
DP(bt-1);
}
int main()
{
//freopen("test.in","r",stdin);
init();
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d",&n,&k);
v.clear();
while(n) v.push_back(n&1),n>>=1;
dif[(int)v.size()-1]=0;
for(int i=(int)v.size()-2;i>=0;i--) dif[i]=dif[i+1]+(v[i]^v[i+1]);
ans=0;
DP((int)v.size()-1);
printf("%I64d\n",ans%1000000007);
}
//fclose(stdin);
return 0;
}
DP: dp[d][s][b][0/1] is the number of ways to fix the first d bits of the number x bits so that we already have s pairs of adjacent non-equal bits, the d-th bit from the left is b, and the entire number is already smaller than n (when the last parameter is 0) or yet equal to n in the first d bits (when the last parameter is 1).
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) let's call this Siala
X <= n As a result, there is a bit like j which: 1. Every bit k > j in x is equal to n. 2. The jth bit of n should be 1 and x should be 0. As if for the conditional condition x < n, the previous j bits have no effect. We fix c and count the number of x's: The suffix [j,61] in x is specified uniquely, thus the number of adjacent pairs of bits [1,j] is uniquely specified. Suppose the bits [1,j] They must have up to k2 distinct pairs. The JM bit is also 0. As a result, X bits are in the form: 0000,11111,00000..0,111..1, ... are defined as the number of consecutive bases equal to one. K2+1 should be. Masila was converted into a Siala average: a1+a2+…+a(k2+1) = j, a(i) >= 1 The number of solutions to the above equation is equal to: C(k2, j — 1) Finally, if f(n)=k, we increase the answer by one.
#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=1010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n,tt,ans;
int t[N],s[N],dt[N],ds[N];
int dp[N][N];
int main()
{
//freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&tt);
for(int i=1;i<=n;i++) scanf("%d%d%d%d",&t[i],&s[i],&dt[i],&ds[i]);
ans=0;
for(int i=1;i<=tt;i++)
{
vector<pair<int,int> > v;
for(int j=1;j<=n;j++)
{
if(i+dt[j]>tt) v.push_back(make_pair(s[j],j));
else v.push_back(make_pair(ds[j],j));
}
sort(v.begin(),v.end());
for(int j=1;j<=n;j++)
for(int k=0;k<=i;k++)
dp[i][j]=-INF;
dp[0][0]=0;
for(int j=1;j<=n;j++)
{
int num=v[j-1].second;
if(i-t[num]>=0) ans=max(ans,dp[j-1][i-t[num]]+s[num]-v[j-1].first);
for(int k=0;k<=i;k++)
{
dp[j][k]=dp[j-1][k];
if(k-t[num]>=0) dp[j][k]=max(dp[j][k],dp[j-1][k-t[num]]+s[num]);
}
}
}
printf("%d\n",ans);
}
//fclose(stdin);
return 0;
}
Consider:for a fixed problem set you choose,which problem will the hacker hack?
For problem $$$i$$$,$$$f_i \leq T-Σt$$$,hack it will decrease you score by $$$p_i$$$.
However,for problem $$$i$$$,$$$f_i >T-Σt$$$,hack it will decrease you score by $$$a_i$$$,since you don't have enough time to fix the bug.
Note $$$decrease_i$$$ as the score that actually decreased for the i-th hacked problem.Hacker'll hack the problem with the max $$$decrease$$$ value.
We find $$$decrease$$$ is depend on the value of $$$Σt$$$.
Enumeration $$$Σt$$$ from $$$0$$$ to $$$T$$$,calculate the corresponding $$$true_decrease$$$,then do classic knapsack DP.It's $$$O(n^2T)$$$.
#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,ls,lt;
ll ans;
int x[N],a[N],S[N],s[N],t[N],nxt[N];
vector<int> p;
//
void build_nxt(int s[],int l)
{
for(int i=1;i<l;i++)
{
int j=i;
while(s[nxt[j-1]]!=s[i]&&j!=0) j=nxt[j-1];
nxt[i]=(s[i]==s[nxt[j-1]])?nxt[j-1]+1:0;
}
//for(int i=0;i<l;i++) printf("%d ",nxt[i]);
//printf("\n");
}
void KMP(int s[],int t[],int ls,int lt,vector<int> &v)
{
build_nxt(t,lt);
int ps=0,pt=0;
while(1)
{
if(pt>=lt)
{
v.push_back(ps-lt);
pt=nxt[pt-1];
}
if(ps==ls) break;
while(s[ps]!=t[pt])
{
if(!pt) break;
else pt=nxt[pt-1];
}
if(s[ps]==t[pt]) ps++,pt++;
else ps++,pt=0;
}
}
//
//
ll md(ll a,ll b) //a mod b
{
if(a>0) return a%b;
return (-(-a)%b+b)%b;
}
void exgcd(ll &x,ll &y,ll a,ll b){
if(!b){
x=1;y=0;
return ;
}
exgcd(x,y,b,a%b);
ll xx=x,yy=y;
x=yy;y=xx-(a/b)*yy;
}
ll solve_equation(ll a,ll b,ll k) //solve ax=b(mod k),x>=0 and x is minimal
{
ll x,y,g;
md(a,k);md(b,k);
exgcd(x,y,a,k); //ax+ky=gcd(a,k)
g=a*x+k*y;
if(b%g) return -1;
return md(x*(b/g),k/g);
}
int check()
{
for(int i=1;i<=n;i++) if(x[i]%k) return 0;
return 1;
}
//
int main()
{
//freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
if(check())
{
printf("0\n");
continue;
}
for(int i=1;i<=n;i++) S[i]=(S[i-1]+a[i])%k;
ls=2*n-1;lt=n-1;
for(int i=1;i<n;i++) s[i-1]=a[i+1]%k;
for(int i=n;i<2*n;i++) s[i-1]=a[i-n+1]%k;
for(int i=1;i<n;i++) t[i-1]=md(a[i]+x[i]-x[i+1],k);
p.clear();
KMP(s,t,ls,lt,p);
ans=INF*INF;
for(int i=0;i<p.size();i++)
{
ll y=x[1]+S[1+p[i]],sol=solve_equation(S[n],-y,k);
if(sol==-1) continue;
ans=min(ans,sol*n+p[i]+1);
}
if(ans==INF*INF) printf("-1\n");
else printf("%I64d\n",ans);
}
//fclose(stdin);
return 0;
}
Let's say t = n*m+p (for 0<=p<n).
S is sum of all a[i].
Note pref[i] is prefix sums of a[i](two times).
Then we want x[i] + S*m + pref[i+p] — pref[i] =0 (mod K).
Can we not enumerate m?Yes!
We notice for all i,j,x[i] + pref[i+p] — pref[i] = x[j] + pref[j+p] — pref[j] = -S*m (mod k).
We only need to consider i,i+1,and convert the equation into:(x[i] — pref[i]) — (x[i+1] — pref[i+1]) = -pref[i+p] + pref[i+p+1].
Construct L[i]=(x[i] — pref[i]) — (x[i+1] — pref[i+1]),R[i]=-pref[i] + pref[i+1].
Do KMP for L,R,we can get p.
Then use exgcd to get m.After that,we get t=n*m+p.
