2021南京（重温经典）

• 导语
• 涉及的知识点
• 题目
• • • C
    • D
    • J
• 参考文献

导语

打的不好，本来以为训练了这么长时间会有不少效果，但是被打的稀里哗啦，思维没有打开

涉及的知识点

思维，树状数组，记忆化搜索

链接：The 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)

题目

C

题目大意：给出一个序列 a 1 , a 2 , … a n a_1,a_2,\dots a_n a1​,a2​,…an​和一个整数$k$，现在可以对序列的任意长度的区间都加上这个$k$，但最多只能执行一次（也可以不进行这个操作），求出操作之后得到的众数的最大个数

思路：对于每一个$x$和$x-k$考虑构造，因为彼此间会产生影响，设$sum[i][0]$为前i中x的个数，$sum[i][1]$为x-k个数，那么对于一个区间$[l,r]$，那么从x-k变到x得到的贡献为$sum[r][1]-sum[l-1][1]$，这中间减少的x的贡献为$sum[r][0]-sum[l-1][0]$，那么可以得到挑选当前区间得到的总贡献：
$sum[len][0]+sum[r][1]-sum[l-1][1]-sum[r][0]+sum[l-1][0]$
移项可得
$sum[len][0]+sum[r][1]-sum[r][0]+sum[l-1][0]-sum[l-1][1]$
这样在处理r的时候也就顺带获得了l-1的数值，详见代码
代码

#include #define int long longusing namespace std;const int N=4e6+5;const int M=1e6+9;const int offset=2e6;int n,k,ans,cnt,a[M],mx,sum[M][2];vector<int>v[N];signed main() {    ios::sync_with_stdio(0);    cin.tie(0);    cin >>n>>k;    for(int i=1; i<=n; i++) { cin >>a[i]; a[i]+=offset; v[a[i]].push_back(a[i]),v[a[i]+k].push_back(a[i]); //a[i]在这个位置有一个值,a[i]+k可以在这个位置有一个值 mx=max(mx,max((int)v[a[i]].size(),(int)v[a[i]+k].size()));//记录初始的最大值    }    if(!k) { cout <<mx/2<<endl;//会重复计算，需要去重 return 0;    }    for(int i=0; i<=4e6; i++) { int len=v[i].size();//获得数量 if(len==0)continue; for(int j=0; j<len; j++) {//遍历其每一个位置     sum[j+1][0]=sum[j][0]+(v[i][j]==i);//记录前j个位置有多少个i     sum[j+1][1]=sum[j][1]+(v[i][j]!=i);//记录前j个位置有多少个i-k } int tmp=0; ans=max(ans,sum[len][0]);//获得最大值 for(int j=1; j<=len; j++) {     tmp=max(tmp,sum[j-1][0]-sum[j-1][1]);//获得公式后缀最大值     ans=max(ans,sum[len][0]+sum[j][1]-sum[j][0]+tmp);//获得公式最值 }    }    cout <<ans<<endl;    return 0;}

D

题目大意：略

思路：对于每个长度的第一轮循环之后，结果是将其严格单增序列相对后移（这里的相对后移指的是单增序列的相对位置），之后第2,3…轮排序的交换次数就是前i个比a[i]大的个数（去重）
因此为了获得最后的解，在扫描的时候可以直接在线处理，保证每次只获得当前长度下第一次循环的结果，当遇到a[i]>a[1]时，就交换a[i]和a[1]的位置，这就是一次必要的交换，计数器增加，然后对于每个在线处理录入的a[i]，统计先前比它大的个数，直接加上即可
但是，当录入的a[i]与a[1]（当前最大值）相等（假设值为x）并且后面存在比a[1]更大的数（假设值为y），那么在后面的长度当中，第一轮排序会使得当前的a[i]的值不变，而a[1]对应的值被移到了更大的数位置上，就是这样的情况：x,x,y->y,x,x，那么在插入y之后，由于y前移了，y对x也有一个需要交换的贡献，举例如下，假设当前长度构造的序列为
$x,a,a,a,x,x-1,x-2,x-1$
插入y之后，由于y大于x
$y,a,a,a,x,x-1,x-2,x-1,x$
那么对于$x,x-1,x-2,x-1$这几个数，都需要加上$y$的这个贡献，所有需要增加一个计数器，记录第二个x到y间有几个数，插入y的时候结果加上计数器值即可

代码

#include #define int long longusing namespace std;const int maxn=1e5+5;int n,a[maxn],t,tree[maxn];bool vis[maxn];int lowbit(int x) {    return x&(-x);}void Add(int x) {    for(int i=x; i<=n; i+=lowbit(i)) tree[i]++;}int Sum(int x) {    int ans=0;    for(int i=x; i; i-=lowbit(i)) ans+=tree[i];    return ans;}signed main() {    ios::sync_with_stdio(0);    cin.tie(0);    cin >>t;    while(t--) { cin >>n; int res=0,cnt=0; bool flag=0; memset(tree,0,sizeof(tree)); memset(vis,0,sizeof(vis));//初始化 for(int i=1; i<=n; i++)//录入数据     cin >>a[i]; cout <<0;//第一个结果 vis[a[1]]=1;//代表已经访问过 Add(a[1]);//加进来 for(int i=2; i<=n; i++) {     if(!vis[a[i]])vis[a[i]]=1,Add(a[i]);//未访问插入     if(a[i]==a[1])flag=1;//标记存在多个最值     cnt+=flag-(flag?a[i]>a[1]:0);//未统计的贡献     if(a[i]>a[1])res+=1+cnt,swap(a[1],a[i]),cnt=flag=0;     //a[1]永远只存最大的数字     res+=Sum(a[1])-Sum(a[i]);//在i之前出现的比a[i]大的数字个数     cout <<" "<<res; } cout <<endl;    }    return 0;}

J

题目大意：给出两个正整数a,b，每次可以进行三种操作：都+1，都-1，都除以一个它们共同的质数因子，判断最少多少次能使得其中一个数为1

思路：如果不进行除法操作，那么ab差值是固定的，如果存在一个数能够整除a和b，那么一定也能整除它们的差值，那么就可以将其差值进行质因子分解，将ab中的较小数加/减到距离质因子最小的数，对a,b及差值同时除质因子，以此反复即可，当无质因子时只能一直减了

代码

#include #define int long longusing namespace std;const int maxn=1e5+5;int n,a,b,t;vector<int>v;unordered_map<int,int>level;int gethash(int b,int c) {//哈希    return b*1e9+c;}int DFS(int b,int c) {    if(b==1)return 0;    if(c==1)return b-1;//差值为1，只能一直减    if(level[gethash(b,c)])return level[gethash(b,c)];//记忆化搜索    int mn=b-1;//至少需要的次数    for(auto i:v)//遍历所有的质因子 if(c%i==0) {//如果还没有除过     int ans=b%i;//获得差距     mn=min({mn,ans+1+DFS(b/i,c/i),i-ans+1+DFS(b/i+1,c/i)});     //分别是b大于i的情况和b小于i的情况，+1是因为进行了一次除 }    return level[gethash(b,c)]=mn;}signed main() {    ios::sync_with_stdio(0);    cin.tie(0);    cin >>t;    while(t--) { cin >>a>>b; if(a<b)swap(a,b);//强制b为小值 int c=a-b; v.clear(); for(int i=2; i<=c/i; i++)     if(c%i==0) {//获得质因子  v.push_back(i);  while(c%i==0)c/=i;     } if(c>1)v.push_back(c);//最后除剩的也是质因子 cout <<DFS(b,a-b)<<endl;//记忆化搜索    }    return 0;}

参考文献

1. 2021 46届icpc 南京
2. 【题目记录】——ICPC南京2021

养殖设备