【题目记录】——ICPC南京2021

A Oops, It's Yesterday Twice More 签到C Klee in Solitary Confinement 思维题D Paimon Sorting 思维题H Crystalfly 树上dpJ Xingqiu's Joke 记忆化搜索M Windblume Festival 思维
题目集地址 ICPC南京2021
参考博客 第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（南京） CDH
2021 46届icpc 南京

A
题目大意:略
思路:判断离哪个角近，先走到角上再走到(a,b)，分类讨论

#include 
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

void solve()
{
	int n,a,b;
	scanf("%d%d%d",&n,&a,&b);
	int x1=n/2;
	int dx=0,dy=0;
	bool mark1=true,mark2=true;
	if(a<=x1)
    {
        mark1=true;
        dx=a-1;
        for(int i=1;i 
C Klee in Solitary Confinement 思维题 
C
 题目大意:给出一个数组和数字k，你可以执行1次或者不执行下面的操作
 选择一个区间[l,r]将这个区间的所有数加上一个k
 最后问整个数组中个数最多的数字的个数最大是多少？
 思路：
 我一开始一直认为这个要用什么数据结构来做，没有往这个方向考虑。
 先预处理出每个数的个数，若k为0，直接输出最大的个数。若不为0，对于每个数，对自己x贡献-1，并且当贡献≤0时，重新置0，意味着不对前面的数+k。然后对x+k贡献+1,并更新最大值，最后输出最大值即可
 tcnt数组相当于在某个区间的数加上k后对于x的贡献量，如果贡献量为负数，说明操作此区间必然不可能是最大值，则令tcnt[x]=0，即不操作此区间。
 
#include 

using namespace std;
const int offset=2e6;
int tcnt[4000010],num[4000010],a[4000010];
int main()
{
    freopen("in.txt", "r", stdin);
    int n,k,ans=0;
    scanf("%d%d", &n, &k);
    int x;
    for(int i = 1; i<=n;i++)
    {
        scanf("%d",a+i);
        num[a[i]+offset]++;
        ans=max(ans,num[a[i]+offset]);
    }
    if(k!=0)
    {
        for(int i = 1;i <= n;i++)
        {
            x=a[i];
            tcnt[x+offset]--;
            if(tcnt[x+offset]<0)
            {
                tcnt[x+offset]=0;
            }
            tcnt[x+offset+k]++;
            ans=max(ans,tcnt[x+offset+k]+num[x+offset+k]);
        }
    }
    printf("%dn",ans);
    return 0;
}
 
D Paimon Sorting 思维题 
D
 题目大意:给出一段排序代码，给出一个长度为n的随机序列，然后对于此序列的长度为1-n的前缀使用此代码进行排序，分别需要多少次交换。
 思路:
 因为对于序列的每一个数都要询问一次，且该数后面的数对结果没有影响，故考虑插入法
 如果插入的数小于当前最大值，则直到最后一轮之前该数都不会对结果有贡献，最后一轮的贡献则为前面比它大的数的个数（去重后），这里用两个树状数组维护。
 如果相等，则始终不会产生贡献。
 如果插入的数大于当前最大值，经过手模，观察出为2+当前最大值第二次出现后的数的个数。
 
#include
#define LL long long
using namespace std;
const int N=1e5+9;
int T,n,cnt,flag,maxn;
LL ans;
int a[N],c[N],vis[N];
int lowbit(int x)
{
	return x&(-x);
}
void Add(int x)
{
	while(x<=n)
	{
		c[x]++;
		x+=lowbit(x);
	}
}
int Sum(int x)
{
	int tot=0;
	while(x)
	{
		tot+=c[x];
		x-=lowbit(x);
	}
	return tot;
}
void solve()
{
	cin>>n;
	memset(c,0,sizeof(int)*(n+9));
	memset(vis,0,sizeof(int)*(n+9));
	maxn=cnt=flag=0; ans=0;
	for(int i=1;i<=n;i++)
		cin>>a[i],maxn=max(maxn,a[i]);
	cout<a[1]:0);
		if(a[i]>a[1]) ans+=1+cnt,swap(a[1],a[i]),cnt=flag=0;
		ans+=Sum(a[1])-Sum(a[i]);
		cout<<" "<>T;
	while(T--) solve();
	return 0;
}
 
H Crystalfly 树上dp 
H
 树形dp。f[x]记录子树x得到的最优值；g[x]记录不取x的孩子，也就是走到x惊扰了x的孩子但不去取他们,
    
     
      
       
        g
       
       
        [
       
       
        x
       
       
        ]
       
       
        =
       
       
        f
       
       
        [
       
       
        
         y
        
        
         i
        
       
       
        ]
       
       
        −
       
       
        a
       
       
        [
       
       
        
         y
        
        
         i
        
       
       
        ]
       
      
      
       g[x]=f[y_i]-a[y_i]
      
     
    g[x]=f[yi​]−a[yi​]，
    
     
      
       
        
         y
        
        
         i
        
       
      
      
       y_i
      
     
    yi​是x的孩子。
 从下至上，对每个 x，首先
    
     
      
       
        f
       
       
        [
       
       
        x
       
       
        ]
       
       
        =
       
       
        m
       
       
        a
       
       
        x
       
       
        (
       
       
        f
       
       
        [
       
       
        x
       
       
        ]
       
       
        ,
       
       
        g
       
       
        [
       
       
        x
       
       
        ]
       
       
        +
       
       
        a
       
       
        [
       
       
        
         y
        
        
         i
        
       
       
        ]
       
       
        )
       
      
      
       f[x]=max(f[x],g[x]+a[y_i])
      
     
    f[x]=max(f[x],g[x]+a[yi​])，再对他的孩子讨论。
 若t[y]=3，可以先走到另一个孩子节点z去取再返回y取，这样就惊扰了z的孩子，因此，z子树的贡献就变成了
    
     
      
       
        g
       
       
        [
       
       
        z
       
       
        ]
       
      
      
       g[z]
      
     
    g[z]，
    
     
      
       
        f
       
       
        [
       
       
        x
       
       
        ]
       
       
        =
       
       
        m
       
       
        a
       
       
        x
       
       
        (
       
       
        f
       
       
        [
       
       
        x
       
       
        ]
       
       
        ,
       
       
        g
       
       
        [
       
       
        x
       
       
        ]
       
       
        +
       
       
        a
       
       
        [
       
       
        y
       
       
        ]
       
       
        +
       
       
        g
       
       
        [
       
       
        z
       
       
        ]
       
       
        −
       
       
        (
       
       
        f
       
       
        [
       
       
        z
       
       
        ]
       
       
        −
       
       
        a
       
       
        [
       
       
        z
       
       
        ]
       
       
        )
       
       
        )
       
      
      
       f[x]=max(f[x],g[x]+a[y]+g[z]−(f[z]−a[z]))
      
     
    f[x]=max(f[x],g[x]+a[y]+g[z]−(f[z]−a[z]))。因此只需要记录下
    
     
      
       
        g
       
       
        [
       
       
        y
       
       
        ]
       
       
        −
       
       
        f
       
       
        [
       
       
        y
       
       
        ]
       
       
        +
       
       
        a
       
       
        [
       
       
        y
       
       
        ]
       
       
        g
       
       
        [
       
       
        y
       
       
        ]
       
       
        −
       
       
        f
       
       
        [
       
       
        y
       
       
        ]
       
       
        +
       
       
        a
       
       
        [
       
       
        y
       
       
        ]
       
      
      
       g[y]-f[y]+a[y]g[y]−f[y]+a[y]
      
     
    g[y]−f[y]+a[y]g[y]−f[y]+a[y]的最大值和次大值就行了。
 
#include
#define LL long long
#define pb push_back
using namespace std;
const int N=1e5+9;
int T,n;
LL a[N],t[N],f[N],g[N];
vectore[N];
void dfs(int x,int fa)
{
	g[x]=a[x];
	LL maxn1=-1e16-9,maxn2=-1e16-9;
	for(auto y:e[x])
	{
		if(y==fa) continue;
		dfs(y,x);
		g[x]+=f[y]-a[y];
		LL temp=g[y]-f[y]+a[y];
		if(temp>maxn1) maxn2=maxn1,maxn1=temp;
		else if(temp>maxn2) maxn2=temp;
	}
	f[x]=g[x];
	for(auto y:e[x])
	{
		if(y==fa) continue;
		f[x]=max(f[x],g[x]+a[y]);
		if(t[y]==3)
		{
			if(g[y]-f[y]+a[y]==maxn1) f[x]=max(f[x],g[x]+a[y]+maxn2);
			else f[x]=max(f[x],g[x]+a[y]+maxn1);
		}
	}
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],f[i]=g[i]=0,e[i].clear();
	for(int i=1;i<=n;i++)
		cin>>t[i];
	for(int i=1;i>x>>y;
		e[x].pb(y); e[y].pb(x);
	}
	dfs(1,0);
	cout<>T;
	while(T--) solve();
	return 0;
}
 
J Xingqiu’s Joke 记忆化搜索 
J
 题目大意:给你两个数a，b，每次可对两个数同时进行三种操作：加1，减1或者同时除以他们的公共质因数，问使得其中任意一个数到达1的最小操作次数。
 思路:我们可以发现，a和b同时加1或者减1，他们的差值不会变，同时如果a和b的公因数必然是他们差值的因数，执行一次除法之后(a,b,b-a)->
    
     
      
       
        (
       
       
        
         a
        
        
         g
        
       
       
        ,
       
       
        
         b
        
        
         g
        
       
       
        ,
       
       
        
         
          b
         
         
          −
         
         
          a
         
        
        
         g
        
       
       
        )
       
      
      
       (frac{a}{g},frac{b}{g},frac{b-a}{g})
      
     
    (ga​,gb​,gb−a​)，我们需要在执行除法之前将a或者b通过加1减1的操作使得a或b能够被g整除，这样我们就会得到一个递推式,f(a,b-a)=min(f(a/g,(b-a)/b)+a%g+1,f(a/g+1,(b-a)/g)+a-a%g+1))
 然后我们进行dfs，我们把中途得到的状态f(x,y)都记录下来，进行搜索，也就是记忆化搜索即可。
 代码:
 
#include 
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

vectorv;
unordered_mapf; //基于hash，无序，查找快速，用map会T
//这里也可以不用hash而是数对pair
//素数筛
const int N=3e7+1;
bool IsPrime[N];//真值为素数
int Prime[N],cnt;//存储的素数从下标1开始

void ola(int n) { //筛选到n
	memset(IsPrime,1,sizeof(IsPrime));//初始化
	//假设每个数都为素数
	IsPrime[1]=IsPrime[0]=0;
	for(int i=2; i<=n; i++) {
		if(IsPrime[i])//如果这个数没筛掉，那么将其加入素数序列
		{
			Prime[++cnt]=i;
		}
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			IsPrime[i*Prime[j]]=0;
			if(!i%Prime[j])
			break;
		}
	}
}

ll H(int a,int c)//hash函数
{
	return a*1e9+c;
}

int dfs(int a,int c)
{
	if(a==1) return 0;
	if(c==1) return a-1;
	if(f[H(a,c)]) return f[H(a,c)];
	int minn=a-1;
	for(auto x:v)
		if(c%x==0)
		{
			int res=a%x;
			minn=min({minn,res+1+dfs(a/x,c/x),x-res+1+dfs(a/x+1,c/x)});
		}
	return f[H(a,c)]=minn;
}

void solve()
{
    ll a,b;
    scanf("%lld%lld",&a,&b);
    if(a>b) swap(a,b);
    int c=b-a;
    v.clear();
    for(int i=1;Prime[i]*Prime[i]<=c;i++)//这里先把a与b的差值c的所有质因数找出来
    {
        if(c%Prime[i]==0)
        {
            v.push_back(Prime[i]);
            while(c%Prime[i]==0)
            {
                c/=Prime[i];
            }
        }
    }
    if(c>1){
        v.push_back(c);
    }
    printf("%dn",dfs(a,b-a));
}

int main()
{
//	freopen("in.txt","r",stdin);
	ola(N);
	int t = 1;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
    return 0;
}
 
M Windblume Festival 思维 
M
 题目大意:n个数字排成圆环状，每次操作可以选择一个数字，让他减去他的下一个数的值，问最后剩下的数字的最大值可能是多少。
 思路：有规律如下，若有正数有负数，那就是把所有数字的绝对值加到一起
 若全为正数或者全为负数，就将所有值的绝对值加到一起在减去最小绝对值的2倍即可。
 n=1时特判一下
 
#include 
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e6+10;
ll a[maxn];

void solve()
{
	int n;
	scanf("%d",&n);
	int k[5]={0};
	ll sum=0,minx=1e18+1;
	if(n==1)
    {
        scanf("%lld",&a[0]);
        printf("%lldn",a[0]);
        return ;
    }
    for(int i=0;i0)
            k[1]=1;
    }
    if(k[0]+k[1]==2)
        printf("%lldn",sum);
    else
    {
        printf("%lldn",(sum-2*minx));
    }
}

int main()
{
//	freopen("in.txt","r",stdin);
	int t = 1;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
    return 0;
}