天津网站设计推荐刻,为什么做域名跳转网站样式不见了,免费推广平台有哪些?,网页设计工作内容怎么写传送门 这些天风也温柔#xff0c;题也温柔 开车啦#xff01; 文章目录A1#xff1a;Add on a Tree题意翻译题解证明代码实现B#xff1a;Count Pairs题意翻译题解代码实现C#xff1a;Array Beauty题目描述题解代码实现A1#xff1a;Add on a Tree
题意翻译
给定一棵…传送门 这些天风也温柔题也温柔 开车啦 文章目录A1Add on a Tree题意翻译题解证明代码实现BCount Pairs题意翻译题解代码实现CArray Beauty题目描述题解代码实现A1Add on a Tree
题意翻译
给定一棵树树上的边权初始为0你可以在任意两个叶子之间的简单路径上的边上加上一个权值实数x。问能否在有限次数的操作内得到边权任意组合的树。 题目描述 Note that this is the first problem of the two similar problems. You can hack this problem only if you solve both problems. You are given a tree with n n nodes. In the beginning, 0 is written on all edges. In one operation, you can choose any 2 distinct leaves u , v and any real number x and add x x to values written on all edges on the simple path between u and v . For example, on the picture below you can see the result of applying two operations to the graph: adding 2 on the path from 7 to 6 , and then adding −0.5 on the path from 4 to 5 . Is it true that for any configuration of real numbers written on edges, we can achieve it with a finite number of operations? Leaf is a node of a tree of degree 1 . Simple path is a path that doesn’t contain any node twice. 输入格式 The first line contains a single integer n n ( 2≤n≤10^5) — the number of nodes. Each of the next n−1 lines contains two integers u and v (1≤u,v≤n , u≠v ), meaning that there is an edge between nodes u and v. It is guaranteed that these edges form a tree.
输出格式 If there is a configuration of real numbers written on edges of the tree that we can’t achieve by performing the operations, output “NO”. Otherwise, output “YES”.
You can print each letter in any case (upper or lower). 输入输出样例 输入 2 1 2 输出 YES 输入 3 1 2 2 3 输出 NO 输入 5 1 2 1 3 1 4 2 5 输出 NO 输入 6 1 2 1 3 1 4 2 5 2 6 输出 YES 说明/提示 In the first example, we can add any real x x to the value written on the only edge (1, 2) In the second example, one of configurations that we can’t reach is 0 0 written on (1, 2) and 1written on(2,3) . Below you can see graphs from examples 3 , 4 :
题解
首先看这个题目大意你可能会被吓到这题这么难但是你想这可是CF第一题啊 那么一定是水题而这道题就是一个神仙结论题
如果有一个点只连了两条边就一定是输出NO没有就输出YES
我当时知道后一脸懵逼
证明
后来拿着数据慢慢推又发现自己脑子不行我们还是假设未知数来推吧 首先如果这是一条单链我们也能将它变为一个二叉树 接下来的讨论情况是在不是单链的前提下进行的
因为是要两个叶子节点彼此间的路径全都加上或减去x一定会经过它们的lca 所以我们要以lca来进行讨论 也可以这么理解把它们的lca和lca的子树单独抠出来考虑让lca成为根节点
设i点连的边数为edge 1edge 1意味着i点是叶子节点不考虑特殊情况输出YES如样例1 2edge 2如图 如果这两条边的边权要求不一样就无法完成 因为加权或减权都要选择两个不同的叶子节点 而lca只有这两个叶子节点也就是说这两个点的边只能一起加一起减 自然也就组合不出不同的边权了
3edge3如图 因为要组合成任意边权所以357与537本质上木有区别 所以我们就假设要满足的边权ijk 1ijk直接ik和jk就能完成 2ijk,首先一三点都加上i和二三点jk都加上j此时第三个点还差k-i-j 如果差的是奇数 那么第一二个点就分别与他组合k-i-j*1.0 / 2 再一二个点组合减去k-i-j*1.0/ 2即可满足 如果差的是偶数 那么第一二个点就分别与他组合k-i-j/ 2 再一二个点组合减去k-i-j/ 2也可满足 PS加减实数即有理数所以也可以加减无限循环或有限小数 3ijk与情况二差不多 首先一三点都加上i和二三点jk都加上j此时第三个点多了k-i-j 如果多的是奇数 那么第一二个点就分别与他组合减掉k-i-j*1.0 / 2 再一二个点组合加上k-i-j*1.0/ 2即可满足 如果差的是偶数 那么第一二个点就分别与他组合减掉k-i-j/ 2 再一二个点组合加上k-i-j/ 2也可满足
综上当叶子节点个数为3时一定能凑出任何边权
4当edge4时 1ijkl坑定可以满足不多说 2ijkl首先iljlkl分别组合先让l满足就不用再考虑l了 于是就转换成了让ijk三个满足边权我们已经证明过了三个的时候一定成立 所以这个情况也一定成立 3ijkl与情况2一样先让l满足后就不考虑l转换成三个叶子节点的情况 所以此情况也一定成立
5以此类推edge3的时候就依次让edgeedge-1edge-2满足要求不再考虑 最后都能转换成edge3的情况 所以edge3也是一定可以组合出任意边权
所以综上所述只有edge2的时候会组合不出任意边权输出NO否则YES 好了证明完了这道题发挥了它该有的价值我也心安理得了
代码实现
这是个水题代码量自然也就不会那么ex主要是寡人刚开始没把这个英文题意搞懂
#include cstdio
#define MAXN 100005
int n;
int du[MAXN];
int main() {scanf ( %d, n );for ( int i 1;i n;i ) {int u, v;scanf ( %d %d, u, v );du[u] ;du[v] ;}for ( int i 1;i n;i )if ( du[i] 2 )return ! printf ( NO );printf ( YES );return 0;
}BCount Pairs
题意翻译
给定一个质数 p , 一个长度为 n 的序列 a1,a2,…,an和一个整数 k. 求所有数对 (i, j) (1≤i,j≤n) 中满足 (ai aj) * (ai^2 aj^2 ) ≡k mod p.的个数.
题目描述 You are given a prime number p , n integers a1, a2…an and an integer k . Find the number of pairs of indexes (i, j)(1≤ij≤n) for which (aiaj)(ai^2 aj^2) ≡k mod p . 输入格式 The first line contains integers n, p, k ( 2≤n≤3⋅10^5, 2≤p≤10^9,0≤k≤p−1 ). p is guaranteed to be prime. The second line contains n integers a1, a2,…,a n,0≤ai≤p−1 ). It is guaranteed that all elements are different. 输出格式 Output a single integer — answer to the problem. 输入输出样例 输入 3 3 0 0 1 2 输出 1 输入 6 7 2 1 2 3 4 5 6 输出 3 说明/提示 In the first example: (01)(0^2 1^2) 1 ≡ 1 mod 3 . (02)(0^2 2^2) 8 ≡ 2 mod 3 . (12)(1^2 2^2) 15 ≡ 0 mod 3 . So only 1 pair satisfies the condition. In the second example, there are 3 3 such pairs: (1, 5) , (2, 3), (4, 6) .
题解
首先要知道n的范围很大这就告诉我们时间复杂度控制在On 尽管这个时间开的是4sn^2也不是我们想要的好代码 那么我们就要式子进行变换而且看到同余就知道是数论也就要用到数学 (ai aj) * (ai^2 aj^2 ) ≡k mod p 因为p是质数所以左右两边同时乘以ai-aj等式仍然成立 即aiaj)(ai-aj)(ai^2 aj^2) %p ≡ k(ai-aj)%p 即(ai^2 - aj^2) (ai^ aj^2) % p ≡ k(ai-aj) %p 即(ai^4 - aj^4)%p ≡(aik - ajk) %p 移向即
(ai^4-aik) %p ≡ (aj^ajk)% p
我们设f(x)表示(ax^4-axk) %pkp都是一定的 所以我们可以在输入ai的时候就处理出每一个f(x)
之后我们只需要找到有多少个与f(x)同余的即可ij与ji算一个 我们不能用两重循环去找因为会TLE所以我们可以sort一下保持它的单调性这样就可以在一重循环内进行答案计算
答案每次应该加多少呢我们来想如果有n个同余的数 那么第一个数与后面的组合个数为n-1第二个数与后面的组合个数为n-2以此类推 最后一个后面没数组合数为0 就可以列出公式012…n-2n-1也就是我们的等差数列求和公式 好了话不多说屁不多放上马
代码实现
终于本仙女没有在mod上怀疑人生了我很欣慰
#include cmath
#include cstdio
#include algorithm
using namespace std;
#define MAXN 300005
#define LL long long
int n, p;
LL k, t;
LL result;
LL f[MAXN];
int main() {scanf ( %d %d %lld, n, p, k );for ( int i 1;i n;i ) {scanf ( %lld, t );//f[i] ( ( LL ) pow ( t, 4 ) % p - ( t * k ) % p p ) % p;//不要这么写炸不炸longlong全靠运气pow不会炸duoble会炸longlong//相同代码在luogu交有时会AC有时连样例数据都过不了//真玄学LL ip t * t % p * t % p * t % p;f[i] ( ip % p - ( t * k ) % p p ) % p;}sort ( f 1, f n 1 );LL cnt 1;for ( int i 2;i n;i ) {if ( f[i] f[i - 1] )cnt ;else {result ( result ( ( cnt - 1 ) * cnt / 2 ) % p ) % p;cnt 1;}}if ( cnt 1 )result ( result ( ( cnt - 1 ) * cnt / 2 ) % p ) % p;printf ( %lld, result );return 0;
}CArray Beauty
题目描述
我们称序列b 1 ,b 2 ,…,b n ( n 1 ) 的美丽值为min ∣b i −b j ∣1≤ij≤n 给你一个序列a 1 ,a 2 ,…a n 和一个数字k请您计算出长度为k的序列a的所有子序列的美丽值之和由于这个值可能很大所以输出是模998244353。 如果可以通过删除几个可能为零或全部元素从B中获得A则序列A是数组B的子序列。
输入输出格式 输入格式 第一行包含整数 ( 2≤k≤n≤1000 )。 第二行包含n个整数 a 1 ,a 2 ,…,a n ( 0≤a i ≤10^ 5 )。 输出格式 输出一个整数 — 长度为k的序列a的所有子序列的美丽值之和 由于这个值可能很大所以输出是模998244353 。
题目描述 Let’s call beauty of an array b1, b2,…,bn( n 1) —(1≤ij≤n) min∣bi−bj∣ .
You’re given an array a1, a2,…an and a number k . Calculate the sum of beauty over all subsequences of the array of length exactly k . As this number can be very large, output it modulo 998244353 .
A sequence a is a subsequence of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements.
输入格式 The first line contains integers n, k ( 2≤k≤n≤1000 ). The second line contains n integers a1, a2,…,an( 0≤a i ≤10^5 ). 输出格式 Output one integer — the sum of beauty over all subsequences of the array of length exactly k . As this number can be very large, output it modulo 998244353 . 输入输出样例 输入 4 3 1 7 3 5 输出 8 输入 5 5 1 10 100 1000 10000 输出 9 说明/提示 In the first example, there are 4 subsequences of length 3 — [1, 7, 3] [1, 3, 5] , [7, 3, 5] , [1, 7, 5] , each of which has beauty 2 , so answer is 8 .
In the second example, there is only one subsequence of length 5 — the whole array, which has the beauty equal to |10-1| 9.
题解
对于给定的数组由于不是有序的所有相连的值最小而子序列也不要求是连续的肯定要先进行排序从小到大得到一个有序的数组 这样得到的子序列也是有序的。 假设一个序列的最小值为x即a[i]−a[i−1]≥x即所有的相连数字之差都大于等于x。
如果一个我们要找序列的值为1的个数为N那么和就是1×N 如果序列的的值为2的个数为M那么和就是2×M 但是在N个序列中肯定包含值为2的M个序列 那么总的和就是N2×M−M×1NMM×1就是在值为1中重复的个数容斥思想 这样我们就可以发现我们从小到大连续 的序列的值就是将他们的序列个数相加。
用动态规划DP的思想 dp[i][len] 其中i表示第i个数组加入序列len表示此时序列的长度为len 那么dp[i][len] 就表示第i个数字加入长度为len的子序列的个数。
假设此时序列的最小值为x 那么对于第i个数字如果它不加入序列那么此时就可以表示为 dp[i][len]dp[i−1][len] 如果加入序列那么我们需要找到一个位置让a[i]−a[j]≥x1≤j≤last dp[i][len]dp[last][len−1]
综上
dp[i][len]dp[i−1][len]dp[last][len−1]
最后对于序列最小值为x得到的序列个数就是dp[n][k]由于这个值和x有关记为f(x) 那么最终的结果就是
result∑x(1,10^5/(k-1))*f(x)
所以这道题就是一个简单 dp 代码实现
这里解释两个地方 1result求解的for循环的取值范围 首先i模拟的是美丽值那么有长度为k的序列为了维护序列中最小的美丽值为i 最大的一个数应该是i*(k-1)因为i占第一个所以是乘以k-1 而且每一个a都不能超过100000所以条件是这个序列的最后一个的值MAX
2)为什么last是与i满足条件的最接近与i的下标 dp[i][j]是i进入序列和i不进入序列的情况数总和 那么dp[i-1][j-1]也包含了i-1进入序列和i-1不进入序列情况的总和 所以如果是加上dp[i-1][j-1] 也包含了i直接略过last接在前面任何一个与i满足美丽值要求的方案总数
如果不这样写就要再用一重循环去模拟前面所有与i组合合法的j再累加
#include cstdio
#include algorithm
using namespace std;
#define mod 998244353
#define LL long long
#define MAXN 1005
#define MAX 100000
int n, k;
int a[MAXN];
LL dp[MAXN][MAXN];
LL result;int beauty ( int val ) {dp[0][0] 1;int last 0;for ( int i 1;i n;i ) {while ( a[i] - a[last 1] val ) last ;dp[i][0] dp[i - 1][0];for ( int j 1;j k;j )dp[i][j] ( dp[i - 1][j] dp[last][j - 1] ) % mod;}return dp[n][k];
}int main() {scanf ( %d %d, n, k );;for ( int i 1;i n;i )scanf ( %d, a[i] );sort ( a 1, a n 1 );for ( int i 1;i * ( k - 1 ) MAX;i )result ( result beauty ( i ) ) % mod;printf ( %lld, result );return 0;
}好了你左丢一个表情包右丢一个表情包闪现收人头 今天的节目到此结束有任何问题欢迎留言也可以留下你的想法和思路 帮助博主完善这份博客小朋友。我们下期再见哦~~
