网页建站总结报告,多语言商城系统,网站建设源码安装教程,wordpress 安装插件慢Wannafly挑战赛26
题目连接
https://www.nowcoder.com/acm/contest/212#question
A. 御坂网络
枚举圆心所在的位置,O(n)O(n)O(n) 检查即可,总时间复杂度为O(n2)O(n^2)O(n2)
B. 冥土追魂
这题比较坑,我感觉题意叙述有问题,总之也是一道水题,题解略去.
C. 七彩线段
题解 …Wannafly挑战赛26
题目连接
https://www.nowcoder.com/acm/contest/212#question
A. 御坂网络
枚举圆心所在的位置,O(n)O(n)O(n) 检查即可,总时间复杂度为O(n2)O(n^2)O(n2)
B. 冥土追魂
这题比较坑,我感觉题意叙述有问题,总之也是一道水题,题解略去.
C. 七彩线段
题解
考虑到只有777种颜色,因此可以枚举最后选出线段的颜色组合,272^727种情况.
线段选法类似于会议安排,对于两个颜色相同的线段,我们必然优先选择右端点小的,因此我们第一步需要对线段以右端点从小到大进行排序.
预处理出数组pre[i]pre[i]pre[i],表示与线段iii不想交的右端点最大的线段是谁.
然后考虑状态压缩dpdpdp:
dp[i][S]dp[i][S]dp[i][S]表示考虑前iii个线段,已经选出来的线段颜色组合为SSS,所取得的最大长度.
转移方程dp[i][S∣(1lt;lt;color[i])]max(dp[pre[i]][S],dp[i−1][S(1lt;lt;color[i])])dp[i][S | (1 lt;lt; color[i])] max(dp[pre[i]][S],dp[i-1][S(1lt;lt;color[i])])dp[i][S∣(1color[i])]max(dp[pre[i]][S],dp[i−1][S(1color[i])])
代码
#include iostream
#include algorithm
#include cstring
#include vector
#define pr(x) std::cout #x : x std::endl
#define rep(i,a,b) for(int i a;i b;i)
#define clr(x) memset(x,0,sizeof(x))
#define setinf(x) memset(x,0x3f,sizeof(x))
struct seg{int l,r,c;bool operator(const seg sg)const{return r sg.r;}
};
std::vectorseg segs;
int n,m;
long long dp[100007][17];
int used[1 7];inline int cnt(int x) {int res 0;while (x) {res;x - x -x;}return res;
}
int pre[100007];
int main() {std::cin n m;for(int S 0;S (17);S) {if(cnt(S) m) used[S] 1;}for(int i 0;i n;i) {int l,r,c;std::cin l r c;c--;segs.push_back((seg){l,r,c});}std::sort(segs.begin(),segs.end());for(int i 0;i n;i) {int id (std::lower_bound(segs.begin(),segs.end(),(seg){0,segs[i].l,0}) - segs.begin());--id;pre[i] id;}long long ans -1;dp[0][1segs[0].c] segs[0].r - segs[0].l;for(int i 1;i n;i) {dp[i][1 segs[i].c] segs[i].r - segs[i].l;for(int S 0;S (17);S) {dp[i][S] std::max(dp[i][S],dp[i-1][S]);}if(pre[i] 0)for(int S 0;S (1 7);S) {int nS S|(1segs[i].c);if(dp[pre[i]][S])dp[i][nS] std::max(dp[i][nS],dp[pre[i]][S] segs[i].r - segs[i].l);}for(int S 0;S (1 7);S) {if(used[S] dp[i][S] ans)ans dp[i][S]; }}if(ans 0) ans -1;std::cout ans std::endl;
}D.禁书目录
题解
我们考虑每种颜色被在排列中被计数了多少次.
[0]结论: 一本书不会消失当且仅当所有aaa大于等于它的书都在它的右边.
因此假设有ttt本书其ai≥axa_i \ge a_xai≥ax,只考虑这ttt本书的排列,书xxx被看见的概率是1t\frac{1}{t}t1.
[1]假设有书axgt;aya_x gt; a_yaxay,且ai≥axa_i \ge a_xai≥ax的有txt_xtx本书,ai≥aya_i \ge a_yai≥ay的有tyt_yty本书,显然txlt;tyt_x \lt t_ytxty,我们希望求出xxx和yyy都没有出现的概率:
txt_xtx本书的相互排列中,书xxx必然不能出现在第一个位置,这样概率是tx−1tx\frac{t_x-1}{t_x}txtx−1.然后tyt_yty本书中yyy也不能出现在第一个位置,txt_xtx的排列对书yyy的选择没有影响,因此概率是ty−1ty\frac{t_y-1}{t_y}tyty−1,乘起来就是ty−1ty∗tx−1tx\frac{t_y-1}{t_y}*\frac{t_x-1}{t_x}tyty−1∗txtx−1.
[2]假设有书axaya_x a_yaxay,且ai≥axa_i \ge a_xai≥ax的书有ttt本,我们希望求出书xxx和yyy都没有出现的概率.先不考虑axa_xax,那么aya_yay不出现的概率是t−2t−1\frac{t-2}{t-1}t−1t−2,再考虑axa_xax不出现的概率是t−1t\frac{t-1}{t}tt−1,乘起来就是t−2t\frac{t-2}{t}tt−2,可以猜测有kkk本书aaa相同时,且ai≥aa_i \ge aai≥a的书有ttt本,那么这kkk本书都没出现的概率是t−kt\frac{t-k}{t}tt−k ps:我们为什么要求[2]呢,为什么axaya_x a_yaxay时候,求两者都不出现的概率时候不能直接使用[0]结论呢? 这是因为 当对axa_xax使用结论[0]时候,默认aya_yay在axa_xax右侧,而再对aya_yay使用结论[0]时候,默认axa_xax在aya_yay右侧,这样就出现了矛盾,因此,当两者aaa相等时,就不能直接用结论000了,而需要扩展一下. 结合[1][2]两个结论,我们枚举每一种颜色,计数这些颜色的书每一本都没有被看到的概率. 然后最后用111减去这个概率再乘以n!n!n!即是这部分颜色的贡献.
举个例子,当颜色为ccc的书为 a1lt;a3a5lt;a6lt;a7a_1 lt; a_3 a_5 lt; a_6 lt; a _ 7a1a3a5a6a7 时候是,对答案的贡献就是
n!∗(1−t1−1t1∗t3−2t3∗t6−1t6∗t7−1t7)n! * (1-\frac{t_1-1}{t_1}*\frac{t_3-2}{t_3}*\frac{t_6-1} {t_6}*\frac{t_7-1}{t_7})n!∗(1−t1t1−1∗t3t3−2∗t6t6−1∗t7t7−1)
其中tit_iti表示不小于aia_iai的书的本数.
代码
#include iostream
#include algorithm
#include map#define pr(x) std::cout #x : x std::endlconst int N 1000007;typedef long long ll;
typedef std::pairint,int pii;
const ll P 998244353;
std::mapint,ll mp;
ll mod_pow(ll x,ll n) {ll res 1;while(n) {if(n 1) res res * x % P;x x * x % P;n 1;}return res;
}
int n;
pii ps[N];
int main() {std::ios::sync_with_stdio(false);std::cin n;for(int i 1;i n;i) {int a,b;std::cin a b;ps[i-1] (pii){a,b};}std::sort(ps,psn);ll ans 0;ll nn 1;for(int i 1;i n;i) nn nn * i % P;int last 0;for(int i 0;i n ;i) {int pos i;while(pos n-1 ps[pos] ps[pos1])pos;if(mp.count(ps[pos].second) 0) mp[ps[pos].second] 1;if(ps[i].first ! ps[last].first) last i;ll big n - last;mp[ps[pos].second] mp[ps[pos].second] * (big - (pos - i 1)) % P* mod_pow(big,P-2) % P;i pos;}for(auto p : mp) {ans (ans (nn * (1 P - p.second) % P)) % P;}std::cout ans std::endl;
}
E.蚂蚁开会
待解决
F.msc的棋盘
题解
这其实是一道现寻找充要条件,然后使用dpdpdp计数的题.
如果给出a数组a数组a数组(行数组),和b数组b数组b数组(列数组),要进行判定,那么我们想到了用网络流进行判定,如果满流的话,就表示判定成功.
如n4,m2,b[1]1,b[2]3n 4,m 2,b[1] 1,b[2] 3n4,m2,b[1]1,b[2]3时候, 左边一排点有444个,右边一排点有222个,且两排点之间两两有边容量为111.源点向第一排点连边容量为a[i]a[i]a[i],第二排点向汇点连边,容量为b[i]b[i]b[i].
设sum∑b[i]sum \sum{b[i]}sum∑b[i]
根据最大流最小割定理,也就是说图的最小割必然要sum sumsum
考虑一个割选取了左边xxx个点,右边yyy个点,那么必然会选择左边a[i]a[i]a[i]最小的前xxx个点,同理右边会选择b[i]b[i]b[i]最小的前yyy个点.同样在剩下的没有选择的边中中间容量为111的边都要被切掉.
用sa,sbsa,sbsa,sb表示a,ba,ba,b排好序的前缀和.
割(x,y)sa[x]sb[y](n−x)(m−y)≥sum割(x,y) sa[x] sb[y] (n-x)(m-y) \ge sum割(x,y)sa[x]sb[y](n−x)(m−y)≥sum
且由于最大流≤sum\le sum≤sum,所以保证了有割sum割sum割sum.
因此我们就得到了一个充要条件.
那就是所有的割割割必然要≥sum\ge sum≥sum,求方案数.
相当于要把sumsumsum个棋子,分给每一行,使得割割割满足≥sum\ge sum≥sum,的方案数.直觉告诉我们要用dpdpdp来做.
定义dp[i][j][k]dp[i][j][k]dp[i][j][k]表示考虑a[i]a[i]a[i]前iii小的行,且最大行的a[i]≤ja[i] \le ja[i]≤j,且sa[i]ksa[i] ksa[i]k的方案数.
转移方程:
dp[it][j1][kt(j1)]dp[i][j][k]Cn−it,且0≤t≤n−idp[it][j1][kt(j1)] dp[i][j][k]C_{n-i}^{t},且0 \le t \le n-idp[it][j1][kt(j1)]dp[i][j][k]Cn−it,且0≤t≤n−i
观察dpdpdp方程,只有第二维严格递增,因此转移的时候我们先枚举第二维,然后再枚举第一维和第三维,这样保证了dpdpdp的无后效性.
代码
#include cstdio
#include iostream
#include algorithm#define pr(x) std::cout #x : x std::endl
typedef long long ll;
const ll P 1000000007;
const int N 51;
int n,m;
ll dp[N][N][N*N];
// dp[i][j][k] 表示前i小的行都已经考虑完,第i小的行有j个棋子,且前i行总棋子数量为k的可能的方案数.int sa[N],sb[N];
//sa[i]表示前i小的行棋子总数的最小限度
ll C[N][N];
void init() {C[0][0] 1;for(int i 1;i N;i) {C[i][0] 1;for(int j 1;j i;j) {C[i][j] (C[i-1][j-1] C[i-1][j]) % P;}}
}
ll fC(int n,int m) {if(m n || m 0) return 0;return C[n][m];
}
void add(ll x,ll y) {x x y;if(x P) x - P;
}int main() {init();std::cin n m;for(int i 1;i m;i) std::cin sb[i];std::sort(sb1,sb1m);for(int i 1;i m;i)sb[i] sb[i-1];for(int i 1;i n;i) {int mi 2500;for(int j 1;j m;j) {mi std::min(mi,sb[j] (n-i)*(m-j));}sa[i] sb[m] - mi;}int lim sb[m];for(int i 0;i n 0 sa[i];i) {dp[i][0][0] fC(n,i);}for(int j 0;j m;j) {for(int i 0;i n;i) {for(int k 0;k lim;k) {if(dp[i][j][k] 0) continue;for(int t 0;it n k t*(j1) lim k t*(j1) sa[it];t) {add(dp[it][j1][kt*(j1)],dp[i][j][k]*fC(n-i,t)%P);}}}}std::cout dp[n][m][lim] std::endl;
}
