算法设计备考

1729石子合并问题

#include <bits/stdc++.h>
const int maxn=1e2+100;
using namespace std;
int n;
int w[maxn];
int minans[maxn][maxn],maxans[maxn][maxn];
int getsum(int i,int j){
    int sum=0;
    for(;j>0;i++,j--){
        sum+=w[i%n];
    }
    return sum;
}

int main()
{
    memset(minans,0x3f3f3f3f,sizeof(minans));
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>w[i];
        minans[i][1]=0;
    }
    for(int len=2;len<=n;len++){
        for(int i=0;i<n;i++){
            for(int k=1;k<len;k++){
                maxans[i][len]=max(maxans[i][len],maxans[i][k]
                               +maxans[(i+k)%n][len-k]+getsum(i,len));
                minans[i][len]=min(minans[i][len],minans[i][k]
                                +minans[(i+k)%n][len-k]+getsum(i,len));
            }
        }
    }
    int ansa=1e9,ansb=0;
    for(int i=0;i<n;i++){
        ansa=min(ansa,minans[i][n]);
        ansb=max(ansb,maxans[i][n]);
    }
    cout<<ansa<<endl;
    cout<<ansb<<endl;
    return 0;
}

1760 多元Huffman编码问题

#include <bits/stdc++.h>
const int maxn=1e5+100;
using namespace std;
long long n,k;
long long w[maxn];
int main()
{
    cin>>n>>k;
    priority_queue<long long>q;
    priority_queue<long long,vector<long long> ,greater<long long> >qq;
    for(int i=0;i<n;i++){
        cin>>w[i];
        q.push(w[i]);
        qq.push(w[i]);
    }
    long long ansa=0,ansb=0;
    while(q.size()>1){
        int x=q.top();
        q.pop();
        int y=q.top();
        q.pop();
        x+=y;
        q.push(x);
        ansa+=x;
    }
    cout<<ansa<<" ";
    while(qq.size()%(k-1)!=1)
        qq.push(0);
    while(qq.size()>1){
        int sum=0;
        for(int i=0;i<k;i++){
            sum+=qq.top();
            qq.pop();
        }
        qq.push(sum);
        ansb+=sum;
    }
    cout<<ansb<<endl;
    return 0;
}

1298 活动选择问题

#include <bits/stdc++.h>
const int maxn=1e5+100;
using namespace std;
struct node{
    int s,e,id;
}a[110],b[110];
bool cmp(node a,node b){
    if(a.e<b.e){
        return true;
    }
    else return false;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].s>>a[i].e;
        a[i].id=i+1;
    }
    sort(a,a+n,cmp);
    int k=0;
    for(int i=0;i<n;i++){
        if(a[i].s>=b[k].e){
            b[++k]=a[i];
        }
    }
    for(int i=1;i<=k;i++){
        if(i!=1)cout<<",";
        cout<<b[i].id;
    }
    return 0;
}

1764 子集和问题

#include <bits/stdc++.h>
const int maxn=1e5+100;
using namespace std;
int w[maxn];
int n,c;
long long sum;
stack<int>ans;
int dfs(int now){
    if(sum==c){
        return 1;
    }
    if(sum>c){
        return 0;
    }
    if(now==n){
        return 0;
    }
    sum+=w[now];
    if(dfs(now+1)){
        ans.push(w[now]);
        return 1;
    }
    sum-=w[now];
    if(dfs(now+1)){
        return 1;
    }
    return 0;
}
int main()
{
    cin>>n>>c;
    int sum=0;
    for(int i=0;i<n;i++){
        cin>>w[i];
        sum+=w[i];
    }
    if(sum<c){
        cout<<"No Solution!"<<endl;
        return 0;
    }
    if(dfs(0)){
        while(ans.size()>1){
            cout<<ans.top()<<" ";
            ans.pop();
        }
        cout<<ans.top();
    }
    else cout<<"No Solution!"<<endl;
    return 0;
}

1767 运动员最佳匹配问题

#include <bits/stdc++.h>
const int maxn=22;
using namespace std;
int n;
int p[maxn][maxn],q[maxn][maxn],vis[maxn],a[maxn];
int best;
void dfs(int x,int s){
    if(x>n){
        best=max(best,s);
        return;
    }
    if(s+a[n]-a[x-1]<best){
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            dfs(x+1,p[x][i]*q[i][x]+s);
            vis[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>p[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>q[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i]=max(a[i],p[i][j]*q[j][i]);
        }
        a[i]+=a[i-1];
    }
    dfs(1,0);
    cout<<best;
    return 0;
}

1776 工作分配问题

#include <bits/stdc++.h>
const int maxn=1e2+100;
using namespace std;
int n;
int minans=10000100;
int vis[maxn];
int a[maxn][maxn];
void solve(int x,int s){
    if(x>n&&minans>s){
        minans=s;
        return;
    }
    if(minans<s)
        return;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            solve(x+1,s+a[x][i]);
            vis[i]=0;
        }
    }
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    solve(1,0);
    cout<<minans<<endl;
    return 0;
}

1771 整数变换问题

#include <bits/stdc++.h>
const int maxn=1e2+100;
using namespace std;
int k;
int n,m;
vector<char>a;
int s(int i,int n){
    if(i==0)
        return 3*n;
    else return n/2;
}
int f(int x,int n,int m){
    int sum=0;
    if(x>k)
        return 0;
    for(int i=0;i<2;i++){
        sum=s(i,n);
        if(sum==m||f(x+1,sum,m)){
            if(i==0)
                a.push_back('f');
            else a.push_back('g');
            return 1;
        }
    }
    return 0;
}
int main()
{
    cin>>n>>m;
    k=1;
    while(!f(1,n,m))
        k++;
    cout<<k<<endl;
    for(int i=0;i<a.size();i++){
        cout<<a[i];
    }
    cout<<endl;
    return 0;
}

1750 汽车加油问题

#include <bits/stdc++.h>
const int maxn=5e3+100;
using namespace std;
int dis[maxn];

int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<=k;i++){
        cin>>dis[i];
    }
    int s=n;
    int num=0;
    for(int i=0;i<=k;i++){
        if(dis[i]>n){
            cout<<"No Solution!"<<endl;
            return 0;
        }
        else{
            if(s>=dis[i]){
                s-=dis[i];
            }
            else {
                s=n-dis[i];
                num++;
            }
        }
    }
    cout<<num<<endl;
    return 0;
}

2052 装船问题

#include <bits/stdc++.h>
const int maxn=5e3+100;
using namespace std;
struct node{
    int w,p;
    double b;
}a[110];

bool cmp(node x,node y){
    return x.b>y.b;
}

int main()
{
    int m;
    cin>>m;
    for(int i=0;i<10;i++){
        cin>>a[i].p>>a[i].w;
        a[i].b=a[i].p*1.0/a[i].w;
    }
    sort(a,a+10,cmp);
    int ans=0;
    for(int i=0;i<10;i++){
        if(a[i].w<=m){
            m-=a[i].w;
            ans+=a[i].p;
        }
        else{
            ans+=a[i].b*m;
            m=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

1743 最优合并问题

#include <bits/stdc++.h>
const int maxn=5e3+100;
using namespace std;

int main()
{
    priority_queue<int>q;
    priority_queue<int,vector<int>,greater<int> >qq;
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        int d;
        cin>>d;
        q.push(d);
        qq.push(d);
    }
    int ansa=0,ansb=0;
    while(q.size()>1){
        int a=q.top();
        q.pop();
        int b=q.top();
        q.pop();
        a+=b;
        q.push(a);
        ansa+=a;
    }
    while(qq.size()>1){
        int a=qq.top();
        qq.pop();
        int b=qq.top();
        qq.pop();
        a+=b;
        qq.push(a);
        ansb+=a;
    }
    cout<<ansa-k+1<<" "<<ansb-k+1<<endl;
    return 0;
}

1751 区间覆盖问题

#include <bits/stdc++.h>
const int maxn=5e4+100;
using namespace std;
int a[maxn];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    int num=1;
    int mark=a[0];
    for(int i=0;i<n;i++){
        if(a[i]>mark+k){
            mark=a[i];
            num++;
        }
    }
    cout<<num<<endl;
    return 0;
}

3358 高数Umaru系列(9)——哈士奇

#include <bits/stdc++.h>
const int maxn=5e4+100;
using namespace std;
int dp[maxn];
struct node {
    int p,m;
} a[maxn];
int main() {
    int n,x;
    while(cin>>n>>x) {
        memset(dp,0,sizeof(dp));
        for(int i=0; i<n; i++) {
            cin>>a[i].p>>a[i].m;
        }
        for(int i=0; i<n; i++) {
            for(int j=x; j>=a[i].p; j--) {
                dp[j]=max(dp[j],dp[j-a[i].p]+a[i].m);
            }
        }
        cout<<dp[x]<<endl;
    }
    return 0;
}

1725 最少硬币问题

#include <bits/stdc++.h>
const int maxn=5e5+100;
using namespace std;
int dp[maxn];
int coins[maxn];
int t[maxn];

int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>t[i]>>coins[i];
    }
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        dp[i]=0x3f3f3f3f;
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<=coins[i];j++){
            for(int k=m;k>=t[i];k--){
                dp[k]=min(dp[k],dp[k-t[i]]+1);
            }
        }
    }
    if(dp[m]<m)
        cout<<dp[m];
    else cout<<"-1"<<endl;
    return 0;
}

2080 最长公共子序列问题

#include <bits/stdc++.h>
const int maxn=5e2+100;
using namespace std;
int mp[maxn][maxn];
string s,ss;
int main() {
    while(cin>>s>>ss) {
        memset(mp,0,sizeof(mp));
        int len=s.size(),lenn=ss.size();
        for(int i=1; i<=len; i++) {
            for(int j=1; j<=lenn; j++) {
                int ii=i-1;
                int jj=j-1;
                if(s[ii]==ss[jj]) {
                    mp[i][j]=mp[i-1][j-1]+1;
                } else {
                    mp[i][j]=max(mp[i-1][j],mp[i][j-1]);
                }
            }
        }
        cout<<mp[len][lenn]<<endl;
    }
    return 0;
}

1710 众数问题

#include <bits/stdc++.h>

using namespace std;
unordered_map<int,int>mp;
int main()
{
    int n;
    scanf("%d",&n);
    int d,ans=0,maxxx=0;
    for(int i=0;i<n;i++){
        scanf("%d",&d);
        mp[d]++;
        if(mp[d]>maxxx){
            maxxx=mp[d];
            ans=d;
        }
        else if(mp[d]==maxxx&&d<ans){
            ans=d;
        }
    }
    printf("%d\n%d\n",ans,mp[ans]);
    return 0;
}

1722 整数因子分解问题

#include <bits/stdc++.h>

using namespace std;
int f(int n){
    int sum=1;
    int d=sqrt(n);
    for(int i=2;i<=d;i++){
        if(n%i==0){
            if(i*i==n){
                sum+=f(i);
            }
            else sum+=f(i)+f(n/i);
        }
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    cout<<f(n)<<endl;
    return 0;
}

3664 顺序表应用7:最大子段和之分治递归法

#include <bits/stdc++.h>

using namespace std;
int a;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int sum=0,ans=0;
    for(int i=1;i<=n;i++){
        cin>>a;
        if(sum+a>=0){
            sum+=a;
            ans=max(ans,sum);
        }
        else sum=0;
    }
    cout<<ans<<" "<<n*2-1<<endl;
    return 0;
}

1018 骨牌铺方格

#include <bits/stdc++.h>

using namespace std;
long long a[60];
int main()
{
    ios::sync_with_stdio(false);
    a[1]=1;
    a[2]=2;
    for(int i=3;i<=50;i++){
        a[i]=a[i-1]+a[i-2];
    }
    int n;
    while(cin>>n){
        cout<<a[n]<<endl;;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注