Pinely Round 2 (Div. 1 + Div. 2)-526互联

简单分类讨论情况即可算下最多有多少人在线即可

void solve(){
    int n , a , q ; 
    cin >> n >> a >>q ; 
    int add = 0 , minn = 0 , maxx = 0 ; 
    cin >>in +1  ; 
    for(int i = 1 ; i <= q ; i++){
        if(in[i] == '+' )
            add++; 
        else minn++; 
        maxx = max(maxx , add - minn) ; 
    }
    if(a + add < n){
        printf("NO\n") ; 
    }
    else if(a + maxx >= n){
        printf("YES\n") ; 
    }
    else printf("MAYBE\n") ;  
}

Split Sort

如果x+1在x前面出现过了那么我一定会选一次x+1使得他们有序因此数一下这样的逆序对就行

void solve(){
    int n , ans = 0 ; 
    cin >> n ; 
    for(int i = 1; i <= n +1 ; i++)
        d[i] = 0 ; 
    for(int i = 1; i <= n ; i++){
        cin >> a[i]; 
        if(d[a[i]+1])
            ans++ ; 
        d[a[i]] = 1 ; 
    }
    printf("%d\n" , ans) ; 
}

Two-Colored Dominoes

先考虑行的要求所以横着的对行无影响只有竖着的个数为偶数才可以竖着的也同理

void solve() {
  cin >> n >> m;
  V<std::string> mp(n);
  for (auto &s : mp) cin >> s;
  V<i64> row(n), col(m);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (mp[i][j] == 'L') {
        col[j]++;
      }
      if (mp[i][j] == 'U') {
        row[i]++;
      }
    }
  }
  bool pos = true;
  for (auto &i : row) {
    if (i & 1) pos = false;
    i /= 2;
  }
  for (auto &i : col) {
    if (i & 1) pos = false;
    i /=2;
  }
  if (!pos) {
    cout << "-1\n";
    return;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (mp[i][j] == 'L') {
        if (col[j]) {
          mp[i][j] = 'W';
          mp[i][j + 1] = 'B';
          col[j]--;
        } else {
          mp[i][j] = 'B';
          mp[i][j + 1] = 'W';
        }
      }
      else if (mp[i][j] == 'U') {
        if (row[i]) {
          mp[i][j] = 'W';
          mp[i + 1][j] = 'B';
          row[i]--;
        } else {
          mp[i][j] = 'B';
          mp[i + 1][j] = 'W';
        }
      }
    }
  }
  for (auto s : mp) cout << s << "\n";
}

Speedrun

先考虑拓扑排序计算顺序然后每一个任务的执行时间其实通过拓扑中也可以很快算出来
因此一个很自然的想法就是给DAG的零入度点排序，然后按顺序枚举某个作为起始时刻，不难发现其实就是不断地把前一个起始时刻加上k的过程
考虑修改某个点的值后会影响它后面的点的值，乍一看复杂度很爆炸，但仔细一想最后至多每个数都比原来大k，因此每个点最多被松弛一次，复杂度是对的

const int N=200005;
int t,n,m,k,h[N],x,y,deg[N],f[N],mx[N],ret; vector <int> v[N];
inline int calc(CI x,CI y)
{
    int d=x/k,r=x%k; return (d+(y<r))*k+y;
}
inline void reset(CI now)
{
    if (calc(mx[now],h[now])<=f[now]) return;
    ret=max(ret,f[now]=calc(mx[now],h[now]));
    for (auto to:v[now]) mx[to]=max(mx[to],f[now]),reset(to);
}
signed main()
{
    for (scanf("%lld",&t);t;--t)
    {
        RI i; for (scanf("%lld%lld%lld",&n,&m,&k),i=1;i<=n;++i)
        mx[i]=deg[i]=0,v[i].clear(),scanf("%d",&h[i]);
        for (i=1;i<=m;++i) scanf("%lld%lld",&x,&y),v[x].push_back(y),++deg[y];
        queue <int> q; vector <pi> st;
        for (i=1;i<=n;++i) if (!deg[i]) mx[i]=h[i],q.push(i),st.push_back(pi(h[i],i));
        sort(st.begin(),st.end()); ret=0; while (!q.empty())
        {
            int now=q.front(); q.pop(); ret=max(ret,f[now]=calc(mx[now],h[now]));
            for (auto to:v[now])
            {
                mx[to]=max(mx[to],f[now]); if (!--deg[to]) q.push(to);
            }
        }
        int ans=ret-st[0].fi; for (i=0;i<st.size()-1;++i)
        mx[st[i].se]+=k,reset(st[i].se),ans=min(ans,ret-st[i+1].fi);
        printf("%lld\n",ans);
    }
    return 0;
}