lp70295 整数校验器

细节题,要注意单独判断只有一个负号,形如“-”的情形。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

__int128 l,r;
char ch[200005];
int init(){
	cin>>ch+1;
	int n=strlen(ch+1);
	__int128 nw=0;
	bool bo=1;
	if(ch[1]=='-'){
		if(n==1){
			return 1;
		}
		for(int i=2;i<=n;++i){
			if(i==2&&ch[i]=='0'){
				return 1;
			}
			nw*=10;
			nw+=ch[i]-'0';
			if(-nw<l||-nw>r){
				return 2;
			}
		}
		return 0;
	}else{
		for(int i=1;i<=n;++i){
			if(i==1&&n>1&&ch[i]=='0'){
				return 1;
			}
			nw*=10;
			nw+=ch[i]-'0';
			if(nw<l||nw>r){
				return 2;
			}
		}
		return 0;
	}
}
int main(){
	long long L,R;
	int T;
	scanf("%lld%lld%d",&L,&R,&T);
	l=L,r=R;
	while(T--){
		printf("%d\n",init());
	}
	return 0;
}

CF1131

这么早的CF已经很少见了,不过我还是大力掉分。
我好菜啊.jpg


CF1131A
观察题意,随便推个式子提交就AC了。
打卡题。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int a,b,c,d,ans=0;
void init(){
	scanf("%d%d%d%d",&a,&b,&c,&d);
	ans=a+b*2+c+d*2+std::abs(a-c)+4;
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1131B
一道比较简单的题,但是如果脑残了会非常难。
反正我脑残以后是瞎jb写了二十七个特判死活PP不了。
当然仔细理解题意会发现还是比较简单的——当且仅当上一个的终止状态是平局态的时候,答案会有额外的统计。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n,a[100005],b[100005],ans=1;

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",&a[i],&b[i]);
		ans+=max(0,min(a[i],b[i])-max(a[i-1],b[i-1])+1);
		if(a[i-1]==b[i-1]){
			--ans;
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1131C
比B简单,普通构造题。
第一个直观的感觉是从小到大排列,但是仔细想想觉得那样不一定更优。
所以考虑到FJ省冬令营ZZQ讲的构造技巧,可以上一个奇偶排序。
于是AC此题。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n,a[100005];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i+=2){
		printf("%d ",a[i]);
	} 
	for(int i=n;i>=1;--i){
		if(!(i&1)){
			printf("%d ",a[i]);
		}
	}
}
int main(){
	init();
	return 0;
}


CF1131D
一道细节题,车站分级弱化版。
如果没有等于号,直接拓扑排序就可以通过。
但是等于号比较蛋疼。
会发现等于号得到的东西都是相同等级的,所以可以考虑用并查集维护。
两个坑点:首先要考虑记录访问过的点的次数来判是否无解,因为可能存在一个独立的环。
然后更新答案应该要按照最后一个更新,而非第一个。这是由这个解法的基本特性,也就是解集是所有约束条件的并集这一特性决定的。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n,m,in[2005];
char ch[1005][1005];

int f[2005];
inline int fa(int X){
	return f[X]==X?X:f[X]=fa(f[X]);
}
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	f[X]=Y;
}
bool mp[2005][2005];
queue<int> q;
bool vis[2005];
int ans[2005];
inline bool srt(){
	for(int i=1;i<=n+m;++i){
		if(!in[i]){
			q.push(i);
			ans[i]=1;
			vis[i]=1;
		}
	}
	int cnt=0; 
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		++cnt;
		for(int i=1;i<=n+m;++i){
			if(mp[p][i]){
				if(!in[fa(i)]){
					return 0;
				}else{
					--in[fa(i)];
					if(!in[fa(i)]){
						q.push(fa(i));
						ans[fa(i)]=min(ans[p]+1,ans[fa(i)]);
					}
				}
			}
		}
	}
	return cnt==n+m;
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		std::cin>>ch[i]+1;
	}
	for(int i=1;i<=n+m;++i){
		f[i]=i,ans[i]=0x3f3f3f3f;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(ch[i][j]=='<'){
				mp[i][n+j]=1;
			}
			if(ch[i][j]=='>'){
				mp[n+j][i]=1;
			}
			if(ch[i][j]=='='){
				uni(i,n+j);
			}
		}
	}
	for(int i=1;i<=n+m;++i){
		if(fa(i)!=i){
			for(int j=1;j<=n+m;++j){
				mp[fa(i)][j]|=mp[i][j];
				mp[i][j]=0;
			}
			for(int j=1;j<=n+m;++j){
				if(mp[j][i]){
					mp[j][fa(i)]=1;
					mp[j][i]=0;
				}
			}
		}
	}
	for(int i=1;i<=n+m;++i){
		for(int j=1;j<=n+m;++j){
			if(mp[i][j]){
				++in[j];
			}
		}
	}
	if(!srt()){
		puts("No");
		return;
	}else{
		puts("Yes");
		for(int i=1;i<=n;++i){
			printf("%d ",ans[fa(i)]);
		}
		puts("");
		for(int i=n+1;i<=n+m;++i){
			printf("%d ",ans[fa(i)]);
		}
	}
	
	
}
int main(){
	init();
	return 0;
}


CF1131F
这道题和D题有一点神似。
我们维护每一个已经弄好的连续块的左端点和右端点,每次访问到这个块就直接连接到它的父亲。
这个过程用并查集完成,使得可以直接搜索到整个块的端点。每一次直接把前一个块接在后一个块的左边就好了。
把每个连接记录一下最后输出即可。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

struct ee{
	int v;
	int nxt;
}e[300005];
int h[150005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int n,l[150005],r[150005];
int f[150005];
inline int fa(int X){
	return X==f[X]?X:f[X]=fa(f[X]);
}
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	f[X]=Y;
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		l[i]=r[i]=i,f[i]=i;
	}
	int a,b;
	for(int i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		a=fa(a),b=fa(b);
		add(r[a],l[b]);
		uni(a,b);
		l[b]=l[a];
	}
	a=l[fa(1)],b=0;
	printf("%d ",a);
	for(int i=1;i<n;++i){
		for(int j=h[a];j;j=e[j].nxt){
			if(e[j].v!=b){
				printf("%d ",e[j].v);
				b=a,a=e[j].v;
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp2044 NOI2012 随机数生成器

我们不妨将原式递归展开,可以得到形如此的式子:
$$f_{n}=a^nf_{0}+\frac{(a^{n}-1)c}{a-1}$$
对于这个式子的值,我们看似可以上一个快速幂直接求得。
然而仔细观察上式的情况,发现如果出现了奇妙的模数时,\(a-1\)是不一定有逆元的!
这就很令人难受了。
我们找到原来的问题,我们不得不求下述式子的值:
$$f_{n}=a^nf_{0}+\sum_{i=0}^{n-1}a^ic=a^nf_{0}+(\sum_{i=0}^{n-1}a^i)c$$
求值的最大障碍是这个式子:
$$\sum_{i=0}^{n-1}a^i$$
将这个式子分奇偶讨论后递归求解。
我们令:
$$u_{x}=\sum_{i=0}^{x-1}a^i$$
若是偶数,则有:
$$u_x=\sum_{i=0}^{\frac{x-1}{2}}a^i+a^{\frac{x+1}{2}} (\sum_{i=0}^{\frac{x-1}{2}}a^i)$$
即,
$$u_x=(a^{\frac{x+1}{2}}+1)u_{\frac{x-1}{2}}$$
若是奇数,则只需将第一项单独计算。
这样就可以在对数复杂度内对式子求解了。
另外,考虑到模数的数据范围,我们需要使用一种被称为「龟速乘」,也就是「快速幂」在乘法意义上的等同的操作,使得不会出现乘法,也就不会爆范围。

#include<iostream>
#include<cstdio>

long long MOD,a,c,x0,n,g;
//必须注意,不能重载一个全部是标准型的运算符。 
inline long long mlt(long long A,long long X){
	long long BS=A,RT=0,CNT=X;
	while(CNT){
		if(CNT&1){
			RT+=BS;
			RT%=MOD;
		}
		CNT>>=1;
		BS+=BS;
		BS%=MOD;
	}
	return RT;
}
inline long long pw(long long A,long long X){
	long long BS=A,RT=1,CNT=X;
	while(CNT){
		if(CNT&1){
			RT=mlt(RT,BS)%MOD;
		}
		CNT>>=1;
		BS=mlt(BS,BS)%MOD;
	}
	return RT;
}
inline long long calc(long long X){
	if(X==2){
		return (a+1)%MOD;
	}
	if(X==1){
		return 1;
	}
	if(X&1){
		return (pw(a,X-1)+calc(X-1))%MOD;
	}
	return mlt((pw(a,(X+1)>>1)+1),calc(X>>1));
}
void init(){
	scanf("%lld%lld%lld%lld%lld%lld",&MOD,&a,&c,&x0,&n,&g);
	printf("%lld",((mlt(pw(a,n),x0)+mlt(calc(n),c))%MOD)%g);
}

int main(){
	init();
	return 0;
}

lp5079 Tweetuzki 爱伊图

看似是一道暴力模拟题,实际上是一个技巧性模拟题。
我们注意到,对于除了2和5以外的所有的数,它们的每一列的#数量都是不同的,故而我们可以用1代表”#”,0代表”.”,然后跑一遍求和即可。
对于2和5,我们特殊处理,暴力扫描即可。

#include<iostream>
#include<cstdio>
#include<algorithm>

char lst[12][100005];
int lst2[100005][12];
int cnt[100005];
int r,c;

inline bool cmp(int A,int B){
	return A>B;
}

void init(){
	scanf("%d%d",&r,&c);
	for(int i=1;i<=r;++i){
		for(int j=1;j<=c;++j){
			std::cin>>lst[i][j];
		}
	}
	for(int i=1;i<=r;++i){
		for(int j=1;j<=c;++j){
			lst2[j][i]=lst[i][j]=='#'?1:0;
		}
	}
	for(int i=1;i<=c;++i){
		std::sort(lst2[i]+1,lst2[i]+1+r,cmp);
	}
	for(int i=1;i<=c;++i){
		for(int j=1;j<=r;++j){
			cnt[i]+=lst2[i][j];
		}
	}
	int cnt1=0,cnt2=0,cnt3=0;
	for(int i=1;i<=c;++i){
		if(!cnt[i]){
			cnt1=cnt2=cnt3=0;
		}else{
			cnt1=cnt[i],cnt2=cnt[i+1],cnt3=cnt[i+2];
			if(cnt1==5&&!cnt2){
				printf("1");
			}else{
				if(cnt1==4&&cnt2==3&&cnt3==4){
					bool bo=0;
					for(int j=1;j<=r;++j){
						if(lst[j][i]=='.'&&lst[j][i+1]=='.'&&lst[j][i+2]=='#'){
							bo=1;
						}else if(lst[j][i]=='#'&&lst[j][i+1]=='.'&&lst[j][i+2]=='.'){
							if(bo){
								printf("2");
							}else{
								printf("5");
							}
							break;
						}
					}
				}else if(cnt1==3&&cnt2==3&&cnt3==5){
					printf("3");
				}else if(cnt1==3&&cnt2==1&&cnt3==5){
					printf("4");
				}else if(cnt1==5&&cnt2==3&&cnt3==4){
					printf("6");
				}else if(cnt1==1&&cnt2==1&&cnt3==5){
					printf("7");
				}else if(cnt1==5&&cnt2==3&&cnt3==5){
					printf("8");
				}else if(cnt1==4&&cnt2==3&&cnt3==5){
					printf("9");
				}else if(cnt1==5&&cnt2==2&&cnt3==5){
					printf("0");
				}
				i+=2; 
			}
		}
	}
}

int main(){
	init();
	return 0;
}

lp2540 NOIP2015 斗地主增强版

首先,我们注意到花色对于斗地主不会造成任何影响,所以我们可以忽视掉花色这个信息。
然后,我们将剩余的信息,依据数码的从小到大储存。
然后我们可以注意到,对于一种出牌方式,调整一些牌组的出牌顺序对答案并不会造成影响。
并且,散牌似乎具有贪心的性质。看起来如果能出三带二那么出三带一就不会更优,如果能出四带二那出三带二就不会更优。
对于顺子的情况是一个例外,因为如果能出顺子的话,可能存在一种情况,使得不出顺子比出顺子更优;亦有可能将一个顺子出一部分会更优。故而对于顺子应该爆搜判定。
总结起来就是:爆搜出顺子,贪心出散牌。
但是仔细考虑,我们可以发现,这种贪心是一种想当然的对正确答案的近似。这事实上仅因为四不可带一这一性质。
故而,对于4 4 1 2的情况,用上述的贪心得出的答案应当是3,然而事实上只需2即可。
但是,前面仍然有一个结论是正确的——也就是,出牌顺序不对答案造成影响。又考虑到,数码的顺序其实仅对顺子而言有意义。
所以我们可以仅储存,数量为k的数码有多少种,从而可以用5^13的空间复杂度预处理每一种散牌的状态。
但是如果这么做的话会发现连样例二都过不了。这事实上是因为,暴力搜索散牌的时间复杂度是完全不可接受的。
考虑到状态数极少,可以记忆化搜索来完成预处理。
用f[i][j][k][l]表示,有i个1,j个2,k个3,l个4时的最小解决花费即可。
几个坑点:
1.出顺子的时候应当是-=,+=而非直接赋值。
2.预先判双王以后应当计算花费。
3.出顺子的时候,在遍历到长度没达到要求的区间的时候也应当先将其清零然后在遍历之后加回去。
4.注意四带二的各种拆法:理论上应当有\(C_{4}^{2}+C_{3}^{2}\)种,少一种都不行,例如:两组三张和两组四张可以把两组三张拆开来打。
真可以说是丧心病狂的模拟题。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define dfs(X) X.srch()
//所有数+10之后mod13,13小王,14大王。 
inline int Max(int A,int B){
    return A>B?A:B;
}
inline int Min(int A,int B){
    return A<B?A:B;
}
struct statue;
int n,ans=0x3f3f3f3f,f[14][14][9][7];
int CNT[4]={0,0,0,0};
struct statue{
    int cst;
    int a[15];
    inline void init(){
        for(int i=0;i<15;++i){
            a[i]=0;
        }
    }
    inline statue(int cstin){
        cst=cstin;
    }
    inline void srch(){
        /*
        for(int i=0;i<15;++i){
            printf("%d ",a[i]);
        }
        printf("\n");
        */
        statue nw(cst+1);
        for(int i=0;i<15;++i){
            nw.a[i]=a[i];
        }
        for(int i=0;i<12;++i){
            if(a[i]>=3){
                nw.a[i]-=3;
                for(int j=i+1;j<12;++j){
                    if(a[j]<3){
                        break;
                    }
                    nw.a[j]-=3;
                    dfs(nw);
                }
                for(int j=i+1;j<12;++j){
                    if(a[j]<3){
                        break;
                    }
                    nw.a[j]+=3;
                }
                nw.a[i]+=3;
            }
            if(a[i]>=2){
                nw.a[i]-=2;
                for(int j=i+1;j<12;++j){
                    if(a[j]<2){
                        break;
                    }
                    nw.a[j]-=2;
                    if(j-i<2){
                        continue;
                    }
                    dfs(nw);
                }
                for(int j=i+1;j<12;++j){
                    if(a[j]<2){
                        break;
                    }
                    nw.a[j]+=2;
                }
                nw.a[i]+=2;
            }
            if(a[i]>=1){
                --nw.a[i];
                for(int j=i+1;j<12;++j){
                    if(a[j]<1){
                        break;
                    }
                    --nw.a[j];
                    if(j-i<4){
                        continue;
                    }
                    dfs(nw);
                }
                for(int j=i+1;j<12;++j){
                    if(a[j]<1){
                        break;
                    }
                    ++nw.a[j];
                }
                ++nw.a[i];
            }
        }
        CNT[0]=CNT[1]=CNT[2]=CNT[3]=0;
        for(int i=0;i<15;++i){
        	++CNT[a[i]-1];
		}
		ans=Min(ans,cst+f[CNT[0]][CNT[1]][CNT[2]][CNT[3]]);
//		printf("%d:%d %d %d %d\n",cst,CNT[0],CNT[1],CNT[2],CNT[3]);
    }
};
int II=0,JJ=0,KK=0,LL=0;
inline int rnw(int A,int B,int C,int D){
	if(A<0||B<0||C<0||D<0||A>13||B>13||C>8||D>6){
		return 0;
	}
    f[A][B][C][D]=Min(f[A][B][C][D],f[II][JJ][KK][LL]+1);
    return 0;
}
inline void prpr(){
    memset(f,0x3f,sizeof(f));
    f[0][0][0][0]=0;
    for(int i=0;i<=13;++i){
        for(int j=0;j<=13;++j){
            for(int k=0;k<=8;++k){
                for(int l=0;l<=6;++l){
//                	printf("%d %d %d %d\n",i,j,k,l);
                    II=i,JJ=j,KK=k,LL=l;
                    rnw(i,j,k,l+1);
                    rnw(i+2,j,k,l+1);
                    rnw(i,j+1,k,l+1);
                    rnw(i-1,j,k+1,l+1),rnw(i+1,j-1,k+1,l+1),rnw(i,j-1,k,l+2),rnw(i+1,j,k-1,l+2),rnw(i-1,j+1,k-1,l+2),rnw(i,j-2,k+2,k+1);
                    rnw(i,j+2,k,l+1);
                    rnw(i,j,k,l+2);
                    rnw(i-1,j+1,k+1,l+1),rnw(i-1,j-1,k+1,l+2),rnw(i-2,j,k+2,l+1);
                    
                    rnw(i,j,k+1,l);
                    rnw(i+1,j,k+1,l);
                    rnw(i,j+1,k+1,l);
                    
                    rnw(i,j+1,k,l);
                    
                    rnw(i+1,j,k,l);
                }
            }
        }
    }
}
void init(){
    ans=0x3f3f3f3f;
    int x,xx;
    statue s(0);
    s.init();
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x,&xx);
        ++s.a[(!x)?(12+xx):((x+10)%13)];
    }
    if(s.a[13]&&s.a[14]){
        s.a[13]=s.a[14]=0;
        ++s.cst;
        dfs(s);
        --s.cst;
        s.a[13]=s.a[14]=1;
    }
    dfs(s);
    printf("%d\n",ans);
}
int main(){
	prpr();
    int T;
    scanf("%d%d",&T,&n);
    while(T--){
        init();
    }
    return 0;
}

 

lp5006 空间复杂度

一道大力模拟题。
凡是模拟题都可以考虑面向对象。
当然面向对象在速度上有劣势,但是显然是更清晰的。


#include<iostream>
#include<cstdio>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
struct Ans{
    int HP,STR,DEF;
};
char MAP[105][105];
int enemyHP,enemySTR,enemyDEF;
class Player{
    private:
        int HP;
        int STR;
        int DEF;
        int X;
        int Y; 
    public:
        inline void playerReset(int _X,int _Y,int _STR,int _DEF){
            X=_X,Y=_Y,STR=_STR,DEF=_DEF;
            HP=0;
        }
        inline Ans playerQuery(){
            return (Ans){HP,STR,DEF};
        }
        inline void eventQ(){
            STR+=5;
        }
        inline void eventY(){
            DEF+=5;
        }
        inline void eventR(){
            HP=(HP>10)?(HP-10):0;
        }
        inline void eventM(){
            int monsterDamage;
            monsterDamage=Max(1,((enemyHP+Max(1,STR-enemyDEF)-1)/(Max(1,STR-enemyDEF)))*(Max(1,enemySTR-DEF)));
            HP+=monsterDamage;
        }
        inline void playerGetEvent(){
            switch(MAP[X][Y]){
                case '.':{
                    return;
                    break;
                }
                case 'M':{
                    eventM();
                    break;
                }
                case 'R':{
                    eventR(); 
                    break;
                }
                case 'Q':{
                    eventQ();
                    break;
                }
                case 'Y':{
                    eventY();
                    break;
                }
            }
        }
        inline void playerMove(char moveOperator){
            int _DX,_DY;
            switch(moveOperator){
                case 'W':{
                    _DX=0;
                    _DY=-1;
                    break;
                }
                case 'E':{
                    _DX=0;
                    _DY=1;
                    break;
                }
                case 'N':{
                    _DX=-1;
                    _DY=0;
                    break;
                }
                case 'S':{
                    _DX=1;
                    _DY=0;
                    break;
                }
            }
            X+=_DX,Y+=_DY;
            playerGetEvent(); 
        }
};
int n,m,q;
Player player;
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        cin>>MAP[i]+1;
    }
    scanf("%d%d%d",&enemyHP,&enemySTR,&enemyDEF);
    int x,y,d,e;
    scanf("%d%d%d%d%d",&x,&y,&d,&e,&q);
    player.playerReset(x,y,d,e);
    char ch[5];
    Ans nw;
    for(int i=1;i<=q;++i){
        cin>>ch;
        if(ch[0]=='M'){
            cin>>ch;
            player.playerMove(ch[0]);
        }else if(ch[0]=='Q'){
            nw=player.playerQuery();
            printf("%d %d %d\n",nw.HP,nw.STR,nw.DEF);
        }
    }
}
int main(){
    init();
    return 0;
}

 

lp1563 NOIP2016 玩具谜题

一道简单的大力模拟题。

#include<iostream>
#include<cstdio>
using namespace std;

char ch[100005][15];
int typ[100005];
int n,m;
void init(){
    scanf("%d%d",&n, &m);
    for(int i=1;i<=n;++i){
        scanf("%d",&typ[i]);
        cin>>ch[i];
    }
    int x,v,p=1;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&v);
        x^=typ[p];
        if(x){
            p+=v;
            p=(p-1)%n+1;
        }else{
            p-=v;
            p=(p+n-1)%n+1;
        }
    }
    puts(ch[p]);
}
int main(){
    init();
    return 0;
}

 

lp3958 NOIP2017 奶酪

简单结论+并查集+大力模拟
注意并查集不要写挂。
另:记住long double的范围小于long long

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

#define eps 1E-9
long long n,h,r;
inline double clac(const long long &x1,const long long &y1,const long long &z1,const long long &x2,const long long &y2,const long long &z2){
    return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}
long long f[1005],x[1005],y[1005],z[1005];
inline long long fa(const long long &x){
    return (f[x]==x)?(x):(f[x]=fa(f[x]));
}
inline void uni(const long long &x,const long long &y){
    (fa(x)==fa(y))?0:f[fa(x)]=fa(y);
}
bool up[1005],dn[1005];
void init(){
    scanf("%lld%lld%lld",&n,&h,&r);
    memset(up,0,sizeof(up));
    memset(dn,0,sizeof(dn));
    for(int i=1;i<=n;++i){
        f[i]=i;
    }
    long long nx,ny,nz;
    for(int i=1;i<=n;++i){
        scanf("%lld%lld%lld",&nx,&ny,&nz);
        x[i]=nx;
        y[i]=ny;
        z[i]=nz;
        if(z[i]<=r){
            dn[i]=1;
        }
        if(h-z[i]<=r){
            up[i]=1;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(fa(i)==fa(j)){
                continue;
            }
            if((double)(r*2)>=clac(x[i],y[i],z[i],x[j],y[j],z[j])){
                uni(i,j);
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(!dn[i]){
            continue;
        }
        for(int j=1;j<=n;++j){
            if(!up[j]){
                continue;
            }
            if(fa(i)==fa(j)){
                puts("Yes");
                return;
            }
        }
    }
    puts("No");
} 
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

lp3952 NOIP2017 时间复杂度

魔鬼的大力模拟题。
千万要注意大小写。
注意数字、字符串转化。这个细节困扰了我很久。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
bool usd[30];
//lv==-1:这层循环根本不会被执行。 
struct data{
    int lv;
    int x;
}st[105];
int tp=0,n,slv=0,nlv=0,ans=0;
char ch[105];
inline int cg(){
    int _X=0,_BS=10,i=0;
    while(ch[i]<'0'||ch[i]>'9'){
        ++i;
    }
    while(ch[i]>='0'&&ch[i]<='9'){
        _X*=_BS;
        _X+=((ch[i]-'0'));
        ++i;
    }
    return _X;
}
void init(){
    scanf("%d",&n);
    memset(usd,0,sizeof(usd));
    tp=0,nlv=0;
    int ss,tt;
    cin>>ch;
    if(ch[2]=='1'){
        slv=0;
    }else{
        slv=cg();
    }
    st[0].lv=0;
    st[0].x=-1;
    bool bo=0; 
    for(int i=1;i<=n;++i){
        cin>>ch;
        if(ch[0]=='E'){
            if(!tp){
                bo=1;
            }else{
                nlv=Max(nlv,st[tp].lv);
                usd[st[tp].x]=0;
                --tp;
            }
        }else{
            cin>>ch;
            ++tp;
            if(usd[ch[0]-'a']){
                bo=1;
            }else{
                usd[ch[0]-'a']=1;
                st[tp].x=ch[0]-'a';
            }
            memset(ch,0,sizeof(ch));
            cin>>ch;
            if(ch[0]=='n'){
                ss=100000;
            }else{
                ss=cg();
            }
            memset(ch,0,sizeof(ch));
            cin>>ch;
            if(ch[0]=='n'){
                tt=100000;
            }else{
                tt=cg();
            }
            memset(ch,0,sizeof(ch));
            if(st[tp-1].lv==-1){
                st[tp].lv=-1;
                continue;
            }
            if(ss>tt){
                st[tp].lv=-1;
            }else if(ss==tt||(tt!=100000)){
                st[tp].lv=st[tp-1].lv;
            }else if(tt==100000){
                st[tp].lv=st[tp-1].lv+1;
            }
        }
    }
    if(tp||bo){
        puts("ERR");
        return;
    }
    if(nlv==slv){
        puts("Yes");
    }else{
        puts("No");
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

lp1199 NOIP2009 三国游戏

首先我们定义最优配对:最优配对指的是,对于一个武将而言,与他默契值最高的武将。
其次我们定义次优配对,次优配对指的是,对于一个武将而言,与他默契值次高的武将。
那么我们知道,无论如何,人类能够选取的一定只能是一组次优配对,而不可能是一组最优配对。
当然人类一定可以取到次优配对中的最大值。这是因为电脑的操作一定会用于破坏人类取到最优配对,因此取到次优配对一定是可能的。
如果人类想要胜利,就必须防止电脑取到最优配对中比次优配对最大值更大的那些值。我们定义这样的值为「危险值」
如果危险值存在,那么组成它的两个部分一定都互为最优配对:证明如下。
如果组成危险值的两个部分不互为最优配对,那么危险值一定是两者中一者关于另一者的最优配对。
我们不妨设定甲武将是乙的最优配对,该配对是危险值,那么乙武将必须存在一个最优配对,使得该配对的值大于危险值。
这时候乙武将的次优配对一定大于等于危险值,但是这与危险值的定义矛盾。所以组成危险值的两个部分一定互为最优配对。
故而,我们发现,危险值一定是一种最优配对。
那么,当我们优先取得足以构成次优配对中的最大值的两个武将以后,电脑已经控制的一个武将总是不能构成危险值。
这是因为组成危险值的两个武将一定互为最优配对,而电脑已经控制的仅为其中的一个武将,并且与该武将构成最优配对的武将控制在玩家手中。
当游戏进行三步时,玩家已经控制了次优配对中的最大值,并且电脑不控制任何危险值,此时可以将游戏转化为
「电脑先手且必须控制危险值」的情况。
由于危险值总是需要由一组互为最优配对的武将构成,容易证明无论电脑如何选择,玩家都可以破坏危险值的构成。
因此,总是有解,且解总为次优配对中的最大值。

当然这一题还有一个实现难点在于读入,这里就不再细说。

#include<iostream>
#include<cstdio>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
/*
lp1199 三国游戏
*/
int n,f[505][505];
void init(){
    scanf("%d",&n);
    int mx,lmx,ans=0,x;
    for(int i=1;i<n;++i){
        for(int j=i+1;j<=n;++j){
            scanf("%d",&f[i][j]);
            f[j][i]=f[i][j];
        }
    }
    /*
    for(int i=1;i<n;++i){
        for(int j=1;j<n;++j){
            printf("%d ",f[i][j]);
        }
        puts("");
    }
    */
    for(int i=1;i<=n;++i){
        mx=0,lmx=0;
        for(int j=1;j<=n;++j){
            x=f[i][j];
            if(mx<x){
                lmx=mx;
                mx=x;
            }else{
                lmx=Max(lmx,x);
            }
        }
        ans=Max(ans,lmx);
    }
    puts("1");
    printf("%d",ans);
}
int main(){
    init();
    return 0;
}