2023NOIP 试题及参考答案分享

//T1.词典#include <bits/stdc++.h>using namespace std;#define int long long#define MAXN 3001
int n, m;string s;string str[MAXN], str2[MAXN];bitset<MAXN> vis;bitset<MAXN> f[MAXN][27];
signed main(){//  freopen("dict.in", "r", stdin);//  freopen("dict.out", "w", stdout);    ios::sync_with_stdio(false);  cin.tie(0);  cout.tie(0);    cin >> n >> m;  for (int i(0); i<n; ++i){    cin >> s;    sort(s.begin(), s.end());    str[i] = s;    reverse(s.begin(), s.end());    str2[i] = s;  }  for (int i(0); i<m; ++i){    for (int j(0); j<27; ++j){      for (int k(0); k<n; ++k) f[i][j].set(k);    }  }  for (int i(0); i<n; ++i){    for (int j(0); j<m; ++j) f[j][str2[i][j]-'a'].reset(i);  }  for (int i(0); i<m; ++i){    for (int j(25); j>=0; --j) f[i][j] &= f[i][j+1];  }    for (int i(0); i<n; ++i){    vis.set();    for (int j(0); j<m; ++j) vis &= f[j][str[i][j]-'a'+1];    cout << ((str[i] == str2[i] && vis.count() == 1) || vis.count() == 0);  }    return 0;}

//T2.三值逻辑#include<bits/stdc++.h>using namespace std;int fl[200005],val[200005];int n,m;int in[200005],out[200005],ans[200005],vis[200005],pp[200005],ss[200005],fa[200005],used[200005];int sz[200005];vector<pair<int,int> >p[200005],p1[200005];int find(int x){    if(fa[x] == x)return x;    return fa[x] = find(fa[x]);}void merge(int x,int y){    int a = find(x),b = find(y);    if(b == a)return;    fa[b] = a;sz[a]+=sz[b];sz[b] = 0;}void dfs(int now,int val){vis[now] = 1;    ans[now] = val;    for(int i =0;i<p1[now].size();i++){        dfs(p1[now][i].first,p1[now][i].second*val);    }return;}int pro = 1,ok = 0;void dfs1(int now){    if(vis[now] == 1){        if(pp[now]!=pro)ok = 1;        return;    }vis[now] =1;pp[now] = pro;    for(int i =0;i<p[now].size();i++){        pro = pro*p[now][i].second;        dfs1(p[now][i].first);    }}void solve(){    cin >> n >> m;    for(int i =1;i<=n;i++)fl[i] = 1,val[i] = i,in[i] = 0,out[i] = 0,ans[i] = -2,vis[i] = 0,ss[i] = 0,sz[i] = 1;    for(int i =1;i<=n;i++)fa[i] = i,used[i] = 0;    for(int i = 1;i<=n;i++)p[i].clear(),p1[i].clear();    for(int i =1;i<=m;i++){        char c;cin >> c;        if(c == '-'){            int x,y;cin >> x >> y;            if(fl[y] == 0){                fl[x] = 0;val[x] = -val[y];            }else{                fl[x] = -fl[y],val[x] = val[y];            }        }if(c == '+'){            int x,y;cin >> x >> y;            val[x] = val[y],fl[x] = fl[y];        }if(c == 'T'){            int x;cin >> x;            fl[x] = 0,val[x] = 1;        }if(c == 'F'){            int x;cin >> x;            fl[x] = 0,val[x] = -1;        }if(c == 'U'){            int x;cin >> x;            fl[x]  =0,val[x] = 0;        }    }for(int i = 1;i<=n;i++){        if(fl[i]!=0){            p1[val[i]].push_back({i,fl[i]});            p[i].push_back({val[i],fl[i]});merge(val[i],i);        }    }for(int i = 1;i<=n;i++){        if(fl[i] == 0){                used[find(i)] = 1;            dfs(i,val[i]);        }    }int tot = 0;    for(int i= 1;i<=n;i++){        if(!used[find(i)]){used[find(i)] = 1;            pro =  1,ok = 0;            dfs1(i);            tot+=ok*sz[find(i)];        }    }    for(int i = 1;i<=n;i++)if(ans[i] == 0)tot++;    cout << tot << endl;}int id;signed main(){ //   freopen("tribool.in","r",stdin); //   freopen("tribool.out","w",stdout);    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);    cin >> id;    int t;cin >> t;    while(t--){        solve();    }    return 0;}

//T3.双序列拓展#include <iostream>#include <cstdio>#include <cassert>using namespace std;const int N = 5e5 + 5;int f[N], g[N]; struct Node {int min, max; Node(int ge = 0, int fe = 0): min(ge), max(fe){}} preX[N], preY[N], sufX[N], sufY[N];#define update(T, p) (Node){T[i] < T[p.min] ? i : p.min, T[i] > T[p.max] ? i : p.max};bool check1(int x, int y, int n, int m) //左上区域{  if (x == 1 || y == 1) return true;  Node X = preX[x - 1], Y = preY[y - 1];  if (f[X.min] < g[Y.min]) return check1(X.min, y, n, m);  if (g[Y.max] > f[X.max]) return check1(x, Y.max, n, m);  return false;}bool check2(int x, int y, int n, int m) //右下区域，同左上区域{  if (x == n || y == m) return true;  Node X = sufX[x + 1], Y = sufY[y + 1];  if (f[X.min] < g[Y.min]) return check2(X.min, y, n, m);  if (g[Y.max] > f[X.max]) return check2(x, Y.max, n, m);  return false;}bool solve(int tmpf[], int tmpg[], int n, int m){  if (tmpf[1] >= tmpg[1]) return false; //一个特判  for (int i = 1; i <= n; i++) f[i] = tmpf[i]; //copy 一下，方便在全局定义函数  for (int i = 1; i <= m; i++) g[i] = tmpg[i];
    //这里求出 X,Y 的前后缀 最大/最小值 的位置，为了让代码更优美，使用了 update()  for (int i = 1; i <= n; i++) preX[i] = (i == 1) ? (Node){1, 1} : update(f, preX[i - 1]);  for (int i = 1; i <= m; i++) preY[i] = (i == 1) ? (Node){1, 1} : update(g, preY[i - 1]);  for (int i = n; i >= 1; i--) sufX[i] = (i == n) ? (Node){n, n} : update(f, sufX[i + 1]);  for (int i = m; i >= 1; i--) sufY[i] = (i == m) ? (Node){m, m} : update(g, sufY[i + 1]);
  Node X = preX[n], Y = preY[m]; //找出两条红线的位置  if (f[X.min] >= g[Y.min] || g[Y.max] <= f[X.max]) return false; //一个特判  return check1(X.min, Y.max, n, m) && check2(X.min, Y.max, n, m); //分左上右下递归即可}int tx[N], ty[N], ttx[N], tty[N];int main(){  int n, m, q;  scanf("%*d%d%d%d", &n, &m, &q);  for (int i = 1; i <= n; i++) scanf("%d", &tx[i]);  for (int i = 1; i <= m; i++) scanf("%d", &ty[i]);  putchar(solve(tx, ty, n, m) || solve(ty, tx, m, n) ? '1' : '0');  while (q--)  {    for (int i = 1; i <= n; i++) ttx[i] = tx[i];    for (int i = 1; i <= m; i++) tty[i] = ty[i];    int cx, cy;    scanf("%d%d", &cx, &cy);    while (cx--) {int p, v; scanf("%d%d", &p, &v); ttx[p] = v;}    while (cy--) {int p, v; scanf("%d%d", &p, &v); tty[p] = v;}    putchar(solve(ttx, tty, n, m) || solve(tty, ttx, m, n) ? '1' : '0');  }  return 0;}

//T4.天天爱打卡#include <algorithm>#include <iostream>
using namespace std;using LL = long long;
const int kM = 1e5 + 1, kN = kM * 2;
struct C {  int l, r, v;
  bool operator<(const C &o) const { return r < o.r; }} a[kM];struct E {  LL mx, ta;} e[kN << 2];int cid, tt;int n, m, k, v, b[kN];LL d, f[kN];
void Pu(int x) { e[x].mx = max(e[x * 2].mx, e[x * 2 + 1].mx); }void Pa(int x, LL v) { e[x].mx += v, e[x].ta += v; }void Pd(int x) { Pa(x * 2, e[x].ta), Pa(x * 2 + 1, e[x].ta), e[x].ta = 0; }void B(int x, int l, int r) {  e[x].ta = 0;  if (l == r) {    e[x].mx = (l ? -1e18 : 0);    return;  }  int m = l + r >> 1;  B(x * 2, l, m), B(x * 2 + 1, m + 1, r);  Pu(x);}void U(int x, int l, int r, int t, LL v) {  if (l == r) {    e[x].mx = v;    return;  }  Pd(x);  int m = l + r >> 1;  if (t <= m) {    U(x * 2, l, m, t, v);  } else {    U(x * 2 + 1, m + 1, r, t, v);  }  Pu(x);}void A(int x, int l, int r, int tl, int tr, LL v) {  if (l == tl && r == tr) {    Pa(x, v);    return;  }  Pd(x);  int m = l + r >> 1;  if (tl <= m) {    A(x * 2, l, m, tl, min(m, tr), v);  }  if (m < tr) {    A(x * 2 + 1, m + 1, r, max(m + 1, tl), tr, v);  }  Pu(x);}LL Q(int x, int l, int r, int tl, int tr) {  if (l == tl && r == tr) {    return e[x].mx;  }  Pd(x);  int m = l + r >> 1;  LL s = -1e18;  if (tl <= m) {    s = max(s, Q(x * 2, l, m, tl, min(m, tr)));  }  if (m < tr) {    s = max(s, Q(x * 2 + 1, m + 1, r, max(m + 1, tl), tr));  }  return s;}
int main() {  ios::sync_with_stdio(0), cin.tie(0);  for (cin >> cid >> tt; tt--;) {    cin >> n >> m >> k >> d;    v = 0;    for (int i = 1; i <= m; ++i) {      cin >> a[i].r >> a[i].l >> a[i].v;      a[i].l = a[i].r - a[i].l;      b[++v] = a[i].l, b[++v] = a[i].r;    }    sort(b + 1, b + v + 1);    v = unique(b + 1, b + v + 1) - b - 1;    for (int i = 1; i <= m; ++i) {      a[i].l = lower_bound(b + 1, b + v + 1, a[i].l) - b;      a[i].r = lower_bound(b + 1, b + v + 1, a[i].r) - b;    }    sort(a + 1, a + m + 1);    B(1, 0, v);    LL pm = 0;    for (int i = 1, j = 1, u = 0; i <= v; ++i) {      U(1, 0, v, i, pm + d * b[i]);      for (; j <= m && a[j].r == i; ++j) {        A(1, 0, v, 0, a[j].l, a[j].v);      }      for (; u < i && b[u] < b[i] - k; ++u) {      }      if (u < i) {        f[i] = Q(1, 0, v, u, i - 1) - d * b[i];      } else {        f[i] = -1e18;      }      pm = max(pm, f[i]);    }    cout << pm << '\n';  }  return 0;}