當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

Codeforces Round #520 (Div. 2)

發布時間：2025/6/17 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了 Codeforces Round #520 (Div. 2) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

A.prank

題意：給出一個含有n個數的遞增的序列，問最多能刪除多少個連續的數字，使得這個數列還是只可能有這一種形式。

分析：那就找出一段最長的差為1的序列就行。

B.Math

題意：給出一個正整數n，可以進行以下兩種操作。1將n乘一個整數x。2將n開平方。問最少需要多少次操作能將n變得最小？

分析：將n唯一分解，n能變得最小得值就是n所有得質因子得乘積。次數就是先將所有質因子得次數都變成一個2得某次方，然后不斷開方。

C.Banh-mi

題意：略

分析：我對這個題完全沒印象了···汗···

D.Fun with Integers

題意：給出一個大于等于2的正整數n，對于每一對正整數a,b，你可以將a變成b當存在一個x滿足a*x = b或者b*x =a。每次變完以后的得分是|x|。問最大得分。

分析：我們發現，對于n以內的每一對滿足條件的a,b都可以像樣例那么變換。那么只要找出n以內成對的倍數就可以了。

E.Company

題意：給出一課有n個點的樹，和q個詢問，每個詢問給出一個區間[li,ri]。你可以刪除區間內的一個結點，使得刪除以后區間內點的lca深度最大。

分析：區間的lca怎么求？[l,r]內dfs序最大的點和最小的點的lca就是這個區間的lca。那要刪除的點一定就是這兩個點其中的一個。按照慣例我們用線段樹維護就可以了。

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 #include <stack> 8 #include <cmath> 9 #include <cstdlib> 10 #include <set> 11 #include <map> 12 13 14 using namespace std; 15 typedef long long LL; 16 typedef unsigned long long ull; 17 typedef pair<int,int>pir; 18 const int INF = 2147000000; 19 const LL inf = 1e18; 20 const int maxn = 100000 + 10; 21 int head[maxn],to[2*maxn],Next[2*maxn]; 22 int depth[maxn],order[maxn],idx[maxn];//order dfs序列,idx是dfs結點的dfs序 23 int f[maxn][30]; 24 int n,sz,q,maxd,N; 25 void init(){ 26 sz = 0; 27 N = 0; 28 memset(head,-1,sizeof(head)); 29 } 30 void add_edge(int a,int b){ 31 ++sz; 32 to[sz] = b; 33 Next[sz] = head[a]; 34 head[a] = sz; 35 } 36 void dfs(int u,int fa,int dep){ 37 depth[u] = dep; 38 f[u][0] = fa; 39 N++; 40 order[N] = u; 41 idx[u] = N; 42 for(int i = 1; i <= maxd; i++){ 43 f[u][i] = f[f[u][i-1]][i-1]; 44 } 45 for(int i = head[u]; i != -1; i = Next[i]){ 46 int v = to[i]; 47 if(v == fa) 48 continue; 49 dfs(v, u, dep + 1); 50 } 51 return; 52 } 53 pir minv[4*maxn],maxv[4*maxn]; 54 void build(int o,int L,int R){ 55 if(L == R){ 56 minv[o].first = idx[L]; 57 minv[o].second = L; 58 maxv[o] = minv[o]; 59 return ; 60 } 61 int M = L +(R - L)/2; 62 build(2*o,L,M); 63 build(2*o+1,M+1,R); 64 minv[o] = min(minv[2*o], minv[2*o+1]); 65 maxv[o] = max(maxv[2*o], maxv[2*o+1]); 66 } 67 68 pir query_min(int o,int L,int R,int ql,int qr){ 69 if(ql<=L&&qr>=R){ 70 return minv[o]; 71 } 72 int M = L + (R - L)/2; 73 pir res = make_pair(INF,INF); 74 if(ql <= M) 75 res = query_min(2*o,L,M,ql,qr); 76 if(qr > M) 77 res = min(res, query_min(2*o+1,M+1,R,ql,qr)); 78 return res; 79 } 80 81 pir query_max(int o,int L,int R,int ql,int qr){ 82 if(ql<=L&&qr>=R){ 83 return maxv[o]; 84 } 85 int M = L + (R - L)/2; 86 pir res = make_pair(-INF,-INF); 87 if(ql <= M) 88 res = query_max(2*o,L,M,ql,qr); 89 if(qr > M) 90 res = max(res, query_max(2*o+1,M+1,R,ql,qr)); 91 return res; 92 } 93 94 int lca(int u, int v){ 95 if(depth[u] > depth[v])swap(u,v); 96 for(int i = maxd; i >= 0; i--){ 97 if(depth[f[v][i]] >= depth[u]) 98 v = f[v][i]; 99 } 100 if(u == v) 101 return u; 102 for(int i = maxd; i >= 0; i--){ 103 if(f[u][i] != f[v][i]){ 104 u = f[u][i], v = f[v][i]; 105 } 106 } 107 return f[u][0]; 108 } 109 110 int main(){ 111 scanf("%d%d",&n,&q); 112 maxd = (int)(log(n)/log(2)) + 1; 113 //printf("%d\n",maxd); 114 init(); 115 for(int i = 2; i <= n; i++){ 116 int fa; 117 scanf("%d",&fa); 118 add_edge(fa,i); 119 add_edge(i,fa); 120 } 121 dfs(1,-1,1); 122 build(1,1,n); 123 124 for(int i = 1; i <= q; i++){ 125 int l , r; 126 scanf("%d%d",&l,&r); 127 pir Max = query_max(1,1,n,l,r); 128 pir Min = query_min(1,1,n,l,r); 129 int lc1,lc2; 130 //先嘗試刪最大的 131 pir max1 = make_pair(-INF,-INF); 132 if(Max.second > l) 133 max1 = query_max(1,1,n,l,Max.second-1); 134 if(Max.second < r) 135 max1 = max(max1,query_max(1,1,n,Max.second+1,r)); 136 lc1 = lca(max1.second,Min.second); 137 pir min1 = make_pair(INF,INF); 138 if(Min.second > l) 139 min1 = query_min(1,1,n,l,Min.second-1); 140 if(Min.second < r) 141 min1 = min(min1,query_min(1,1,n,Min.second+1,r)); 142 lc2 = lca(Max.second,min1.second); 143 if(depth[lc1] >= depth[lc2]){ 144 printf("%d %d\n",Max.second,depth[lc1]-1); 145 }else{ 146 printf("%d %d\n",Min.second,depth[lc2]-1); 147 } 148 } 149 return 0; 150 } View Code

F.Upgrading Cities

這個題參考的一位巨巨的博客：https://blog.csdn.net/corsica6/article/details/84098779

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <queue> 6 7 8 using namespace std; 9 const int maxn = 300000+100; 10 int n,m,sz,l,r; 11 int head[maxn],Next[maxn],to[maxn],in[maxn],out[maxn],deg[maxn],q[maxn]; 12 void init(){ 13 sz = 0; 14 memset(deg,0,sizeof(deg)); 15 memset(head,-1,sizeof(head)); 16 } 17 void add_edge(int a,int b){ 18 ++sz; 19 to[sz] = b; 20 Next[sz] = head[a]; 21 head[a] = sz; 22 } 23 struct Edge{ 24 int from,to; 25 }edges[maxn]; 26 int main(){ 27 init(); 28 scanf("%d%d",&n,&m); 29 for(int i = 1; i <= m; i++){ 30 int a , b; 31 scanf("%d%d",&a,&b); 32 edges[i].from = a; 33 edges[i].to = b; 34 add_edge(a,b); 35 deg[b]++; 36 } 37 l = r = 0; 38 for(int i = 1; i <= n; i++){ 39 if(!deg[i]){ 40 q[r++] = i; 41 } 42 } 43 44 while(l<r){ 45 int u = q[l++]; 46 if(l==r){ 47 out[u] = n - r; 48 }else if(l+1 == r){ 49 int v = q[l]; 50 int flag = 1; 51 for(int i = head[v]; i!=-1; i = Next[i]){ 52 int vv = to[i]; 53 if(deg[vv] == 1){ 54 flag = 0; 55 break; 56 } 57 } 58 if(!flag) 59 out[u] = -n; 60 else 61 out[u] = n - r; 62 }else 63 out[u] = -n; 64 65 for(int i = head[u]; i!=-1; i = Next[i]){ 66 int v = to[i]; 67 deg[v]--; 68 if(!deg[v]) 69 q[r++] = v; 70 } 71 } 72 init(); 73 for(int i = 1; i <= m; i++){ 74 add_edge(edges[i].to,edges[i].from); 75 deg[edges[i].from]++; 76 } 77 l=r=0; 78 for(int i = 1; i <= n; i++){ 79 if(!deg[i]){ 80 q[r++] = i; 81 } 82 } 83 while(l<r){ 84 int u = q[l++]; 85 if(l==r){ 86 in[u] = n - r; 87 }else if(l+1 == r){ 88 int v = q[l]; 89 int flag = 1; 90 for(int i = head[v]; i != -1; i = Next[i]){ 91 int vv = to[i]; 92 if(deg[vv] == 1){ 93 flag = 0; 94 break; 95 } 96 } 97 if(!flag) 98 in[u] = -n; 99 else 100 in[u] = n - r; 101 }else 102 in[u] = -n; 103 for(int i = head[u]; i != -1; i = Next[i]){ 104 int vv = to[i]; 105 deg[vv] --; 106 if(!deg[vv]) 107 q[r++] = vv; 108 } 109 } 110 int ans = 0; 111 for(int i = 1; i <= n; i++){ 112 // printf("%d %d\n",in[i],out[i]); 113 if(in[i] + out[i] >= n-2){ 114 ans++; 115 } 116 } 117 printf("%d\n",ans); 118 return 0; 119 } View Code

轉載于:https://www.cnblogs.com/LQLlulu/p/10011917.html

總結

以上是生活随笔為你收集整理的Codeforces Round #520 (Div. 2)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。