备孕百度之星-9月15日

猎人杀

#include<iostream>
#include<cstring>

using namespace std;
typedef long long ll;
inline ll read(){
    ll x=0;char ch;bool f=true;
    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
    for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
    return x;
}
int main( )
{    
    int T = read();
    while(T-- > 0){
        int t;
        int n = read();
        int bk = 0;//已经寄了的 
        int lang = -1;
        int tag[n];
        memset(tag, 0, sizeof(tag));//1表示寄了
        for(int i = 0; i < n; i++) {
            t = read();
            if(t == 1) lang = i;
        }  
        int kill[n][n];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++){
                kill[i][j] = read();
                kill[i][j]--; 
            } 
        int cur_l = 0;            
        //狼杀人
        while(tag[kill[lang][cur_l]] == 1) cur_l++;//找个活人 
        tag[kill[lang][cur_l]] = 1;
//        cout << "狼杀" << kill[lang][cur_l] + 1 << endl; 
        
        //死的猎人杀人 
        t = kill[lang][cur_l];
        bk++; 
        while((n-bk) > 2){
            //判断狼是否死
            if(tag[lang] == 1) break;//狼自杀 
            int in = 0; 
            while(tag[kill[t][in]] == 1) in++;//找个活人 
            tag[kill[t][in]] = 1;
            
//            cout << "猎人杀" << kill[t][in] + 1 << endl; 
            t = kill[t][in];
            if(tag[lang] == 1) break;//狼寄 
            bk++;
        }
        if(tag[lang] == 0){
            cout << "langren" << endl;
        }else{
            cout << "lieren" << endl;
        }
    } 
    return 0;
}

区别于前一篇博文发的，这个使用了快速读，一开始没有使用快速读，在马蹄集AC，换了HUD，结果就是卡常，换成快速读之后快了8倍左右，以后涉及大量读写的要用快速读写

二分

看不懂题目啊，又有知识点要恶补了

毒瘤数据结构题

一开始思路是红黑树的map，可以nlogn，看了题解发现维护两个0，O(N)

#include<iostream>
#include<cstring>

using namespace std;
typedef long long ll;
int nums[5000005];

inline ll read(){
    ll x=0;char ch;bool f=true;
    for(ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')f^=f;
    for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
    return x;
}
//快写
void write(int x) {
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
struct FastIO//输入挂
{
    static const int S=200;
    int wpos;
    char wbuf[S];
    FastIO():wpos(0){}
    inline int xchar()
    {
        static char buf[S];
        static int len=0,pos=0;
        if(pos==len) pos=0,len=fread(buf,1,S,stdin);
        if(pos==len) exit(0);
        return buf[pos++];
    }
    inline int read()
    {
        int s=1,c=xchar(),x=0;
        while(c<=32) c=xchar();
        if(c=='-') s=-1,c=xchar();
        for(;'0'<=c&&c<='9';c=xchar()) x=x*10+c-'0';
        return x*s;
    }
    ~FastIO()
    {
        if(wpos) fwrite(wbuf,1,wpos,stdout),wpos=0;
    }
}io;
int main( )
{	
	memset(nums, 0, sizeof(nums));
	int T = io.read();
	int n = T;
	int a,b;
	int x = 1, y = 2;//x在前 
	while(T-- > 0){
		a = io.read();
		b = io.read();
		if(a == 1){
			nums[b] = 1;
			if(nums[x] == 1)
				while(x <= n && nums[x] == 1)x++;
			if(x == y || nums[y] == 1){
				y++;
				while(y <= n && nums[y] == 1) y++;
			}
		}else{
			if(b == x){
				write(y);
			}else{
				write(x);
			}
			putchar('\n');
		}
	} 
    return 0;
}

hud真的太卡常了，换了最高效的快读才通过。然后通过马蹄集测了一下两种快读的效率，就差一点。。