头像

朴小明




离线:7小时前


最近来访(202)
用户头像
懒狗就是w
用户头像
不拿周赛牌不改名
用户头像
jelly_07
用户头像
Royal
用户头像
卐LUO卍
用户头像
HfjNUlYZ
用户头像
骂完继续写
用户头像
没鱼
用户头像
JesseChan
用户头像
雪落之声-2010
用户头像
77777777777
用户头像
@ljr.
用户头像
SolitudeFate
用户头像
GRID
用户头像
用户头像
yxc的小迷妹
用户头像
yxc的小迷妹1
用户头像
左手影视
用户头像
Return_O
用户头像
c语言的acwing新手


D. Not Quite Lee

题意:

给定数组 $a[]$,求合法的子序列有多少。
合法的序列 $b[]$是这样的:
对于 $b_i$,与之对应要构造一个等差数列,公差为 $1$,首项是 $x$(未知数)。所有的等差数列之和如果是 $0$ ,那么这个 $b[]$合法。

分析:

第一个结论:

如果确定了数组$b[\:]$,设与之对应的等差数列的首项为$x_i$,那么构造出来的所有的等差数列的和为:

$\displaystyle \sum {\frac{b_i (x_i + x_i + b_i - 1)}{2}} = 0$,

方程思想,将未知量尽量留在左边,移项得:
$\displaystyle \sum {b_i x_i} = - \displaystyle \sum {\frac{b_i (b_i - 1)}{2}}$,

此时,由裴蜀定理有:
当 $gcd(b_{1-i})$ 是 $\displaystyle \sum {\frac{b_i (b_i - 1)}{2}}$的因子时,方程才会有解。

下面用 $g$ 来代表 $gcd(b_{1-i})$。

当 $g$ 是奇数的时候,很显然他是每个 $\frac{b_i(b_{i-1})}{2}$ 的因子,也就是说他可以被整除,方程一定有解。

由此,得到本题第一个结论,序列中,只要有奇数,那他一定是合法的。因为此时gcd必定为奇数。

第二个结论:

当 $g$ 是偶数的时候,很显然他是每个 ${b_i}$ 的因子,但是这时候还剩一个分母的 $2$,这个额外的要求还需要继续推式子,探索什么条件才能让其满足:

也就是,要满足:

$2$ 是 $\displaystyle \sum {\frac{b_i (b_i - 1)}{g}}$ 的因子。

这时候,就要研究 $g$ 含有的 $2$ 的数量了。

$\displaystyle \sum {\frac{b_i (b_i - 1)}{g}}$经过约分,可以得到$\displaystyle \sum {c_i (b_i - 1)}$,只要$\displaystyle \sum {c_i (b_i - 1)}$是偶数,那这个序列就是合法的,现在来研究这个式子的奇偶性:

其中,$(b_i - 1)$ 一定是奇数(因为这里选取的 $b_i$均为偶数),那么他不可能让式子变成偶数;所以目光转向 $c_i$,这里因为 $gcd$ 的特性,必定存在一些 $c_i$ 是奇数(这里不再详细说明,能看到这里,这个小结论必定是能够理解的), 当偶数个 $c_i$ 是奇数的时候,这个式子就能变成偶数了。

至此,得到第二个结论,当序列中,除完 $g$ 之后,剩下的奇数如果有偶数个,那序列就合法。

做法:

对于结论一,统计出有 $cnt$ 个奇数,那么 $ans += (2^{cnt} - 1) \times 2^{n-cnt}$ 。

剩下的情况,枚举 $2$的幂次 $k$,对于 $a_i$ ,如果他含有的$2$的最高幂次是$k$,在经历了约分过后,他就成为了奇数。剩下的统计也就不难,这里不展开详细说明(还是那句话,能看到这里,这个统计一定能独立想出来)。

并不重要的代码,数学的推理过程才是最重要的:

int a[N], f[40];
int qpow (int x, int n)
{
    int ret = 1;
    while (n) {
        if (n & 1) ret = ret * x % mod;
        x = x* x % mod;
        n >>= 1;
    }
    return ret;
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++){
        int cnt = 0;
        while(a[i] % 2 == 0){
            a[i] >>= 1;
            cnt++;
        }
        f[cnt]++;
    }
    ans += (qpow(2, f[0]) - 1) * qpow(2, n - f[0]) % mod;
    for (int i = 1; i <= 30; i++){
        //当前位选偶数个,后面的任意个
        if (f[i] == 0) continue;
        int sum = 0;
        for (int j = i + 1; j <= 30; j++) sum += f[j];
        ans += (qpow(2, f[i] - 1) - 1) * qpow(2, sum) % mod;
        ans %= mod;
    }
    cout << (ans + mod) % mod;
}



就c有点意思,A,B,D1感觉都很好想。

C - Paprika and Permutation

题意:

给定了一个数组,要求转换成一个排列,问能否变换,如果能,输出最小操作次数。
这里的操作是,选择整数x,然后a[i] %= x;

做法:

已经在1~n里的数可以不去动了,剩下的数,考虑怎么变成排列里的数。
这里一时想不到怎么去变,可以稍微打个表,然后就很容易发现,n可以通过一次操作,变成1~(n - 1) / 2的数。
然后这题就做完了,贪心的从小到大遍历,能变成排列里的数,那就变。

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    set<int> s, f;
    for (int i = 1; i <= n; i++) s.insert(i), f.insert(i);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s.erase(a[i]);   //还缺的数
    }
    int cnt = 0;
    sort(a.begin(), a.end());
    for (int i = 1; i <= n; i++){
        if (f.count(a[i])){
            f.erase(a[i]);   //要是不在这个排列里面,那就要开始变化了
            continue;
        }
        int ans = 1e18;
        for (auto j : s){
            if ((a[i] - 1) / 2 < j) continue;
            ans = j;
            break;
        }
        s.erase(ans);
        cnt++;
    }
    if (s.size()) cout << "-1\n";
    else cout << cnt << "\n";
}



4727. 摆放棋子

很多人的写法都是当前状态往后更新,然后只有3个维度,但是我看到这个题的时候想的就是这个从前面继承的暴力四维dp,就是细节挺多。
然后这个取模是从队友代码偷学来的。感觉非常好使啊,完美的压行了。

做法:

简单dp,f[i][j][k][l]表示前i个点,已经用了j个黑色的妻子,最后一段黑色的妻子长度为k,此时l = 0;为最后一段长度为l的白色妻子,此时k = 0.
然后就是比较细节的转移:

  • j从0开始循环
  • 要特判 j - 1是不是>=0,当前转移才能进行下去
  • 第一维的空间大小要开200

本地wa了无数发的原因。。最后的统计答案,参数写错了。。

int f[N][N][15][15];
void solve()
{
    int n1, n2, k1, k2;
    cin >> n1 >> n2 >> k1 >> k2;
    f[0][0][0][0] = 1;
    for (int i = 1; i <= n1 + n2; i++)
    {
        for (int j = 0; j <= n1; j++)
        {
            if (j - 1 >= 0) for (int b = 0; b <= k2; b++) (f[i][j][1][0] += f[i - 1][j - 1][0][b]) %= mod;
            if (j - 1 >= 0) for (int h = 2; h <= k1; h++) (f[i][j][h][0] += f[i - 1][j - 1][h - 1][0]) %= mod;

            for (int h = 0; h <= k1; h++) (f[i][j][0][1] += f[i - 1][j][h][0]) %= mod;
            for (int b = 2; b <= k2; b++) (f[i][j][0][b] += f[i - 1][j][0][b - 1]) %= mod;
        }
    }
    int ans = 0;
    for (int h = 1; h <= k1; h++) (ans += f[n1 + n2][n1][h][0]) %= mod;
    for (int b = 1; b <= k2; b++) (ans += f[n1 + n2][n1][0][b]) %= mod;
    cout << ans;
}



C.Game Master

这种1700的题还是挺好想的,多想想哪里漏了,就修出bug了。

12.4 换了正确的方法做B题。

题意:

一共有n个人,两张地图。每个人在两张地图上都有相应的战斗力,一共进行n - 1次竞赛,最终选出胜利者。现在要你安排比赛顺序,问每个人是否能获胜。

思路:

首先很经典的将a[]排序,这时候最大战力的显然可以获胜。
然后模拟样例,发现有一个位置pos,满足b[pos] > b[n]的时候,pos ~ n的人全都能获胜。

这个思路我wa了3发,然后才想到,漏解了。

pos前可能还有pos1,满足b[pos1] > pos ~ n中的某个数。然后就改用ST表来一直更新这个pos。就做完这个题了。

struct node{
    int a, b, pos;
    bool operator < (const node &k) const {
       return a < k.a;
    }
}a[N];
int ans[N], BB[N];
struct ST
{
    // 注意下标范围是0开始还是1开始,下面有提示
    int f_max[N][20], lg[N];
    int f_min[N][20];
    void init(int a[], int n)
    {
        lg[0] = -1;
        for (int i = 1; i <= n; i++)
        {
            f_max[i][0] = a[i];
            f_min[i][0] = a[i];
            if ((i & (i - 1)) == 0) lg[i] = lg[i - 1] + 1;
            else lg[i] = lg[i - 1];
        }
        // 还有这里
        f_max[0][0] = a[0];
        int t = lg[n];
        for (int j = 1; j <= t; j++)
        {
            // 这里
            for (int i = 1; i <= n - (1ll << j) + 1; i++)
            {
                f_max[i][j] = max(f_max[i][j - 1], f_max[i + (1ll << (j - 1))][j - 1]);
                f_min[i][j] = min(f_min[i][j - 1], f_min[i + (1ll << (j - 1))][j - 1]);
            }
        }
    }
    int que_max(int l, int r)
    {
        int k = lg[r - l + 1];
        if (l == 0 && r > 0)
        {
            l = 1;
            k = lg[r - l + 1];
            return max({f_max[0][0], f_max[l][k], f_max[r - (1ll << k) + 1][k]});
        }
        return max(f_max[l][k], f_max[r - (1ll << k) + 1][k]);
    }
    int que_min(int l, int r)
    {
        int k = lg[r - l + 1];
        if (l == 0 && r > 0)
        {
            l = 1;
            k = lg[r - l + 1];
            return min({f_max[0][0], f_min[l][k], f_min[r - (1ll << k) + 1][k]});
        }
        return min(f_min[l][k], f_min[r - (1ll << k) + 1][k]);
    }
} S;
void solve()
{
    int n;
    cin >> n;
    fill(ans + 1, ans + 1 + n, 0);
    for (int i = 1; i <= n; i++) cin >> a[i].a;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].b;
        a[i].pos = i;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) BB[i] = a[i].b;
    int pos = n, val = a[n].b;
    S.init(BB, n);

    //往左找最远的位置,这个位置的b值大于现在的val
    for (int i = 1; i <= n; i++){
        int l = 1, r = pos - 1;
        if (l > r) break;
        while(l < r){
            int mid = (l + r) >> 1;
            if (S.que_max(1, mid) > val) r = mid;
            else l = mid + 1;
        }
        if (S.que_max(1, l) > val){
            val = S.que_min(l, pos);   //打败这个区间的最小值即可
            pos = l;
        }
    }

    for (int i = pos; i <= n; i++) ans[a[i].pos] = 1;
    for (int i = 1; i <= n; i++) cout << ans[i];
    cout << "\n";
}

Build the Permutation

题意:

构造一个排列,有a个峰,b个谷。

做法:

非常暴力。

12.4 换了新的方法做B题,发现从位置1开始交换,会多一个谷地;从位置n开始交换,会多一个山峰。
然后加上之前推过的结论,abs(x - y) >= 2 || x + y > n - 2就无法构造。
剩下的就是分三类讨论了,代码还是很简短的。
注意复制的时候一些细节仍要修改。

int p[N];
bool check(int n, int a, int b)
{
    int cnta = 0, cntb = 0;
    for (int i = 2; i <= n - 1; i++){
        if (p[i - 1] < p[i] && p[i] > p[i + 1]) cnta++;
        if (p[i - 1] > p[i] && p[i] < p[i + 1]) cntb++;
    }
    return (cnta == a && cntb == b);
}
void solve()
{
    int n, a, b;
    cin >> n >> a >> b;
    for (auto val : {a, b}){
        for (auto pos : {1, 2}){
            for (auto kk : {-1, 0, 1}){
                for (auto yy : {-1, 0, -2}){
                    for (int i = 1; i <= n; i++) p[i] = i;
                    for (int i = pos, j = 1; i + 1 <= n + yy && j <= val + kk; i += 2, j++){
                        swap(p[i], p[i + 1]);
                    }
                    if (check(n, a, b)){
                        for (int i = 1; i <= n; i++) cout << p[i] << " ";
                        cout << "\n";
                        return;
                    }

                    for (int i = 1; i <= n; i++) p[i] = i;
                    for (int i = n, j = 1; i - 1 >= 1 && j <= val + kk; i -= 2, j++){
                        swap(p[i], p[i - 1]);
                    }
                    if (check(n, a, b)){
                        for (int i = 1; i <= n; i++) cout << p[i] << " ";
                        cout << "\n";
                        return;
                    }
                }

            }
        }
    }
    cout << "-1\n";
}
int a[N];
void solve()
{
    int n, x, y;
    cin >> n >> x >> y;
    for (int i = 1; i <= n; i++) a[i] = i;
    if (abs(x - y) >= 2 || x + y > n - 2){
        cout << "-1\n";
        return;
    }

    if (x > y){  //多一个山峰
        for (int i = n, j = 1; i - 1 >= 1 && j <= x; i -= 2){
            swap(a[i], a[i - 1]);
            j++;
        }
    }
    else if (x < y){ //谷地多一个
        for (int i = 1, j = 1; i + 1 <= n && j <= y; i += 2){
            swap(a[i], a[i + 1]);
            j++;
        }
    }
    else {
        for (int i = 2, j = 1; i <= n - 1 && j <= x; i += 2){
            swap(a[i], a[i + 1]);
            j++;
        }
    }
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << "\n";
}



C. Keshi Is Throwing a Party

题意:

有n个人,你要从中选出k个满足条件的人,让k最大化。
对于第i个人,他希望选出来的人中,在他后面不能超过a[i]人,在他前面不能超过b[i]人。

做法:

条件中的a[i]具有后效性,所以不可以dp解决,(无论是正着dp还是倒着,都不能解决这个后效性)。考虑到最后的答案具有单调性,所以可以二分答案。
考虑一个集合,里面有x个人了,他们是符合条件的,如果想要添加一个人进入这个集合,然后毫不影响前面的人:

  • 对于条件b,这个很容易想到,只要b[i] - x >= 0即可。

  • 对于条件a,想要毫不影响前面的人,不如考虑当这个人加入集合后,绝对不影响后面的人加入。那就和当前枚举的mid有关了,他后面还有mid - x - 1个人,那么a[i] - (mid - x - 1) >= 0,这个人才可以加入。

最后判断x是不是大于等于mid,就能知道合不合法了。

int a[N], b[N];
int n;
bool check(int mid)
{
    int ret = 0;
    for (int i = 1; i <= n; i++){
        if (a[i] - (mid - ret - 1) >= 0 && b[i] - ret >= 0) ret++;
    }
    return ret >= mid;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
    }
    int l = 1, r = n;
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << "\n";
}



前言:

本场校赛的题解按难度来排序。先按照过题人数多的题来更新题解。
题目以思维题居多,但是没想到大家的语法基础比较差。
赛后补题才能更好的提高自己的水平,补题的链接也包含在下面的标题中了,大家点进去补题就好。

homo VS Jesse

题意:

t组数据,输入t行字符串,对于每个字符串,判断里面‘J’的数量和‘H’的数量,输出相应的答案。

做法:

使用scanf读入字符串,然后用strlen函数求出字符串的长度,就可以遍历这个字符串了。

#include <bits/stdc++.h>
char s[100];
void solve()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    int H = 0, J = 0;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == 'H') H++;
        if (s[i] == 'J') J++;
        if (H == 3)
        {
            printf("Sleep~\n");
            return;
        }
        if(J == 3)
        {
            printf("Practise!\n");
            return;
        }
    }
}
int main()
{
    int tt = 1;
    scanf("%d", &tt);
    while (tt--) solve();
    return 0;
}

homo’s mini train

做法:

从1到n,一直求最小值,然后输出就可以了。

#include <bits/stdc++.h>
void solve()
{
    int n;
    scanf("%d", &n);
    int mi = 1e9;
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        if (x < mi) mi = x;
        printf("%d ", mi);
    }
    printf("\n");
}
int main()
{
    int tt = 1;
    scanf("%d", &tt);
    while (tt--) solve();
    return 0;
}

play chess with homo

做法:

显然,最终每一行,每一列都不会有多于3及3个以上个炮,否则,他们一定会产生攻击。
所以答案的最大也就是4。所有的答案无非就是1,2,4这三个数。
特判行和列是不是为1的情况,其他的情况输出4即可。

这种题就是ACM圈子里经常提到的“思维题”。

#include <stdio.h>
void solve()
{
    int a, b;
    scanf("%d%d",&a,&b);
    if (a > 2) a = 2;
    if (b > 2) b = 2;
    printf("%d\n", a * b);
}
int main()
{
    int tt = 1;
    scanf("%d", &tt);
    while (tt--) solve();
    return 0;
}

Sign in here!

做法:

对于问题一,特判a = 1的情况,此时问题无解。
对于a > 1,只要模拟这个式子就好,可以证明相乘的次数不会太多,因为这是个指数级增长的式子。

对于问题二,相信大家的C语音课程会有求最大公约数的练习题,此处就不展开详细的说明。

#include <bits/stdc++.h>
int _1(int a, int b)
{
    if (a == 1) return 0;
    int ret = 0;
    int k = 1;
    while(k * a <= b)
    {
        ret++;
        k *= a;
    }
    return ret;
}
int _2(int a, int b) {return std::__gcd(a, b);}
void solve()
{
    int a, b;
    scanf("%d%d",&a,&b);
    printf("%d\n", (_1(a, b) ^ _2(a, b)));
}
signed main()
{
    int tt = 1;
    scanf("%d", &tt);
    while (tt--) solve();
    return 0;
}

Jesse VS Yaozi

做法:

对于每一局,数组中数的个数是 2 * n,先手可以取的位置是1或者2 * n,即先手可以拿到奇数位置的数或者偶数位置的数。

先说结论,先手一定可以拿到所有的奇数下标的数,或者偶数下标的数。

证明很简单,假设先手想要奇数位置的数,那他先拿走位置1的数,这时候后手只能选偶数位置的数了,以此类推,先手可以拿到所有的奇数位置的数。
偶数位置的同理。

下面的代码使用了c++语法,大家只需要关心solve函数中的逻辑即可,不用关心怎么输入输出。

#include <bits/stdc++.h>

#define endl "\n"
#define i128  __int128
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define lowbit(x) ((x) & (-x))
#define popcount(x) __builtin_popcount(x)
#define all(x) x.begin() ,x.end()

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--)
    {
        int n, f;
        cin >> n >> f;
        n <<= 1;
        ll a = 0, b = 0;
        for(int i = 0; i < n; i++)
        {
            int x;
            cin >> x;
            if(i & 1) a += x;
            else b += x;
        }
        if(a == b) cout << "Pingju" << endl;
        else if(f) cout << "Jesse" << endl;
        else cout << "Yaozi" << endl;
    }


    return 0;
}

0 and 1 (easy version)

做法:

  • 对于easy version,直接遍历l ~ r这个区间,计算其中的数到0的距离更小,还是到k的距离更小即可。然后累加输出答案。

  • 对于hard version,需要用到离散化和树状数组,这里说一下大致思路,将询问离线后,树状数组离线求出区间第k小的位置,接着再用树状数组快速求和即可。

注意输出的数,有可能会超过int的范围,所以要使用long long,赛中wa的十几分代码,大概都是这个原因。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, mod = 1e9 + 7;
int a[N];
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++){
        int l, r, k;
        cin >> l >> r >> k;
        int ans = 0;
        for (int j = l; j <= r; j++){
            ans += min(a[j], k - a[j]);
        }
        cout << ans << "\n";
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
//    cin >> tt;
    while (tt--) solve();
    return 0;
}

如果对hard version 版本的代码感兴趣,可以私聊出题人要,这里就不放了。

homo’s CCPC medal

做法:

四层暴力循环,输入的时候,标记一下哪些数是不能使用的。在四层循环内,如果遇见了不能使用的数,那就continue。然后使用map统计,或者数组统计数字出现过的次数就可以了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, mod = 1e9 + 7;
void solve()
{
    int n;
    cin >> n;
    vector<int> f(10);
    for (int i = 1; i <= n; i++) 
    {
        // cin >> a[i];
        int x;
        cin >> x;
        f[x] = 1;
    }
    int cnt = 0;
    for (int i = 0; i < 10; i++)
    {
        if (f[i]) continue;
        for (int j = 0; j < 10; j++)
        {
            if (f[j]) continue;
            for (int k = 0; k < 10; k++)
            {
                if (f[k]) continue;
                for (int l = 0; l < 10; l++)
                {
                    if (f[l]) continue;
                    map<int, int> mp;
                    mp[i]++;
                    mp[j]++;
                    mp[k]++;
                    mp[l]++;
                    if (mp.size() == 2 && (*mp.begin()).second == (*mp.rbegin()).second) cnt++;
                }
            }
        }
    }
    cout << cnt << "\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}



前言:

有种入门概率dp的感觉了,C是难度1900的概率dp,自己做出来的,感觉挺好。
D1是个不难想的交互,比起近一年的cf的交互题,可以说是简单很多了,但是难度是1700,这种难度以前比赛的时候我做不出来的,难道是我实力终于有所提高了吗。希望下次赛时再遇见1700的也能做出来吧。

C.Need for Pink Slips

题意:

给定三种牌的抽取概率,还有一个扰动因素…要是抽到第三种牌,那就结束了。然后问抽到第三种牌的期望次数。

思路:

本来想推式子然后进行个逆推的dp,因为期望dp的套路一般都是这样子的。
但是这个状态转移挺多的,于是决定记忆化搜索了。然后就很简单了,各种状态之间的转移模拟好就行。
注意进入第三种牌的时候就不要再dfs了,我是爆栈了无数发之后才意识到这里不用再递归下去了,因为有可能是死递归。
最后一跑样例发现总差了那么点,于是改了递归出口f[{x, y, z] = 1就能过了,不知道这是为什么,感觉这里是0才对。。。

const long double eps = 1e-5;
struct node{
    double x, y, z;
    bool operator < (const node &k) const{
        if (x != k.x) return x < k.x;
        else if (y != k.y) return y < k.y;
        return z < k.z;
    }
};
map<node, double> f;
double v;
double dfs(double x, double y, double z)
{
//    cout << x << " " << y << " " << z << " " <<  "\n";
    if (f.count({x, y, z})) return f[{x, y, z}];
    if (x == 1 || y == 1 || z == 1) {
        return f[{x, y, z}] = 1;
    }
    double ret = 1;
    if (x > eps){
        int cnt = 0;
        if (y > eps) cnt++;
        if (z > eps) cnt++;
        double jia = min(x, v);
        ret = ret + dfs(
                        x - jia,
                        (y < eps ? 0 : y + jia / cnt),
                        (z < eps ? 0 : z + jia / cnt)) * x;

    }
    if (y > eps){
        int cnt = 0;
        if (x > eps) cnt++;
        if (z > eps) cnt++;
        double jia = min(y, v);
        ret = ret + dfs(
                (x < eps ? 0 : x + jia / cnt),
                y - jia,
                (z < eps ? 0 : z + jia / cnt)) * y;
    }
    return f[{x, y, z}] = ret;
}
void solve()
{
    double c, m, p;
    cin >> c >> m >> p >> v;
    printf("%.10lf\n", dfs(c, m, p));
    f.clear();
}

D1.RPD and Rap Sheet (Easy Version)

题意:

让我们猜数字,他有一个数字x,我们猜这个数字是y,如果猜对了就结束了;猜错了就x = x ^ y,然后继续猜。
x的范围是0~n-1,最多猜n次。

思路:

先不管次数,考虑一定能找出x的方案,那不就是枚举每个数。如果否那这个数就再枚举一次,相当于是保持了x一直不变,于是必定能找到。
然后优化这个枚举次数,发现再枚举一次错误答案,为了让x去异或这个操作很浪费,那就优化他好了,把异或这个操作放进下一次询问里,就能省一次询问了。

int MYANS = 3;
int ask(int x)
{
    cout << x << endl;
    int ret;
    cin >> ret;
//    MYANS ^= x;
//    return MYANS == 0;
    return ret;
}
void solve()
{
    int n, k;
    cin >> n >> k;
    set<int> s;
    int now = 0;
    int cnt = 1;
    MYANS = rand() % n;
    for (int i = 0; i < n; i++){
        int ret = ask(now);
        if (ret == 1) {
//            cout << "ACCEPT!" << endl;
            break;
        }
        now = i ^ cnt;
        cnt++;
    }
}



朴小明
13天前

前言

做完然后看看题解是怎么写的,好像都是单调队列优化dp,我的ST优化dp居然能卡过去也是万幸了。

题意:

…有点长,略略略了

做法:

线性dp,f[i][j]代表截止第i个点,锅里一共有j种配料时最大的价值。
转移方程也很简单,从上一层开始转移,因为有拿走s个的限制条件,所以暴力的dp是N^3的复杂度。

考虑优化

f[i][j] = max(f[i][j], f[i - 1][k] + j * a[i]);

能看出只要取出上一层的某个最大值,就不用这样子枚举一遍了。所以我采用ST表优化。


int a[N], f[N][N];
struct ST
{
    // 注意下标范围是0开始还是1开始,下面有提示
    int f_max[N][13], lg[N];
    void init(int a[], int n)
    {
        lg[0] = -1;
        for (int i = 1; i <= n; i++) 
        {
            f_max[i][0] = a[i];
            if ((i & (i - 1)) == 0) lg[i] = lg[i - 1] + 1;
            else lg[i] = lg[i - 1];
        }
        // 还有这里
        f_max[0][0] = a[0];
        int t = lg[n];
        for (int j = 1; j <= t; j++)
        {
            // 这里
            for (int i = 0; i <= n - (1ll << j) + 1; i++)
            {
                f_max[i][j] = max(f_max[i][j - 1], f_max[i + (1ll << (j - 1))][j - 1]);
            }
        }
    }
    int que_max(int l, int r)
    {
        int k = lg[r - l + 1];
        if (l == 0 && r > 0) 
        {
            l = 1;
            k = lg[r - l + 1];
            return max({f_max[0][0], f_max[l][k], f_max[r - (1ll << k) + 1][k]});
        }
        return max(f_max[l][k], f_max[r - (1ll << k) + 1][k]);
    }
} S;
void solve()
{
    int n, w, s;
    cin >> n >> w >> s;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i <= n; i++)
    for (int j = 0; j <= w && j <= i; j++)
        f[i][j] = -1e18;
    f[0][0] = 0;
    S.init(f[0], n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= w && j <= i; j++)
        {
            // for (int k = j - 1; k <= w && k - (j - 1) <= s && k <= i - 1; k++) 
            // {
            //     f[i][j] = max(f[i][j], f[i - 1][k] + j * a[i]);
            // }
            // 想办法优化掉这个维度,感觉可以优化
            // 从上一层的 j - 1开始,最长到 min(w, j - 1 + s, i - 1), 三个数都是定值啊
            f[i][j] = S.que_max(j - 1, min({w, j - 1 + s, i - 1})) + j * a[i];
        }
        S.init(f[i], min(w, i));
        // if (i == 1)
        // {
        //     cout << "====================\n";
        //     cout << S.que_max(0, 1) << "\n";
        //     cout << "=============\n";
        // }
    }
    // cout << f[2][1] << "\n";
    cout << *max_element(f[n] + 1, f[n] + 1 + w);
}



朴小明
14天前

前言

上午就写完这题了,但是因为还有很多别的麻烦事导致现在才有空写题解。

好多看起来暴力的代码,实际上复杂度都是完全正确的,自己也想到过这种暴力代码,但是就是觉得复杂度不对,所以就不敢写。

比如某场校赛的那个质数的暴力题,赛时一直想不出怎么写,也不敢交暴力代码,没想到正解就是暴力。。。

还有就是这题,这题敢于交上代码了,然后看着绿油油的AC我也很意外。细细分析完复杂度,却又发现是正确的了。。还是太笨了捏

题意

给定数组a[],求数组中有多少等差子数组。

做法

考虑f[i][d]表示以第i个数字结尾,公差的d的方案数。

然后转移很简单,f[i][d] += f[j][d],其中a[j] + d == a[i]。做到这里 ,可能就会发现,不止a[j] + d,还有a[j] - d。那就再加一个g[i][d]表示第i个数字结尾,公差为d的方案数好了。

至于a[i] ± d的位置怎么找,很简单,放进vector就好了。

int a[N], f[N][20005], g[N][20005];
vector<int> v[20005];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        v[a[i]].emplace_back(i);
    }
    int ma = *max_element(a + 1, a + 1 + n);
    // f[i][d]表示第i个路灯结尾?
    // f[j][d] 其中 a[i] -或+ d == a[j]
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int d = 0; d <= ma; d++)
        {
            // 枚举公差,看看前面有几个符合条件的
            int pos;
            pos = a[i] - d;
            if (pos >= 0) for (auto j : v[pos]) {
                                if (j < i) f[i][d] = (f[i][d] + f[j][d] + 1) % mod;
                                else break;
                            }
            ans = (ans + f[i][d]) % mod;

            if (d != 0)
            {
                pos = a[i] + d;
                if (pos <= ma) for (auto j : v[pos]) {
                                    if (j < i) g[i][d] = (g[i][d] + g[j][d] + 1) % mod;
                                    else break;
                                }
                ans = (ans + g[i][d]) % mod;
            }
        }
    }
    cout << (ans + n) % mod;
}



朴小明
14天前

前言:

应该没什么人打这场吧。。
写个题解给自己看了。
K 不会,其他的都不是很难,顶多G和H算midium难度。
A用python写实在是太好写了!!!我用C++写了一大坨样例过不去,用python三两下就整完了,感受到了python做模拟题的方便。

H.原始串的个数

题意:求长度为n的非周期二进制字符串的数量。即没有长度 < n的循环节。

做法一(dp):

考虑f[i]为长度为i的非周期二进制字符串的数量,显然01能够构成的字符串数量是2^i个,对于不合法的数量,那就是这个串有循环节,即循环节的长度是i的因子。
那么dp的转移方程就是,f[i] = qpow(2, i) - f[d] ,其中d是i的因子。

int f[N];
void solve()
{
    int n;
    cin >> n;
    f[0] = 1;
    int mul = 1;
    for (int i = 1; i <= n; i++)
    {
        f[i] += mul * 2 % mod;
        for (int j = i * 2; j <= n; j += i) 
        {
            f[j] -= f[i];
            f[j] %= mod;
        }
        mul = mul * 2 % mod;
    }
    for (int i = 1; i <= n; i++) 
    {
        cout << (f[i] + mod) % mod << "\n";
    }
}

做法二:(偷鸡)

打开OEIS输入给的样例,就会发现一个公式:
d91df144a8a321cab5df20920c87feb.png
于是套个莫比乌斯反演的板子就能水过去了。。

int f[N], g[N];
int mu[N], flg[N], p[N];
void getMu(int n)
{
    int tot = 0;
    mu[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (!flg[i]) p[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * p[j] <= n; ++j)
        {
            flg[i * p[j]] = 1;
            if (i % p[j] == 0)
            {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
}
void solve()
{
    int n;
    cin >> n;
    getMu(n);
    g[0] = 1;
    for (int i = 1; i <= n; i++) g[i] = g[i - 1] * 2 % mod;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j += i) 
        {
            f[j] += g[j / i] * mu[i];
            f[j] %= mod;
        }
    }
    for (int i = 1; i <= n; i++) cout << (f[i] + mod) % mod << "\n"; 
}

G.猫雷的复活赛

题意:两个人博弈,从(0,0)位置开始移动,每次可以移动【1,k】之间的一个整数,终点是(n,m),谁先无法操作谁就输了,问谁能赢。

做法:

先简单证明下一维的情况:
2beb07a2f40524401ed2fca4d4d2cc7.png
从终点往前考虑,就能看出来哪些是必胜区间,哪些是必败区间了。

于是就可以得到结论:n % (k + 1) != 0时,那就必胜。

对于二维的情况,可以把他们当成两个独立的游戏,在博弈论中,两个互相独立的游戏,他们的结果异或起来,为0那就是输,不为0那就是赢。具体证明可以见进阶指南p187和p188的例题。

于是这题就做完了。