总结

写这种比较新的题目，尤其是里面的思维题真的好多，我们队伍里面还是太欠缺了，这方面还是要好好增强一下。从这套题目里面也看到了很多的不足，心情多少有点小失落QWQ。
这里摆上一个题解链接，后面想起来要再翻开看的时候方便一点。

C Klee in Solitary Confinement

这道题想了很长时间，都是代码写的差不多了才发现原来又原则性的错误，整得整个人都很麻，这点一定要改正，至少心里已经有谱了之后才能下手写（虽然当时觉得已经很有谱了）。这里首先提示一下，之所以$vector$数组的数量是$4e6$是因为$k$的值可以是$\pm 1e6$，而负数域的数需要映射到正数域，因此要定义这个大小的数组。否则可能会溢出。
很显然能够看出来的是只需要考虑$x$和$x+k$即可，因为其他的值不影响这个结果，将其存到一个$vector$里，$vector[i]$里面存的就相当于只有$i$和$i-k$两个数（因为$i-k+k$的结果是$i$），这样存是为了后面的$sum$数组进行准备。
设$sum[i][0]$是前$i$中$x$的个数，$sum[i][1]$ 是$x-k$ 的个数。对每个$[l,r]$贡献是：
$sum[m][0]-(sum[r][0]-sum[l-1][0])+(sum[r][1]-sum[l-1][1])$
移一下项就是：
$sum[m][0]+(sum[r][1]-sum[r][0])+(sum[l-1][0]-sum[l-1][1])$
之后就可以线性解决了。每一次记录$l-1$的最大值，加上前面的取个，然后$r$的话就是直接这样遍历一遍就行了，在这个过程中取最大值就行了。这里注意一下对于区间$[l,r]$，一定是满足$r\ge l$的。

附上代码

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxyu=4e6+9,maxm=1e6+9,basse=2e6;
int cnt,maxn;
int a[maxm],sum[maxm][2];
vector<int>v[maxyu];
int main()
{
    int n,k,ans=0;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        a[i]+=basse;
        v[a[i]].pb(a[i]);
        v[a[i]+k].pb(a[i]);//当k为零时相当于是进去了两次
        maxn=max(maxn,max((int)v[a[i]].size(),(int)v[a[i]+k].size()));
    }
    if(!k)
    {
        printf("%dn",maxn/2);//所以k为零的话这里就要除以二再输出
        return 0;
    }
    for(int i=0; i<=4e6; i++)
    {
        if(!v[i].size()) continue;
        for(int j=0; j<(int)v[i].size(); j++)
        {
            sum[j+1][0]=sum[j][0]+(v[i][j]==i);
            sum[j+1][1]=sum[j][1]+(v[i][j]!=i);
        }
        int temp=0;
        ans=max(ans,sum[v[i].size()][0]);
        for(int j=1; j<=(int)v[i].size(); j++)
        {
            temp=max(temp,sum[j-1][0]-sum[j-1][1]);
            ans=max(ans,sum[v[i].size()][0]+sum[j][1]-sum[j][0]+temp);
        }
    }
    printf("%dn",ans);
    return 0;
}

D Paimon Sorting

题目大意:给出一段排序代码，给出一个长度为n的随机序列，然后对于此序列的长度为1-n的前缀使用此代码进行排序，分别需要多少次交换。
思路:
因为对于序列的每一个数都要询问一次，且该数后面的数对结果没有影响，故考虑插入法
如果插入的数小于当前最大值，则直到最后一轮之前该数都不会对结果有贡献，最后一轮的贡献则为前面比它大的数的个数（去重后），这里用两个树状数组维护。
如果相等，则始终不会产生贡献。
如果插入的数大于当前最大值，经过手模，观察出为2+当前最大值第二次出现后的数的个数。

代码

#include<bits/stdc++.h>
#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<<ans;
	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]) ans+=1+cnt,swap(a[1],a[i]),cnt=flag=0;
		ans+=Sum(a[1])-Sum(a[i]);
		cout<<" "<<ans;
	}
	cout<<"n";
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>T;
	while(T--) solve();
	return 0;
}

H Crystalfly

这道题目对于每一个样例，给了一棵树，树上有蝴蝶，每个节点上有一定数量的蝴蝶，然后还有一个参数，这个参数是当父节点被经过之后在经过多少时间上面的蝴蝶就会飞走，然后让我们求最多能够抓取的蝴蝶个数。

树形dp。$f[x]$记录子树$x$得到的最优值；$g[x]$记录不取$x$的孩子，也就是走到$x$惊扰了$x$的孩子但不去取他们，$g[x]=f[y_i]-a[y_i]$，$y_i$是$x$的孩子。

从下至上，对每个$x$，首先$f[x]=max(f[x],g[x]+a[y_i])$ ，再对他的孩子讨论。

若$t[y]=3$，可以先走到另一个孩子节点$z$去取再返回$y$ 取，这样就惊扰了 $z$的孩子，因此，$z$子树的贡献就变成了$g[z]$，而不是之前预处理的$(f[z]-a[z])$（这里$z$就是$x$的另一个儿子节点），$f[x]=max(f[x],g[x]+a[y]+g[z]-(f[z]-a[z]))$。把括号去掉后看出只需要记录下$g[y]-f[y]+a[y]$的最大值和次大值就行了。

代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int maxn=1e5+9;
int casenum,n;
ll a[maxn],t[maxn],f[maxn],g[maxn];
struct Edge{
    int to,next;
}edge[maxn<<1];
int head[maxn],cnt;

void add_edge(int from,int to)
{
    edge[++cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt;
}

void dfs(int x,int fa)
{
    g[x]=a[x];
    ll maxn1=-1e16-9,maxn2=-1e16-9;
    int k=1,y=1;
    for(k=head[x];k;k=edge[k].next)
    {
        y=edge[k].to;
        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(k=head[x];k;k=edge[k].next)
    {
        y=edge[k].to;
        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()
{
    cnt=0;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%lld",&a[i]),f[i]=g[i],head[i]=0;
    for(int i=1; i<=n; i++)
        scanf("%lld",&t[i]);
    for(int i=1; i<n; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs(1,0);
    printf("%lldn",f[1]);
}
int main()
{
    scanf("%d",&casenum);
    while(casenum--)
        solve();
    return 0;
}

J Windblume Festival

题目大意:给你两个数a，b，每次可对两个数同时进行三种操作：加1，减1或者同时除以他们的公共质因数，问使得其中任意一个数到达1的最小操作次数。
思路:我们可以发现，a和b同时加1或者减1，他们的差值不会变，同时如果a和b的公因数必然是他们差值的因数，执行一次除法之后$(a,b,b-a)->(\frac{a}{g},\frac{b}{g},\frac{b-a}{g})$，我们需要在执行除法之前将a或者b通过加1减1的操作使得a或b能够被g整除，这样我们就会得到一个递推式,
$f(a,b-a)=min(f(a/g,(b-a)/b)+a\mathrm{m}\mathrm{o}\mathrm{d}g+1,f(a/g+1,(b-a)/g)+a-a\mathrm{m}\mathrm{o}\mathrm{d}g+1))$
然后我们进行dfs，我们把中途得到的状态f(x,y)都记录下来，进行搜索，也就是记忆化搜索即可。

代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

vector<int>v;
unordered_map<ll,int>f; //基于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;
}

最后

以上就是威武砖头为你收集整理的2021icpc南京训练总结总结C Klee in Solitary ConfinementD Paimon SortingH CrystalflyJ Windblume Festival的全部内容，希望文章能够帮你解决2021icpc南京训练总结总结C Klee in Solitary ConfinementD Paimon SortingH CrystalflyJ Windblume Festival所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。