网站一定要备案才能设计,沉默是金歌词谐音对照,项目外包平台,百度seo公司整站优化牛客网暑期ACM多校训练营#xff08;第一场#xff09; A. Monotonic Matrix 考虑0和1的分界线#xff0c;1和2的分界线#xff0c;发现问题可以转化为两条不互相穿过的路径的方案数#xff08;可重叠#xff09;#xff0c;题解的做法就是把一条路径斜着平移#xff0… 牛客网暑期ACM多校训练营第一场 A. Monotonic Matrix 考虑0和1的分界线1和2的分界线发现问题可以转化为两条不互相穿过的路径的方案数可重叠题解的做法就是把一条路径斜着平移然后就转化为不可重叠了。现在考虑如何计算从(0,0)道(n,m)不相交不可重叠的方案数一条从(0,1)出发到达(n-1,m)一条从(1,0)出发到达(n,m-1)将他们乘起来的结果还包含相交的情况于是再减去从(0,1)到(n,m-1)与(1,0)到(n-1,m)的方案数。 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
typedef long long ll;
const int N 1e5 7;
const ll mod 1e9 7;
using namespace std;
ll n,m,CC[2005][2005];
ll C(int n,int m) {return CC[n][m];}
int main() {rep(i,0,2003) CC[i][i]CC[i][0]1;rep(i,2,2003)rep(j,1,i) CC[i][j] (CC[i-1][j]CC[i-1][j-1])%mod;while(scanf(%lld%lld,n,m)!EOF) {ll ans ((C(nm,m)*C(nm,m))%mod - (C(nm,m1)*C(nm,n1))%modmod)%mod;printf(%lld\n,ans);}return 0;
}B. Symmetric Matrix 关键在于把这个矩阵考虑成一个邻接矩阵然后发现一个每个点有两条边且无自环可以有重边。这张图实际上就是每个点都属于唯一的一个环环的大小大于等于2。求这种图的方案数。好像第一类斯特灵数还得递推搞一下。详见大佬的推导 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
const int N 1e5 7;
using namespace std;
ll dp[N],n,m;
int main() {dp[1] 0, dp[2] 1, dp[3] 1, dp[4] 6;while(scanf(%lld%lld,n,m)!EOF) {if(n4) {printf(%lld\n,dp[n]%m);}else {ll M;rep(i,5,n)M 1LL*(i-1LL)*(i-2LL)/2LL,M%m,dp[i] (((((i-1)*dp[i-1])%m ((i-1)*dp[i-2])%m)%m) - (M*dp[i-3])%m m)%m;printf(%lld\n,dp[n]);}}return 0;
}D. Two Graphs \(n!\) 枚举与 \(G1\) 同构的图在 \(G2\) 中找到相应的边如果 \(m1\) 条边都可以匹配到则将这种方案中用到的边压成一个64位二进制数放到set里去重。另一种思路是出现重算的情况就是这个同构的图与自身的图相同即使用这些点的映射形成的新图与原图一致这种自同构的情况要从答案中除去。 #include bits/stdc.h
typedef unsigned long long ll;
const ll seed 31;
const ll mod 1e9 7;
inline int read() {char c getchar();int x0, f1;while(c0||c9){if(c-)f -1;cgetchar();}while(c0c9){xx*10c-0;cgetchar();}return x*f;
}
using namespace std;
int n,m1,m2,g[11][11],PH[11];
pairint,int p[1111];
int main() {while(scanf(%d%d%d,n,m1,m2)!EOF) {setint s;s.clear();memset(g,0,sizeof(g));for(int i1;im1;i) {int uread(),vread();g[u][v] g[v][u] 1;}for(int i1;im2;i) {int uread(),vread();p[i] make_pair(u,v);}for(int i1;in;i) PH[i]i;do{ll hs0,cnt0;for(ll i1;im2;i){if(g[PH[p[i].first]][PH[p[i].second]]) {hs | ((ll)1(i-(ll)1));cnt;}}if(cnt m1)s.insert(hs);}while(next_permutation(PH1,PH1n));printf(%d\n,(int)s.size());}return 0;
}J. Different Integers 先写了分块莫队tle然后写了曼哈顿mst莫队tle然后分块乱狗tlet到终场。结束后加了个快读分块莫队ac..。还有其他一些做法其实把整个序列在后边复制一份不就变成了单个区间询问数字种类的模板题了。让快读成为习惯。。。为何泥萌常数辣么小 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
typedef long long ll;
const int N 1e5 7;
inline int read() {char c getchar();int x0, f1;while(c0||c9){if(c-)f -1;cgetchar();}while(c0c9){xx*10c-0;cgetchar();}return x*f;
}
using namespace std;
int n,q,a[N];
struct pp{int l,r,id,ans;}Q[N];
int B,belong[N];
void build() {B sqrt(n);for(int i1; in; i) belong[i] (i-1)/B 1;
}
bool cmp(pp a, pp b) {if(belong[a.l] belong[b.l]) return a.r b.r;return belong[a.l] belong[b.l];
}
int sum0,num[N];
void update(int p,int d) {if(num[a[p]]1d-1) --sum;else if(num[a[p]]0d1) sum;num[a[p]]d;
}
bool cmp1(pp a,pp b) {return a.id b.id;
}
int main() {while(scanf(%d%d,n,q)!EOF) {for(int i1;in;i)num[i]0;build();for(int i1;in;i)a[i]read();for(int i1;iq;i) {Q[i].lread(),Q[i].rread();Q[i].idi;}sort(Q1,Q1q,cmp);int l0, rn1;sum 0;for(int i1;iq;i) {while(rQ[i].r)update(r,-1),r;while(rQ[i].r)--r,update(r,1);while(lQ[i].l)l,update(l,1);while(lQ[i].l)update(l,-1),--l;Q[i].ans sum;}sort(Q1,Q1q,cmp1);for(int i1;iq;i)printf(%d\n,Q[i].ans);}return 0;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9339002.html
