爱飞鱼的blog

...

Codeforces Round 937 (Div. 4) B题是输出规律图形题，对于这种题不能直接不思考就上去模拟，而应该思考一下数学规律，往往是模意义下的规律。 本题只需要模4以后的结果分为两类，分别讨论即可。对于模4可以利用位运算取出第二位的，这与模2同理。 123456789101112131415161718192021222324252627282930char s1='#';char s2='.';void solve(){ cin>>n; vector<vector<char>>ans(2*n+1,vector<char>(2*n+1,'0')); //vector<vector<bool>>v(2*n+1,vector<bool>(2*n+1,0)); for(int i=1;i<=2*n;i++){ for(int j=1;j<=2*n;j++){ int...

Codeforces Round 944 (Div. 4) 需要一些trick的一场 H: 2 -sat的板子，已经计入2-sat专题，此处不再详细描述。题目用矩阵包装和博弈包装，我们需要慢慢读题，分析样例，找到问题的关键点。 G：题意：给定一个数组，数组中任何两个数异或<4的数对可以交换位置 ，可以交换无限次，求能够形成的字典序最小的数组。 Sol：我们希望能够快速将能够交换的数对都聚集在一起，然后内部排个序，再按顺序送回每个位置上，时间复杂度O(nlogn)O(nlogn)O(nlogn)。所以我们只需要思考两个数怎么样才能异或起来<4，那么显然应该二进制位下分析，我们发现只需要高29位一样，剩的低三位随便怎么样我们不在乎，也就是说这样的数共有的特征是x>>2都是一样的，所以我们直接map<int,vector>存一下每个数，再对于每个vector排序.又由于不想存下标，所以我们只能倒着做回去利用vector的pop_back功能 12345678910111213141516171819void solve(){ ...

Codeforces Round 964 (Div. 4)](https://codeforces.com/contest/1999) B.如何优雅的暴力？ 题意：总共四张牌，每个人分两张牌，进行两轮游戏。每轮游戏双方各出一张牌，谁大谁win。在所有可能的抽卡结果和出牌顺序中，alice能win的数量。win定义为两场全胜 12345678910111213141516171819202122int f(int x, int y) { if (x > y) return 1; else if (x == y) return 0; else return -1;}void solve() { int a, b, c, d; cin >> a >> b >> c >> d; int ans = 0; if (f(a, c) + f(b, d) > 0) ans++; if (f(a, d)...

E题：题意：给定一个数组，你有两个操作，第一个操作是对任意前缀减去一个数，第二个操作是对任意后缀减去一个数。现在希望你用这两个操作将这两个数都变成0，要求操作次数最少，无解情况需要判断。 Sol:考虑两种操作，一种前缀操作，一种后缀操作都是对一整个区间操作，我们应该想到区间加常用的差分！我们记d为差分数组 操作1等价于d[1]−=k和d[i+1]+=kd[1]-=k和d[i+1]+=kd[1]−=k和d[i+1]+=k 操作2等价于d[n+1]+=k和d[n−i+1]−=kd[n+1]+=k和d[n-i+1]-=kd[n+1]+=k和d[n−i+1]−=k 题目要求我们用最少操作次数完成原数组恰好全部置0，等价于差分数组变0. 问题转化到这逐渐清晰。 考虑d[n+1]是不影响答案的，也就是操作二使用没有代价，对于差分数组中的所有正元素全部可以免费变0 对于为0的不用管 对于负元素，我们需要用操作1将其变0，考虑代价是次数加1以及d[1]减小，如果d[1]不够减，则原问题无解。 123456789101112131415void...

倍增大专题【每日一题】倍增专题11月26-12月3日题目_牛客网 (nowcoder.com) [AHOI2008] 紧急集合 / 聚会 - 洛谷 题意：给定一棵树，多次查询费马点（bushi 费马点的含义是：到三个点的距离之和最小 Solution:考虑画图发现树上三点两两求lca，必然至少两个相同，然后我们只需要让费马点为另一个点就可以了，因为这一段路程只需要一个点走就最好了。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152//考虑到让一个点走多的路程，两点走短路程//首先对多种情况画图，可以知道树上三点两两求lca，必然至少两个相同vector<int> e[N];int fa[N],son[N],dep[N],siz[N];int top[N];void dfs1(int u,int f){ //搞fa,dep,son fa[u]=f;siz[u]=1;dep[u]=dep[f]+1; for(int...

倍增大专题 [AHOI2008] 紧急集合 / 聚会 - 洛谷 题意：给定一棵树，多次查询费马点（bushi 费马点的含义是：到三个点的距离之和最小 Solution:考虑画图发现树上三点两两求lca，必然至少两个相同，然后我们只需要让费马点为另一个点就可以了，因为这一段路程只需要一个点走就最好了。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152//考虑到让一个点走多的路程，两点走短路程//首先对多种情况画图，可以知道树上三点两两求lca，必然至少两个相同vector<int> e[N];int fa[N],son[N],dep[N],siz[N];int top[N];void dfs1(int u,int f){ //搞fa,dep,son fa[u]=f;siz[u]=1;dep[u]=dep[f]+1; for(int v:e[u]){ if(v==f) continue; ...

二进制拆位 题意：给定一个数组，求所有子区间的区间异或和的sum Sol：先做异或前缀和，原问题则变成求数组中任意两个数的异或，然后全部相加起来的结果。我们考虑每个元素每位的贡献，只需要统计前面（偏序计数）有多少个数的本位与自己不同。 12345678910111213141516171819202122232425//这个题目显然应该作为模板题，似乎没有找到直白的在原数组上作拆位前缀和//本题先通过异或前缀和预处理，来将问题转化为两两之间的异或和，//如果不转化，就需要计算贡献次数void solve(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)a[i]^=a[i-1]; vector<int>c0(len+2,1),c1(len+2,0); int ans=0; for(int i=1;i<=n;i++){ int u=a[i]; for(int...

分治专题 分治初步 归并排序求逆序对 Sol：在归并排序过程中，本身就是分治思想，递归的对左区间排序，右区间同理。对于已经有序两段进行合并只需要O(n)O(n)O(n)的时间，递归共log2nlog_{2}{n}log2​n层，时间复杂度为O(nlog2n)O(nlog_{2}{n})O(nlog2​n) debug:1.对于没有到达边界的一段也需要放入临时数组，并且继续统计答案 2，先审核一遍代码，出现了没有调用函数，只打个括号的情况，没有报错，需要注意 1234567891011121314151617181920212223242526272829int solve(int l,int r){ if(l==r)return 0; int mid=(l+r)>>1; int res=solve(l,mid)+solve(mid+1,r); int pl=l,pr=mid+1; int...

贪心 环形均分纸牌问题 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;#define LL long longLL read(){ LL s=0,ne=1; char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1; for(;c>='0'&&c<='9';c=getchar())...