Arn01d's planet

例 有一个 $n$ 个数的序列只由0，1组成，$m$ 个条件，每个条件告诉区间 $[l,r]$ 有奇数个1还是偶数个1，判断是否会出现矛盾。 每个条件可转化为 $sum[r]-sum[l-1]$ 是奇数还是偶数，即 $sum[l-1]$ 与 $sum[r]$ 的奇偶性是否相同。 边带权 边权 $d[x]$ 为0表示与父亲奇偶性相同，为1表示奇偶性不同，多次异或可得到 $x$ 与根的关系。 在父亲合并时，要注意父亲到新父亲的d怎么计算，因 $d[x]\ xor\ d[y]\ xor\ d[p]=ans$ ，故 $d[p]=ans\ xor\ d[x]\ xor\ d[y]$ 。 1234567int getfa(int x){ if(x==fa[x])return x; int rt=getfa(x); d[x]^=d[fa[x]]; return fa[x]=rt;} 拓展域 把每个节点拆成两个节点 $x_{odd}$ 与 $x_{even}$ ，若 $sum[x]$ 与 $sum[y]$ 奇偶性相同，那么分别合并 $y_{odd},x_{odd}$ 与$y_{e ...

在dp阶段增长过程中，当决策范围每次只扩大、不缩小时，那就可以仅用一个变量维护最值。 在复杂情况下，可以用到数据结构进行维护决策的候选集合。 例1： 用 $n$ 张贴纸覆盖一段长度为 $m$ 的丝带，每张丝带可以覆盖 $[L_i,R_i]$ ，价格为 $c_i$ ，求最小花费。 可以得到转移方程： $$ dp[r_i]=\underset {l_i\leq x\leq r_i}{min}dp[x]+c_i $$ $dp[x]$ 表示覆盖 $[1,x]$ 的最小花费。注意到此题本质即为求 $l_i\leq x\leq r_i$ 的最小值 $dp[x]$ ，那么可以用线段树维护最小值，每次查询即可。 例2： 给定长度为 $n$ 的数组，求有多少个严格递增子序列长度为 $m$ 。 可以得到转移方程： $$ dp[i,j]=\sum_{k<j&&a_k<a_j}dp[i-1,k] $$ $dp[i,j]$ 表示以 $a_j$ 结尾的长度为 $i$ 的子序列。普通dp需要三重循环，但是可以优化： 设 $val(x)$ 表示 $x$ 离散化之后的值，对每一个 $i$ ...

对于一系列约束条件进行转化建图，最终转化为最短路的模型。 如给定以下条件： $$ x_2-x_1\leq c_1 $$ $$ x_3-x_2\leq c_2 $$ $$ … $$ $$ x_n-x_{n-1}\leq c_{n-1} $$ 求 $max(x_n-x_1)$ 。即 $x_n-x_1\leq c$ ，求 $c$ 的最小值。注意到约束关系 $x_i-x_j\leq c$ 类似于最短路的关系 $dis[v]\leq dis[u]+w(u,v)$ ，对比可以得到：建立边 $add(j,i,c)$ ，然后跑spfa最短路（有负权边），得到的值即为要求的最大值。若有负环，那么无解。 若得到的关系为 $x_i-x_j\geq c$ ，那么可以转化为 $x_j\leq x_i-c$ ，建边 $add(i,j,-c)$ 。 为了判断连通性，可以建立超级源点，从源点向所有点建立 $add(0,i,0)$ ，并且跑一遍spfa(0)。 例：Layout G 123456789101112131415161718192021222324252627282930313233343536373839 ...

1. Junk Mail 题意：共对n个元素进行m次操作，操作共有两种，$M\ a\ b$ 为定义 $a$ 与 $b$ 为同一类元素，$S\ a$ 定义为将 $a$ 节点与其他节点分离。输出共有几类元素。 操作1很好处理，关键在于操作2，考虑到在并查集中不好操作，于是想到如下方法：将删除的元素映射为一个新的元素 $mp[x]$，并且后续所有涉及该元素的操作都用 $mp[x]$ 进行操作。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include<bits/stdc++.h>using namespace std;int n,m,lst;int fa[2000005];int mp[100005];int getfa(int x){ return fa[x] = fa[x]==x?x:getfa(fa[x]);}void merge(int x,int ...

比赛地址：Dashboard - Codeforces Round 955 (Div. 2, with prizes from NEAR!) - Codeforces 一个月没做了，期末周太忙了呜呜呜 D太遗憾了，结束7分钟后就出代码了，后来一测一发过，，前中段太唐了 A 题意：给出两个比分，一段时间后又给出一个比分，问这期间两队有没有可能出现平局的局面。 比较一下大小就行，水题。 1234567891011121314151617181920212223#include<bits/stdc++.h>using namespace std;int main(){ int t; cin>>t; while(t--) { int a,b,c,d; cin>>a>>b>>c>>d; if(a<b) { if(c<d)cout<<"YES\n"; ...

比赛地址：Dashboard - 2024 Xian Jiaotong University Programming Contest - Codeforces 记录下一个人vp整场比赛。 西交校赛蒸不错。 A、B、C、F 签到 D 题意：给出 $n$ 个点与 $m$ 个形如 $i,j$ 的限制条件，表示 $i$ 是 $j$ 的直接父亲。限构造一棵树，对于每个条件，若满足分数+1，若不满足分数-1，若两者互不支配那么分数不变。最终要使分数非负。 考虑构造“菊花树”，即设 $i$ 为根节点，则其有 $n-1$ 个儿子。那么应该满足在所有的 $m$ 个关系 $i,j$ 中，根节点出现在 $i$ 的次数应大于等于出现在 $j$ 次数，这样可以保证分数非负。 简单分析知一定存在一个点满足。 123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;int t[100005];int main(){ int n,m; cin> ...

比赛地址：Dashboard - Codeforces Round 945 (Div. 2) - Codeforces A 题意：三个人下棋，两两下棋，胜者2分负者0分，平局两人各得1分。现在告诉三人最终得分 $p_1\leq p_2\leq p_3$，求最多下了多少局。 首先 $p_1+p_2+p_3$ 要是一个偶数。 若 $p_3\geq p_1+p_2$ ，答案是 $p_1+p_2$ ，即前尽量多的平局。 否则，答案为 $p_3+(p_1+p_2-p_3)/2$ ，也是尽量多平局。 1234567891011121314151617181920212223#include<bits/stdc++.h>using namespace std;int main(){ int t; cin>>t; while(t--) { int a,b,c; cin>>a>>b>>c; if((a+b+c)%2==1) { ...

​ 利用 $vivado$ 定制同步/异步 RAM 核并观察不同的行为特征。 1. 观察同步RAM行为状态 ​ 定制的IP核如下： ​ 可见RAM有四个读入口和一个输出口，分别是： $addr$ ：地址 $clk$：时钟信号 $din$：写入数据 $dout$：读出数据 $we$：写使能信号 ​ 写入 $tb$ 文件后得到的波形如下： ​ 可以看到，在时钟的上升沿 RAM 读出数据；当写使能有效时，只在时钟上升沿**读出地址 $addr$ 的数据。 2. 观察异步RAM行为状态 定制的IP核如下： ​ 可见RAM有四个读入口和一个输出口，分别是： $a$ ：地址 $clk$：时钟信号 $d$：写入数据 $spo$：读出数据 $we$：写使能信号 ​ 写入 $tb$ 文件后得到的波形如下： ​ 可以看到，在时钟的上升沿 RAM 读出数据；当写使能有效时，立刻读出现在的地址 $addr$ 的数据。

1. 注意事项 代码中禁止使用 initial。 代码中禁止使用 casex，casez。 代码中禁止用 “#” 表示延迟。 clock 只能出现在 always @(posedge clock)。 触发器要么全部同步复位要么全部异步复位。 模块的输入必须是 wire 类型。 例化的输出必须是 wire 类型。 2. 模块声明与实例化 123456789101112131415module test #( parameter A_width=8, parameter B_width=4, parameter C_width=2) ( input wire [A_width-1:0] a, input wire [B_width-1:0] b, input wire [C_width-1:0] c, output wire [3:0] y, output reg [B_width-1:0] z); ...endmodule 1234567891011121314151617wire [15:0] a;wire [7:0] b;w ...

比赛链接：The 2023 ICPC China Shaanxi Provincial Programming Contest - Dashboard - Contest - QOJ.ac A 题意：给定一个包含加减括号的式子，涉及到的数字都是一位数。在式子中最多出现两个问号，现需要在问号填入数字，使得式子的值最大。 直接枚举“0 0”，“0 9”，“9 0”，“9 9”即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132#include<bits/st ...