欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客-西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛

程序员文章站 2023-12-24 15:09:27
...

A-找规律

牛客-西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛

2*9-13=5,映射13次一次循环

/*
* problem:找规律
* method:映射循环
* date:2020/07/07
*/
#include<iostream>
#include<string>
#define LL long long
using namespace std;
string s1[14],s2[14];
int f[14],n=13;
int main() {
	int i,j;
	while(cin>>s1[0]) {
		for(i=1; i<n; i++) cin>>s1[i];
		for(i=0; i<n; i++) cin>>s2[i];
		for(i=0; i<n; i++) {
			for(j=0; j<n; j++) {
				if(s1[i]==s2[j]) {
					f[i]=j;
					break;
				}
			}
		}
		for(i=0; i<n; i++) {
			int t=i;
			for(j=0; j<9; j++) t=f[t];
			s2[t]=s1[i];
		}
		for(i=0; i<n-1; i++) {
			cout<<s2[i]<<' ';
		}
		cout<<s2[n-1]<<endl;
	}
	return 0;
}

B-签到题

牛客-西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛

找公式,(n-1)!*(n-1)*n/2

/*
* problem:签到题
* method:阶乘、取余、空间换时间
* date:2020/07/07
*/
#include<iostream>
using namespace std;
long long int MAX=1e9+7;
long long int f[100005];
int main(){
    long long n;
    f[0]=1;
    for(int i=1;i<100005;i++){
    	f[i]=(i*f[i-1])%MAX;
	}
    while(cin>>n){
        cout<<(((n*(n-1)/2%MAX)*f[n])%MAX)<<endl;
    }
    return 0;
}

C-救救AR

牛客-西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛

找规律:两个A,n-2个R,cell(n/2)+floor(n/2)=n

/*
* problem:救救AR
* method:找规律、string
* date:2020/07/07
*/
#include<iostream>
#include<string>
#define LL long long
using namespace std;
int main(){
	int n;
	string s;
	while(cin>>n){
		if(n<4){
			cout<<"-1"<<endl;
		}else{
			s="";
			int i,x=n/2,y=n-x;
			s+="A";
			for(i=0;i<y-x;i++) s+="R";
			s+="A";
			for(i=0;i<x;i++) s+="R";
			cout<<s<<endl;
		}
		
	}
	return 0;
}

D-ar采蘑菇

牛客-西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛

动态规划,位表示集合

/*
* problem:ar采蘑菇
* method:dp、位压缩表示集合
* date:2020/07/11
*/
#include<iostream>
#include<string>
#include<utility>
#define LL long long
using namespace std;
typedef pair<int,int> P;
int n,m,k,t;
P p[5];
int dp[105][105];
int popcount(int x) {
	int count=0;
	while(x) {
		x=(x&(x-1));
		count++;
	}
	return count;
}
void bfs(int x,int y,int z) {
	int i,j,num,nx,ny,nz;
	if(x==n&&y==m) return;
	for(i=0; i<k; i++) {
		nx=x+p[i].first;
		ny=y+p[i].second;
		nz=z|(1<<i);
		num=popcount(nz);
		if(nx<=n&&ny<=m&&num>dp[ny][nx]){
			dp[ny][nx]=num;
			bfs(nx,ny,nz);
		} 
	}
}
int main() {
	int i,j,num;
	cin>>t;
	while(t--) {
		num=0;
		cin>>n>>m>>k;
		for(i=0;i<=m;i++){
			for(j=0;j<=n;j++) dp[i][j]=0;
		}
		for(i=0; i<k; i++) {
			string s;
			p[i].first=0;
			p[i].second=0;
			cin>>s;
			for(j=0; j<s.size(); j++) {
				if(s[j]=='R') {
					p[i].first++;
				} else if(s[j]=='U') {
					p[i].second++;
				}
			}
		}
		bfs(0,0,0);
		cout<<dp[m][n]<<endl;
	}
	return 0;
}

E-呼兰河传

牛客-西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛

筛素数法、快速幂、LCM

/*
* problem:
* method:
* date:
*/
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
const int N=1e6+5,MAX=1e5+5,MOD=1e9+9;
int prime[N],p[N],power[N],mp[N],cnt;
int max(int a,int b){
	return a>b?a:b;
}
void init(){//筛素数
	prime[0]=1;
	prime[1]=1;
	for(int i=2;i<=sqrt(MAX);i++){
		if(!prime[i]){
			p[cnt++]=i;
			mp[i]=cnt-1;
			for(int j=2;i*j<=MAX;j++) prime[i*j]=1;
		}
	}
}
ll fastPower(ll base,ll power){
	ll result=1;
	while(power>0){
		if(power&1){
			result=result*base%MOD;
			power--;
		}
		base=base*base%MOD;
		power>>=1;
	}
	return result;
}
int main(){
	int n,i,j,x;
	init();
	cin>>n;
	while(n--){
		cin>>x;
		for(i=0;i<cnt&&x>=p[i];i++){
			int cur=0;
			if(x%p[i]==0){
				while(x%p[i]==0){
					cur++;
					x/=p[i];
				}
			}
			power[i]=max(power[i],cur);
		}
		if(x>1){
			int j=0;
			if(!mp[x]){
				p[cnt++]=x;
				mp[x]=cnt-1;
				j=cnt-1;
			}else{
				j=mp[x];
			}
			power[j]=max(1,power[j]);
		}
	}
	ll lcm=1;
	for(i=0;i<cnt;i++){
		if(power[i]) lcm=lcm*fastPower(p[i],power[i])%MOD;
	}
	cout<<lcm<<endl;
	return 0;
}

上一篇:

下一篇: