Codeforces Round #560 (Div. 3)A-E

先更个这两天练手速的一场吧。

A. Remainder

题意

给出一个长度为n的二进制串，若要令该串对1<<x求模后为1<<y，最少需要改动多少位

题解

水题， 0 ~ y-1位为0，y位为1，y+1 ~ x-1位为0，比较不同即可

Code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;

int main()
{
   // int t;
   // cin>>t;
   // while(t--){
      int n,x,y;
      cin>>n>>x>>y;
      string s;
      cin>>s;
      reverse(s.begin(),s.end());
      int cnt = 0;
      for(int i = 0;i < y;++i){
         if(s[i] == '1') cnt++;
      } 
      if(s[y] == '0') cnt++;
      for(int i = y+1;i < x;++i){
         if(s[i] == '1') cnt++;
      }
      printf("%d\n",cnt);
   // }


   return 0;
}

B. Polycarp Training

题意

给出n场比赛列表，每场比赛包含若干问题，第i天要解决i道问题，但是打过的比赛就不能再打了，问这些场比赛能够用来训练多久

题解

直接升序排序，找到所有a[j] >= i 的场数即可。

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;

int main()
{
   ios;
   int n;
   cin>>n;
   vector<int> a;
   a.resize(n);
   for(int i = 0;i < n;++i) cin>>a[i];
   sort(a.begin(),a.end());
   int cnt = 1;
   for(int i = 0;i < n;++i){
      if(a[i] < cnt) continue;
      cnt++; 
   }
   printf("%d\n",cnt-1);

   return 0;
}

C. Good String [贪心]

题意

定义goodstring 为对于所有奇数位置上的字符均不与其下一个字符相同，给出一个字符串，问最少删掉多少字符能使该串变为goodstring.

题解

贪心即可，当有n(n>1)个相同字符连在一起的时候，若第一个字符为奇数位，则这n个字符只能留下一个，相反，若为偶数位置，则n个字符可留下2个。
只需要在处理过程中计数，并对每段相同字符新建串即可，需要注意结果的长度不能为奇数，若为奇数直接删掉尾字符即可。

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;

int main()
{
   int n;
   cin>>n;
   string s;
   cin>>s;
   int cnt = 0;
   int suc = 1;
   string res;
   for(int i = 1;i < n;++i){
      if(s[i] == s[i-1]) suc++;
      else{
         if(suc == 1){
            res += s[i-1];
            continue;
         }
         if((i - cnt - suc) & 1) res+=s[i-1],res+=s[i-1],cnt += suc - 2;
         else res += s[i-1],cnt += suc - 1;
         suc = 1;
      }
   }
   int i = n;
   if(suc == 1){
      res += s[i-1];
   }
   else{
      if((i - cnt - suc) & 1) res+=s[i-1],res += s[i-1],cnt += suc - 2;
      else res += s[i-1],cnt += suc - 1;
   }
   if((n - cnt)&1) res.pop_back(),cnt++;
   printf("%d\n",cnt);
   cout<<res<<endl;

   return 0;

D. Almost All Divisors

题意

给出n个数，为数x除1和x外的所有因子，问能否得到这个x，能输出x不能输出-1

题解

先把因子排序，若因子是全的，则x可以用最小的数与最大的数相乘得到。接下来只需要判断所有的因子是否均是x的因子，和因子个数是否缺少即可。

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;

ll a[350];


int main()
{
   int t;
   cin>>t;
   while(t--){
      int n;
      scanf("%d",&n);
      for(int i = 0;i < n;++i){
         scanf("%lld",&a[i]);
      }
      sort(a,a+n);
      ll res = 0;
      if(n & 1) res = a[n/2] * a[n/2];
      else res = a[0] * a[n-1];
      int ok = 1;
      for(int i = 0;i < n/2;++i){
         if(a[i] * a[n-1-i] != res){
            ok = 0;
            break;
         }
      }
      if(ok){
         int cnt = 0;
         for(int i = 2;i <= sqrt(res);++i){
            if(res % i == 0){
               if(a[cnt++] != i){
                  ok = 0;
                  break;
               }
            }  
         }
      }
      if(ok) printf("%lld\n",res);
      else printf("-1\n");
   }

   return 0;
}

E. Two Arrays and Sum of Functions [数学]+[贪心]

题意

定义 $f(l, r) = \sum\limits_{l \le i \le r} a_i \cdot b_i$ ,
给出a，b序列，对b数组进行任意排序求解对于给出的l,r最小的 $\sum\limits_{1 \le l \le r \le n} f(l, r)$

题解

我们设 $f(i)$ 为 $a_{i}*b_{i}$ ,根据 $\sum\limits_{1 \le l \le r \le n} f(l, r) = \sum^{r}_{i = l} \sum^{r}_{j = i} \sum^{j}_{k = i} a_k \cdot b_k$
显而易见的是，对于每个 $f(i)$ ,所求和的次数为 $i*(n-i+1)$ 次。
所有原式可变为 $\sum^{n}_{i = 1} i \cdot(n-i+1)\cdot a_{i} \cdot b_{i}$

考虑对于两个可重排的序列a，b，如何使 $\sum^{n}_{i=1}a_{i} \cdot b_{i}$ 最小？
显然将两个序列一个升序排列一个降序排列即可。

那么回到本题，我们完全可以将 $i \cdot(n-i+1)\cdot a_{i}$ 看为一个整体，这样 $c_{i} = i \cdot(n-i+1)\cdot a_{i}$ 求解如何使 $\sum^{n}_{i=1}c_{i} \cdot b_{i}$ 最小,这就回到了刚刚最简单的贪心问题。

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 2e5 + 10;
const ll mod = 998244353;

ll a[maxn],b[maxn];
ll cnt[maxn];

int main()
{
   int n;
   cin>>n;
   for(int i = 0;i < n;++i) scanf("%lld",&a[i]);
   for(int i = 0;i < n;++i) scanf("%lld",&b[i]);
   for(int i = 1;i <= n;++i){
      cnt[i-1] = 1ll * i * (n-i+1);
   }
   for(int i = 0;i < n;++i) a[i] = a[i] * cnt[i];
   sort(a,a+n);
   sort(b,b+n);
   reverse(b,b+n);
   ll res = 0;
   for(int i = 0;i < n;++i){
      res = (res + a[i] % mod * b[i] % mod) % mod;
   }
   printf("%lld\n",res);
   return 0;
}

写完发现前几道题实在太水了写不写好像没啥意义...以后div3abc不写了好了...