洛谷88375文华信奥题单题解

章杨一

2024-09-15 11:41:56

发布于：浙江

2阅读

0回复

0点赞

洛谷 88375文华信奥题单题解

一、第一次作业

1、简单计算器

#include<bits/stdc++.h>
using namespace std;
int main() {
	int a,b;
	char c;
	cin>>a>>b>>c;
	switch(c) {
		case '+':
			cout<<a+b;
			break;
		case '-':
			cout<<a-b;
			break;
		case '*':
			cout<<a*b;
			break;
		case '/':
			if(!b)cout<<"Divided by zero!";
			else cout<<a/b;
			break;
		default:
			cout<<"Invalid operator!";
			break;
	}
	return 0;
}

2、第 k 小整数

#include<bits/stdc++.h>
using namespace std;
const int N = 3e4+10;
int n,k,vis[N],a[N];
int main() {
	cin >> n >> k;
	int idx = 1;
	for (int i=1; i<=n; i++) {
		int x;
		cin >> x;
		if (!vis[x]) {
			a[idx++] = x;
			vis[x] = 1;
		}
	}
	sort(a+1,a+idx);
	if(idx-1 >= k) {
		cout << a[k];
	} else {
		cout << "NO RESULT";
	}
	return 0;
}

3、[NOIP2001 普及组] 最大公约数和最小公倍数问题

#include <bits/stdc++.h>
using namespace std;
long long x,y;
long long gcd(long long a,long long b)
{
    return b? gcd(b,a%b):a;
}
bool vis[100005]={0};
long long lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
int main()
{
    cin>>x>>y;
    long long i,j;
    long long z=x*y;
    long long ans=0;
    for(i=x;i<=y;i++) 
    {
        if(z%i==0)
        {
            if(gcd(i,z/i)==x&&lcm(i,z/i)==y)
            {
                if(i==z/i)
                {
                    cout<<ans*2+1;
                    return 0;
                }
                if(vis[i])
                {
                    cout<<ans*2;
                    return 0;
                }
                else
                {
                    ans++;
                    vis[i]=vis[z/i]=1;
                }
            }
        }
    }
    if(ans==0)cout<<0;
    return 0;
}

4、台阶问题

#include<bits/stdc++.h>
using namespace std;
int n,k;
int dp[1000005];
int main() {
	cin>>n>>k;
	dp[0]=1;
	dp[1]=1;
	for(int i=2; i<=n; i++) {
		for(int j=1; j<=k; j++) {
			if((i-j)>=0) {
				dp[i]=(dp[i]+dp[i-j])%100003;
			}
		}
	}
	cout<<dp[n]%100003;
	return 0;
}

5、硬币问题

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin>>n;
    if(n%11==0){
        cout<<n/11;
    }else if(n/11-1+(n%11+11)/5+(n%11+11)%5<(n/5+n%5)&&n/11-1+(n%11+11)/5+(n%11+11)%5<(n/11+n%11%5+n%11/5)){
        cout<<n/11-1+(n%11+11)/5+(n%11+11)%5;
    }else if((n/11+n%11%5+n%11/5)>=(n/5+n%5)){
        cout<<n/5+n%5;
    }else{
        cout<<n/11+n%11/5+n%11%5;
    }
	return 0;
}

6、[NOIP2006 提高组] 能量项链

#include<bits/stdc++.h>
#define map unordered_map
using namespace std;
#define prc(x) printf(#x":%c\n",x)
#define pri(x) printf(#x":%d\n",x)
#define prl(x) printf(#x":%lld\n",x)
#define ll long long
#define ull unsigned long long
int f[305][305],a[305];
int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	for(int i=n+1;i<=n<<1;i++)
		a[i]=a[i-n];
	int nn=n;
	n=n<<1;
	for(int i=1;i<=n;i++) f[i][i]=f[i][i+1]=0;
	for(int l=1;l<=n;l++){
		for(int i=1;i+l<=n;i++){
			int j=i+l;
			for(int k=i+1;k<j;k++){
				f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=nn;i++) ans=max(ans,f[i][nn+i]);
	cout << ans;
	return 0; 
}