B. Number Circle
题意:环形排列给定的数列,使得每个数小于 它相邻的两个数之和。
先安排好最大的数,只有在它两边放第二,第三大的数才可能满足。接着把整个数列剩下的数从大到小放就好了,由于每个数一定与某个比它大的数相邻,所以一定满足条件。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<ll, ll> pii;const int INF = 0x3f3f3f3f ;const int maxn = 1e5 + 10 ;int n;int a[maxn];int main () { scanf ("%d" , &n); for (int i = 0 ; i < n; i++)scanf ("%d" , &a[i]); sort (a, a + n); swap (a[n-1 ], a[n-2 ]); for (int i = 0 ; i < n; i++) { if (a[i] + a[(i + 2 ) % n] <= a[(i + 1 ) % n]) { puts ("NO" ); return 0 ; } } puts ("YES" ); for (int i = 0 ; i < n; i++)printf ("%d%s" , a[i], (i == n - 1 ? "\n" : " " )); return 0 ; }
D. Add on a Tree
题意:给定一棵树,每次操作可以选两个叶子,把他们的路径上所有边加x,问是否能通过不断操作,使得所有边呈任意值。
如果有一个点的度为2,他所连的两条边的值不管怎样一定相同,这时就不能为任意值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<int , int > pii;const int INF = 0x3f3f3f3f ;const int maxn = 2e5 + 10 ;int n;int d[maxn];int main () { scanf ("%d" , &n); for (int i = 1 ; i < n; i++) { int u, v; scanf ("%d%d" , &u, &v); d[u]++; d[v]++; } for (int i = 1 ; i <= n; i++) { if (d[i] == 2 ) { puts ("NO" ); return 0 ; } } puts ("YES" ); return 0 ; }
E. Add on a Tree: Revolution
题意:上一题的加强版,给定每条边的边权,要求给出操作,使得最终形成这种情况。保证边的值一定为偶数。
其实看到保证为偶数就应该想到把边权除2。
首先判断是否能做到,由上一题,度为2的点连的两条边值必须相等,否则不行。
以下可以假设一条全是度为2的点的链缩为一条边,则所有点要么是叶子,要么度大于等于3。枚举每一条边,两个端点一定还各自连着另外两个叶子设为Lx,Ly;Rx,Ry.则从Lx到Rx,再从Ly到Ry路径加边权/2,再从Lx到Ly,从Rx到Ry路径减边权/2,就只有这条边的值改变,其它边不受影响,可以对每条边这样处理。
再考虑度为2的链,对链上某一个边处理,就把其他边都处理到了,所以一条链上最多只能处理一条边,所以每次处理完向两端拓展,保证链上都标记完。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<int , int > pii;const int INF = 0x3f3f3f3f ;const int maxn = 1010 ;int n;vector<int >G[maxn]; vector<pii>edges; int w[maxn][maxn], vis[maxn], used[maxn][maxn];int dfs (int u, int _fa) { vis[u] = 1 ; if ((int )G[u].size () == 1 )return u; for (int v : G[u]) { if (v == _fa || vis[v])continue ; return dfs (v, u); } } void pre (int u, int _fa) { used[u][_fa] = 1 ; if ((int )G[u].size () != 2 )return ; for (int v : G[u]) { if (u == _fa)continue ; pre (v, u); } } struct X { int u, v, w; }; vector<X>ans; int main () { scanf ("%d" , &n); for (int i = 1 ; i < n; i++) { int u, v, ww; scanf ("%d%d%d" , &u, &v, &ww); w[u][v] = w[v][u] = ww; G[u].push_back (v); G[v].push_back (u); edges.push_back (pii (u, v)); } for (int i = 1 ; i <= n; i++) { if ((int )G[i].size () == 2 && w[i][G[i][0 ]] != w[i][G[i][1 ]]) { puts ("NO" ); return 0 ; } } puts ("YES" ); for (pii e : edges) { int u = e.first, v = e.second; if (used[u][v])continue ; fill (vis + 1 , vis + n + 1 , 0 ); int Lx = dfs (u, v); int Ly = dfs (u, v); int Rx = dfs (v, u); int Ry = dfs (v, u); ans.push_back (X{ Lx,Rx,w[u][v] / 2 }); ans.push_back (X{ Ly,Ry,w[u][v] / 2 }); if (Lx != Ly)ans.push_back (X{ Lx,Ly,-w[u][v] / 2 }); if (Rx != Ry)ans.push_back (X{ Rx,Ry,-w[u][v] / 2 }); pre (u, v); pre (v, u); } printf ("%d\n" , (int )ans.size ()); for (X p : ans)printf ("%d %d %d\n" , p.u, p.v, p.w); return 0 ; }
F. Count Pairs
题意:给定一列数和质数 p p p ,求满足 ( a i + a j ) ( a i 2 + a j 2 ) ≡ k m o d p (a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p ( a i + a j ) ( a i 2 + a j 2 ) ≡ k mod p 的数对个数。
左边这个式子明明去年还在初中题里见过。。
主要是要把 i i i 和 j j j 分开来。
两边乘以 a i − a j a_i-a_j a i − a j ,化简,( a i 4 − k a i ) − ( a j 4 − k a j ) ≡ 0 m o d p (a_i^4-ka_i)-(a_j^4-ka_j)\equiv 0\bmod p ( a i 4 − k a i ) − ( a j 4 − k a j ) ≡ 0 mod p ,则 ( a i 4 − k a i ) m o d p = ( a j 4 − k a j ) m o d p (a_i^4-ka_i)\bmod p=(a_j^4-ka_j)\bmod p ( a i 4 − k a i ) mod p = ( a j 4 − k a j ) mod p
算出每个模,放进map里,最后算即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<int , int > pii;const int INF = 0x3f3f3f3f ;const int maxn = 2e5 + 10 ;int n;ll p, k; map<ll, int >mp; ll ans; int main () { scanf ("%d%lld%lld" , &n, &p, &k); for (int i = 1 ; i <= n; i++) { ll u; scanf ("%lld" , &u); ll x = u; for (int j = 0 ; j < 3 ; j++)x = x * u%p; ll tmp = x - k * u%p; while (tmp < 0 )tmp += p; tmp = tmp % p; mp[tmp]++; } for (auto it : mp) { ans += it.second*(it.second - 1 ) / 2 ; } cout << ans << endl; return 0 ; }
G. Array Beauty
题意:定义数组的beauty为差值最小的两个数的差值 min 1 ≤ i < j ≤ n ∣ a i − a j ∣ \min\limits_{1 \leq i < j \leq n} |a_i - a_j| 1 ≤ i < j ≤ n min ∣ a i − a j ∣ 。求给定数组的所有长度为 k k k 的子序列的beauty之和。
显然不能直接算,还是要枚举每个beauty值的贡献。
问题就是求 ∑ b e a u t y = 1 M A X I b e a u t y ⋅ n u m O f B e a u t y \sum_{beauty=1}^{MAXI}beauty\cdot numOfBeauty ∑ b e a u t y = 1 M A X I b e a u t y ⋅ n u m O f B e a u t y ,可以发现还能变为 ∑ b e a u t y = 1 M A X I f [ b e a u t y ] \sum_{beauty=1}^{MAXI}f[beauty] ∑ b e a u t y = 1 M A X I f [ b e a u t y ] ,其中 f [ b e a u t y ] f[beauty] f [ b e a u t y ] 为长度为 k k k ,beauty 大于等于 i i i 的子序列个数。
接下来dp求 f [ b e a u t y ] f[beauty] f [ b e a u t y ] 。
由于是求差值,所以其实与顺序无关,所以先排个序。
d p [ i ] [ j ] dp[i][j] d p [ i ] [ j ] 表示子序列最后一个数为第 i i i 个数,序列长度为 j j j 的序列数。
则 d p [ i ] [ j ] = ∑ a i − a k ≥ b e a u t y d p [ k ] [ j − 1 ] dp[i][j]=\sum_{a_i-a_k\geq beauty}dp[k][j-1] d p [ i ] [ j ] = ∑ a i − a k ≥ b e a u t y d p [ k ] [ j − 1 ] 。
对于每一个长度 j j j ,每一次算 d p [ i ] [ j ] dp[i][j] d p [ i ] [ j ] 都是算第 j − 1 j-1 j − 1 层的一个前缀的和。所以可以外层循环 j j j ,这样每一层都可以通过一次遍历处理完所有的 i i i 。
还有另一种dp方法是 d p [ i ] [ j ] dp[i][j] d p [ i ] [ j ] 只是表示处理到第 i i i 个数,长度为 j j j ,并不一定选第 i i i 个数,所以要分取/不取考虑,并且取的话也只要加上 d p [ k ] [ j ] dp[k][j] d p [ k ] [ j ] 其中 k k k 为最后一个满足 a [ i ] − a [ k ] ≥ b e a u t y a[i]-a[k]\geq beauty a [ i ] − a [ k ] ≥ b e a u t y 的数。即 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ k ] [ j − 1 ] dp[i][j]=dp[i-1][j]+dp[k][j-1] d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ k ] [ j − 1 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<int , int > pii;const int INF = 0x3f3f3f3f ;const int maxn = 1e5 + 10 ;const int mod = 998244353 ;int n, k;int a[maxn];int MAX;ll ans; ll dp[1010 ][1010 ]; int main () { scanf ("%d%d" , &n, &k); for (int i = 1 ; i <= n; i++)scanf ("%d" , &a[i]), MAX = max (MAX, a[i]); sort (a + 1 , a + n + 1 ); for (int i = 1 ; i <= n; i++)dp[i][1 ] = 1 ; for (int x = 1 ; x <= MAX / (k - 1 ); x++) { for (int j = 2 ; j <= k; j++) { ll sum = 0 ; int now = 1 ; for (int i = 2 ; i <= n; i++) { while (now < i&&a[i] - a[now] >= x) { sum = (sum + dp[now][j - 1 ]) % mod; now++; } dp[i][j] = sum; } } for (int i = 1 ; i <= n; i++)ans = (ans + dp[i][k]) % mod; } cout << ans << endl; return 0 ; }
M. Consecutive Subsequence
题意:给定一个数列,求满足递增,且每次递增1的最长子序列。
直接dp数值,d p [ i ] dp[i] d p [ i ] 表示末尾数值为 i i i 的子序列最长长度,然后从前向后在原数组里找这一串数,用map存dp数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<int , int > pii;const int INF = 0x3f3f3f3f ;const int maxn = 2e5 + 10 ;int n;int a[maxn];map<int , int >mp; int main () { scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) { scanf ("%d" , &a[i]); if (!mp.count (a[i]-1 ))mp[a[i]] = 1 ; else mp[a[i]] = mp[a[i] - 1 ] + 1 ; } int mx = -1 , mxid = -1 ; for (auto p : mp) { if (mx < p.second) { mx = p.second; mxid = p.first; } } int st = mxid - mx + 1 ; printf ("%d\n" , mx); for (int i = 1 ; i <= n; i++) { if (a[i] == st)printf ("%d%s" , i, a[i] == mxid ? "\n" : " " ), st++; } return 0 ; }