A - Oops, It's Yesterday Twice More

题意

有一个 $n\times n\ \ (2\leq n\leq 500)$ 网格,每个网格上有一只袋鼠.求一组移动操作使得它们都移动到给定的点 $(a,b)\ \ (1\leq a,b\leq n)$ 处,要求移动次数不超过 $3(n-1)$ .

操作用'U'、'D'、'L'、'R'分别表示全体袋鼠向上、向下、向左、向右移动一格,下一步移动会越界的袋鼠不动.

思路

显然只有所有袋鼠都移动到一个角落处才能统一行为.考察点 $(a,b)$ 离哪个角落更近(Manhattan距离,即移动的步数最少,若步数相等随便选一个),先将所有袋鼠移动到角落,再从该角落移动到点 $(a,b)$ .将所有袋鼠移动到一个角落所需的最小步数等于该角落对角的袋鼠移动到该角落的步数,即 $(n-1)+(n-1)=2n-2$ 步.将所有袋鼠从一个角落移动到点 $(a,b)$ 所需步数为 $(a-1)+(b-1)=a+b-2\leq 2n-2$ .似乎加起来 $(4n-4)$ 步,超过了最大步数.但是 $(a,b)=(n,n)$ 时,点 $(a,b)$ 离得最近的角落即点 $(n,n)$ ,则只需前 $(2n-2)$ 步即可完成.最坏的情况是 $n$ 为奇数时的网格的中心点 $\left(\dfrac{n+1}{2},\dfrac{n+1}{2}\right)$ ,此时它离各个角落一样远,不妨设都移动到 $(1,1)$ ,则总步数 $(2n-2)+\left(\dfrac{n+1}{2}-1\right)+\left(\dfrac{n+1}{2}-1\right)=3(n-1)$ ,满足要求.

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,a,b;
    cin>>n>>a>>b;
    int d1=abs(a-1)+abs(b-1);
    int d2 = abs(a - 1) + abs(b - n);
    int d3 = abs(a - n) + abs(b - 1);
    int d4 = abs(a - n) + abs(b - n);
    int mn=min({d1,d2,d3,d4});
    if(mn==d1){
        for(int i=1;i<n;i++)cout<<"LU";
        for(int i=1;i<a;i++)cout<<"D";
        for(int i=1;i<b;i++)cout<<"R";
        cout<<"\n";
        return 0;
    }
    else if(mn==d3){
        for (int i = 1; i < n; i++)
            cout << "DL";
        for (int i = 1; i < b; i++)
            cout << "R";
        for (int i = n; i > a; i--)
            cout << "U";
        cout << "\n";
        return 0;
    }
    else if(mn==d2){
        for (int i = 1; i < n; i++)
            cout << "RU";
        for (int i = n; i >b; i--)
            cout << "L";
        for (int i = 1; i < a; i++)
            cout << "D";
        cout << "\n";
        return 0;
    }
    else if(mn==d4){
        for (int i = 1; i < n; i++)
            cout << "RD";
        for (int i = n; i >b; i--)
            cout << "L";
        for (int i = n; i > a; i--)
            cout << "U";
        return 0;
    }
    return 0;
}

M - Windblume Festival

题意

有 $T$ 组测试数据.每组测试数据有 $n\ \ (1\leq n\leq 1\mathrm{e}6)$ 个数 $a_i\ \ (-1\mathrm{e}9\leq a_i\leq 1\mathrm{e}9,1\leq i\leq n)$ 围成一圈,其中第 $x\ \ (1\leq x\leq n)$ 个数与第 $(x\ \mathrm{mod}\ n) +1$ 个数相邻.现进行若干次操作直至只剩下一个数:设当前还剩下 $k\ \ (2\leq k\leq n)$ 个数,每次操作取定一个 $x\ \ (1\leq x\leq k)$ ,将令 $a_i\leftarrow a_i-a_{(i\ \mathrm{mod}\ k)+1}$ 后删去 $a_{(i\ \mathrm{mod}\ k)+1}$ ,删去后 $a_i$ 与 $a_{(i\ \mathrm{mod}\ k)+1}$ 的下一个相邻.求最后剩下的数的最大值.数据保证所有测试数据的 $n$ 之和不超过 $1\mathrm{e}6$ .

特别注意特判 $n=1$ 的情况

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int a[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        bool flag_n=1,flag_p=1;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]>0) flag_n=0;
            if(a[i]<0) flag_p=0;
        }
        if(n==1){
            cout<<a[1]<<'\n';
            continue;
        }
        sort(a+1,a+n+1);
        int ans=0;
        if(flag_n){
            for(int i=1;i<n;i++) ans+=abs(a[i]);
            ans+=a[n]; 
        }
        else if(flag_p){
            for(int i=2;i<=n;i++) ans+=a[i];
            ans-=a[1]; 
        }
        else{
            for(int i=1;i<=n;i++) ans+=abs(a[i]);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

C - Klee in Solitary Confinement

题意

给定一个长度为 $n\ \ (1\leq n\leq 1\mathrm{e}6)$ 的序列 $a_i\ \ (-1\mathrm{e}6\leq a_i\leq 1\mathrm{e}6,1\leq i\leq n)$ 和一个操作数 $k\ \ (-1\mathrm{e}6\leq k\leq 1\mathrm{e}6)$ .可至多进行一次操作:选定一个区间 $[l,r]\ \ (1\leq l\leq r\leq n)$ ,将其中的数 $+=k$ .求最后序列中的众数的出现次数.

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,offset=2e6;
unordered_set<int> cand;
int freq[N<<2];
vector<vector<int>> mp(N<<2);
int max_subarray_sum(const vector<int>& arr){
    int n=arr.size();
    int res=arr[0];
    int dp0=arr[0],dp1;
    for(int i=1;i<n;i++){
        dp1=max(dp0+arr[i],arr[i]);
        dp0=dp1;
        res=max(res,dp1);
    }
    return max(0,res);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    int ans=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        mp[x+offset].push_back(i);
        cand.insert(x);//插入候选集合
        freq[x+offset]++;
        ans=max(ans,freq[x+offset]);
    }
    if(k==0) cout<<ans<<'\n';
    else{
        for(int x:cand){
            vector<int> delta;
            vector<int>& v1=mp[x+offset];
            vector<int>& v2=mp[x-k+offset];
            //类似归并排序
            int n1=v1.size(),m1=v2.size();
            if(n1==0||m1==0) ans=max(ans,freq[x+offset]);
            else{
                int i=0,j=0;
                while(i<n1&&j<m1){
                    while(i<n1&&j<m1&&v1[i]<v2[j]){
                        delta.push_back(-1);
                        i++;
                    }
                    while(i<n1&&j<m1&&v1[i]>v2[j]){
                        delta.push_back(1);
                        j++;
                    }
                }
                while(i<n1){
                    delta.push_back(-1);
                    i++;
                }
                while(j<m1){
                    delta.push_back(1);
                    j++;
                }
                ans=max(ans,freq[x+offset]+max_subarray_sum(delta));
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

J - Xingqiu's Joke

题意

有 $T\ \ (1\leq T\leq 300)$ 组测试数据,每组测试数据输入两相异整数 $a,b\ \ (1\leq a,b\leq 1\mathrm{e}9)$ ,每次进行如下三种操作之一,直至 $a,b$ 中至少有一个为 $1$ ,输出最少操作次数.操作:①两数同时 $+1$ ;②两数同时 $-1$ ;③两数同除以它们的一个公共素因子.

思路

在变化中寻找不变量,同时 $+1$ 和 $-1$ 让人联想到年龄的增长,注意到年龄差不变,可以发现加减过程中 $c=abs(a-b)$ 不变,则每一组 $(a,b)$ 的公共素因子也是 $c$ 的素因子.可想到对 $c$ 素因数分解,枚举 $c$ 的所有素因子 $d$ ,进行状态 $(a,b,c)$ 到状态 $\left(\dfrac{a}{d},\dfrac{b}{d},\dfrac{c}{d}\right)$ 的转移.显然状态的前两维可只保留一个,不妨设 $a<b$ ,则只需保留 $(a,c)$ ,因为最坏的情况要做 $(\min\{a,b\}-1)$ 次 $-1$ ,从状态 $(a,c)$ 开始记搜.

考虑如何记录状态,最直接的想法是用一个map<pair<int,int>,int>来记数,担心超时可以用哈希表,用一个哈希函数来将每组 $(a,c)$ 映射为一个特征值,如 $hash(a,c)=a*1\mathrm{e}9+c$ .

考察 $dfs(a,c)$ 的状态数.显然第二维的状态数即 $c$ 的因子个数,由熟知结论:int范围内因数最多的数有 $1600$ 个因子.考察第一维的状态数,即 $\dfrac{a}{d}$ 上下取整共会产生多少个数.注意到int范围内的数至多有 $30$ 个素因子(即 $30$ 个 $2$ ),此时 $\dfrac{a}{d}$ 上取整或下取整分别产生的数的个数约 $\log_2 a$ 个,约 $30$ 个,总共加起来约 $60$ 个.考察 $a$ 除以 $d_i$ 的顺序不同会不会导致结果数不同,猜测不会,理由在补充部分说明,此处先用约 $60\times 1600\times 300=2.88\mathrm{e}7$ 的时间复杂度玄学过题.

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> pfactor;
struct hash_pair{
    template<class T1,class T2>
    size_t operator()(const pair<T1,T2>& p)const{
        return hash<T1>()(p.first)^hash<T2>()(p.second);
    }
};
void divide(int x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            while(x%i==0) x/=i;
            pfactor.push_back(i);
        }
    }
    if(x>1) pfactor.push_back(x);
}
unordered_map<pair<int,int>,int,hash_pair> dp;
int dfs(int a,int c){
    if(a==1) return 0;
    if(c==1) return a-1;
    if(dp[make_pair(a,c)]) return dp[make_pair(a,c)];
    int res=a-1;
    for(int prime:pfactor){
        if(c%prime==0){
            int rest=a%prime;
            int tmp1=rest+1+dfs(a/prime,c/prime);
            int tmp2=prime-rest+1+dfs(a/prime+1,c/prime);
            res=min({tmp1,tmp2,res});
        }
    }
    return dp[make_pair(a,c)]=res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        pfactor.clear();
        dp.clear();
        divide(abs(a-b));
        cout<<dfs(min(a,b),abs(a-b))<<'\n';
    }
    return 0;
}

2021 ICPC 亚洲区域赛南京站

2021 ICPC 亚洲区域赛南京站

A - Oops, It's Yesterday Twice More

题意

思路

M - Windblume Festival

题意

C - Klee in Solitary Confinement

题意

J - Xingqiu's Joke

题意

思路

参考题解

推荐阅读更多精彩内容