首先因为是个环,我们得先随机分配一个确定起点,然后剩下的方案总数是(2*n-1)!.然后就是我们的容斥原理了,0个相邻的-1个相邻的+2个相邻的-3+4... 0个相邻的答案就是(2*n-1)! 1个相邻的答案是2*C(n,1)*(2*n-2)!.对于这个的解释就是你n对中选取1对,然后前后顺序考虑一下.其他的同理,我们可以得到i对相邻的方案数是: (2^i)*C(n,i)*(2*n-i)!.如此这个题就可以通过预处理O(N)解决了.代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; c...

树状数组一般都是计数问题,这个题目也不例外,我们可以发现题目讲的很复杂,但是换一种理解方式(或者画图可以知道),行列是可以单独考虑的,单独考虑行列,一行和一列一定是存在交点的,对于两个相同的行/列出现了,就等同于这里没有行/列了,我们只需要维护拿树状数组区间有多少行列就行了.代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; int sum[2][N];//维护矩阵中行列有多少. int dx[N],dy[N]; int lowbit(int x) ...

原来这题是每日一题......?这题可以用树状数组求逆序对解决,首先我们可以知道..我们把其中一维排序,另外一维按第一维的顺序插入就会产生一组答案.对于可计数的答案来说,我们考虑两种,第一种是我第一维大于它的第二维,我的第二维小于它的第二维,第三维未知但是算出来的答案重复次数只会是1,因为第三维可能是继续大于,那么只会和第二种重复,要么小于只会和第一种重复...好了,牛客的每日一题,假如我没做过,还是可以做一下的...毕竟有很多题解,对于萌新可真是太友好了. #include <bits/stdc++.h> using namespace std; typedef long lon...

老实说牛客的题真的挺不错的,但是题解太少了,萌新做着难受唉...............................................................................................................................哭了

https://ac.nowcoder.com/acm/problem/13332谢谢大佬

借一个入门题引入下线段树吧..其实我的树状数组区间修改区间查询还没更,也不太会...毕竟要死记推导也挺难的.线段树是一种分治结构,我觉得是这样的,同时也是一颗二叉搜索树.它有几个代码,其中包括建树,修改,查询.和树状数组类似,线段树的懒标记就是你不要用的时候先保留,要用的时候再用.就这些吧...好像说起来很简单...但是因为我写的太少了.然后导致我emmm..拿这个题说吧,合并字符串的价值,还是感谢好心的不知名的大佬...确实挺简单的.首先我们先预处理下A段,算下切A的每个位子和B一起的max_val.然后我们在用线段树维护区间最大值,什么最大值呢,就是在A段中的(l-r)切一刀的最大值,分治...

直接dfs即可...emmm好水,好了,学树状数组线段树去了...ggg #include <bits/stdc++.h> using namespace std; const int N=100; string s; int vis[N],ans; void dfs(int u,int op) { //cout<<s.size()<<endl; //cout<<u<<' '<<op<<endl; if(op==1) { if(vis[s[u]-'0']) return; vis[s[u]-'0']=1; if...

一个计数问题,下次看到数据就直接dp吧.有点分治思想在里面.就是一个点一个点的计数,一条链一条链的来,f[i][j]表示到了i这个点值为j的方案数...如此转移下就好了. #include <bits/stdc++.h> using namespace std; const int N=2e4+5,M=2e3+2e2; int f[N][M]; struct vv{ int to,val; }; vector<vv>v[N]; int ans=0; void dfs(int u,int fa) { for(int i=0;i<2019;i++) f[u][i]=0...

有些数据结构不管你是学什么的,你都得精通对吧,对内分工是不可靠的..尽量完全会吧..https://ac.nowcoder.com/acm/skill/detail/acm/1297 https://ac.nowcoder.com/acm/skill/detail/acm/1315 加油...做完他们.线段树是分治思想,树状数组是种简单的维护工具,他们对于dp学习都有作用的.

直接按题意模拟计数即可,拿个单调栈和树状数组维护下...题目不是求二元组的数量吗?i<j&&ai>=j&&aj>=i.这是一个二维问题对吧,我们一维一维的解决.首先对于ai>n的直接取n就好,因为n一定是满足条件的.然后我们令val和id,字面意思呐.我们都排序一下,对于原数组按val升序排序.当然在排序之前,我们需要存下它的值对吧,因为我们后面要枚举的.后面枚举的话也是一个一个处理的,我们考虑枚举i=1到n.然后对于每个i判断下ai这个位子合法的数量,我们很容易知道,假如aj<i当前,那么这个j就不可能作为贡献,且以后也不会成为贡...

希望两天后能打到ccpc的名额~

#include <bits/stdc++.h> using namespace std; const int N=1e5+5; const int inf=2e9; struct vv{ int l,r,id; }tree[N<<2]; int a[N]; void build(int l,int r,int p) { tree[p].l=l;tree[p].r=r; if(tree[p].l==tree[p].r) { tree[p].id=0; return; } int mid=(tree[p].l+tree[p].r)>>1; build(l,mi...

不会数据结构的人去理解真ri gou #include <bits/stdc++.h> using namespace std; const int N=1e6+5; int n,sum[N]; int lowbit(int x) { return x&(-x); } struct vv{ int l,r; }; vector<vv>W[N]; vector<int>L[N],R[N]; int ask(int pos) { int res=0; while(pos) { res+=sum[pos]; pos-=lowbit(pos); } retu...

一个简单的计数问题. #include <bits/stdc++.h> typedef long long ll; const ll N=5e3+5,M=30; const ll mod=1e9+7; ll s[N],c[N],f[N],g[N],st[M]; ll qp(ll a,ll b) { ll res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } bool cmp(ll x,ll y) { return x>y; } int main() { ll n...