2024 CSP-S第二轮复赛试题及参考答案

//T1.决斗#include<bits/stdc++.h>using namespace std;const int N=1e5+10;int n,a[N],l=1;signed main() {  cin>>n;  for(int i=1;i<=n;i++) scanf("%d",&a[i]);  sort(a+1,a+n+1);  for(int i=1;i<=n;i++) {    if(a[l]>=a[i]) continue ;//减不掉    l++;  }  cout<<n-l+1;  return 0;}

//T2.超速检测#include <bits/stdc++.h>using namespace std;#define double long doubleint a[100005], d[100005], v[100005], p[100005];int del[100005];
struct node {  int ql, qr;  friend bool operator<(node l, node r) {    if (l.ql != r.ql)      return l.ql < r.ql;    return l.qr > r.qr;  }} s[100005];
int main() {  ios::sync_with_stdio(false);  cin.tie(0), cout.tie(0);  int t;  cin >> t;  while (t--) {    int n, m, L, V;    cin >> n >> m >> L >> V;    for (int i = 1; i <= n; i++)      cin >> d[i] >> v[i] >> a[i];    for (int i = 1; i <= m; i++)      cin >> p[i];    int tot = 0;    for (int i = 1; i <= n; i++) {      if (a[i] <= 0 && v[i] <= V)        continue;      if (a[i] > 0) {        int wei = V * V - v[i] * v[i];        wei /= (2 * a[i]);        wei += d[i];        if (v[i] > V)          wei = d[i] - 1;        int l = 1, r = m, ans = 0;        while (l <= r) {          int mid = (l + r) / 2;          if (p[mid] > wei) {            r = mid - 1;            ans = mid;          } else            l = mid + 1;        }        if (!ans)          continue;        s[++tot].ql = ans, s[tot].qr = m;      } else {        int l = 1, r = m, pos = 0;        while (l <= r) {          int mid = (l + r) / 2;          if (p[mid] >= d[i]) {            r = mid - 1;            pos = mid;          } else            l = mid + 1;        }        if (!pos)          continue;        l = pos, r = m;        int ans = 0;        while (l <= r) {          int mid = (l + r) / 2;          double su = sqrt(v[i] * v[i] * 1.0 + 2.0 * a[i] * (p[mid] - d[i]));          if (su > V) {            l = mid + 1;            ans = mid;          } else            r = mid - 1;        }        if (ans < pos)          continue;        s[++tot].ql = pos, s[tot].qr = ans;      }    }    sort(s + 1, s + tot + 1);    int mr = 1000000000;    for (int i = tot; i >= 1; i--) {      if (mr <= s[i].qr)        del[i] = 1;      mr = min(mr, s[i].qr);    }    int ans = 0, fu = 0;    for (int i = 1; i <= tot; i++) {      //  cout << s[i].ql << " " << s[i].qr << " " << del[i] << endl;      if (del[i]) {        del[i] = 0;        continue;      }      if (fu < s[i].ql) {        ans++;        fu = s[i].qr;      }    }    cout << tot << " " << m - ans << "\n";  }}

//T3.染色#include<bits/stdc++.h>using namespace std;inline void rd(){}template<typename T,typename ...U>inline void rd(T &x,U &...args){  char ch=getchar();  T f=1;x=0;    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();  x*=f;rd(args...);}typedef long long ll;const int N=2e5+5,V=1e6+5;int T,n,a[N];ll r[V];inline void Solve(){  memset(r,-0x3f,sizeof r);  ll mxr=0,tgr=0;rd(n);  for(int i=1;i<=n;i++){    rd(a[i]);    ll tmpr=max(mxr,r[a[i]]+a[i])+tgr;    if(a[i]==a[i-1])tgr+=a[i];    r[a[i-1]]=max(r[a[i-1]],tmpr-tgr);    mxr=max(mxr,r[a[i-1]]);  }  mxr=0;  for(int i=1;i<=1000000;i++)mxr=max(mxr,r[i]);  printf("%lld\n",mxr+tgr);}signed main(){  rd(T);  while(T--)Solve();  return 0;}

//T4.擂台游戏#include <bits/stdc++.h>
using LL = long long;
const int N = 1 << 18 | 7;const int M = 18;
int n, m, t, aa[N], a[N], c[N];int b[N], r[N], id[N], lp[N], rp[N];LL sum[N], ans[N];char s[M][N];
void build() {  for(int i = 0; i < t; ++i) {    r[i + t] = 0;    id[i + t] = i;    b[i + t] = i + 1;    sum[i + t] = lp[i + t] = rp[i + t] = i + 1;  }  for(int i = t - 1; i >= 1; --i) {    r[i] = r[i << 1] + 1;    id[i] = id[i << 1] >> 1;    lp[i] = lp[i << 1];    rp[i] = rp[i << 1 | 1];    sum[i] = sum[i << 1] + sum[i << 1 | 1];    if(s[r[i]][id[i]] == '0')      b[i] = a[b[i << 1]] >= r[i] ? b[i << 1] : b[i << 1 | 1];    else      b[i] = a[b[i << 1 | 1]] >= r[i] ? b[i << 1 | 1] : b[i << 1];  }}
LL vt[N], st;int rd;void dfs(int i, LL ss, int zl) {  if(i >= t) {    ans[i - t] = st + ss + lp[i];    return ;  }  LL trd = rd, tst = st;  if(s[r[i]][id[i]] == '0') {    if(b[i] == b[i << 1]) {      LL v = a[b[i]] >= rd ? b[i] : a[b[i]] + 1 >= zl ? 0 : vt[a[b[i]] + 1];      std::fill(ans + lp[i << 1 | 1] - 1, ans + rp[i << 1 | 1], v + ss);    }    else {      vt[r[i]] = vt[r[i] + 1];      dfs(i << 1 | 1, ss, zl);    }    rd = trd, st = tst;    rd = std::max(rd, r[i]);    st += sum[i << 1 | 1];    vt[r[i]] = st;    dfs(i << 1, ss, zl);  }  else {    vt[r[i]] = 0;    st = 0;    dfs(i << 1, ss + sum[i << 1 | 1] + tst, r[i]);    st = tst, rd = trd;    if(a[b[i << 1]] >= rd) {      rd = std::max(rd, r[i]);      vt[r[i]] = b[i << 1];      st += b[i << 1];      dfs(i << 1 | 1, ss, zl);    }    else {      int tp = std::max(r[i], a[b[i << 1]]) + 1;      vt[r[i]] = tp >= zl ? 0 : vt[tp];      dfs(i << 1 | 1, ss, zl);    }  }  vt[r[i]] = 0;  rd = trd, st = tst;} void solve() {  build();  for(int i = 1; i < t; i <<= 1)    if(s[r[i]][id[i]] == '0')      if(b[i] == b[i << 1])    std::fill(ans + lp[i << 1 | 1] - 1, ans + rp[i << 1 | 1], b[i]);      else {        vt[r[i]] = 0;        rd = st = 0;        dfs(i << 1 | 1, 0, 20);      }    else {      rd = r[i];      st = vt[r[i]] = b[i << 1];      dfs(i << 1 | 1, 0, 20);    }  LL val = 0;  for(int i = 1, x; i <= m; ++i) {    for(x = 0; (1 << x) < c[i]; ++x) ;    LL v = (1 << x) == c[i] ? b[t / c[i]] : ans[c[i]];    //printf("%lld ", v);    val ^= i * v;  }  printf("%lld\n", val);}
int main() {
  freopen("arena.in", "r", stdin);  freopen("arena.out", "w", stdout);      scanf("%d%d", &n, &m);  for(int i = 1; i <= n; ++i)    scanf("%d", &aa[i]);  for(int i = 1; i <= m; ++i)    scanf("%d", &c[i]);  for(t = n; t & (t - 1); t += t & -t) ;  for(int i = 1; (1 << i) <= t; ++i)    scanf("%s", s[i]);    int cases;  scanf("%d", &cases);
  while(cases--) {    int x[4];    scanf("%d%d%d%d", &x[0], &x[1], &x[2], &x[3]);    for(int i = 1; i <= n; ++i)      a[i] = aa[i] ^ x[i & 3];    solve();  }    return 0;
}