这是一场毒瘤的测试。

这是一场适用于NOIP提高组的测试。

题目来源：计蒜客NOIP模拟赛。

推荐一首歌。

劫富济贫

问题描述

吕弗·普自小从英国长大，受到骑士精神的影响，吕弗·普的梦想便是成为一位劫富济贫的骑士。吕弗·普拿到了一份全国富豪的名单(不在名单上的都是穷人)，上面写着所有富豪的名字以及他们的总资产，比如豪特斯·珀去年资产有$8.6\times 10^9$，吕弗·普就会准备抢来资助贫困的伯恩兄弟……现在吕弗·普做了$m$次打劫计划，每次要打劫若干个人，他想知道每次能打劫到的总资产是多少。

输入格式

  • 第一行一个正整数$n$，代表富豪的个数。
  • 接下来$n$行，每行一个由小写字母组成的字符串$s_i$和一个非负整数$w_i$，分别代表第$i$个富豪的名字和第$i$个富豪的资产数量。
  • 接下来一行一个正整数$m$，代表吕弗·普的打劫计划数
  • 接下来$m$行，每行第一个数为正整数$x_i$，代表这次要打劫$x_i$个人，接下来有$x$个字符串，说明了这$x$个人的名字。

输出格式

对于每个打劫计划，输出一个整数表示打劫到的总资产。

如果这次打劫任务中打劫了一个穷人，那就输出$-1$

样例

样例输入#1

2
a 10
b 20
3
2 a b
1 b
2 a c

样例输出#1

30
20
-1

数据范围与约定

  • 对于$30\%$的数据，输入中每个名字的长度均为$1$；
  • 对于$60\%$的数据，$n \leq 100,\Sigma xi \leq 100$,输入中每个名字的长度$s \leq 10$；
  • 对于 100%的数据，$n \leq 10^5,\Sigma xi \leq 10^5$,输入中所有名字的总长度$\Sigma s_i \leq2 \times 10^6,w_i<=10^9$
    保证任意两个富豪名字不同,但不保证打劫计划中会不会有重复的人。
如果打劫重复的人，请重复计算打劫的金额。
例如打劫a三次，每次$100$，则总共打劫了$300$，而不是$100$。

代码

#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
const int MAXN = 2e6 + 10;
const int P = 29, M = 1e9 + 9;
string s;
tr1::unordered_map<long long, int> table;
long long get_hash() {
    long long hash = 0;
    for (int i = 0; i <s.length(); i++) {
        hash = hash * P + s[i] - 'a' + 1;
        hash %= M;
    }
    return hash;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> s >> t;
        table[get_hash()] = t;
    }
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        long long ans = 0;
        for (int j = 1; j <= x; j++) {
            cin >> s;
            long long key = get_hash();
            if (ans != -1 && table.count(key))
                ans += table[key];
            else {
                ans = -1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

以上是我的考场代码，但是出于一些奇特的原因他TLE了，但是在AUOJ上正常工作。

题解

大力hash即可。

紫色百合

问题描述

“牵着你的手的是她，路边开满了紫色的百合花……” 你从梦中醒来，却依然忘不了梦中的她百合花。

每朵百合花都有一个权值。第$i$朵紫色百合的权值是$ \left(\begin{matrix} \underbrace{ 1\cdots 1 } \\ i个1\end{matrix}\right)_2 $。

定义“一束百合花”的价值为这些百合花组成的集合的所有子集的权值乘积的和(空集的权值乘积算$1$)。如价值为$1$和$3$组成的一束百合花价值为$1+1+3+1\times3=8$ 。

你想从$1$到第$n$朵中挑出其中一些组成“一束百合花”且价值恰好为$ \left(\begin{matrix} 1\underbrace{ 0\cdots 0 } \\ p个0\end{matrix}\right)_2 $，那么有多少种挑选方案呢？

输入格式

一行两个正整数$n,p$，含义如题目中所示。

输出格式

一个正整数，表示方案数对$998244353$取模的结果

样例

样例输入#1

3 3

样例输出#1

2

样例输入#2

233 666

样例输出#2

572514965

数据范围和提示

测试点编号$n$的最大值$p$的最大值
18100
212100
315100
4100100
510001000
620002000
7100000100000
8100000100000
9100000100000
10100000100000

代码

#include <bits/stdc++.h>
using namespace std;
const unsigned int MOD = 998244353;
long long f[451][100011], ans, n, p;
int main() {
    long long i, j;
    cin >> n >> p;
    f[0][0] = 1;
    for ( i = 1; i * ( i + 1 ) <= ( p << 1 ); i++ ) {
        for ( j = i; j <= p; j++ ) {
            f[i][j] = f[i - 1][j - i] + f[i][j - i];
            if ( j >= ( n + 1 ) )
                f[i][j] -= f[i - 1][j - n - 1];
            while ( f[i][j] < 0 )
                f[i][j] += MOD;
            f[i][j] %= MOD;
        }
        ans = ( ans + f[i][p] ) % MOD;
    }
    cout << ans % MOD << endl;
    return 0;
}

题解

首先需要对题目进行加工。

求集合$A \in \left\{x \in n^* \mid 1 \leq x \leq n \right\}$，$s.t. 2^{\Sigma_{i\in A}}=2^p$的方案数。

然后对根据对数函数的单调性，两边同时取$2$的对数。

求集合$A \in \left\{x \in n^* \mid 1 \leq x \leq n \right\}$，$s.t. \Sigma_{i\in A}=p$的方案数。

因为集合有不重复性，所以最多选择$\sqrt{n}$个数。

设$dp_{i,j}$是指取$i$朵花，和为$j$。

下面分两种情况讨论。

  • 情况A：选取了一号花

对每朵花减少$1$，则第一朵花消失了。所以可以由$dp_{i-1,j-i}$转移来。

  • 情况B：未选取一号花

对每朵花减少$1$。所以可以由$dp_{i,j-i}$转移来。

所以$dp_{i,j}=dp_{i-1,j-i}+dp_{i,j-i}$

但是有个问题，就是选择了第$n+1$朵花。减去该方案数$dp_{i-1,j-n+1}$。

代码复杂度$O(n\sqrt{n})$。

银河战舰

问题描述

瑞奥和玛德利德是非常好的朋友。瑞奥平时的爱好是吹牛，玛德利德的爱好是戳穿瑞奥吹的牛。

这天瑞奥和玛德利德来到了宇宙空间站，瑞奥向玛德利德炫耀这个空间站里所有的银河战舰都是自己的。整个空间站可以看成一个无限大的二维平面，而每个战舰都可以看做一个点，在空间站中一共分布着$n$艘银河战舰。

玛德利德：“你说这些都是你的，那你让他们动一动啊。”
瑞奥：“诶你看，那艘动了！”
玛德利德：“操作指令由我来发，一共有 5 种动的方法……”
瑞奥：“我觉得这样有失公正……”

输入格式

  • 第一行一个正整数$n$，表示战舰的数量。
  • 接下来$n$行，每行两个实数，代表第$i$个战舰的坐标$x_i,y_i$。
  • 接下来一行一个正整数$m$，代表调度的次数。

  • 接下来$m$行操作，每个操作都是如下类型的一种：

    • M l r p q：把编号在$[l,r]$区间内的战舰$x$坐标加上$p$，$y$坐标加上$q$；
    • X l r：把编号在$[l,r]$区间内的战舰沿$x$轴翻转；
    • Y l r：把编号在$[l,r]$区间内的战舰沿$y$轴翻转；
    • O l r：把编号在$[l,r]$区间内的战舰沿直线$y=x$翻转；
    • R l r a：把编号在$[l,r]$区间内的战舰绕原点逆时针旋转$a°$。

输出格式

输出包括$n$行，第$i$行表示着第$i$艘战舰经过$m$次调度之后的坐标（保留两位小数）。

样例输入

3
1 2
-2 2.5
0 -3
3
X 1 3
M 1 3 3 6
R 1 3 90

样例输出

-4.00 4.00
-3.50 1.00
-9.00 3.00

代码

#include <bits/stdc++.h>
using namespace std;
const unsigned int MAXN = 100001;
struct Matrix {
    double a[3][3];
    void setIdentity() {
        a[0][0] = a[1][1] = a[2][2] = 1;
    }
    void reset() {
        memset( a, 0, sizeof( a ) );
    }
    Matrix() {
        reset();
        setIdentity();
    }
} Mat, c[MAXN << 2], st;
double x[MAXN], y[MAXN];
Matrix operator*( const Matrix& x, const Matrix& y ) {
    Matrix ans;
    ans.reset();
    for ( int j = 0; j < 3; j++ ) {
        for ( int k = 0; k < 3; k++ )
            if ( y.a[k][j] ) {
                for ( int i = 0; i < 3; i++ ) {
                    ans.a[i][j] += x.a[i][k] * y.a[k][j];
                }
            }
    }
    return ans;
}
void pushdown( int rt ) {
    c[rt << 1] = c[rt << 1] * c[rt];
    c[( rt << 1 ) | 1] = c[( rt << 1 ) | 1] * c[rt];
    c[rt] = st;
}
void update( int rt, int l, int r, int L, int R ) {
    if ( l >= L && r <= R ) {
        c[rt] = c[rt] * Mat;
    }
    else {
        pushdown( rt );
        int mid;
        mid = ( l + r ) >> 1;
        if ( L <= mid ) {
            update( rt << 1, l, mid, L, R );
        }
        if ( R > mid ) {
            update( ( rt << 1 ) | 1, mid + 1, r, L, R );
        }
    }
}
void dfs( int rt, int l, int r ) {
    if ( l == r ) {
        cout << fixed << setprecision( 2 ) << x[l] * c[rt].a[0][0] + y[l] * c[rt].a[1][0] + c[rt].a[2][0] << " " << fixed << setprecision( 2 ) << y[l] * c[rt].a[1][1] + x[l] * c[rt].a[0][1] + c[rt].a[2][1] << endl;
    }
    else {
        pushdown( rt );
        int mid = ( l + r ) >> 1;
        dfs( rt << 1, l, mid );
        dfs( ( rt << 1 ) | 1, mid + 1, r );
    }
}
int n, m;
int main() {
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> x[i] >> y[i];
    }
    cin >> m;
    for ( int i = 1; i <= m; i++ ) {
        int l, r;
        double p, q, a;
        string s;
        cin >> s >> l >> r;
        if ( s[0] == 'M' ) {
            cin >> p >> q;
            Mat.reset();
            Mat.a[0][0] = 1;
            Mat.a[2][0] = p;
            Mat.a[1][1] = 1;
            Mat.a[2][1] = q;
            Mat.a[2][2] = 1;
            update( 1, 1, n, l, r );
        }
        else if ( s[0] == 'X' ) {
            Mat.reset();
            Mat.a[1][1] = -1;
            Mat.a[0][0] = 1;
            Mat.a[2][2] = 1;
            update( 1, 1, n, l, r );
        }
        else if ( s[0] == 'Y' ) {
            Mat.reset();
            Mat.a[1][1] = 1;
            Mat.a[0][0] = -1;
            Mat.a[2][2] = 1;
            update( 1, 1, n, l, r );
        }
        else if ( s[0] == 'O' ) {
            Mat.reset();
            Mat.a[1][0] = 1;
            Mat.a[0][1] = 1;
            Mat.a[2][2] = 1;
            update( 1, 1, n, l, r );
        }
        else if ( s[0] == 'R' ) {
            Mat.reset();
            cin >> a;
            Mat.a[0][0] = Mat.a[1][1] = cos( a * acos( -1 ) / 180 );
            Mat.a[0][1] = sin( a * acos( -1 ) / 180 );
            Mat.a[1][0] = -sin( a * acos( -1 ) / 180 );
            Mat.a[2][2] = 1;
            update( 1, 1, n, l, r );
        }
    }
    dfs( 1, 1, n );
    return 0;
}

题解

用正常的线段树操作可以拿下M，X，Y，O操作，期望得分$70$分。

将每个点的坐标用矩阵$\begin{bmatrix}x & y & 1\end{bmatrix}$表示。

操作M

$$ \begin{bmatrix}x+p & y+q & 1\end{bmatrix}=\begin{bmatrix}1 & 0 & 0\\ 0 &1&0\\ p&q&1\end{bmatrix}\times\begin{bmatrix}x & y & 1\end{bmatrix} $$

操作X

$$ \begin{bmatrix}x & -y & 1\end{bmatrix}=\begin{bmatrix}1 & 0 & 0\\ 0 &-1&0\\ 0&0&1\end{bmatrix}\times\begin{bmatrix}x & y & 1\end{bmatrix} $$

操作Y

$$ \begin{bmatrix}-x & y & 1\end{bmatrix}=\begin{bmatrix}-1 & 0 & 0\\ 0 &1&0\\ 0&0&1\end{bmatrix}\times\begin{bmatrix}x & y & 1\end{bmatrix} $$

操作O

$$ \begin{bmatrix}y & x & 1\end{bmatrix}=\begin{bmatrix}-1 & 0 & 0\\ 0 &1&0\\ 0&0&1\end{bmatrix}\times\begin{bmatrix}x & y & 1\end{bmatrix} $$

操作R

$$ \begin{bmatrix}xcosa-ysina & xsina+ycosa & 1\end{bmatrix}=\begin{bmatrix}cosa & sina & 0\\ -sina &cosa&0\\ 0&0&1\end{bmatrix}\times\begin{bmatrix}x & y & 1\end{bmatrix} $$

用线段树维护矩阵标记，并下传。

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/570.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。

Last modification：January 19, 2020
© Allow specification reprint
如果您觉得我的文章有用，给颗糖糖吧~