Codeforces 890-891的一些题目的反思

// 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;
}

 // 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;
}

 // 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;
}