WAhaha_hnu(zoj 2010 oct月試合)

公式解題報告 http://blog.watashi.ws/1515/zojmonthly1010/
 
A題 签到问题,


View Code

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<string>



using namespace std;



const int N = 101100;

char str[N];





bool isch( char ch ){

    if( (ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z') )

        return true;

    return false;

}

string get_str( int x ){

    

    string tmp;

    char sa[1010];    

    int len = 0;

    while( x ){

        sa[len++] = x%10 + '0'; x /= 10;

    }

    for(int i = len-1; i >= 0; i-- )

        tmp += sa[i];

    return tmp;

}

int main(){

    while( gets( str) ){

        if( strcmp( str, "EOF" ) == 0 ) break; 



        //printf("str = %s", str );    

        int len = strlen(str), n = 0, i = 0;

        string s;    

        

        while( i < len )    

        {

            if( isch( str[i] ) ){



                s += str[i];



                int t = i+1;

                while( isch(str[t]) && (t<len) ) ++t;

                t--;



                if( t-i >= 1 ){

                    if( t-i >= 2 )    

                        s += get_str( t-i-1 );

                    s += str[t];    

                }    

                i = t+1;    

            }    

            else    s += str[i++];

        }

        printf("%s
", s.c_str() );    

    }

    return 0;

}

 
B題 最初は問題の意味を間違えて理解していたので、最後まで油断していました~~
横断をx,縦断をy,クローンをaとすると,総分数n,および操作回数mに対して共有する.
　　　　2*x*(y+1) + a = n
　　　　x + y + a = m 
n,mはいずれも比較的大きいが,x*y<=n=>x<=sqrt(n)‖y<=sqrt(n)
したがって,x,yが対称であるため,x,yからsqrt(n)をそれぞれ列挙することによって結果を得ることができ,1サイクルで得ることができる.
また,以上の2式の成立条件はx>0を前提としているので,x=0の場合は特判,n<=mの場合も特判とする.


View Code

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#define MIN(a,b) (a)<(b)?(a):(b)

typedef long long LL;



int main(){



    int n, m, T;

    scanf("%d", &T);



    while( T-- )

    {

        scanf("%d %d", &n,&m);

        if( n <= m ){

            printf("-1
");

            continue;

        }    

        if( n-1 == m ){

            printf("0
");

            continue;

        }    

        bool flag = false;

        int res = m+1;

        int Max = sqrt(n)+1;    

        for(int x = 0; x <= Max; x++ )

        {

            int ta = n-m-x, tb = 2*x-1;    

            if( ta%tb == 0 ){

                int y = ta/tb;

                if( (y>=0) && (x+y<=m) ){    

                    flag = true;    

                    res = MIN( res, m-x-y );    

                }    

            }

            ta = n-m+x; tb = 2*x+1;

            if( ta%tb == 0 ){

                int y = ta/tb;

                if( (y >=0) && (x+y<=m) ){

                    flag = true;

                    res = MIN( res, m-x-y);

                }

            }

        }    

        if( flag )  printf("%d
", res );

        else    printf("-1
");

    }

    return 0;

}

 
E问题看题后第一眼想到DP,但时间复雑度不能接受,然后没管管了,振り返って考えてみると、贪欲は过ごすことができるはずだと思った...学べば学ぶほど愚かになった~~~
タイトルはトラップ順に限定されず、トラップをD順に並べた後、順次処理し、累積時間T<=Diであれば取り壊し、そうでなければ失血し、この場合[1,i]区間を選択する
中時間消費が最も大きく、ここでは優先キューを使用してメンテナンスします.


View Code

#include<iostream>

#include<cstdio>

#include<cstring> 

#include<queue>

#include<algorithm>

using namespace std;

const int N = 25010;



pair<int,int> p[N];



int n, k;



int main(){

    while( scanf("%d%d", &n,&k) != EOF)

    {

        for(int i = 0; i < n; i++)

            scanf("%d%d", &p[i].second,&p[i].first );

        sort( p, p+n );

        int T = 0, hp = 0;

        priority_queue< int > Q;

        

        for(int i = 0; i < n; i++ ){

            T += p[i].second;

            Q.push( p[i].second );

            while( T > p[i].first ){

                T -= Q.top(); Q.pop();

                hp++;

            }    

        }

        if( hp < k ) printf("%d
", hp );

        else printf("-1
");

    }

    return 0;    

}

 
I題じòぴé(′▽`)∞は、試合中に問題を見る能力がまだ足りないので、問題を割引上の点が隣接する直接距離と見間違えた.
折れ線の全長を計算し、点間距離を求め、始点からシミュレーション検索を開始すると結果が得られます.