【NOIP 2019シミュレーション19.8.20】

#
タイトル
A
【NOIP 2018シミュレーション19.8.20】妹
B
【NOIP 2018シミュレーション19.8.20】ボス
C
【NOIP 2018シミュレーション19.8.20】旅
A.【NOIP 2018シミュレーション19.8.20】妹
この问题は点が多くて、、、第1回はコードを打って完全に头を动かしていないで、直接比较的に长くて広くて、终わった后にいつもおかしいと感じて、考えてみて反転して置くことができることを発见して、、、结果、意外にも斜めに置くことができます!!
正解のようなコードを打って、矩形の回転の角度を列挙して、それから三角関数の知識で小さい矩形の辺の大きい矩形の上のマッピングを求めて、比較の長さでいいです

#include
#define pai 3.1415926 
using namespace std;
int main(){
//	freopen("girls.in","r",stdin);
//	freopen("girls.out","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		int a1,b1,a2,b2;
		scanf("%d%d%d%d",&a1,&b1,&a2,&b2);
		if((a1<=a2&&b1<=b2)||(b2<=b1&&a2<=a1)||(a1<=b2&&b1<=a2)||(a2<=b1&&b2<=a1))printf("Yes");
		else{
			if(a1*b1>a2*b2)swap(a1,a2),swap(b1,b2);
		int flag=0;
		for(double i=0;i<=90;i+=0.01){
			if(b1*sin(i*pai/180)+a1*cos(i*pai/180)<=a2&&b1*cos(i*pai/180)+a1*sin(i*pai/180)<=b2){printf("Yes");flag=1;break;
			}
		}
		if(!flag)printf("No");
		}
		if(t)printf("
");
	}
	return 0;
}

B.【NOIP 2018シミュレーション19.8.20】ボス
試験の時に考えたのはまず木全体の重心を探して、それから重心の1本1本の木でそれぞれ重心を探して、しかし時間が足りなくて終わっていないで、実はこのやり方の正確性は私も完全に証明していないで、しかしやはり30点を取った
正解の結論は、トロフィーは必ず木全体の直径に置いて、反証法で証明すればいいということです.
トロフィーがすべての点を覆う前提は必ず直径の2つの端点を覆うことであり、そこで2分列挙端点からトロフィーまでの距離は、check関数は2つのトロフィーの間のサブツリーが要求に合っているかどうかを検査すればよい.端点からトロフィーの間のサブツリーは必ず条件に合っているため、依然として反証法を使うことができる.この間に1つのサブノードからトロフィーまでの距離がエンドポイントからトロフィーまでの距離より大きい場合、このノードから別の直径エンドポイントまでの距離は現在の直径より大きくなり、明らかに不可能である.

#include 
#define inf 99999999
using namespace std;
int n,s,t;
struct node{
	int e,n;
}pr[1001000];
int f[1001000],in[1001000],head[1001000],idx,dep[1001000],son[1001000];
void add(int u,int v){
	pr[++idx].e=v;
	pr[idx].n=head[u];
	head[u]=idx;
}
int read(){
	char ch;
	int flag=1;
	ch=getchar();
	while(ch'9'){
		if(ch=='-')flag=-1;
		ch=getchar();
	}
	int sum=0;
	while(ch>='0'&&ch<='9'){
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return flag*sum;
}
void dfs1(int x,int fa){
	f[x]=fa;
	for(int i=head[x];i;i=pr[i].n){
		int y=pr[i].e;
		if(y==fa)continue;
		dep[y]=dep[x]+1;
		dfs1(y,x);
	}
}
int dis[1001000];
void dfs2(int x){
	dis[x]=dep[x];
	for(int i=head[x];i;i=pr[i].n){
		int y=pr[i].e;
		if(y==f[x]||in[y])continue;
		dfs2(y);
		dis[x]=max(dis[x],dis[y]);
	}
}
bool check(int mid){
	int a=s,b=t;
	while(a!=t){
		if(dep[a]-dep[s]==mid)break;
		a=son[a];
	}
	while(b!=s){
		if(dep[t]-dep[b]==mid)break;
		b=f[b];
	}
	if(dep[b]-dep[a]>2*mid)return 0;
	int ll=a,rr=b;
	while(a!=b){
		dfs2(b);
		int d=dis[b]-dep[b];
		if(min(dep[b]-dep[ll],dep[rr]-dep[b])+d>mid)return 0;
		b=f[b];
	}
	dfs2(b);
	int d=dis[b]-dep[b];
	if(min(dep[b]-dep[ll],dep[rr]-dep[b])+d>mid)return 0;
	return 1;
}
int main(){
//	freopen("ob.in","r",stdin);
//	freopen("ob.out","w",stdout);
	n=read();
	for(int i=1;idep[s])s=i;
	memset(dep,0,sizeof(dep));
	dfs1(s,0);
	for(int i=1;i<=n;i++)if(dep[i]>dep[t])t=i;
	
	int now=t;
	while(now){
		in[now]=1;
		son[f[now]]=now;
		now=f[now];
	}
	in[s]=in[t]=1;
	int l=0,r=dep[t],ans;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid))r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%d",ans);
	return 0;
}

C.【NOIP 2018シミュレーション19.8.20】旅
試験場で私は直接毎回強引に削除してspfaを走って、40しかありません
正解の考え方はとても巧みで、問題の考え方を変換して、削除の辺の操作をプラスの辺に変換して、このように私達はfloyedで毎回維持することができて、1つの細部は繰り返し削除することができるため、私達は毎回第1回の削除の辺の操作がどのステップであることを記録して、記録のこのステップを読み取ってやっとプラスすることができます

#include 
#define inf 1e15
#define ll long long
using namespace std;
int n,m,top,v[1001][1001];
ll d[1001][1001],ans[100100],a[1001][1001];
struct node{
	int c,x,y;
}pr[1001000];
int main(){
//	freopen("journey.in","r",stdin);
//	freopen("journey.out","w",stdout);
	memset(a,127,sizeof(a));
	memset(v,127,sizeof(v));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)scanf("%lld",&a[i][j]),d[i][j]=a[i][j];
	}
	for(int i=1;i<=n;i++)a[i][i]=d[i][i]=0;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&pr[i].c,&pr[i].x,&pr[i].y);
		if(pr[i].c==1){
			a[pr[i].x][pr[i].y]=inf;
			v[pr[i].x][pr[i].y]=min(v[pr[i].x][pr[i].y],i);
		}
	}
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(i!=j&&i!=k&&k!=j)a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
	
	for(int i=m;i>=1;i--){
		if(pr[i].c==2)ans[++top]=a[pr[i].x][pr[i].y];
		else{
			int x=pr[i].x,y=pr[i].y;
			if(v[x][y]!=i)continue;
			a[x][y]=min(a[x][y],d[x][y]);
			for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)a[i][j]=min(a[i][j],a[i][x]+a[x][y]+a[y][j]);
		}
	}
	for(int i=top;i>=1;i--){
		printf("%lld",ans[i]);
		if(i>1)printf("
");
	}
	return 0;
}