cf #572 div2 solution (RW personal)

2023-10-12 14:20
文章标签 cf div2 solution 572 personal rw

本文主要是介绍cf #572 div2 solution (RW personal),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

cf #572 div2 my solution

A

水题

#include<bits/stdc++.h>
using namespace std;const int maxn = 2e5+10;
const int mod = 1e9+7;int solve(string s)
{int num=0;for(int i=0;i<s.length();++i){if(s[i]=='1') num++;}return num;
}int main()
{int n;cin>>n;string s;cin>>s;if(solve(s) != n - solve(s)){cout<<1<<endl;cout<<s<<endl;}else{cout<<2<<endl;cout<<s[0]<<" "<<s.substr(1)<<endl;}return 0;
}

B

排序,构造一下即可

#include<bits/stdc++.h>
using namespace std;const int maxn = 1e5+10;int a[maxn];int main()
{int n;cin>>n;for(int i=0;i<n;++i) cin>>a[i];sort(a,a+n);if(a[n-1]>=a[n-2]+a[n-3]){cout<<"NO"<<endl;}else{cout<<"YES"<<endl;cout<<a[n-3]<<" "<<a[n-1]<<" "<<a[n-2];for(int i=n-4;i>=0;--i) cout<<" "<<a[i];cout<<endl;}return 0;
}

上面的方法要进行排序,思考下面问题

在这里插入图片描述

C

注意到所有区间最后会化为一个数,过程中每有大于等于10的数,计数+1

所以可以直接将区间求和,下取整除10即可。

#include<bits/stdc++.h>
using namespace std;const int maxn = 1e5+10;
const int duan = 32*(1<<1)-(1<<5);
int n;
int a[maxn];
int pre[maxn];void init()
{pre[1] = a[1];for(int i=2;i<=n;++i) pre[i] = pre[i-1] + a[i];
}int main()
{ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;++i){cin>>a[i];}init();int q;cin>>q;while(q--){int l,r;cin>>l>>r;cout<<(pre[r] - pre[l-1] )/10<<endl;//cout<<l<<" "<<r<<endl;}return 0;
}

D1

直观感觉,有度数为2的点,就不能任意构造,因为该点相连的两个边的权值一定相同。

要证明的是,为什么只要没有度数为2的点,就能构造出任意权值组合。见官方题解

#include<bits/stdc++.h>
using namespace std;const int maxn = 1e5+10;int n;
int du[maxn];int main()
{ios::sync_with_stdio(false);cin>>n;int nn=n;int a,b;n--;while(n--){cin>>a>>b;du[a]++;du[b]++;}bool flag=0;for(int i=1;i<=nn;++i){if(du[i]==2){cout<<"NO"<<endl;return 0;}}cout<<"YES"<<endl;return 0;
}

D2

给你一颗无根树,边权都不相同(且均为偶数),问如何通过每次选两个叶子节点并对路径+数,来构造所有边权.

注意D1中+的数可以是任意实数,而D2是整数.

首先,我们证明D1中为什么可以任意构造(只要度不为2),

一个性质:对于树中的任意一个点 v v v到一个叶子节点 u u u的路径,我可以只改变他们的权值(使之都+x),而其他边上的权值都不变.具体来说,有两种情况.

  1. v是另外一个叶子节点,显然满足

  2. v不是叶子节点,则其度数一定>2,(2不可能,因为直接令相关的两条边权值不同,就构造不了)

    由于其度数>2,则至少对应3颗子树. 我们分别找三颗子树中的三个叶子,记为 l 1 , l 2 , u l_1, l_2, u l1,l2,u.

    则对 u − &gt; l 1 u-&gt;l_1 u>l1 加上 x / 2 x/2 x/2 , 对 u − &gt; l 2 u-&gt;l_2 u>l2加上 x / 2 x/2 x/2, l 1 − &gt; l 2 l_1-&gt; l_2 l1>l2减去 x / 2 x/2 x/2 ,

    最后相当于对 u − &gt; v u-&gt;v u>v 加上了 x x x . #

有了上面这个性质,继续说明如何构造任意情况.

在这里插入图片描述

solve(v):

if v v v doesn’t have sons, then return.

otherwise, for each son u u u we wiil find a leaf in subtree of u u u — let’s name it w w w. Than, add a u v a_{uv} auv on the path
v w vw vw and recalculate needed numbers on the edge in this path(it means for each edge e e e on the path make this a e − = a u v a_e -= a_{uv} ae=auv),
after it, call solve( u u u).

非要这样递归维护下面的边权吗? 其实一条边,可以直接用两次上述性质做个差分(注意到,能用性质的前提是权值为偶数)即可凑成.(差一条边的两条路径)

所以先预处理出每个点的叶子节点即可.时间复杂度 O ( n ) O(n) O(n).

#include<bits/stdc++.h>
using namespace std;const int maxn = 1e3+10;int a[maxn],root;// fa[root] = 0
pair<int,int> b[maxn];//two leaf for every node
vector<pair<int,int>> G[maxn];void dfs(int u, int fa){if(G[u].size()==1 && fa){// leaf  返回自己的编号b[u].first = u;//自己指向自己b[u].second = -1;//标记return ;}for(int i=0;i<G[u].size();++i){int v = G[u][i].first;if(v == fa) continue;dfs(v, u);if(!b[u].first) b[u].first = b[v].first;else if(!b[u].second) b[u].second = b[v].first;}
}void dfs2(int u, int fa){if(G[u].size()==1) return ;for(int i=0;i<G[u].size();++i){if(G[u][i].first == fa) continue;int v = G[u][i].first;int val = G[u][i].second;//u->v valint l1 = b[u].first;int l2 = b[u].second;assert(l1!=l2);if(b[v].first == l1 || b[v].first == l2){//将l1 或 l2换掉if(u == root){//如果是根至少有三个值 一定能找到for(int j=0;j<G[u].size();++j){if(b[G[u][j].first].first!= l1 && b[G[u][j].first].first!=l2){if(b[v].first == l1) l1 = b[G[u][j].first].first;if(b[v].first == l2) l2 = b[G[u][j].first].first;break;}}}else{//u不是根 则fa一定有另一个兄弟 取他的叶子for(int j=0;j<G[fa].size();++j){if(G[fa][j].first ==u ) continue;if(b[G[fa][j].first].first != l1 && b[G[fa][j].first].first != l2){if(b[v].first == l1) l1 = b[G[fa][j].first].first;if(b[v].first == l2) l2 = b[G[fa][j].first].first;break;}if(b[G[fa][j].first].second != l1 && b[G[fa][j].first].second != l2){if(b[v].first == l1) l1 = b[G[fa][j].first].second;if(b[v].first == l2) l2 = b[G[fa][j].first].second;break;}}}}cout<<b[v].first<<" "<<l1<<" "<<val/2<<endl;cout<<b[v].first<<" "<<l2<<" "<<val/2<<endl;cout<<l1<<" "<<l2<<" "<<-val/2<<endl;//v 不是叶子if(G[v].size()!=1){//取 l1 b[v].first  和 b[v].secondcout<<b[v].first<<" "<<l1<<" "<<-val/2<<endl;cout<<b[v].first<<" "<<b[v].second<<" "<<-val/2<<endl;cout<<l1<<" "<<b[v].second<<" "<<val/2<<endl;}dfs2(v,u);}
}int main()
{//freopen("in.txt","r",stdin);ios::sync_with_stdio(false);int n,leanum=0;cin>>n;for(int i=0;i<n-1;++i){int u,v,val;cin>>u>>v>>val;G[u].push_back(make_pair(v,val));G[v].push_back(make_pair(u,val));}for(int i=1;i<=n;++i) if(G[i].size()==2) {cout<<"NO"<<endl;return 0;}if(n==2){cout<<"YES"<<endl;cout<<"1"<<endl;cout<<"1 2 "<<G[1][0].second<<endl;return 0;}//找一个du>1的node作为根for(int i=1;i<=n;++i) if(G[i].size()>2){root = i ;break;}dfs(root, 0);//for(int i=1;i<=n;++i) cout<<b[i].first<<" "<<b[i].second<<endl;for(int i=1;i<=n;++i) if(G[i].size()==1) leanum++;cout<<"YES"<<endl;cout<<6*(n-1) - 3*leanum<<endl;dfs2(root, 0);return 0;
}

这题写的我很难受,估计写复杂了. 我是先记录下每个点可能的两个叶子 (属于不同的子树)

然后各种判 先这样把 不改了…

E

find how many pairs satisfy below :
( a i + a j ) ( a i 2 + a j 2 ) ≡ k &VeryThinSpace; m o d &VeryThinSpace; p (a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p (ai+aj)(ai2+aj2)kmodp

比赛的时候不会。看题解发现是个水题 /(ㄒoㄒ)/~~ 数学直觉不好

问题的难点在于转化,于是往原根方向想,可是没有思路。

实际上,只要两边同乘以 a i − a j a_i - a_j aiaj就可以继续操作了。

a i 4 − a j 4 ≡ k ∗ ( a i − a j ) a_i^4 - a_j^4 \equiv k*(a_i - a_j) ai4aj4k(aiaj)

a i 4 − k ∗ a i ≡ a j 4 − k ∗ a j m o d p a_i^4 - k*a_i \equiv a_j^4 - k*a_j \quad mod \ p ai4kaiaj4kajmod p

发现式子两边都只和一个数有关了 ,于是对之前的 a a a数组做对应的操作后,看有多少数对在 m o d p mod \ p mod p的意义下是相同的即可。 用map即可

#include<bits/stdc++.h>
using namespace std;const int maxn = 3e5+10;int n,k,p;int a[maxn];
unordered_map<int, int> mp;
int main()
{ios::sync_with_stdio(false);cin>>n>>p>>k;for(int i=0;i<n;++i){long long t;cin>>t;a[i] = t*t%p*t%p*t%p;a[i] = ((a[i] - k*t)%p + p)%p;}long long ans=0;for(int i=0;i<n;++i){int t = mp[a[i]];ans+=t;mp[a[i]] = t+1;}cout<<ans<<endl;return 0;
}

F

题目意思是,给你一个数组a[],那么他又很多子序列对吧.

我们定义一个子序列的价值是, m i n ∣ a i − a j ∣ , i ≠ j min|a_i -a_j|, \ i \neq j minaiaj, i̸=j

求数组中所有长度为 k k k的子序列的价值和

数组长度1e3 ,值域1e5

思路

考虑怎么转化这个问题, 发现这个价值是变得,不太好dp

我们定义 p i p_i pi 为数组中,价值$\geq i $的子序列数目(即至少为i),

那么,可以说 p 1 + p 2 + p 3 + . . . + p m a x ( a ) p_1 + p_2 + p_3 +...+p_{max(a)} p1+p2+p3+...+pmax(a) 即为所求. (没有 P 0 P_0 P0,是因为其)

为什么呢?有一种前缀和的思想在里面.

比如数组中有一些子序列的价值为3,那么他们最后对答案的贡献是 数量*3

看上面的式子, p 1 , p 2 , p 3 p_1 , p_2, p_3 p1,p2,p3 中肯定包含有这些价值为3的序列. 也是3个 (对其他价值的序列同理)

那现在还有两个问题:

  1. 如何求 p i p_i pi

    d p [ i ] [ j ] dp[i][j] dp[i][j] 表示以第 i i i个数结尾,长度为 j j j 且满足价值至少为 l i m i t limit limit 的序列数量.

    转移: 从 d p [ j − 1 , j , . . . i − 1 ] [ j − 1 ] dp[j-1,j,...i-1][j-1] dp[j1,j,...i1][j1] 转移过来 第一感觉时间复杂度 O ( n 2 k ) O(n^2 k ) O(n2k)

    考虑对原数组排序,不影响答案.(原先要任意挑出一对 , 排序前 排序后看成双射即可)

    如果数组是有序的,对于 d p [ . . i − 1 , i , i + 1.. ] [ j ] dp[..i-1,i,i+1..][j] dp[..i1,i,i+1..][j] 他们的转移有公共部分.

    具体来说,是单调的 所以对同一列的 d p dp dp值,可以维护一个now指针,表示最靠右的数 且满足 a [ n o w ] + l i m i t &lt; = a [ i ] a[now]+limit&lt;=a[i] a[now]+limit<=a[i]

    当i+1了,再尽量让now变大 , 时间复杂度为 O ( n k ) O(nk) O(nk)

  2. 时间复杂度

    再加上一开始的Limit的枚举,复杂度为 O ( m a x ( a ) ∗ n ∗ k ) O(max(a)*n*k) O(max(a)nk)

    考虑真的要 d p dp dp m a x ( a ) max(a) max(a) 次吗?

    假设当前 l i m i t = x limit = x limit=x, 则从 a [ 1 ] a[1] a[1] a [ k ] a[k] a[k] 至少增加了 ( k − 1 ) ∗ x (k-1)*x (k1)x 而对于数组 a a a ,提供的最大增量为 a [ n ] − a [ 1 ] a[n]-a[1] a[n]a[1] (排序后). 因此只要对 ( k − 1 ) ∗ x ≤ a [ n ] − a [ 1 ] (k-1) *x \leq a[n] - a[1] (k1)xa[n]a[1]的那些 x x x ,求 p x p_x px 而更大的 x x x ,显然 p x = 0 p_x = 0 px=0 .

    时间复杂度为 O ( m a x ( a ) ( k − 1 ) ∗ n k ) = O ( m a x ( a ) ∗ n ) O({max(a) \over (k-1)} * nk) = O(max(a) * n) O((k1)max(a)nk)=O(max(a)n) 可以跑完.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int k,n;
const int maxn = 1e3+10;
const int mod = 998244353;
int a[maxn];
int dp[maxn][maxn];//dp[i][len] 以第i个数结尾 长度为len的序列 (且满足价值最小比某个下界大于等于)的数量int solve(int limit)
{for(int j=2;j<=k;++j){//后面每一列int now_v = 0, now_i = j-2;for(int i=j;i<=n;++i){while( a[now_i+1]+limit<=a[i]  && now_i+1 < i){//先维护now_i 看最右能到哪now_i++;now_v=now_v + dp[now_i][j-1];if(now_v > mod) now_v-=mod;}dp[i][j]=now_v;}}int ans = 0;for(int i=k;i<=n;++i) ans = (ans + dp[i][k] >= mod) ? ans+dp[i][k] - mod : ans + dp[i][k];return ans;
}int main()
{//freopen("in.txt","r",stdin);ios::sync_with_stdio(false);cin>>n>>k;for(int i=1;i<=n;++i) cin>>a[i];sort(a+1,a+1+n);int ans = 0;for(int i=1;i<=n;++i) dp[i][1] = 1;    //第一列for(int i=1;i<=(a[n] - a[1])/(k-1);++i) ans = (ans + solve(i))%mod;cout<<ans<<endl;return 0;
}

这篇关于cf #572 div2 solution (RW personal)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/196420

相关文章

cf 164 C 费用流

给你n个任务,k个机器,n个任务的起始时间,持续时间,完成任务的获利 每个机器可以完成任何一项任务,但是同一时刻只能完成一项任务,一旦某台机器在完成某项任务时,直到任务结束,这台机器都不能去做其他任务 最后问你当获利最大时,应该安排那些机器工作,即输出方案 具体建图方法: 新建源汇S T‘ 对任务按照起始时间s按升序排序 拆点: u 向 u'连一条边 容量为 1 费用为 -c,

CF 508C

点击打开链接 import java.util.Arrays;import java.util.Scanner;public class Main {public static void main(String [] args){new Solve().run() ;} }class Solve{int bit[] = new int[608] ;int l

AtCoder Beginner Contest 370 Solution

A void solve() {int a, b;qr(a, b);if(a + b != 1) cout << "Invalid\n";else Yes(a);} B 模拟 void solve() {qr(n);int x = 1;FOR(i, n) FOR(j, i) qr(a[i][j]);FOR(i, n) x = x >= i ? a[x][i]: a[i][x];pr2(

【CF】C. Glass Carving(二分 + 树状数组 + 优先队列 + 数组计数)

这题简直蛋疼死。。。。。 A了一下午 #include<cstdio>#include<queue>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 200005;int h,w,n;int C1[maxn],C2[maxn];int

【CF】E. Anya and Cubes(双向DFS)

根据题意的话每次递归分3种情况 一共最多25个数,时间复杂度为3^25,太大了 我们可以分2次求解第一次求一半的结果,也就是25/2 = 12,记录结果 之后利用剩余的一半求结果 s-结果 = 之前记录过的结果 就可以 时间复杂度降低为 3 ^ (n/2+1) 题目链接:http://codeforces.com/contest/525/problem/E #include<set

【CF】D. Arthur and Walls(BFS + 贪心)

D题 解题思路就是每次检查2X2的方格里是否只有一个‘*’,如果有的话这个*就需要变成‘.’,利用BFS进行遍历,入队的要求是这个点为. 一开始将所有的'.'全部加入队列,如果碰到一个'*'变成'.'就入队,判断的时候从4个方向就行判断 题目链接:http://codeforces.com/contest/525/problem/D #include<cstdio>#include<

CF#271 (Div. 2) D.(dp)

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/474/problem/D We s

CF Bayan 2015 Contest Warm Up B.(dfs+暴力)

B. Strongly Connected City time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/probl

CF Bayan 2015 Contest Warm Up A.(模拟+预处理)

A. Bayan Bus time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/475/problem/A The fi

CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造)

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/B There