Codeforces 890-891的一些题目的反思-Toy模板网

这篇具有很好参考价值的文章主要介绍了Codeforces 890-891的一些题目的反思。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

和atcoder一起出交互题是吧。

D题回复逆序对个数，对于[L,R-1]和[L,R]，如果R是最大值，那么对逆序对个数无影响。这样来确认某个数是不是最大的，然后递归扩展到整个区间

这里看到逆序对，要想到归并排序、分治、递归、区间合并。。。。。

查看代码


// Problem: D. More Wrong
// Contest: Codeforces - Codeforces Round 890 (Div. 2) supported by Constructor Institute
// URL: https://codeforces.com/contest/1856/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
#include<iostream>
using namespace std;
int ask(int l,int r)
{
	if(l==r)return 0;
	cout<<"? "<<l<<" "<<r<<endl;
	int c;
	cin>>c;
	return c;
}
int solve(int l,int r)
{
	if(l==r)return r;
	int mid=l+r>>1;
	int L=solve(l,mid),R=solve(mid+1,r);
	if(ask(L,R-1)==ask(L,R))
	return R;
	return L;
}
int main()
{
	int T,n;
	cin>>T;
	while(T--)
	{
		cin>>n;
		int ans=solve(1,n);
		 cout << "! " << ans << endl;
	}
	return 0;
}

E1当时想到了思路，不过在怎么让乘积最大那里陷入困境。DP实在是太差了。每一层贡献的是分成两个后的最大乘积。另外就是算子树大小也不熟练，老是害怕DFS会爆。顺便学习了bitset优化的01背包

查看代码

 // LUOGU_RID: 119388498
// Problem: E1. PermuTree (easy version)
// Contest: Codeforces - Codeforces Round 890 (Div. 2) supported by Constructor Institute
// URL: https://codeforces.com/contest/1856/problem/E1
// Memory Limit: 512 MB
// Time Limit: 2000 ms

#include<iostream>
#include<vector>
#include<bitset>
using namespace std;
const int maxn=5005;
int n,x;
long long tot;
vector<int>tree[5005];
int sz[5005];
void dfs(int i)
{
	bitset<maxn>dp;
	dp[0]=1;
	//dp.set(0);
	for(auto nex:tree[i])//这个for循环承载了太多
	{
		dfs(nex);//计算子树大小
		sz[i]+=sz[nex];
		dp|=dp<<sz[nex];//相当于01背包的内层循环。
	}
	long long tmp=0;
	for(int j=0;j<=n/2;j++)
	{
		//if(dp.test(j))
		if(dp[j])
		{
			tmp=max(tmp,1LL*j*(sz[i]-j));
		}
	}
	tot+=tmp;
	sz[i]++;
}
signed main()
{
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		cin>>x;
		tree[x].push_back(i);
	}
	dfs(1);
	cout<<tot;
	return 0;
}

891G

当时想到了枚举一个点两边连的点数多少，有点小歪。而且没有想到怎么计算点的个数。并查集和最小生成树已经快忘没了。

查看代码

 // Problem: G. Counting Graphs
// Contest: Codeforces - Codeforces Round 891 (Div. 3)
// URL: https://codeforces.com/contest/1857/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int mod=998244353;
inline int qow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1)ans=(ans*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return ans;
}
int f[200005],sz[200005];
int fin(int x)
{
	if(x==f[x])return f[x];
	return f[x]=fin(f[x]);
}
struct node
{
	int x,y,w;
}a[200005];
void solve()
{
	int n,s,ans=1;
	cin>>n>>s;
	f[n]=n;
	sz[n]=1;
	for(int i=1;i<n;i++)
	{
		f[i]=i;
		sz[i]=1;
		cin>>a[i].x>>a[i].y>>a[i].w;
	}
	sort(a+1,a+n,[](node x, node y){return x.w<y.w;});
	for(int i=1;i<n;i++)
	{
		int x=fin(a[i].x),y=fin(a[i].y),szx=sz[x],szy=sz[y];
		int edgeset=szx*szy-1;//除了已经添加的这条边,其它可以添加的边
		if(s-a[i].w+1>0)
		ans=(ans*qow(s-a[i].w+1,edgeset))%mod;//每个可以添加边的空位都可以添加大于该边长度到上限的个数或者不加
		sz[x]+=sz[y];
		f[y]=x;
		sz[y]=0;
	}
	cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}

文章来源地址https://www.toymoban.com/news/detail-633047.html

到了这里，关于Codeforces 890-891的一些题目的反思的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！