首页 > 其他分享 >CF#845

CF#845

时间：2023-01-25 00:44:08浏览次数：47  
标签：845 const int CF long return ModInt define

题目链接

A

核心思路

只需要知道\(奇数*奇数=奇数，偶数*偶数=偶数\)，这个性质就好了。

// Problem: A. Everybody Likes Good Arrays!
// Contest: Codeforces - Codeforces Round #845 (Div. 2) and ByteRace 2023
// URL: https://codeforces.com/contest/1777/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 

const int N=1e6+10;
int a[N];

void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	int ans=0;
	for(int i=1;i<n;i++)
	{
		if((a[i]%2)==(a[i+1]%2))
		{
			ans++;
		}
	}
	cout<<ans<<endl;
	
}


signed main()
{
int T;
cin>>T;
while(T--)
{
	solve();
}
}

B

核心思路

我们先从最基本的情况分析：123321.我们知道这个逆序对是\(2*(0+1+2)\).发现这个性质，再结合样例我们可以知道一个一般的结论：321123这种也是和上面的是一样的，所以结论也就是\(1\sim n的数打乱顺序和一般的正序的逆序对是一样的\)。所以我们只需要求出来:\(A_{n}^{n}\)，这个就是他的全部组合情况。因此答案也就呼之欲出了。

// Problem: B. Emordnilap
// Contest: Codeforces - Codeforces Round #845 (Div. 2) and ByteRace 2023
// URL: https://codeforces.com/contest/1777/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 

int mod=1e9+7;

void solve()
{
int n;
cin>>n;
int ans1=1;
for(int i=1;i<=n;i++)
ans1=ans1*i%mod;

int ans2=0;
for(int i=1;i<=n;i++)
{
	ans2=(ans2+(i-1))%mod;
}
ans2=(ans2+ans2)%mod;

int ans=ans1*ans2%mod;

cout<<ans<<endl;

}


signed main()
{
int T;
cin>>T;
while(T--)
{
	solve();
}
}

C

这个题目其实题意还是比较清楚的，他是要我们求\(a_n中的某些数来构成数组b_n使得b_n中的数可以被1\sim m整除，并且还要是得b数组的首尾之差最小\)。我们一个首先的想法就是肯定是从大到小选，因为越大的数一般质因子就越多。所以第一步我们可以选择对a数组排下序。

然后我们可以想使用双指针来维护我们的区间，具体怎么去做呢。

  1. 首先我们肯定需要添加数进入我们的区间知道区间内的数满足以上的性质，所以我们先要移动右指针。
  2. 再然后就是移动左指针看可不可以缩小他们之间的差值。不需要担心我们的答案是否会受影响因为只有符合要求才会更新我们的答案。
// Problem: C. Quiz Master
// Contest: Codeforces - Codeforces Round #845 (Div. 2) and ByteRace 2023
// URL: https://codeforces.com/contest/1777/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long 

const int N=1e6+10;
int a[N];
int cnt[N];
int num,ans;
int n,m;
/*
这个题目有一个需要注意的就是约数1这个边界。

*/

void insert(int x)//因为我们这里枚举的是约数。
{
	if(x<=1||x>m)
	return;
	cnt[x]++;
	if(cnt[x]==1)
	num++;
}
void del(int x)
{
	if(x<=1||x>m)//因为我们已经把1加进去了.
	return;
	cnt[x]--;
	if(cnt[x]==0)
	num--;
}


void solve()
{
		cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	sort(a+1,a+1+n);
	int r=0;
	num=1;//表示的是1，
	ans=1e9;
	if(m==1)
	{
		cout<<0<<endl;
		return;
	}
	for(int l=1;l<=n;l++)//枚举左边界
	{
		while(num!=m)
		{
			if(r==n)
			break;
			for(int i=1;i<=sqrt(a[r+1]);i++)
			{
				if(a[r+1]%i==0)
				{
					insert(i);
					if(a[r+1]/i!=i)
					{
						insert(a[r+1]/i);
					}
				}
			}
			r++;
			
		}
		
		if(num==m)
		ans=min(ans,a[r]-a[l]);
		
		for(int i=1;i<=sqrt(a[l]);i++)
		{
			if(a[l]%i==0)
			{
				del(i);
				if(a[l]/i!=i)
				del(a[l]/i);
			}
		}
		
	}
	if(ans==1e9)
	cout<<-1<<endl;
	else
	cout<<ans<<endl;
	
	
	
}

signed main()
{
int T;
cin>>T;
while(T--)
{
	solve();
}
}

D

我们的目的是要求对于所有的\(2^n\)种初始权值数组A[]对应的F(A)之和，这里有个很重要的点就是使用期望来化简我们需要求得式子。所以\(ans=2^n*E(F(A))\).

而我们的\(F_u(A)表示的是节点的初始权值数组是A[]时，节点u在时刻t的权值之和，也就是F(A)=\sum_{u}F_u(A)\).然后回代我们原来的式子就是\(E(F(A)=\sum _u E(F_u(A))\).像这里就是用到了期望的化简。

\(V_u(A,t)表示节点的初始权值数组A[],节点u在t时刻的权值\)。这里有两种情况：

  1. 如果以u为根的子树不存在和u相据为t的节点，那么\(V_u(A,t)=0\)
  2. 如果存在那就等于\(v_1,v2...\)的异或和。这些节点都是和他相距为t的。

我们使用\(height_u表示以节点u为根的到u的最远的叶子节点的距离\)

\(E(V_u(A,t))=1/2(t\leq height_u)\).首先我们可以知道\(V_u(A,t)就只有1和0两种取值\)。当v1,v2...这些里面有奇数个1那么他的结果就是1.这个其实很好想，我们直接次昂所有的组合情况，在除以2就好了。因为要么就是奇数个1，要么就是偶数个1.

所以\(P_1=2^k/2=2^{k-1}\).另外一个肯定也是二分之一。所以\(E(V_u(A,t))=0*0.5+1*0.5=0.5\)

假设我们的树的高度从0开始，所以

\(E(F_u(A))=E(\sum_{t=0}^{10^{100}} V_u(A,t))=(\sum_{t=0}^{height_u}+\sum_{height_u}^{10^{100}}E(V_u(A,t)))=\frac{height_u+1}{2}\).

所有\(ans=2^{n-1}\sum (height_u+1)\)

下面的代码好像还有点问题。

// Problem: D. Score of a Tree
// Contest: Codeforces - Codeforces Round #845 (Div. 2) and ByteRace 2023
// URL: https://codeforces.com/contest/1777/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

template<const int T>
struct ModInt {
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    ModInt(long long x) : x(int(x % mod)) {} 
    int val() { return x; }
    ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
    void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
    void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
    void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator /= (const ModInt &a) { *this = *this / a; }
    friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
    
    ModInt pow(int64_t n) const {
        ModInt res(1), mul(x);
        while(n){
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    
    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        if (u < 0) u += mod;
        return u;
    }
    
};
typedef ModInt<1000000007> mint;

const int N=2e5+10;
int h[N],e[N],ne[N];
int idx;
int f[N];
 mint pow2[N];
 


void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

void dfs(int u,int fa)
{
	f[u]=1;
	
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j==fa)
		continue;
		
		dfs(j,u);
		f[u]=max(f[u],f[j]+1);
		
	}
}


void solve()
{
	int m;
	cin>>m;
	memset(h,-1,sizeof h);
	memset(e,0,sizeof e);
	memset(ne,0,sizeof ne);
	idx=0;
	int n=m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	
	dfs(1,-1);
	mint sum=0;
	for(int i=1;i<=n;i++)
	sum+=f[i];
	cout<<sum*pow2[n-1]<<endl;
	
}


signed main()
{
int T;
cin>>T;
pow2[0]=1;
	for(int i=1;i<N;i++)
	{
		pow2[i]=pow2[i-1]*2;
	}
	
while(T--)
{
	solve();
}



}

标签：845,const,int,CF,long,return,ModInt,define
From： https://www.cnblogs.com/xyh-hnust666/p/17066586.html

相关文章

  • CF1726D 题解
    EdgeSplit。一开始nt了，以为红边为一颗树，蓝边为剩余边，蓝边就不会有环了。假设有\(n\)个点，\(m\)条边，且这些边没有出现环，那么连通块的数量为\(n-m\)，因为不存在环，......
  • CF1768C 题解
    \(\mathcalSolution\)【题意】题目要你构造两个序列\(p,q\)，满足\(\max\{p_i,q_i\}=a_i\)。【分析】如果满足\(\max\{p_i,q_i\}=a_i\)，则满足\(p_i=a_i,q_i\le......
  • CF1768D 题解
    \(\mathcalSolution\)【题意】我们可以交换任意两个数，求最小操作几次能让逆序对变成\(1\)。【分析】如果逆序对为\(1\)的排列一定是:\(2,1,\cdotsn\)\(1,3,......
  • CF1736D
    \(\mathcalSolution\)\(s^p=s^q\)，即满足\(s\)中可以划分成若干段连续序列，这些序列左半部分和右半部分相等。【无解】显然当\(0/1\)的个数不是偶数时无解。其他......
  • Codeforces Round #845 (Div. 2) and ByteRace 2023 A-D
    CodeforcesRound#845(Div.2)andByteRace2023A-DA.EverybodyLikesGoodArrays!题意：对给定数组进行操作：删除相邻两项，替换为两项的乘积，使得该数组奇偶相间。......
  • CF Div2 Round 845
    A注意到奇数和奇数的乘积仍是奇数。偶数和偶数的乘积仍是偶数。所以答案就是\(n\)减去奇偶连续段段个数。#include<cstdio>#include<vector>usingnamespacestd......
  • CF1715C
    *1700Monoblock-洛谷|计算机科学教育新生态(luogu.com.cn)首先看数据范围  1≤n,m≤1e5。主要是修改1e5,查询1e5,这里的话要么O(log)做法，要么O(1)做O(log)没......
  • Codeforces Round #845 (Div. 2) and ByteRace 2023
    《B.Emordnilap》数学，思维   题意：给定一个由1~n组成序列，然后将这序列复制，反转，再放到原序列的末尾，得到新的序列（设为s）问s的逆序对个数 当时我写......
  • 32. CF-Tree Queries
    题目链接给一棵树，多次询问，每次给出若干个点，问是否存在从从根到叶的一条路径满足这些点到这条路径的距离均不超过\(1\)。容易想到，只需要dfs一遍预处理一下深度之类的信......
  • [CF1748F] Circular Xor Reversal
    题目描述Youhaveanarray$a_0,a_1,\ldots,a_{n-1}$oflength$n$.Initially,$a_i=2^i$forall$0\lei\ltn$.Notethatarray$a$iszero-i......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99