竞赛讨论区 > 10.4 提高组OI集训营第一场题解
头像
鸡尾酒QAQ
编辑于 2022-10-04 22:22 上海
+ 关注

10.4 提高组OI集训营第一场题解

T1 光

20pt

枚举每一盏灯的耗电量,然后按照公式计算每一个格子的亮度是否符合要求。

70pt

枚举三盏灯的耗电量,计算出此时每个格子的亮度,算出每个格子当前亮度与需求亮度的差值,这个差值由第四盏灯来填补。即枚举好三盏灯之后,我们可以 O(1) 算出第四盏灯的最低耗电量。

100pt

本题显然具有二分性,考虑二分答案。假设总共有 mid 的耗电量可以分配给四盏灯,我们考虑如何分配: 枚举对角线的两盏灯的耗电量,假设枚举的是左上角 a 和右下角 b。那么我们可以发现,右上角这个格子当前亮度为 ,左下角的格子的亮度也一样。我们可以算出这两个格子的亮度与需求的差值,再将 mid - a- b 的耗电量分配给这两盏灯。

一种减少写代码细节的小技巧是:算出左下角格子的大致耗电量,然后用 for 循环在估计值的附近枚举即可,这样就不需要判断边界条件了。

#include <bits/stdc++.h>
using namespace std;
int a, b, c, d;
bool check(int mid){
	for(int i = 0; i <= b; i++){
		for(int j = 0; j <= c; j++){
			int need = max(b - i - j / 4, c - j - i / 4);
			if((mid - i - j) / 2 < need){
				continue;
			}
			int now = mid - i - j;
			int tempa = max(0, a - i / 2 - j / 2), tempd = max(0, d - j / 2 - i / 2);
			int aa = max(0, (tempa - now / 4) * 4 / 3);
			for(int k = max(0, aa - 5); k <= min(now, aa + 5); k++){
				if(k + (now - k) / 4 >= tempa && k / 4 + now - k >= tempd){
					return true;
				}
			}
	
		}
	}
	return false;
}
int main(){
	cin >> a >> b >> c >> d;
	int l = 0, r = a + b + c + d, ans = a + b + c + d;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(check(mid)){
			ans = mid;
			r = mid - 1;
		}else{
			l = mid + 1;
		}
	}
	cout << ans << endl;
}

T2 爬

考虑每个位置每个二进制位对答案的贡献。

例如考虑某一点 A 上的第 m 位二进制对答案的贡献。(第 m 位的权值是

统计 A 点以及 A 点的直接孩子(只有直接孩子才可以爬到 A 点)中,有多少只蚂蚁的第 M 位二进制是 1,我们把这种蚂蚁称为好蚂蚁,不是 1 的则称为坏蚂蚁。

如果有奇数只好蚂蚁爬到 A 点,那么他们就可以异或出这个数字。假设好蚂蚁的数量为 N,那么这些好蚂蚁爬到 A 点的方案数就是 。然后我们还要统计其他对答案没有影响的蚂蚁的方案数,例如坏蚂蚁。或者是压根与 A 点无关的蚂蚁,要记得我们刚刚只是统计所有和 A 点直接相关的蚂蚁是好的还是坏的,但还有很多蚂蚁我们根本没有统计,那些蚂蚁也会形成一些方案。每一只坏蚂蚁都可以向上爬或者不爬两种都行,那么我们这个方案数就是一个2的幂次;还有其他的蚂蚁,也是可以向上爬或者不爬,他的方案数也是 2 的幂次。但是我们要特殊判断根结点不能向上爬的情况,以及 A 点只有一只好蚂蚁的情况(如果某一点只有一只蚂蚁,那么它是不能异或对答案产生贡献的)

#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
#define mod 1000000007
using namespace std;
int n;
basic_string<int> edge[maxn];
ll a[maxn],t;
ll two[maxn],ans;
void add(int x,int *num)
{
	for (int i=0;i<30;i++)
	{
		if (x&1) num[i]++;
		x=x>>1;
	}
	return;
}
void dfs(int x)
{
	int num[31]; memset(num,0,sizeof(num));
	int tot=1;
	add(a[x],num);
	for (int y:edge[x])
	{
		dfs(y);
		add(a[y],num);
		tot++;
	}
	if (tot==1) return;
	ll temp,rr=two[tot-1],pp=two[n-tot]; //rr:选了奇数个的方案 pp:除了涉及节点之外的方案 
	if (x==1) rr=two[tot-2]; //根节点不能爬,所以方案减半 
	if (x!=1) pp=two[n-tot-1]; //根节点不能爬 

	for (int i=0;i<30;i++)
	if (num[i])
	{
		temp=(1<<i);
		//刚好有一半是1,一半是0
		ll xi=rr;
		//如果x是根,且a[x]是唯一使得这一位是1的,那么就是全部情况,而非一半情况 
		if (x==1 && ((a[x]>>i)&1) && (num[i]==1)) xi=(xi*2)%mod;
		ans=(ans+temp*xi%mod*pp)%mod; 
	}
	//减去留下了单个蚂蚁的方案
	//自己留下了,无论是不是根节点都有此情况 
	ans=(ans-a[x]*pp%mod+mod)%mod;
	//某个儿子留下了,这个情况只有x不是根的情况才有 
	if (x!=1) for (int y:edge[x]) ans=(ans-a[y]*pp%mod+mod)%mod;	 
	return;
}


int main()
{
	two[0]=1;
	for (int i=1;i<maxn;i++) two[i]=(two[i-1]+two[i-1])%mod;
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=2;i<=n;i++) {cin>>t; edge[t]+=i;}
	dfs(1);
	cout<<ans<<endl;
}

T3 字符串

50pt

的动态规划,dp[i][j][0/1] 表示当前看到第 i 个位置,已经选了 j 个字母 A,上一个是字母 。转移的时候要枚举上一个位置 k,然后将 这一段全部弄成 A 或者 B。所以 dp 的。

100pt

首先对三条规则进行简单分析

1. 对于规则 3 来说,假设 ,那么如果想要通过 AB 切换来获得价值,那字符串就应该形如 BBBABBBABBBA 这样,即每 3 个 B 就切换成 A。
2. 对于规则 1.2 来说,把字母放在连续的一段地方,第一次产生价值需要 个 A 或者 个 B,第二次及以后产生价值只需要 a 个 A 或者 b 个 B

我们可以枚举 A 和 B 切换了多少次,假定我们切换的方式就是 BBBABBBABBBA,即每一段 A 的长度都为 1,我们又知道 AB 的切换次数,就可以知道现在已经用掉了几个 A,然后我们先考虑把 A 全部用完。

1. 在 BBBABBBA 的形式前面 只需要花费一个 A 就可以拿到一个价值
2. 然后将多余的 A 填充进字符串中,因为每一段 A 的长度都是 1,所以此时本质上是每多 a 个 A,答案 +1。

然后再考虑将剩余的 B 用完。

1. 如果倒数第二个位置是 A 的话,那么最后一个只需要花费一个 B 就能拿到一个价值
2. 例如 ,本来我们填充的是 BBBABBBABBBA,根据规则 2,当一段 B 的长度达到 5 的时候又可以使得价值 +1,所以我们尽量将每一段 B 都填充到长度为 5。如果全部填充好了且还有多余的 B,那么每多 b 个 B,答案 +1。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin >> t;
//bbbbabbbba
	while(t--){
		int n,m,a,b,c;
		cin >> n >> m >> a >> b >> c;
		int maxn = 0;
		for(int i = 0; i <= min(n,m / c); i++){
			int sum = 0;
			if(i == 0){
				sum++;
				sum += (n - 1) / a;
				sum += (m - 1) / b;
			}else{
				sum++;
				sum += (i - 1) * 2;
				if(n - i >= 1){
					sum++;
					int x = n - i - 1;
					sum += x / a;
				}
				
				if(c > b){
					sum += (c - 1) / b * i;
				}
				
				if(m - c * i >= 1){
					sum++;
				
					int x = m - i * c - 1;
					int mod = (((c - 1) / b + 1) * b) - (c - 1);
					if(x / mod >= i) sum += i,x -= mod * i;
					else{
						sum += x / mod;
						x -= x / mod * mod;
					}
					sum += x / b;
					
				}
			}
			maxn = max(maxn,sum);
		}
		cout << maxn + 1 << endl;
		
		
		
	}
	return 0;
}

T4 奇怪的函数

测 试点 1 :

O(nq)暴力。

测 试点 2~6 :

容易看出这是一个分段函数,形如:

我们只需要通过二分找到这个分段函数的三个断点,就可以在O(1)的时间回答每一个询问了。



测 试点 7~11:

最多只有10个取min,max的位置,那么直接维护1操作对应区间内的和,对于每一次询问,分段算答案即可,树状数组可以解决这个问题。



测 试点12~16:

可以直接DDP来处理取min操作,就变成DDP模板题了:

对于只有取min操作的询问,我们可以构造一个如下的矩阵乘法操作:



对于一个当前的数字xvmin,我们只需要构造矩阵

即可。

对于一个当前的数字xv,我们只需要构造矩阵

即可。

那么对于一次询问F(x),就相当于是让矩阵依次乘以这些矩阵,由于上述矩阵的乘法依旧满足结合律,我们用线段树维护这些矩阵的乘积即可。



除此之外这个部分分还有一个单纯用线段树维护后续起作用的min操作的位置的做法,大致结论是:对于任意一个位置开始向后,最多只有一个位置的取min操作生效了,我们维护那个唯一生效的取min位置即可,但这是某个验题人的做法,出题人并不清楚细节,所以不展开描述。

测 试点1~20:我们知道这是一个分段函数,那么就可以直接在线段树上来维护它了。

参考测 试点2~6,我们知道把任意一段区间的操作按顺序考虑,它都是一个形如测试点2~6题解所示的分段函数,如果我们知道区间对应的分段函数,以及区间对应的分段函数,那么我们可以在的时间内求出区间所对应的分段函数,那么我们就可以直接用线段树来维护这个分段函数,在O(logn)的时间里完成一个修改操作的更新,在O(1)的时间里回答一次询问。

这个做法最难写的部分是合并两个分段函数,出题人的写法相对比较通用,直接用双指针来扫描两个分段函数的值域, 然后动态的合并它,常数比分类讨论略大。

这是出题人的 pushup 部分代码:

void pushup(int now)
{
	temp.clear();
	int sz1=f[ls].size(),sz2=f[rs].size();
	int tt=0;
	for (int i=0;i<sz1;i++) //枚举左边的每一个区间 
	{
		int L,R,l,r,v;
		l=f[ls][i].l; r=f[ls][i].r; v=f[ls][i].v;
		if (f[ls][i].tp==1) L=l+v,R=r+v; else L=R=v;
		if (L==R && L>MAX) continue;
		
		if (R>MAX) {int len=R-MAX; R-=len; r-=len;} //如果超过维护的区间,就给他们减掉

		while (tt<sz2 && f[rs][tt].r<L) tt++; //找到第一个跟你相交的区间

		if (f[ls][i].tp==2)//特例1:l,r的取值区间是单点,则直接处理掉 
		{
			int zhi;
			if (f[rs][tt].tp==2) 
			{
				zhi=f[rs][tt].v;
			}
			else
			{
				zhi=L+f[rs][tt].v;
			}
			temp+=nod(l,r,2,zhi); 
			continue;
		}
		
		//l,r-->L,R
		while (l<=r && tt<sz2)
		{
			int LL,RR; //LL,RR是rs对应的起点区间
			LL=f[rs][tt].l; RR=f[rs][tt].r;		
			int tl,tr;
			tl=max(L,LL); tr=min(R,RR); //tl,tr是你们相交的区间 
			int len=tr-tl+1;
			if (len==0) {tt++; continue;}
			int ll,rr;
			ll=l+(tl-L),rr=ll+(tr-tl); 
			if (f[rs][tt].tp==2) //如果你是赋值的单点
			{
				temp+=nod(ll,rr,2,f[rs][tt].v);
				l=rr+1; L=tr+1;
				continue; 
			}
			else //你是区间+操作 
			{
				temp+=nod(ll,rr,1,f[rs][tt].v+v);
				l=rr+1; L=tr+1;
			}
		} 
	}
	
	f[now].clear();
	int flag=0; nod x;
	for (nod tt:temp)
	{
		if (flag==0) {x=tt; flag=1;}
		if (x.tp==tt.tp && x.v==tt.v)
		{
			x.r=tt.r;
			continue;		
		}
		else
		{
			f[now]+=x;
			x=tt;
		}
	}
	f[now]+=x;
}
更简便的写法是某做题人的代码:
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
const int N = 1e5 + 5, inf = 1e9;
struct atom {
  int l, r, a;
  friend atom operator + (atom x, atom y) {
    y.l -= x.a;
    y.r -= x.a;
    x.a += y.a;
    x.l = max(min(x.l, y.r), y.l);
    x.r = max(min(x.r, y.r), y.l);
    return x;
  }
} t[N << 2];
atom get(int op, int val) {
  if (op == 1) return (atom){-inf, inf, val};
  if (op == 2) return (atom){-inf, val, 0};
  return (atom){val, inf, 0};
}
void modify(int p, int l, int r, int x, int op, int val) {
  if (l == r) {
    t[p] = get(op, val);
    return ;
  }
  if (x <= mid) modify(p << 1, l, mid, x, op, val);
  else modify(p << 1 | 1, mid + 1, r, x, op, val);
  t[p] = t[p << 1] + t[p << 1 | 1];
}
int n, q;
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int op, val;
    scanf("%d%d", &op, &val);
    modify(1, 1, n, i, op, val);
  }
  scanf("%d", &q);
  while (q--) {
    int op, pos, val;
    scanf("%d", &op);
    if (op <= 3) {
      scanf("%d%d", &pos, &val);
      modify(1, 1, n, pos, op, val);
    } else {
      scanf("%d", &val);
      printf("%d\n", max(t[1].l, min(val, t[1].r)) + t[1].a);
    }
  }
  return 0;
}



全部评论

(3) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐