牛客練習試合47題解
8852 ワード
A DongDong破パスワード:
n,mを与え,長さnの01列を与え,毎回1ビット後方に移動し,m−1回移動し,最後にこのn+m−1ビットの各ビットの異種または値が暗号化されることを求めた.長さnの01列がどうなっているかを尋ねるパスワードを与えます.
2<=n+m<=1000000 2<=n+m<=1000000 2<=n+m<=1000000、保証あり
分析:
パスワード第i i iビットをa i a_とするi ai、原列第i i i iビットをb i b_とするi bi a 1 = b 1 a_1=b_1 a1=b1 a 2 = b 1 a_2=b_1 a2=b1^ b 2 b_2 b2 a 3 = b 1 a_3=b_1 a3=b1^ b 2 b_2 b2^ b 3 b_3 b3 a m = b 1 a_m=b_1 am=b1^ b 2 b_2 b2… b m − 1 b_{m-1} bm−1^ b m b_m bm … a n = b n − m + 1 a_n=b_{n-m+1} an=bn−m+1^ b n − m + 2 b_{n-m+2} bn−m+2… b n − 1 b_{n-1} bn−1^ b n b_n bnを上に押すと前のn n n個のb i b_が押し出されます.ibi時間複雑度O(n)O(n)O(n)O(n)
コード:
B DongDongは親戚を知っています.
定義:AとBが親戚で、BとCが親戚であれば、AとCも親戚です.n人がいて、m回の操作はn人の名前がそれぞれ何であるか(複数の名前が同じであれば同じ人と見なす)(名前が小文字文字列であることを保証する)を与えてm個の操作を与えて、各行の操作は1つの数のoptを与えて、2つの名前x、yはopt=1の時、xを表して、yは親戚がopt=2の時、xを尋ねて、yは親戚であるかどうかを表して、1を出力するならば、0ではありません
1<=n,m<=20000,名前文字長が小さいのは10 1<=n,m<=20000,名前文字長が小さいのは10 1<=n,m<=20000,名前文字長が小さいのは10
分析:
名前ごとに異なるi d idをタグ付けし、裸のパラレルセットを検索することができます.i d idはソートして再表示することができます.x、y x、y x、yのi d idクエリーはl o w e r lower lower_を利用することができます.b o u n d bound bound時間複雑度:O(m l o g n)O(mlogn)O(mlogn)
コード:
C DongDongジャンプ:
n本の柱があり、各柱には高さと柱の上の魚の干物の数があります.最初は任意の柱に立って、ジャンプのたびに長さに制限されず、左から右にジャンプするしかありませんが、現在の高さとの差の絶対値がm以下の柱にジャンプするしかありません.問最も多く食べられる干物(最終的にはn本目の柱に落ちる必要はない)1<=n<=200000,1<=m<=500,000,1<=n<=200000,1<=m<=500,000,1<=n<=500,000,1<=m<=500柱あたりの高さxと干物の数yに対して、1<=x<=100000,1<=x,y<=100000,1<=x,y<=100000,000,1<=x,y<=100000
分析:
d p i dp_を設定i dpiは、最後に高さi i iの柱に落下したときに得ることができる最大の魚の幹を表し、次に左から右に柱を列挙する、現在の柱k k,d p x k=m a x(d p x k,m a x(d p x k−m,d p x k−m+1,.,d p x k+m−1,d p x+m)+y k dp_{x_k}=max(dp_{x_k},max(dp_{x_k-m},dp_{x_k-m+1},...,dp_{x_k+m-1},dp_{x_k+m})+y_kdpxk=max(dpxk,max(dpxk−m,dpxk−m+1,...,dpxk+m−1,dpxk+m)+yk)そしてm a x(dpxk−m,dpxk−m−m,dpxk−m−m+1,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,k−m+1,...,dpxk+m−1,dpxk+m)線分ツリーでメンテナンスできる時間の複雑さはO(nl o g(xm a x))O(nlog(x_{max}))O(nlog(xmax))である可能性のある境界x k−m<0 x_に注意k-m<0 xk−m<0またはx k+m>xma x_k+m>x_{max} xk+m>xmax
コード:
D DongDong飛行機に乗る:
n都市、m航路、k回半額の機会を与え、1はDongDong家、nはサモエ家、各片側には始点と航空券の価格(すべての価格が0より大きいことを保証する)があり、彼女はk回半額割引を使って、1からnまでの最小費用を求めることができます.(1からnまで出力-1)すべての価格が偶数であることを保証できないn<=10000,m<=50000,k<=10,0<=100000 n<=10000,m<=50000,k<=10,000,0<=w<=10,000,m<=10,000,m<=10,000,k<=10,0<=w<=10,000,000,000,m<=10,000,m<=10,000,w<=10,000,000,m
分析:
階層図が最も短絡し、d i s i,j dis_{i,j}disi,jは都市i i iを表し,j j j半額割引に必要な最小費用を用いてs pf a spfa spfaを直接行えば理論的複雑度O(n k l o g(n k))O(nklog(nk))O(nklog(nk))
コード:
E DongDong数の色:
n個の点を与え、n-1辺の木図(1号店を根とする)は、各点に1色、m個の問い合わせがあり、xを根とするサブツリーの中で何種類の異なる色があるかを尋ねるたびに、2<=n<=100000、1<=m、c o l o r<=n 2<=n<=100000、1<=n 2<=n<=n 2<=n<=100000、1<=m、1<=n 2<=n
分析:
a n s i ans_を設定するi ansiはxをルートとするサブツリーに何種類の異なる色があるかを表す.次に、s e t set内の要素の重複性を利用して、下から上へ結合し、現在のx xノードのs e t setの大きさはa n s x ans_である.x ansx質問ごとに直接答えればいい
コード:
F DongDongの生成ツリー:
完了待ち
n,mを与え,長さnの01列を与え,毎回1ビット後方に移動し,m−1回移動し,最後にこのn+m−1ビットの各ビットの異種または値が暗号化されることを求めた.長さnの01列がどうなっているかを尋ねるパスワードを与えます.
2<=n+m<=1000000 2<=n+m<=1000000 2<=n+m<=1000000、保証あり
分析:
パスワード第i i iビットをa i a_とするi ai、原列第i i i iビットをb i b_とするi bi a 1 = b 1 a_1=b_1 a1=b1 a 2 = b 1 a_2=b_1 a2=b1^ b 2 b_2 b2 a 3 = b 1 a_3=b_1 a3=b1^ b 2 b_2 b2^ b 3 b_3 b3 a m = b 1 a_m=b_1 am=b1^ b 2 b_2 b2… b m − 1 b_{m-1} bm−1^ b m b_m bm … a n = b n − m + 1 a_n=b_{n-m+1} an=bn−m+1^ b n − m + 2 b_{n-m+2} bn−m+2… b n − 1 b_{n-1} bn−1^ b n b_n bnを上に押すと前のn n n個のb i b_が押し出されます.ibi時間複雑度O(n)O(n)O(n)O(n)
コード:
#include
#define N 1000005
using namespace std;
int a[N], c[N], n, m;
char s[N];
// 110, 000, 011, 101
int main()
{
scanf("%d %d", &n, &m);
scanf("%s", s + 1);
for (int i = 1; i <= n + m - 1; i++) a[i] = s[i] - '0';
int now = a[1]; c[1] = a[1];
printf("%d", a[1]);
for (int i = 2; i <= n; i++)
{
if (i > m) now ^= c[i - m];
c[i] = a[i] ^ now;
printf("%d", c[i]);
now ^= c[i];
}
return 0;
}
B DongDongは親戚を知っています.
定義:AとBが親戚で、BとCが親戚であれば、AとCも親戚です.n人がいて、m回の操作はn人の名前がそれぞれ何であるか(複数の名前が同じであれば同じ人と見なす)(名前が小文字文字列であることを保証する)を与えてm個の操作を与えて、各行の操作は1つの数のoptを与えて、2つの名前x、yはopt=1の時、xを表して、yは親戚がopt=2の時、xを尋ねて、yは親戚であるかどうかを表して、1を出力するならば、0ではありません
1<=n,m<=20000,名前文字長が小さいのは10 1<=n,m<=20000,名前文字長が小さいのは10 1<=n,m<=20000,名前文字長が小さいのは10
分析:
名前ごとに異なるi d idをタグ付けし、裸のパラレルセットを検索することができます.i d idはソートして再表示することができます.x、y x、y x、yのi d idクエリーはl o w e r lower lower_を利用することができます.b o u n d bound bound時間複雑度:O(m l o g n)O(mlogn)O(mlogn)
コード:
#include
#define N 20005
using namespace std;
int fa[N], n, m;
string s[N];
int find(int x)
{
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) cin >> s[i];
sort(s + 1, s + n + 1);
int tot = unique(s + 1, s + n + 1) - s - 1;
for (int i = 1; i <= tot; i++) fa[i] = i;
for (int i = 1; i <= m; i++)
{
int opt; string x, y;
scanf("%d", &opt); cin >> x >> y;
int pos1 = lower_bound(s + 1, s + tot + 1, x) - s - 1;
int pos2 = lower_bound(s + 1, s + tot + 1, y) - s - 1;
if (opt == 1) fa[find(pos1)] = find(pos2);
else { if (find(pos1) == find(pos2)) printf("1
"); else printf("0
"); }
}
return 0;
}
C DongDongジャンプ:
n本の柱があり、各柱には高さと柱の上の魚の干物の数があります.最初は任意の柱に立って、ジャンプのたびに長さに制限されず、左から右にジャンプするしかありませんが、現在の高さとの差の絶対値がm以下の柱にジャンプするしかありません.問最も多く食べられる干物(最終的にはn本目の柱に落ちる必要はない)1<=n<=200000,1<=m<=500,000,1<=n<=200000,1<=m<=500,000,1<=n<=500,000,1<=m<=500柱あたりの高さxと干物の数yに対して、1<=x<=100000,1<=x,y<=100000,1<=x,y<=100000,000,1<=x,y<=100000
分析:
d p i dp_を設定i dpiは、最後に高さi i iの柱に落下したときに得ることができる最大の魚の幹を表し、次に左から右に柱を列挙する、現在の柱k k,d p x k=m a x(d p x k,m a x(d p x k−m,d p x k−m+1,.,d p x k+m−1,d p x+m)+y k dp_{x_k}=max(dp_{x_k},max(dp_{x_k-m},dp_{x_k-m+1},...,dp_{x_k+m-1},dp_{x_k+m})+y_kdpxk=max(dpxk,max(dpxk−m,dpxk−m+1,...,dpxk+m−1,dpxk+m)+yk)そしてm a x(dpxk−m,dpxk−m−m,dpxk−m−m+1,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,k−m+1,...,dpxk+m−1,dpxk+m)線分ツリーでメンテナンスできる時間の複雑さはO(nl o g(xm a x))O(nlog(x_{max}))O(nlog(xmax))である可能性のある境界x k−m<0 x_に注意k-m<0 xk−m<0またはx k+m>xma x_k+m>x_{max} xk+m>xmax
コード:
#include
#define lson(x) x * 2
#define rson(x) x * 2 + 1
#define M 1000005
#define N 200005
using namespace std;
typedef long long ll;
struct Node { int x; ll y; }a[N];
ll dp[M], C[M*5];
int maxnum, n, m;
void change(int G, int l, int r, int num1, ll num2)
{
if (l == r) { C[G] = num2; return; }
int mid = (l + r) >> 1;
if (num1 <= mid) change(lson(G), l, mid, num1, num2);
else change(rson(G), mid + 1, r, num1, num2);
C[G] = max(C[lson(G)], C[rson(G)]);
}
ll Get_max(int G, int l, int r, int ll, int rr)
{
if (ll == l && rr == r) return C[G];
int mid = (l + r) >> 1;
if (rr <= mid) return Get_max(lson(G), l, mid, ll, rr);
if (ll > mid) return Get_max(rson(G), mid + 1, r, ll, rr);
if (ll <= mid && rr > mid) return max(Get_max(lson(G), l, mid, ll, mid), Get_max(rson(G), mid + 1, r, mid + 1, rr));
return 0;
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d %lld", &a[i].x, &a[i].y), maxnum = max(maxnum, a[i].x);
dp[a[1].x] = a[1].y;
change(1, 1, maxnum, a[1].x, a[1].y);
for (int i = 2; i <= n; i++)
{
ll now = Get_max(1, 1, maxnum, max(a[i].x - m, 1), min(a[i].x + m, maxnum)) + a[i].y;
if (now > dp[a[i].x]) dp[a[i].x] = now, change(1, 1, maxnum, a[i].x, dp[a[i].x]);
}
ll ans = 0;
for (int i = 1; i <= maxnum; i++) ans = max(ans, dp[i]);
printf("%lld
", ans);
return 0;
}
D DongDong飛行機に乗る:
n都市、m航路、k回半額の機会を与え、1はDongDong家、nはサモエ家、各片側には始点と航空券の価格(すべての価格が0より大きいことを保証する)があり、彼女はk回半額割引を使って、1からnまでの最小費用を求めることができます.(1からnまで出力-1)すべての価格が偶数であることを保証できないn<=10000,m<=50000,k<=10,0<=100000 n<=10000,m<=50000,k<=10,000,0<=w<=10,000,m<=10,000,m<=10,000,k<=10,0<=w<=10,000,000,000,m<=10,000,m<=10,000,w<=10,000,000,m
分析:
階層図が最も短絡し、d i s i,j dis_{i,j}disi,jは都市i i iを表し,j j j半額割引に必要な最小費用を用いてs pf a spfa spfaを直接行えば理論的複雑度O(n k l o g(n k))O(nklog(nk))O(nklog(nk))
コード:
#include
#define N 10005
#define M 50005
using namespace std;
typedef long long ll;
struct Node { int To, nxt; ll w; }e[M];
struct Code { int u, v; ll w; }a[M];
int ls[N], n, m, K, cnt;
ll dis[N][11], inf = 0x7fffffff;
bool vis[N][11];
queue Q[2];
bool cmp(Code aa, Code bb)
{
if (aa.u == bb.u) return aa.v < bb.v;
return aa.u < bb.u;
}
void Addedge(int u, int v, ll w)
{
e[++cnt].To = v, e[cnt].w = w, e[cnt].nxt = ls[u], ls[u] = cnt;
}
void spfa()
{
for (int i = 1; i <= n; i++)
for (int j = 0; j <= K; j++) dis[i][j] = inf * 10;
Q[0].push(1); Q[1].push(0);
vis[1][0] = 1; dis[1][0] = 0;
while (Q[0].size())
{
int u = Q[0].front(); Q[0].pop();
int num = Q[1].front(); Q[1].pop();
for (int i = ls[u]; i; i = e[i].nxt)
{
if (dis[u][num] + e[i].w / 2 <= dis[e[i].To][num + 1] && num + 1 <= K)
{
dis[e[i].To][num + 1] = dis[u][num] + e[i].w / 2;
if (!vis[e[i].To][num + 1]) Q[0].push(e[i].To), Q[1].push(num + 1), vis[e[i].To][num + 1] = 1;
}
if (dis[u][num] + e[i].w <= dis[e[i].To][num])
{
dis[e[i].To][num] = dis[u][num] + e[i].w;
if (!vis[e[i].To][num]) Q[0].push(e[i].To), Q[1].push(num), vis[e[i].To][num] = 1;
}
}
vis[u][num] = 0;
}
}
int main()
{
scanf("%d %d %d", &n, &m, &K);
for (int i = 1; i <= m; i++) scanf("%d %d %lld", &a[i].u, &a[i].v, &a[i].w);
for (int i = 1; i <= m; i++)
if (a[i].u != a[i].v)
if (a[i].u != a[i - 1].u || a[i].v != a[i - 1].v) Addedge(a[i].u, a[i].v, a[i].w);
spfa();
ll ans = inf * 10;
for (int i = 0; i <= K; i++) ans = min(ans, dis[n][i]);
if (ans == inf * 10) printf("-1
"); else printf("%lld
", ans);
return 0;
}
E DongDong数の色:
n個の点を与え、n-1辺の木図(1号店を根とする)は、各点に1色、m個の問い合わせがあり、xを根とするサブツリーの中で何種類の異なる色があるかを尋ねるたびに、2<=n<=100000、1<=m、c o l o r<=n 2<=n<=100000、1<=n 2<=n<=n 2<=n<=100000、1<=m、1<=n 2<=n
分析:
a n s i ans_を設定するi ansiはxをルートとするサブツリーに何種類の異なる色があるかを表す.次に、s e t set内の要素の重複性を利用して、下から上へ結合し、現在のx xノードのs e t setの大きさはa n s x ans_である.x ansx質問ごとに直接答えればいい
コード:
#include
#define N 100005
using namespace std;
struct Node{ int To, nxt; }e[N*2];
int ans[N], col[N], ls[N], n, m, cnt;
void Addedge(int u, int v)
{
e[++cnt].To = v, e[cnt].nxt = ls[u], ls[u] = cnt;
e[++cnt].To = u, e[cnt].nxt = ls[v], ls[v] = cnt;
}
set dfs(int x, int y)
{
set a;
for (int i = ls[x]; i; i = e[i].nxt)
{
if (e[i].To == y) continue;
set b = dfs(e[i].To, x);
for (set::iterator j = b.begin(); j != b.end(); j++) a.insert(*j);
}
a.insert(col[x]);
ans[x] = a.size();
return a;
}
int main()
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &col[i]);
int u, v;
for (int i = 1; i < n; i++) scanf("%d %d", &u, &v), Addedge(u, v);
ans[1] = dfs(1, -1).size();
for (int i = 1; i <= m; i++)
{
int ask; scanf("%d", &ask); printf("%d
", ans[ask]);
}
return 0;
}
F DongDongの生成ツリー:
完了待ち