首页 > 其他分享 >CF题解

CF题解

时间:2023-04-17 21:45:59浏览次数:57  
标签:res int 题解 CF ans fac mod

D. Guess the Permutation 2000 逆序性质 二分

https://codeforces.com/contest/1589/problem/D
题解:首先我们可以二分查找i的位置:当1->x逆序对>0,则在i右,否则在左,log(n)次询问。找到i的位置后,我们发现逆序对有如下性质,i->j-1的数量和i+1->j-1的数量差为j-1-i,故我们可以询问i+1->n,i->n的值得到j的位置,同理询问j->n的值和j+1->n的值得到k,总询问为32+2+2<40。

D. Hossam and (sub-)palindromic tree 2100 gq! dp,树

https://codeforces.com/problemset/problem/1771/D
题解:这种回文串且在树上,显然可以转移。如何转移?我们可以拓展回文串的两侧,我们令to(u,v)为u—>v路径上距离u为1的点,那么当s[u]!=s[v]时f(u,v)=max(f(to(u,v),v),f(u,to(v,u))),当s[u]==s[v]时,ans=max(ans,f(to(u,v),to(v,u))+2)。这样可以得到最长答案,我们只需预处理f(u,u)=0,和距离为1的u,v,将剩下的点对按照距离排序后遍历,即可得到ans。to数组的处理可以以u为根,对于其每个子节点的儿子,其to[u,v]=it。

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=3e3+10;
int d[N][N],f[N][N],go[N][N];
char s[N];
vector<int> g[N];
vector<pair<int,int> > e;
void dfs(int x,int fa,int w,int u){
	d[u][x]=d[u][fa]+1;
	for(auto it:g[x]){
		if(it==fa) continue;
		go[u][it]=w;
		dfs(it,x,w,u);
	}
}
bool cmp(pair<int,int> x,pair<int,int> y){
	auto [u1,v1]=x;
	auto [u2,v2]=y;
	return d[u1][v1]<d[u2][v2];
}
void solve(){
	int n;cin>>n;
	int ans=1;
	string ss;cin>>ss;
	for(int i=1;i<=n;i++){
		g[i].clear();
		s[i]=ss[i-1];
	}
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		g[u].pb(v);g[v].pb(u);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=0;
			d[i][j]=0;
			go[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++){
		f[i][i]=1;
		d[i][i]=0;
		for(auto it:g[i]){
			if(s[it]==s[i]){
				f[i][it]=f[it][i]=2;
			}
			else f[i][it]=f[it][i]=1;
			ans=max(ans,f[i][it]);
		}
	}
	for(int i=1;i<=n;i++){
		for(auto it:g[i]){
			d[i][it]=1;
			dfs(it,i,it,i);
		}
	}
	e.clear();
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(d[i][j]<=1) continue;
			e.pb({i,j});
		}
	}
	sort(e.begin(),e.end(),cmp);
	for(auto it:e){
		auto [u,v]=it;
		f[u][v]=max({f[u][v],f[go[u][v]][v],f[u][go[v][u]]});
		if(s[u]==s[v]) f[u][v]=max(f[go[u][v]][go[v][u]]+2,f[u][v]);
		f[v][u]=f[u][v];ans=max(ans,f[u][v]);
//		cout<<u<<" "<<v<<" "<<d[u][v]<<" "<<f[u][v]<<endl;
	}
	cout<<ans<<endl;
}
signed main(){
	int T;cin>>T;
	while(T--) solve();
}
···

## Tyler and Strings 1900
https://codeforces.com/problemset/problem/1648/C
题解:我们可以枚举第一个比b小的位置,由多重排列公式,每次用一个比b[i]小的数相当于乘上一个系数(该数数量),那么我们可以维护比b[i]小的所有数的数量并求其和,树状数组很容易做到,复杂度nlogn。具体细节见代码:

include<bits/stdc++.h>

define int long long

using namespace std;
const int N=2e5+10,mod=998244353;
int a[N],b[N],c[N],fac[N],s[N],v[N];
void add(int x,int k){
for(;x<=2e5;x+=x&-x) c[x]=(c[x]+k)%mod;
}
int ask(int x){
int res=0;
for(;x;x-=x&-x) res=(res+c[x])%mod;
return res;
}
void init(int n){
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]i%mod;
}
int qpow(int x,int y){
int res=1;
while(y){
if(y&1) res=res
x%mod;
x=xx%mod;
y>>=1;
}
return res;
}
int inv(int x){
return qpow(x,mod-2);
}
signed main(){
int n,m;cin>>n>>m;
init(200005);
for(int i=1;i<=n;i++) cin>>a[i],v[a[i]]++,s[a[i]]++;
for(int j=1;j<=m;j++) cin>>b[j];
int mul=1;
for(int i=1;i<=n;i++){
add(a[i],v[a[i]]);
mul=mul
fac[v[a[i]]]%mod;
v[a[i]]=0;
}
int ans=0;
for(int i=1;i<=min(n,m);i++){
int w=fac[n-i];
w=winv(mul)%mod;
int p=ask(b[i]-1);
w=w
p%mod;
ans=(ans+w)%mod;
int sum=ask(b[i])-ask(b[i]-1);
mul=mulinv(fac[sum])%modfac[sum-1]%mod;
add(b[i],-1);
}
if(n<m){
int ok=1;
for(int i=1;i<=n;i++){
if(!s[b[i]]) ok=0;
else s[b[i]]--;
}
if(ok) ans=(ans+1)%mod;
}
cout<<ans<<endl;
}

标签:res,int,题解,CF,ans,fac,mod
From: https://www.cnblogs.com/wjhqwq/p/17327603.html

相关文章

  • CF 476B Dreamoon and WiFi
    DreamoonandWiFi一个简答的组合数学题。开始想弄一个很妙的做法,但是我理解不了,或者说理解困难,半天没搞出来,然后试着还是用朴素好想的做法做吧,结果马上做出来了。选择朴素的做法时还是有个地方想不清楚,分类讨论+举例一下子清楚了。......
  • GDOU-CTF-2023新生赛Pwn题解与反思
    第一次参加CTF新生赛总结与反思因为昨天学校那边要进行天梯模拟赛,所以被拉过去了。16点30分结束,就跑回来宿舍开始写。第一题和第二题一下子getshell,不用30分钟,可能我没想那么多,对比网上的WP,自己和他们有点不太一样,比较暴力。大概17点10的时候,写第三题,可能自己第一次遇到随机数问......
  • elementui select下来内容过长问题解决方案
    :popper-append-to-body="false"必写自定义显示<divclass="select-flow">{{dict.declareConditions}}</div>自定义css样式el-option添加title属性 <el-selectv-model="formData.declCondition"placeholder="请选择"sty......
  • CF1646E Power Board 题解
    题目链接:https://codeforces.com/contest/1646/problem/E题目大意:有一个\(n\timesm\)的矩阵,其中第\(i\)行第\(j\)列的格子中的数字是\(i^j\)。问:矩阵中存在多少个不同的数?解题思路:可以很明显地发现,第\(1\)行的数字全部都是\(1\),而且在其它行不会出现数值为\(1\)......
  • idea中tomcat中文显示乱码问题解决
    组合拳:1、找到tomcat安装目录下面的logging.properties文件如下图:2、修改java.util.logging.ConsoleHandler.encoding=utf-8为java.util.logging.ConsoleHandler.encoding=UTF-8 3、打开idea,在file->settings->appearence里修改Name的值为支持中文的字体4、修改file......
  • CF1728D
    博弈论dp模板题首先我们可以先确定dp状态dp[round][L][R][0/1]表示第round轮,现在字符串为[L~R],上一轮的人取了左边还是右边然后发现round是可以由字符串L~R确定而来的,因为每一轮只删除一个数,因此可以优化round这维我们令dp[L][R][0/1]=1为 Alice赢,dp[L][R][0/1]=0为平局,dp[......
  • 洛谷P7492 [传智杯 #3 决赛] 序列 题解 数列分块
    题目链接:https://www.luogu.com.cn/problem/P7492解题思路:分块。解题思路全部来自yzy1大佬的博客额外掌握技能:编译时加入-Wall参数。示例程序:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+5;intn,m,blo,//n表示数列长度,m表......
  • abc250_d 250-like Number 题解
    250-likeNumber题意给定一个整数\(n\),求有多少小于等于\(n\)的满足以下条件的整数\(k\):\(k\)可以被表示为\(k=p\timesq^3\),其中\(p\ltq\),并且\(p,q\)均为质数。数据范围\(1\leqslantn\leqslant10^{18}\),\(n\)是整数。思路首先,我们发现这个式子中......
  • AT_agc003_e 题解
    题目链接神仙题,我会把我自己思考的过程一步步写出来。初看这题时感觉没什么思路,所以随便算了点东西。很容易发现如果对于一个$i$,$q_i\geqq_{i+1}$,那么$q_i$就没有意义,每次把元素放进来时先把头部比它大的都弹走,再把它放进去,设处理完的size为cnt。然后就是这道题的精髓所......
  • Atcoder题解:Agc002_f
    我们可以把这个理解成一种类似卡塔兰数的形式,我们发现,被安排的\(0\)球总数\(i\)和已经出现的颜色种数\(j\)在任意时刻都必须满足\(i\gej\)。然后就可以\(dp\)了,我们每次钦定下一个转移的球是某种颜色。如果下一个转移的球不是\(0\),那么我们就一次性把后面所有这种颜色......