Codeforces Round #722 (Div. 2)

比赛链接

Problem A:Eshag Loves Big Arrays

$$\begin{gathered} 给你n个数的数组a，对于a的任意序列，我们可以把该序列中严格大于该序列AVG(平均值)的数字删除， \\ 问最多能删除多少个数字。 \\ 思路：要想删除多的数字，最好就是让最小的逐个去和最大的数字去匹配，模拟就好了 \end{gathered}$$

// Problem: A. Eshag Loves Big Arrays
// Contest: Codeforces - Codeforces Round #722 (Div. 2)
// URL: https://codeforces.com/contest/1529/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=2e5+10,M=1e9+7;
ll n,m,_;

void solve()
{
	cin>>n;
	double a[110];
	fo(i,1,n)cin>>a[i];
	sort(a+1,a+n+1);
	int res=0;
	double aver=a[1];
	for(int i=n;i>=2;i--)
	{
		aver+=a[i];
		if(aver/2<a[i])res++;
		aver-=a[i];
	}
	cout<<res<<endl;
}

int main()
{
	cin>>_;
	while(_--)
	{
		solve();
	}
	return 0;
}

Problem B:Sifid and Strange Subsequences

$$\begin{gathered} 非常唬人的一道题，一开始没人过就离谱，以为是dp，后来画了画，就是贪心，但是没有注意到特殊 \\ 情况（就是考虑的有问题），一直wa \end{gathered}$$

$$\begin{gathered} 给定n个数的数组a，求出a中最长的strange数组的长度是多少 \\ 我们定义(b_1,b_2,...,b_k)是strange的 \\ 当对于数组中的任意pair(i,j)，1<=i<=j<=k,|a_i-a_j|>=MAX(MAX是序列中元素的最大值),定义1个数是strange的 \end{gathered}$$

$$\begin{gathered} 容易发现负数和0是都可以要的，想到先进行排序，容易发现a[j]-a[i]是递增的，我们只需要 \\ 判断a[j]-a[i]>=max即可，也容易得到最多只有一个正数,累加答案即可 \end{gathered}$$

1
4
-300 -1 0 2
    ans=3

按照思路重新打的,话说md里边也有自动换行，不错啊
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
const int M=1e9+10;
int t,n,a[N];
int minn;
void solve()
{
    cin>>n;
	minn=2*M;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
	int res=1;
    for(int i=2;i<=n;i++)
    {
        minn=min(minn,a[i]-a[i-1]);
        if(minn>=a[i])
        {
            res++;
        }
        else break;
    }
    cout<<res<<endl;
}

int main()
{
    cin>>t;
    while(t--)
        solve();
    return 0;
}

Problem C:Parsa’s Humongous Tree

$$\begin{gathered} 给你n个节点的一棵树，树中节点从1n编号,无根树,每个节点都有一个l_v,r_v，节点的权值a_v \\ {l}_v<=a_v<=r_v，对于（u,v）的一条路径，让\sum |a_u-a_v|值最大,求最大值 \end{gathered}$$

$$\begin{gathered} 250组测试样例，n<=10^5，（1<=l_i<=r_i<=10^9），说实话想不到怎么写，现在学到了，以前 \\ 还是写过树形dp的，但是这题不会就代表学的有问题，或者不会处理有很多人都过的题，既然这题 \\ 很多人都过了(div2的话1000人以上的题都算是很多人都会的题了)，那么肯定不是非常难的题 \\ 当然可能思路很难想 \end{gathered}$$

$$\begin{gathered} 注意到如果每个点的权值都去临界的话，那么绝对值的差是最大的，问题就是对于每个点我们取左边界 \\ 还是右边界,树形dp即可 \end{gathered}$$

// Problem: C. Parsa's Humongous Tree
// Contest: Codeforces - Codeforces Round #722 (Div. 2)
// URL: https://codeforces.ml/contest/1529/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1e5+10,M=1e9+7;
ll n,m,_;

int l[N],r[N];
int dp[N][2];
vector<int>adj[N];

void init()
{
	fo(i,1,n)dp[i][0]=dp[i][1]=0,adj[i].clear();
}

void dfs(int u,int fa)
{
	for(int i=0;i<adj[u].size();i++)
	{
		int j=adj[u][i];//临界点
		if(j==fa)continue;
		dfs(j,u);//得到了dp[j][0],dp[j][1]，求dp[u];
		dp[u][0]+=max(dp[j][0]+abs(l[u]-l[j]),dp[j][1]+abs(l[u]-r[j]));
		dp[u][1]+=max(dp[j][0]+abs(r[u]-l[j]),dp[j][1]+abs(r[u]-r[j]));
	}
}

void solve()
{
	cin>>n;
	init();
	fo(i,1,n)scanf("%d%d",&l[i],&r[i]);
	n--;
	while(n--){
		int u,v;scanf("%d%d",&u,&v);
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1,0);
	cout<<max(dp[1][0],dp[1][1])<<endl;
	
}
int main()
{
	cin>>_;
	while(_--)
	{
		solve();
	}
	return 0;
}

Problem D:Kavi on Pairing Duty

$$\begin{gathered} 对于2\ast n个在数轴1\sim 2\ast n的数，对他们进行配对，如果两个线段A、B有 \\ 1.A被B或B被A完全覆盖2.A和B有相同的长度,那么认为他们是合法的 \\ 求合法的方案对998244353取模 \end{gathered}$$

$$\begin{gathered} 确实是dp+数学,考虑已经知道了dp[1],dp[2],dp[3]，求dp[4],通过画图，首先是将n==4时 \\ 把1和n用一个线段覆盖，那么转换成了dp[3]，同理还有dp[2],dp[1],dp[0],最后考虑将1n覆盖 \\ 此时的方案数是n的非1的因子数,使用一个sum前缀和数组处理即可,画图好理解 \end{gathered}$$

在N*(ln(sqrt(N)))中求1~N的所有数的因数
void get()
{// 得到n的非1的约数个数 4 ==2 4 ==2
	for(int i=1;i*i<N;i++)//约数总是从对存在的
	{//枚举第一个约数
		for(int j=i;i*j<N;j++)//因为i是从小到大枚举的，j是枚举的另一个约数
		{
			// num[i*j]++;
			num[i*j]+=2;//假设i和j是两个不同的约数，num++
			if(i==j)num[i*j]--;//如果是两个相同的约数num--; 
		}
	}
	for(int i=1;i<N;i++)
		num[i]--;
}

如何求N的所有因子呢？
    （基础课的题）
容易知道约数是成对的，除非完全平方数,扫描d=1~sqrt(N),若d能整除，N/d也能整除
    时间复杂度是O(sqrt(N))
int fa[1600],m=0;
for(int i=1;i*i<=n;i++){
    if(n%i==0)
        	fa[++m]=i;
   	if(i!=n/i)fa[++m]=n/i;
}
for(int i=1;i<=m;i++)cout<<fa[i]<<" ";

// Problem: D. Kavi on Pairing Duty
// Contest: Codeforces - Codeforces Round #722 (Div. 2)
// URL: https://codeforces.com/contest/1529/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define pb push_back 
#define in insert
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1e6+10,mod=998244353;
ll n,m,_;
int dp[N];
int num[N];
int f[N];

void get()
{// 得到n的非1的约数个数 4 ==2 4 ==2
	for(int i=1;i*i<N;i++)//约数总是从对存在的
	{//枚举第一个约数
		for(int j=i;i*j<N;j++)//因为i是从小到大枚举的，j是枚举的另一个约数
		{
			// num[i*j]++;
			num[i*j]+=2;//假设i和j是两个不同的约数，num++
			if(i==j)num[i*j]--;//如果是两个相同的约数num--; 
		}
	}
	for(int i=1;i<N;i++)
		num[i]--;
}
void solve()
{
	get();
	dp[0]=1;//前缀和
	// dp[1]=2;	
	// f[1]=1;
	// for(int i=1;i<=100;++i)
		// cout<<i<<" "<<num[i]<<endl;
	//dp[1]=dp[0]+get(1);
	//dp[2]=dp[1]+dp[0]+get(2)=1+1+1==3
	//dp[3]=dp[2]+dp[1]+dp[0]+get(3);
	//dp[4]=dp[3]+dp[2]+dp[1]+dp[0]+get(4);
	
	//dp[i]表示dp数组的前缀和,不算num
	
	for(int i=1;i<=n;i++)
	{
		f[i]=(dp[i-1]+num[i])%mod;
		dp[i]=(dp[i-1]+f[i])%mod;
	}
	cout<<f[n]<<endl;
}

int main()
{
	cin>>n;solve();
	return 0;
}