1. 首页
  2. 文章中心
  3. c++

2021icpc南京训练总结总结C Klee in Solitary ConfinementD Paimon SortingH CrystalflyJ Windblume Festival

130 阅读 0 评论
我是靠谱客的博主 威武砖头，这篇文章主要介绍2021icpc南京训练总结总结C Klee in Solitary ConfinementD Paimon SortingH CrystalflyJ Windblume Festival，现在分享给大家，希望可以做个参考。

2021icpc南京训练

  • 总结
  • C Klee in Solitary Confinement
    • 附上代码
  • D Paimon Sorting
    • 代码
  • H Crystalfly
    • 代码
  • J Windblume Festival
    • 代码

题目集链接

总结

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

C Klee in Solitary Confinement

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

附上代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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+当前最大值第二次出现后的数的个数。

代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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 ] f[x] f[x]记录子树 x x x得到的最优值； g [ x ] g[x] g[x]记录不取 x x x的孩子，也就是走到 x x 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 x的孩子。

从下至上，对每个 x 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 t[y]=3 t[y]=3，可以先走到另一个孩子节点 z z z去取再返回 y y y 取，这样就惊扰了 z z z的孩子，因此， z z z子树的贡献就变成了 g [ z ] g[z] g[z]，而不是之前预处理的 ( f [ z ] − a [ z ] ) (f[z]−a[z]) (f[z]−a[z])（这里 z z z就是 x x x的另一个儿子节点）， 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]的最大值和次大值就行了。

代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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 ) − > ( a g , b g , b − a g ) (a,b,b-a)->(frac{a}{g},frac{b}{g},frac{b-a}{g}) (a,b,b−a)−>(ga​,gb​,gb−a​)，我们需要在执行除法之前将a或者b通过加1减1的操作使得a或b能够被g整除，这样我们就会得到一个递推式,
f ( a , b − a ) = m i n ( f ( a / g , ( b − a ) / b ) + a m o d    g + 1 , f ( a / g + 1 , ( b − a ) / g ) + a − a m o d    g + 1 ) ) f(a,b-a)=min(f(a/g,(b-a)/b)+amod g+1,f(a/g+1,(b-a)/g)+a-amod g+1)) f(a,b−a)=min(f(a/g,(b−a)/b)+amodg+1,f(a/g+1,(b−a)/g)+a−amodg+1))
然后我们进行dfs，我们把中途得到的状态f(x,y)都记录下来，进行搜索，也就是记忆化搜索即可。

代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#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内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(86)

相关文章

2021ICPC南京线上游记
2021ICPC南京线上游记
TikTok产品分析&竞品分析
TikTok产品分析&竞品分析
第 46 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京），签到题5题
第 46 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京），签到题5题
Ensemble算法之GreedyEnsemble前言一、 ensemble介绍二、引入GreedyEnsemble
Ensemble算法之GreedyEnsemble前言一、 ensemble介绍二、引入GreedyEnsemble
2021icpc南京训练总结总结C Klee in Solitary ConfinementD Paimon SortingH CrystalflyJ Windblume Festival
2021icpc南京训练总结总结C Klee in Solitary ConfinementD Paimon SortingH CrystalflyJ Windblume Festival
腾讯2018广告算法大赛思路解析(python)
腾讯2018广告算法大赛思路解析(python)
机器学习比赛—杀入Kaggle Top 1%
机器学习比赛—杀入Kaggle Top 1%
分分钟带你杀入Kaggle Top 1%
分分钟带你杀入Kaggle Top 1%

评论列表共有 0 条评论

立即
投稿
返回
顶部