首页 > 其他分享 >『模拟赛』CSP-S模拟5

『模拟赛』CSP-S模拟5

时间:2024-09-27 21:01:31浏览次数:10  
标签:rt ch int sum qr ans CSP 模拟

Rank

一般

image

A. 光

胱!

妈的传奇题目控我两个小时想 \(\mathcal{O(1)}\) 做法。

其实带下取整的四个四元一次方程根本解不了,考虑到这个题给的范围只有 \(n\le 1500\),可以枚举两维剩下二分到一个小区间里去做,复杂度 \(\mathcal{O(n^2\log n)}\),当然数据水卡卡枚举的边界 \(\mathcal{O(n^3)}\) 也能过。

学的 K8He 的带 \(4^4\) 常数的 \(\mathcal{O(n)}\) 做法。考虑到以四为单位减小不会有浪费的亮度,因此这样贪心着耗电是很优的。我们枚举最后剩下需要的亮度,进而求出我们需要进行以四为单位贪心的数据,优先队列随便维护一下,然后处理一下以四为单位贪不了的和我们枚举的剩余局面,三者消耗之和即为答案。

想卡最优解来着,所以提前跑了一遍把剩余局面的所有消耗跑出来赋给数组了,结果还是比不过小常数选手们,拜谢!

注释掉的是跑剩余局面的代码,有需要的自行打开。

点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch = getchar();lx x = 0 , f = 1;
	for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
	for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5 , M = 6000;
const int mod = 998244353;
int a, b, c, d;
int ans = 1e9;
int res[4][4][4][4]={0,1,2,3,1,2,2,3,2,2,3,4,3,3,4,4,1,2,2,3,2,2,2,3,3,3,3,4,4,4,4,4,2,2,
3,4,3,3,3,4,4,4,4,4,5,5,5,5,3,3,4,4,4,4,4,4,5,5,5,5,6,6,6,6,1,2,3,4,2,3,3,4,2,2,3,4,3,3,
4,4,2,3,3,4,3,3,3,4,3,3,4,4,4,4,4,4,2,2,3,4,3,3,4,4,4,4,4,4,5,5,5,5,3,3,4,4,4,4,4,4,5,5,
5,5,6,6,6,6,2,3,4,5,2,3,4,5,3,3,4,5,4,4,5,5,2,3,4,5,2,3,4,5,3,4,4,5,4,4,5,5,3,3,4,5,3,4,
4,5,4,4,4,5,5,5,5,6,4,4,5,5,4,4,5,5,5,5,5,6,6,6,6,6,3,4,5,6,3,4,5,6,4,4,5,6,4,4,5,6,3,4,
5,6,3,4,5,6,4,4,5,6,4,4,5,6,4,4,5,6,4,4,5,6,5,5,5,6,5,5,6,6,4,4,5,6,4,4,5,6,5,5,6,6,6,6,6,6};
priority_queue<pii, vector<pii >, less<pii > > q;
namespace Wisadel
{
    void Wfang(pii x, pii y)
    {
        if(x.se + y.se == 5) q.push({y.fi - 1, y.se});
        else q.push({y.fi - 2, y.se});
    }
    short main()
    {
        freopen("light.in", "r", stdin) , freopen("light.out", "w", stdout);
        a = qr, b = qr, c = qr, d = qr;
        fo(i1, 0, 3) fo(i2, 0, 3) fo(i3, 0, 3) fo(i4, 0, 3)
        {
            int A = a - i1, B = b - i2, C = c - i3, D = d - i4;
            q.push({A, 1}), q.push({B, 2}), q.push({C, 3}), q.push({D, 4});
            int tim = 0, cs;
            int ba, bb, bc, bd;
            while(q.top().fi >= 4)
            {
                pii aa = q.top(); q.pop();
                pii bb = q.top(); q.pop();
                pii cc = q.top(); q.pop();
                pii dd = q.top(); q.pop();
                q.push({aa.fi - 4, aa.se});
                Wfang(aa, bb), Wfang(aa, cc), Wfang(aa, dd);
                tim++;
            }
            A = max(q.top().fi, 0), ba = q.top().se, q.pop(), B = max(q.top().fi, 0), bb = q.top().se, q.pop(),
            C = max(q.top().fi, 0), bc = q.top().se, q.pop(), D = max(q.top().fi, 0), bd = q.top().se, q.pop();
            cs = A + B + C + D;
            if(ba + bd != 5) swap(B, D), swap(bb, bd);
            if(ba + bd != 5) swap(C, D), swap(bc, bd);
            fo(i, 0, A) fo(j, 0, B) fo(k, 0, C)
            {
                int l = -1;
                if(A - i - (j / 2) - (k / 2) >= 0) l = max(l, (A - i - (j / 2) - (k / 2)) * 4);
                if(B - j - (i / 2) - (k / 4) >= 0) l = max(l, (B - j - (i / 2) - (k / 4)) * 2);
                if(C - k - (i / 2) - (j / 4) >= 0) l = max(l, (C - k - (i / 2) - (j / 4)) * 2);
                if(D - (i / 4) - (j / 2) - (k / 2) >= 0) l = max(l, D - (i / 4) - (j / 2) - (k / 2));
                if(l != -1) cs = min(cs, i + j + k + l);
            }
            // fo(i, 0, i1) fo(j, 0, i2) fo(k, 0, i3)
            // {
            //     int l = -1;
            //     if(i1 - i - (j / 2) - (k / 2) >= 0) l = max(l, (i1 - i - (j / 2) - (k / 2)) * 4);
            //     if(i2 - j - (i / 2) - (k / 4) >= 0) l = max(l, (i2 - j - (i / 2) - (k / 4)) * 2);
            //     if(i3 - k - (i / 2) - (j / 4) >= 0) l = max(l, (i3 - k - (i / 2) - (j / 4)) * 2);
            //     if(i4 - (i / 4) - (j / 2) - (k / 2) >= 0) l = max(l, i4 - (i / 4) - (j / 2) - (k / 2));
            //     if(l != -1) res = min(res, i + j + k + l);
            // }
            // cout<<res<<',';
            ans = min(ans, res[i1][i2][i3][i4] + tim * 4 + cs);
        }
        // cout<<endl;
        printf("%d\n", ans);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

B. 爬

感觉最简单的一道,赛时 20min 就做出来了,不过因为 T1 耽误太久导致没细想复杂度,暴力找每一个点的所有贡献好像无论时间空间都是 \(\mathcal{O(2^n)}\) 的,不过还是能拿到 80pts,但是我在求贡献的时候没取模导致爆 long long 了挂 20pts。

其实关键点在于想到每个点的贡献是独立的,只与它和它的子节点有关。一共只有 \(n-1\) 个点可以移动,因此共有 \(2^{n-1}\) 种方案。对于非根的节点来说,它对全局的贡献应该是它的总贡献乘上其它节点的总方案数,即若设它和它子节点的个数为 \(tot\),应乘上 \(2^{n-1-tot}\),因为根节点上的蚂蚁不会动,所以 \(tot\) 要减一。

然后考虑怎么求每个点的贡献和。一种优化的思路是二进制拆分。对于二进制下数的每一位,只有出现的次数为奇异或起来才会有贡献,因此我们可以将每个数拆成二进制,在统计总贡献时先求出一点和它的子节点每一位上为 1 的数的个数,再逐位去求,那么有贡献的方案应该是 $C_{tot}^1 \ +\ C_{tot}^3\ +\cdots\ = 2^{tot-1} $,每次的贡献是 \(1\)<<\(i\),记得算上该位为 0 的数的方案数,把各位上的贡献加起来就是该点的总贡献。

点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch = getchar();lx x = 0 , f = 1;
	for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
	for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n;
int fa[N], a[N][31], num[N][31];
int hh[N], to[N], ne[N], cnt;
ll Ans;
namespace Wisadel
{
    void Wadd(int u, int v)
    {
        to[++cnt] = v;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    ll Wqp(ll x, int y)
    {
        ll res = 1;
        while(y)
        {
            if(y & 1) res = res * x % mod;
            x = x * x % mod;
            y >>= 1;
        }
        return res;
    }
    void Wdfs(int u, int fa)
    {
        int tot = (u != 1);
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            tot++;
            Wdfs(v, u);
            fo(j, 0, 30) num[u][j] += a[v][j];
        }
        ll res = 0;
        if(u != 1)
        {
            fo(i, 0, 30)
            {
                if(!num[u][i]) continue;
                res = (res + (1ll << i) * (Wqp(2, num[u][i] - 1) * Wqp(2, tot - num[u][i]) % mod - num[u][i] + mod) % mod) % mod;
            }
        }
        else
        {
            fo(i, 0, 30)
            {
                if(a[u][i])
                {
                    if(!num[u][i])
                        res = (res + (1ll << i) * (Wqp(2, tot) - 1) % mod) % mod;
                    else
                        res = (res + (1ll << i) * (Wqp(2, num[u][i] - 1) * Wqp(2, tot - num[u][i]) % mod - 1 + mod) % mod) % mod;
                }
                else
                {
                    if(!num[u][i]) continue;
                    res = (res + (1ll << i) * Wqp(2, num[u][i] - 1) % mod * Wqp(2, tot - num[u][i]) % mod) %mod;
                }
            }
        }
        Ans = (Ans + res * Wqp(2, n - 1 - tot) % mod) % mod;
    }
    short main()
    {
        freopen("climb.in", "r", stdin) , freopen("climb.out", "w", stdout);
        n = qr;
        memset(hh, -1, sizeof hh);
        fo(i, 1, n)
        {
            int bb = qr, ttt = 0;
            while(bb) a[i][ttt] = bb & 1, bb >>= 1, ttt++;
            if(i != 1) fo(j, 0, ttt) num[i][j] = a[i][j];
        }
        fo(i, 2, n) fa[i] = qr, Wadd(fa[i], i);
        Wdfs(1, 0);
        printf("%lld\n",Ans);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

C. 字符串

贪心 唐氏大分讨。

感觉做到这如果有时间静下心来想应该很好得出结论:只有 \(A\) 与 \(B\) 紧密交替出现时每个字符的回报率是 1,其它情况均小于 1,因此能交替就交替是第一准则。称 1 个 \(A\) 与 \(c\) 个 \(B\) 交替出现的串为紧密交替出现的串。

我们枚举交替串的数量,规定 \(B\) 在前 \(A\) 在后。对于剩下的 \(A\),首先置于串首最优,回报率为 1;其次由于我们交替串数量固定了,不能在新加串,因此剩下的 \(A\) 要插入到原来的 \(A\) 串中,考虑到此时每个 \(A\) 串长度为 \(1\),因此每 \(a\) 个 \(A\) 可以提供 1 的贡献。再考虑剩下的 \(B\),首先在末尾增加一个最优;其次考虑在原有的长度为 \(c\) 的 \(B\) 串中加入 \(B\),先都将其补至长度为 \(b\),剩下的每 \(b\) 个还能产生 1 的贡献。然后就做完了。

头脑冷静,理清思路最重要。

点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch = getchar();lx x = 0 , f = 1;
	for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
	for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n, m, a, b, c;
int ans;
namespace Wisadel
{
    short main()
    {
        freopen("string.in", "r", stdin) , freopen("string.out", "w", stdout);
        int T = qr;
        while(T--)
        {
            n = qr, m = qr, a = qr, b = qr, c = qr;
            int sum = 0; ans = -1e9;
            fo(i, 0, m / c)
            {
                sum = i * 2 + (c - 1) / b * i;
                int _n = n - i, _m = m - i * c;
                if(_n < 0 || _m < 0) break;
                if(_m)
                {
                    _m--, sum++;
                    if(_m)
                    {
                        int w = min(i, _m / (b - (c - 1) % b));
                        sum += w + (_m - w * (b - (c - 1) % b)) / b;
                    }
                }
                if(_n)
                {
                    _n--,sum++;
                    if(_n) sum += _n / a;
                }
                ans = max(ans, sum);
            }
            printf("%d\n", ans);
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

D. 奇怪的函数

赛时没时间了,5pts 暴力都没打完。

稍微手模一下就能发现这 \(n\) 次操作本质上是一个分段函数,考虑如何实现动态维护这个函数。

容易想到线段树,以操作为维护对象,维护每个区间有实际意义值域对应的定义域范围,所有 1 操作的总和。由于可能存在上述定义域范围不存在的情况,而此时该函数实质上变为了一个定函数,即只有一个值,所以我们还需要维护这个值。

考虑两个问题:首先是边界问题。比较好得出取 min 操作是划定定义域的上界,取 max 划定下界。其他情况我们将范围赋成极大区间即可。定值由于是定值无论取啥都一样。

第二是 pushup,考虑如何合并两个分段函数。1 操作的总和不用说,直接加就行。定义域,我们要取左区间的定义域在右区间上仍有意义的区间,思考一下,从左到右之间做了左区间的加操作,那么若一个数在定义域内,一定有 \(x+sum_{ls} \ge L_{rs}\),转换过去就是 \(x\ge L_{ls}- sum_{ls}\),由于我们取得是区间的交集,所以要取 \(L\) 的最大值和 \(R\) 的最小值。至于定值,我们可以看成是执行完左区间的操作后继续执行右区间的,如果右区间定义域不存在就取右区间的,否则视为求 \(ans_{ls}\) 在右区间上的值,跟总函数一样如下:

\[F(x)=\begin{cases}R+sum\quad x\ge R\\ x+sum\quad L\lt x\lt R\\L+sum\quad x\le L\end{cases} \]

其中 \(L,R\) 表示区间函数的定义域。

然后就做完了,比一般的线段树甚至好写。

点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch = getchar();lx x = 0 , f = 1;
	for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
	for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
int n, m;
int op[N], v[N];
ll L[N << 2], R[N << 2], sum[N << 2], ans[N << 2];
namespace Wisadel
{
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    #define mid ((l + r) >> 1)
    void Wpushup(int rt)
    {
        L[rt] = max(L[ls], L[rs] - sum[ls]), R[rt] = min(R[ls], R[rs] - sum[ls]);
        sum[rt] = sum[ls] + sum[rs];
        if(L[rs] > R[rs]) ans[rt] = ans[rs];
        else if(ans[ls] < L[rs]) ans[rt] = L[rs] + sum[rs];
        else if(ans[ls] > R[rs]) ans[rt] = R[rs] + sum[rs];
        else ans[rt] = ans[ls] + sum[rs];
    }
    void Wbuild(int rt, int l, int r)
    {
        L[rt] = -1e9, R[rt] = 1e9;
        if(l == r)
        {
            if(op[l] == 1) sum[rt] = v[l], ans[rt] = v[l];
            else if(op[l] == 2) R[rt] = v[l], ans[rt] = 0;
            else L[rt] = v[l], ans[rt] = v[l];
            return ;
        }
        Wbuild(ls, l, mid), Wbuild(rs, mid + 1, r);
        Wpushup(rt);
    }
    void Wupd(int rt, int l, int r, int x, int k, int opp)
    {
        if(l == r)
        {
            if(opp == 1) L[rt] = -1e9, R[rt] = 1e9, ans[rt] = sum[rt] = k;
            else if(opp == 2) L[rt] = -1e9, R[rt] = k, ans[rt] = sum[rt] = 0;
            else ans[rt] = L[rt] = k, R[rt] = 1e9, sum[rt] = 0;
            return ;
        }
        if(x <= mid) Wupd(ls, l, mid, x, k, opp);
        else Wupd(rs, mid + 1, r, x, k, opp);
        Wpushup(rt);
    }
    ll Wq(int x)
    {
        if(L[1] > R[1]) return ans[1];
        if(x < L[1]) return 1ll * L[1] + sum[1];
        else if(x > R[1]) return 1ll * R[1] + sum[1];
        else return x + sum[1];
    }
    short main()
    {
        freopen("function.in", "r", stdin) , freopen("function.out", "w", stdout);
        n = qr;
        fo(i, 1, n) op[i] = qr, v[i] = qr;
        Wbuild(1, 1, n);
        m = qr;
        fo(i, 1, m)
        {
            int opp = qr, pos = qr, vv;
            if(opp == 4) printf("%lld\n", Wq(pos));
            else vv = qr, Wupd(1, 1, n, pos, vv, opp);
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

这场策略依托。

感觉挺玄学的,就这场没有通读题面,就这场四道可做题。赛时光觉着 T1 大水,切不了寄寄,然后被控了 2h,本来 T3 会 50pts,T4 会 20pts,结果没做到,T2 的唐错也没拍出来,如果没写完算挂的话,这场挂了得有快 100pts 了。

还有,谁家好人打模拟赛的时候练马蜂啊啊啊!昨天打一天超级线段树因为写紧了调试不方便看所以就加了空格,然后看啥都想加空格,T1 有一半时间推式子,另一半全驯服代码了。

吃一堑长一智,以后得注意考场策略了。

快夸夸我的马蜂!


完结撒花

标签:rt,ch,int,sum,qr,ans,CSP,模拟
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18436483

相关文章

  • CSP2024-27
    2A题意:1A题意:给定\(n\timesn\)种物品,\((i,j)\)有\(a_{i,j}\)个,权值为\(b_{i,j}\),两个物品等价当且仅当\(i\)相等或\(j\)相等。初始有一个空(可重)集\(S\),每次等概率从剩余物品中选一个\(x\)出来。如果\(S\)中没有和\(x\)等价的物品,那么\(x\)加入\(S\)......
  • 9.27 模拟赛(NOIP十三连测 #10)
    2024--梦熊&太戈--NOIP十三连测#10【订正】-比赛-梦熊联盟(mna.wang)复盘开T1。差分转化。模拟了一下样例感觉方案好像是唯一确定的,不需要贪心/DP。但不太能证。想了会感觉找不出反例。然后写完了。对拍没挂。用时不到\(30\)分钟。T2。\(m\le20\)且数据随机感觉很......
  • 信息学奥赛复赛复习05-CSP-J2020-01优秀的拆分-对数函数、自然对数、以2为底的对数、
    PDF文档回复:2024092712020CSP-J题目1优秀的拆分[题目描述]一般来说,一个正整数可以拆分成若干个正整数的和例如,1=1,10=1+2+3+4等。对于正整数n的一种特定拆分,我们称它为“优秀的”,当且仅当在这种拆分下,n被分解为了若干个不同的2的正整数次幂。注意,一个数x能......
  • NOIP2024模拟测试赛(一)
    比赛链接A.tree当\(\forallv_i\le1\)时,可以直接从下往上贪心选,一个以\(u\)为根的子树中联通块如果权值和\(>k\)那么肯定能删到恰好\(k\)。否则的话就把这个联通块并到\(u\)父亲上再看就行。当\(\forallv_i\le2\)时,直接贪心可能有问题,大于\(k\)的权值和可能......
  • CSP-S 2024 第五次
    建议倒序开题A枚举\(A,D\)灯的亮度\(A,D\),设\(B,C\)灯的亮度为\(B,C\),则可以得到不等式组:\[\begin{aligned}&B/2+C/2\gea-A-D/4\\&B/2+C/2\ged-D-A/4\\&B+C/4\geb-A/2-D/2\\&B/4+C\gec-A/2-D/2\end{aligned}\]设\(B=4u+x,C=4v+y\),枚举\(x......
  • 南沙csp-j/s一对一家教 解一本通题: 1937:【06NOIP普及组】数列
    ​【题目描述】给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列,例如,当k=3时,这个序列是:1,3,4,9,10,12,13,…请你求出这个序列的第N项的值(用10进制数表示)。例如,对于k=3,N=100,正确答案应该是981。【输入】只有1行,为2个正整数,用一个......
  • [35] (CSP 集训) CSP-S 模拟 5
    T1光Hikari好神秘这个题,我觉得我解法够神秘了结果是正解考虑到这四个数虽然不能二分答案,但是它们的和是能二分答案的因此对和做二分答案然后问题变成了check怎么写设和最小的答案为\((i_1,i_2,i_3,i_4)\)注意到\(n\)只有\(1500\),考虑直接\(n^2\)枚举前两个数那么......
  • 2024/09/26 模拟赛总结
    rk4,\(0+30+40+30=100\),T1挂惨了#A.智乃的差分分类讨论,由于\(a_i\ge0\),当\(x<0\)时,可以直接升序排列当\(x>0\)时,大部分情况下可以降序排列,但可能会出现\(a_1=x\)的情况,就可以找到第一个不为\(x\)且不为\(0\)的数,swap掉即可然后是最麻烦的\(x=0\),当出现最多的......
  • 20240926 模拟赛总结
    \(10+30+30+10=80\),有挂惨了。比赛链接:http://172.45.35.5/d/HEIGETWO/homework/66f4fec944f0ed11b057cca9或http://172.45.35.5/d/HEIGETWO/homework/66f4fec944f0ed11b057cca9A-智乃的差分题意:给定一个数列\(a_n\)(\(0\lea_i\le10^9\)),你可以重排这个数组,问是否存在一......
  • 2024/09/25 模拟赛总结
    rk5,\(100+40+5+0=145\)。T2上物理课把式子推出来了,感谢孟德的馈赠#A.变换简单dp,为什么都写\(3\)维啊令\(dp_{i,j,0/1,0/1}\)为考虑前\(i\)位改了\(j\)位,当前是/不是“山谷”,前一位是/不是“山谷”显然,相邻两位一定不会都是山谷,所以\(dp_{i,j,1,1}\)一定不存在考......