The 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)
A.Oops, It’s Yesterday Twice More
思路：考虑先把所有袋鼠集中在一起然后再移动。因为有步数限制(\(\le3(n-1)\))。那么分类讨论移动到四个角上，看哪个符号条件的就输出。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,a,b;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>a>>b;
//LU
int x = 1,y = 1;
if((a-x)+(b-y)<=(n-1))
{
for(int i = 1;i <= n-1;i++)cout<<"L";
for(int i = 1;i <= n-1;i++)cout<<"U";
for(int i = 1;i <= b-y;i++)cout<<"R";
for(int i = 1;i <= a-x;i++)cout<<"D";
return 0;
}
//RU
x = 1,y = n;
if((a-x)+(y-b)<=(n-1))
{
for(int i = 1;i <= n-1;i++)cout<<"R";
for(int i = 1;i <= n-1;i++)cout<<"U";
for(int i = 1;i <= y-b;i++)cout<<"L";
for(int i = 1;i <= a-x;i++)cout<<"D";
return 0;
}
//LD
x = n,y = 1;
if((x-a)+(b-y)<=(n-1))
{
for(int i = 1;i <= n-1;i++)cout<<"L";
for(int i = 1;i <= n-1;i++)cout<<"D";
for(int i = 1;i <= b-y;i++)cout<<"R";
for(int i = 1;i <= x-a;i++)cout<<"U";
return 0;
}
//RD
x = n,y = n;
if((x-a)+(y-b)<=(n-1))
{
for(int i = 1;i <= n-1;i++)cout<<"R";
for(int i = 1;i <= n-1;i++)cout<<"D";
for(int i = 1;i <= y-b;i++)cout<<"L";
for(int i = 1;i <= x-a;i++)cout<<"U";
return 0;
}
return 0;
}
C. Klee in Solitary Confinement
思路：
做法一：(公式推导)我们考虑枚举众数是谁，然后去写。对于众数是\(x+k\)的情况，只有\(x\)对它有贡献。那么考虑对于一段区间\([L,R]+k\),我们对于众数是\(x\)情况的贡献是什么呢？
如上图所示：
为了更快的处理区间问题，我们先预处理出对于某个数\(x+k\)的前缀出现次数\(pre2\)，和\(x\)的前缀出现次数\(pre1\)
那么对于\([L,R]+k\)，对于众数是\(x+k\)的贡献是\(pre2[L-1]+pre2[n]-pre[R]+pre1[R]-pre1[L-1]\)
移向得：\(pre2[n]+(pre1[R]-pre1[L-1])-(pre2[R]-pre2[L-1])\)
因为\(pre2[n]\)是定值，那么我们只需要后面这个东西最大就行了。我们固定左界去枚举右界，取max就是答案。
还有一个问题，如何处理出这个东西？
我们先用\(vector<int>idx[N]\)存下每种值的下标，然后呢，对于众数是\(x+k\)的情况，只有\(x\)是对它有贡献的。我们把\(idx[x]\)和\(idx[x+k]\)取出来，根据下标，把它们排成一排，假设这两组数总共是有\(c\)个，那\(for(1～c)\)对两组数做前缀操作。做完以后还是\(for(1～c)\)去求\(pre2[n]+(pre1[R]-pre1[L-1])-(pre2[R]-pre2[L-1])\)的最大值。
对于时间复杂度：因为每个数\(x\)至多被访问\(2\)次(\(x+k\)和\(x-k\))，那么时间复杂度\(O(2n)\).
注意：下标有负数，我们做个偏移。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 4e6 + 10,M = 2e6;
vector<int>idx[N];
int pos[N];
int cnt[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n,k;
cin>>n>>k;
ll maxn = -1e9;
ll res = -1e18;
for(int i = 1;i <= n; i++)
{
ll x;
cin>>x;
x += M;
cnt[x]++;
if(cnt[x]>res)res = cnt[x];
maxn = max(maxn,x);
idx[x].push_back(i);
}
//cout<<"mx = "<<maxn<<"\n";
for(int i = 0;i <= 4e6; i++)
{
int c = 0;
int x = i,y = i+k;
if(y<0||y>4e6)continue;
int sz1 = idx[x].size(),sz2 = idx[y].size();
if(y<0||y>4e6||sz1==0||sz2==0)continue;
//cout<<"x = "<<x-M<<" y = "<<y-M<<"\n";
int cnt1 = 0,cnt2 = 0;
while(cnt1 < sz1|| cnt2 < sz2)
{
if(cnt1 == sz1)
pos[idx[y][cnt2]] = ++c,cnt2++;
else if(cnt2 == sz2)
pos[idx[x][cnt1]] = ++c,cnt1++;
else{
if(idx[x][cnt1] < idx[y][cnt2])
pos[idx[x][cnt1]] = ++c,cnt1++;
else pos[idx[y][cnt2]] = ++c,cnt2++;
}
}
// cout<<"pos1 :";
// for(int i = 0;i<sz1;i++)
// cout<<pos[idx[x][i]]<<" ";
// cout<<"\n";
// cout<<"pos2 :";
// for(int i = 0;i<sz2;i++)
// cout<<pos[idx[y][i]]<<" ";
// cout<<"\n";
vector<ll>pre1(c+1),pre2(c+1);
for(auto j:idx[x])
pre1[pos[j]]++;
for(auto j:idx[y])
pre2[pos[j]]++;
for(int i = 1; i <= c; i++)
pre1[i] += pre1[i-1],pre2[i] += pre2[i-1];
// for(int i = 1;i <= c;i++)
// cout<<pre1[i]<<" ";
// cout<<"\n";
// for(int i = 1;i <= c;i++)
// cout<<pre2[i]<<" ";
// cout<<"\n";
ll t = 0;
for(int i = 1;i <= c; i++)
{
t += (pre1[i]-pre1[i-1])-(pre2[i]-pre2[i-1]);
if(t<0)t = 0;
res = max(res,t + pre2[c]);
}
}
cout<<res<<"\n";
return 0;
}
做法二：
考虑一个区间\(+k\)带来的影响：
对于一个区间原本的数是\(x\)，现在变成了\(x+k\)，原本是\(x-k\)的数现在变成了\(x\)。
如果选择\(x\)是众数，那么对于这个所选区间内\(x\)的贡献是\(-1\),\(x-k\)的贡献是\(+1\)。那么对于给定\(x\)，我们只需要找出最大贡献区间即可。但是如果枚举每个\(a_i\)然后再去扫一遍看贡献肯定超时了，那怎么办呢？当我们枚举到第\(i\)个位置的时候，我们统计\(a_i\)和\(a_i+k\)产生的贡献，也就是说，我们\(for\)一遍相当于枚举了全部的\(a_i\)。
那么如何选区间呢？从开始一直去取，直到某个位置贡献小于0了，那就不要这段了，因为从这段负的继续加不会更优。所以我们把这段区间丢掉，从新开始计算贡献。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 4e6 + 10,M = 2e6;
vector<int>idx[N];
int ret[N],a[N],pre[N],cnt[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n,k;
cin>>n>>k;
int ans = 0;
for(int i = 1;i <= n; i++)
{
cin>>a[i];
cnt[a[i]+M]++;
ans = max(ans,cnt[a[i]+M]);
}
if(k==0){
cout<<ans<<"\n";
return 0;
}
for(int i = 1;i <= n; i++)
{
ret[a[i]+M]--;
if(ret[a[i]+M]<0)ret[a[i]+M] = 0;
ret[a[i]+k+M]++;
ans = max(ans,cnt[a[i]+k+M]+ret[a[i]+k+M]);
}
cout<<ans<<"\n";
return 0;
}
思想：边扫边统计答案，无需先确定区间再去算。
J. Xingqiu's Joke
思路：对于同时\(+1\)和同时\(-1\)的操作，两数的差值的不变的。\(c = abs(a-b)\)。
若\(g|a\)且\(g|c\)那么\(g|abs(a-b)\)。
\(dp[\lbrace a,a+\delta\rbrace]\)表示从\((a,a+\delta)\)得到\(1\)的步数。我们去枚举\(\delta\)的质因数\(g\)。
而\(dp[\lbrace a,a+\delta\rbrace]\)可以由\(dp[\lbrace \lfloor \dfrac{a}{g}\rfloor,\dfrac{\delta}{g}\rbrace]\)和\(dp[\lbrace \lceil \dfrac{a}{g}\rceil,\dfrac{\delta}{g}\rbrace]\)转移得到。我们去记忆化一下就可以写了。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ll int
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
vector<ll>d;
void div(ll x)
{
for (ll i = 2; i <= x / i; i++)
{
if (x % i == 0)
{
int s = 0;
while (x % i == 0)
{
x = x / i;
s++;
}
d.push_back(i);
}
}
if (x > 1)d.push_back(x);
}
map<pair<ll,ll>,ll>dp;
ll dfs(ll a,ll c)
{
if(a==1)return 0;
if(c==1)return a-1;
ll &res = dp[{a,c}];
if(res)return res;
res = a-1;
for(auto g : d)
{
if(c % g == 0)
{
int left = a%g;
ll t1 = left+1+dfs(a/g,c/g);
ll t2 = (g-left)+1+dfs(a/g+1,c/g);
res = min({res,t1,t2});
}
}
return res;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
ll a,b;
cin>>a>>b;
d.clear();
dp.clear();
if(a>b)swap(a,b);
ll c = abs(a-b);
div(c);
// for(auto g : d)
// cout<<g<<" ";
// cout<<"\n";
cout<<dfs(a,c)<<"\n";
}
return 0;
}
M. Windblume Festival
思路：分类讨论。
- 有正有负。用负数一直减正数。最后用正数减负数这样最优。结果是\(\sum_{i = 1}^{n}a_i\)
- 全正。先变出一个负数之后，变成第一种情况。
- 全负。先变出一个正数之后，变成第一种情况。
因为\(2,3\)不知道变哪个，需要\(for\)一遍。
注意：特判\(n=1\)的情况。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
ll a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int cntn = 0,cntp = 0;
ll sum = 0;
for(int i = 0;i < n; i++)
{
cin>>a[i];
sum += abs(a[i]);
if(a[i]<0)cntn++;
else if(a[i]>0)cntp++;
}
if(n==1)
{
cout<<a[0]<<"\n";
continue;
}
ll ans = -1e18;
if(cntn>0&&cntp>0)
{
ans = sum;
}
else if(cntn)
{
for(int i = 0;i < n; i++)
{
if(a[i]-a[(i+1)%n]>=0)
ans = max(ans,(a[i]-a[(i+1)%n])+sum+a[i]+a[(i+1)%n]);
}
}
else if(cntp)
{
for(int i = 0;i < n; i++)
{
if(a[i]-a[(i+1)%n]<=0)
ans = max(ans,sum-(a[i]-a[(i+1)%n])-a[i]-a[(i+1)%n]);
}
}
else ans = 0;
cout<<ans<<"\n";
}
return 0;
}