2019年5月9日試験問題解き報告

5437 ワード

2019年5月9日試験問題解き報告
私の考え
二百五を試験したが...やっぱり、**は**桶の中にいるべきだ.
全体的に今回の試験は比較的簡単で、最後の問題は私はどうして過ぎなかったのか分かりません.やはりあまりにljしました
T 1:多重リュックサック裸問題、何の装飾も必要ありません......T 2:接頭辞とT 3を求めます:簡単で貪欲で、私はただ50分だけあります
(ここでこの問題解きのレポートが終わるはずだと感じて、書くことがないようですqwq)
問題解たち.
多重リュックサック
(backpack.cpp/c/pas)
(1s/256M)
タイトルの説明
最大重量Wの荷物を積むリュックサックを提供します.今N種類の物品を提供します:i種類の物品に対して、全部でCi件の物品があります;各アイテムについて、重量はWi、価値はViです.リュックサックの中の物の総価値を最大にするロード方法を見つけます.
入力フォーマット(backpack.in)
1行目の2つの整数N,Wは、物品の種類とリュックサックの総負荷を表す.第2〜N+1行目は、1行当たり3つの整数Wi,Vi,Ciであり、第i種の物品の重量、価値及び数量を表す.
出力フォーマット(backpack.out)
1行のみ、整数Vは最大の総価値を表します.
サンプル入力
3 9 5 8 2 3 6 2 2 1 5
サンプル出力
14
データ範囲と制限
\(1<=N<=20, 0<=W<=1000\)\(1<=Wi<=100, 0<=Vi<=100, 0<=Ci<=100\)
構想
これは多重リュックサックの裸の問題で、直接テンプレートを出して使えばいいです.ここではバイナリ変換を使いました.
コード#コード#
#include
#include
#include
#include
#define N 50010
#define MAXN 1001
#define ll long long
using namespace std;

inline int read() {
    char c=getchar();
    int x=0,f=1;
    for(; !isdigit(c); c=getchar())if(c=='-')f=-1;
    for(; isdigit(c); c=getchar())x=x*10+c-48;
    return x*f;
}

ll f[N],v[MAXN],w[MAXN];

int main() {
    freopen("backpack.in","r",stdin);
    freopen("backpack.out","w",stdout);
    int n,W,wi,vi,ci,tot=0;
    n=read(),W=read();
    for(int i=1; i<=n; ++i) {
        wi=read(),vi=read(),ci=read();
        for(int j=1;; j<<=1) {
            if(ci=v[i]; --j)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
    cout<

ループシーケンス
(circulate.cpp/c/pas)
(1s/256M)
タイトルの説明
AliceとBobはゲームをしています:Aliceはまず2つの数(X)と(Y)((X<=Y))を与えます;Bobは順番に(X,X+1,X+2,...,Y−1,Y)を大数Sと書く.アリスは最後にSの首尾をつなぎ、輪にした.このとき、Bobは、Sの先頭から、後のL位からR位までの数字の和がどれくらいなのか知りたい.
入力フォーマット(circulate.in)
最初の行の4つの整数(X,Y,L,R)は、Aliceの2つの数字とBobが知りたい(L)位から(R)位までの数字の和を表します.
出力フォーマット(circulate.out)
1行のみで、L位からR位までの数字の和を表す整数M.
サンプル入力
10 11 4 12
サンプル出力
7
サンプル解釈
Bobは数字を1行の大数(S=1011)と書く.1つの輪を囲むと、4位から12位までが(1,1,0,1,1,1,1,0,1)であり、それらの和は(7)である.
データ範囲と制限
50%のデータに対して、L=1、X、Y、L、R<=1000;100%のデータに対して、Sの長さは10000以下、X、Y、L、R<=1億0,000,000万以下である.
構想
私たちはまずそのすべてのビットを分解して、それから接頭辞の和を求めることができて、1つの環なので、直接除算して更に型を取って多くの空間と多くの時間を消費しないで解答を得ることができます
コード#コード#
#include
#include
#include
#include
#define N 1010
#define MAXN 10100
using namespace std;

inline int read() {
    char c=getchar();
    int x=0,f=1;
    for(; !isdigit(c); c=getchar())if(c=='-')f=-1;
    for(;isdigit(c); c=getchar())x=x*10+c-48;
    return x*f;
}

int x,y,l,r;
int a[MAXN],s[MAXN],n=0,m,b[N];

int work(int x){
    if(x==0)return 0;
    int g=x/n;
    int r=x%n;
    return s[n]*g+s[r];
}

int main(){
    //freopen("circulate.in","r",stdin);
    //freopen("circulate.out","w",stdout);
    x=read(),y=read(),l=read(),r=read();
    for(int i=x;i<=y;i++){
        m=0;
        int tmp=i;
        while(tmp!=0)b[++m]=tmp%10,tmp/=10;
        for(int j=m;j!=0;j--)a[++n]=b[j];
    }
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i];//     
    }
    int lefted=work(l-1);
    int righted=work(r);
    cout<

マージゲーム
merge.cpp/c/pas
(1s/256M)
タイトルの説明
CindyとDanはゲームをしています.
最初CindyはN個の数を考え出して、それから彼女はこのN個の数を全部Danにあげました.
Danはこのグループの数を得ると、3つの数を選びます(3つ未満であれば全部選びます).Danはこれらの数を合わせて1つの数にし、その数を残りの数と一緒に置きます.Danは最後まで1つの数しか残っていません.
CindyはDanごとに得た数を横にメモし、彼女はこれらの数を合わせて今回のゲームの得点とした.彼女は1組の数に対して、Danが得ることができる最大の得点はいくらですか?
入力フォーマット
1行目の正の整数Nは、この数の個数を表す.2行目のN個の正の整数は、このN個の整数を表す.
出力フォーマット
可能な最大得点を表す1行1つの整数.
サンプル入力(merge.in)
4 3 1 5 6
サンプル出力(merge.out)
29
サンプル解釈
Danはまず(3,5,6)の3つの数を先に統合して,3+5+6=14を得ることができる.そして彼は残りの2つの数を合わせて1+14=15を得た.これで、総得点は最大の14+15=29となります.
データ範囲と制限
50%のデータに対して、N<=10は100%のデータに対して、N<=1000、すべての数は1000以下である.
構想
この問題はやはり簡単ですが、残念ながら私はやはり点数をつけました.
並べ替えは大きいものから小さいものまで最大のものを探して一緒に加えればいいです.
コード#コード#
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

inline int read() {
    char c=getchar();
    int x=0,f=1;
    for(; !isdigit(c); c=getchar())if(c=='-')f=-1;
    for(; isdigit(c); c=getchar())x=x*10+c-48;
    return x*f;
}

int n;
int a[1001];

bool cmp(int a,int b) {
    return a>b;
}

int main() {
    freopen("merge.in","r",stdin);
    freopen("merge.out","w",stdout);
    n=read(); 
    for(int i=1; i<=n; ++i)a[i]=read();
    sort(a+1,a+1+n,cmp);
    long long ans = 0;
    long long now = a[1];
    for(int i=2; i<=n; i+=2) {
        now+=a[i]+a[i+1];
        ans+=now;
    }
    printf("%d
",ans); fclose(stdin); fclose(stdout); return 0; }

転載先:https://www.cnblogs.com/loceaner/p/10840786.html