A~E题个人题解

A

找大于l的第一个为x的倍数的数

#include <iostream>
using namespace std;

int main() {
  int l,r,x;
  cin>>l>>r>>x;
  cout<<((l-1)/x*x+x <= r ? (l-1)/x*x+x : -1)<<'\n';
  
  return 0;
}

B

该区间长度最长为(n-1)*x+1 最短为(n+1)*x-1
一种构造方法是先令区间长度最短 然后在左右两侧延长

#include <iostream>
using namespace std;

int main() {
  long long n,k,x;
  cin>>n>>k>>x;
  if (k > (n+1)*x-1 || k < (n-1)*x+1) {
    cout<<-1<<'\n';
    return 0;
  }
  long long l = x, r = x*n;
  k -= (n-1)*x+1;
  l -= min(x-1, k);
  if (l == 1)
    r += k-x+1;
  cout<<l<<' '<<r<<'\n';
  
  return 0;
}

C

最后一位为0时无解 因为全部n个数字一定匹配
一种构造方法是每次查找到1时 从这个下标开始倒序填充

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n, p = 0;
  string s;
  vector<int> vec;
  cin>>n>>s;
  if (s[n-1] == '0') {
    cout<<-1<<'\n';
    return 0;
  }
  while (s.find('1', p) != string::npos) {
    p = s.find('1', p) + 1;
    int q = p;
    while (vec.size() != p)
      vec.push_back(q--);
  }
  for (auto &x: vec)
    cout<<x<<' ';
  cout<<'\n';
  
  return 0;
}

D

滑动窗口
每多一个1 cnt加上区间内0的个数
每少一个0 cnt减去区间内1的个数

#include <iostream>
using namespace std;

int main() {
  int n;
  long long k;
  string s;
  cin>>n>>k>>s;
  int i = 1, j = 0;
  long long cnt = 0, c0 = 0, c1 = 0;
  while (j < n) {
    while (j < n && cnt < k)
      c0 += s[j] == '0', c1 += s[j] == '1', cnt += s[j] == '1' ? c0 : 0, j++;
    if (cnt == k) {
      cout<<i<<' '<<j<<'\n';
      return 0;
    }
    while (cnt > k)
      c0 -= s[i-1] == '0', c1 -= s[i-1] == '1', cnt -= s[i-1] == '0' ? c1 : 0, i++;
  }
  cout<<-1<<'\n';
  
  return 0;
}

E

只要能把这n个点划分为度数总和相等的两个集合 然后一一匹配 就是满足要求的一个解 因为允许重边
用大小为sum/2的01背包记录某个体积是否可达 同时用bitset记录达成的dp解 找到任意一个解即可

#include <iostream>
#include <bitset>
#include <vector>
using namespace std;

int a[105];
bitset<101> dp[5000];

int main() {
  int n, sum = 0;
  cin>>n;
  for (int i=1; i<=n; i++)
    cin>>a[i], sum += a[i];
  if (sum%2) {
    cout<<-1<<'\n';
    return 0;
  }
  int m = sum/2;
  dp[0][0] = 1;
  for (int i=1; i<=n; i++)
    for (int j=m; j>=a[i]; j--)
      if (dp[j] == 0 && dp[j-a[i]] != 0)
        dp[j] = dp[j-a[i]], dp[j][i] = 1;
  if (dp[m] == 0) {
    cout<<-1<<'\n';
    return 0;
  }
  cout<<m<<'\n';
  vector<int> v1, v2;
  for (int i=1; i<=n; i++)
    dp[m][i] ? v1.push_back(i) : v2.push_back(i);
  int i = 0, j = 0;
  while (m--) {
    cout<<v1[i]<<' '<<v2[j]<<'\n';
    a[v1[i]]--;
    if (a[v1[i]] == 0)
      i++;
    a[v2[j]]--;
    if (a[v2[j]] == 0)
      j++;
  }
  
  return 0;
}