F
找规律题，点击查看全网最详解（臭不要脸的本人给自己打广告）：
2024牛客多校第四场F.Good Tree 挑战全网最详解 - liyishui - 博客园 (cnblogs.com)
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#define int long long
using namespace std;
int T,x;
int sol(){
cin >> x;
int n=sqrt(x);
while (n*n>x) n--;
//printf("n=%lld\n",n);
if (n*n==x) return 2*n+1;
if (n*n+n>=x){
if ((n*n+n-x)%2) return 2*n+3;
return 2*n+2;
}
else{
return 2*n+3;
}
}
void test(){
for (int i=1;i<=10;i++){
x=i;
printf("%lld:%lld\n",i,sol());
}
}
signed main(){
// test();
cin >> T;
while(T--) cout << sol() << endl;
return 0;
}
A
带权并查集或者先dfs搜一遍都可做。
std是带权并查集，我队友写的先dfs预处理出每个点最后深度，再维护一个当前u所形成的联通块的最大深度，对减一下就是答案
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int T;
const int N=1e6+505;
int n,root,u[N],v[N],c[N],vis[N];
int fa[N],h[N];
int edgenum,head[N],vet[N],Next[N],dep[N];
void edge(int u,int v){
edgenum++;
Next[edgenum]=head[u];
head[u]=edgenum;
vet[edgenum]=v;
}
void dfs(int u,int depth){
dep[u]=depth;
for (int i=head[u];i;i=Next[i]){
int v=vet[i];
if (dep[v]) continue;
dfs(v,depth+1);
}
}
int find(int x){
if (fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void work(){
scanf("%d",&n);
edgenum=0;
for (int i=1;i<=n;i++){
head[i]=0;
vis[i]=0;
dep[i]=0;
fa[i]=i;
}
for (int i=1;i<n;i++){
scanf("%d%d%d",&u[i],&v[i],&c[i]);
edge(u[i],v[i]);
vis[v[i]]=1;
}
for (int i=1;i<=n;i++)
if (vis[i]==0){
root=i;
break;
}
dfs(root,1);
for (int i=1;i<=n;i++)
h[i]=dep[i];
for (int i=1;i<n;i++){
int top=find(u[i]);
fa[v[i]]=top;
h[top]=max(h[top],h[v[i]]);
printf("%d ",h[c[i]]-dep[c[i]]);
}
printf("\n");
}
signed main(){
cin >> T;
while(T--) work();
return 0;
}
G
中考数学，做对称轴
#include<cstdio>
#include<iostream>
#include<cmath>
#define int long long
using namespace std;
int T,s1,t1,s2,t2;
double dist(int s1,int t1,int s2,int t2){
int s=s1-s2;
int t=t1-t2;
return sqrt(s*s+t*t);
}
void work(){
cin >> s1 >> t1 >> s2 >> t2;
printf("%.10lf\n",min(dist(s1,-t1,s2,t2),dist(-s1,t1,s2,t2)));
}
signed main(){
cin >> T;
while(T--) work();
return 0;
}
I
经典双指针
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,m,R[N+5],ans=0;
vector<int> v[N+5];
void Kafka()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;++i)
{
int x,y;
cin>>x>>y;
if(x>y) swap(x,y);
v[x].push_back(y);
}
for(int i=1;i<=n;++i) sort(v[i].begin(),v[i].end());
for(int i=1;i<=n;++i)
{
R[i]=i;
for(int j=0,lim=v[i].size();j<lim;++j)
{
int y=v[i][j];
if(y==R[i]+1)++R[i];
else break;
}
}
for(int i=n,cur=n,len;i;--i)
{
cur=min(cur,R[i]);
len=cur-i+1;
ans+=len;
}
cout<<ans<<endl;
}
signed main()
{
Kafka();
return 0;
}
H
折纸题。这里提供另一个不同于题解的证明思路：
考虑从小到大的三个点a1，a2，a3。并假设a1和a2之间的距离为x，a2和a3的距离为y。
2x-y的操作其实是以x为对称轴做y的对称点y'（这提示我们有的式子可以拆数学意义or几何意义）
现在选择a2为对称轴，把a1对称过去（你说可能a1对称后比a3还大，那我们就操作a3，这里以a1为例）
现在两点之间的差距变成了y，y-x。
从x，y变成y，y-x！这个形式不就是更相减损吗？这其实就是我们求gcd的过程，只不过求gcd时用了%加速了，本质上是一样的。
那么我们就可以得到：对于两个数x，y来说，最后有一个数变成0，另一个数变成它们的gcd
再回到图像上，不就是有两个点重叠，三个点变成两个点，差值也变成gcd了嘛
现在把3个点的情况扩展到4个，5个...也是一样的
所以最后的答案是gcd(a2-a1,a3-a2,a4-a3...an-an-1)
多倍经验好题：
#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
const int N=1e5+505;
int T,n;
int a[N];
int gcd(int x,int y){
if (y==0) return x;
return gcd(y,x%y);
}
void work(){
scanf("%lld",&n);
for (int i=1;i<=n;i++)
scanf("%lld",&a[i]);
int res=0;
for (int i=1;i<n;i++){
int x=a[i+1]-a[i];
if (x<0) x=-x;
res=gcd(res,x);
}
cout << res << endl;
}
signed main(){
cin >> T;
while(T--) work();
return 0;
}
C
经典置换环，发现每个点的去向是固定的，把每个位置向最后要去的地方连边，最后图一定是若干个环（因为每个点都是一个出度一个入度）
讨论一下环大小对答案的影响即可。
一次能操作4，所以环为4直接一起干掉，3的话也是。
2比较特别，一次能操作两个2，这块和在一起做掉。
5以上的发现一次最多能满足3个，就不断-3，看最后剩多少。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int vis[N],a[N],to[N];
int n,ans=0,cnt2=0;
void dfs(int u,int len){
vis[u]=1;
if(vis[to[u]]) {
if(len==1) { }
else if(len==2) cnt2++;
else if(len==3||len==4) ans++;
else if(len>=5){
if( (len-4)%3==0 ) ans+=(len-4)/3+1;
else if(len%3==0) ans+=len/3;
else if(len%3==2) ans+=len/3,cnt2++;
}
return;
}
else dfs(to[u],len+1);
}
void solve(){
cin>>n;
ans=cnt2=0;
for(int i=1;i<=n;i++){
cin>>a[i];
vis[i]=0;
to[i]=a[i];
}
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i,1);
}
}
ans+=cnt2/2;
if(cnt2&1) ans++;
cout<<ans<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
}
J
把式子用二项式定理展开
#include<bits/stdc++.h>
using namespace std;
const int N=1e5,mod=998244353;
inline int add(int x,int y){return (x+=y)>=mod?x-mod:x;}
inline int sub(int x,int y){return (x-=y)<0?x+mod:x;}
inline int mul(int x,int y){return 1LL*x*y%mod;}
inline int qpow(int a,int p){int res=1;for(;p;p>>=1,a=mul(a,a))if(p&1)res=mul(res,a);return res;}
int n,k,sum[N+5],ans=0;
char s[N+5];
int fac[N+5],invf[N+5];
inline int C(int x,int y){return x<y?0:mul(fac[x],mul(invf[y],invf[x-y]));}
void Himeko()
{
fac[0]=1;for(int i=1;i<=N;++i) fac[i]=mul(fac[i-1],i);
invf[N]=qpow(fac[N],mod-2);for(int i=N-1;~i;--i) invf[i]=mul(invf[i+1],i+1);
}
void Kafka()
{
cin>>n>>k;
cin>>s+1;
for(int p=0,div2=qpow(2,mod-2),q,res;p<=k;++p)
{
q=k-p,res=0;
for(int i=n;i;--i)
{
if(s[i]=='0') sum[i]=0;
else sum[i]=add(sum[i+1],qpow(i,q));
if(s[i]=='?') sum[i]=mul(sum[i],div2);
}
for(int i=1;i<=n;++i)
{
if(s[i]=='0') continue;
int tmp=mul(sum[i],qpow(i-1,p));
// if(s[i]=='?') tmp=mul(tmp,div2);
res=add(res,tmp);
}
res=mul(res,C(k,p));
if(p&1) ans=sub(ans,res);
else ans=add(ans,res);
}
cout<<ans<<endl;
}
signed main()
{
Himeko();
Kafka();
return 0;
}
/*
2 3
1?
*/
标签：std,第四场,int,void,len,2024,牛客,return,include From： https://www.cnblogs.com/liyishui2003/p/18329667