Pinely Round 2 (Div. 1 + Div. 2)

标签：int Pinely cin pos ++ mp Div Round

Channel

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

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;
}

 

 

标签：int,Pinely,cin,pos,++,mp,Div,Round
From： https://www.cnblogs.com/Vellichor/p/17674824.html