Educational Codeforces Round 81 (Rated for Div. 2) A-E简要题解

链接:https://codeforces.com/contest/1295

A. Display The Number

贪心思路，尽可能放置更多位，如果n为奇数，消耗3去放置一个7，剩下的放1

AC代码:

 #include<bits/stdc++.h>

 #define inf 0x3f3f3f3f

 using namespace std;

 int n,m;

 int main(){

     int t;

     cin>>t;

     while(t--){

         int n;

         cin>>n;

         string ans = "";

         if(n% == ) ans.append(,''),ans.append((n-)/,'');

         else ans.append(n/,'');

         cout<<ans<<endl;

     }

     return ;

 }

B. Infinite Prefixes

前缀和思路，存字符串前n个位置的前缀和，如果cnt0+cnt1 = 0，且 x 在前缀和中出现过，那么就是无限的。

其他情况扫一遍字符串的前缀和，然后与x的差值和f[n]取余，如果为0，说明差值可以用任意个字符串的cnt0-cnt1拼接起来，ans就++

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int main(){

     int t;

     cin>>t;

     while(t--){

         int n,x;

         cin>>n>>x;

         string s;

         cin>>s;

         int f[n+];

         f[] = ;

         int can = ;

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

             if(f[i] == x) can = ;

             if(s[i] == '') f[i+] = f[i]-;

             else f[i+] = f[i] + ;

         }

         if(f[n] == x) can = ;

         if(can ==  && f[n] == ) {

             cout<<-<<endl;

             continue;

         }

         int ans = ;

         ll d = f[n];

     //    cout<<d<<endl;

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

             if(f[i] == x) ans++;

             if(i!= && f[i]<x && d> &&(x-f[i])%d==) ans++;

             if(i!= && f[i]>x && d< &&(f[i]-x)%(-d)==) ans++;

         }

         cout<<ans<<endl;

     }

     return ;

 }

C. Obtain The String

贪心思路，用一个next二维数组存储当前位置i 下一个26个字母的距离最近的位置，然后按需求跳转过去，如果找不到，那么需要的字串数量就+1，再从头开始扫描原串。

 #include<bits/stdc++.h>

 typedef long long ll;

 using namespace std;

 const int maxn = 1e5+;

 int main()

 {

     int n;

     cin>>n;

     while(n--){

         string s,t;

         cin>>s>>t;

         int next[s.length()+][];

         for(int i = ;i<;i++) next[s.length()][i] = -;

         for(int i = s.length()-;i>=;i--){

             for(int j = ;j<;j++) next[i][j] = next[i+][j];//存储i后面，26个字母距离i最近的位置

             int cur = s[i]-'a';

             next[i][cur] = i+;

         }

         int ans = ;

         int cur = ;

         bool f = true;

         for(int i = ;i<t.length();i++){

             int now = t[i]-'a';

             if(next[cur][now]!=-) cur = next[cur][now];//跳转过去

             else{

                 ans++;//如果找不的ans就++

                 cur = ;

                 if(next[cur][now] == -){//如果还没有，说明无法拼接起来

                     f = false;

                     break;

                 }

                 cur = next[cur][now];

             }

         }

         if(!f) cout<<-<<endl;

         else cout<<ans<<endl;

     }

     return ;

 }

D. Same GCDs

设gcd（a，m）= n，那么找gcd（a +x ，m）= n个数，其实就等于找gcd（（a+x）/n，m/n) = 1的个数，等价于求m/n的欧拉函数

 #include<bits/stdc++.h>

 typedef long long ll;

 using namespace std;

 ll euler_phi(ll n) {

   ll m = ll(sqrt(n + 0.5));

   ll ans = n;

   for (ll i = ; i <= m; i++)

     if (n % i == ) {

       ans = ans / i * (i - );

       while (n % i == ) n /= i;

     }

   if (n > ) ans = ans / n * (n - );

   return ans;

 }

 ll gcd(ll a, ll b) {

   if (b == ) return a;

   return gcd(b, a % b);

 }

 int main()

 {

     int t;

     cin>>t;

     while(t--){

         ll a,m;

         cin>>a>>m;

         m=m/gcd(a,m);

         ll x = euler_phi(m);

         cout<<x<<endl;

     }

     return ;

 }

E. Permutation Separation

建一颗线段树，叶子结点是花费从1到i所需要花费的前缀和，表示前i个元素全部移动到右边的花费，再维护区间最小值，然后从1到n-1扫一遍，对于第i个位置，找到数字i在序列中的位置 pos ，将区间1到pos-1加上数字i移动的花费，pos到n-1减去数字i移动的花费，因为位置大于等于i 的时候，不需要将数字i移动到右边，位置小于i 时，需要把数字i移动到左边，所以需要增加数字i的花费，结合线段树维护的是前缀和数组，那么对于每一个位置i 用线段树维护的最小值去更新答案ans即可。

 #include<bits/stdc++.h>

 typedef long long ll;

 using namespace std;

 const int maxn = 2e5+;

 ll pos[maxn],cost[maxn],a[maxn],sum[maxn];

 struct segT{

     ll l,r;

     ll dat,lz;

 }t[maxn*];

 void build(ll p,ll l,ll r){

     t[p].l = l,t[p].r = r;

     if(l == r) { t[p].dat = sum[l] ,t[p].lz = ;return;}

     ll mid = (l+r)/;

     build(p*,l,mid);

     build(p*+,mid+,r);

     t[p].dat = min(t[p*].dat ,t[p*+].dat );

 }

 void upd(ll p,ll L,ll R,ll v){

     if(t[p].l >= L&&t[p].r <= R ) {t[p].dat += v,t[p].lz +=v;return;}

     if (t[p].lz && L!=R ) {

     t[p * ].dat += t[p].lz ,t[p*+].dat +=t[p].lz  ;

     t[p * ].lz  += t[p].lz ,t[p*+].lz += t[p].lz;

     t[p].lz = ;

     }

     int mid = (t[p].l + t[p].r )/;

     if(L<=mid) upd(p*,L,R,v);

     if(R>mid) upd(p*+,L,R,v);

     t[p].dat = min(t[p*].dat ,t[p*+].dat );

 }

 int query(ll p,ll l,ll r){

     if(l<=t[p].l && r>=t[p].r ) return t[p].dat ;

     int mid = (t[p].l + t[p].r )/;

     int val = 0x3f3f3f3f;

     if(l<=mid) val = min(val,query(p*,l,r));

     if(r>mid)  val = min(val,query(p*+,l,r));

     return val;

 }

 int main()

 {

     int n;

     scanf("%d",&n);

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

         scanf("%lld",&a[i]);

         pos[a[i]] = i;

     }

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

         scanf("%lld",&cost[i]);

         sum[i] = sum[i-] + cost[i];

     }

     build(,,n-);

     ll ans = cost[n];

     ans = min(ans,t[].dat );//特判

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

         if(pos[i]!=n) upd(,pos[i],n-,-cost[pos[i]]);

         if(pos[i]!=) upd(,,pos[i]-,cost[pos[i]]);

         ans = min(ans,t[].dat);

     }

     printf("%lld",ans);

     return ;

 }

巴特西

Educational Codeforces Round 81 (Rated for Div. 2) A-E简要题解

最新文章

热门文章