牛客-西南科技大学第十六届ACM程序设计竞赛暨绵阳市邀请赛
程序员文章站
2023-12-24 15:09:27
...
A-找规律
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-签到题
找公式,(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
找规律:两个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采蘑菇
动态规划,位表示集合
/*
* 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-呼兰河传
筛素数法、快速幂、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;
}