アルゴリズムコンテストステップガイド0 x 08まとめ練習(下)

数の進数変換
1つの数字を1つの進数から別の進数に変換するプログラムを作成します.
ここには62個の異なる数ビット{0−9,A−Z,a−z}がある.
入力フォーマットの最初の行は、次の行数を表す整数を入力します.
次に、各行には3つの数字が含まれています.まず、入力(10進)で、次に出力(10進)で、最後に入力で表される入力数字で、数字の間にスペースが隔てられています.
入力進数と出力進数は2～62の範囲内です.
(10進数で)A=10,B=11,…,Z=35,a=36,b=37,…,z=61(0-9は依然として0-9を表す).
出力フォーマットは、各進数変換のセットに対して、プログラムの出力が3行で構成されます.
最初の行には2つの数字が含まれています.まず、入力進数(10進数)、次に入力進数で表される入力数字です.
2行目には2つの数字が含まれています.まず、出力進数(10進数)、次に出力進数で表される入力数字です.
3行目の空白行.
同じ行の数字はスペースで区切られています.
入力サンプル例:8 62 2 abcdefghiz 10 16 1234567890123459012345678901234556789012345678901234556789016 35 3 A 0 C 9275 C 0 DBF 3 B 8 A CBC 5 F 96 CE 3 F 0 AD 2 35 23 333 YMHOUE 8 JPLT7 OX 6 K 9 FYCQ 8 A 23 49 946 B 9 AA02 MI 37 E 3 D 3 MMJ 4 G 7 BL 2 F 05 61 1 VbDkSIMJJJJJJRgAdlUfcaWj 61 5 dl 9 MDSWqwHDnToKcsWES 5 10 42444444444444444444444444444444444444444444444444444444444444444444444444444441001444012213024020212333403111042120022123030330出力サンプル:62 abcdefghiz 2 11011100000100010111110010010110011111001001100011010010001
10 1234567890123456789012345678901234567890 16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2 35 333YMHOUE8JPLT7OX6K9FYCQ8A
35 333YMHOUE8JPLT7OX6K9FYCQ8A 23 946B9AA02MI37E3D3MMJ4G7BL2F05
23 946B9AA02MI37E3D3MMJ4G7BL2F05 49 1VbDkSIMJL3JjRgAdlUfcaWj
49 1VbDkSIMJL3JjRgAdlUfcaWj 61 dl9MDSWqwHjDnToKcsWE1S
61 dl9MDSWqwHjDnToKcsWE1S 5 42104444441001414401221302402201233340311104212022133030
5 42104444441001414401221302402201233340311104212022133030 10 1234567890123456789012345678901234567890
これは非常に基礎的な進数変換問題で、A進数->B進数ですが、高精度で、一般的な思考はA->10、それから10->Bですが、この問題のやり方は一歩で着くことができます.A->B、10->B進数を振り返ってみましょう.私たちはans.push_back(a%B)a/=B、これは私たちが10進数に基づく除法ですが、A進数に関するaの除法を実現できれば、私たちは一歩で着くのではないでしょうか.~.~、コードを見てみましょう.

#include
#include
#include
#include

using namespace std;

inline int get(char ch)
{
    if(ch>='A'&&ch<='Z') return ch-'A'+10;
    else if(ch>='a'&&ch<='z') return ch-'a'+36;
    return ch-'0';
}

inline char out(int num)
{
    if(num<=9&&num>=0) return num+'0';
    else if(num>=10&&num<=35) return num-10+'A';
    else return num-36+'a';
}

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    int T;
    cin>>T;

    while(T--)
    {
        int a1,a2;
        string s1,s2;
        cin>>a1>>a2>>s1;
        vector<int> v;
        for(auto ch:s1)
            v.push_back(get(ch));
        
        reverse(v.begin(),v.end());
        while(v.size())
        {
            int t=0;
            for(int i=v.size()-1;i>=0;i--)
            {
                t=a1*t+v[i];
                v[i]=t/a2;
                t%=a2;
            }
            s2.push_back(out(t));
            while(v.size()&&v.back()==0) v.pop_back();
        }
        reverse(s2.begin(),s2.end());
        cout<<a1<<" "<<s1<<endl<<a2<<" "<<s2<<endl;
        puts("");
    }

    return 0;
}

曲芸の牛
農民ジョンのN頭乳牛(番号1...N)は逃げてサーカス団に入る計画で、サーカスの練習をすることにした.
乳牛たちは非常に創意的ではなく、雑技の演技をしただけです.
畳羅漢、演技の時、乳牛たちはお互いの体に立って、高い垂直な積み重ねを形成しました.
乳牛たちは、この積み重ねの中で自分が置かなければならない位置の順序を見つけようとしている.
このN頭の乳牛のどれもが自分の重さWiと自分の強さSiを持っている.
1頭の牛が支えられない可能性は、頭のすべての牛の総重量(自分を含まない)から体の強さを差し引いた値に依存し、現在はこの数値をリスク値と呼び、リスク値が大きいほど、この牛が耐えられない可能性が高い.
あなたのタスクは、すべての乳牛のリスク値の最大値ができるだけ小さくなるように、乳牛のソートを決定することです.
フォーマットの最初の行に整数Nを入力し、乳牛の数を表します.
次に、N行目は、牛の重量および強壮度を表す2つの整数を入力し、i行目はi頭牛の重量Wiおよびその強壮度Siを表す.
出力フォーマットは、最大リスク値の最小可能値を示す整数を出力します.
データ範囲1≦N≦50000,1≦Wi≦10000,1≦Si≦10000000入力サンプル:3 103 2 5 3出力サンプル:2
あの王のゲームに似ています.私たちは強い+重いステーキの順番でいいです.

#include
#include
#include

#define ll long long
#define pll pair

using namespace std;

const int N=50010;

pll cows[N];
int n;

bool CMP(const pll &a,const pll &b)
{
    return a.first+a.second<b.first+b.second;
}
int main(){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&cows[i].first,&cows[i].second);
    
    sort(cows+1,cows+n+1,CMP);
    ll temp=0;
    ll res=-100000000000;

    for(int i=1;i<=n;i++)
    {
        res=max(res,temp-cows[i].second);
        temp+=cows[i].first;
    }

    printf("%lld
",res);
    

    return 0;
}

最大和
整数を含む2次元行列が与えられ、サブ長方形は、アレイ全体にわたって任意のサイズ1*1以上の連続サブアレイである.
長方形の合計は、長方形内のすべての要素の合計です.
この問題では,最大和を持つサブ矩形を最大サブ矩形と呼ぶ.
たとえば、次の配列があります.
0-2-7-70 9 2-6 2-4 1-4 1-18 0-2最大サブ矩形:
9 2-4 1-18最大15を持ちます.
入力フォーマット入力には、N*Nの整数配列が含まれます.
最初の行には、正方形の2次元配列のサイズを表す整数Nのみが入力されます.
2行目から、スペースと改行で区切られたN 2個の整数、すなわち2次元配列中のN 2個の要素を入力し、入力順は2次元配列の1行目から下へ、同じ行のデータは左から右へ入力します.
配列内の数値は[-127127]の範囲内に保持されます.
出力フォーマットは、最大サブ長方形の合計を表す整数を出力します.
データ範囲1≦N≦100入力サンプル:4 0-2-7 0 9 2-6 2-41-41-1
8 0-2出力サンプル:15
この問題は最長男序和の2次元バージョンで、1次元は暴力で、1次元はDPでいいhhで、何も言うことはありません.コードを見てみましょう.

#include
#include
#include
#include

using namespace std;

const int N=110;

int g[N][N];
int n;

int main(){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    cin>>n;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>g[i][j];
            g[i][j]+=g[i-1][j];
        }
    
    int res=INT_MIN;

    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
        {
            int last=0;
            for(int k=1;k<=n;k++)
            {
                last=max(last,0)+g[i][k]-g[j][k];
                res=max(res,last);
            }
        }

    cout<<res<<endl;
    return 0;
}

タスク#タスク#
今日ある会社はMつの任務を完成しなければならない.
各タスクには、対応する難易度レベルとタスクの完了に要する時間があります.
i番目のタスクの難易度レベルはyiで、タスクを完了するのにxi分かかります.
企業がこのタスクを完了すると、(500*xi+2*yi)ドルの収入が得られます.
同社にはN台の機器があり、各機器には最長稼働時間とレベルがある.
タスクに要する時間がマシンの最長稼働時間を超えると、マシンはこのタスクを完了できません.
タスクの難易度がマシンのレベルを超えると、マシンは次のタスクを完了できません.
各機械は1日に1つの任務しか完成できない.
各任務は1台の機械でしか完成できない.
今日完了できるタスクの数を最大化できるように、タスク割り当てスキームを設計してください.
多くの解決策があれば、利益が最も高いものを選びたいと思っています.
入力フォーマット入力には、いくつかのテスト例が含まれます.
各試験例について、第1行は、機械数およびタスク数を表す2つの整数NおよびMを含む.
次のN行は、各行に2つの整数xi,yiを含み、それぞれマシンの最長稼働時間とマシンレベルを表す.
次にM行、各行には2つの整数xi,yiが含まれ、それぞれタスクの完了に要する時間とタスクの難易度レベルを表します.
出力フォーマットは、各テスト・インスタンスについて、会社が今日完了できる最大タスク数と収益を表す2つの整数を出力します.
データ範囲1≦N,M≦100000,0≦yi≦100入力サンプル:1 2 100 3 100 2 100 1出力サンプル:1 50004
贪心策略:第一キーワードを第一キーワードとし、第二キーワードを第二キーワードとしてランキングし、本当に何も言うことはありません.日焼け止めの问题に似ています.基操hh、第二キーワードは局面を変えることができないので、せいぜい100しかありません.~

#include
#include
#include
#include

#define pii pair
#define ll long long

using namespace std;

const int N=100010;

pii mach[N],task[N];
int n,m;

inline int calc(const pii &p)
{
    return 500*p.first+2*p.second; 
}

int main(){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)
            cin>>mach[i].first>>mach[i].second;
        for(int i=1;i<=m;i++)
            cin>>task[i].first>>task[i].second;
        sort(mach+1,mach+n+1);
        sort(task+1,task+m+1);
        multiset<int> s;
        ll res=0,cnt=0;
        for(int i=m,j=n;i>=1;i--)
        {
            while(j>=1&&task[i].first<=mach[j].first) s.insert(mach[j--].second);
            auto it=s.lower_bound(task[i].second);
            if(it!=s.end())
            {
                res+=calc(task[i]);
                s.erase(it);
                cnt++;
            }
        }
        cout<<cnt<<" "<<res<<endl;    
    }

    return 0;
}