牛客小白月赛107（A~E）

牛客小白月赛107

A Cidoai的吃饭

思路

签到题，按题意模拟即可

code

void solve(){
	int n,a,b,c;
	cin >> n >> a >> b >> c;
	int ans=0;
	ans+=n/a;
	n%=a;
	ans+=n/b;
	n%=b;
	ans+=n/c;
	n%=c;
	cout << ans << endl;
	return ;
}

B Cidoai的听歌

思路

通过模拟不难发现，这个序列操作的次数和最终的数字跟这个序列的最小值和最大值有关
如果这个序列的最大值为mx，最小值为mn，假设最终的数字为x
那么它所需的操作次数就为$(mx-x)+(x-mn)=mx-mn$
既然这个数字x跟mx和mn有关，那么数字x取到这两个数的平均值显然是最优的
由于操作是先+1后-1，显然这个平均值要向上取整

code

void solve(){
	int n;
	cin >> n;
	for(int i=1;i<=n;++i) cin >> a[i];
	int mx=0,mn=inf;
	for(int i=1;i<=n;++i){
		mx=max(mx,a[i]);
		mn=min(mn,a[i]);
	}
	cout << mx-mn << " " << (mx+mn+1)/2 << endl;
	return ;
}

C Cidoai的植物

思路

考点：读题？？？（不是）：模拟优化
（这题赛时看了好久才看懂的，服啦）

显然，如果纯模拟这题会超时$O(nk)>1e8$
那么我们就需要考虑如何优化这个 $n$
对于操作1，我们只需要将 $i$ 行没有植物的数填上x
那么我们就可以用树的思想去优化，即用一个动态二维数组e，让列数存储行数
如果当前动态数组$e[i]$不为空，遍历这个数组，将x填进去，然后让$e[i]$清空
对于操作2，我们将行数b存储列数a，即$e[b].push\_back(a)$

这样就可以将时间复杂度压缩成$O(mk)$，可以过这道题了

code

const int N=2e4+5;
unsigned n,m,k,seed;
int p[N][210];
vector<int> e[210];
unsigned rnd(){
	int ret=seed;
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return ret;
}
void solve(){
	cin >> n >> m >> k >> seed;
	for(int j=1;j<=m;++j)
	   for(int i=1;i<=n;++i){
	   	e[j].push_back(i); 
	   }
	for(int t=1;t<=k;++t){
		int op=(rnd() % 2) + 1;
		if(op==1){
			int I=(rnd() % m) + 1;
        	int x=(rnd() % (n*m)) + 1;
        	if(e[I].empty()) continue;
        	for(auto i : e[I]){
        		p[i][I]=x;
			}
			e[I].clear();
		}
		else{
			int a=(rnd() % n) + 1;
        	int b=(rnd() % m) + 1;
        	p[a][b]=0;
        	e[b].push_back(a);
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i)
	   for(int j=1;j<=m;++j){
	   	ans^=p[i][j]*((i-1)*m+j);
	   }
	cout << ans << endl;
	return ;
}

D Cidoai的猫猫

思路

对于超过 $k$ 的连续子串，我们让这个子串的个数变为$k$
接着考虑如何将 $O(n^2)$ 优化成$O(n)$
我们可以倒着遍历，如果当前下标为 $i$ 时，有连续子串的长度为 $i$
那么我们用一个sum累加这个连续子串$i$，在用一个num统计可变的子串个数
显然对于每一个$i$来说，它最小长度为 $sum-num\ast i$
最后按题意求出ans即可

code

const int N=5e6+5;
int cnt[N],ans[N];
void solve(){
	int n;cin >> n;
	string s;cin >> s;
	s+=' ';
	int len=1;
	for(int i=1;i<=n;++i){
		if(s[i]==s[i-1]) len++;
		else{
			cnt[len]++;
			len=1;
		}
	}
	int sum=0,num=0;
	for(int i=1;i<=n;++i) ans[i]=n;
	for(int i=n;i>=1;--i){
		ans[i]-=sum-num*i;
		sum+=cnt[i]*i;
		num+=cnt[i];
	}
	int res=0;
	for(int i=1;i<=n;++i){
		res^=i*ans[i];
	}
	cout << res << endl;
	return ;
}

E Cidoai的可乐

思路

这题非常的简单（赛时根本没看QAQ）
每个节点的度就是它拥有的子树个数
对于$n$个节点，我们只需要连 $n-1$ 条线即可
我们每次挑选一个节点，显然每次用权值最小的节点来建树是最优的
将权值从小到大排序，将权值最小的节点的度全填满，接着连权值第二小的节点，循环往复，直到连接$n-1$条线
最后统计一个它的权值即可

code

PII a[N];
bool cmp(PII x,PII y){
	return x.fi<y.fi;
}
void solve(){
	int n;cin >> n;
	for(int i=1;i<=n;++i) cin >> a[i].fi;
	for(int i=1;i<=n;++i) cin >> a[i].se;
	sort(a+1,a+1+n,cmp);
	int ans=0,k=n-1;
	for(int i=1;i<n;++i){
		if(a[i].se<k){
			ans+=a[i].fi*a[i].se;
			k-=a[i].se;
		}
		else{
			ans+=k*a[i].fi;
			break;
		}
	}
	cout << ans << endl;
	return ;
}