HDU-2018多校7th-1011-Swordsman 附杜教fread代码

题意：

　　　背景是打怪升级的故事，有k个不同属性的初始的能力值，每只怪物也有相同个数的能力值，你只能放倒k个能力值都比怪物大的，每放倒一个怪物，都可以得到相应的k个能力值。

思路：

　　　根据k个能力值得到k个不同的排序，设立k个不同的指针从小到大开始移动，对满足被放倒的条件的属性进行标记，当某只monster的所有防御属性都被标记时，更新打怪者的能力值。

　　这里的移动操作，可以通过判断cnt是否更新来结束循环。而每次移动操作都使得指针跑到打怪者能力小于monster的位子。

　　自己在练习的时候想的思路有点不周全，我们先对k个能力单独排序，单独给能放倒的怪兽打标记，最后看标记个数是否等于k个。反例是：对某种属性值，你只有打败了A号怪物，才能通过得到的能力值打败其他怪物，而在另一种属性下，A好怪物不能被放倒，但其他怪物能被放倒，这就造成了误判。

代码：

//#include<bits/stdc++.h>

//#include<unordered_map>

//#include<unordered_set>

#include<functional>

#include<algorithm>

//#include<ext/rope>

#include<iomanip>

#include<climits>

#include <iostream>

#include<cstring>

#include<cstdlib>

#include<cstddef>

#include<stdio.h>

#include<memory>

#include<vector>

#include<cctype>

#include<string>

#include<cmath>

#include<queue>

#include<deque>

#include<ctime>

#include<stack>

#include<map>

#include<set>

#define fi first

#define se second

#define pb push_back

#define INF 0x3f3f3f3f

#define pi 3.1415926535898

#define lowbit(a)  (a&(-a))

#define lson l,(l+r)/2,rt<<1

#define rson (l+r)/2+1,r,rt<<1|1

#define Min(a,b,c)  min(a,min(b,c))

#define Max(a,b,c)  max(a,max(b,c))

using namespace std;

//using namespace __gnu_cxx;

typedef long long ll;

typedef pair<int,int> P;

typedef unsigned long long ull;

const ll LLMAX=2e18;

const int MOD=1e9+;

const int MAXN=1e6+;

namespace IO{

    #define BUF_SIZE 100000

    #define OUT_SIZE 100000

    #define ll long long

    //fread->read 

    bool IOerror=;

    inline char nc(){

        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;

        if (p1==pend){

            p1=buf; pend=buf+fread(buf,,BUF_SIZE,stdin);

            if (pend==p1){IOerror=;return -;}

            //{printf("IO error!\n");system("pause");for (;;);exit(0);}

        }

        return *p1++;

    }

    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}

    inline void read(int &x){

        bool sign=; char ch=nc(); x=;

        for (;blank(ch);ch=nc());

        if (IOerror)return;

        if (ch=='-')sign=,ch=nc();

        for (;ch>=''&&ch<='';ch=nc())x=x*+ch-'';

        if (sign)x=-x;

    }

    inline void read(ll &x){

        bool sign=; char ch=nc(); x=;

        for (;blank(ch);ch=nc());

        if (IOerror)return;

        if (ch=='-')sign=,ch=nc();

        for (;ch>=''&&ch<='';ch=nc())x=x*+ch-'';

        if (sign)x=-x;

    }

    inline void read(double &x){

        bool sign=; char ch=nc(); x=;

        for (;blank(ch);ch=nc());

        if (IOerror)return;

        if (ch=='-')sign=,ch=nc();

        for (;ch>=''&&ch<='';ch=nc())x=x*+ch-'';

        if (ch=='.'){

            double tmp=; ch=nc();

            for (;ch>=''&&ch<='';ch=nc())tmp/=10.0,x+=tmp*(ch-'');

        }

        if (sign)x=-x;

    }

    inline void read(char *s){

        char ch=nc();

        for (;blank(ch);ch=nc());

        if (IOerror)return;

        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;

        *s=;

    }

    inline void read(char &c){

        for (c=nc();blank(c);c=nc());

        if (IOerror){c=-;return;}

    }

    //fwrite->write

    struct Ostream_fwrite{

        char *buf,*p1,*pend;

        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}

        void out(char ch){

            if (p1==pend){

                fwrite(buf,,BUF_SIZE,stdout);p1=buf;

            }

            *p1++=ch;

        }

        void print(int x){

            static char s[],*s1;s1=s;

            if (!x)*s1++='';if (x<)out('-'),x=-x;

            while(x)*s1++=x%+'',x/=;

            while(s1--!=s)out(*s1);

        }

        void println(int x){

            static char s[],*s1;s1=s;

            if (!x)*s1++='';if (x<)out('-'),x=-x;

            while(x)*s1++=x%+'',x/=;

            while(s1--!=s)out(*s1); out('\n');

        }

        void print(ll x){

            static char s[],*s1;s1=s;

            if (!x)*s1++='';if (x<)out('-'),x=-x;

            while(x)*s1++=x%+'',x/=;

            while(s1--!=s)out(*s1);

        }

        void println(ll x){

            static char s[],*s1;s1=s;

            if (!x)*s1++='';if (x<)out('-'),x=-x;

            while(x)*s1++=x%+'',x/=;

            while(s1--!=s)out(*s1); out('\n');

        }

        void print(double x,int y){

            static ll mul[]={,,,,,,,,,

                ,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,

                100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};

            if (x<-1e-)out('-'),x=-x;x*=mul[y];

            ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;

            ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);

            if (y>){out('.'); for (size_t i=;i<y&&x3*mul[i]<mul[y];out(''),++i); print(x3);}

        }

        void println(double x,int y){print(x,y);out('\n');}

        void print(char *s){while (*s)out(*s++);}

        void println(char *s){while (*s)out(*s++);out('\n');}

        void flush(){if (p1!=buf){fwrite(buf,,p1-buf,stdout);p1=buf;}}

        ~Ostream_fwrite(){flush();}

    }Ostream;

    inline void print(int x){Ostream.print(x);}

    inline void println(int x){Ostream.println(x);}

    inline void print(char x){Ostream.out(x);}

    inline void println(char x){Ostream.out(x);Ostream.out('\n');}

    inline void print(ll x){Ostream.print(x);}

    inline void println(ll x){Ostream.println(x);}

    inline void print(double x,int y){Ostream.print(x,y);}

    inline void println(double x,int y){Ostream.println(x,y);}

    inline void print(char *s){Ostream.print(s);}

    inline void println(char *s){Ostream.println(s);}

    inline void println(){Ostream.out('\n');}

    inline void flush(){Ostream.flush();}

    #undef ll

    #undef OUT_SIZE

    #undef BUF_SIZE

};

using namespace IO;

template<class T>

inline void read(T &DataIn)

{

    DataIn=;    T Flag=;   char c=getchar();

    while(!isdigit(c)){ Flag|=c=='-'; c=getchar(); }

    while(isdigit(c)){ DataIn=DataIn*+c-''; c=getchar(); }

    DataIn= Flag? -DataIn: DataIn;

}

template<class T>

inline void write(T DataOut,char EndChar='\n')

{

    T lenth=,number[];

    if(DataOut==){ putchar(); return; }

    while(DataOut>){ number[++lenth]=DataOut%; DataOut/=;}

    for(int i=lenth;i>=;i--)    putchar(number[i]+);

    putchar(EndChar);

}

int a[],pos[];

struct node{

    ll hit[],exp[],id;

}b[MAXN];

int p[][MAXN];

inline bool cmp1(int x,int y){

    return b[x].hit[]<b[y].hit[];

}

inline bool cmp2(int x,int y){

    return b[x].hit[]<b[y].hit[];

}

inline bool cmp3(int x,int y){

    return b[x].hit[]<b[y].hit[];

}

inline bool cmp4(int x,int y){

    return b[x].hit[]<b[y].hit[];

}

inline bool cmp5(int x,int y){

    return b[x].hit[]<b[y].hit[];

}

int vis[MAXN];

int main()

{

    int T;  cin>>T;

    while(T--){

        int n,k,cnt=;

        read(n);read(k);

        //scanf("%d%d",&n,&k);

        for(int i=;i<k;i++)  read(a[i]);

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

            vis[i] = ;

            b[i].id=i;

            for(int j=;j<k;j++)

                read(b[i].hit[j]),p[j][i] = i;;

            for(int j=;j<k;j++)

                read(b[i].exp[j]);

        }

        pos[] = pos[] = pos[] =pos[] = pos[] = ;

        for(int i=; i<k; i++){

            if(i==) sort(p[],p[]+n,cmp1);

            else if(i==) sort(p[],p[]+n,cmp2);

            else if(i==) sort(p[],p[]+n,cmp3);

            else if(i==) sort(p[],p[]+n,cmp4);

            else if(i==) sort(p[],p[]+n,cmp5);

        }

        while(true){

                int c = cnt;

                for(int i=; i<k; i++){

                    while(pos[i] < n && b[p[i][pos[i]]].hit[i] <= a[i]){

                        int id =  p[i][pos[i]];

                        vis[id]++;

                        if(vis[id] == k){

                            cnt++;

                            for(int j=; j<k; j++){

                                a[j] += b[id].exp[j];

                            }

                        }

                        pos[i]++;

                    }

                }

                if(cnt==c){

                    break;

                }

        }

        //write(cnt);

        IO::println(cnt);

        for(int i=;i<k;i++)

            IO::print(a[i]),IO::print(i!=k-?' ':'\n');

    }

    return ;

}

FREAD in here

巴特西

HDU-2018多校7th-1011-Swordsman 附杜教fread代码

题意：

思路：

最新文章

热门文章