codeforces Hello 2018(A-E)

A題

B題

C題

D題

E題

A題
标题:m%2 nの値を求める
mの範囲は1 e 8しかないので、nが30未満の範囲を見るだけでいいです
B題
标题:1つのツリーで、非リーフノードが3つ以上のリーフノードに接続されていなければ、Noを出力し、そうでなければYesを出力する
bfsかdfsでやってもいいですよ.一度遍歴してみてください.ここで注意したいのはdfsの中でreturnを落とさないようにすることですね.ローカルマシンでは正しい結果が出ることもありますが、コンパイルするときにwaが出るかもしれません.あるいは、木を建てる過程の再帰(ポインタ)が1つも書かれていないことを思い出したり、プログラムに問題がなく、正しい結果が出たりして、私が何を考えているのか知っているかもしれません.
C題
标题:レモン水、容量によって、価格が违います.Lリットル以上のレモン水を买うには、少なくとも使うお金が必要です.第i容量に対応した価格が与えられ,容量は2 i−1であり,各容量は任意に購入できる.
最初の考えは欲張りだったが、waが来て、それからまるでリュックサックのように感じて、範囲を見て、だめだと感じて、それから欲張りだった...考えは単価順に、できるだけ単価が少ないものを持って、l容量を超えたら、現在の値を記録して、それから毎回超えて、値を記録して、最小は結果を記録したwa、、、最後にソート関数の問題であることに気づきました???

bool cmp(node a1,node a2)
{
    if(abs(a1.per-a2.per).v>a2.v;
    return a1.per.per;
}

単価が同じなら、体積によって大通りから小さく、そうでなければ単価によって小さいから大きいまで
単価が同じ考えを除けばAです...
もう一つのアイデアはバイナリに関係していて、巧みな感じがしますね~

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
const double eps = 1e-6;
const ll inf = 1e18;
ll a[100];
int main()
{
    int n,l;
    scanf("%d %d",&n,&l);
    for(int i=0;iscanf("%I64d",&a[i]);
    for(int i=1;i1]*2ll);
    for(int i=n-2;i>=0;i--)
        a[i]=min(a[i],a[i+1]);
    for(int i=n;i<=30;i++)
        a[i]=a[i-1]*2ll;
    ll ans = 0;
    int i=0;
    while(l)
    {
        if(l&1) ans = ans + a[i];
        i++;
        if(ans>a[i]) ans = a[i];
        l=l/2;
    }
    if(a[i]printf("%I64d
",ans);
    return 0;
}

D題
題意:n個の問題があり、時間制限はTであり、各問題のaiとtiを与え、tiは消費する時間を表す.T時間内にk個の問題が解決すると、m=解決の問題となる.ai>=k、の数量はmを求めて最大でいくらです.
何度もタイトルを読み始めても分からなかった....これは、優先順位キューであり、キューに格納される問題は解決され、ai>=q.size()である.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
const int maxn = 2*100000+10;
struct node {
    int ai,ti,id;
    operator < (const node&temp)const {
        return ai>temp.ai;
    }
}a[maxn];
priority_queueq;
bool cmp(node a1,node a2)
{
    return a1.tiint main()
{
    int n,t;
    scanf("%d %d",&n,&t);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&a[i].ai,&a[i].ti);
        a[i].id = i;
    }
    sort(a+1,a+n+1,cmp);
    int i;
    for(i=1;i<=n;i++)
    {
        t-=a[i].ti;
        if(t<0) break;
        q.push(a[i]);
    }
    t+=a[i].ti;
    while(!q.empty())
    {
        node a1 = q.top();
        if(a1.aielse break;
    }
    for(;i<=n;i++)
    {
        int temp = t-a[i].ti;
        if(temp<0) break;
        if(a[i].ai1)) continue;//      ，       
        q.push(a[i]);
        t=temp;
        node a1 = q.top();
        if(a1.aiprintf("%d
",q.size());
    printf("%d
",q.size());
    if(q.size()>=1){
        node a1 = q.top();
        printf("%d",a1.id);q.pop();
        while(!q.empty())
        {
            a1 = q.top();
            printf(" %d",a1.id);
            q.pop();
        }
    }
    printf("
");
    return 0;
}

E題
标题:x=0001111 b,y=00010011 b,z=0100101 bの3つの操作があり、優先度が高いから問題までそれぞれ!,&,|,もう一つ()は,n個の値を与え,x,y,zに対してどのような操作をすれば与えられた値になるかを尋ね,式を出力する.
これはdp F[i]:最後の操作は!T[i]:最後のステップ操作は&E[i]:最後のステップ操作は|状態遷移:F[i]はF[i^255]F[i]に移行可能T[i]T[i]に直接移行可能E[i]E[i]に移行可能F[i]に移行可能(((()で読めなくても大丈夫、直接コードを見て、コードがはっきり書いてある.

/*
by:sllsll
*/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define mem(a,b) memsert(a,b,sizeof(a))
#define rep(a,b) for(int i=(a);i
const int maxn = 1e5+10;
string F[maxn],T[maxn],E[maxn];
int x = 15,y=51,z=85;
int flag=0;
void fz(string&a,const string& b)
{
    if(a=="")
    {
        flag=1;
        a=b;return;
    }
    int size1 = a.length(),size2 = b.length();
    //     
    if(size1>size2) a = b,flag=1;
    else if(size1==size2)
        if(a>b)a=b,flag=1;

}
void dp()
{
    F[x]='x',F[y]='y',F[z]='z';
    while(1)
    {
        flag=0;
        rep(0,256)
            if(F[i]!="")
                fz(F[i^255],'!'+F[i]);
        for(int i=0;i<256;i++)
            if(F[i]!=""){
                fz(T[i],F[i]);
                for(int j=0;j<256;j++)
                    if(T[j]!="")
                        fz(T[i&j],F[i]+"&"+T[j]);
                }
        for(int i=0;i<256;i++)
            if(T[i]!=""){
                fz(E[i],T[i]);
                for(int j=0;j<256;j++)
                    if(E[j]!="")
                        fz(E[i|j],T[i]+"|"+E[j]);
            }
        for(int i=0;i<256;i++)
        if(E[i]!=""){
                fz(F[i],"("+E[i]+")");
        }
    if(!flag) break;
    }
}
int d[10]={128,64,32,16,8,4,2,1};
int change(string str)
{
    int ans = 0;
    for(int i=0;i<8;i++)
    {
        if(str[i]=='1') ans+=d[i];
    }
    return ans;
}
int main()
{
    dp();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        string str;
        cin>>str;
        int n=change(str);
        cout<return 0;
}

ps:一時変数を参照型パラメータとする場合はconstを付ける
もう一つの方法は最小生成ツリー転送であり,この差は多くなく,まずすべての値を計算し,ここのwhile(1)をwhile(!q.empty()に変更し,その後同じ転送である.