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

『模拟赛』CSP-S模拟9

时间:2024-10-06 17:44:19浏览次数:9  
标签:ch return int tot ya ans CSP 模拟

Rank

烂,知耻而后勇

image

A. 邻面合并

签。

注意到列数 \(m\le 8\),我们可以直接先搜出每一行可能的“分块”情况,然后转移时枚举上一行的所有状态和这一行的所有状态,根据拼接情况来更新答案,最终答案即为 \(n\) 行所有情况的最小值。

赛时开始打的错解,错解如果第一行总数计算错了就能过小样例(?),然后就改错了,后来打了正解,没改回来能过大样例,而且不是很会打这一题的暴力就没写拍,故挂 30pts。

由于状态那不太会表示,所以存状态用了 vector<vector<int> >,可能不是最优的。

点击查看代码
#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 = 100 + 5;
int n, m, ans = 1e9;
int d[N][N], zt[N], zc[N];
vector<vector<int> > v[N];
vector<int> f[N];
bool yz[N];
namespace Wisadel
{
    void Wdfs(int hang, int x)
    {
        if(x > m)
        {
            vector<int> cz;
            fo(i, 1, m)
            {
                cz.push_back(zc[i]);
            }
            v[hang].push_back(cz);
            return;
        }
        if(d[hang][x] == 0) zc[x] = 0, Wdfs(hang, x + 1);
        else
        {
            if(d[hang][x - 1] == 1) zc[x] = zc[x - 1], Wdfs(hang, x + 1);
            zc[x] = x, Wdfs(hang, x + 1);
        }
    }
    short main()
    {
        freopen("merging.in", "r", stdin) , freopen("merging.out", "w", stdout);
        n = qr, m = qr;
        fo(i, 1, n) fo(j, 1, m) d[i][j] = qr, zt[i] |= d[i][j] * (1 << (j - 1));
        fo(i, 1, n) Wdfs(i, 1), f[i].resize(v[i].size());
        fo(i, 0, v[1].size() - 1)
        {
            f[1][i] = 0;
            int num = 0;
            fo(j, 0, m - 1)
            {
                if(j == 0 &&v[1][i][j] != 0) num++;
                else if(v[1][i][j] != v[1][i][j - 1] && v[1][i][j] != 0) num++;
            }
            f[1][i] = num;
        }
        fo(i, 2, n)
        {
            fo(k, 0, v[i].size() - 1)
            {
                f[i][k] = 1e9;
                fo(j, 0, v[i - 1].size() - 1)
                {
                    int num = 0, las = v[i][k][0], st = 0; bool lian = 0;
                    fo(z, 1, m - 1)
                    {
                        if(v[i][k][z] != las && las != 0)
                            if(v[i][k][z - 1] != v[i - 1][j][z - 1] || v[i][k][st] != v[i - 1][j][st] || v[i - 1][j][z] == las)
                                num++;
                        if(las != v[i][k][z]) las = v[i][k][z], st = z;
                        if(v[i][k][z] == 0) continue;
                    }
                    if(v[i][k][m - 1] != 0 && (v[i][k][m - 1] != v[i - 1][j][m - 1] || v[i][k][st] != v[i - 1][j][st])) num++;
                    f[i][k] = min(f[i][k], num + f[i - 1][j]);
                }
            }
        }
        fo(i, 0, v[n].size() - 1) ans = min(ans, f[n][i]);
        printf("%d\n", ans);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

B. 光线追踪

由于看到区间(面)修改和单点(线)查询就一下想到了线段树,赛时思路是先离线将询问按斜率升序映射到一个序列上,由于边界等种种问题导致这样很不好实现,由于没开 long long 挂掉可以拿到的 30pts。

用线段树维护关键在想到转换成角度来做。角度范围只有 \(\left[0,\frac{\pi}{2}\right]\),每次加面相当于是对一定角度做区间推平,查询一个向量相当于是对一个角度做单点查询,理解这种转化后 这题就好说了 还是很恶心。

想到映射就该想到离散化的。考虑每次覆盖一个面对答案有影响的只有下面和左面的两条边,因此有用的三个向量即为原点指向左上、左下、右下三点的向量。我们将它们同询问的向量全部离散化,最多只会有 \(3n\) 个不同的向量,这样它们映射后的下标就形成了一个序列,我们就可以愉快地在上面进行区间修改单点查询的操作了。

不过想必 T2 不会这么容易,还有很多细节要处理。首先是修改后答案是否更改,由小样例可知存在一种这样的情况:

image

可以看到,2 虽然是后加的,但是红线范围内的答案仍是 1。

我们考虑针对横纵坐标分别开线段树维护其范围内相反坐标的最小值及其序号。简单说,就是对于横坐标的线段树,维护其范围内最小的纵坐标及其序号(答案),纵坐标相同取序号大的,对于纵坐标同理。

每次新增障碍即横坐标线段树增加长方形下边,纵坐标线段树增加长方形左边;每次询问即查询横坐标和纵坐标的线段树并取优。如何取优?首先对于横纵其中一种答案为 0 的,去另一种即可;否则因为斜率相同,我们取横坐标小的;若都相同则取序号大的即可。

实现起来细节还是挺多的,注意横坐标线段树维护的最小纵坐标和纵坐标线段树维护的最小横坐标需要开 long long,因为这个调了快一个小时。注意比较斜率用交叉相乘法,以及线段树大小开够,其它地方正常 'int' 和 'double' 就能过。

点击查看代码
#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, tot;
double k[N << 2];
struct rmm{int op, xa, ya, xb, yb;} q[N];
struct Ans{int ans; ll minn;};
struct Wtree
{
    Ans t[N << 2];
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    #define mid ((l + r) >> 1)
    void Wupd(int rt, int l, int r, int x, int y, int id, int minn)
    {
        if(x <= l && r <= y)
        {
            if(!t[rt].ans || (t[rt].minn >= minn))
                t[rt].ans = id, t[rt].minn = minn;
            return;
        }
        if(x <= mid) Wupd(ls, l, mid, x, y, id, minn);
        if(y > mid) Wupd(rs, mid + 1, r, x, y, id, minn);
    }
    Ans Wq(int rt, int l, int r, int x)
    {
        if(l == r) return t[rt];
        Ans res;
        if(x <= mid) res = Wq(ls, l, mid, x);
        else res = Wq(rs, mid + 1, r, x);
        if(!t[rt].ans) return res;
        if(!res.ans) return t[rt];
        if(t[rt].minn < res.minn) return t[rt];
        else if(t[rt].minn == res.minn && t[rt].ans > res.ans) return t[rt];
        return res;
    }
} h, s;
namespace Wisadel
{
    double Wget(int x, int y)
    {
        if(x == 0) return 1.0 * 1e18;
        return 1.0 * y / (1.0 * x);
    }
    int Wpk(Ans x, Ans y, int xx, int yy)
    {
        if(!x.ans && !y.ans) return 0;
        if(!x.ans) return y.ans;
        if(!y.ans) return x.ans;
        if(!xx)
        {
            if(q[x.ans].ya < q[y.ans].ya) return x.ans;
            return y.ans;
        }
        if(!yy)
        {
            if(q[x.ans].xa < q[y.ans].xa) return x.ans;
            return y.ans;
        }
        if(x.minn * xx == y.minn * yy)
        {
            if(x.ans > y.ans) return x.ans;
            return y.ans;
        }
        if(x.minn * xx < y.minn * yy) return x.ans;
        return y.ans;
    }
    short main()
    {
        freopen("raytracing.in", "r", stdin) , freopen("raytracing.out", "w", stdout);
        n = qr;
        fo(i, 1, n)
        {
            q[i].op = qr, q[i].xa = qr, q[i].ya = qr;
            if(q[i].op == 1)
            {
                q[i].xb = qr, q[i].yb = qr;
                k[++tot] = Wget(q[i].xa, q[i].ya);
                k[++tot] = Wget(q[i].xa, q[i].yb);
                k[++tot] = Wget(q[i].xb, q[i].ya);
            }
            else k[++tot] = Wget(q[i].xa, q[i].ya);
        }
        sort(k + 1, k + 1 + tot);
        tot = unique(k + 1, k + 1 + tot) - k - 1;
        fo(i, 1, n)
        {
            if(q[i].op == 1)
            {
                int zs = lower_bound(k + 1, k + 1 + tot, Wget(q[i].xa, q[i].yb)) - k,
                    zx = lower_bound(k + 1, k + 1 + tot, Wget(q[i].xa, q[i].ya)) - k,
                    yx = lower_bound(k + 1, k + 1 + tot, Wget(q[i].xb, q[i].ya)) - k;
                h.Wupd(1, 1, tot, yx, zx, i, q[i].ya);
                s.Wupd(1, 1, tot, zx, zs, i, q[i].xa);
            }
            else
            {
                int kk = lower_bound(k + 1, k + 1 + tot, Wget(q[i].xa, q[i].ya)) - k;
                Ans La = h.Wq(1, 1, tot, kk), Ca = s.Wq(1, 1, tot, kk);
                printf("%d\n", Wpk(La, Ca, q[i].xa, q[i].ya));
            }
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

C. 百鸽笼

学习题面,鸽鸽鸽。

据说是 NOI UNR 的原题。

D. 滑稽树下你和我

有点高级,不过数据很水啊,直接输出起点距离基本上全能过,得亏绑包了。

因为数组范围开小导致少拿了 15pts。

挂挂挂挂挂挂挂。

挂了 75pts,跟得的一样多。

虽然开场再次被 T1 硬控后果断选择看后面的题,结果发现甚至都不如 T1 可做,于是只得应干 2h T1,结果还因为唐错没 AC。

开场原题,梦回 T1 3100 高光时刻,然后就罚坐 20min 后换来了这套高质量模拟赛

最近挂分越来越多了,必须得重视起来了,虽然有可能是因为昨天 abc 一发罚时没吃导致的

abc 上青了,cf 打一题摆了回来改 T2。


完结撒花~

image

标签:ch,return,int,tot,ya,ans,CSP,模拟
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18449235

相关文章

  • 傻逼模拟赛搬的时候能不能看看题面改之后还是不是让人能看懂还有不发 checker 是有什
    如题。傻逼模拟赛搬的时候能不能看看题面改之后还是不是让人能看懂还有不发checker是有什么心事吗还在最后一道题放集训队互测什么意思什么叫有\(b_{k}\)种\(k\)类型的货币,同一种流通的货币不会超过二十种什么叫接下来\(n\)个数表示\(a_{1}\sima_{n-1}\)......
  • P7078 [CSP-S2020] 贪吃蛇 题解
    P7078[CSP-S2020]贪吃蛇这题好啊题目传送门看到题之后觉得有点像砍蚯蚓的那道题看看题目可以证明,若一条蛇在吃完之后不是最弱的那一条蛇,那么他一定会选择吃,证明如下设蛇长为\(a_{1,\dots,n}\)且依次递增,那么很明显的因为​......
  • 信息学奥赛复赛复习13-CSP-J2021-02插入排序-排序稳定性、插入排序、sort排序、结构体
    PDF文档公众号回复关键字:202410061P7910[CSP-J2021]插入排序[题目描述]插入排序是一种非常常见且简单的排序算法。小Z是一名大一的新生,今天H老师刚刚在上课的时候讲了插入排序算法。假设比较两个元素的时间为O(1),则插入排序可以以O(n^2)的时间复杂度完成长度为......
  • CSP2024-S1游记
    额额,由于对自己水平极度自信,所以没怎么练初赛,只做了两张真题,教练一直叫我做NFLS的模拟题,我一个都没做好吧膜拜巨佬ydy,真的勇诶,直接不做(他把卡涂错了,最后61pts)初赛随便考考都能过吧听说这次CCF不仅把J组分线推上90的高位还泄题了,怎么出的卷啊话说回来,这次又是主场作战,所以在前一......
  • 冲刺CSP联训模拟2
    冲刺CSP联训模拟2A.挤压考虑把一个数写成二进制,不妨记为$\sums_i\times2^i,s=0或1$,设其概率为$p_k$,则期望值:\[p_k\times(\sum_{i=0}^{29}s_i)^2=p_k\times\sum_{i=0}^{29}\sum_{j=0}^{29}s^i\timess^j\times2^{i+j}\]设$dp[i][j]$为异或后......
  • NOIP 模拟赛:2024-9-30
    为什么会有傻子每次计算都初始化线段树一次……st=SegmentTree(n)改成st.mdf(1,n+1,-1)就+=25pts了……T1T2类似上一场的trick,筛法求质数。对于每个质数求最长的段,使得段内\(1\)的个数\(\gelen/2\)。原始的想法是枚举两个\(1\)的位置\(p_x,p_y(x>y)\),若......
  • c语言模拟实现qsort
    要想模拟首先qsort函数首先我们应该知道这个函数的功能是什么接下来我为大家引入一个列子我们想要实现一组有序数的升序可以通过冒泡排序法思想是 两两相邻元素进行比较 代码如下 通过冒泡排序法 #define_CRT_SECURE_NO_WARNINGS#include<stdio.h>voidbubbl......
  • 冲刺CSP联训模拟2
    A.挤压拆位算贡献,一个数二进制表示平方为\(\sum_{i,j}s_i*s_j*2^{i+j}\),单独算每一项的贡献,枚举\(i,j\),只有当这两位都为1时结果才是1,所以我们要找异或后这两位都是1的方案数,这里需要\(dp\)用\(f_{i,j,k}\)表示前\(i\)个数异或出来的\(j,k\)两位是1/0的方案数,对于......
  • 10.5 模拟赛(NOIP十三连测 #11)
    2024--梦熊&太戈--NOIP十三连测#11【订正】-比赛-梦熊联盟(mna.wang)复盘赢麻了(?)老师说照着\(300\)分打。顺序开题。T1读懂题后模拟了一下样例,发现答案就是$n-$连通块???快速写完了代码发现大样例全过了。此时8:05。T2。一眼DP。但是\(n\le10^6\)所以放弃了。......
  • 信息学奥赛复赛复习12-CSP-J2021-01分糖果-模运算、余数、打擂台求最值、最大值、最小
    PDF文档公众号回复关键字:202410051P7909[CSP-J2021]分糖果[题目描述]红太阳幼儿园有n个小朋友,你是其中之一。保证n≥2有一天你在幼儿园的后花园里发现无穷多颗糖果,你打算拿一些糖果回去分给幼儿园的小朋友们由于你只是个平平无奇的幼儿园小朋友,所以你的体力有限,至......