首页 > 其他分享 >牛客第四场补题 AFHJL

牛客第四场补题 AFHJL

时间：2023-07-29 18:00:10浏览次数：48  
标签：后缀 第四场 正方形 int ++ 最小 牛客 补题 正数

牛客第四场补题 AFHJL

J. Qu'est-ce Que C'est?

题意：
构建一个n个数的数组，满足：

  • \(-m<=a_i<=m\)
  • 对于所有的\(1\le l<r\le n\)都有 \(\sum^{r}_{i=l}a_i\ge0\)

思路：
简单翻译就是最小字段和必须大于等于0。

先来做一个简单版本：要求必须区间长度为2的情况下所有都满足上面的关系。
考虑\(dp[i][j]\)表示用了i个数字，第i个数字以j结尾的方案数。
转移：对于j用原先\([-j,m]\)里面的所有数字作为结尾的时候的\(dp[i-1][j]\)都加起来.
所以每一轮i更新之后处理一个后缀和最后就是\(n\cdot n\)的时间复杂度。
提一嘴：上面式子负数不能做下标，所以所有数都加上一个m。每次可以放的新的数字的区间就是：\([0,2\cdot m]\)

但其实，和这个题目没有什么巨大的卵用。

考虑这个题目的性质，所有长度大于等于2的区间都满足和大于等于0.
也就是最小的区间和大于等于0。

考虑这样一件事情：

只需要考虑最小后缀
放的一个大前提，就是最小的区间和大于等于0.那么最小后缀，一定就是最坏的情况。
所以每一次只关注当前的最小后缀就一定可以满足要求。

如何关注最小后缀：

  • 最小后缀是负数：这种情况下，必须最后加一个正数，之后这种情况下的最小后缀，就是当前的负数加上这个正数。（加上这个正数之后，一定要变为正数才可以满足题意）
  • 最小后缀是正数：
    • 如果再放一个正数，应该更新最小后缀就是新的正数。因为是最小的后缀。
    • 如果再放一个负数，应该更新最小后缀直接是最后放进去的负数。

那么转移方程就变为了：\(dp[i][j]\)表示放了i个数，当前最小后缀是j时候的方案数。

上面的论述都只是大致的放物品，转移的过程，具体转移方程，有了上面第一种问题的铺垫，是很好写的。同样用了后缀前缀的思路。
要理清楚一些细节：
比如当前后缀是5的情况下，再放一个数字，后缀可以变为：\([-5,m]\)里面的任何一种。
打个表就能够得知当前的后缀可以由哪些推理过来，并基于此发现应该每一次更新后缀、前缀。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll =long long; 

const ll P=998244353;
const int N=5e3+5;
ll f[N],z[N],fq[N],zh[N];
//记录放了i个数字之后最小后缀是x的时候的方案数。
//i被滚动掉了。

//正数最小后缀:
//加正数 变为新加的正数
//加负数 变为新加的负数
//如果是负数最小后缀：
//加正数:最小后缀等于之前最小后缀+新放进去的正数。


int n,m;

//对于z[0~m] 每一个都是把所有的z[0~m] 都加上。
//对于对于f[1] 把在[1~m] 都加上 
//对于f[2] 把【2~m】都加上 需要有一个后缀 把正数的当前的
//对于z[m-x] 需要原先的f[1~x];
void ch_zh(){
	zh[m+1]=0;
	for(int i=m;i>=0;i--){
		zh[i]=(z[i]+zh[i+1])%P;
	}
}

void ch_fq(){
	fq[0]=0;
	for(int i=1;i<=m;i++){
		fq[i]=(f[i]+fq[i-1])%P;
	}
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin>>n>>m;
	for(int i=0;i<=m;i++) z[i]=1;
	for(int i=1;i<=m;i++) f[i]=1;

	fq[0]=0;
	for(int i=1;i<=m;i++){
		fq[i]=(f[i]+fq[i-1])%P;
	}
	zh[m+1]=0;
	for(int i=m;i>=0;i--){
		zh[i]=(z[i]+zh[i+1])%P;
	}


	for(int i=2;i<=n;i++){
		for(int j=0;j<=m;j++) z[j]=zh[0];
		for(int j=1;j<=m;j++) f[j]=zh[j];
		for(int j=1;j<=m;j++) z[m-j]=(z[m-j]+fq[j])%P;
		ch_fq();	
		ch_zh();
	}

	ll ans=0;
	for(int i=0;i<=m;i++) ans=(ans+z[i])%P;
	for(int i=1;i<=m;i++) ans=(ans+f[i])%P;

		
	cout<<ans<<"\n";
	return 0;
}

H.Merge the squares!

题意：
给定一个n*n的 正方形。
目的：通过一些操作，使得最后整个正方形最后被一个正方形覆盖把所有的正方形覆盖住。
要求：
每一个正方形覆盖的时候下面的正方形的数目必须在\([2,50]\)之间。

距离：
对于\(8\cdot8\)，直接用边长为8的正方形，会直接覆盖64个，不可以。
把\(8\cdot8\)分为四个\(2\cdot2\),最后再用边长为8的正方形，最后一步其实是覆盖了4个正方形，符合规则。
要求按照顺序输出每一次操作。
题目保证有解

思路：
考虑如何构造才是可以的。

对于一个正方形：

  • 如果边长小于等于7可以直接覆盖。
  • 如果大于7，就在左上角和右下角各自开一个正方形，还会留有两个一模一样的长方形。
    但是如何判定在当前的分割每一次操作所覆盖的正方形都是数目最小的？

比如：\(13*13\)
可以在左上角用边长为6的正方形，右下角用边长为7的正方形。
剩下两个长方形刚好为：\(6\cdot7\)
对于一个\(6*7\)的长方形:
\(6*7\)不太有代表性，假设为\(2*7\):
放三个\(2\cdot2\)的正方形，最后再放两个1*1的。
会发现，其实和gcd的过程一样。

int gcd(int a,int b){
	if(b==0) return a;
	else return gcd(b,a%b);
}

一次操作之后b变为了1，此时最后需要剩下的a只能一个一个放。
重写一个gcd:

int gcd(int a, int b, int &cnt) {
    if (b) {
        cnt += a / b;
        return gcd(b, a % b, cnt);
    }
    else return a;
}

就能很快计算出来需要的操作次数（其实是需要至少放几个正方形），如果不是<=24次，就说明当前不行。
因为分为了两个正方形，两个长方形，总共的最后剩的正方形的数目必须小于等于50.

#include <bits/stdc++.h>
using namespace std;
struct node{ int x,y,k;};
vector<node>ans;

int gcd(int a,int b,int &cnt){
	if(b==0) return a;
	else {
		cnt+=a/b;
		return gcd(b,a%b,cnt);
	}
}

void dfs_sqa(int x,int y,int a);
void dfs_rec(int x, int y, int a, int b) {
    if (a >= b) {
        if (!b) return;
        for (int i = b;i <= a;i += b) dfs_sqa(x + i - b, y, b);
        dfs_rec(x + a / b * b, y, a % b, b);
    }
    else {
        if (!a) return;
        for (int i = a;i <= b;i += a) dfs_sqa(x, y + i - a, a);
        dfs_rec(x, y + b / a * a, a, b % a);
    }
}

void dfs_sqa(int x,int y,int a){
	if(a==1) return ;
	if(a<=7){
		ans.push_back({x,y,a}); 
		return ;
	}

	for(int i=1;i<=a-i;i++){
		int cnt=0;
		gcd(i,a-i,cnt);
		if(cnt>24) continue;
		dfs_sqa(x,y,i);
		dfs_rec(x+i,y,a-i,i);
		dfs_sqa(x+i,y+i,a-i);
		dfs_rec(x,y+i,i,a-i);
		break;
	}

	ans.push_back({x,y,a});

}

int main()
{

	int n;
	cin>>n;
	dfs_sqa(1,1,n);
	cout<<ans.size()<<"\n";
	for(auto v:ans){
		cout<<v.x<<' '<<v.y<<' '<<v.k<<'\n';
	}
	return 0;
}

A.Bobo String Construction

思路：
直接判断全为1或者全为0可不可以即可。
用kmp或者find函数都可以满足要求。
代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e3 + 10;
int n;
string t;
int pmt[maxn];

void get_pmt(string s){
	int len = s.size();
	for(int i = 1, j = 0; i < len; i++){
		while(j && s[i] != s[j]) j = pmt[j - 1];
		if(s[i] == s[j]) j++;
		pmt[i] = j;
	}
}

int  kmp(string s, string t){
	int len = s.size();
	int len2 = t.size();
	int cnt = 0;
	for(int i = 0, j = 0; i < len; i++){
		while(j && s[i] != t[j]) j = pmt[j - 1];
		if(s[i] == t[j]) j++;
		if(j == len2){
			cnt++;
		}
	}
	return cnt;
}

void solve(){
	cin>>n;
	cin>>t;
	int len = t.size();
	memset(pmt, 0, 4 * (len + 5));
	int num0 = 0, num1 = 0;
	for(int i = 0; i < len; i++){
		if(t[i] == '0') num0++;
		else num1++;
	}

	if(num0 == len){
		for(int i = 1; i <= n; i++) cout<<1;
		cout<<'\n';
		return;
	}

	if(num1 == len){
		for(int i = 1; i <= n; i++) cout<<0;
		cout<<"\n";
		return;
	}

	string ans1;
	string ans2;

	char c = '0';
	for(int i = 1; i <= n; i++){
		ans1 += c;
	}
	c = '1';
	for(int i = 1; i <= n; i++){
		ans2 += c;
	}
	string s1 = t + ans1 + t;
	string s2 = t + ans2 + t;
	get_pmt(t);
	int cnt1 = kmp(s1, t);
	int cnt2 = kmp(s2, t);
	if(cnt1 <= 2){
		cout<<ans1<<"\n";
	}
	else if(cnt2 <= 2){
		cout<<ans2<<"\n";
	}
	else{
		cout<<"-1\n";
	}
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int T = 1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

F. Election of the King

思路：
根据当前最小值和最大值的特征，判断删除哪一个即可。
进行n-1轮次。

#include <bits/stdc++.h>
using namespace std;
using ll=long long ;
const int N=1e6+5;
ll a[N];
pair<ll,int>c[N];
ll b[N];
int main()
{
	cin.tie(0);
ios::sync_with_stdio(false);	
int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]; a[i]*=2;
		c[i]={a[i],i};
	}
	sort(c+1,c+1+n);

	for(int i=1;i<=n;i++){
		b[i]=c[i].first;
	}


	int l=1;int r=n;

	for(int i=1;i<=n-1;i++){
		int mid=(b[r]+b[l])/2;

		int p=lower_bound(b+l,b+r+1,mid)-b;
		int z,y;
		if(b[p]!=mid){
			z=r-p+1;
			y=p-1-l+1;
		}
		else{
			if(c[r].second>c[l].second) y++;
			else z++;
			z=r-(p+1)+1;
			y=p-1-l+1;
		}
		if(z>y) l++;
		else r--;

	}
	cout<<c[l].second<<"\n";

	return 0;
}

L. We are the Lights

倒着模拟就好了。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 1e6 + 10;
int n, m, q;
int r[maxn];
int visr[maxn];
int c[maxn];
int visc[maxn];

struct node{
	string s;
	int x;
	string op;
};

void solve(){
	cin>>n>>m>>q;
	vector<node>tmp;
	while(q--){
		string s, op;
		int x;
		cin>>s>>x>>op;
		tmp.push_back({s, x, op});
	}

	int len = tmp.size();
	int numc = 0;
	int numr = 0;
	ll ans = 0;
	for(int i = len - 1; i >= 0; i--){
		string s = tmp[i].s;
		int x = tmp[i].x;
		string op = tmp[i].op;
		if(s == "row"){
			if(visr[x]) continue;
			visr[x] = 1;
			if(op == "on"){
				ans += (ll)(m - numc);
				numr++;
			}
			else{
				numr++;
			}

		}
		else{
			if(visc[x]) continue;
			visc[x] = 1;
			if(op == "on"){
				ans += (ll)(n - numr);
				numc++;
			}
			else{
				numc++;
			}
		}
	}
	cout<<ans<<"\n";
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int T = 1;
	while(T--){
		solve();
	}
	return 0;
}

标签：后缀,第四场,正方形,int,++,最小,牛客,补题,正数
From： https://www.cnblogs.com/dhu-gxy/p/17590224.html

相关文章

  • 补题
    暑假友谊赛No.2——冰题意：n个人，m句话，用一个字符串表示一个人是否会说第i句话。选出一些人组成一个队列，要求按原来的顺序但可以不连续，相邻的两个人不能会说同样的话。求队列的种数。思路：状态压缩dp，把字符串转换成01字符串。0表示不说，1表示说。相邻两人不能会说同样的话转换......
  • 牛客暑假多校 2023 第四场
    目录写在前面ALFJH写在最后写在前面比赛地址：https://ac.nowcoder.com/acm/contest/57358。那时，天下人的口音，言语，都是一样。他们往东边迁移的时候，在示拿地遇见一片平原，就住在那里。他们彼此商量说，来吧，我们要作砖，把砖烧透了。他们就拿砖当石头，又拿石漆当灰泥。他们说，来吧，我......
  • 【题解】[2023牛客多校] Qu'est-ce Que C'est?
    题目传送门：[2023牛客多校]Qu'est-ceQueC'est?题意给定\(n，m\)构造\(a_{1},a_{2},...,a_{n}\)，其中\(a_{i}\in[-m,m]\)之间取值。需要保证序列任意连续子段和都非负。\(0\leqn,m\leq5000\)分析记录合法序列的最小后缀。通过最小后缀来判断下一个数的取值范围。......
  • 暑假牛客多校第四场 2023-7-28
    未补完L.WearetheLights算法：反向构造做法：  我们用c_on,r_on,c_off,r_off分别表示倒着推的行灯打开的集合、列灯打开的集合、列灯关闭的集合、行灯关闭的集合。倒着推时，我们先考虑on的情况。为了偷懒，我们就只考虑行的情况，因为列的情况实际上是一样的。  打开......
  • 暑假集训D5 2023.7.28 补题
    首先来回顾一下\(dijkstra\)和\(SPFA\)里面\(vis\)数组的作用和区别,以及不用\(vis\)数组的影响.(今天发现之前写堆优化的\(Dijkstra\)都不加\(vis\)数组...)\(Dijkstra\)算法中,每次取出距离源点最近的一个点来更新与他相连的其他点,置\(vis\)数组为\(true\)......
  • HDU 暑假多校 2023 第四场
    目录写在前面731773237314732173227318写在最后写在前面补题地址：https://acm.hdu.edu.cn/listproblem.php?vol=64，题号7312~7323。我是飞舞。小子们哪，你们要自守，远避偶像。Dearchildren,keepyourselvesfromidols.——约翰一书以下按照个人向难度排序。7317签到，特......
  • 2023牛客多校7.24补题
    J-FineLogic题意：给定n个点和m对偏序关系(x,y)，构造最少的排列数目k，使得在这k个排列中至少有一个排列满足x出现在y的前面。分析：很考验思维的一道题，首先如果m对偏序关系不构成环，也就是一张有向无环图，于是用拓扑排序构造出一个合理排列即可。要是有环，就直接构造两个排列，一个是1<2<.......
  • 暑假集训D3 2023.7.26 补题
    G.P6183[USACO10MAR]TheRockGameS题意:给定长度n,构造\(2^n\)个由X和O组成的字符串,使得第一个字符串和最后一个字符串只由O组成,并且相邻的字符串只有一处不同,不得有重复的字符串.BFS貌似做不了.看题解有佬用格雷码的知识.代码如下#include<stdio.h>#include<st......
  • 暑假集训D2 2023.7.25 补题
    D.P1796汤姆斯的天堂梦这道题目非常ex，赛时死活调不出来，思路是对的,容易发现是一个DAG,所以直接DP就好,虽然后面看题解AC了，发现是重边的问题。但还是来记录一下这道ex的题目，警醒一下自己切记注意重边！！如下两份代码，一份爆0，一份AC#include<stdio.h>#include<stdlib.h>#include<s......
  • 补题报告之S班暑训第二场
    成绩比赛经过糟糕记不清了？\(\text{A}\)题，结论很显然，不出意外应该是很快就搞出来了，但是没有考虑所给的子图可能不连通！挂成\(\text{50}\)了？\(\text{B}\)题，一眼\(\text{DP}\)事实证明我是对的。但是我对一个子问题\(\text{DP}\)。考虑的是\(0\)时刻的方案选取数，本来想......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99