Codeforces Round #564(div2)

本来以为是送分场,结果成了送命场.

菜是原罪

A

SB题,上来读不懂题就交WA了一发,代码就不粘了

B

简单构造

很明显,\(n*n\)的矩阵可以按照这个顺序排列

然后根据\(n\)的大小搞一搞就好了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define LL long long#define pii pair
          
           #define mk make_pairusing namespace std;const int N = 1e5 + 3;inline int read(){ int v = 0,c = 1;char ch = getchar(); while(!isdigit(ch)){ if(ch == '-') c = -1; ch = getchar(); } while(isdigit(ch)){ v = v * 10 + ch - 48; ch = getchar(); } return v * c;}int n,m;int aa[N];int main(){ n = read(); aa[1] = 1; for(int i = 1;i <= 10000;++i) aa[i] = 2 * i - 1; int now = 1; while(aa[now] < n) now++; printf("%d\n",now); for(int i = 1;i <= now;++i) printf("1 %d\n",i); int cc = 2; for(int i = now + 1;i <= n;++i) printf("%d %d\n",cc,now),cc++; return 0;}
          
         
        
       
      
     
    

C

送命题,卡了一个多小时,非常思维的一道题目

首先,答案肯定不会超过\(2*n\)，最坏情况我们将非空白牌都攒在手上然后一张一张打出

我们有两种策略

1:直接将手中的牌打出,这时需要满足队尾的一个\(1\)开头的连续字段的结尾的下一张牌在我们的手中,后者我们可以通过上一次摸到.所以如果队尾有连续子段,那么我们就判一下能否直接插入,若果可以，显然这是最优解

2:当队尾不符合上述条件,或者我们没办法接上连续字段时,我们就要一直攒牌,在某一时刻依次打出

我们设\(p_i\)表示\(i\)号牌在队列中的位置(不在队列视为\(0\)),接着,若果我们在\(p_i\)成为队头的时刻(设为\(t\))打出

首先需要满足\(\max_{i = t}^npi - (i - 1) == p_i-(i - 1)\)

\(p_i-(i - 1)\)是最难理解的地方.

我理解为我们插入了\(i - 1\)次时,还有要几步才可以将\(i\)给搞出来(此时我们已经默认我们有了\(1—i - 1\))

也就是说,我确保手里有\(1—i - 1\)并且至少再插完\(i - 1\)之前摸到\(i\)必须再插入\(p_i-(i - 1)\)次,因为我的手中有\(1—i- 1\),这个是不算贡献的(或者重叠部分只算一次)

但是如果这时我们手中没有\(i - 1\)该怎么办？

没关系,如果出现上述情况\(p_{i - 1}\)一定在\(p_i\)后面,我们取得是最大值,\(p_{i + 1}\)的贡献显然要大

所以答案就是\(n + max_{i =1}^np_i-i+1\)

#include
    
     #include
     
      #include
      
       using namespace std;const int N = 2e5 + 3;int p[N];int a[N];int b[N];int book[N];int n;inline bool check(){    for(int i = 1;i <=  n;++i) if(book[i] == 0) return false;    return true;    }int main(){    scanf("%d",&n);    for(int i = 1;i <= n;++i) scanf("%d",&a[i]),book[a[i]] = 1;    for(int i = 1;i <= n;++i) scanf("%d",&b[i]),p[b[i]] = i;//  bool flag = 0;    int now = n;    while(now >= 2 && b[now - 1] != 0 && b[now - 1] == b[now] - 1) now--;//  cout << now << endl;    int t = 1;    if(b[now] == 1){        for(int i = 1;i <= b[n];++i) book[i] = 1;        for(int i = b[n] + 1;i <= n;++i){            if(!book[i]){break;}            book[b[t]] = 1;            t++;        //  cout << t << endl;        }        if(check()){            printf("%d\n",now - 1);            return 0;           }    }//  cout << flag << endl;//  cout << t << endl;    //  cout << "GG";        int ans = 0;        for(int i = 1;i <= n;++i)            ans = max(ans,p[i] - i + 1);        printf("%d\n",ans + n);    return 0;   }
      
     
    

D

首先，我们发现每一颗子树一定是连续的一段圆弧,所以每一颗子树互不影响,那么我们考虑\(DP\)求贡献

我们固定跟,设\(f_i\)表示以\(i\)为跟时的答案

\(f_i = (son_i + [i !=root])!\prod_{j\in son_i}f_j\)

\(ans = nf_{root}\)

为什么呢

想一下,由于每颗子树是互不影响的所以总答案一定和子树答案的乘积有关，又因为他们的相对顺序没有限制

所以和儿子数量的阶乘有关系,但是当前父节点不为跟时,也要参与排列.

而跟有\(n\)个位置可以放

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define LL long long#define pii pair
            
             #define mk make_pairusing namespace std;const int N = 3e5 + 3;const LL mod = 998244353;vector 
             
               G[N];LL ans = 0;int son[N];LL dp[N];LL inv[N];inline int read(){ int v = 0,c = 1;char ch = getchar(); while(!isdigit(ch)){ if(ch == '-') c = -1; ch = getchar(); } while(isdigit(ch)){ v = v * 10 + ch - 48; ch = getchar(); } return v * c;}int n;inline void dfs(int x,int f){ dp[x] = 1; for(int i = 0;i < (int)G[x].size();++i){ int y = G[x][i]; if(y == f) continue; dfs(y,x); son[x]++; } int w = (x != 1) ? son[x] + 1: son[x]; for(int i = 0;i < (int)G[x].size();++i){ int y = G[x][i]; if(y == f) continue; dp[x] = dp[x] * dp[y] % mod; } dp[x] = dp[x] * inv[w] % mod;}int main(){ inv[0] = 1; n = read();for(int i = 1;i <= n;++i) inv[i] = inv[i - 1] * i % mod; for(int i = 1;i < n;++i){ int x = read(),y = read(); G[x].push_back(y); G[y].push_back(x); } dfs(1,0); printf("%I64d\n",dp[1] * n % mod); return 0;}
             
            
           
          
         
        
       
      
     
    

E

题目大意:给你\(n\)件物品,每件物品有其价值,以及是否喜欢,每次有\(\frac{w_i}{\sum{w_i}}\)的几率选择\(i\)

如果\(i\)是他喜欢的,就把他的价值\(+1\),否则如果是他不喜欢的就把他\(-1\)，但价值最小为\(0\).

求操作\(m\)次后每个物品的价值的期望

这道题,我们可以把喜欢的和不喜欢的综合起来看成两个物品

感性理解一下,就是喜欢的物品之间的价值比无论选择多少次期望是不变的.

同理不喜欢的物品之间期望的相对的价值比也是不会变的.

我们设\(f_{i,j}\)表示选择了\(i\)次,有\(j\)次选择了喜欢的概率.

我们设\(sum_1\)表示喜欢的物品的价值之和

\(sum_2\)表示不喜欢的物品的价值之和

很明显

\(f_{i + 1,j + 1} = f_{i,j} * (sum_1 + j ) / (sum_1+sum_2+j - (i - j))\)

\(f_{i + 1,j} = f_{i,j}*(sum_2-(i - j))/(sum1 + sum2 + j - (i - j))\)

之后我们设\(r_1\)表示操作完之后喜欢的物品的期望价值之和

设\(r_2\)表示不喜欢的物品的期望价值之和

则有

\(r_1 = \sum_{i = 0}^m{f_{m,i}*(sum_1+i)}\)

\(r_2=\sum_{i = 0}^mf_{m,i}*(sum_2-(m - i))\)

最终根据本来占比直接乘回去就好了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
           #define LL long longusing namespace std;const LL mod = 998244353;const int N = 5e3 + 3;const int M = 5e5 + 3;LL f[N][N]; int n,m;LL ans[M];int a[M],w[M];LL sum1,sum2;inline LL quick(LL x,LL y){ if(x < 0) return 0; LL res = 1; while(y){ if(y & 1) res = res * x % mod; x = x * x % mod; y >>= 1; } return res;}int main(){ scanf("%d%d",&n,&m); for(int i = 1;i <= n;++i) scanf("%d",&a[i]); for(int i = 1;i <= n;++i){ scanf("%d",&w[i]); if(a[i] == 1) sum1 += w[i]; else sum2 += w[i]; } f[1][1] = sum1 * quick(sum1 + sum2,mod - 2) % mod; f[1][0] = sum2 * quick(sum1 + sum2,mod - 2) % mod; for(int i = 1;i < m;++i){ for(int j = 0;j <= i;++j){ int g = i - j; f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j] * (sum1 + j) % mod * quick(sum1 + sum2 + j - g,mod - 2)) % mod; f[i + 1][j] = (f[i + 1][j] + f[i][j] * max(0ll,sum2 - g) % mod * quick(sum1 + sum2 + j - g,mod - 2)) % mod; } } //for(int i = 1;i <) //for(int i = 0;i <= m;++i){ LL r1 = 0,r2 = 0; for(int i = 0;i <= m;++i){ r1 = (r1 + f[m][i] * (sum1 + i)) % mod; r2 = (r2 + f[m][i] * (max(0ll,sum2 - m + i))) % mod; } for(int i = 1;i <= n;++i){ if(a[i] == 1) ans[i] = r1 * w[i] % mod * quick(sum1,mod - 2) % mod; else ans[i] = r2 * w[i] % mod * quick(sum2,mod - 2) % mod; printf("%I64d\n",ans[i]); } //} return 0; }