The 15th Jilin Provincial Collegiate Programming Contest

垂死挣扎一个月，求求省赛别让孩子打铁吧！！！！我真的不想打铁了QAQ

A. Random Number Checker

int a[N];
void solves(){
	int n;cin>>n;
	int o=0,j=0;
	for(int i=0;i<n;i++){
		int x;cin>>x;
		if(x&1) j++;
		else o++;
	}
	cout<<(abs(j-o)<=1 ? "Good":"Not Good")<<endl;
}

B. Arithmetic Exercise

选拔赛有个差不多的但是数据水了，没考虑四舍五入后进位的情况都AC了。搞得这题直接思维定势wa了几发，呃

int ans[1007];
void solves(){
	int a,b,k;cin>>a>>b>>k;
	for(int i=1;i<=k+2;i++){
		ans[i]=(a*10)/b;
		a=(a*10)%b;
	}
	if(ans[k+1]>=5)
		ans[k]++;
	for(int i=k;i>0;i--){
		if(ans[i]>=10){
			int re=ans[i]/10;
			ans[i-1]+=re;
			ans[i]=ans[i]%10;
		}
	}
	for(int i=0;i<=k;i++){
		cout<<ans[i];
		if(i==0) cout<<".";
	}
}

E. Great Detective TJC

大概是div2 A的难度，原来还有人写字典树

异或值为1的数必然是相邻的两个数，相邻的两个数不一定是异或值为1的数。

void solves(){
	int n;cin>>n;
	vector<int>a(n);
	for(auto &i:a) cin>>i;
	sort(a.begin(),a.end());
	for(int i=0;i<n-1;i++){
		if((a[i]^a[i+1])==1){
			cout<<"Yes"<<endl; return;
		}
	}
	cout<<"No"<<endl;
}

G. Matrix Repair

不会

H. Visit the Park

这个题意真的好难懂，读得真的想摆，读题的时间>>找思路+写代码的时间

拿样例1举个例子，样例1如上图。

$14×\frac{1}{6}+11×\frac{1}{6}+24×\frac{1}{3}+21×\frac{1}{3}=(1+2+2)×10^1×\frac{1}{3}+(1+4)×10^0×\frac{1}{2}$

即将$A_i$到$A_{i+1}$的路径的权值和以及路径的个数统计一下即可，考虑用$map$对两点做映射来统计，无需建图。

ll exgcd(ll a,ll b,ll &x,ll &y){
    ll d=a;
    if(b){
        d=exgcd(b,a%b,y,x);
    	y-=(a/b)*x;
    } else{
        x=1;y=0;
    }
    return d;
}
ll inv(ll a,ll mod){
    ll x,y;
    if (exgcd(a, mod, x, y)!=1)
        return -1;
    return (x%mod+mod)%mod;
}
map<pair<int,int>,ll>val,cnt;
void solves(){
	int n,m,k;cin>>n>>m>>k;
	while(m--){
		int u,v,w;cin>>u>>v>>w;
		val[{u,v}]+=w;
		val[{v,u}]+=w;
		cnt[{u,v}]++;
		cnt[{v,u}]++;
	}
	vector<int>a(k);
	for(auto &i:a) cin>>i;
	reverse(a.begin(),a.end());
	ll ans=0;
	for(int i=0;i<k-1;i++){
		int u=a[i],v=a[i+1];
		if(!cnt.count({u,v})){
			cout<<"Stupid Msacywy!"<<endl;
			return ;
		} else{
			ans+=(val[{u,v}]%mod*qpow(10,i)%mod*inv(cnt[{u,v}],mod)%mod)%mod;
			ans%=mod;
		}
	}
	cout<<ans<<endl; 
}

K. Bracket Sequence

$n$对括号，问有多少种“括号匹配”的括号序列。很经典的卡特兰数模型。

其中有$k$种括号，即对于每个括号都有$k$种形式。由高中数学可得，答案为卡特兰数再乘一个$k^n$。

ll exgcd(ll a,ll b,ll &x,ll &y){
    ll d=a;
    if(b){
        d=exgcd(b,a%b,y,x);
    	y-=(a/b)*x;
    } else{
        x=1;y=0;
    }
    return d;
}
ll inver(ll a,ll mod){
    ll x,y;
    if(exgcd(a, mod, x, y)!=1)
        return -1;
    return (x%mod+mod)%mod;
}
ll inv[N],f[N];
void pre(){
	f[0]=1;
	for(int i=1;i<N;++i) f[i]=f[i-1]*i%mod;
	inv[N-7]=inver(f[N-7],mod);
	for(int i=N-8;i>=0;--i) inv[i]=inv[i+1]*(i+1)%mod;
}
ll cal(ll n,ll m){
	if(!m)return 1;
	if(m>n)return 0;
	return f[n]*inv[m]%mod*inv[n-m]%mod;//组合数
//	return f[n]*inv[n-m]%mod;//排列数
}
void solves(){
	int n,k;cin>>n>>k;
	cout<<(cal(2*n,n)*inver(n+1,mod)%mod*qpow(k,n))%mod<<endl;
}

L. Suzuran Loves Stringz

容易发现，两个后缀串的开头第一个字母不一样的时候，答案为两个串的长度之和。

进一步考虑两个后缀串，答案为长度之和减去相等的前缀。

再考虑一个字符串，他的后缀串的相等的前缀取决于他的前缀有多少个相等的字符。

然后再特判一下所有字母都相等的字符串的情况。

void solves(){
	string s;cin>>s;
	int n=s.size();
	int idx=1;
	for(;idx<n;idx++){
		if(s[0]!=s[idx]) break;
	}
	if(idx==n){
		cout<<n-1<<endl;
	} else{
		cout<<n+(n-idx)<<endl;
	}
}

M. Sequence

void solves(){
	int n;cin>>n;
	int mi=inf,ma=-inf;
	for(int i=0;i<n;i++){
		int x;cin>>x;
		ma=max(ma,x);
		mi=min(mi,x);
	}
	cout<<n*(ma-mi)<<endl;
}

打赏