title : “?？低暠?2022年第十四屆四川省大學生程序設(shè)計大賽
tags : ACM,練習記錄
date : 2022-10-18
author : Linno

“?？低暠?2022年第十四屆四川省大學生程序設(shè)計大賽

題目鏈接：https://ac.nowcoder.com/acm/contest/42105

出題數(shù)量：5/11 （順序：K->F->B->H->A）

A-Adjacent Swapping

顯然可以先貪心移動（直接掃一遍）字符使前后兩半在字符數(shù)量上是一樣的，這樣便構(gòu)造出了$s1,s2$，長度均為$len=n/2$。我的移動次數(shù)計算方法就是用$s1$每個字符原來的位置和減去原來前$len$個位置的位置和$len?(len?1)/2$。接下來只需要考慮多少步使得$s2?>s1$，對于相鄰兩個位置交換的排序移動次數(shù)，本質(zhì)上求一個逆序?qū)涂梢粤耍ㄓ浟私Y(jié)論），那么直接用$s1$編號每個字符，然后減去逆序?qū)湍艿贸龃鸢浮?/p>

#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$概率基礎(chǔ)上多乘路徑上邊概率的乘積，六位小數(shù)顯然是會爆的。那么經(jīng)典做法就是取對數(shù)，于是就變成了遞推式：

#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

不會證，打表打出來了規(guī)律（順便把打表程序貼在下面了），后面所有$x$都是三個最小間隔的質(zhì)數(shù)相乘，這個間隔指三個數(shù)差不小于$n$,同時第一個數(shù)至少大于$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

感覺這才應(yīng)該是簽到題吧，簡單來說就是問有多少對$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

簽到題。直接照著按點旋轉(zhuǎn)的板子寫就行了。文章來源地址http://www.zghlxwxcb.cn/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.【點、向量的旋轉(zhuǎn)】*/
inline Point turn_P(Point a,LD theta){//【點A\向量A順時針旋轉(zhuǎn)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順時針旋轉(zhuǎn)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;
}

到了這里，關(guān)于【超好懂的比賽題解】2022CCPC四川省賽 個人題解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！