Codeforces Educational Codeforces Round 54 题解

2024-02-19 13:02:04

A. Minimizing the String

题意：给出一个字符串，最多删掉一个字母，输出操作后字典序最小的字符串。

题解：若存在一个位置 i 满足 a[i] > a[i+1]，若不删除 a[i] 则后续操作不可能更优。

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int MAXN = 2e5 + ;

 const int MAXM = 2e5 + ;

 const ll mod = 1e9 + ;

 char s[MAXN];

 int main() {

 #ifdef local

     freopen("data.txt", "r", stdin);

 //    freopen("data.txt", "w", stdout);

 #endif

     int n;

     scanf("%d%s",&n,s);

     int pos = n - ;

     for(int i = ; i < n - ; i++) {

         if(s[i] > s[i + ]) {

             pos = i;

             break;

         }

     }

     for(int i = ; i < n; i++)

         if(i != pos) printf("%c",s[i]);

     return ;

 }

B. Divisor Subtraction

题意：对于一个 n，每次减去它的最小质因子直到为 0，求操作次数。

题解：n <= 1e10，所以先筛出 1e5 以内的质因子，然后暴力找最小质因子，当最小质因子为 2 的时候，已经不存在更小的质因子，直接跳出循环即可。

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int MAXN = 2e5 + ;

 const int MAXM = 2e5 + ;

 const ll mod = 1e9 + ;

 bool check[MAXN];

 int prime[MAXN];

 int tot;

 void init() {

     mst(check, false);

     tot = ;

     for(int i = ; i <= 1e5; i++) {

         if(!check[i]) prime[tot++] = i;

         for(int j = ; j < tot; j++) {

             if(i * prime[j] > 1e5) break;

             check[i * prime[j]] = true;

             if(i % prime[j] == ) break;

         }

     }

 }

 int main() {

 #ifdef local

     freopen("data.txt", "r", stdin);

 //    freopen("data.txt", "w", stdout);

 #endif

     init();

     ll n;

     scanf("%lld",&n);

     ll ans = ;

     while(n) {

         bool flag = false;

         for(int i = ; i < tot && n >= prime[i]; i++) {

             if(n % prime[i] == ) {

                 if(prime[i] == ) {

                     flag = true;

                     ans += n / ;

                     n = ;

                     break;

                 }

                 n -= prime[i];

                 ans++;

                 flag = true;

                 break;

             }

         }

         if(!flag) {

             ans++;

             break;

         }

     }

     printf("%lld\n",ans);

     return ;

 }

C. Meme Problem

题意：给出一个 d，求是否存在 a + b = d 且 ab = d。

题解：解一元二次方程，判一下无解的条件即可。

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int MAXN = 2e5 + ;

 const int MAXM = 2e5 + ;

 const ll mod = 1e9 + ;

 int main() {

 #ifdef local

     freopen("data.txt", "r", stdin);

 //    freopen("data.txt", "w", stdout);

 #endif

     int t;

     cin >> t;

     while(t--) {

         int d;

         cin >> d;

         if(d <  && d != ) {

             cout << "N" << endl;

             continue;

         }

         cout << "Y ";

         long double a = sqrt(((long double)d * d - 4.0 * (long double)d) / 4.0) + (long double)d / 2.0;

         long double b = (long double)d - a;

         cout << fixed << setprecision() << a << ' ';

         cout << fixed << setprecision() << b << endl;

     }

     return ;

 }

D. Edge Deletion

题意：给出一个 n 个点 m 条边的图，问最多保留 k 条边的情况下，起点 1 到每个点的最短路不变的最多有多少个，输出保留的边。

题解：先对起点 1 跑一遍 dij，因为 n - 1 条边可以构成图的最短路，每条边产生对一个点的最短路，故跑 dij 时记录一下走当前这个点的边，跑 dfs 按顺序输出结果即可。

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int MAXN = 3e5 + ;

 const int MAXM = 2e5 + ;

 const ll mod = 1e9 + ;

 struct edge {

     int v,w,id;

 };

 vector<edge>g[MAXN];

 bool vis[MAXN];

 ll dis[MAXN];

 vector<int>ans;

 pii add[MAXN];

 void dij(int s, int n) {

     ll inf2 = 1e16;

     for(int i = ; i <= n; ++i)

         dis[i] = inf2, vis[i] = ;

     dis[s] = ;

     priority_queue<pair<ll, int> >q;

     q.push(mp(, s));

     for(; !q.empty();) {

         int u = q.top().second;

         q.pop();

         if(vis[u]) continue;

         vis[u] = ;

         for(int j = , sz = g[u].size(); j < sz; ++j) {

             int v = g[u][j].v;

             int w = g[u][j].w;

             int id = g[u][j].id;

             if(dis[v] > dis[u] + w) {

                 add[v] = mp(u,id);

                 dis[v] = dis[u] + w;

                 q.push(mp(-dis[v], v));

             }

         }

     }

 }

 vector<pii>vec[MAXN];

 int tot;

 void dfs(int u) {

     vis[u] = true;

     for(int i = ; i < vec[u].size() && tot; i++) {

         int v = vec[u][i].first, id = vec[u][i].second;

         if(vis[v]) continue;

         printf("%d ",id);

         tot--;

         dfs(v);

     }

 }

 int main() {

 #ifdef local

     freopen("data.txt", "r", stdin);

 //    freopen("data.txt", "w", stdout);

 #endif

     int n,m,k;

     scanf("%d%d%d",&n,&m,&k);

     for(int i = ; i <= m; i++) {

         int u,v,w;

         scanf("%d%d%d",&u,&v,&w);

         g[u].pb({v,w,i});

         g[v].pb({u,w,i});

     }

     dij(,n);

     for(int i = ; i <= n; i++) {

         vec[i].push_back(mp(add[i].first,add[i].second));

         vec[add[i].first].push_back(mp(i,add[i].second));

     }

     tot = min(n - ,k);

     printf("%d\n",min(n - ,k));

     mst(vis, false);

     dfs();

     return ;

 }

E. Vasya and a Tree

题意：有一棵 n 个点的树，有 m 次操作（v，d，x），每次将以 v 为根且距离 v <= d 的点加上权值 x（初始权值为0），输出最后每个点的权值。

题解：考虑离线操作，把每个点作为根的操作存起来，dfs 记录当前深度所增加的权值，对于不可到达的深度，用一个数组来记录要减去的值，差分的思想，详见代码~

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int MAXN = 3e5 + ;

 const int MAXM = 2e5 + ;

 const ll mod = 1e9 + ;

 vector<int>vec[MAXN];

 vector<pii>q[MAXN];

 int h = -;

 ll ans[MAXN],dep[MAXN],now = ;

 void dfs(int u,int fa) {

     h++;

     now += dep[h];

     for(int i = ; i < q[u].size(); i++) {

         int d = q[u][i].first, x = q[u][i].second;

         now += x;

         if(h + d +  < MAXN) dep[h + d + ] -= x;

     }

 //    cout << u << " " << fa << ":" << now << endl;

     ans[u] += now;

     for(int i = ; i < vec[u].size(); i++) {

         int v = vec[u][i];

         if(v == fa) continue;

         dfs(v,u);

     }

     for(int i = ; i < q[u].size(); i++) {

         int d = q[u][i].first, x = q[u][i].second;

         now -= x;

         if(h + d +  < MAXN) dep[h + d + ] += x;

     }

     now -= dep[h];

     h--;

 }

 int main() {

 #ifdef local

     freopen("data.txt", "r", stdin);

 //    freopen("data.txt", "w", stdout);

 #endif

     int n;

     scanf("%d",&n);

     for(int i = ; i < n; i++) {

         int u,v;

         scanf("%d%d",&u,&v);

         vec[u].push_back(v);

         vec[v].push_back(u);

     }

     int m;

     scanf("%d",&m);

     while(m--) {

         int v,d,x;

         scanf("%d%d%d",&v,&d,&x);

         q[v].push_back(mp(d,x));

     }

     dfs(,);

     for(int i = ; i <= n; i++)

         printf("%lld ",ans[i]);

     return ;

 }

F. Summer Practice Report

题意：一本书有 n 页，每页有 xi 个 0 和 yi 个 1，问存不存在每页的数字构成一个序列，连起来之后最多连续的 0 和 1 不超过 k。

题解：记录每一页组成序列之后，连续 1 和连续 0 的最小值，转移即可。因为一页中连续的 1 最多 k 个，所以可容纳的 0 的个数为 pre0 + k * x，记录这个数是否大于 0 即可判断是否合法，1 也同理。

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int MAXN = 3e5 + ;

 const int MAXM = 2e5 + ;

 const ll mod = 1e9 + ;

 ll x[MAXN],y[MAXN];

 int main() {

 #ifdef local

     freopen("data.txt", "r", stdin);

 //    freopen("data.txt", "w", stdout);

 #endif

     int n;

     ll k;

     scanf("%d%lld",&n,&k);

     for(int i = ; i <= n; i++) scanf("%lld",&x[i]);

     for(int i = ; i <= n; i++) scanf("%lld",&y[i]);

     ll nowx = -k, nowy = -k;

     for(int i = ; i <= n; i++) {

         nowx += x[i] - y[i] * k;

         nowy += y[i] - x[i] * k;

         if(nowx < -k) nowx = -k;

         if(nowy < -k) nowy = -k;

         if(nowx >  || nowy > ) {

             puts("NO");

             return ;

         }

     }

     puts("YES");

     return ;

 }

G. Array Game（待补）

题意：

题解：

码农公寓

相关文章