• A 签到
  • B 签到
  • C dp
    • 题意:n道题,第i道题做对的概率为 p i p_i pi,问分别做对n道题中分别做对0,1,2,3,…n道的概率。
    • 思路: d p [ i ] [ j ] i j dp[i][j]表示前i道题中对了j道的概率 dp[i][j]ij
      d p [ i ] [ 0 ] = d p [ i 1 ] [ 0 ] ( 1 p i ) dp[i][0]=dp[i-1][0]*(1-p_i) dp[i][0]=dp[i1][0](1pi)
      d p [ i ] [ j ] = d p [ i 1 ] [ j ] ( 1 p i ) + d p [ i 1 ] [ j 1 ] p i dp[i][j]=dp[i-1][j]*(1-p_i)+dp[i-1][j-1]*p_i dp[i][j]=dp[i1][j](1pi)+dp[i1][j1]pi
  • D 签到 注意判断三角形是否合法(三点共线)
  • E 签到 将原式平方+质因子分解
  • F 贪心 按照a+b降序排列即可
  • G hash 选取模数如402653189看等式两边对模数取模的结果是否相同即可
  • H
    • 题意:
    • 思路:升序排列,设遍历到i(i≥k),dp[i]表示前i个处理完之后至少需要的魔力值。
      那么 d p [ i ] = m i n 1 j i k + 1 { a [ i ] a [ j ] + d p [ j 1 ] } = a [ i ] m i n 1 j i k + 1 { d p [ j 1 ] a [ j ] } dp[i]=min_{1≤j≤i-k+1}\{a[i]-a[j]+dp[j-1]\}=a[i]-min_{1≤j≤i-k+1}\{dp[j-1]-a[j]\} dp[i]=min1jik+1{a[i]a[j]+dp[j1]}=a[i]min1jik+1{dp[j1]a[j]}且每次往下遍历一个,j范围的左边界不变,右边界只增加一个值,可以在遍历的时候处理出来。最后求得的dp[n]即答案。
  • I
    • 题意:
    • 思路:对于 v i = v j v_i=v_j vi=vj,花费为0,所以 v i = v j v_i=v_j vi=vj的点一定是相连的。假如这n个点去重后有m个不同的点,那么只需要连m-1条边,找到最低的位p,如果存在 v i v_i vi的p位为0, v j v_j vj的p位为1,那么最终的答案就是 2 p ( m 1 ) 2^p*(m-1) 2p(m1),这是由于lowbit只关系找到最后一个是1的位置,让p位上值不同的点之间相连。
      对于如何处理上述的"如果存在 v i v_i vi的p位为0, v j v_j vj的p位为1"问题呢,将所有的v相&,可以得到哪些位上的值全为1,相|可以得到哪些位上的值全为0,再将结果异或,就可以得到哪些位上的值即有0也有1了,且异或结果上该位为1。
    • ac代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
int n;
int a[maxn];
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &n);
    int x = (1<<30)-1, y = 0;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        x &= a[i];
        y |= a[i];
    }
    x ^= y;
    sort(a+1, a+1+n);
    int m = unique(a+1, a+1+n)-(a+1);
    ll ans = 0;
    for(int p = 0; p <= 30; p++)
    {
        if(x&(1<<p))
        {
            ans = (1ll<<p)*(m-1);
            break;
        }
    }
    cout << ans;
    return 0;
}
  • J
    • 题意:
    • 思路:
    • ac代码:
//题解代码,我偷懒了
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7, mod = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> pii;
int n, m, t[N << 2], t1[N << 2], k[N];
void modify(int o, int l, int r, int k, ll v, ll v1) {
  if (l == r) return t[o] = v, t1[o] = v1, void();
  int mid = (l + r) >> 1;
  if (k <= mid) modify(o << 1, l, mid, k, v, v1);
  else modify(o << 1 | 1, mid + 1, r, k, v, v1);
  t[o] = (t[o << 1] * 1ll * t[o << 1 | 1]) % mod;
  t1[o] = (t1[o << 1] * 1ll * t[o << 1 | 1] + t1[o << 1 | 1]) % mod;
}
 
pii merge(pii a, pii b) {
  return {a.first * 1ll * b.first % mod, (a.second * 1ll * b.first + b.second) % mod};
}
 
pii query(int o, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return {t[o], t1[o]};
  int mid = (l + r) >> 1;
  if (qr <= mid) return query(o << 1, l, mid, ql, qr);
  if (ql > mid) return query(o << 1 | 1, mid + 1, r, ql, qr);
  return merge(query(o << 1, l, mid, ql, qr), query(o << 1 | 1, mid + 1, r, ql, qr));
}
 
int main() {
  scanf("%d%d", &n, &m);
  int op, x, y, z;
  for (int i = 1; i <= n; ++i) scanf("%d", k + i);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &x);
    modify(1, 1, n, i, k[i], x);
  }
  while (m--) {
    scanf("%d%d%d", &op, &x, &y);
    if (op == 2) {
      pii ans = query(1, 1, n, x, y);
      printf("%d\n", (ans.first + ans.second) % mod);
    } else scanf("%d", &z), modify(1, 1, n, x, y, z);
  }
  return 0;
}