【超好懂的比赛题解】2022CCPC四川省赛个人题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了【超好懂的比赛题解】2022CCPC四川省赛个人题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

title : “海康威视杯“ 2022年第十四届四川省大学生程序设计大赛
tags : ACM,练习记录
date : 2022-10-18
author : Linno

“海康威视杯“ 2022年第十四届四川省大学生程序设计大赛

题目链接：https://ac.nowcoder.com/acm/contest/42105

出题数量：5/11 （顺序：K->F->B->H->A）

A-Adjacent Swapping

显然可以先贪心移动（直接扫一遍）字符使前后两半在字符数量上是一样的，这样便构造出了 $s 1, s 2$ ，长度均为 $l e n = n /2$ 。我的移动次数计算方法就是用 $s 1$ 每个字符原来的位置和减去原来前 $l e n$ 个位置的位置和 $l e n * (l e n - 1) /2$ 。接下来只需要考虑多少步使得 $s 2 - > s 1$ ，对于相邻两个位置交换的排序移动次数，本质上求一个逆序对就可以了（记了结论），那么直接用 $s 1$ 编号每个字符，然后减去逆序对就能得出答案。

#include<bits/stdc++.h>
#define lb(x) (x&-x) 
#define int long long
using namespace std;
const int N=2e5+7;

int n,num[30],now[30],len1=0,len2=0;
char s1[N],s2[N];
string str;
queue<int>pos[30];

int tr[N<<1];
inline int query(int x){
	int sum=0;
	for(;x;x-=lb(x)) sum+=tr[x];
	return sum;
}
inline void update(int x){
	for(;x<=len2;x+=lb(x)) tr[x]+=1;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	cin>>str;
	for(int i=0;i<n;++i) ++num[str[i]-'a'];
	vector<int>vt;
	int i,j,ans=0;
	for(i=0,j=0;i<n;++i){
		if(j<n/2){
			if(now[str[i]-'a']+1<=num[str[i]-'a']/2) ++now[str[i]-'a'],++j,s1[++len1]=str[i],ans+=i;
			else vt.emplace_back(i);  //将其放到后半段 
		}else{
			if(vt.size()){
				for(auto to:vt) s2[++len2]=str[to];
				vt.clear();
			}
			s2[++len2]=str[i]; 
		}
	}
	for(int i=1;i<=len1;++i) pos[s1[i]-'a'].emplace(i);
	for(int i=1;i<=len2;++i){
		ans-=query(pos[s2[i]-'a'].front());
		update(pos[s2[i]-'a'].front());
		pos[s2[i]-'a'].pop();
	}
	cout<<ans<<"\n";
	return 0;
}

B-usiness Website

对于一条链 $u - > v$ 来说， $v$ 的概率就在 $v$ 概率基础上多乘路径上边概率的乘积，六位小数显然是会爆的。那么经典做法就是取对数，于是就变成了递推式： $dis[v]+=pow(2,log_2(dis[u])+log2(w))，其中w为边权，dis为概率$

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7;

struct E{
	int v,nxt;
	double w;
}e[N<<1];
int head[N],cnt=0;
inline void addedge(int u,int v,double w){
	e[++cnt]=(E){v,head[u],w};head[u]=cnt;
}

int n;
double dis[N],lf[N];

void solve(){
	scanf("%d",&n);
	for(int i=1,x;i<n;++i){
		scanf("%d",&x);
		for(int j=1,v;j<=x;++j){
			double w;
			scanf("%d%lf",&v,&w);
			addedge(i,v,w);
			lf[i]+=w;
		}
	}
	dis[1]=1.0;
	for(int i=1;i<n;++i){
		for(int j=head[i];j;j=e[j].nxt){
			int to=e[j].v;double w=e[j].w;
			dis[to]+=pow(2,log2(dis[i])+log2(w));
		}
		dis[i]*=(1.0-lf[i]);
	}
	for(int i=1;i<=n;++i) printf("%.8lf ",dis[i]);
	puts("");
	for(int i=0;i<=n;++i) head[i]=dis[i]=lf[i]=0;
	cnt=0; 
}

signed main(){
	int t;
	scanf("%d",&t);
	while(t--){
		solve();
	}
	return 0;
}

/*
3
3
2 2 0.300000 3 0.300000
1 3 0.500000
5
1 2 0.111111
1 3 0.111111
1 4 0.111111
1 5 0.111111
4
3 2 0.500000 3 0.100000 4 0.200000
2 3 0.400000 4 0.600000
1 4 0.700000
*/

F-Factor Difference

不会证，打表打出来了规律（顺便把打表程序贴在下面了），后面所有 $x$ 都是三个最小间隔的质数相乘，这个间隔指三个数差不小于 $n$ ,同时第一个数至少大于 $n$ （因为1也是因子）。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+7;
const int inf=0x3f3f3f3f; 

int n,t,np[N],pri[N],cnt=0;
void init(){
	np[1]=1;
	for(int i=2;i<N;++i){
		if(!np[i]) pri[++cnt]=i;
		for(int j=1;j<=cnt&&pri[j]*i<N;++j){
			np[pri[j]*i]=1;
			if(i%pri[j]==0) break;
		}
	}
}

void solve(){
	cin>>n;
	if(n==1){
		cout<<"24\n";
		return;
	}else if(n==2){
		cout<<"105\n";
		return;
	}else{
		int k=lower_bound(pri+1,pri+1+cnt,n+1)-pri;
		int p=lower_bound(pri+1,pri+1+cnt,pri[k]+n)-pri;
		int q=lower_bound(pri+1,pri+1+cnt,pri[p]+n)-pri;
		int ans=pri[k]*pri[p]*pri[q];
		//cout<<n<<" "<<pri[k]<<" "<<pri[p]<<" "<<pri[q]<<" "<<ans<<"!!\n";	
		cout<<ans<<"\n";
	}
}

signed main(){
	init();
	cin>>t;
	for(int i=1;i<=t;++i){
		//n=i;
		solve();
	}
	return 0;
}

/*
int solve(int n,int lst){
	for(int ans=24;;++ans){
		int lst=1,cnt=1,flag=1;
		for(int j=2;j<=ans;++j){
			if(ans%j==0){
				if(j-lst<n){
					flag=0;
					break;
				}
				else ++cnt,lst=j;
			}
		}
		if(flag&&cnt>=8){
			return ans;
		}
	} 
}

signed main(){
	init();
	cin>>t;
	for(int n=1,lst;n<=t;++n){
		int ans=solve(n,lst);
		cout<<n<<" "<<ans<<" ";
		for(int j=1;j<=20;++j){
			int len=0;
			while(ans%pri[j]==0) ++len,ans/=pri[j];
			cout<<len<<" ";
		}
		lst=ans;
		cout<<"\n";
	}
	return 0;
}*/

H-Hacking Interview Solution

感觉这才应该是签到题吧，简单来说就是问有多少对 $n$ 维向量是冲突的。这不就直接双哈希搞定了吗。

#include<bits/stdc++.h>
#define int long long
#define mk make_pair
#define pii pair<int,int>
using namespace std;
const int mod1=1e9+7,mod2=1e9+9;
const int b1=131,b2=233;
const int N=1e5+7;

int n,m,t,a[N];
map<pii,int>mp;

inline int read(){
	int x=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x; 
}

void solve(){
	mp.clear();
	n=read();m=read();
	int ans=0;
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=m;++i){
		int hs1=0,hs2=0;
		for(int j=1,x;j<=n;++j){
			x=read();
			hs1=(hs1*b1+x)%mod1;
			hs2=(hs2*b2+x)%mod2;
		}
		ans+=mp[mk(hs1,hs2)];
		++mp[mk(hs1,hs2)];
	}
	printf("%lld\n",ans);
}

signed main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

K-Kooky Clock

签到题。直接照着按点旋转的板子写就行了。文章来源地址https://www.toymoban.com/news/detail-472324.html

#include<bits/stdc++.h>
#define LD double
#define LL long long
#define Re int
#define Vector Point
using namespace std;
const int N=262144+3;
const LD eps=1e-8,Pi=acos(-1.0);
inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}//处理精度
inline LD Abs(LD a){return a*dcmp(a);}//取绝对值
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}
    inline void in(){scanf("%lf%lf",&x,&y);}
    inline void out(){printf("%.8lf %.8lf\n",x,y);}
};


/*二：【向量】*/
inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}//【点积】
inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}//【叉积】
inline LD Len(Vector a){return sqrt(Dot(a,a));}//【模长】
inline LD Angle(Vector a,Vector b){return acos(Dot(a,b)/Len(a)/Len(b));}//【两向量夹角】
inline Vector Normal(Vector a){return Vector(-a.y,a.x);}//【法向量】
inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}
inline bool operator==(Point a,Point b){return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y);}//两点坐标重合则相等


/*三：【点、向量的位置变换】*/

/*1.【点、向量的旋转】*/
inline Point turn_P(Point a,LD theta){//【点A\向量A顺时针旋转theta(弧度)】
    LD x=a.x*cos(theta)+a.y*sin(theta);
    LD y=-a.x*sin(theta)+a.y*cos(theta);
    return Point(x,y);
}
inline Point turn_PP(Point a,Point b,LD theta){//【将点A绕点B顺时针旋转theta(弧度)】
    LD x=(a.x-b.x)*cos(theta)+(a.y-b.y)*sin(theta)+b.x;
    LD y=-(a.x-b.x)*sin(theta)+(a.y-b.y)*cos(theta)+b.y;
    return Point(x,y);
}

signed main(){
	int T,l1,l2,l3,t1,t2,t3;
	scanf("%d",&T);
	scanf("%d%d%d",&l1,&l2,&l3);
	scanf("%d%d%d",&t1,&t2,&t3);
	Point p1(0,l1),O(0,0);
	p1=turn_PP(p1,O,2.0*Pi*T/t1);
	Point p2(p1.x,p1.y+l2);
	p2=turn_PP(p2,p1,2.0*Pi*T/t2);
	Point p3(p2.x,p2.y+l3);
	p3=turn_PP(p3,p2,2.0*Pi*T/t3);
	p3.out();
	return 0;
}