题目链接:https://codeforc.es/gym/444200/problem/F

大意是存在一个类字符串为 ababa ,修改为类似马拉车算法的,&|a|b|a|b|a|,给出每个位置以它为中心的回文半径的长度。

构造一个仅包含a和b的字符串,满足输入的2*n+2长度的序列。

根据序列构造字符串,设当前字符串长度为r,当r<a[i]+i-1时,将左边的移动到右边来。

code:


void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=2*n+2;i++){
		cin>>a[i];
	}
	char ch = 'a';
	for(int i=1,r=1;i<=2*n+2;i++){
		while(i+a[i]-1>r) r++,c[r] = c[2*i-r];
		if(i==1) c[i] = '&';
		else if(i%2==0) c[i] = '|';
		else if(c[i]==0) c[i] = ch, ch = (ch=='a'?'b':'a');
	}
	for(int i=1;i<=2*n+2;i++){
		if(c[i]!='&'&&c[i]!='|') cout<<c[i];
	}
}


题目链接:https://codeforc.es/gym/444200/problem/H

大意是给出一个无向图,对于i从1-n的任意一个点的边数  到 任意j从1-n的任意一个点的边数。f(i,j) = cnt[i]&cnt[j] + cnt[i]|cnt[j] + cnt[i]^cnt[j] 求cgm。

猜想:因为n和m大小差不多,也就是说m不是很大,那么一定存在许多边数一样的点。直接哈希一下边数相同的数量,然后暴力+公式跑一下。

code:


const int nn = 1e6+10;
vector<int> ve[nn];
void solve()
{
	int n,m;
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		ve[x].push_back(y);
		ve[y].push_back(x);
	}
	map<ll,ll>mp;
	for(int i=1;i<=n;i++){
		mp[ve[i].size()]++;
	}
	vector<int> kk;
	for(auto c:mp){
		kk.push_back(c.fi);
	}
	ll ans = 0;
	for(int i=0;i<kk.size();i++){
		for(int j=i+1;j<kk.size();j++){
			ans+=mp[kk[i]]*mp[kk[j]]*(kk[i]&kk[j])*(kk[i]|kk[j])*(kk[i]^kk[j]);
			ans%=mod9;
		}
	}
	cout<<ans<<endl;
}


题目链接:https://codeforc.es/gym/444200/problem/J

这题当时读的有点不太明白。大意就是给出一个序列,每天可以占有土地并吸取前缀和。需要保证能量为非负数,不能保证输出-1.

做法:记录下前缀和,然后每到一个点更新一下当前最大前缀和,如果为负数,求去累加一下前面最大的前缀和。题不是很难,,,,

code:


int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n');
	ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0);
	ll n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i] = s[i-1]+a[i];
	}
	if(s[n]<0){
		cout<<-1<<endl;
		return 0;
	}
	ll maxt = 0;
	ll sum = 0;
	ll ans = 0;
	for(int i=1;i<=n;i++){
		ans++;
		maxt = max(maxt,s[i]);
		if(sum+s[i]<0){
			if(maxt<=0){
				cout<<-1<<endl;
				return 0;
			}
			else{
				ll sy = abs(sum+s[i]);
				ans+=upchu(sy,maxt);
				sum+=maxt*(upchu(sy,maxt));
			}
		}
		sum+=s[i];
	}
	cout<<ans<<endl;
}


题目链接:https://codeforc.es/gym/444200/problem/K

大意是有n+1个人投骰子,第一个人只能投1-m中的一个数,每个骰子有m面。求1-m的失败概率。

做法:这个题是队友做的,当时我绕进去出不来了。这个题对于1-n次投掷,都是等概率的,跟之前的结果有关系,所以每次概率都是(m-i)^n/(m-1)^n

啊啊啊啊啊。这个题没想出来是我的锅,队友狠狠捞了一把。

code:


void solved()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a=quick_power(m-i,n,mod);
		int b=quick_power(m-1,n,mod);
		cout<<a*quick_power(b,mod-2,mod)%mod<<" ";
	//	cout<<((a%mod)*quick_power(b,mod-2,mod))%mod<<" ";
	}
}


题目链接:https://ac.nowcoder.com/acm/contest/58871/D

大意是给出一个n*m的图,每个点存在一个数。你可以从任意点作为起点,四连通移动,如果数相等,不加能力,如果比当前小+1能力,否则不能移动(比当前数大)。求最大能量值。

做法:记忆化搜索。记忆化是想到了,但是没想到怎么具体实现它。这个题我们可以反向考虑,我们从小点往大点搜索,这样我们就可以覆盖掉大点的所有获得的最大能量。初始每个点能量为-1,如果点能量比走的步数多了就直接返回,否则,进行赋值并搜索。

code:


void dfs(int curx,int cury,int w){
	if(f[curx][cury]>=w) return;
	f[curx][cury] = w;
	for(int i=0;i<4;i++){
		int nx = curx+fx[i],ny = cury+fy[i];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
			if(a[nx][ny]>a[curx][cury])
				dfs(nx,ny,w+1);
			else if(a[nx][ny]==a[curx][cury])
				dfs(nx,ny,w);
		}
	}
}
void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			f[i][j] = -1;
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dfs(i,j,0);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			ans = max(ans,f[i][j]);
	}
	cout<<ans<<endl;
}


题目链接:https://ac.nowcoder.com/acm/contest/58871/I

大意是建立n-1条连通n个点的树,给出每个点可以链接的边数,求最小花费。链接两个点的代价是i*i+j*j。

做法:这个题很好,首先我们需要确定的是每个都应该被连接,先预处理一下每个点。我们需要链接n-1条边,所需的代价就是(n-1)*2次代价,然而我们已经给出了n个代价,也就是还有n-2个代价需要我们给出。从小到大依次给出这些代价即可。很巧妙的题,好评!

code:


void solve()
{
	int n;
	cin>>n;
	ll ans = 0;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		ans+=i*i;
		a[i]--;
	}
	int num = n-2;
	for(ll i=1;i<=n;i++){
		while(a[i]){
			ans+=i*i;
			num--;
			a[i]--;
			if(num==0){
				cout<<ans<<endl;
				return;
			}
		}
	}
	cout<<-1<<endl;
}


题目链接:https://ac.nowcoder.com/acm/contest/58177/C

大意是构造一颗数,使得树有n种状态。规则为,如果该点为僵尸,则它的子树点全为僵尸,如果该点为猫,则它的子树点不受限制。

做法:这个题比赛的时候没想出来。这个题应该要倒着做,首先可以确定的是如果直连,状态只会+1,倒着做对应-1,对于任意分叉的节点,贡献为*2+1,这里想到了,其实就是可以在n为奇数时直接/2整除。2特判一下,然后就是3的时候直接连一条边就可以了,这些特判条件还是挺难想到的。

总结一下就是,n&1时,n为3直接链接,否则从上一个点分两支。n&1=0时,直接直连一条边,然后更新即可。

code:

void solve()
{
	ll n;
	cin>>n;
	ll cu = 2;
	if(n==2){
		cout<<1<<endl;
		return;
	}
	vector<ii> ve;
	int pre = 1;
	for(int i=2;i<=1e5&&n>2;i++){
		if(n&1){
			if(n==3){
				ve.push_back(make_pair(pre,i));
				break;
			}
			ve.push_back(make_pair(pre,i));
			i++;
			ve.push_back(make_pair(pre,i));
			pre = i;
			n/=2;
		}else{
			ve.push_back(make_pair(pre,i));
			pre = i;
			n--;
		}
	}
	cout<<ve.size()+1<<endl;
	for(auto c:ve){
		cout<<c.fi<<' '<<c.se<<endl;
	}
}

题目链接:https://ac.nowcoder.com/acm/contest/58177/M

这个题快气死我了。啊啊啊啊啊。大意就是说给出一个n*m的矩阵仅含01,最外面一圈都是0,要求构造两个矩阵,满足a矩阵和b矩阵共同的1在原矩阵为1,否则为0。a和b的构造需要能够四连通,注意是连通不是四面有1。

做法,直接首先初始化ab为原,然后奇a为1,偶b为1(对行操作吧),然后对于列第一列初始a1 b0 ,最后一列a0 b1,类似这种构造。

code:

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=0;j<s.size();j++){
			c[i][j+1] = s[j]-'0';
			a[i][j+1] = b[i][j+1] = c[i][j+1];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i&1){
				a[i][j] = 1;
			}else
				b[i][j] = 1;
		}
	}
	for(int i=1;i<=n;i++){
		a[i][1] = 1;
		b[i][1] = 0;
		a[i][m] = 0;
		b[i][m] = 1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) cout<<a[i][j];
		cout<<endl;
	}
	// cout<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) cout<<b[i][j];
		cout<<endl;
	}
}

————