oj: 牛客
A 九峰與簽到題
oj: 牛客
題解
簽到題
代碼
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define _for(i, a) for(int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(int i = (a), lennn = (b); i <= lennn; ++i)
#define nl(i, n) (i == n - 1 ? "\n":" ")
using namespace std;
const int maxn = 100005;
inline int read() {
int x(0), f(1); char ch(getchar());
while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int num[maxn], f[maxn], ac[maxn];
vector<int> a;
int n, m;
int main() {
m = read(), n = read();
char s[10];
_rep(i, 1, m) {
int x = read();
scanf("%s", s);
++num[x];
if(s[0] == 'A') ++ac[x];
if(ac[x] * 2 < num[x]) f[x] = 1;
}
vector<int> ans;
_rep(i, 1, n) if(!f[i]) ans.push_back(i);
if(ans.size() == 0) {
printf("-1\n");
return 0;
}
_for(i, ans.size()) printf("%d%s", ans[i], nl(i, ans.size()));
return 0;
}
B 武辰延的字串
oj: 牛客
題意
給出兩個字串，如果可以從 s s s 串中取出兩個前綴組合而成的串正好也是 t t t 串的前綴，求出有多少種組合，
題解
可以認為組合的程序就是先從 s s s 中取出一段前綴同時也是 t t t 的前綴，我們稱這一段為 A A A ；再從 s s s 中取出一段前綴，我們稱這一段為 B B B ， A A A 和 B B B 合成 A B AB AB 依然是 t t t 的前綴，
想到擴展 K M P KMP KMP 演算法的 e x t e n d extend extend 陣列的意義為 s [ i , n ] s[i,n] s[i,n] 與 t t t 的最長公共前綴的長度，
首先求出 s s s 和 t t t 的最長公共前綴，它的長度為 e x t e n d [ 0 ] extend[0] extend[0] ，這也是 A A A 串的最長長度，
當 A A A 確定后，只需取出 t t t 中除了 A A A 之外的部分和 s s s 求最長公共前綴，求出的前綴長度就是這個 A A A 對答案的貢獻，
列舉 A A A 的長度即可， A A A 的長度的取值范圍是 [ 1 , e x t e n d [ 0 ] ] [1,extend[0]] [1,extend[0]] ，
代碼
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define _for(i, a) for (LL i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (LL i = (a), lennn = (b); i <= lennn; ++i)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
typedef long long LL;
const LL maxn = 100005;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
char s[maxn], t[maxn];
int n, m;
int nxt[maxn], ext[maxn];
void getnext(char t[]) {
int tlen = strlen(t);
nxt[0] = tlen;
int now = 0;
while (t[now] == t[now + 1] && now + 1 < tlen) now++;
nxt[1] = now;
int p0 = 1;
for (int i = 2; i < tlen; i++) {
if (i + nxt[i - p0] < nxt[p0] + p0)
nxt[i] = nxt[i - p0];
else {
int now = nxt[p0] + p0 - i;
now = max(0ll, now);
while (t[now] == t[i + now] && i + now < tlen) now++;
nxt[i] = now;
p0 = i;
}
}
}
void exkmp(char s[], char t[]) {
getnext(t);
int slen = strlen(s), tlen = strlen(t);
int now = 0;
while (s[now] == t[now] && now < min(slen, tlen)) now++;
ext[0] = now;
int p0 = 0;
for (int i = 1; i < slen; i++) {
if (i + nxt[i - p0] < ext[p0] + p0)
ext[i] = nxt[i - p0];
else {
int now = ext[p0] + p0 - i;
now = max(now, 0ll);
while (t[now] == s[i + now] && now < tlen && now + i < slen) now++;
ext[i] = now;
p0 = i;
}
}
}
int main() {
scanf("%s%s", s, t);
n = strlen(s), m = strlen(t);
LL ans = 0;
getnext(s);
exkmp(t, s);
_rep(i, 1, ext[0]) ans += ext[i];
printf("%lld\n", ans);
return 0;
}
D 溫澈瀅的狗狗
oj: 牛客
題意
有 n n n 個狗狗，按照 1 ? n 1-n 1?n 編號，每個狗狗有一個顏色值，不同顏色值的狗狗會有親密度，其親密度為編號差的絕對值，
對所有的狗狗組合按照“親密度、較小的編號、較大的編號”為 3 3 3 個關鍵字排序，求出第 k k k 大的組合的狗狗的編號，如果不存在就輸出 ? 1 -1 ?1.
題解
我們發現組合的個數 v a l val val 隨著最大的狗狗編號差值 d i f dif dif 線性增加，可以考慮二分列舉 d i f dif dif 求出 v a l val val，使之與 k k k 作比較，以此求出第一個大于等于 k k k 的 v a l val val 對應的 d i f dif dif，
列舉方法采用尺取法保證 O ( n ) O(n) O(n) 的復雜度，
如果不存在這樣的 d i f dif dif 就輸出 ? 1 -1 ?1.
如果存在，那么我們可以斷定第 k k k 大的組合的編號差的絕對值為 d i f dif dif，并且最后一個差值為 d i f dif dif 的狗狗組合的排名是 v a l val val，
之后只需要將最后一個組合向前移動 v a l ? k val-k val?k 次，即可求出排名為 k k k 的組合，
代碼
#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 100005;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
LL n, k;
int a[maxn];
int num[maxn];
LL che(int mid) {
_for(i, mid + 1) ++num[a[i]];
LL ans = 0;
int l = 0, r = mid;
do {
ans += mid + 1 - num[a[l]];
++num[a[++r]];
--num[a[l++]];
}while(r < n);
do {
ans += r - l - num[a[l]];
--num[a[l++]];
}while(l < n);
return ans;
}
void sol() {
_for(i, n) a[i] = read();
LL l = 0, r = n, dif = 0, val = 0;
while(l <= r) {
LL mid = (l + r) >> 1;
LL tem = che(mid);
if(tem >= k) {
dif = mid;
val = tem;
r = mid - 1;
}
else l = mid + 1;
}
if(dif == 0 || dif == n) {
printf("-1\n");
return;
}
l = n - dif - 1, r = n - 1;
while(a[l] == a[r]) --l, --r;
while(val > k) {
--l, --r;
while(a[l] == a[r]) --l, --r;
--val;
}
printf("%lld %lld\n", l + 1, r + 1);
}
int main() {
while(cin >> n >> k) {
sol();
}
return 0;
}
E 九峰與子序列
oj: 牛客
題意
給定長度為 n n n 的字串序列 a a a 和字串 k k k ，詢問 a a a 有多少子序列拼接起來等于 k k k ，
題解
因為我們要組合的是 a a a 的子序列，所以每個序列都有取和不取兩個狀態，這樣組成一個 01 01 01 背包的問題，
我們記錄 d p [ i ] [ j ] dp[i][j] dp[i][j] 為前 i i i 個序列組成 k k k 串的前 j j j 個字符的情況數，
那么當 k [ j ? l e n ( a [ i ] ) + 1 : j ] = a [ i ] k[j-len(a[i])+1:j]=a[i] k[j?len(a[i])+1:j]=a[i] 時， d p [ i ] [ j ] + = d p [ i ? 1 ] [ j ? l e n ( a [ i ] ) ] dp[i][j]+=dp[i-1][j-len(a[i])] dp[i][j]+=dp[i?1][j?len(a[i])] ，
同時使用字串哈希快速比較兩個串是否相等，
然后列舉 i i i 和 j j j 即可，
代碼
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define _for(i, a) for(int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 5000005;
inline int read() {
int x(0), f(1); char ch(getchar());
while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
const ULL P = 131;
ULL has[maxn], p[maxn];
char s[maxn], t[maxn];
int n;
int sl;
LL dp[maxn];
int che(ULL hash, int l, int r) {
return hash == has[r] - has[l] * p[r - l];
}
int main() {
p[0] = 1;
for(int i = 1; i < maxn; ++i) {
p[i] = p[i - 1] * P;
}
n = read();
scanf("%s", s);
sl = strlen(s);
has[0] = 0;
_for(i, sl) has[i + 1] = has[i] * P + s[i];
dp[0] = 1;
_for(j, n) {
scanf("%s", t);
int tl = strlen(t);
ULL hat = 0;
_for(i, tl) hat = hat * P + t[i];
for(int i = sl; i >= tl; --i) {
dp[i] += dp[i - tl] * che(hat, i - tl, i);
}
}
printf("%lld\n", dp[sl]);
return 0;
}
F 魏遲燕的自走棋
oj: 牛客
題意
有 n n n 個人和 m m m 件裝備，每件裝備各有一個屬性值，且每件裝備只可以被裝備給特定的幾個人，求出如何給這些人配備裝備可以使得總屬性值最大，
題解
每件裝備不管配給誰，只要被配備，它的屬性值就會對答案有貢獻，
所以我們采取貪心的策略，按照屬性值的大小從大到小地列舉裝備，去找增廣路，
若找到則把這件裝備的屬性值加到答案上，
若找不到則意味著一旦裝上這件裝備則會有另一件已經使用的裝備被卸下來，而我們是按照屬性值從大到小列舉的，所以被卸下來的裝備的屬性值一定不比裝上的屬性值小，所以總的來看這樣做會減小總屬性值，所以直接放棄即可，
增廣路采用匈牙利演算法尋找，
值得注意的是一般的匈牙利演算法會超時，原因在于每次尋找增廣路前都要清空 v i s vis vis 陣列，這會占用大量的時間，所以我們尋找完增廣路后回溯地清空增廣路上的 v i s vis vis 陣列，這樣就不用額外清空了，節省了大量的時間，
至于沒有找到增廣路的點，意味著下一次遍歷到它依然找不到增廣路，所以他們的 v i s vis vis 陣列不清空也不影響答案，
代碼
#include<bits/stdc++.h>
#define m_p make_pair
#define _for(i, a) for(int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const int maxn = 100005;
const int maxm = 200005;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
int n, m;
pair<int, int> p[maxn];
int head[maxn], to[maxm], nex[maxm], tot;
inline void addedge(int u, int v) {
to[tot] = v;
nex[tot] = head[u];
head[u] = tot++;
}
int vis[maxn], matching[maxn];
inline int dfs(int u) {
for(int i = head[u]; ~i; i = nex[i]) {
int v = to[i];
if(!vis[v]) {
vis[v] = 1;
if(matching[v] == 0 || dfs(matching[v])) {
matching[v] = u;
vis[v] = 0;
return 1;
}
}
}
return 0;
}
int main() {
n = read(), m = read();
tot = 0;
_for(i, m + 1) head[i] = -1;
_rep(i, 1, m) {
int tn = read();
_for(j, tn) addedge(i, read());
p[i].first = read();
p[i].second = i;
}
sort(p + 1, p + m + 1);
LL ans = 0;
for(int i = m; i > 0; --i) {
if(dfs(p[i].second)) {
ans += p[i].first;
}
}
printf("%lld\n", ans);
return 0;
}
G 九峰與蛇形填數
oj: 牛客
題意
把從 1 1 1 開始的數字按照 S S S 型填入一個矩形，
在一個初始全 0 0 0 的矩形區域內填入若干個小矩形，每個小矩形填入后會覆寫掉原先的數字，
求出 m m m 次操作后的大矩形的數字，
題解
利用線段樹維護每一行的每個區間的小矩形的編號，所有的操作都結束后，再通過每個位置的矩形編號和矩形資訊算出這個位置的數字，
時間復雜度： O ( m k l o g n ) O(mk\ logn) O(mk logn)，
代碼
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define _for(i, a) for(int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(int i = (a), lennn = (b); i <= lennn; ++i)
#define nl(i, n) (i == n - 1 ? "\n":" ")
using namespace std;
typedef long long LL;
const int maxn = 2005;
inline int read() {
int x(0), f(1); char ch(getchar());
while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
struct poi {
int x, y, k;
poi() {}
poi(int x, int y, int k): x(x), y(y), k(k) {}
};
LL T[maxn][maxn << 2];
void update(int s, int node, int beg, int end, int l, int r, int f) {
if(l <= beg && r >= end) {
T[s][node] = f;
return;
}
if(T[s][node]) {
T[s][node << 1] = T[s][node << 1 | 1] = T[s][node];
T[s][node] = 0;
}
int mid = (beg + end) >> 1;
if(l <= mid) update(s, node << 1, beg, mid, l, r, f);
if(r > mid) update(s, node << 1 | 1, mid + 1, end, l, r, f);
return;
}
LL query(int s, int node, int beg, int end, int pos) {
if (T[s][node] || beg == end) return T[s][node];
int mid = (beg + end) >> 1;
if(mid >= pos) return query(s, node << 1, beg, mid, pos);
else return query(s, node << 1 | 1, mid + 1, end, pos);
}
int n, m;
vector<poi> a;
void init() {
a.clear();
a.push_back(poi(0, 0, 0));
}
int getval(int v, int i, int j) {
int px = i - a[v].x, py = j - a[v].y;
int ans = px * a[v].k;
if(px & 1) ans += a[v].k - py;
else ans += py + 1;
return ans;
}
void sol() {
init();
_rep(i, 1, m) {
int x = read(), y = read(), k = read();
a.push_back(poi(x, y, k));
_for(j, k) update(x + j, 1, 1, n, y, y + k - 1, i);
}
_rep(i, 1, n) {
_rep(j, 1, n) {
int val = query(i, 1, 1, n, j);
if(val == 0) printf("0%s", nl(j, n + 1));
else printf("%d%s", getval(val, i, j), nl(j, n + 1));
}
}
}
int main() {
n = read(), m = read();
sol();
return 0;
}
H 吳楚月的運算式
oj: 牛客
題意
給你一顆樹，樹上每個節點有一個正數，樹的每條邊有一個運算子，樹的每條路徑是一個運算式，求出節點 1 1 1 到其他節點的路徑的運算式的值，
題解
時間所限，必須僅僅遍歷 1 1 1 遍就求出所有運算式的值，
由于運算式只有 + ? ? / +-*/ +??/ 四種運算，而且沒有括號，所以任意一個運算式都可以分解為 A + B A+B A+B， B B B 為最后面的僅由 ? / */ ?/ 構成的運算式， A A A 為剩余部分，遇到減號就變成加上負數，
每個節點的 A + B A+B A+B 僅僅依賴父節點的 A + B A+B A+B，所以我們可以通過一次遍歷就求出所有節點的 A + B A+B A+B，然后單獨計算出每個節點的運算式的值，
代碼
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define m_p make_pair
#define p_i pair<LL, LL>
#define _for(i, a) for(LL i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(LL i = (a), lennn = (b); i <= lennn; ++i)
#define nl(i, n) (i == n - 1 ? "\n":" ")
using namespace std;
typedef long long LL;
const LL maxn = 100005;
const LL mod = 1000000007;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
struct poi {
LL num, op;
poi() {}
poi(LL num, LL op): num(num), op(op) {}
};
LL n, a[maxn];
char s[maxn];
LL fa[maxn];
vector<poi> G[maxn];
LL ans[maxn];
vector<pair<LL, LL> > lastans;
void init() {
lastans.clear();
_rep(i, 1, n) ans[i] = -1;
}
void exgcd(LL a, LL b, LL &g, LL &x, LL &y) {
if (!b) {
g = a;
x = 1;
y = 0;
} else {
exgcd(b, a % b, g, y, x);
y -= x * (a / b);
}
}
LL inv(LL x) {
LL a, k, g;
exgcd(x, mod, g, a, k);
if(a < 0) a += mod;
return a;
}
void dfs(LL u) {
for(auto i : G[u]) {
if(i.op == 1) lastans.push_back(m_p(lastans.back().first + lastans.back().second, a[i.num]));
else if(i.op == 2) lastans.push_back(m_p(lastans.back().first + lastans.back().second, -a[i.num]));
else if(i.op == 3) lastans.push_back(m_p(lastans.back().first, lastans.back().second * a[i.num]));
else lastans.push_back(m_p(lastans.back().first, lastans.back().second * inv(a[i.num])));
lastans.back().first %= mod;
lastans.back().second %= mod;
ans[i.num] = lastans.back().first + lastans.back().second;
dfs(i.num);
lastans.pop_back();
}
}
void sol() {
init();
_rep(i, 1, n) a[i] = read();
for(LL i = 2; i <= n; ++i) fa[i] = read();
scanf("%s", s + 2);
_rep(i, 2, n) {
if(s[i] == '+') G[fa[i]].push_back(poi(i, 1));
else if(s[i] == '-') G[fa[i]].push_back(poi(i, 2));
else if(s[i] == '*') G[fa[i]].push_back(poi(i, 3));
else if(s[i] == '/') G[fa[i]].push_back(poi(i, 4));
}
ans[1] = a[1];
lastans.push_back(m_p(0, a[1]));
dfs(1);
_rep(i, 1, n) {
if(ans[i] < 0) ans[i] += mod;
else if(ans[i] >= mod) ans[i] %= mod;
}
_rep(i, 1, n) printf("%lld%s", (ans[i] + mod) % mod, nl(i, n + 1));
}
int main() {
n = read();
sol();
return 0;
}
J 鄔澄瑤的公約數
oj: 牛客
題意
求出 gcd ? ( x 1 p 1 , ? ? , x n p n ) \gcd(x_1^{p_1},\cdots,x_n^{p_n}) gcd(x1p1??,?,xnpn??) 的值，
題解
分別分解出每個數字的質因數以及每個質因數出現的次數，然后取出所有數字的公共質因數并取最小次數構成的數就是答案，
代碼
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define _for(i, a) for(LL i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for(LL i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;
const LL maxn = 100005;
const LL mod = 1000000007;
inline LL read() {
LL x(0), f(1); char ch(getchar());
while (ch<'0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
map<LL, LL> mp[2];
LL f;
LL n;
vector<LL> x, p;
vector<LL> arr;
LL vis[100006];
void doit(LL maxnum) {
for(LL i = 2; i <= maxnum; ++i) {
if(!vis[i]) arr.push_back(i);
for(LL j = 0; j < arr.size() && arr[j] * i <= maxnum; ++j) {
vis[arr[j] * i] = 1;
if(i % arr[j] == 0) break;
}
}
}
LL quickPow(LL x, LL n, LL mod) {
LL ans = 1;
while(n) {
if(n & 1) ans *= x, ans %= mod;
x *= x, x %= mod;
n >>= 1;
}
return ans;
}
void sol() {
_for(i, n) x.push_back(read());
_for(i, n) p.push_back(read());
for(LL i = 0, tx = x[0]; i < arr.size() && arr[i] <= tx; ++i) {
if(tx % arr[i] == 0) {
LL num = 0;
while(tx % arr[i] == 0) {
++num;
tx /= arr[i];
}
mp[f][arr[i]] = num * p[0];
}
}
f ^= 1;
for(LL i = 1; i < n; ++i) {
mp[f].clear();
for(LL j = 0, tx = x[i]; j < arr.size() && arr[j] <= tx; ++j) {
if(tx % arr[j] == 0) {
LL num = 0;
while(tx % arr[j] == 0) {
++num;
tx /= arr[j];
}
if(mp[f ^ 1].count(arr[j])) mp[f][arr[j]] = min(mp[f ^ 1][arr[j]], num * p[i]);
}
}
f ^= 1;
}
LL ans = 1;
f ^= 1;
for(auto i : mp[f]) {
ans *= quickPow(i.first, i.second, mod);
ans %= mod;
}
printf("%lld\n", ans);
}
int main() {
doit(10000);
n = read();
sol();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262204.html
標籤：其他