• 欢迎光临~

2022.8.6 颓废记录

开发技术 开发技术 2022-08-06 次浏览

Preface

又是颓废的一天 www

Content

[CF912D]Fishes

有一个长为 (n),宽为 (m) 的鱼缸,还有一个边长为 (r) 的正方形渔网。往鱼缸里放 (k) 条鱼,问用渔网随机在浴缸里捞鱼的最大期望是多少。

(1le r le n,mle 10^5,1le k le min(ntimes m,10^5))

虽然题面含期望,但其实这题思路和期望没有半毛钱关系 qwq。

(也不知道为啥我会在 (texttt{graph}) 题单里看到这题 /yiw)

把期望转化成总答案除以总个数的形式,会发现这题要求的就是总答案的最大值。

一个网格如果放了一条鱼,那么这个网格对答案的贡献显然就是被渔网覆盖的次数。

那么我们选出被覆盖次数最多的网格即可。

然而 (10^5) 的数据范围显然不支持枚举,可以用数学方法,但 wtcl QAQ,想了半天不会。

但这并不意味着这道题就做不出来了,考虑一个网格的经典处理手法,行列分离处理。

一个网格被覆盖的次数,珂以化为它被横向覆盖的次数乘以它被纵向覆盖的次数。

这两个东西很好处理,直接跑差分就行。

然后这个问题就转化为:给定 (a,b) 两个序列,求 (a_itimes b_j) 的前 (k) 大值。

这个问题也比较经典,参考 [POJ2442]Sequence 这题的思路,用优先队列维护即可。

这里我用了 std::unordered_map 判重,时间复杂度姑且算作 (O(klog^2k)) 叭 awa。

// Problem: CF912D Fishes
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF912D
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,m,r,k;
int a[maxn],b[maxn];
struct node {
    int x,y;
    node() {
        x = y = 0;
    }
    node(int x,int y):x(x),y(y){}
    bool operator < (const node& p)const {
        return 1ll * a[x] * b[y] < 1ll * a[p.x] * b[p.y];
    }
};
priority_queue<node> q;
unordered_map<int,bool> vis[maxn];
int main() {
    scanf("%d %d %d %d",&n,&m,&r,&k);
    for(int i = 1;i <= n - r + 1;++ i)++ a[i],-- a[i + r];
    for(int i = 1;i <= m - r + 1;++ i)++ b[i],-- b[i + r];
    for(int i = 1;i <= n;++ i)a[i] += a[i - 1];
    for(int i = 1;i <= m;++ i)b[i] += b[i - 1];
    sort(a + 1 , a + 1 + n , greater<int>());
    sort(b + 1 , b + 1 + m , greater<int>());
    q.emplace(1 , 1);
    vis[1][1] = true;
    long long ans = 0;
    while(k --) {
        auto [x , y] = q.top();
        q.pop();
        ans += 1ll * a[x] * b[y];
        if(x < n&&vis[x + 1].find(y) == vis[x + 1].end()) {
            vis[x + 1][y] = true;
            q.emplace(x + 1 , y);
        }
        if(y < m&&vis[x].find(y + 1) == vis[x].end()) {
            vis[x][y + 1] = true;
            q.emplace(x , y + 1);
        }
    }
    printf("%.10lfn",(double)(1.0 * (double)ans) / (double)(1.0 * (double)(n - r + 1) * (double)(m - r + 1)));
    return 0;
}

小插曲:一开始我怎么调都调不对,改了半天后发现 while 循环里我写成了 auto& [x,y]=q.top(),这样一搞 (x,y) 的取值就成了 q.pop() 后的队首,然后就爆炸了 QAQ。

这个故事告诉我们,不要瞎用不熟悉的语法 QAQ。

[CF1056E]Check Transcription

给定一个 (01)(t) 和一个字符串 (s),求字符串对 ((r_0,r_1)(r_0neq r_1)) 的个数,满足将 (t) 中所有 (0) 置换为 (r_0)(1) 置换为 (r_1)(t=s)

(2le |t|le 10^5,1le |s|le 10^6)

当初压根看不明白的题,现在感觉好简单 /cy

SA 的解法,但我 SA 太渣想不到 QAQ。

方案数并不是非常多,考虑枚举 (r_0) 的长度。

发现此时 (r_1) 的长度也随之确定,那么 (t,r_0,r_1) 其实就已经确定下来了,判断是否满足 (t=sland r_0neq r_1) 即可。

这个问题可以用哈希解决,思路并不复杂,但代码写出来真的很恶心。

至于时间复杂度,发现 (0,1) 至少有一个在 (t) 中出现了不少于 (frac{|t|}{2}) 次。

那么枚举的次数为 (O(frac{|s|}{|t|})),每次判断是 (O(|t|)) 的,则时间复杂度 (O(|s|))

(我并没有直接去枚举那个出现次数较多的,这样虽然时间复杂度不标准但也能过)

要注意的是,这题用自然溢出会 Wrong Answer on test#17(别问我怎么知道的)

我尝试了 intlong long 都不行,不知道 unsigned long long行不行,反正换成取模就过了 awa

Code

// Problem: CF1056E Check Transcription
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1056E
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 5;
const int maxm = 1e5 + 5;
const ll p = 13331;
const ll mod = 1e9 + 7;
char t[maxn],s[maxn];
unsigned long long Hash[maxn],pw[maxn];
int n,m;
int main() {
    scanf("%s %s",t + 1,s + 1);
    m = strlen(t + 1);
    n = strlen(s + 1);
    pw[0] = 1;
    Hash[0] = 0;
    for(int i = 1;i <= n;++ i) {
        pw[i] = pw[i - 1] * p % mod;
        (Hash[i] = Hash[i - 1] * p % mod + s[i]) % mod;
    }
    int ans = 0;
    int cnt1 = 0,cnt2 = 0;
    for(int i = 1;i <= m;++ i)cnt1 += t[i] == '0',cnt2 += t[i] == '1';
    for(int len1 = 1;len1 <= (n - cnt2) / cnt1;++ len1) {
        int len2 = (n - cnt1 * len1) / cnt2;
        if(len1 * cnt1 + len2 * cnt2 != n)continue ;
        int cur = 0,st1 = 0,st2 = 0;
        bool flag = true,flag1 = false,flag2 = false;
        for(int i = 1;i <= m;++ i) {
            if(!flag)break ;
            if(t[i] == '0') {
                if(flag1)flag &= ((Hash[cur + len1] - Hash[cur] * pw[len1] % mod + mod) % mod == (Hash[st1 + len1] - Hash[st1] * pw[len1] % mod + mod) % mod);
                else st1 = cur,flag1 = true;
                cur += len1;
            }
            else {
                if(flag2)flag &= ((Hash[cur + len2] - Hash[cur] * pw[len2] % mod + mod) % mod == (Hash[st2 + len2] - Hash[st2] * pw[len2] % mod + mod) % mod);
                else st2 = cur,flag2 = true;
                cur += len2;
            }
            if(flag1&&flag2)flag &= ((Hash[st1 + len1] - Hash[st1] * pw[len1] % mod + mod) % mod != (Hash[st2 + len2] - Hash[st2] * pw[len2] % mod + mod) % mod);
        }
        ans += flag;
    }
    printf("%d",ans);
    return 0;
}

[CF1093G]Multidimensional Queries

(n)(k) 维的点 (a_1ldots a_n)​,两点 ((x_1,x_2,ldots,x_k​),(y_1​,y_2​,ldots,y_k​))间的曼哈顿距离为 (sumlimits_{i=1}^k |x_i-y_i|)

(Q) 次操作,操作分两种:

  • (1 i b_1 b_2,ldots,b_k)​,表示将 (a_i) 修改为 ((b_1,b_2,ldots,b_k))

  • (2 l r),表示询问 ([l,r]) 内最大的两点间曼哈顿距离。

(1 le n,Q le 2times 10^5,1le kle 5)

这种数据结构的处理手法还是不够熟练 QAQ。

此处令 (a) 数组第二维和 (b) 数组下标从 (0) 开始,即 (a_{i,0},a_{i,1}ldots a_{i,k-1})(b_0,b_1ldots b_{k-1})

首先发现 (k) 这个玩意非常小,时间复杂度带个 (2^k) 都完全没问题。

发现绝对值非常不友好,考虑去掉绝对值,然后我就在那推导转切比雪夫距离,然后去世

发现 (|x-y|) 其实可以转化为 (max(x-y,y-x))

再结合 (k) 如此小的范围,设计出一个算法:

用二进制表示点 (a_i)(k) 个坐标是取正还是取负,比如(17=(10001)),也就是 (+a_{i,0}-a_{i,1}-a_{i,2}-a_{i,3}+a_{i,4}),记作 (a_i) 的权值。

(2^k) 棵线段树,第 (x) 棵线段树中的叶子结点就表示 (x) 的二进制位对应的点的权值。

至于询问,设 (f(i)) 表示第 (i) 棵线段树中 ([l,r]) 区间内的最大值。

(ans = maxlimits_{iin [0,2^{k-1})} f(i)+f(2^{k}-1-i))

时间复杂度 (O(Nlog N times 2^k))

Code

// Problem: CF1093G Multidimensional Queries
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1093G
// Memory Limit: 500 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int maxk = 5;
int n,k,x;
int a[maxn][maxk];
int b[maxk];
struct Segment_Tree {
    int ls[maxn << 2],rs[maxn << 2],sum[maxn << 2];
    void pushup(int i) {
        sum[i] = max(sum[i << 1] , sum[i << 1 | 1]);
        return ;
    }
    void build(int i,int l,int r) {
        ls[i] = l;
        rs[i] = r;
        sum[i] = -1e9;
        if(l == r) {
            sum[i] = 0;
            for(int j = 0;j < k;++ j)sum[i] += (x >> j & 1) ? a[l][j] : -a[l][j];
            return ;
        }
        int mid = l + r >> 1;
        build(i << 1 , l , mid);
        build(i << 1 | 1 , mid + 1 , r);
        pushup(i);
        return ;
    }
    void modify(int i,int pos) {
        if(ls[i] == rs[i]) {
            sum[i] = 0;
            for(int j = 0;j < k;++ j)sum[i] += (x >> j & 1) ? b[j] : -b[j];
            return ;
        }
        int mid = ls[i] + rs[i] >> 1;
        if(pos <= mid)modify(i << 1 , pos);
        else modify(i << 1 | 1 , pos);
        pushup(i);
        return ;
    }
    int query(int i,int l,int r) {
        if(ls[i] >= l&&rs[i] <= r) {
            return sum[i];
        }
        if(ls[i] > r||rs[i] < l)return -1e9;
        int mid = ls[i] + rs[i] >> 1,s = -1e9;
        if(l <= mid)s = max(s , query(i << 1 , l , r));
        if(r > mid)s = max(s , query(i << 1 | 1 , l , r));
        return s;
    }
}tr[32];
int main() {
    scanf("%d %d",&n,&k);
    for(int i = 1;i <= n;++ i)
        for(int j = 0;j < k;++ j)scanf("%d",&a[i][j]);
    for(x = 0;x < (1 << k);++ x)tr[x].build(1 , 1 , n);
    int Q;
    scanf("%d",&Q);
    int S = (1 << k) - 1;
    while(Q --) {
        int op,i,l,r;
        scanf("%d",&op);
        if(op & 1) {
            scanf("%d",&i);
            for(int j = 0;j < k;++ j)scanf("%d",&b[j]);
            for(x = 0;x < (1 << k);++ x)tr[x].modify(1 , i);
        }
        else {
            scanf("%d %d",&l,&r);
            int ans = -1e9;
            for(x = 0;x < (1 << (k - 1));++ x)ans = max(ans , tr[x].query(1 , l , r) + tr[S ^ x].query(1 , l , r));
            printf("%dn",ans);
        }
    }
    return 0;
}

下午打珂学月赛,被题面气得够呛,随便划了划水就跑路了。

晚上比赛前写了道交互题,然后不出意外崩了,感觉药丸。

upd:晚上交互题居然做出来了,可惜一开始脑抽,复杂度实现错了,不然排名能高好多的 QAQ。

[CF1713D]Tournament Countdown

(注:写题解时 system test 还未进行,如果 fst 了就看个乐吧 qwq)

(2^n) 个人打淘汰赛。(1) 号和 (2) 号打,(3) 号和 (4) 号打,依次类推。

胜利的 (2^{n-1}) 人再这样打下去,直到唯一的胜者出现。

你不知道比赛的具体情况,请用不超过 (lceil frac{2^{n+1}}{3} rceil) 次询问得出胜者,询问格式如下:

  • ? a b,表示询问 (a) 号和 (b) 号胜利次数的关系。(1) 表示 (a) 赢的次数比 (b) 多,(2) 表示 (a) 赢的次数比 (b) 少,(0) 表示 (a,b) 胜利次数相同。

(1le nle 17)

为了方便,设 (i) 胜利次数为 (c_i)

发现题中要求的其实就是 (c) 值最大的人,显然最暴力的解法是直接进行 (2^n-1) 次询问得出答案。

但想一想会发现,这些询问里有很多是不必要的,我们可以通过已知的条件推断出来。

先推导简单的情况再进行推广,先令 (n=2),发现其实只需要 (2) 次询问就能找出答案,推导过程如下:

首先,询问 (1 3),对交互结果进行分类讨论:

  • 结果为 (1):也就是 (c_1gt c_3= 0),说明 (c_1 = 1),也就是说 (1)(2) 的比赛中 (1) 一定胜利了,否则 (c_1) 不可能为 (1)。那 (2) 就没有询问的必要了,直接询问下 (1 4) 即可。

  • 结果为 (2):和上面类似。

  • 结果为 (0):即 (c_1=c_3=0),那就可以推出来 (c_2=c_4=1),询问 (2 4) 即可。

综上,(n=2) 的时候只需 (2) 次询问。

考虑推广,(n=3) 的时候怎么办?

其实就是拆成两个 (n=2),然后再对这两个局部的胜利者进行一次询问。

继续写下去,正解就呼之欲出了。

  1. 首先特判 (n=1) 的情况,直接用一次询问得出答案。

  2. (n gt 1),就把 (2^n) 拆成 (2^{n-2})(4) 人小组,用我们上面的算法判断,得出 (2^{n-2}) 个胜者,再递归到 (n-2) 的情况求解。

分析一下询问次数(这个我并不是太懂,如果有误请大佬指出):

原来 (4) 个数中求最大值需要 (3) 次询问,现在变成了 (2) 次,那么询问次数就是 (frac{2}{3}times 2^{n-2}=frac{2^{n-1}}{3}) 次,可以通过。

(老觉得这个东西很怪,可能有问题,请大佬们帮忙看看 QAQ)

Code

// Problem: D. Tournament Countdown
// Contest: Codeforces - Codeforces Round #812 (Div. 2)
// URL: https://codeforces.com/contest/1713/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define Chtholly set<node>::iterator
#define SET set<int>::iterator
#define VEC vector<int>::iterator
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 5e5 + 5;
const int maxm = 3e6 + 5;
const int maxk = 30;
const ll mod = 1e9 + 7;
const int INF = 1e9;
const ll INFll = 1e16;
int n;
std::vector<int> s;
int ask(int a,int b) {
    int p;
    printf("? %d %dn",a,b);
    fflush(stdout);
    scanf("%d",&p);
    return p;
}
void solve(int n) {
    if(n <= 1) {
        printf("! %dn",ask(s[0] , s[1]) == 1 ? s[0] : s[1]);
        fflush(stdout);
        return ;
    }
    else if(n == 2) {
        int p = ask(s[0] , s[3]);
        if(p == 1) {
            printf("! %dn",ask(s[0] , s[2]) == 1 ? s[0] : s[2]);
            fflush(stdout);
        }
        else if(p == 2) {
            printf("! %dn",ask(s[1] , s[3]) == 1 ? s[1] : s[3]);
            fflush(stdout);
        }
        else {
            printf("! %dn",ask(s[1] , s[2]) == 1 ? s[1] : s[2]);
            fflush(stdout);
        }
        return ;
    }
    vector<int> G;
    for(int i = 0;i < (1 << n);i += 4) {
        int p = ask(s[i] , s[i + 2]);
        if(p == 1) {
            G.pb(ask(s[i] , s[i + 3]) == 1 ? s[i] : s[i + 3]);
        }
        else if(p == 2) {
            G.pb(ask(s[i + 2] , s[i + 1]) == 1 ? s[i + 2] : s[i + 1]);
        }
        else {
            G.pb(ask(s[i + 1] , s[i + 3]) == 1 ? s[i + 1] : s[i + 3]);
        }
    }
    s = G;
    solve(n - 2);
    return ;
}
void work() {
    scanf("%d",&n);
    s.clear();
    for(int i = 1;i <= (1 << n);++ i)s.pb(i);
    solve(n);
    return ;
}
int main() {
    int T;
    scanf("%d",&T);
    while(T --)work();
    return 0;
}
程序员灯塔
转载请注明原文链接:2022.8.6 颓废记录
喜欢 (0)