2021.9.20考试总结[NOIP模拟57]

T1 2A


考察快读的写法。

$code:$

T1

#include<bits/stdc++.h>
#define scanf SCANF=scanf
using namespace std;

namespace IO{
	inline int read(){
		char ch=getchar(); int x=0,f=1;
		while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
		while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
		return x*f;
	}
	inline void write(int x,char sp){
		char ch[20]; int len=0;
		if(x<0){ putchar('-'); x=~x+1; }
		do{ ch[len++]=x%10+(1<<4)+(1<<5); x/=10; }while(x);
		for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
	}
	inline int max(int x,int y){ return x<y?y:x; }
	inline int min(int x,int y){ return x<y?x:y; }
	inline void swap(int &x,int &y){ x^=y^=x^=y; }
	inline void chmax(int &x,int y){ x=x<y?y:x; }
	inline void chmin(int &x,int y){ x=x<y?x:y; }
} using namespace IO;

const int NN=50;
int SCANF;
int tmp,len,cnt,num[10];
bool flag;
char s[NN];

signed main(){
	FILE *R=freopen("ip.in","r",stdin);
	FILE *W=freopen("ip.out","w",stdout);
	scanf("%s",s+1); len=strlen(s+1); tmp=1;
	for(int i=1;i<=len;i++){
		if(s[i]=='0'&&s[i+1]>='0'&&s[i+1]<='9') flag=1;
		if(s[i]<'0'||s[i]>'9'){
			++cnt;
			if(s[i]!='.'||cnt>3) flag=1;
		}
	}
	while(num[0]<5){
		int x=0;
		while(tmp<=len&&(s[tmp]<'0'||s[tmp]>'9')) ++tmp;
		while(tmp<=len&&s[tmp]>='0'&&s[tmp]<='9'){ x=(x<<1)+(x<<3)+(s[tmp]^48); ++tmp; }
		if(x>255) x=255, flag=1;
		num[++num[0]]=x;
	}
	puts(flag?"NO":"YES");
	for(int i=1;i<5;i++) write(num[i],i==4?'\n':'.');
	return 0;
}

T2 2B


不会打暴力,于是切了。

显然的贪心:先消$AP$后消$PP$。

又发现对于每个$A$,只要它右边有足够的$P$,总能被消。因此扫一边模拟即可。不知道为啥极限数据去了$3$个零。($1e7 \to 1e4$

我写的比较麻烦,实际上从左向右扫,遇到$P$就减$A$的数量就行。

T2%%WTZ超简洁写法
#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define chkmax(x,y) (x)=(x>y)?(x):(y)
#define chkmin(x,y) (x)=(x<y)?(x):(y)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void write(int x){
	static int sta[42];int top=0;
	do{sta[++top]=x%10,x/=10;}while(x);
	while(top) putchar(sta[top--]+'0');
	return void();
}
int n,suma,sump;
char str[10010];
signed main(){
	freopen("apstr.in","r",stdin);
	freopen("apstr.out","w",stdout);
	scanf("%s",str+1);n=strlen(str+1);
	for(int i=1;i<=n;i++){
		if(str[i]=='A'){suma++;}
		else{
			if(suma){suma--;}
			else{sump++;sump%=2;}
		}
	}
	printf("%lld\n",suma+sump);
	return 0;
}
T2我的不知道为啥很麻烦的写法
#include<bits/stdc++.h>
#define scanf SCANF=scanf
using namespace std;

namespace IO{
	inline int read(){
		char ch=getchar(); int x=0,f=1;
		while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
		while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
		return x*f;
	}
	inline void write(int x,char sp){
		char ch[20]; int len=0;
		if(x<0){ putchar('-'); x=~x+1; }
		do{ ch[len++]=x%10+(1<<4)+(1<<5); x/=10; }while(x);
		for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
	}
	inline int max(int x,int y){ return x<y?y:x; }
	inline int min(int x,int y){ return x<y?x:y; }
	inline void swap(int &x,int &y){ x^=y^=x^=y; }
	inline void chmax(int &x,int y){ x=x<y?y:x; }
	inline void chmin(int &x,int y){ x=x<y?x:y; }
} using namespace IO;

const int NN=1e5+5;
int SCANF;
int n,pos,ans,sump,suma,totp,tota,rest,s[NN];
char str[NN];

signed main(){
	FILE *R=freopen("apstr.in","r",stdin);
	FILE *W=freopen("apstr.out","w",stdout);
	scanf("%s",str+1); n=strlen(str+1); s[0]=1;
	for(int i=1;i<=n;i++) s[i]=(str[i]=='P');
	for(pos=n;!s[pos];pos--) ++ans;//cout<<ans<<endl;
	for(int i=1;i<=pos;i++) tota+=s[i]^1, totp+=s[i];
	while(pos){
		sump+=s[pos]; suma+=s[pos]^1;
		if(s[pos-1]&&!s[pos]){//cout<<pos-1<<' '<<suma<<' '<<sump<<endl;
			rest+=max(0,suma-sump);
			sump-=min(sump,suma); suma=0;
		}
		pos--;
	}//cout<<tota<<' '<<totp<<' '<<rest<<endl;
	ans+=rest;
	ans+=totp-tota+rest&1;
	write(ans,'\n');
	return 0;
}
T2拿来对拍但依然能A的n2写法
#include<bits/stdc++.h>
#define scanf SCANF=scanf
using namespace std;

namespace IO{
	inline int read(){
		char ch=getchar(); int x=0,f=1;
		while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
		while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
		return x*f;
	}
	inline void write(int x,char sp){
		char ch[20]; int len=0;
		if(x<0){ putchar('-'); x=~x+1; }
		do{ ch[len++]=x%10+(1<<4)+(1<<5); x/=10; }while(x);
		for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
	}
	inline int max(int x,int y){ return x<y?y:x; }
	inline int min(int x,int y){ return x<y?x:y; }
	inline void swap(int &x,int &y){ x^=y^=x^=y; }
	inline void chmax(int &x,int y){ x=x<y?y:x; }
	inline void chmin(int &x,int y){ x=x<y?x:y; }
} using namespace IO;

const int NN=1e5+5;
int SCANF;
int n,pos,ans,sump,suma,totp,tota,rest,s[NN];
char str[NN];

signed main(){
	freopen("in","r",stdin);
	freopen("out2","w",stdout);
	scanf("%s",str+1); n=strlen(str+1); s[0]=1;
	for(int i=1;i<=n;i++) s[i]=(str[i]=='P');
	while(n){
		bool flag=0;
		for(int i=1;i<=n;i++) if(s[i+1]==1&&!s[i]){
			for(int j=i;j<=n-2;j++) s[j]=s[j+2];
			s[n]=s[n-1]=-1;
			flag=1; n-=2; break;
		}
		if(!flag) break;
	}
//	for(int i=1;i<=n;i++)cout<<s[i]<<' ';cout<<endl;
	int tmp=n;
	for(int i=1;i<=tmp;i+=2) if(s[i]==1&&s[i+1]==1) n-=2;
	write(n,'\n');
	return 0;
}

T3 2C


前两个限制很好搞,第三个限制用$bitset$记每个点的祖先,两两枚举声明的类,如果二者祖先有交且都不是对方的祖先则不合法。

也可$O(nlog)$排序后扫一遍。2021.9.20考试总结[NOIP模拟57]

$code:$

T3
#include<bits/stdc++.h>
#define bst bitset<NN>
using namespace std;

namespace IO{
	inline int read(){
		char ch=getchar(); int x=0,f=1;
		while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
		while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
		return x*f;
	}
	inline void write(int x,char sp){
		char ch[20]; int len=0;
		if(x<0){ putchar('-'); x=~x+1; }
		do{ ch[len++]=x%10+(1<<4)+(1<<5); x/=10; }while(x);
		for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
	}
	inline int max(int x,int y){ return x<y?y:x; }
	inline int min(int x,int y){ return x<y?x:y; }
	inline void swap(int &x,int &y){ x^=y^=x^=y; }
	inline void chmax(int &x,int y){ x=x<y?y:x; }
	inline void chmin(int &x,int y){ x=x<y?x:y; }
} using namespace IO;

const int NN=1010;
map<string,int>has;
int n,tot,cnt;
bst anc[NN],t;
bool flag;
string nul,tmp[NN];

signed main(){
	FILE *R=freopen("class.in","r",stdin);
	FILE *W=freopen("class.out","w",stdout);
	n=read();
	while(n--){
		cnt=0; flag=0;
		cin>>tmp[0]>>nul;
		while(tmp[cnt][0]!=';') cin>>tmp[++cnt]; --cnt;

		if(has.find(tmp[0])!=has.end()) flag=1;
		for(int i=1;i<=cnt;i++)
			if(has.find(tmp[i])==has.end()){ flag=1; break; }
		if(flag){ puts("greska"); continue; }
		
		for(int i=1;i<cnt;i++)
			for(int j=i+1;j<=cnt;j++){
				int a=has[tmp[i]],b=has[tmp[j]];
				t=anc[a]&anc[b];
				if(t.none()) continue;
				if(!anc[a][b]&&!anc[b][a]){ flag=1; break; }
			}
		puts(flag?"greska":"ok");
		if(flag) continue;
		
		has[tmp[0]]=++tot;
		for(int i=1;i<=cnt;i++){
			anc[tot]|=anc[has[tmp[i]]];
			anc[tot].set(has[tmp[i]]);
		}
	}
	return 0;
}
/*
10
shape : ;
rectangle : shape ;
circle : shape ;
circle : ;
square : shape rectangle ;
runnable : object ;
object : ;
runnable : object shape ;
thread : runnable ;
applet : square thread ;
*/

T4 2D


枚举$k$,每次在子图中$DFS$记录答案,然后拓扑排序将度数为$k$的点删掉,继续枚举$k+1$。

看起来及其暴力,但由于$n,m$同级所以不大好卡,即使被卡了也可以优化枚举策略。

注意开始时要把度数为$0$的点先删掉。

$code:$

T4
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

namespace IO{
	inline int read(){
		char ch=getchar(); int x=0,f=1;
		while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
		while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
		return x*f;
	}
	inline void write(LL x,char sp){
		char ch[20]; int len=0;
		if(x<0){ putchar('-'); x=~x+1; }
		do{ ch[len++]=x%10+(1<<4)+(1<<5); x/=10; }while(x);
		for(int i=len-1;~i;--i) putchar(ch[i]); putchar(sp);
	}
	inline int max(int x,int y){ return x<y?y:x; }
	inline int min(int x,int y){ return x<y?x:y; }
	inline void swap(int &x,int &y){ x^=y^=x^=y; }
	inline void chmax(int &x,int y){ x=x<y?y:x; }
	inline void chmin(int &x,int y){ x=x<y?x:y; }
} using namespace IO;

const int NN=1e6+5;
int n,m,mx,idx,to[NN<<1],head[NN],nex[NN<<1],in[NN],deg[NN],res;
LL M,N,B,mm,nn,bb,now,ans;

int l,r,sum,q[NN];
bool ban[NN],vis[NN];
inline void add(int a,int b,int i){
	to[++idx]=b; nex[idx]=head[a]; head[a]=idx; ++deg[a]; chmax(mx,deg[a]);
	to[++idx]=a; nex[idx]=head[b]; head[b]=idx; ++deg[b]; chmax(mx,deg[b]);
}

void dfs(int s){
	bb+=in[s]; ++nn; vis[s]=1;
	for(int i=head[s];i;i=nex[i]){
		int v=to[i];
		if(ban[v]) continue;
		++mm;
		if(!vis[v]) dfs(v);
	}
}

void topo(int lmt){
	l=1; r=0;
	for(int i=1;i<=n;i++)
		if(!ban[i]&&deg[i]==lmt) ban[i]=1, q[++r]=i, --sum;
	while(l<=r){
		int x=q[l++];
		for(int i=head[x];i;i=nex[i]) if(!ban[to[i]]){
			--deg[to[i]];
			if(deg[to[i]]==lmt)
				ban[to[i]]=1, q[++r]=to[i], --sum;
		}
	}
}

signed main(){
	FILE *R=freopen("kdgraph.in","r",stdin);
	FILE *W=freopen("kdgraph.out","w",stdout);
	n=sum=read(); m=read(); M=read(); N=read(); B=read(); ans=-1e18;
	for(int a,b,i=1;i<=m;i++)
		a=read(),b=read(), add(a,b,i);
	for(int i=1;i<=n;i++){
		in[i]=deg[i];
		if(!in[i]) --sum, ban[i]=1;
	}
	for(int k=1;k<=mx&&sum;k++){
		for(int i=1;i<=n;i++) vis[i]=0;
		for(int i=1;i<=n;i++) if(!ban[i]&&!vis[i]){
			mm=0; bb=0; nn=0;
			dfs(i);
			bb-=mm; mm>>=1;
			now=mm*M-nn*N+bb*B;
			if(now>=ans) res=k, ans=now;
		}
		topo(k);
	}
	write(res,' '); write(ans,'\n');
	return 0;
}
上一篇:C Primer Plus 编程练习 第二章


下一篇:NOIP模拟57