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

『模拟赛』CSP-S模拟5

时间：2024-09-30 16:12:56浏览次数：1  
标签：cnt return int targ now CSP 模拟 fo

Rank

烂

image

A. median

签。

你说得对，但是赛时嗯打 150 行 5k 代码超级分讨过了。

因为容斥做的不好，求总的然后减总会差点东西，所以直接分着加。发现如果中位数在这五个数中不止出现一次那么就会算重，所以分三种大情况考虑。

一，中位数只有一个。那么此时我们需要找到另外两个小于它的和另外两个大于它的，符合乘法原理。

二，中位数有两个。那么此时要分为一个数比它们小和两个数比它们小的情况。

三，中位数三个及以上。此时无论其它数选什么都不会改变贡献。

考虑实现以上操作需要维护什么。首先值域范围 \(10^9\)，硬维护数量铁开不下，但 \(n\) 只有 \(10^5\)，也就是说最多有 \(5\times 10^5\) 种不同的数，读入之后离散化一下即可，然后处理出每个数组的前缀和，再根据上述情况做就行了。外层枚举中位数在离散化后的编号，内层找含有该数的数组，然后进 dfs 找到方案即可。复杂度看起来是 \(\mathcal{O(5n\times 2^5)}\) 的，但实际上跑不满，效率还是很高的。

赛时由于是一点一点打的，可能常数有点大，很多赘余可以合并起来，但我不想重构了，所以就放这个删了注释的赛时代码了，理解之后还是很好理解的。

点击查看代码 
#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 = 998244353;
int n, m;
int a[6][N], al[N * 5], tot, cnt[6][N * 5];
bool yz1[6], yz2[6], yzz[6], yz3[6], yz4[6];
ll ans;
namespace Wisadel
{
    void Wdfs1(int wc, int targ, int now, int rsum)
    {
        if(rsum == 2)
        {
            ll res = cnt[wc][targ] - cnt[wc][targ - 1];
            ll lca = 1, rca = 1;
            fo(i, 1, 5)
            {
                if(i == wc) continue;
                if(yz1[i]) lca = lca * cnt[i][targ - 1] % mod;
                if(yz2[i]) rca = rca * (cnt[i][tot] - cnt[i][targ]) % mod;
            }
            res = res * lca % mod * rca % mod;
            ans = (ans + al[targ] * res) % mod;
            return;
        }
        if(now > 5) return ;
        if(now == wc || yz1[now]){Wdfs1(wc, targ, now + 1, rsum); return;}
        if(cnt[now][tot] - cnt[now][targ] > 0) yz2[now] = 1, Wdfs1(wc, targ, now + 1, rsum + 1), yz2[now] = 0;
        Wdfs1(wc, targ, now + 1, rsum);
    }
    void Wdfs(int wc, int targ, int now, int lsum)
    {
        if(lsum == 2)
        {
            Wdfs1(wc, targ, 1, 0);
            return ;
        }
        if(now > 5) return ;
        if(now == wc){Wdfs(wc, targ, now + 1, lsum); return;}
        if(cnt[now][targ - 1] > 0) yz1[now] = 1, Wdfs(wc, targ, now + 1, lsum + 1), yz1[now] = 0;
        Wdfs(wc, targ, now + 1, lsum);
    }
    void Wdfss(int now, int targ, int ned)
    {
        if(ned <= 0)
        {
            ll res = 1, cc = 1;
            fo(i, 1, 5)
            {
                if(yzz[i]) res = res * (cnt[i][targ] - cnt[i][targ - 1]) % mod;
                else cc = cc * (cnt[i][tot] - (cnt[i][targ] - cnt[i][targ - 1])) % mod;
            }
            ans = (ans + res * cc % mod * al[targ] % mod) % mod;
            return;
        }
        if(now > 5) return;
        if(cnt[now][targ] - cnt[now][targ - 1] > 0) yzz[now] = 1, Wdfss(now + 1, targ, ned - 1), yzz[now] = 0;
        Wdfss(now + 1, targ, ned);
    }
    void Wdfsss(int now, int targ, int ned)
    {
        if(ned <= 0)
        {
            ll res = 1, lsu = 1, rsu = 1;
            fo(i, 1, 5)
            {
                if(yz3[i]) res = res * (cnt[i][targ] - cnt[i][targ - 1]) % mod;
                else if(yz4[i]) lsu = lsu * cnt[i][targ - 1] % mod;
                else rsu = rsu * (cnt[i][tot] - cnt[i][targ]) % mod;
            }
            ans = (ans + res * lsu % mod * rsu % mod * al[targ] % mod) % mod;
            return;
        }
        if(now > 5) return;
        if(yz3[now]){Wdfsss(now + 1, targ, ned); return ;}
        if(cnt[now][targ - 1] > 0) yz4[now] = 1, Wdfsss(now + 1, targ, ned - 1), yz4[now] = 0;
        Wdfsss(now + 1, targ, ned);
    }
    void Wdfs2(int now, int targ, int ned)
    {
        if(ned <= 0)
        {
            Wdfsss(1, targ, 1);
            Wdfsss(1, targ, 2);
            return;
        }
        if(now > 5) return;
        if(cnt[now][targ] - cnt[now][targ - 1] > 0) yz3[now] = 1, Wdfs2(now + 1, targ, ned - 1), yz3[now] = 0;
        Wdfs2(now + 1, targ, ned);
    }
    short main()
    {
        freopen("median.in", "r", stdin) , freopen("median.out", "w", stdout);
        n = qr;
        fo(i, 1, 5)
            fo(j, 1, n) a[i][j] = qr, al[(i - 1) * n + j] = a[i][j];
        tot = n * 5;
        sort(al + 1, al + tot + 1);
        tot = unique(al + 1, al + tot + 1) -al - 1;
        fo(i, 1, 5)
            fo(j, 1, n)
                cnt[i][lower_bound(al + 1, al + tot + 1, a[i][j]) -al] ++;
        fo(i, 1, 5) fo(j, 1, tot) cnt[i][j] += cnt[i][j - 1];
        fo(i, 1, tot)
            fo(j, 1, 5)
                if(cnt[j][i] - cnt[j][i - 1] > 0)
                    Wdfs(j, i, 1, 0);
        fo(i, 1, tot)
        {
            if(i > 1 && i < tot) Wdfs2(1, i, 2);
            fo(tim, 3, 5)
                Wdfss(1, i, tim);
        }
        printf("%lld\n", ans);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

B. travel

也算是签吧，虽然改了数据绑包之后保龄了。

赛时完全没想到自环对答案也是有影响的，就直接删了没管，然后 hack 全输出 Yes 的人的时候顺手给我 hack 了。

借助样例解释理解一下，就是当选择一个起点和终点后能一直跑下去并且存在不一样的路径数。事实上就是找环，显然当取环上某一点作为起点和终点时，如果 \(k\) 是环大小的倍数，则答案为 1，否则为 0，无论 \(k\) 取多大都不会成为一个定值。再考虑我漏掉的自环的影响，发现如果一条路径上存在两个及以上的自环，它的每一个自环都可以走任意次，以相连的两个点各有一个自环为例，根据 \(k\) 值的不同，它所得到的答案的数量为 \(k\)，显然不存在一个极限值使得其成为定值。

那么就考虑如何实现了。其实是非常简单的，一开始仍然不把自环连进去，重边用 set 处理一下，找环用 dfs 就行，找不到环再去枚举每一条路径求其上自环数量，复杂度 \(\mathcal{O(n+m)}\)。

点击查看代码 
#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 = 5e5 + 5;
const int mod = 998244353;
int n, m;
int hh[N], to[N << 1], ne[N << 1], cnt, tot[N], rd[N], zh[N];
bool vis[N], bb[N], huan, yz[N];
set<int> st[N];
namespace Wisadel
{
    void Wadd(int u, int v)
    {
        to[++cnt] = v;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    void Wdfs(int u)
    {
        vis[u] = 1,yz[u] = 1;
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(yz[v]){huan = 1; return;}
            Wdfs(v);
            if(huan) return;
        }
        yz[u] = 0;
    }
    bool Wbfs(int x)
    {
        queue<int> q;
        int sum = 0;
        q.push(x);
        while(q.size())
        {
            int u = q.front(); q.pop();
            sum += zh[u];
            if(sum > 1) return 1;
            for(int i = hh[u]; i != -1; i = ne[i])
                q.push(to[i]);
        }
        return 0;
    }
    short main()
    {
        freopen("travel.in", "r", stdin) , freopen("travel.out", "w", stdout);
        n = qr, m = qr; huan = 0;
        memset(hh, -1, sizeof hh);
        fo(i, 1, m)
        {
            int a = qr, b = qr;
            if(a == b){zh[a] += 1; continue;}
            st[a].insert(b);
        }
        fo(i, 1, n) for(auto j : st[i]) Wadd(i, j);
        fo(i, 1, n)
        {
            if(!vis[i]) Wdfs(i);
            if(huan) break;
        }
        if(huan) printf("Yes\n");
        else
        {
            bool can = 0;
            fo(i, 1, n)
                if(!bb[i])
                    if(Wbfs(i)){can = 1; break;}
            if(can) printf("Yes\n");
            else printf("No\n");
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

C. game

挺简单的博弈论，不过赛时唐了错解没注释掉，然后又顺手给我 hack 了。

首先最基本的，偶数个 1 同时存在的局面一定是必败局面；额外很显然的，两个相同的数的局面也一定是必败局面；那么给出推论：偶数个相同的数存在的局面一定是必败局面。

那么现在只需证明两件事。其一是这些局面无论如何操作结果均不在这个集合内。比较显然的是，后首跟着先手做相同操作，一定能使结果局面仍为必败，因为这样操作的终点是剩余两个 1。此时我们发现可以将必败局面集合扩展到偶数个并且可分为两两相同的若干组的局面。

其二是不在集合内的局面有可以一步操作达到这个局面的操作。我们将个数按升序排序。可以发现此时只要我们选取最大的无法配对为两两相同的一组的一个数，一定存在一组分配方案使得结果局面在集合内。这个证明比较容易，对于当前有奇数的数的情况，达到必败局面所需的个数为 \(\sum_{i=1}^n\ a_{i+1}-a_i\ [i \mod 2 = 0]\)，显然其值是小于最大值的；对于偶数的情况，我们让最大的无法配对的数与最小的无法配对的数配对，所需结果仍然是小于拿去后可操作数的，所以结论得证。

然后就非常简单了，对于奇数直接 Yes，偶数就排个序，判一下能否两两配对即可。

点击查看代码 
#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;
const int mod = 998244353;
int n;
int a[N];
namespace Wisadel
{
    short main()
    {
        freopen("game.in", "r", stdin) , freopen("game.out", "w", stdout);
        int T = qr;
        while(T--)
        {
            n = qr;
            fo(i, 1, n) a[i] = qr;
            if(n & 1){printf("Yes\n"); continue;}
            bool can = 0;
            sort(a + 1, a + 1 + n);
            fo(i, 1, n)
            {
                if(i & 1) continue;
                if(a[i] != a[i - 1]){can = 1; break;}
            }
            if(can) printf("Yes\n");
            else printf("No\n");
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

D. counter

二分的题，看着想 ABC 常出的那种头脑风暴题，改出来再写。

末

模拟赛之决战数据之巅

赛后一看人都傻了，一车 300+，要是 noip 也能这样就好了。

然后就是各种群魔乱舞，T2 输出 Yes 拿 90pts 都算好的，T3 多测输出 Yes 也能拿 90pts 就很逆天了，T4 下午发现没人打到的点也锅了几个，牛牛牛！

收到了高三放六天假的孬消息，然而我们只有不到 30h 的长 假，友好学校不够友好，下次记得把我们 OIer 带上。

想玩炉石了。

完结撒花~

image

标签：cnt,return,int,targ,now,CSP,模拟,fo
From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18442032

相关文章

  • [37]（CSP 集训）CSP-S 模拟 7
    A.median你说得对，但是你知道怎么不排序求中位数吗inlineintmid(inta1,inta2,inta3,inta4,inta5){ intd=-inf,x=inf,cd=-inf,cx=inf; if(a1>d)cd=d,d=a1; elseif(a1>cd)cd=a1; if(a1<x)cx=x,x=a1; elseif(a1<cx)cx=a1; if(a2>d)cd=d,d=a2; elseif(a2>......
  • 20240930模拟赛
    T1连珠风暴（necklace.pas/c/cpp）问题描述：给定M种颜色的珠子，每种颜色珠子的个数均不限，将这些珠子做成长度为N的项链。问能做成多少种不重复的项链.并且两条项链相同，当且仅当两条项链通过旋转或是翻转后能重合在一起，且对应珠子的颜色相同。样例输入：25样例输出：8下图是......
  • 南沙C++信奥赛陈老师解一本通题 2005：【20CSPJ普及组】直播获奖
    ​ 【题目描述】NOI2130即将举行。为了增加观赏性，CCF决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 w%w%，即当前排名前 w%w% 的选手的最低成绩就是即时的分数线。更具体地，若当前已评出了 pp 个选手的成绩，则当前计划获奖人数为 max(1,⌊p∗w%......
  • 如何选择合适的量化交易策略，回测与模拟交易的实战演练
    炒股自动化：申请官方API接口，散户也可以python炒股自动化（0），申请券商API接口python炒股自动化（1），量化交易接口区别Python炒股自动化（2）：获取股票实时数据和历史数据Python炒股自动化（3）：分析取回的实时数据和历史数据Python炒股自动化（4）：通过接口向交易所发送订单Python炒股自动化（5）：......
  • 开源免费Switch模拟器 Ryujinx v1.1.1400 中文免费版
    下载地址:https://pan.quark.cn/s/590ac8551aa7介绍Ryujinx是一款免费、开源的NintendoSwitch模拟器，它可以在电脑上模拟NintendoSwitch游戏机的运行环境，让玩家们能够在PC上畅玩Switch游戏。Ryujinx支持大部分NintendoSwitch游戏，包括TheLegendofZelda:Breath......
  • NZOJ 模拟赛3
    T1地理geo奶牛们刚学习完地理课，知道地球是个球。他们非常震惊，满脑子都是球形。他们试图把地球表面看成一个NxN(1<=N<=100)的方格，但是顶端连接着底部、左边连接到右边。格子用坐标表示，左下角坐标为(1,1)。例如：N=5时，牛从(1,3)位置向下走会到(5,3)；从(2,5)向右走会到(2,1)位......
  • 【题解】【模拟，字符串】—— [NOIP2011 普及组] 统计单词数
    【题解】【字符串】——[NOIP2011普及组]统计单词数[NOIP2011普及组]统计单词数题目描述输入格式输出格式输入输出样例输入#1输出#1输入#2输出#2提示1.思路解析2.AC代码[NOIP2011普及组]统计单词数通往洛谷的传送门题目描述一般的文本编辑器都有查找......
  • Luogu P5663 CSP-J2019 加工零件 题解 [ 绿 ] [ 同余最短路 ]
    加工零件：非常好的一道图论题。CCF普及组的题目大概也只有图论出的比较巧妙了。题意简述：给你一张无向图，\(q\)次询问，判断是否存在一条从\(a\)到\(1\)且长度为\(L\)的路径。看到\(L\)很大，我们立刻想到了要撇开\(L\)的限制思考问题。首先，对于一条路径，我们肯定能找到从......
  • [CSP-J2020] 直播获奖
    [CSP-J2020]直播获奖题目描述NOI2130即将举行。为了增加观赏性，CCF决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为w%w\%......
  • 95th 2024/8/20 模拟赛总结59
    本次爆炸场，也是习惯了赛时：冲T3正解，但是pushdown......OUT！真的得细心，复制第一句时忘记修改第二句了，离谱的是小样例全过了还有pushdown的位置，应注意，防止在叶子节点爆4N空间，比赛时一开始打出了假的T3算法，也是因为当时想了想直接就开打了，没多过脑子，应该多想几下，不然没RP又打假......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99