比賽位址

https://gmoj.net/senior/#contest/home/3248

題目

gmoj 6839. 【2020.11.5提高組模拟】淘淘藍藍喜歡 01串

gmoj 6840. 【2020.11.5提高組模拟】鏟雪（snow）

gmoj 6841. 【2020.11.5提高組模拟】淘淘藍藍之樹林

gmoj 6842. 【2020.11.5提高組模拟】淘淘藍藍之扮豬吃愉悅

總結

這次是CSP複賽前的最後一場模拟賽了，但我卻考得非常差。

T1

很簡單的一道題，發現對于操作的第二步而言，塊的長度不重要。是以操作的第一步在長度大于1的塊中删除即可，而删除靠前的塊中的元素一定是最優的。

手玩了幾個資料後，我就覺得這題OK了，于是打第二題去了。

結果成績出來後傻眼了——WA 30！！！

檢查後發現問題是這樣的：我用兩個指針向右掃，一個表示目前最靠前的是哪個塊，另一個維護最靠前的長度大于1的塊。但是我沒有強制要求第二個指針必須在第一個指針後面！！！

T2

這題想了不久就會做了。

發現如果一行上的積雪被清理得可以走了，這整個行的位置都是可以到達的，也就是可以到達任意的可走的列。

考慮怎麼從起點走到終點，分3種讨論：

起點和終點之間的行都是可走的，直接走最短的路徑即可；
起點的行和終點的列是可走的，從起點順着行走到行、列的交點，再順着列走到終點即可，這也是最短的路徑；
起點和終點的行是可走的，那麼在選擇一個列 l l l，使得 ∣ y s t − l ∣ + ∣ y e d − l ∣ |y_{st}-l|+|y_{ed}-l| ∣yst−l∣+∣yed−l∣最小。

走起點的列的情況也是同理。

這個用兩棵線段樹維護起來很友善。

打得很順（這個鍵盤真是舒服），敲了 3000 b y t e s + 3000bytes+ 3000bytes+也不覺得累，測了幾個資料後覺得過了，就看後面的題目去了。

結果成績出來之和更傻眼了——WA 0？！！

後來檢查了一下，是兩個問題導緻的：

有一個變量 rx 打成了 ly ；
在處理第3種情況時，沒有判斷這個列是否存在。

T3

沒想到怎麼做。

一開始的想法是先把與

八聯通的點全部取出來，然後問題就是怎麼把這條鍊壓縮得短一些（比如這條鍊上x到y之間的距離大于兩點間的切比雪夫距離時，就把這兩個點之間的路徑壓縮一下）

但是這樣子還是做不了。

想了好久還是沒有想出來，見時間不夠了，就打T4 A=0的部分分去了。

題解：https://blog.csdn.net/huangzihaoal/article/details/109521582

T4

A=0的資料顯然power越大，最後得分越多。是以二分+樹上DP即可。

但是沒有打對，最後加上n=1的資料拿了40分。

題解：https://blog.csdn.net/huangzihaoal/article/details/109520644

總結

這次比賽考得奇爛無比，我覺得原因有兩點：

我T1、T2沒有打對拍。就算是一道簡單的題，隻要正解不是暴力模拟，都應該要對拍。想要省下那對拍的十多分鐘，分數可能就會少上幾十分；
我T3沒有下定決心拿40分暴力分。如果想了好久都沒有頭緒，就應該直接暴力拿部分分。最後的對決，不在于有沒有切某一道難題，而在于部分分拿了多少！

祝CSP RP++！

CODE

T1

#include<cstdio>
using namespace std;
#define N 100005
char s[N];int a[N];
int main()
{
	freopen("str.in","r",stdin);
	freopen("str.out","w",stdout);
	int t,n,m,ans;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%s",&n,s+1);
		m=a[1]=1,ans=0;
		for(int i=2;i<=n;++i)
		{
			if(s[i]!=s[i-1]) a[++m]=0;
			++a[m];
		}
		for(int i=1,j=1;i<=m;++i)
		{
			++ans;
			if(j<i) j=i;
			while(j<m&&a[j]==1) ++j;
			if(a[j]==1) ++i;
			else --a[j];
		}
		printf("%d\n",ans);
	}
	return 0;
}

T2

#include<cstdio>
using namespace std;
#define print {printf("%d\n",dis(s,t));continue;}
#define rson k<<1|1
#define lson k<<1
#define M 5000005
#define N 1000005
inline int mymin(int x,int y){return x<y?x:y;}
inline int mymax(int x,int y){return x>y?x:y;}
struct line
{
	int a[N],min[M],max[M];
	void modify(int k,int l,int r,int x)
	{
		if(l==r) min[k]=max[k]=a[l];
		else
		{
			int mid=l+r>>1;
			if(x<=mid) modify(lson,l,mid,x);
			else modify(rson,mid+1,r,x);
			min[k]=mymin(min[lson],min[rson]);
			max[k]=mymax(max[lson],max[rson]);
		}
	}
	int qry(int k,int l,int r,int x,int y)
	{
		if(l==x&&r==y) return min[k];
		int mid=l+r>>1;
		if(y<=mid) return qry(lson,l,mid,x,y);
		if(x>mid) return qry(rson,mid+1,r,x,y);
		return mymin(qry(lson,l,mid,x,mid),qry(rson,mid+1,r,mid+1,y));
	}
	int get_max(int k,int l,int r,int num)
	{
		if(max[k]<num) return 0;
		if(l==r) return l;
		int mid=l+r>>1,res=get_max(rson,mid+1,r,num);
		return res?res:get_max(lson,l,mid,num);
	}
	int find_max(int k,int l,int r,int x,int y,int num)
	{
		if(max[k]<num) return 0;
		if(l==x&&r==y) return get_max(k,l,r,num);
		int mid=l+r>>1;
		if(y<=mid) return find_max(lson,l,mid,x,y,num);
		if(x>mid) return find_max(rson,mid+1,r,x,y,num);
		int res=find_max(rson,mid+1,r,mid+1,y,num);
		return res?res:find_max(lson,l,mid,x,mid,num);
	}
	int get_min(int k,int l,int r,int num)
	{
		if(max[k]<num) return 0;
		if(l==r) return l;
		int mid=l+r>>1,res=get_min(lson,l,mid,num);
		return res?res:get_min(rson,mid+1,r,num);
	}
	int find_min(int k,int l,int r,int x,int y,int num)
	{
		if(max[k]<num) return 0;
		if(l==x&&r==y) return get_min(k,l,r,num);
		int mid=l+r>>1;
		if(y<=mid) return find_min(lson,l,mid,x,y,num);
		if(x>mid) return find_min(rson,mid+1,r,x,y,num);
		int res=find_min(lson,l,mid,x,mid,num);
		return res?res:find_min(rson,mid+1,r,mid+1,y,num);
	}
}a,b;
struct node{int x,y;}s,t;
inline int abs(int x){return x<0?-x:x;}
inline int dis(node x,node y){return abs(x.x-y.x)+abs(x.y-y.y);}
int main()
{
	freopen("snow.in","r",stdin);
	freopen("snow.out","w",stdout);
	int n,m,q,opt,x,k,lx,rx,ly,ry,ans1,ans2,ans,tmp,res1,res2;
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=q;++i)
	{
		scanf("%d",&opt);
		if(opt==1) scanf("%d",&x),a.a[x]=i,a.modify(1,1,n,x);
		else if(opt==2) scanf("%d",&x),b.a[x]=i,b.modify(1,1,m,x);
		else
		{
			scanf("%d%d%d%d%d",&s.x,&s.y,&t.x,&t.y,&k);
			k=i-k,lx=mymin(s.x,t.x),rx=mymax(s.x,t.x);
			ly=mymin(s.y,t.y),ry=mymax(s.y,t.y),ans=-1;
			if(a.a[s.x]>=k)
			{
				if(b.a[t.y]>=k) print
				if(a.qry(1,1,n,lx,rx)>=k) print
				if(a.a[t.x]>=k)
				{
					if(b.find_max(1,1,m,ly,ry,k)) print
					ans1=ans2=0;
					if(ly>1)
					{
						res1=b.find_max(1,1,m,1,ly-1,k);
						ans1=res1?ly-res1:0;
					}
					if(ry<m)
					{
						res2=b.find_min(1,1,m,ry+1,m,k);
						ans2=res2?res2-ry:0;
					}
					if(ans1) ans=(ans2?mymin(ans1,ans2):ans1)*2+dis(s,t);
					else if(ans2) ans=ans2*2+dis(s,t);
				}
			}
			if(b.a[s.y]>=k)
			{
				if(a.a[t.x]>=k) print
				if(b.qry(1,1,m,ly,ry)>=k) print
				if(b.a[t.y]>=k)
				{
					if(a.find_max(1,1,n,lx,rx,k)) print
					ans1=ans2=0;
					if(lx>1)
					{
						res1=a.find_max(1,1,n,1,lx-1,k);
						ans1=res1?lx-res1:0;
					}
					if(rx<n)
					{
						res2=a.find_min(1,1,n,rx+1,n,k);
						ans2=rx<n&&res2?res2-rx:0;
					}
					tmp=0;
					if(ans1) tmp=(ans2?mymin(ans1,ans2):ans1)*2+dis(s,t);
					else if(ans2) tmp=ans2*2+dis(s,t);
					if(tmp) ans=ans<0?tmp:mymin(ans,tmp);
				}
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

T3

#include<cstdio>
#include<cstring>
using namespace std;
#define M 4000005
#define N 2005
const int dx[8]={1,1,1,0,0,-1,-1,-1},dy[8]={0,1,-1,1,-1,0,1,-1};
char a[N][N];int f[N][N],data[M][2],n,m;
inline void bfs(int stx,int sty)
{
	int x,y,xx,yy,head=0,tail=1;
	data[1][0]=stx,data[1][1]=sty;
	memset(f,0x3f,sizeof f);
	f[stx][sty]=0;
	while(head<tail)
	{
		x=data[++head][0],y=data[head][1];
		for(int i=0;i<8;++i)
		{
			xx=x+dx[i],yy=y+dy[i];
			if(xx&&yy&&xx<=n&&yy<=m&&a[xx][yy]=='.'&&f[xx][yy]>f[x][y]+1)
			{
				f[xx][yy]=f[x][y]+1;
				data[++tail][0]=xx,data[tail][1]=yy;
			}
		}
	}
}
int main()
{
	freopen("forest.in","r",stdin);
	freopen("forest.out","w",stdout);
	int stx,sty,x=0,y=0,ans=999999999,up,down;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%s",a[i]+1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(a[i][j]=='*'){stx=i,sty=j;goto out;}
	out:
	for(int j=1;j<=m;++j)
		for(int i=1;i<=n;++i)
			if(a[i][j]=='X'){x=i,y=j;goto judge;}
	judge:
	if(stx==x&&sty<y)
	{
		for(int j=1;j<=m;++j)
			for(int i=1;i<=n;++i)
				if(a[i][j]=='X'){x=i,y=j;goto mark;}
		mark:
		for(int i=y+1;i<=m;++i) a[x][i]='+';
	}
	else for(int i=1;i<y;++i) a[x][i]='+';
	bfs(stx,sty);
	for(int i=1;i<=m;++i) if(a[x][i]=='+')
	{
		up=f[x-1][i];
		if(i>1&&f[x-1][i-1]<up) up=f[x-1][i-1];
		if(i<m&&f[x-1][i+1]<up) up=f[x-1][i+1];
		down=f[x+1][i];
		if(i>1&&f[x+1][i-1]<down) down=f[x+1][i-1];
		if(i<m&&f[x+1][i+1]<down) down=f[x+1][i+1];
		if(up+down+2<ans) ans=up+down+2;
	}
	printf("%d\n",ans);
	return 0;
}

T4

#include<cmath>
#include<cstdio>
using namespace std;
typedef long double LF;
#define inf 500000
#define M 200005
#define N 100005
#define e 1e-8
int fir[N],to[M],nex[M],a[N],b[N],deg[N],son[N][2],A,p0,p1,s;
//a:power; b:point
LF f[N],g[N][2],maxx,P;
inline void inc(int x,int y)
{
	++deg[x],++deg[y];
	to[++s]=y,nex[s]=fir[x],fir[x]=s;
	to[++s]=x,nex[s]=fir[y],fir[y]=s;
}
inline int sig(LF x){return x==0?0:(x<0?-1:1);}
inline LF calc(int k,LF power,LF point)
{return 2*sig(power-a[k])*(sqrt(abs(power-a[k])+1)-1)-
A*sig(point-b[k])*(sqrt(abs(point-b[k])+1)-1);}
void dfs(int k,int fa)
{
	g[k][0]=g[k][1]=-inf,son[k][0]=son[k][1]=0;
	if(k>1&&deg[k]==1) return;
	for(int i=fir[k];i;i=nex[i]) if(to[i]!=fa)
	{
		dfs(to[i],k);
		if(f[to[i]]>g[k][0])
			g[k][1]=g[k][0],son[k][1]=son[k][0],
			g[k][0]=f[to[i]],son[k][0]=to[i];
		else if(f[to[i]]>g[k][1]) g[k][1]=f[to[i]],son[k][1]=to[i];
	}
	f[k]=g[k][0]+calc(k,P,g[k][0]);
}
void rotate(int k,int fa)
{
	if(deg[k]==1&&f[k]>maxx) maxx=f[k];
	LF gk[2],sk[2],fk=f[k],gi[2],si[2],fi;
	gk[0]=g[k][0],sk[0]=son[k][0];
	gk[1]=g[k][1],sk[1]=son[k][1];
	for(int i=fir[k];i;i=nex[i]) if(to[i]!=fa)
	{
		gi[0]=g[to[i]][0],si[0]=son[to[i]][0];
		gi[1]=g[to[i]][1],si[1]=son[to[i]][1],fi=f[to[i]];
		if(to[i]==son[k][0]) f[k]=deg[k]==1?p0+calc(k,P,p0):g[k][1]+calc(k,P,g[k][1]);
		if(f[k]>g[to[i]][0])
		{
			g[to[i]][1]=g[to[i]][0],son[to[i]][1]=son[to[i]][0];
			g[to[i]][0]=f[k],son[to[i]][0]=k;
			f[to[i]]=f[k]+calc(to[i],P,f[k]);
		}
		else if(f[k]>g[to[i]][1]) g[to[i]][1]=f[k],son[to[i]][1]=k;
		rotate(to[i],k);
		g[to[i]][0]=gi[0],son[to[i]][0]=si[0];
		g[to[i]][1]=gi[1],son[to[i]][1]=si[1];
		g[k][0]=gk[0],son[k][0]=sk[0];
		g[k][1]=gk[1],son[k][1]=sk[1];
		f[k]=fk,f[to[i]]=fi;
	}
}
int main()
{
	freopen("pigeatyy.in","r",stdin);
	freopen("pigeatyy.out","w",stdout);
	LF l=-inf,r=inf,mid,ans=0;
	int test,n,x,y;
	scanf("%d%d%d%d%d",&test,&n,&p0,&p1,&A);
	for(int i=1;i<n;++i) scanf("%d%d",&x,&y),inc(x,y);
	for(int i=1;i<=n;++i) scanf("%d%d",a+i,b+i);
	while(l<=r)
	{
		mid=(l+r)/2;
		if(n==1) maxx=p0+calc(1,mid,p0);
		else
		{
			for(int i=1;i<=n;++i)
				if(deg[i]==1)
				{
					f[i]=p0+calc(i,mid,p0);
					if(f[i]>=p1){r=mid-e,ans=mid;continue;}
				}
				else f[i]=0;
			P=mid,dfs(1,0);
			maxx=0,rotate(1,0);
		}
		if(maxx>=p1) r=mid-e,ans=mid;
		else l=mid+e;
	}
	printf("%.6LF\n",ans);
	return 0;
}

2020.11.05【NOIP提高A組】模拟比賽總結比賽位址題目總結CODE

比賽位址

題目

總結

T1

T2

T3

T4

總結

CODE

T1

T2

T3

T4

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

2020.11.05【NOIP提高A組】模拟 比賽總結比賽位址題目總結CODE

比賽位址

題目

總結

T1

T2

T3

T4

總結

CODE

T1

T2

T3

T4

繼續閱讀

2020.11.05【NOIP提高A組】模拟比賽總結比賽位址題目總結CODE