阅读量:0
1001.循环位移
字符串
题目大意
给定两个字符串 A , B A,B A,B 。
定义 [ A ] [A] [A] 为字符串 A A A 的循环位移任意次可以得到的所有字符串的集合。
求 B B B 包含 [ A ] [A] [A] 中元素的个数。
解题思路
利用字符串Hash快速匹配。
将 [ A ] [A] [A] 中所有元素的Hash记录到一个set：计算 A + A A+A A+A 的Hash前缀和，以快速得到所有长度为 ∣ A ∣ |A| ∣A∣ 的子串的Hash值，并加入set中。
枚举 B B B 的所有长度为 ∣ A ∣ |A| ∣A∣ 的子串，计算Hash值，判断是否在set中，计数。
参考程序
void solve() { string a,b; cin >> a >> b; ll n=a.length(),m=b.length(); set<pll> st; strHash sa(a+a); FORLL(i,1,n) st.insert(sa.findz(i,i+n-1)); strHash sb(b); ll ans = 0 ; FORLL(i,1,m-n+1) if(st.count(sb.findz(i,i+n-1))) ans++; cout << ans << endl; } 1002.星星
背包DP
题目大意
小A要进行n次选择，每次可以选择一项：
- 不执行操作
- 付出 a i a_i ai点代价得到1颗星星
- 付出 b i b_i bi点代价得到2颗星星
- 付出 c i c_i ci点代价得到3颗星星
- 付出 d i d_i di点代价得到4颗星星
求恰好得到 k k k颗星星的最小代价。
解题思路
一眼顶针鉴定为背包DP的分组背包问题。
d p x dp_x dpx表示选x个物品的最低cost。
在第 i i i组时，从大到小遍历作出选择后有 j j j个星星。
遍历这一步的选择（ l l l 个星星），从 d p j − l dp_{j-l} dpj−l 更新到 d p j dp_j dpj ，这样更新保证了一次操作只生效一项。
参考程序
void solve() { ll n,k;cin >> n >> k; vector<array<ll,5>> cost(n,{0,0,0,0,0}); vector<ll> dp(k+1,INF); dp[0]=0; //选i个物品的最低cost FORLL(i,0,n-1) cin >> cost[i][1] >> cost[i][2] >> cost[i][3] >> cost[i][4]; FORLL(i,0,n-1){ //第i步 FORLL_rev(j,k,1){ //选择后的个数 FORLL(l,0,4){ //这一步选择l个 if(j-l>=0) chmin(dp[j],dp[j-l]+cost[i][l]); } } } cout << dp[k] << endl; } 1008.位运算
题目大意
给定整数 n , k n,k n,k，求满足 ( ( a ⊗ b ) ⊕ c ) ⊖ d = n ((a\otimes b)\oplus c)\ominus d=n ((a⊗b)⊕c)⊖d=n 的四元组 ( a , b , c , d ) ， 0 ≤ a , b , c , d < 2 k (a,b,c,d)，0\le a,b,c,d\lt 2^k (a,b,c,d)，0≤a,b,c,d<2k 的个数。
其中， ⊗ \otimes ⊗ 表示按位与， ⊕ \oplus ⊕ 表示按位异或， ⊖ \ominus ⊖ 表示按位或。
解题思路
转为二进制，按位考虑。
若 n n n 的某一位上是 0 0 0 ， d d d 在这一位上必须为 0 0 0 ， c c c 在这一位上由 a , b a,b a,b 决定（控制这一位为 0 0 0）， a , b a,b a,b 在这一位上任选，即 1 ∗ 1 ∗ 2 ∗ 2 = 4 1*1*2*2=4 1∗1∗2∗2=4 种可能。
若 n n n 的某一位上是 1 1 1 ：
- 若 d d d 在这一位上为 0 0 0 ，则 c c c 在这一位上由 a , b a,b a,b 决定（控制这一位为 1 1 1）， a , b a,b a,b 在这一位上任选，即 1 ∗ 1 ∗ 2 ∗ 2 = 4 1*1*2*2=4 1∗1∗2∗2=4 种可能。
- 若 d d d 在这一位上为 1 1 1 ，则 a , b , c a,b,c a,b,c 在这一位上任选，即 1 ∗ 2 ∗ 2 ∗ 2 = 8 1*2*2*2=8 1∗2∗2∗2=8 种可能。
综上， n n n 的一位上是 1 1 1 时有 12 12 12 种可能，是 0 0 0 时有 4 4 4 种可能。
答案为 4 k × 3 c n t 1 4^k\times 3^{cnt1} 4k×3cnt1 。
参考程序
void solve() { ll n,k; cin >> n >> k; ll cnt1=0; while(n){ if(n%2) cnt1++; n/=2; } cout << qcpow(2,k*2)*qcpow(3,cnt1) << endl; } 1012.并
题目大意
给定 n n n 个矩形，对 k = 1 → n k=1\to n k=1→n 分别求随机取 k k k 个矩形的面积并的期望。
解题思路
平面可以被矩形边界分割成若干个小区域，考虑每个区域对答案的贡献。
因为要求期望，被“相同数量矩形覆盖”的小区域 对答案的贡献是相同的，因此按照 覆盖矩形数量 将这些小区域分组，统计出恰好被 i i i 个矩形覆盖的区域的面积 S i S_i Si。
我的求法就是从左到右扫描，在每条竖线的位置，更新 i i i 个矩形覆盖的y轴长度 y v a l i yval_i yvali ，到下一条竖线再乘经过的x轴长度，得到这一部分的面积（类似于积分？），加入 S i S_i Si
然后考虑贡献的权重。
从 n n n 个矩形中随机选取 k k k 个，对于被 i i i 个矩形覆盖的区域，只要选取的 k k k 个矩形中，存在这 i i i 个矩形之一，那么这个面积就会被计入。
在上述条件下的贡献权重是 v a l k , i = C n k − C n − i k C n k val_{k,i}=\dfrac{C_{n}^{k}-C_{n-i}^{k}}{C_{n}^{k}} valk,i=CnkCnk−Cn−ik ，即从 n n n 个矩形中选取 k k k 个方案数，减去从 n − i n-i n−i 个矩形中选取 k k k 个方案数。
最后答案 a n s k ans_k ansk是 ∑ i = 1 n v a l k , i × S i \sum\limits_{i=1}^{n}val_{k,i}\times S_i i=1∑nvalk,i×Si 。
参考程序
void prepare(){ Prepare_Combination(5005); MOD = 998244353; } ll getval(ll n,ll i,ll j){ ll ret=C[n][i],sb; if(i>n-j) sb=0; else sb = C[n-j][i]; return sub(ret,sb); } void solve() { ll n;cin >> n; ll xx1,xx2,yy1,yy2; vector<tuple<ll,ll,ll,ll>> xlines; vector<ll> ylines; // xline:(y,x1,x2,flag) # 横线 flag:0上边界1下边界 // yline:(x) # 竖线x坐标 FORLL(i,1,n) { cin >> xx1 >> yy1 >> xx2 >> yy2; xlines.emplace_back(yy1,xx1,xx2,0); xlines.emplace_back(yy2,xx1,xx2,1); ylines.emplace_back(xx1); ylines.emplace_back(xx2); } SORT(xlines); SORT(ylines); map<ll,ll> S,yval; ll prex=0; // S[i]:重叠i次部分的面积 for(auto xx:ylines) { ll difx = xx-prex; for(auto [pl,val]:yval) { // S[pl]+=difx*val; addto(S[pl],mul(difx,val)); } yval.clear(); ll cur = 0, prey = 0; for(auto [yy,xx1,xx2,flag]:xlines) { if(xx1<=xx&&xx<xx2) { yval[cur]+=yy-prey; if(flag==0) cur++; else cur--; prey=yy; } } prex = xx; } // for(auto x:S) cout << x.first << ' ' << x.second << endl; FORLL(i,1,n){ ll ans = 0; FORLL(j,1,n){ ll val = getval(n,i,j); ans = add(ans,mul(val,S[j])); } divto(ans,C[n][i]); cout << ans << endl; } } 