08月02, 2018

8.2 牛客网多校5题解及补题

以后发题解的时候代码放到最下面,这样比较好看解法,代码太长比较容易挡住。


比赛过程

1个半小时内完成签到。

中档题,各开一道。

Xander全场被概率DP折磨,最后也没有推出来。

bocity 想出了room的正确模型,Xander发现是道二分图,网上爬了个板子过了。

bocity 想出了vcd的正解,但是少了部分结果,Xander的离散化和逆序对都写挂了,赛后才a.

知识点

  • A 分数规划,二分
  • B 佩尔方程
  • E 带权二分图匹配
  • F 和的期望=期望的和,树状数组维护前缀积+按值插入
  • G 数论
  • H 树状数组/(可持久化线段树?)维护上升序列数
    • 技巧:求和时判断上界
  • I 分类讨论,树状数组逆序对
  • J 线性规划

题解

H subseq

给定一个序列 a[1..n],求下标字典序第 k 小的严格递增子序列 1<=n<=10^5 0<=k<=10^(18)

先考虑什么样的子序列字典序会更小。如果已经选取了部分元素,那么不选其他元素是最小的;其次是取最近的严格递增的元素作下一个数;再其次是在上一步的基础上再取最近的严格递增的元素作下下个数,以此类推。

那么我们有暴力的写法,即按此策略遍历所有的递增子序列。可以证明递增子序列数的上界是 2^n ,因此枚举最坏情况下是 O(2^n)

我们来考虑去掉重复的计算。 对于每一个元素,以该元素为起点的严格递增子序列数是固定的,设其为 F(n) ,则有:

F(n) = \sum_{k>n, a[k]>a[n]}^{N} F(k)

对于形如 \sum_{k>n, a[k]>a[n]} 的求和形式,大多数情况可以使用树状数组/线段树按值插入的方式来维护,计算所有点的 F(n) 的复杂度是 O(n \log n)

那么根据之前找到的性质,可以贪心地处理该问题:对于每个元素,若 F(n) \geq k ,则必须选择它;否则应该 k-=F(n) ,表示跳过了以它为下一个元素的所有可能情况。这样总复杂度是 O(n \log n)

递增子序列数的上界是 2^n 的证明:考虑最大的情况,即元素从1到n严格递增,那么 F(n) = \sum_{k=n+1}^{N} F(k) +1 = 2F(n+1) 因此 \sum F(n) = 2^n 。更简单的证明是,这种情况下可以看成每个元素都有选和不选两种状态,因此可能的状态是 2^n

证明该上界对于此题的实现是有帮助的,因为显然在 n = 1e5的情况下,最坏可能的方案数已经超过了long long的范围。但是考虑k不可能超过1e18,因此可以在求和的时候取上界,来避免溢出。

这题的代码实现难点在于数据范围,求和时必须判断上界,如果超过了就直接返回上界。int真的是会在不知道什么地方让你溢出。。。。只要是数据还是尽量用long long。

A gpa

\frac{\sum s_i c_i} {\sum s_i}

经典分数规划:最小化加权平均值。

二分平均值X

\sum s_i c_i \geq {\sum s_i X} \ \Leftrightarrow \sum ( s_i c_i - s_i X ) \geq 0

二分判断答案时候,判断上式不为负数的i的个数是否大于n-k即可

E room

有一堆四元组,给出变换后所有四元组,需要给所有四元组匹配一个目标状态,使得匹配后每个四元组和目标状态的差异和最小。

转化成完全二分图最小权值匹配问题,用KM算法。四元组即点,边权为差异个数。

F taken

n个箱子,每个有pi的概率有di大小的数和(1-pi)的概率有0,按顺序打开箱子,初始数为0,每个箱子的数如果有比当前得到的数更大,就替换。求替换次数的期望。

(这题要气死我了)

上来就考虑总体,整体非常麻烦,情况是一颗 n^2 的概率树,答案是树上路径长度的期望。

但其实这类直接求和的期望计算不应该看整体,而是使用期望的线性性质:

E \sum X_i = \sum E X_i

把每次是否替换看成一个随机变量,那么答案就是上式。

那么求和的期望就是求期望的和。单个箱子是否会打开,这个概率很好求。然后所有概率乘1求和就是答案:

\sum_{i=1}^{n} p_i \cdot \Big( \prod_{j<i, d[j]\geq d[i]} (1-p[j]) \Big)

所以说概率论的关键在于正确建立概率模型,找出随机变量。然后根据概率的性质求解。

G max

给你n,c,求gcd = c的不大于n的a和b,使得它们的积最大。

数论定理:两个连续的自然数必互质。

因此小于n的最大的两个c的倍数,gcd必然为c。所以答案就是这两个数。

但是要特判一种情况,就是 2c > n ,这时找不出两个c的倍数,答案就是c*c。

I vcd

Kanade has an infinity set H contain all of sets such as {(x,y)|x>=a,l<=y<=r} (a,l,r are arbitrary real numbers)

A point set S is good if and only if for each subset T of S there exist h in H satisfy h \cap S = T

Now kanade has n distinct points and she want to know how many non-empty subset of these points is good.

You need to output the answer module 998244353

题意不是很好读,读懂之后,意思就是在点集里计算子集S个数,子集S需要满足对于S的任意子集T,能有一个向右不闭合的矩形和S的交集为T。

这题比较神奇。思考的时候需要分类讨论答案。

Bocity推出了性质:

  • |S|>3, 不存在
  • |S|=3, 只有 > 这种形状的三个点才可以
  • |S|=2, y不相同的可以
  • |S|=1, 全部可以

最后两种情况好处理。 第三种情况,计数的方法是按y排序,对于一个元素i,它的方案数为

\sum_{j<i, x_j>x_i, y_j \neq y_i} \times \sum_{i<j, x_j>x_i, y_j \neq y_i}

相当于计算每个点的逆序数,经典的处理方法就是树状数组按值插入。

但是需要处理只计算y不相同,因此需要加入一个数组作缓冲,一次插入所有y相同的元素,这样就可以避免多算了y相同的元素。

J plan

n个人住旅馆,有二人间价格p2,三人间价格p3

类似于鸡兔同笼问题。这是只有两个未知数的情况,显然最优策略是尽可能有性价比高的填满,然后剩下的填另一种。

注意此题的覆盖而不是刚好为n。

此题可以扩展一下:如果有3人间,4人间,n人间呢?

代码

A

#include <bits/stdc++.h>
using namespace std;

#define llp(i, x, y) for (int i = x; i < y; ++i) // [x,y) x->y
#define REP llp
#define rlp(i, x, y) for (int i = y - 1; i >= x; --i) // [x,y) y->x
#define PER rlp
#define lp(i, x) for (int i = 0; i < x; ++i) //[0,x)0->x
#define mem(a, x) memset(a, x, sizeof a)
#define endl "\n"

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
// typedef __int128 ull;
typedef unsigned long long ull;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

const ll MOD = 1e9 + 7;
const ll N = 1e5 + 50;
const db eps = 1e-7;
const ll INF = 3e9;

inline ll qpower(ll x, ll p, ll M = MOD) {
    ll ans = 1;
    while (p) {
        if (p & 1) ans = ans * x % M;
        p >>= 1;
        x = x * x % M;
    }
    return ans;
}
inline ll gcd(ll a, ll b) {
    ll x;
    while (b) {
        x = a % b;
        a = b;
        b = x;
    }
    return a;
}
inline ll modp(ll x, ll p = MOD) {
    return (x % p + p) % p;
} //常数较大
inline ll addp(ll x, ll y, ll p = MOD) {
    return x + y >= MOD ? x + y - MOD : x + y;
}
inline ll subp(ll x, ll y, ll p = MOD) {
    return x - y < 0 ? x - y + MOD : x - y;
}
inline int ifloor(db x) {
    return x > 0 ? int(x + eps) : int(x - eps);
}
inline bool fequal(db x, db y) {
    if (fabs(x - y) <= eps)
        return true;
    else
        return false;
}
// std::ios::sync_with_stdio(false);
// srand((unsigned)time(NULL));

pair<db, int> grade[N];
db c[N];
bool judge(db x, int n, int k) {
    for (int i = 0; i < n; i++) {
        c[i] = grade[i].se * grade[i].fi - x * grade[i].se;
    }
    sort(c, c + n, greater<double>());
    double sum = 0;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        sum += c[i];
        if (sum >= 0.0)
            cnt++;
        else
            break;
    }
    // cout << x << " " << cnt << endl;
    return n - k <= cnt;
}
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    llp(i, 0, n) scanf("%d", &grade[i].se);
    llp(i, 0, n) scanf("%lf", &grade[i].fi);
    db sum = 0, sumq = 0;
    db maxc = 0;
    llp(i, 0, n) {
        // cout << grade[i].fi << " " << grade[i].se << endl;
        sum += grade[i].fi * grade[i].se;
        sumq += grade[i].se;
        maxc = max(grade[i].fi, maxc);
    }

    db l = 0, r = 2000;
    while (!fequal(l, r)) {
        db mid = (l + r) / 2;
        if (judge(mid, n, k))
            l = mid;
        else
            r = mid;
    }
    printf("%.7lf", l);
}

E

#include <bits/stdc++.h>
#define REP(i, x, n) for (int i = x; i < n; ++i)
using namespace std;

#define MAX 100

int m, n;              // x集与y集的点数
int weight[MAX][MAX];  //边的权重
int lx[MAX], ly[MAX];  //期望值,定点标号
bool sx[MAX], sy[MAX]; //记录寻找增广路时点集x,y里的点是否搜索过
int match[MAX];        // match[i]记录y[i]与x[match[i]]相对应

bool search_path(int u) { //给x[u]找匹配,这个过程和匈牙利匹配是一样的
    int v;
    sx[u] = true;
    for (v = 0; v < n; v++) {
        if (!sy[v] && lx[u] + ly[v] == weight[u][v]) {     //对于还没搜索过的且在相等子图中的点
            sy[v] = true;                                  //标记一下表示搜索过
            if (match[v] == -1 || search_path(match[v])) { //名花无主或者还能腾出个位置(使用递归)
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int Kuhn_Munkras(bool max_weight) { //表示求最大匹配(1)还是最小匹配(0)
    int i, j, u, inc, sum;
    if (!max_weight) { //如果求最小匹配,则要将边权取反
        for (i = 0; i < m; i++)
            for (j = 0; j < n; j++) weight[i][j] = -weight[i][j];
    }
    //初始化顶标,lx[i]设置为max(weight[i][j] | j=0,..,n-1 ), ly[i]=0;
    for (i = 0; i < m; i++) {
        lx[i] = -0x7fffffff;
        for (j = 0; j < n; j++)
            if (lx[i] < weight[i][j]) lx[i] = weight[i][j];
    }
    for (j = 0; j < n; j++) ly[j] = 0;
    memset(match, -1, sizeof(match));
    //不断修改顶标,直到找到完备匹配或完美匹配
    for (u = 0; u < m; u++) { //为x里的每一个点找匹配
        while (1) {
            memset(sx, 0, sizeof(sx));
            memset(sy, 0, sizeof(sy));
            if (search_path(u)) // x[u]在相等子图找到了匹配,继续为下一个点找匹配
                break;
            //如果在相等子图里没有找到匹配,就修改顶标,直到找到匹配为止
            //首先找到修改顶标时的增量inc, min(lx[i] + ly [i] - weight[i][j],inc);,lx[i]为搜索过的点,ly[i]是未搜索过的点,因为现在是要给u找匹配,所以只需要修改找的过程中搜索过的点,增加有可能对u有帮助的边
            inc = 0x7fffffff;
            for (i = 0; i < m; i++) {
                if (sx[i]) // x是搜索过的点
                    for (j = 0; j < n; j++) {
                        if (!sy[j] && ((lx[i] + ly[j] - weight[i][j]) < inc))
                            inc = lx[i] + ly[j] - weight[i][j]; // y是未搜索过的点
                    }
            }
            //找到增量后修改顶标,因为sx[i]与sy[j]都为真,则必然符合lx[i] + ly [j] =weight[i][j],然后将lx[i]减inc,ly[j]加inc不会改变等式,但是原来lx[i] + ly [j] !=weight[i][j]即sx[i]与sy[j]最多一个为真,lx[i] + ly [j] 就会发生改变,从而符合等式,边也就加入到相等子图中
            if (inc == 0) cout << "fuck!" << endl; //都无法求其次,简直不可理喻,所以找不到完备匹配
            for (i = 0; i < m; i++) {
                if (sx[i]) lx[i] -= inc; //所有已搜索过的x减少相同的量,便于给其他的x找其他的路径
            }
            for (i = 0; i < n; i++) {
                if (sy[i]) ly[i] += inc; //对应的ly[]加上inc使得Lx[]+Ly[]与weight[]始终保持一致
            }
        }
    }
    sum = 0;
    for (i = 0; i < n; i++)
        if (match[i] >= 0) sum += weight[match[i]][i];

    if (!max_weight) sum = -sum;
    return sum;
}
vector<vector<int>> q1, q2;

int main() {
    int i, j;
    // printf("请输入X集与Y集的点数:M,N\n");
    // scanf("%d%d", &m, &n);
    cin >> n;
    m = n;
    int a, b, c, d;
    REP(i, 0, n) {
        cin >> a >> b >> c >> d;
        q1.push_back(vector<int>{a, b, c, d});
    }
    REP(i, 0, n) {
        cin >> a >> b >> c >> d;
        q2.push_back(vector<int>{a, b, c, d});
    }

    int ans = 0;
    REP(i, 0, n) {
        REP(j, 0, n) {
            ans = 0;
            REP(ii, 0, 4) {
                REP(jj, 0, 4) {
                    if (q1[i][ii] == q2[j][jj]) {
                        ans++;
                    }
                }
            }
            weight[i][j] = 4 - ans;
        }
    }

    // printf("请输入权重\n");
    // for (i = 0; i < m; i++)
    //     for (j = 0; j < n; j++) scanf("%d", &weight[i][j]);
    cout << Kuhn_Munkras(0) << endl;
    // for (i = 0; i < n; i++) printf("%d ", match[i]);
    // system("pause");
    // return 0;
}

G

#include <bits/stdc++.h>
using namespace std;

#define llp(i, x, y) for (int i = x; i < y; ++i) // [x,y) x->y
#define REP llp
#define rlp(i, x, y) for (int i = y - 1; i >= x; --i) // [x,y) y->x
#define PER rlp
#define lp(i, x) for (int i = 0; i < x; ++i) //[0,x)0->x
#define mem(a, x) memset(a, x, sizeof a)
#define endl "\n"

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
// typedef __int128 ull;
typedef unsigned long long ull;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

const ll MOD = 1e9 + 7;
const ll N = 1e5 + 50;
const db eps = 1e-9;
const ll INF = 3e9;

inline ll qpower(ll x, ll p, ll M = MOD) {
    ll ans = 1;
    while (p) {
        if (p & 1) ans = ans * x % M;
        p >>= 1;
        x = x * x % M;
    }
    return ans;
}
inline ll gcd(ll a, ll b) {
    ll x;
    while (b) {
        x = a % b;
        a = b;
        b = x;
    }
    return a;
}
inline ll modp(ll x, ll p = MOD) {
    return (x % p + p) % p;
} //常数较大
inline ll addp(ll x, ll y, ll p = MOD) {
    return x + y >= MOD ? x + y - MOD : x + y;
}
inline ll subp(ll x, ll y, ll p = MOD) {
    return x - y < 0 ? x - y + MOD : x - y;
}
inline int ifloor(db x) {
    return x > 0 ? int(x + eps) : int(x - eps);
}
// std::ios::sync_with_stdio(false);
// srand((unsigned)time(NULL));

int main() {
    ll c, n;
    cin >> c >> n;
    if (c > n)
        cout << -1 << endl;
    else {
        ll a = n / c * c;
        ll b;
        if (a==c) b = c;
        else b = a - c;
        cout << a * b << endl;
    }
}

I

#include <bits/stdc++.h>
using namespace std;

#define llp(i, x, y) for (int i = x; i < y; ++i) // [x,y) x->y
#define REP llp
#define rlp(i, x, y) for (int i = y - 1; i >= x; --i) // [x,y) y->x
#define PER rlp
#define lp(i, x) for (int i = 0; i < x; ++i) //[0,x)0->x
#define mem(a, x) memset(a, x, sizeof a)
#define endl "\n"

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
// typedef __int128 ull;
typedef unsigned long long ull;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

const ll MOD = 998244353;
const ll N = 1e6 + 50;
const db eps = 1e-7;
const ll INF = 3e9;

inline ll qpower(ll x, ll p, ll M = MOD)
{
  ll ans = 1;
  while (p)
  {
    if (p & 1)
      ans = ans * x % M;
    p >>= 1;
    x = x * x % M;
  }
  return ans;
}
inline ll gcd(ll a, ll b)
{
  ll x;
  while (b)
  {
    x = a % b;
    a = b;
    b = x;
  }
  return a;
}
inline ll modp(ll x, ll p = MOD)
{
  return (x % p + p) % p;
} //常数较大
inline ll addp(ll x, ll y, ll p = MOD)
{
  return x + y >= MOD ? x + y - MOD : x + y;
}
inline ll subp(ll x, ll y, ll p = MOD)
{
  return x - y < 0 ? x - y + MOD : x - y;
}
inline int ifloor(db x)
{
  return x > 0 ? int(x + eps) : int(x - eps);
}
inline bool fequal(db x, db y)
{
  if (fabs(x - y) <= eps)
    return true;
  else
    return false;
}
// std::ios::sync_with_stdio(false);
// srand((unsigned)time(NULL));

//树状数组维护前缀和。只维护C,不会使用A。
ll C[N];
int lowbit(int x)
{ // 返回最低位的1
  return -x & x;
}
void update(int i, int x, int n)
{ //需要手动初始化
  for (; i <= n; i += lowbit(i))
    C[i] += x;
}
ll query(int i)
{
  ll ans = 0;
  for (; i; i -= lowbit(i)) //每次处理一个长度为lowbit(i)的区间
    ans += C[i];
  return ans;
}
void init(ll A[], int n)
{
  // memset(C,0,sizeof C);
  for (int i = 1; i <= n; ++i)
    update(i, A[i], n);
}

pii P[N];
int ansr[N];
int ansl[N];
int sub[N];
int main()
{
  ll n;
  scanf("%lld", &n);
  llp(i, 0, n)
  {
    scanf("%d%d", &P[i].se, &P[i].fi); // fi=y,se=x
    sub[i] = P[i].se;
  }

  sort(sub, sub + n);
  ll m = unique(sub, sub + n) - sub;
  for (ll i = 0; i < n; i++)
  {
    int di = lower_bound(sub, sub + m, P[i].se) - sub;
    P[i].se = di + 1;
  }
  sort(P, P + n);
  ll ans = n;
  mem(C, 0);
  stack<int> Q;
  rlp(i, 0, n)
  {
    ansr[i] = query(n - P[i].se);
    // printf("i = %d x = %d query = %d insert = %d\n",i,P[i].se,n-P[i].se,n - P[i].se+1 );
    Q.push(i);
    if (i > 0 && P[i].fi == P[i - 1].fi)
      continue;
    else
    {
      while (!Q.empty())
      {
        update(n + 1 - P[Q.top()].se, 1, n);
        Q.pop();
      }
    }
  }

  mem(C, 0);
  llp(i, 0, n)
  {
    ansl[i] = query(n - P[i].se);
    Q.push(i);
    if (i < n-1 && P[i].fi == P[i + 1].fi)
      continue;
    else
    {
      while (!Q.empty())
      {
        update(n + 1 - P[Q.top()].se, 1, n);
        Q.pop();
      }
    }
  }

  ll k = 1;
  ll anss = 0;
  llp(i, 0, n)
  {
    if (i < n - 1 && P[i].fi == P[i + 1].fi)
    {
      k++;
    }
    else
    {
      anss += 1LL * (n - i - 1) * k;
      k = 1;
    }
  }
  ans = addp(ans, anss);
  llp(i, 0, n)
  {
    ans = addp(ans, 1LL * ansl[i] * ansr[i] % MOD);
  }

  printf("%lld\n", ans);
}

J

/**
 * @Author: Xander663 
 * @Date: 2018-08-02 21:24:46 
 * @Resource: 
 * @Discription:  
 * 
 * @Solution: 
 * 
 * @Proof:  
 * 
 * @Bug:  
 * 1.INF赋小了
 * @Execute:  
 * 
*/
  #include<bits/stdc++.h>
  using namespace std;

  #define llp(i,x,y) for(int i=x;i<y;++i) // [x,y) x->y
  #define REP llp
  #define rlp(i,x,y) for(int i=y-1;i>=x;--i)  // [x,y) y->x
  #define PER rlp
  #define lp(i,x) for(int i=0;i<x;++i) //[0,x)0->x
  #define mem(a,x) memset(a,x,sizeof a)
  #define endl "\n"

  typedef long long ll;
  typedef double db;
  typedef long double ld;
  typedef pair<int,int> pii;
  // typedef __int128 ull;
  typedef unsigned long long ull;

  #define fi first
  #define se second
  #define pb push_back
  #define mp make_pair

  const ll MOD=1e9+7;
  const ll N=1e5+50;
  const db eps=1e-9;
  const ll INF=2e18;

  inline ll qpower(ll x,ll p,ll M=MOD){ll ans=1;while(p){if (p&1) ans=ans*x%M;p>>=1;x=x*x%M;}return ans;}
  inline ll gcd(ll a,ll b){ll x;while(b){x = a%b;a = b;b = x;}return a;}
  inline ll modp(ll x,ll p = MOD){return (x%p+p)%p;} //常数较大
  inline ll addp(ll x,ll y,ll p = MOD){return x+y>=MOD?x+y-MOD:x+y;}
  inline ll subp(ll x,ll y,ll p = MOD){return x-y<0?x-y+MOD:x-y;}
  inline int ifloor(db x){return x>0?int(x+eps):int(x-eps);}
  // std::ios::sync_with_stdio(false);
  // srand((unsigned)time(NULL));

  int main(){
    ll n,p2,p3;
    scanf("%lld%lld%lld",&n,&p2,&p3);
    //3
    ll ans=INF;
    llp(i,0,10){
      ans = min( i*p3+(max(n-3*i,0ll)+1)/2*p2, ans);
      ans = min( i*p2+(max(n-2*i,0ll)+2)/3*p3, ans);
    }
    printf("%lld\n",ans);
  }

H

/**
 * @Author: Xander663 
 * @Date: 2018-08-03 04:58:36 
 * @Resource: 
 * @Discription:  
 * 
 * @Solution: 
 * 
 * @Proof:  
 * 
 * @Bug:  
 * 1.傻逼错误
 * 2.傻逼错误
 * 3.求和不知道取上界的技巧
 * 4.树状数组参数类型ll写的int,结果强制转换直接为0了
 * @Execute:  
 * 
*/
#include<bits/stdc++.h>
using namespace std;

#define llp(i,x,y) for(int i=x;i<y;++i) // [x,y) x->y
#define REP llp
#define rlp(i,x,y) for(int i=y-1;i>=x;--i)  // [x,y) y->x
#define PER rlp
#define lp(i,x) for(int i=0;i<x;++i) //[0,x)0->x
#define mem(a,x) memset(a,x,sizeof a)
#define endl "\n"

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
// typedef __int128 ull;
typedef unsigned long long ull;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

const ll MOD=1e9+7;
const ll N=5e5+50;
const db eps=1e-9;
const ll INF=2e18;

inline ll qpower(ll x,ll p,ll M=MOD){ll ans=1;while(p){if (p&1) ans=ans*x%M;p>>=1;x=x*x%M;}return ans;}
inline ll gcd(ll a,ll b){ll x;while(b){x = a%b;a = b;b = x;}return a;}
inline ll getInv(ll x,ll M=MOD){return qpower(x,M-2,M);}

inline ll modp(ll x,ll p = MOD){return (x%p+p)%p;} //常数较大
inline ll addp(ll x,ll y,ll p = MOD){return x+y>=MOD?x+y-MOD:x+y;}
inline ll subp(ll x,ll y,ll p = MOD){return x-y<0?x-y+MOD:x-y;}

inline int ifloor(db x){return x>0?int(x+eps):int(x-eps);}
inline bool fequal(db x){return x>0?int(x+eps):int(x-eps);}

// std::ios::sync_with_stdio(false);
// srand((unsigned)time(NULL));


ll C[N];
void update(int i,ll x,int n){ //需要手动初始化
  for(;i<=n;i+=i&(-i)) C[i]= min(C[i]+x,INF);
}
ll query(int i){
  ll ans = 0;
  for(;i;i-=i&(-i)) //每次处理一个长度为lowbit(i)的区间
    ans = min(ans+C[i],INF);
  return ans;
}

int tmp[N];
int d[N];
int n;
void discrete(){
  sort(tmp+1,tmp+1+n);
  int m=unique(tmp+1,tmp+1+n)- (tmp+1);
  for (int i=1;i<=n;++i) d[i]=lower_bound(tmp+1,tmp+1+m,d[i])-(tmp+1) + 1;
}

ll ans[N]; //当前元素为第一项,有多少严格递增子序列
int Q[N];
int cnt=0;
int solve(int n,ll k){
  int pos=0;
  while(k && pos<=n){  
    pos++;
    // printf("k=%lld cnt=%d pos=%d ans=%lld\n",k,cnt,pos,ans[pos]);
    if(cnt>0 && d[pos]<=d[Q[cnt-1]]) continue;
    if (ans[pos]<k) {
      k-=ans[pos];
    }
    else{
      Q[cnt++] = pos;
      k-=1;
    }
  }
  return cnt;
}
int main(){
  ll k;
  scanf("%d%lld",&n,&k);
  llp(i,1,n+1) {
    scanf("%d",d+i);
    tmp[i] = d[i];
  }
  discrete();

  for(int i=n;i>=1;--i) { 
    ans[i] = query(n-d[i])+1;
    // cout<<ans[i]<<endl;
    update(n-d[i]+1,ans[i],n);
  }

  if (query(n) < k) printf("-1\n");
  else {
    printf("%d\n",solve(n,k));
    // assert(cnt==0);
    lp(i,cnt) printf("%d%c",Q[i],i==cnt-1?'\n':' ');
  }
}

F

/**
 * @Author: Xander663 
 * @Date: 2018-08-03 01:31:45 
 * @Resource: 
 * @Discription:  
 * 
 * @Solution: 
 * 
 * @Proof:  
 * 
 * @Bug:  
 * 1.离散化挂了
 * 2.公式写错了
 * @Execute:  
 * 
*/
#include<bits/stdc++.h>
using namespace std;

#define llp(i,x,y) for(int i=x;i<y;++i) // [x,y) x->y
#define REP llp
#include<bits/stdc++.h>
using namespace std;

#define llp(i,x,y) for(int i=x;i<y;++i) // [x,y) x->y
#define REP llp
#define rlp(i,x,y) for(int i=y-1;i>=x;--i)  // [x,y) y->x
#define PER rlp
#define lp(i,x) for(int i=0;i<x;++i) //[0,x)0->x
#define mem(a,x) memset(a,x,sizeof a)
#define endl "\n"

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
// typedef __int128 ull;
typedef unsigned long long ull;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

const ll MOD=998244353;
const ll N=1e5+50;
const db eps=1e-9;
const ll INF=3e9;

inline ll qpower(ll x,ll p,ll M=MOD){ll ans=1;while(p){if (p&1) ans=ans*x%M;p>>=1;x=x*x%M;}return ans;}
inline ll gcd(ll a,ll b){ll x;while(b){x = a%b;a = b;b = x;}return a;}
inline ll getInv(ll x,ll M=MOD){return qpower(x,M-2,M);}

inline ll modp(ll x,ll p = MOD){return (x%p+p)%p;} //常数较大
inline ll addp(ll x,ll y,ll p = MOD){return x+y>=MOD?x+y-MOD:x+y;}
inline ll subp(ll x,ll y,ll p = MOD){return x-y<0?x-y+MOD:x-y;}

inline int ifloor(db x){return x>0?int(x+eps):int(x-eps);}
inline bool fequal(db x){return x>0?int(x+eps):int(x-eps);}

// std::ios::sync_with_stdio(false);
// srand((unsigned)time(NULL));

ll C[N];
void update(int i,int x,int n){ //需要手动初始化
  for(;i<=n;i+=i&(-i)) C[i] = C[i]*x%MOD;
}
ll query(int i){
  ll ans = 1;
  for(;i;i-=i&(-i)) //每次处理一个长度为lowbit(i)的区间
    ans = ans*C[i]%MOD;
  return ans;
}

ll tmp[N];
ll d[N];
int n;
void discrete(){
  sort(tmp+1,tmp+1+n);
  int m=unique(tmp+1,tmp+1+n)- (tmp+1);
  for (int i=1;i<=n;++i) d[i]=lower_bound(tmp+1,tmp+1+m,d[i])-(tmp+1) + 1;
}

ll p[N];
int main(){
  ll inv100 = getInv(100);
  scanf("%d",&n);
  llp(i,1,n+1) {
    scanf("%lld%lld",p+i,d+i);
    p[i] = p[i]*inv100%MOD;
    tmp[i] = d[i];
  }

  discrete();

  llp(i,0,n+1) C[i] = 1;

  ll ans=0;
  llp(i,1,n+1){
    ans = addp(ans,p[i]*query(n-d[i])%MOD);
    update(n-d[i]+1,subp(1,p[i]),n);
  }

  printf("%lld\n",ans);
}

本文链接:https://www.haolovej.com/post/multi5.html

-- EOF --

Comments

评论加载中...

注:如果长时间无法加载,请针对 disq.us | disquscdn.com | disqus.com 启用代理。