BUU-ACM选拔赛第一场题解

BUU-ACM选拔赛第一场题解 A题排行榜（模拟）
难度：easy
这题根据题意模拟即可，部分同学WA的原因有几个方面：
1.题意理解不清，注意各个比较条件
2.字符串读入有问题
选用scanf读入字符串时用scanf(“%s”,s1)，判断两队直接比赛状态时直接比较首字母即可，或者调用字符串比较函数
选用string读入字符串时用cin即可，比较字符串直接选用==即可
#include
using namespace std;
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	int t;
	cin>>t;
	while(t--)
	{
		string name1;
		int w1,d1,l1;
		int jin1,shi1,pen1;
		cin>>name1>>w1>>d1>>l1>>jin1>>shi1>>pen1;
		string name2;
		int w2,d2,l2;
		int jin2,shi2,pen2;
		cin>>name2>>w2>>d2>>l2>>jin2>>shi2>>pen2;
		int score1 = w1 * 3 + d1;
		int score2 = w2 * 3 + d2;
		string res;
		cin>>res;
		if(score1>score2)
		{
			cout<
			cout<
			cout<
			cout<qiu2)
		{
			cout<
			cout<jin2)
		{
			cout<
			cout<w2)
		{
			cout<
			cout<
			cout<pen2)
		{
			cout< 
B题 嘀嘀嘀（模拟、格式化读入） 
难度：easy
 本题错误点主要在于大家对数据范围的忽视，题目给出的k的范围为小于1e9，因此小w可能有睡好几天甚至好几年的可能性，因此对于秒数我们需要先将其对86400取模，然后再进行小时、分钟、秒的处理，注意输出时不需要很麻烦，直接选用printf格式化输出即可自动处理前导0的问题。 
#include
using namespace std;
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	int t;
	cin>>t;
	while(t--)
	{
		int t1,t2,t3;
		scanf("%d:%d:%d",&t1,&t2,&t3);
		int k;
		cin>>k;
		int kk = k % (24*60*60);
		int st = t1 * 60 * 60 + t2 * 60 + t3;
		int ed = (st + kk) % (24*60*60);
//		cout< 
C题 搭积木第三季（DP or 暴力） 
难度：mid-
 本题计算暴力时间复杂度为3e8，而题目给出3s的时限，因此本题放开了大家暴力进行尝试，但是很可惜大家都没有尝试暴力解决本题 
#include
using namespace std;
int n,cnt = 0;
int a[10];
void dfs(int deep){
	if(deep == n + 1) {
		cnt++;
		return ;
	}
	for(int i=0;a[deep]>=i;i++){
		if(a[deep]-i>=a[deep-1]){
			a[deep] -=i;
			dfs(deep + 1);
			a[deep] += i;
		}
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	dfs(1);
	cout< 
D题 余数问题（打表找规律） 
难度：mid
 首先观察数据范围为1e12，首先暴力妥妥的tle，那么再看本题的特点，我们可以先看看小数据范围时每个数的答案，将所有答案打出后，规律就显而易见了 

  
#include
using namespace std;
long long mul(long long x,long long y)
{
	long long ans = 1;
	while(y)
	{
		if(y&1)
		{
			ans = x * ans;
		}
		x=x*x;
		y=y>>1;
	}
	return ans ;
}
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	int t;
	cin>>t;
	while(t--)
	{
		long long  n;
		scanf("%lld",&n);
		long long x = n;
		int wei = 0;
		while(x)
		{
			x=x/2;
			wei++;
		}

		if(n == 1)
		{
			cout<<"0"<
			cout<
//			cout< 
E题 病毒侵袭 （prim or Kruskal最小生成树） 
难度：mid
 本题题意很简单，主要是如何转化为最小生成树问题，首先我们要将所有点全部联通，联通性的判断我们可以考虑用并查集，然后就是考虑选边，由于题目要求是最小的，因此我们将所有边按照边权大小从小到大排序，然后依次选边。当所有点相互联通时，那条边即为我们所求的答案。这一过程其实就是kruskal选边的过程，因此直接套用最小生成树模板解决即可 
#include
using namespace std;
const int N = 5005;
long long xx[N];
long long yy[N];
int f[N];
int n;
int getf(int x)
{
	if(f[x]==x)
	return x;
	else
	return f[x]=getf(f[x]);
}
struct edge
{
	int u,v;
	long long d;
	bool operator <(const edge &x)const
	{
		return d
//	return a.d
	sort(e+1,e+tot+1);
	int cnt = 0;
	ans = 0;
	for(int i=1;i<=tot;i++)
	{
		int eu = getf(e[i].u);
		int ev = getf(e[i].v);
		if(eu == ev)
		continue;
		f[eu] = ev;
		cnt++;
		ans = max(ans,e[i].d);
		if(cnt == n-1)
		break;
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld%lld",&xx[i],&yy[i]);
			f[i] = i;
		}
		tot = 0;
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				e[++tot].u=i;
				e[tot].v=j;
				e[tot].d=((xx[i]-xx[j])*(xx[i]-xx[j])+(yy[i]-yy[j])*(yy[i]-yy[j]));
//				printf("%lldn",e[tot].d);
			}
		}
		kruskal();
		printf("%lldn",ans);
	}
	return 0;
 } 
 
F题 勇者闯关 （线段树） 
难度：hard
 首先我们先将所有障碍物进行按照x轴和y轴进行排序，然后我们对每一行建立一个线段树。首先对于任何一个点，如果他左面和上面都是不可到达的，那么这个点就是不可到达的，反之即为可到达。依据这一性质，我们建立一个行线段树，对于每一个障碍物，他的右边的点一定是无法从这一行的左面到达的，因此只需看上一行的状态。对于如果当前在第 i 行 ， 如果
    
     
      
       
        
         a
        
        
         
          i
         
         
          ,
         
         
          k
         
        
       
      
      
       a_{i,k}
      
     
    ai,k和
    
     
      
       
        
         a
        
        
         
          i
         
         
          ,
         
         
          j
         
        
       
      
      
       a_{i,j}
      
     
    ai,j是障碍物，那么我们就找到第 i - 1 行中区间[j + 1 , k - 1]内最左边的能到达的点 x，那么第i行的 [x , k - 1]就是可到达的。此过程用线段树动态查询修改即可。
 时间复杂度为（klogm） 
#include
using namespace std;
const int N = 1e5+5;
#define inf 0x3f3f3f3f
struct node1
{
	int xx;
	int yy;
}e[N*3];
struct node
{
	int l,r,lz;
	int num;
}tr[N*4];
void build(int i,int l,int r)
{
	tr[i].r=r;
	tr[i].l=l;
	if(tr[i].r==tr[i].l)
	{
		tr[i].num = inf;
		return;
	}
	int mid = (l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	tr[i].lz = -1;
	tr[i].num = inf;
	return;
}
void push_down(int i)
{
	if(tr[i].lz!=-1)
	{
		tr[i<<1].lz=tr[i].lz;
		tr[i<<1|1].lz=tr[i].lz;
		int mid=(tr[i].l+tr[i].r)>>1;
		if(tr[i].lz==1)
		{
			tr[i<<1].num=tr[i<<1].l*tr[i].lz;
			tr[i<<1|1].num=tr[i<<1|1].l*tr[i].lz;
		}
		else
		{
			tr[i<<1].num=inf;
			tr[i<<1|1].num=inf;
		}
		tr[i].lz=-1;
	}
	return;
}
void update(int i,int l,int r,int k)
{
	if(tr[i].l>=l&&tr[i].r<=r)
	{
		if(k==1)
		tr[i].num=tr[i].l*k;
		else
		tr[i].num=inf;
		tr[i].lz=k;
		return;
	}
	push_down(i);
	if(tr[i<<1].r>=l)
	{
		update(i<<1,l,r,k);
	}
	if(tr[i<<1|1].l<=r)
	{
		update(i<<1|1,l,r,k);
	}
	tr[i].num = min(tr[i<<1].num,tr[i<<1|1].num);
	return;
}
int query(int i,int l,int r)
{
	if(tr[i].l>=l&&tr[i].r<=r)
	{
		return tr[i].num;
	}
	push_down(i);
	int num=inf;
	if(tr[i*2].r>=l)
	{
		num=min(num,query(i<<1,l,r));
	}
	if(tr[i<<1|1].l<=r)
	{
		num=min(num,query(i<<1|1,l,r));
	}
	return num;
}
bool cmp(node1 a,node1 b)
{
	if(a.xx!=b.xx)
	return a.xx
//	freopen("1008.in","r",stdin);
//	freopen("wa.out","w",stdout);
	int t;
	cin>>t;
	while(t--)
	{
		memset(e,0,sizeof(e));
		memset(tr,0,sizeof(tr));
		long long ans = 0;
		long long n,m,k;
		scanf("%lld%lld%lld",&n,&m,&k);
		for(int i=1;i<=k;i++)
		{
			scanf("%d %d",&e[i].xx,&e[i].yy);
		}
		for(int i=k+1;i<=k+n;i++)
		{
			e[i].xx=i-k;
			e[i].yy=m+1;
		}//增加末尾
		for(int i=k+n+1;i<=k+n+n-1;i++)
		{
			e[i].xx=i-k-n+1;
			e[i].yy=0;
		}//增加开头 
		sort(e+1,e+k+2*n,cmp);
		build(1,1,m);
		if(e[1].xx==1&&e[1].yy!=(m+1))//初始化 
		{
			update(1,1,e[1].yy-1,1);
			update(1,e[1].yy,m,0);
		}
		else
		{
			update(1,1,m,1);
		}
		int tmpnum = 0;
		for(int i=1;i<=k+2*n-1;i++)
		{
//			cout<<"pos:"<
				if(e[i].yy!=0&&e[i].yy!=m+1)
				{
					tmpnum++;
					update(1,e[i].yy,e[i].yy,0);
				}
				l = e[i].yy+1;
				r = e[i+1].yy-1;
				if(r
					update(1,l,r,0);
					ans = ans + (r-l+1); 
				}
				else
				{
					if(pos!=l)
					update(1,l,pos-1,0);
					update(1,pos,r,1);
					ans = ans + (pos-l);
				}
			}
			else//换行 
			{
				ans = ans + tmpnum ;
				tmpnum = 0;
			}
		}
		printf("%lldn",n*m-ans);
	}
	return 0;
}
BUU-ACM选拔赛第一场题解

C/C++/C#相关栏目本月热门文章
