2016.8.28試験解題報告(buylow,line,brush)

11360 ワード

テスト

はい、お久しぶりです.

1.格安購入

質問説明:「低価格購入」という提案は、乳牛株式市場で成功した半分のルールです.偉大な投資家と見なされるには、「低価格で購入する;さらに低価格で購入する」という質問に従わなければなりません.株を買うたびに、前回購入した価格より低い価格で購入しなければなりません.買う回数が多ければ多いほどいい!あなたの目標は、以上のアドバイスを前提に、株を最大で購入できる回数を求めることです.しばらくの間、1株の株の毎日の価格(216範囲の正の整数)が与えられ、どの日にこの株を購入するかを選択することができます.購入するたびに「低価格購入;再低価格購入」の原則に従わなければならない.最大購入回数を計算するプログラムを書きます.ここはある株の価格リストです:日付1 3 4 5 6 7 8 9 10 11 12価格68 69,5464,68,677,7862,9887最も優秀な投資家は最大4回の株を購入することができて、実行可能な方案の1つは:日付2 5 6,10価格69,68,6462
構想:テーマの意味は明らかで、私たちは1つのシーケンスの最長降下サブシーケンスを求める必要があります.そして、私たちはそのスキームの総数を求める必要があります.まず,f[i]をiで終わる最長降下サブシーケンスの長さをどの程度表すかとすると,F[0]=0 F[i]=max{f[j]}+1(ja[i])という方程式の時間的複雑度はO(n^2)である.シナリオ数を記録するために、g[i]をiで終わる最長降下サブシーケンスのシナリオ数を表すと、g[0]=0 g[i]=Ʃg[j]しかし、テーマでは、シナリオが同じように見える場合、同じシナリオとして計算する必要があることが要求されているので、上のすべてのjの中でa[j]が同じで、私はj値が最大であればよい.最後の全時間複雑度はO(n^2)であった.
コード:

/*
2016.8.30 BulaBulaCHN
*/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int a[5005];
int n;
int f[5005];
int g[5005];
int ans,an;
int main()
{
    freopen("buylow.in","r",stdin);
    freopen("buylow.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    a[0]=2147483647;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i-1;j++)
        if(a[i]1);
g[0]=1;
for(int i=1;i<=n;i++)
for(int j=i-1;j>=0;j--)
{
if(a[i]1==f[i]) g[i]+=g[j];
if(a[i]==a[j]) break;// に じものを1 だけ ります。 です。
}
for(int i=1;i<=n;i++) if(f[i]>ans) ans=f[i];
int tot=0;
for(int i=1;i<=n;i++) if(f[i]==ans) tot+=g[i];
cout<" "<return 0;
}

2.通信回線

ある地域にはnの村があり、各村の座標は1対の整数(x,y)で表され、今は村の間に通信ネットワークを構築しなければならない.通信手段は2種類あり、それぞれ敷設が必要な一般路線と衛星設備である.衛星設備の数は限られており、k村に衛星設備を配備するしかない.衛星設備を持つ村は互いに直接通信している.線路が敷設された村同士でも通信できる.衛星の配分は制限されない.どのように合理的に衛星を分配して線路を敷設して、2つの村の間が直接あるいは間接的に通信することができることを保証する前提の下で、線路を敷設する総長さは最も短いです.
構想:この問題を見ると最小生成木を思い出すべきだが、この問題が最小生成木の答えで出力されると衛星の存在を無視する.衛星はk個の連通成分であるk本の木を接続できるので、まずKruskalで最小生成木を作ってから、k-1本の辺権の最大の辺を削除すればいい.具体的には,n−k本の最小エッジを直接選択して同じ目的を達成することができる.具体的にKruskalアルゴリズムと証明する.
コード:

/*
2016.8.30 BulaBulaCHN
*/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct point
{
    int x,y;
}a[2005];
struct Edge
{
    int x,y;
    int val;
}eage[4004005];
int tot=0;
int cacl(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void add(int x,int y,int v)
{
    eage[++tot].x=x;
    eage[tot].y=y;
    eage[tot].val=v;
}
bool cmp(Edge a,Edge b) {return a.valint f[2005];
int findx(int x)
{
    int r=x;
    while(f[r]!=r)
        r=f[r];
    return r;
}
int n,k;
int top=0;
int tim=0;
double ans=0;
int main()
{
    freopen("line.in","r",stdin);
    freopen("line.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        if(i!=j) add(i,j,cacl(a[i],a[j]));
    for(int i=1;i<=n;i++) f[i]=i;
    sort(eage+1,eage+1+tot,cmp);
    while(1)
    {
        top++;
        int g1=findx(eage[top].x);
        int g2=findx(eage[top].y);
        if(g1!=g2)
        {
            f[g2]=g1;
            tim++;
            ans+=sqrt(eage[top].val);
            if(tim==n-k) break;
        }
    }
    printf("%.4llf",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

3.壁を塗る

問題の説明:今1列の壁を塗る必要があって、壁はn段に分けられて、お金を節約するために、科学者はその中のいくつかの段だけを塗ることを決定して、同時に美観のために、科学者は連続するm段の壁の中で少なくとも2つの壁を塗ることを要求して、今すべての壁を塗る費用を知っています.科学者はあなたに最小限の費用を求めてほしいと言った.
考え方:一目dp.まず、0枚目の壁と1枚目の壁が既に塗装されていると仮定することができるので、i枚目の壁より前の全ての壁セグメントの要求を満たし、かつ、塗装された最後の壁がi枚目、塗装された最後の2枚目の壁がi-j枚目であるという態様の最低コストをf[i][j]とすることができる.状態遷移方程式がある:f[i][j]=min(f[i-j][k])+a[i](ブラシの最後の壁がi番目のブロックであると仮定し、条件を満たすすべての状態を列挙する)
コード:

/*
2016.8.30BulaBulaCHN
*/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n,m;
int a[10005];
int f[10005][105];
int ans=0x3f3f3f3f;
int main()
{
    freopen("brush.in","r",stdin);
    freopen("brush.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    memset(f,0x7f,sizeof f);
    for(int i=2;i<=m;i++)
        for(int j=1;jfor(int i=m+1;i<=n;i++)
        for(int j=i-m+1;j<=i+1;j++)
    {
        for(int k=i-m;kfor(int i=n-m+1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        ans=min(ans,f[j][j-i]);
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

comの使用について.flajaxian.file uploaderのいろいろ

配列分割サブ配列と近接