2006年普及组总结

这是第一题的题干：https://www.luogu.org/problemnew/show/P1059
这道题啊，直接排序不就好了嘛。

#include<iostream>
#include<cstdlib>
#include<utility>
#include<cstdio>
using namespace std;
int n,ran[1100],ans[1100],num;

void qsort(int l,int r)
{
    if(l>=r)
        return;
    int t=ran[rand()%(r-l+1)+l];
    int i=l,j=r;
    while(i<=j){
        while(ran[i]<t)i++;
        while(ran[j]>t)j--;
        if(i<=j){
            swap(ran[i],ran[j]);
            i++;
            j--;
        }
    }
    qsort(l,j);
    qsort(i,r);
}

int main()
{
    freopen("random.in","r",stdin);
    freopen("random.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>ran[i];
    srand(1000000);
    qsort(1,n);
    ans[++num]=ran[1];
    for(int i=2;i<=n;++i){
        if(ran[i]!=ran[i-1])
            ans[++num]=ran[i];
    }
    cout<<num<<endl;
    for(int i=1;i<=num;++i)
        cout<<ans[i]<<" ";
    cout<<endl;
    return 0;
}

这是第二道题的题干：https://www.luogu.org/problemnew/show/P1060
这，不就是一道最基础的动态规划的问题吗，也不用太详细说吧。。。直接上代码！！！

#include<iostream>
#include<cstdio>
using namespace std;
int T,M,f[30][30100],money[30],m[30],quan[30];

void prepare()
{
    for(int j=1;j<=T;++j){
        if(j<money[1]) f[1][j]=0;
        else f[1][j]=m[1];
    }
    for(int i=2;i<=M;++i){
        for(int j=1;j<=T;++j){
            if(j>=money[i])
                f[i][j]=max(f[i-1][j],m[i]+f[i-1][j-money[i]]);
            else
                f[i][j]=f[i-1][j];
        }
    }
}

int main()
{
    freopen("happy.in","r",stdin);
    freopen("happy.out","w",stdout);
    cin>>T>>M;
    for(int i=1;i<=M;++i){
        cin>>money[i]>>quan[i];
        m[i]=money[i]*quan[i];
    }
    prepare();
    cout<<f[M][T]<<endl;
    return 0;
}

这是第三题：https://www.luogu.org/problemnew/show/P1061
总感觉这道题真的是模拟啊，首先判断第n个位置的字母后继能不能填，如果不能填，那在看看第n-1位置的字母后继能不能填，如果还不能，那在看看第n-2位置的字母后继能不能填……以此类推，直到可以填了为止。那么每一个位置上的字母就是前一个位置上字母的后继字母。如果可填，字母就是它的后继。嗯哼，就这么完事了？（好像是这样的）

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int s,t,w;
string jam;

int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    cin>>s>>t>>w>>jam;
    for(int i=1;i<=5;i++){
        for(int j=w-1;j;j--)
            if(jam[j]-'a'+1<=j-w+t){
                jam[j]++;
                for(int k=j+1;k<w;k++)
                    jam[k]=jam[k-1]+1;
                cout<<jam<<endl;
            break;
        }
    }
    return 0;
}

这是第四题：https://www.luogu.org/problemnew/show/P1062
这道题，作为一道第四题，真心有点水。。。就是一道简简单单的二进制的问题，每一位，都有选和不选两种选择，这真的没有什么好说的。。。

#include<iostream>
#include<cstdio>
using namespace std;
const int maxN=1100;
int a[maxN],n,k,l=0;

long long mul(int di,int num)
{
    long long nans=1;
    for(int i=1;i<=num;++i)
        nans*=di;
    return nans;
}

int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    long long ans=0;
    cin>>n>>k;
    while(k!=0){
        a[++l]=k%2;
        k/=2;
    }
    for(int i=l;i>=1;i--)
        ans+=mul(n,i-1)*a[i];
    cout<<ans<<endl;
    return 0;
}