J. Sum Plus Product
题意:
给定一个长度为n的数组,每次随机拿出两个数使其变成 (a + b + a * b)再放回数组,最终数组中只剩下一个数,求剩余数字的期望是多少。
分析:
模拟一下就会发现 合并的顺序并不重要
比如 a1 a2 a3 和 a3 a1 a2
两者最后答案都是 a1a2a3 + a1a2 + a2a3 + a1a3 + a1 + a2 + a3
void solve()
{
cin >> n;
for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
int last = a[1];
for(int i = 2 ; i <= n ; i ++ )
last = (last + a[i] + last * a[i] % mod) % mod;
cout << last << endl;
}
G. Matryoshka Doll
题意:
。
分析:
void slove() {
cin >> n >> k >> r;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= n; i++) {
L[i] = 0;
for (int j = i - 1; j >= 1; j--)
if (abs(a[i] - a[j]) < r) {
L[i]++;
}
}
for (int i = 0; i <= n + 2; i++)for (int j = 0; j <= n + 2; j++)dp[i][j] = 0;
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j - 1] + ((ll)dp[i - 1][j] * (j - L[i])) % mod;
dp[i][j] %= mod;
}
}
cout << dp[n][k] << endl;
}
H. Shortest Path in GCD Graph
题意:
给定一张完全图节点1-n,每两个点i, j之间的边长为gcd(i, j),有若干个询问,每次给定两个节点i和j,求i和j的最短路,以及最短路的条数。
分析:
板子题目 https://www.cnblogs.com/wzxbeliever/p/16206695.html
const int N = 1e7 + 10;
int primes[N];
bool st[N];
int minp[N];
void get_primes(int n) {
int cnt = 0;
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i, minp[i] = i;
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
minp[primes[j] * i] = primes[j];
if (i % primes[j] == 0) break;
}
}
}
namespace qjhz {
int p[100],cnt;
void prime(int n) {
cnt = 0;
while (n != 1) {
p[++cnt] = minp[n];
int pr = minp[n];
while (n%pr == 0) {
n /= pr;
}
}
return;
}
ll solve(ll r) {
ll res = 0;
for (int i = 1; i < (1 << cnt); i++) {
int kk = 0;
ll div = 1;
for (int j = 1; j <= cnt; j++) {
if (i&(1 << (j - 1))) {
kk++;
div *= p[j];
}
}
if (kk % 2)
res += r / div;
else
res -= r / div;
}
return r - res;
}
map<set<int>, int>mp;
int calc(int n, int a, int b) {
set<int>v;
prime(a);
for (int i = 1; i <= cnt; i++)v.insert(p[i]);
prime(b);
for (int i = 1; i <= cnt; i++)v.insert(p[i]);
cnt = 0;
for (int x : v) {
p[++cnt] = x;
}
if (mp.count(v))return mp[v];
return mp[v] = solve(n);
}
}
int n, m;
void slove() {
cin >> n >> m;
get_primes(n);
for (int i = 1; i <= m; i++) {
int a, b; cin >> a >> b;
if (gcd(a, b) == 1) {
cout << "1 1" << endl;
}
else if (gcd(a, b) == 2) {
int ans = qjhz::calc(n, a, b);
cout << 2 << " " << ans + 1 << endl;
}
else {
int ans = qjhz::calc(n, a, b);
cout << 2 << " " << ans << endl;
}
}
}
C. Fast Bubble Sort
题意:
分析:
单调栈 :
先考虑第一个小问题,如何找到第一次跳跃的位置?也就是第一个在右边大于自己的数,很显然这是一个基础单调栈问题,我们从后往前推一遍即可。
累计答案:
我们发现对于一个数想要往后跳,每次跳一次,我们要累积答案最简单的方法就是一直往后跳迭代下去即可。但是显然时间复杂度是不允许的,但是其实这个思路很像我们在求lca时的树上倍增的跳跃法。
树上倍增:
我们设R[i]为当前数跳跃一次能够到达的点,用单调栈即可。v[i]表示从当前位置i跳跃到终点需要的次数,我们从后往前迭代一遍即可预处理出全部数组。
for(int i = n ; i ; i -- )
{
v[i] = v[R[i]];
if(R[i] > i + 1) v[i] ++ ;
fa[i][0] = R[i];
for(int j = 1 ; j <= 20 ; j ++ )
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
和树上倍增一样的跳即可,注意如果终点没到的话说明下一次跳可能会出界,也就是答案还需要多加一次。
const int N = 1e5 + 10 , INF = 0x3f3f3f3f, mod = 998244353;
int n, m, a[N], k, r;
int stk[N], top, R[N];
int fa[N][25], v[N];
void solve()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
for(int i = 0 ; i < n + 10 ; i ++ )
for(int j = 0 ; j < 21 ; j ++ ) fa[i][j] = n + 1;
a[n + 1] = INF;
top = 0;
stk[++ top] = n + 1;
for(int i = n ; i ; i -- )
{
while(top && a[stk[top]] <= a[i]) top -- ;
R[i] = stk[top];
stk[++ top] = i;
}
v[n + 1] = 0;
for(int i = n ; i ; i -- )
{
v[i] = v[R[i]];
if(R[i] > i + 1) v[i] ++ ;
fa[i][0] = R[i];
for(int j = 1 ; j <= 20 ; j ++ )
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
for(int i = 1 ; i <= m ; i ++ )
{
int l, r;
cin >> l >> r;
int u = l;
for(int k = 20 ; k >= 0 ; k -- )
{
if(fa[u][k] <= r)
u = fa[u][k];
}
int res = v[l] - v[u];
if(r != u) res ++ ;
cout << res << endl;
}
}
先看这个题:https://uoj.ac/problem/143
题意:
给出一个的数列,将其重新排列,使得其等差子序列的数目最小。输出一种可能的排列后的数列
分析:
通过构造可以使得不存在长度为3的等差子序列。
{s, k, t} 三个数为等差,等价于:s + t = 2 * k。此时{s, t}必须是奇偶性相同的两个数。
按照奇偶性分开后,则只会在奇数或者偶数内部产生等差的三元组,此时分治。
然后又可以得到如下关系:
三个奇数{2s+1, 2k+1, 2t+1}满足:(2s + 1) + (2t + 1) = 2 * (2k + 1)
三个偶数{2s, 2k, 2t}满足:(2s) + (2t) = 2 * (2k)
上面两个式子都等价为 s + t = 2 * k,所以将所有的数整除掉2之后和原问题一样。
如果把所有奇数放到所有偶数的左面,那么就不会出现 “奇-偶-奇” 或 “偶-奇-偶” 的情况。
对于 “奇-奇-奇” 或 “偶-偶-偶” 的情况,将所有 ai 变为 ai/2不影响判断,因此将所有数除以2后重复这个过程即可。
由于一个数除以 logn 次就会变成1,因此这个过程只需要进行 logn 次。
每一层都只会处理 n 个数,时间复杂度 O(nlogn)
#include <cstdio>
int a[510] , p[510] , t[510];
void solve(int l , int r , int x)
{
if(!x || l >= r) return;
int i , b = l , e = r;
for(i = l ; i <= r ; i ++ )
{
if(a[p[i]] & 1) t[b ++ ] = p[i];
else t[e -- ] = p[i];
}
for(i = l ; i <= r ; i ++ ) a[p[i]] >>= 1 , p[i] = t[i];
solve(l , e , x - 1) , solve(b , r , x - 1);
}
int main()
{
int n , i;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , p[i] = i;
solve(1 , n , 30);
for(i = 1 ; i <= n ; i ++ ) printf("%d " , p[i]);
return 0;
}
A. Arithmetic Subsequence
分析:
根据上个题目 只要不出现三个相同的数 一定能构造出不含等差子序列的数组
构造就和上一个题目一模一样
标签:杭电多校,题意,fa,int,void,++,2022,top From: https://www.cnblogs.com/wzxbeliever/p/16722958.html