牛客聯系賽53 A-E
題目鏈接：Link
A 超越學姐愛字串
題意： 長度為N的字串，只能有C，Y字符，且字串中不能連續出現 C，
思路： 其實就是DP，\(Dp[i][c]\) 表示長度為 \(i\) , 以 \(C\) 結尾的字串有多少種，那么整個狀態方程就有：
\[DP[i][c] = Dp[i-1][y]\\ Dp[i][y] = Dp[i-1][c] + Dp[i-1][y] \]會發現其實就是斐波那契數列而已，
Code：
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const ULL MOD = 1000000000 + 7;
const int maxn = 100000 + 13;
ULL Dp[maxn][2];
void Init() {
// 0 --> Y, 1 ---> C
memset(Dp, 0, sizeof(Dp));
Dp[0][0] = Dp[0][1] = 0;
Dp[1][0] = Dp[1][1] = 1;
for(int i = 2; i < maxn; ++i) {
Dp[i][0] = (Dp[i-1][0] + Dp[i-1][1]) % MOD;
Dp[i][1] = Dp[i-1][0];
}
}
int main() {
Init();
int n;
while(scanf("%d", &n) != EOF) {
ULL sum = (Dp[n][0] + Dp[n][1]) % MOD;
printf("%lld\n", sum);
}
return 0;
}
B 美味果凍
題意： $ \sum_{i=1}^{n}\sum_{j=1}^{i} {i * [\frac{i}{j}]^{j}}$ 簡單暴力的題意，，，
思路：這題就是找規律，，，把具體計算式寫出來，就發現規律了，具體如下：
\[\begin{align} &1 \\ &2^2 \ \ 2*1^2 \\ &3^2 \ \ 3*1^2 \ \ 3*1^3 \\ &4^2 \ \ 4*2^2 \ \ 4*1^3 \ \ 4*1^4\\ &\cdots \\ &n^2 \ \ n*[\frac{n}{2}]^2 \ \ n*[\frac{n}{3}]^3 \cdots n*1^n \end{align} \]第一列即為 \(\sum_i^n i^2\) ，第\(J\)列開始，就是以 \([\frac{n}{j}]\) 分塊了，
Code:
int main() {
false_stdio;
cin >> n;
for (ll j = 1; j <= n; j++) {
num[j] = j;
ans = (ans + j * j % mod) % mod;
}
for (ll j = 2; j <= n; j++) {
cnt = n / j;
ll L = j;
for (int i = 1; i < cnt; i++) {
tot = (L * j + (j * (j - 1) >>1)) % mod;
num[i] = num[i] * i % mod;
ans = ans + tot * num[i] % mod;
L += j;
}
num[cnt] = num[cnt] * cnt % mod;
tot = (n - cnt * j + 1) % mod;
ans =ans+ (L * tot % mod + (tot * (tot - 1)>>1)) % mod * num[cnt] % mod;
}
ans = (ans + mod) % mod;
cout << ans << endl;
return 0;
}
C 富豪凱匹配串
題意：0-1 字串匹配， '_' 代表通配符，輸出有多少是成功匹配的，
思路：因為是 0-1 字串，所以是可以使用 bitset 來做這題的，按與操作來匹配相應位是否相等即可，
Code：
int cnt = 0;
bitset<1005> p;
bitset<1005> q;
cin >> str;
for(int j = 0; j < m; ++j) {
char c = str[j];
if(c == '0') {
q[j] = 0; p[j] = 1;
} else if(c == '1') {
p[j] = q[j] = 1;
} else if(c == '_') {
p[j] = q[j] = 0;
}
}
for(int i = 0; i < n; ++i) {
if((p&Str[i]) == q) cnt ++;
}
cout << cnt << endl;
D 德育分博弈政治課
題意：給你 \(N\) 個骰子， 每個骰子的面是給定的 1-9 中的 6個數字， 然后 \(Q\) 次詢問，每次詢問是一個長串字串 \(str\) ，只含有 1 - 9 字符，問你的 \(N\) 個骰子， 骰子朝上的面記錄為 \(c\) ， 問可不可以用你的 \(N\) 個骰子選 \(L\) 個， 排列，使得 \(c_1c_2 \cdots c_l = str\) ，
思路：主要是總共只有 9 個字符，也就是說所有的狀態只有 $2^9 $ 種狀態，，， 可以狀態壓縮 + 暴力搜索狀態，
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1024;
int cnt[maxn];
int num[maxn];
// 離散化狀態， 方便計數， 暴力搜索狀態
int main() {
memset(cnt, 0, sizeof(cnt));
memset(num, 0, sizeof(num));
int n, Q;
string str;
cin >> n >> Q;
//處理狀態
for(int i = 0; i < n; ++i) {
cin >> str;
int len = str.length();
int status = 0;
for(int j = 0; j < 6; ++j) {
status |= 1<<(str[j]-'1');
}
cnt[status]++;
}
//統計 只要串里面有一個相同的，就可以納入狀態 2^9
for(int i = 0; i < 512; ++i) {
for(int j = 0; j < 512; ++j) {
if(i&j) num[i] += cnt[j];
}
}
for(int q = 0; q < Q; ++q) {
cin >> str;
int len = str.length();
bool jug = true;
int cnums[10] = {};
//memset(cnums, 0, sizeof(cnums));
for(int i = 0; i < len; ++i) cnums[str[i]-'1']++;
for(int i = 0; i < 512 && jug; ++i) {
int needNums = 0;
for(int j = 0; j < 9; ++j) {
if((i>>j) & 1) {
needNums += cnums[j];
}
}
if(needNums > num[i]) jug = false;
}
//cout << jug << endl;
string res = (jug ? "dyf" : "zzk");
cout << res << endl;
}
return 0;
}
老瞎眼 pk 小鮮肉
題意： 給一個陣列 \(Num\) ，給 一組區間查詢 \([L_i, R_i]\) ， 使得有區間最短的 \([l_i, r_i]\)在 \(L_i < l_i < r_i < R_i\) 下，有\(Num[l_i] \oplus Num[l_{i+1}]\oplus \cdots \oplus Num[r_i] = 0\) ，
思路： 首先最容易想到的就是前綴和，但是，根據題目資料，又明顯會超時，區間，不難想到會要結合一下線段樹來做，問題是如何用線段樹來優化，
? 首先，不考慮區間，考慮全部陣列，如何得到最短 的區間，顯然就是順序處理前綴和，遇到相等的，記錄下來（Tips：\(a \oplus a = 0\)），對于這道題來說，可以先預處理，把每一對這樣相等的，距離最短的記錄下來，然后離線處理所有詢問 ， 用線段樹維護當前詢問，最大右端為 \(r_i\) 情況下，所能獲得的最區間值，
#include <bits/stdc++.h>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid+1, r, rt<<1|1
#define IOSPEED ios::sync_with_stdio(false); cin.tie(0);
const int maxn = 500000 + 13;
const int INF = 0x7ffffffa;
int minDis[maxn<<2];
int Nums[maxn], pre[maxn], pos[maxn<<2];
void PushUp(int rt) {
minDis[rt] = min(minDis[rt<<1],minDis[rt<<1|1]);
}
void Build(int l, int r, int rt) {
minDis[rt] = INF;
int mid = (l + r) >> 1;
Build(lson);
Build(rson);
}
void Update(int pos, int val, int l, int r, int rt) {
if(l == r) {
minDis[rt] = min(val, minDis[rt]);
return ;
}
int mid = (l + r) >> 1;
if(pos <= mid) Update(pos, val, lson);
else Update(pos, val, rson);
PushUp(rt);
}
int Query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return minDis[rt];
}
int mid = (l + r) >> 1;
int resMin = INF;
if(L <= mid) resMin = min(resMin, Query(L, R, lson));
if(R > mid) resMin = min(resMin, Query(L, R, rson));
return resMin;
}
struct QuesNode {
int l, r, id;
bool operator < (const QuesNode& a) {
return r < a.r;
}
};
QuesNode q[maxn];
int ans[maxn];
int n, Q;
int main() {
IOSPEED;
cin >> n >> Q;
for(int i = 1; i <= n; ++i) {
cin >> Nums[i];
}
fill(begin(minDis), end(minDis), INF);
fill(begin(pre), end(pre), -1);
fill(begin(ans), end(ans), INF);
fill(begin(pos), end(pos), -1);
int sum = 0;
pos[0] = 0;
// 第 i 個數的最短區間為 i - pre[i] + 1
for(int i = 1; i <= n; ++i) {
sum = sum ^ Nums[i];
if(pos[sum] != -1) {
pre[i] = pos[sum]+1;
} else pre[i] = -1;
pos[sum] = i;
}
for(int i = 0; i < Q; ++i) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q, q+Q);
int pos = 0;
for(int i = 1; i <= n; ++i) {
if(pre[i] != -1) Update(pre[i], i-pre[i]+1, 1, n, 1);
while(q[pos].r == i) {
ans[q[pos].id] = Query(q[pos].l, q[pos].r, 1, n, 1);
pos++;
}
}
for(int i = 0; i < Q; ++i) {
cout << (ans[i]==INF ? -1 : ans[i]) << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139971.html
標籤：其他