BZOJ1000-1099板刷计划+一句话题解 73/100

1000-1009

1000A+B Problem

这个还要写???

1001 狼抓兔子

平面图最小割转化为对偶图最短路

 #include<bits/stdc++.h>
 #define id(i , j , k) ((k) * (N - 1) * (M - 1) + ((i) - 1) * (M - 1) + (j))
 #define PII pair < int , int >
 #define st first
 #define nd second
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c) && c != EOF)
         c = getchar();
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return a;
 }

 ;
 struct Edge{
     int end , upEd , w;
 }Ed[MAXN << ];
 int head[MAXN] , dis[MAXN] , N , M , S , T , cntEd;
 priority_queue < PII > q;

 inline void addEd(int a , int b , int c){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     Ed[cntEd].w = c;
     head[a] = cntEd;
 }

 void input(){
     N = read();
     M = read();
     T = id(N -  , M -  , ) + ;
     int k;
      || N == ){
         int lMin = 0x7fffffff;
          ; i < max(N , M) ; ++i)
             lMin = min(lMin , read());
         cout << lMin;
         exit();
     }
      ; i <= N ; ++i)
          ; j < M ; ++j){
             k = read();
             )
                 addEd(S , id(i , j , ) , k);
             else
                 if(i == N)
                     addEd(id(i -  , j , ) , T , k);
                 else{
                     addEd(id(i -  , j , ) , id(i , j , ) , k);
                     addEd(id(i , j , ) , id(i -  , j , ) , k);
                 }
         }
      ; i < N ; ++i)
          ; j <= M ; ++j){
             k = read();
             )
                 addEd(id(i , j , ) , T , k);
             else
                 if(j == M)
                     addEd(S , id(i , j -  , ) , k);
                 else{
                     addEd(id(i , j , ) , id(i , j -  , ) , k);
                     addEd(id(i , j -  , ) , id(i , j , ) , k);
                 }
         }
      ; i < N ; ++i)
          ; j < M ; ++j){
             k = read();
             addEd(id(i , j , ) , id(i , j , ) , k);
             addEd(id(i , j , ) , id(i , j , ) , k);
         }
 }

 void Dijk(){
     memset(dis , 0x3f , sizeof(dis));
     dis[S] = ;
     q.push(PII( , S));
     while(!q.empty()){
         PII t = q.top();
         q.pop();
         if(-t.st > dis[t.nd])
             continue;
         if(t.nd == T)
             return;
         for(int i = head[t.nd] ; i ; i = Ed[i].upEd)
             if(dis[Ed[i].end] > dis[t.nd] + Ed[i].w){
                 dis[Ed[i].end] = dis[t.nd] + Ed[i].w;
                 q.push(PII(-dis[Ed[i].end] , Ed[i].end));
             }
     }
 }

 void work(){
     Dijk();
     cout << dis[T];
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     input();
     work();
     ;
 }

1001 狼抓兔子

1002 轮状病毒

虽然下面的代码是瞪眼写法,但是这里写一个正经的DP写法

设$f_i$为周围有$i$个点时的方案数。考虑断环成链,强制令第$1$个点与第$i$个点不连通,考虑枚举第$1$个点所在联通块的大小,可以得到状态转移方程:$f_i = \sum\limits_{j = 1}^{i} f_{i-j} \times j$,后面的乘$j$表示中心点有$j$种向这个联通块加边的方式。然后考虑$1$与$n$相连的情况,同样考虑$1$和$n$所在联通块的大小。如果联通块大小为$j$,则有$j-1$种方式使得$1$与$n$是相连的,那么就会有$f_i=\sum\limits_{j = 1}^{i} f_{i-j} \times j+\sum\limits_{j = 2}^{i} f_{i-j} \times j \times (j-1)$

至于下面Code,它表示点为$N$时答案是第一项为$1$、第二项为$3$,递推式为Fibonacci递推式的第$N$项的答案的平方,如果N为偶数,则答案-4。

 #include<bits/stdc++.h>
 using namespace std;

 struct BN{
     ];
     BN(){
         memset(arr ,  , sizeof(arr));
     }
     void operator =(int x){
         arr[] = ;
         while(x){
             arr[++arr[]] = x % ;
             x /= ;
         }
     }
     int& operator [](int x){
         return arr[x];
     }
     inline void output(){
         ] ; i ; i--)
             putchar(arr[i] + );
     }

     BN operator +(BN b){
         BN c;
         c[] = max(arr[] , b[]);
          ; i <= c[] ; i++)
             ){
                 c[i + ]++;
                 c[i] -= ;
             }
         ] + ])
             c[]++;
         return c;
     }

     BN operator *(BN b){
         BN c;
         c[] = arr[] + b[] - ;
          ; i <= arr[] ; i++)
              ; j <= b[] ; j++)
                 c[i + j - ] += arr[i] * b[j];
          ; i <= c[] ; i++)
             ){
                 c[i + ] += c[i] / ;
                 c[i] %= ;
                 ])
                     c[]++;
             }
         return c;
     }
 }ans[];

 int main(){
     int N;
     cin >> N;
     ans[] = ;
     ans[] = ;
      ; i <= N ; i++)
         ans[i] = ans[i - ] + ans[i - ];
     ans[N] = ans[N] * ans[N];
      == )
         ] -= ) < ){
             ans[N][] += ;
             ans[N][]--;
             ]])
                 ans[N][]--;
         }
     ans[N].output();
     ;
 }

1002 轮状病毒 瞪眼法

1003 物流运输

因为数据范围很小,故考虑预处理每段时间内不改变航线的情况下的最短路,然后直接DP枚举更换最短路的点即可

 #include<bits/stdc++.h>
 #define int long long
 #define inf 0x3f3f3f3f3f3f3f3fll
 using namespace std;

 struct Edge{
     int end , upEd , len;
 }Ed[];
 ] , minDis[] , minR[][] , dp[] , N , M , K , E , cntEd;
 ] , no[][];
 queue < int > q;

 inline void addEd(int a , int b , int c){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     Ed[cntEd].len = c;
     head[a] = cntEd;
 }

 inline int SPFA(){
     memset(minDis , 0x3f , sizeof(minDis));
     minDis[] = ;
     q.push();
     while(!q.empty()){
         int t = q.front();
         q.pop();
         for(int i = head[t] ; i ; i = Ed[i].upEd)
             if(!cannot[Ed[i].end] && minDis[Ed[i].end] > minDis[t] + Ed[i].len){
                 minDis[Ed[i].end] = minDis[t] + Ed[i].len;
                 q.push(Ed[i].end);
             }
     }
     return minDis[M];
 }

 main(){
     cin >> N >> M >> K >> E;
      ; i <= E ; i++){
         int a , b , c;
         cin >> a >> b >> c;
         addEd(a , b , c);
         addEd(b , a , c);
     }
     int Q;
     for(cin >> Q ; Q ; Q--){
         int a , b , c;
         cin >> a >> b >> c;
         while(b <= c)
             no[b++][a] = ;
     }
     memset(minR , 0x3f , sizeof(minR));
     memset(dp , 0x3f , sizeof(dp));
      ; i <= N ; i++){
         memset(cannot ,  , sizeof(cannot));
         for(int j = i ; j ; j--){
              ; k <= M ; k++)
                 cannot[k] |= no[j][k];
             int t = SPFA();
             if(t == inf)
                 break;
             minR[j][i] = t;
         }
     }
     dp[] = ;
      ; i <= N ; i++)
          ; j >=  ; j--)
             ][i] != inf)
                 dp[i] = min(dp[i] , dp[j] + minR[j + ][i] * (i - j) + K * (bool)j);
     cout << dp[N];
     ;
 }
 

1003 物流运输

1004 Cards

Here

1005 明明的烦恼

高精度是真的恶心……

Purfer序列+组合数

方案是将所有非$-1$的数放入Purfer序列的总方案$\times$Purfer序列中没有填上的位置给所有$-1$的方案$\times$这两种排列合成一个排列的方案

第一个是$\frac{(\sum du_i -1)!}{\prod (du_i - 1)!}$,第二个是$[N - 2 - \sum (du_i - 1)] ^ {\text{-1的个数}}$,第三个是$C_{N-2}^{\sum (du_i - 1)}$

使用质因数分解避免慢到爆炸的高精度除法

 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<ctime>
 #include<cctype>
 #include<algorithm>
 #include<cstring>
 #include<iomanip>
 #include<queue>
 #include<map>
 #include<set>
 #include<bitset>
 #include<stack>
 #include<vector>
 #include<cmath>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = a *  + c - ;
         c = getchar();
     }
     return f ? -a : a;
 }

 struct Bignum{
     ];
     int& operator [](int x){return a[x];}
     Bignum(){
         memset(a ,  , sizeof(a));
     }
     Bignum(int b){
         memset(a ,  , sizeof(a));
         while(b){
             a[++a[]] = b % ;
             b /= ;
         }
     }
     Bignum operator =(int b){
         return *this = Bignum(b);
     }
     void input(){
         string s;
         cin >> s;
         a[] = s.size();
          ; i <= a[] ; ++i)
             a[i] = s[s.size() - i] - ';
     }
     void output(){
         ])
             putchar(');
         ] ; i ; --i)
             putchar(a[i] + ');
         putchar('\n');
     }
     Bignum operator +(Bignum b){
         Bignum c;
         c[] = max(a[] , b[]);
          ; i <= c[] ; ++i)
             ){
                 c[i] -= ;
                 ++c[i + ];
             }
         ] + ])
             ++c[];
         return c;
     }
     Bignum operator +=(Bignum b){
         return *this = *this + b;
     }
     Bignum operator -(Bignum b){
         Bignum c;
         c[] = max(a[] , b[]);
          ; i <= c[] ; ++i)
             ){
                 c[i] += ;
                 --c[i + ];
             }
         ] && !c[c[]])
             --c[];
         return c;
     }
     Bignum operator -=(Bignum b){
         return *this = *this - b;
     }
     Bignum operator *(Bignum b){
         ])
             return b;
         Bignum c;
         c[] = a[] + b[] - ;
          ; i <= a[] ; ++i)
              ; j <= b[] ; ++j)
                 c[i + j - ] += a[i] * b[j];
          ; i <= c[] ; ++i)
             ){
                 c[i + ] += c[i] / ;
                 c[i] %= ;
                 ])
                     ++c[];
             }
         ] && !c[c[]])
             --c[];
         return c;
     }
     Bignum operator *=(Bignum b){
         return *this = *this * b;
     }
     Bignum operator ^(int a){
         Bignum times() , b(*this);
         while(a){
             )
                 times *= b;
             b *= b;
             a >>= ;
         }
         return times;
     }
     bool operator >(Bignum b)const{
         ] > b[])
             ;
         ] < b[])
             ;
         ] ; i ; --i)
             if(a[i] > b[i])
                 ;
             else
                 if(a[i] < b[i])
                     ;
         ;
     }
     bool operator >= (Bignum b){
         ] > b[])
             ;
         ] < b[])
             ;
         ] ; i ; --i)
             if(a[i] > b[i])
                 ;
             else
                 if(a[i] < b[i])
                     ;
         ;
     }
     Bignum operator /(Bignum b){
         Bignum c , d = *this , e;
         c[] = a[] - b[] + ;
         ] ; i && d[] ; --i){
             e = b * (Bignum() ^ (i - ));
              ; j <=  ; ++j)
                 if(e > d){
                     c[i] = j - ;
                     break;
                 }
                 else
                     d -= e;
         }
         ] && !c[c[]])
             --c[];
         return c;
     }
     Bignum operator /=(Bignum b){
         return *this = *this / b;
     }
     Bignum operator %(Bignum b){
         return *this - *this / b * b;
     }
     Bignum operator %=(Bignum b){
         return *this = *this % b;
     }
 }all();

 ] , jc[][] , prime[][] , ans[];

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     //freopen("out","w",stdout);
 #endif
     N = read();
      ; i <= N ; ++i){
         int t = i;
          ; j * j <= t ; ++j)
             ){
                 t /= j;
                 ++prime[i][j];
             }
         )
             ++prime[i][t];
     }
      ; i <= N -  ; ++i)
          ; j <= i ; ++j)
             jc[i][j] = jc[i - ][j] + prime[i][j];
      ; i <= N ; ++i){
         int a = read();
         ){
             ){
                 puts(");
                 ;
             }
             du[++cnt] = a;
         }
     }
     ;
      ; i <= cnt ; ++i)
         sum += du[i] - ;
     ){
         puts(");
         ;
     }
     memcpy(ans , jc[sum] , sizeof(ans));
      ; i <= cnt ; ++i)
          ; j < du[i] ; ++j)
             ans[j] -= jc[du[i] - ][j];
      ; i <= N - cnt ; ++i)
         ans[i] += prime[N - cnt][i] * (N -  - sum);
      ; i <= N -  ; ++i)
         ans[i] = ans[i] + jc[N - ][i] - jc[sum][i] - jc[N -  - sum][i];
      ; i <= N ; ++i)
         all *= Bignum(i) ^ ans[i];
     all.output();
     ;
 }

1005 明明的烦恼

1006 神奇的国度

弦图最小染色,详细做法请见CDQ论文(因为我也不会

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ;
 deque < int > num[MAXN];
 struct Edge{
     int end , upEd;
 }Ed[MAXN * ];
 int head[MAXN] , ans[MAXN] , cnt[MAXN] , mex[MAXN] , col[MAXN] , N , M , cntEd;
 bool vis[MAXN];

 inline void addEd(int a , int b){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     head[a] = cntEd;
 }

 void calc(){
      ; i <= N ; ++i)
         num[].push_back(i);
     ;
     for(int i = N ; i ; --i){
         ;
         while(!cur){
             while(!cur && !num[best].empty()){
                 if(!vis[num[best].back()])
                     cur = num[best].back();
                 num[best].pop_back();
             }
             if(!cur)
                 --best;
         }
         vis[cur] = ;
         ans[i] = cur;
         for(int j = head[cur] ; j ; j = Ed[j].upEd)
             if(!vis[Ed[j].end]){
                 ++cnt[Ed[j].end];
                 num[cnt[Ed[j].end]].push_back(Ed[j].end);
                 best = max(best , cnt[Ed[j].end]);
             }
     }
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     N = read();
     M = read();
      ; i <= M ; ++i){
         int a = read() , b = read();
         addEd(a , b);
         addEd(b , a);
     }
     calc();
     ;
     for(int i = N ; i ; --i){
         for(int j = head[ans[i]] ; j ; j = Ed[j].upEd)
             mex[col[Ed[j].end]] = i;
         col[ans[i]] = ;
         while(mex[col[ans[i]]] == i)
             ++col[ans[i]];
         all = max(all , col[ans[i]]);
     }
     cout << all;
     ;
 }

1006 神奇的国度

1007 水平可见直线

建立一个上凸包,将斜率从小到大排序,用单调栈维护,半平面交判断无用直线

 #include<bits/stdc++.h>
 #define ld long double
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ;
 struct L{
     int A , B , ind;
     bool operator <(const L a)const{
         return A == a.A ? B > a.B : A < a.A;
     }
 }line[MAXN];
 int St[MAXN] , top , N;

 inline int sgn(int x){
      ? - : (x ==  ?  : );
 }

 inline bool cmp(int a , int b , int c){
     int p = line[a].B - line[b].B , q = line[b].A - line[a].A , m = line[b].B - line[c].B , n = line[c].A - line[b].A;
     return 1ll * p * n * sgn(q) * sgn(n) >= 1ll * q * m * sgn(q) * sgn(n);
 }

 signed main(){
 #ifndef ONLINE_JUDGE
     freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     N = read();
      ; i <= N ; ++i){
         line[i].A = read();
         line[i].B = read();
         line[i].ind = i;
     }
     sort(line +  , line + N + );
      ; i <= N ; ++i){
          && line[i].A == line[i - ].A)
             continue;
          && cmp(St[top] , St[top - ] , i) && cmp(St[top - ] , i , St[top]))
             --top;
         St[++top] = i;
     }
      ; i <= top ; ++i)
         St[i] = line[St[i]].ind;
     sort(St +  , St + top + );
      ; i <= top ; ++i)
         printf("%d " , St[i]);
     ;
 }

1007 水平可见直线

1008 越狱

答案等于$M^N$减去不会产生越狱的方案数,不会越狱的方案数显然是$M \times (M-1)^{N-1}$

 #include<bits/stdc++.h>
 #define int long long
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ;

 inline int poww(int a , int b){
     a %= MOD;
     ;
     while(b){
         )
             times = times * a % MOD;
         a = a * a % MOD;
         b >>= ;
     }
     return times;
 }

 signed main(){
 #ifndef ONLINE_JUDGE
     freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     int M = read() , N = read();
     cout << (poww(M , N) - M % MOD * poww(M -  , N - ) % MOD + MOD) % MOD;
     ;
 }

1008 越狱

1009 GT考试

用$KMP$建立转移矩阵进行矩阵$DP$

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 ];
 ];
 struct matrix{
     ][];
     matrix(){memset(a ,  , sizeof(a));}
     int* operator [](int x){return a[x];}
     matrix operator *(matrix b){
         matrix c;
          ; i < L ; ++i)
              ; j < L ; ++j)
                  ; k < L ; ++k)
                     c[i][j] += a[i][k] * b[k][j];
          ; i < L ; ++i)
              ; j < L ; ++j)
                 c[i][j] %= P;
         return c;
     }
 }S , T;

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     nxt[] = -;
     scanf();
     S[][] = ;
      ; i <= L ; ++i){
         ];
          && s[dir + ] != s[i])
             dir = nxt[dir];
         nxt[i] = dir + ;
     }
      ; i < L ; ++i){
         ;
         ] = {};
         ){
             ] - ']){
                 vis[s[t + ] - ;
                 --cnt;
                 )
                     T[i][t + ] = ;
             }
             t = nxt[t];
         }
         T[i][] = cnt;
     }
     while(N){
         )
             S = S * T;
         T = T * T;
         N >>= ;
     }
     ;
      ; i < L ; ++i)
         sum += S[][i];
     cout << sum % P;
     ;
 }

1009 GT考试

1010-1019

1010 玩具装箱

斜率优化裸题,见笔记

1011 遥远的行星

对于$i \times A \leq 300$的暴力统计

对于$i \times A > 300$的先暴力统计最后300个,剩下的分块统计

分块统计过程中一段区间$[x,y]$的贡献变为$M_i \times \frac{\sum\limits_{j = x} ^ y M_j}{i - \frac{x + y}{2}}$

 #include<bits/stdc++.h>
 #define ld long double
 //This code is written by Itst
 using namespace std;

 ;
 ld M[MAXN] , sum[MAXN] , A;
 int N;

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     freopen("out","w",stdout);
 #endif
     scanf("%d %Lf" , &N , &A);
      ; i <= N ; ++i)
         scanf("%Lf" , M + i);
      ; i <= N ; ++i){
         sum[i] = sum[i - ] + M[i];
         ld ans = ;
         int bef = i * A;
          , ) ; --j)
             ans += M[i] * M[j] / (i - j);
         ){
             bef -= ;
             int t = sqrt(bef) , p;
             while(bef){
                 p = max(bef - t , );
                 ans += M[i] * (sum[bef] - sum[p]) / (i - (bef + p) / );
                 bef = p;
             }
         }
         printf("%.5Lf\n" , ans);
     }
     ;
 }

1011 遥远的行星

1012 最大数

动态开点线段树(当然直接开2e5也是可以的),或者ST表动态统计(ST表不知道比线段树快到哪里去了)

 #include<bits/stdc++.h>
 using namespace std;

 inline unsigned int read(){
     ;
     char c = getchar();
     while(!isdigit(c))
         c = getchar();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return a;
 }

 ;
 ] , M , MOD , len , lastans;

 inline void insert(int num){
     ST[++len][] = num;
      ;  << i <= len ; i++)
         ST[len][i] = max(ST[len][i - ] , ST[len - ( << i - )][i - ]);
 }

 inline int query(int ind){
     int l = log2(ind);
      << l)][l]);
 }

 int main(){
     M = read();
     MOD = read();
     while(M--){
         char c = getchar();
         while(!isupper(c))
             c = getchar();
         if(c == 'Q')
             printf("%d\n" , lastans = query(read()));
         else
             insert((read() + lastans) % MOD);
     }
     ;
 }

1012 最大数 ST表

 #include<bits/stdc++.h>
 #define endl '\n'
 using namespace std;
 struct node{
     long long maxN , start , end;
     node *left , *right;
     node(long long _s , long long _e):start(_s) , end(_e)
     {
         maxN = ;
         if(_e - _s)
         {
             left = );
             right = ) +  , _e);
         }
     }
     long long find_max(long long _s, long long _e)
     {
         if(_s == start && _e == end)    return maxN;
         )    return left->find_max(_s , _e);
         )    return right->find_max(_s , _e);
         ) , right->find_max((start + end >> ) +  , _e));
     }
     void change_max(long long k , long long q)
     {
         maxN = max(maxN , q);
         if(start == end)    return;
         )    left->change_max(k , q);
         else    right->change_max(k , q);
     }
 };
 int main(){
     ios::sync_with_stdio();cin.tie();cout.tie();
      , cou = ;
     cin >> M >> D;
     node *Tree =  , M);
      ; i <= M ; i++)
     {
         char c;
         long long a;
         cin >> c >> a;
         if(c == 'Q'){
             ;
              , cou);
             cout << t << endl;
         }
         else    Tree->change_max(++cou , (t + a) % D);
     }
     ;
 }

1012 最大数 动态开点线段树

1013 球形空间产生器

将距离公式拆开,将所有二次项与半径的平方合起来看成一个未知数,剩下的圆心$N$维坐标设$N$个未知数,高斯消元即可

 #include<bits/stdc++.h>
 #define eps 1e-8
 using namespace std;

 ][] , dir[][];

 int main(){
     int N;
     cin >> N;
      ; i <= N +  ; i++){
          ; j <= N ; j++){
             cin >> dir[i][j];
             guass[i][j] =  * dir[i][j];
             guass[i][N + ] += dir[i][j] * dir[i][j];
         }
         guass[i][N + ] = -;
     }
      ; i <= N +  ; i++){
         int j;
          ; j++)
              || guass[j][i] + eps < )
                 break;
         if(j != i)
              ; k <= N +  ; k++)
                 swap(guass[i][k] , guass[j][k]);
          ; j >= i ; j--)
             guass[i][j] /= guass[i][i];
          ; j <= N +  ; j++)
              || guass[j][i] + eps < ))
                  ; k >= i ; k--)
                     guass[j][k] -= guass[i][k] * guass[j][i] / guass[i][i];
     }
      ; i <= N ; i++)
         cout << ) << guass[i][N + ] << ' ';
     ;
 }

1013 球形空间产生器

1014 火星人

Splay维护字符串Hash,每一次LCQ查询时二分答案

本题及其卡常,请使用较快速的IO并使用自然溢出(要选择较大的质数作为Hash进制位)(话说十年前真是清流竟然不卡自然溢出)

 #include<bits/stdc++.h>
 #define ll long long
 using namespace std;

 ;

 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))
         c = getchar();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return a;
 }

 struct node{
     ] , fa , size;
     char c;
     unsigned ll Hash;
 }Tree[MAXN];

 unsigned ll poww[MAXN] = {};
  , root =  , N;

 inline bool son(int dir){
     ] == dir;
 }

 inline void pushup(int dir){
     Tree[dir].size = Tree[Tree[dir].ch[]].size + Tree[Tree[dir].ch[]].size + ;
     Tree[dir].Hash = Tree[Tree[dir].ch[]].Hash + poww[Tree[Tree[dir].ch[]].size] * Tree[dir].c + poww[Tree[Tree[dir].ch[]].size + ] * Tree[Tree[dir].ch[]].Hash;
 }

 inline void ZigZag(int dir){
     bool f = son(dir);
     int t = Tree[Tree[dir].fa].fa;
     if(Tree[dir].fa == root)
         root = dir;
     Tree[Tree[dir].fa].ch[f] = Tree[dir].ch[f ^ ];
     Tree[Tree[dir].ch[f ^ ]].fa = Tree[dir].fa;
     Tree[t].ch[son(Tree[dir].fa)] = dir;
     Tree[Tree[dir].fa].fa = dir;
     Tree[dir].ch[f ^ ] = Tree[dir].fa;
     Tree[dir].fa = t;
     pushup(Tree[dir].ch[f ^ ]);
     pushup(dir);
 }

 inline void Splay(int dir , int fa){
     while(Tree[dir].fa != fa)
         if(Tree[Tree[dir].fa].fa == fa)
             ZigZag(dir);
         else{
             if(son(dir) == son(Tree[dir].fa))
                 ZigZag(Tree[dir].fa);
             else
                 ZigZag(dir);
             ZigZag(dir);
         }
 }

 void insert(int &now , int size , char c , int fa){
     ){
         now = ++cntNode;
         Tree[now].fa = fa;
         Tree[now].c = c - 'a';
         Splay(now , );
         return;
     }
     ]].size + )
         insert(Tree[now].ch[] , size - Tree[Tree[now].ch[]].size -  , c , now);
     else
         insert(Tree[now].ch[] , size , c , now);
 }

 void getKth(int &now , int size , int to){
     ]].size +  == size){
         Splay(now , to);
         return;
     }
     ]].size)
         getKth(Tree[now].ch[] , size - Tree[Tree[now].ch[]].size -  , to);
     else
         getKth(Tree[now].ch[] , size , to);
 }

 inline bool check(int fir , int sec , int len){
     getKth(root , fir , );
     getKth(root , fir + len +  , root);
     unsigned ll t = Tree[Tree[Tree[root].ch[]].ch[]].Hash;
     getKth(root , sec , );
     getKth(root , sec + len +  , root);
     ]].ch[]].Hash;
 }

 inline int getAns(int fir , int sec){
     if(fir > sec)
         swap(fir , sec);
      , r = cntNode - sec - ;
     while(l < r){
          >> ;
         if(check(fir , sec , mid))
             l = mid;
         else
             r = mid - ;
     }
     return l;
 }

 ];

 int main(){
      ; i <=  ; i++)
         poww[i] = poww[i - ] * ;
     scanf("%s" , s);
     Tree[].fa = ;
     Tree[].ch[] = ;
     Tree[].size = ;
     Tree[].size = ;
     int len = strlen(s);
      ; i < len ; i++){
         insert(root , i +  , s[i] , );
         Splay(rand() % cntNode +  , );
     }
     int Q;
     for(Q = read() ; Q ; Q--){
         char c = getchar();
         int a;
         while(!isupper(c))
             c = getchar();
         a = read();
         switch(c){
         case 'Q':
             printf("%d\n" , getAns(a , read()));
             break;
         case 'R':
             c = getchar();
             while(!islower(c))
                 c = getchar();
             getKth(root , a +  , );
             Tree[root].c = c - 'a';
             pushup(root);
             break;
         case 'I':
             c = getchar();
             while(!islower(c))
                 c = getchar();
             insert(root , a +  , c , );
         }
     }
     ;
 }

1014 火星人

1015 星球大战

删边维护并查集显然是不现实的,不过反过来从后往前考虑就是不断加边的过程,并查集就可以实现了。

PS:cout真心慢qwq

 #include<bits/stdc++.h>
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))
         c = getchar();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return a;
 }

 ;
 struct Edge{
     int start , end , time;
 }now[MAXN];
 ] , times[MAXN << ] , N , M;

 int find(int x){
     return x == fa[x] ? x : (fa[x] = find(fa[x]));
 }

 bool cmp(Edge a , Edge b){
     return a.time < b.time;
 }

 int main(){
     memset(times , 0x3f , sizeof(times));
     N = read();
     M = read();
      ; i <= M ; i++){
         now[i].start = read();
         now[i].end = read();
     }
      ; i < N ; i++)
         fa[i] = i;
     int K = read();
      ; i <= K ; i++)
         times[read()] = i;
      ; i <= M ; i++)
         now[i].time = min(times[now[i].start] , times[now[i].end]);
     sort(now +  , now + M +  , cmp);
     int p = M , cnt = N;
      ; i--){
         while(p && now[p].time > i){
             int a = find(now[p].start) , b = find(now[p].end);
             if(a != b){
                 cnt--;
                 fa[a] = b;
             }
             p--;
         }
         ans[i] = cnt;
     }
      ; i <= K ; i++)
         printf("%d\n" , ans[i] - i);
     ;
 }

1015 星球大战

1016 最小生成树计数

$Matrix-tree$定理裸题

注意矩阵树定理必须要在原图联通的情况下才能使用,所以每一次计算的时候要把其他的边连上,否则会出现答案为$0$的情况

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))
         c = getchar();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return a;
 }

 ;
 struct Edge{
     int s , t , w;
     bool operator <(const Edge a)const{
         return w < a.w;
     }
 }Ed[];
 ][] , fa[] , N , M , cntL , ans = ;
 map < int , int > lsh;
 ];

 int find(int x){
     return fa[x] == x ? x : (fa[x] = find(fa[x]));
 }

 inline int getL(int x){
     if(!lsh.count(x))
         lsh[x] = ++cntL;
     return lsh[x];
 }

 inline void calc(int x , int y , int &a , int &b , int &c , int &d , int &flg){
     a = d = flg = ;
     c = b = ;
     while(y){
         int t = x / y;
         x -= t * y;
         a = (a - t * c % MOD + MOD) % MOD;
         b = (b - t * d % MOD + MOD) % MOD;
         swap(x , y);
         swap(a , c);
         swap(b , d);
         flg *= -;
     }
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     N = read();
     M = read();
      ; i <= M ; ++i){
         Ed[i].s = read();
         Ed[i].t = read();
         Ed[i].w = read();
     }
      ; i <= N ; ++i)
         fa[i] = i;
     sort(Ed +  , Ed + M + );
      ; i <= M ; ++i)
         if(fa[find(Ed[i].s)] != fa[find(Ed[i].t)]){
             fa[find(Ed[i].s)] = find(Ed[i].t);
             vis[i] = ;
         }
      ; i <= N ; ++i)
         )){
             puts(");
             ;
         }
      ; i <= M ; ){
         int p = i;
         cntL = ;
         lsh.clear();
         memset(mat ,  , sizeof(mat));
          ; j <= N ; ++j)
             fa[j] = j;
          ; j <= M ; ++j)
             if(vis[j] && Ed[j].w != Ed[i].w)
                 fa[find(Ed[j].s)] = find(Ed[j].t);
         while(p <= M && Ed[i].w == Ed[p].w){
             int m = find(Ed[p].s) , n = find(Ed[p].t);
             if(m != n){
                 m = getL(m);
                 n = getL(n);
                 --mat[m][n];
                 --mat[n][m];
                 ++mat[m][m];
                 ++mat[n][n];
             }
             ++p;
         }
          ; j < cntL ; ++j)
              ; k < cntL ; ++k)
                 )
                     mat[j][k] += MOD;
          ; j < cntL ; ++j)
              ; k < cntL ; ++k)
                 if(mat[k][j]){
                     int a , b , c , d , flg;
                     calc(mat[j][j] , mat[k][j] , a , b , c , d , flg);
                     ans = (ans * flg + MOD) % MOD;
                     for(int l = j ; l < cntL ; ++l){
                         int r = (mat[j][l] * a + mat[k][l] * b) % MOD;
                         int s = (mat[j][l] * c + mat[k][l] * d) % MOD;
                         mat[j][l] = r;
                         mat[k][l] = s;
                     }
                 }
          ; j < cntL ; ++j)
             if(mat[j][j])
                 ans = (ans * mat[j][j] % MOD + MOD) % MOD;
         while(i < p){
             fa[find(Ed[i].s)] = find(Ed[i].t);
             ++i;
         }
     }

     cout << ans << endl;
     ;
 }

1016 最小生成树计数

1018 堵塞的交通

线段树维护列在某一段区间内的矩形的四个顶点之间的连通性,然后大力分类讨论即可

 #include<iostream>
 #include<cstdio>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))
         c = getchar();
     while(isdigit(c)){
         a = a *  + c - ;
         c = getchar();
     }
     return a;
 }

 ;
 ];
 int all;
 namespace segTree{
     struct node{
         bool f1 , f2 , f3 , f4 , f5 , f6;
         /*f1: <^  ^>

           f2: <v  v>

           f3: <^
                   v>

           f4: <^
               <v

           f5:     ^>
               <v

           f6:     ^>
                   v>
          */
         node(){f1 = f2 = f3 = f4 = f5 = f6 = ;}
     }Tree[MAXN << ];

 #define mid ((l + r) >> 1)
 #define lch (x << 1)
 #define rch (x << 1 | 1)
     node merge(node a , node b , int x){
         node t;
         t.f4 |= a.f4; t.f6 |= b.f6;
         ]){
             t.f1 |= a.f1 & b.f1; t.f3 |= a.f1 & b.f3;
             t.f2 |= a.f5 & b.f3; t.f5 |= a.f5 & b.f1;
         }
         ]){
             t.f1 |= a.f3 & b.f5; t.f3 |= a.f3 & b.f2;
             t.f2 |= a.f2 & b.f2; t.f5 |= a.f2 & b.f5;
         }
         ] && link[x][]){
             t.f4 |= a.f1 & a.f2 & b.f4;
             t.f6 |= b.f1 & b.f2 & a.f6;
         }
         return t;
     }

     void init(int x , int l , int r){
         ;
          , r);}
     }

     void modify(int x , int l , int r , int tar , bool flg){
         if(l == r){
             Tree[x].f3 ^= flg; Tree[x].f4 ^= flg;
             Tree[x].f5 ^= flg; Tree[x].f6 ^= flg;
             return;
         }
         if(mid >= tar) modify(lch , l , mid , tar , flg);
          , r , tar , flg);
         Tree[x] = merge(Tree[lch] , Tree[rch] , mid);
     }

     node query(int x , int l , int r , int L , int R){
         if(L > R) return node();
         if(l >= L && r <= R) return Tree[x];
         ;
         node t;
         ; t = query(lch , l , mid , L , R);}
         if(mid < R)
             t = f ? merge(t , query(rch , mid +  , r , L , R) , mid) : query(rch , mid +  , r , L , R);
         return t;
     }
 }
 using namespace segTree;

 inline char getc(){
     char c = getchar();
     while(!isupper(c)) c = getchar();
     return c;
 }

 inline void out(bool f){puts(f ? "Y" : "N");}

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     freopen("out","w",stdout);
 #endif
     init( ,  , all = read());
     char c = getc();
     ;;
     node lft , now , rht;
     while(c != 'E'){
         if(c == 'A'){
             ++cntQue;
             B = read(); A = read(); D = read(); C = read();
             if(A > C){A ^= C ^= A ^= C; B ^= D ^= B ^= D;}
             lft = query( ,  , all ,  , A - );
             rht = query( ,  , all , C +  , all);
             now = query( ,  , all , A , C);
             )
                 )
                     ][] && link[C][] && link[A - ][] && link[C][] && now.f2 && lft.f6 && rht.f4) || (link[A - ][] && link[A - ][] && lft.f6 && now.f5) || (link[C][] && link[C][] && rht.f4 && now.f3));
                 else
                     ][] && link[A - ][] && lft.f6 && now.f2) || (link[C][] && link[C][] && rht.f4 && now.f1) || (link[A - ][] && link[A - ][] && link[C][] && link[C][] && lft.f6 && rht.f4 && now.f5));
             else
                 )
                     ][] && link[A - ][] && lft.f6 && now.f1) || (link[C][] && link[C][] && rht.f4 && now.f2) || (link[A - ][] && link[A - ][] && link[C][] && link[C][] && lft.f6 && rht.f4 && now.f3));
                 else
                     ][] && link[A - ][] && link[C][] && link[C][] && now.f1 && lft.f6 && rht.f4) || (link[A - ][] && link[A - ][] && lft.f6 && now.f3) || (link[C][] && link[C][] && rht.f4 && now.f5));
         }
         else{
             B = read(); A = read(); D = read(); C = read();
              ,  , all , A , );
             else{
                 if(A > C) --A;
                 link[A][B - ] ^= ;
                 modify( ,  , all , A , );
             }
         }
         c = getc();
     }
     ;
 }

1018 堵塞的交通

1020-1029

1022 小约翰的游戏

Anti-SG模板,先手必胜则有:所有石子为$1$且$SG = 0$或者至少有一堆石子不为$1$且$SG \neq 0$

 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<ctime>
 #include<cctype>
 #include<algorithm>
 #include<cstring>
 #include<iomanip>
 #include<queue>
 #include<map>
 #include<set>
 #include<bitset>
 #include<stack>
 #include<vector>
 #include<cmath>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = a *  + c - ;
         c = getchar();
     }
     return f ? -a : a;
 }

 int main(){
 #ifndef ONLINE_JUDGE
     //freopen("in","r",stdin);
     //freopen("out","w",stdout);
 #endif
     for(int T = read() ; T ; --T){
         ;
         ;
         for(int N = read() ; N ; --N){
             int a = read();
             sum ^= a;
             flg &= a == ;
         }
         puts((flg ^ (bool)sum) ? "John" : "Brother");
     }
     ;
 }

1022 小约翰的游戏

1023 仙人掌图

Here

1024 生日快乐

爆搜题

 #include<bits/stdc++.h>
 #define ld long double
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     ;
     char c = getchar();
     while(c != EOF && !isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(c != EOF && isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ;
 ld S;
 int N;
 bool cmp(ld x , ld y){
     return x + eps > y && x - eps < y;
 }
 struct node{
     ld x , y;
 };
 map < node , ld > m;

 bool operator <(node a , node b){
     return !cmp(a.x , b.x) && a.x < b.x || cmp(a.x , b.x) && a.y < b.y;
 }

 bool operator ==(node a , node b){
     return cmp(a.x , b.x) && cmp(a.y , b.y);
 }

 ld dfs(int now , ld nowX , ld nowY){
     if(m.count((node){nowX , nowY}))
         return m[(node){nowX , nowY}];
     if(cmp(nowX * nowY , S))
          ? nowY / nowX : nowX / nowY;
     ld ans = 1e18;
      ; i ; i--){
         ld k = dfs(i , nowX / now * i , nowY);
         if(k < ans)
             ans = min(ans , max(k , dfs(now - i , nowX / now * (now - i) , nowY)));
     }
      ; i ; i--){
         ld k = dfs(i , nowX , nowY / now * i);
         if(k < ans)
             ans = min(ans , max(k , dfs(now - i , nowX , nowY / now * (now - i))));
     }
     return m[(node){nowX , nowY}] = ans;
 }

 int main(){
 #ifdef BZ
     freopen("1024.in" , "r" , stdin);
     //freopen("1024.out" , "w" , stdout);
 #endif
     ld X = read() , Y = read();
     N = read();
     S = X * Y / N;
     printf("%.6Lf" , dfs(N , X , Y));
     ;
 }

1024 生日快乐

1026 Windy数

数位DP裸题(虽然我调了很久,注意边界条件)

 #include<bits/stdc++.h>
 #define BZ
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     ;
     char c = getchar();
     while(c != EOF && !isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(c != EOF && isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ] = {,,,1e3,1e4,1e5,1e6,1e7,1e8,1e9};
 ][];

 inline int abs(int x){
      ? -x : x;
 }

 void init(){
      ; i <  ; i++)
         dp[][i] = ;
      ; j <=  ; j++)
          ; k <  ; k++)
              ; l <  ; l++)
                 )
                     dp[j][k] += dp[j - ][l];
 }

 int dfs(int now , int pos , int pre){
     ){
         ;
          ; i <= now ; i++)
             )
                 sum++;
         return sum;
     }
      , i;
      ; poww10[pos] * (i + ) <= now ; i++)
         )
             sum += dp[pos][i];
     )
          , i);
     else
         return sum;
 }

 inline int work(int pos){
     )
         ;
     ) + 1e- , sum = ;
      ; i < t ; i++)
          ; j <=  ; j++)
             sum += dp[i][j];
     ) - dp[t][] + sum;
 }

 int main(){
 #ifdef BZ
     freopen("1026.in" , "r" , stdin);
     //freopen("1026.out" , "w" , stdout);
 #endif
      , R = read();
     init();
     printf("%d" , work(R) - work(L));
     ;
 }

1026 Windy数

1028 麻将

枚举胡的牌,然后枚举对子,接着从左往右更新,能拿三张就拿三张,不能就拿顺子

 #include<bits/stdc++.h>
 using namespace std;
 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))
         c = getchar();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return a;
 }
 ] , forCheck[] , forDui[] , ansNum[] , M;
 bool check(int dir){
     memcpy(forCheck , pot , sizeof(pot));
     forCheck[dir] -= ;
      ; i <= M ; i++){
         )
             ;
         forCheck[i] %= ;
         forCheck[i + ] -= forCheck[i];
         forCheck[i + ] -= forCheck[i];
     }
     ] ==  && forCheck[M + ] == ;
 }
 int main(){
     M = read();
     int N = read();
      ; i <=  * N +  ; i++){
         int a = read();
         )
             forDui[++forDui[]] = a;
     }
      ; i <= M ; i++){
         pot[i]++;
         )
             if(check(i)){
                 ansNum[++ansNum[]] = i;
                 pot[i]--;
                 continue;
             }
         ;
          ; !f && j <= forDui[] ; j++)
             f = check(forDui[j]);
         if(f)
             ansNum[++ansNum[]] = i;
         pot[i]--;
     }
     ])
         cout << "NO";
      ; i <= ansNum[] ; i++)
         cout << ansNum[i] << ' ';
     ;
 }

1028 麻将

1029 建筑抢修

有点神仙

按照$T2$从小到大排序,每一个任务尽可能安排在前面,如果存在某个任务没法被放进去就考虑是否能够替换前面时间最长的任务来缩短总任务时间

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = a *  + c - ;
         c = getchar();
     }
     return f ? -a : a;
 }

 ;
 priority_queue < int > q;
 struct work{
     int t1 , t2;
     bool operator <(const work a)const{
         return t2 == a.t2 ? t1 < a.t1 : t2 < a.t2;
     }
 }now[MAXN];
 int N;
 long long all;

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     freopen("out","w",stdout);
 #endif
     N = read();
      ; i <= N ; ++i){
         now[i].t1 = read();
         now[i].t2 = read();
     }
     sort(now +  , now + N + );
      ; i <= N ; ++i)
         if(all + now[i].t1 <= now[i].t2){
             q.push(now[i].t1);
             all += now[i].t1;
         }
         else
             if(!q.empty() && now[i].t1 < q.top()){
                 all = all - q.top() + now[i].t1;
                 q.pop();
                 q.push(now[i].t1);
             }
     cout << q.size();
     ;
 }

1029 建筑抢修

1030-1039

1030 文本生成器

Trie图上DP

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = a *  + c - ;
         c = getchar();
     }
     return f ? -a : a;
 }

  , MOD = ;
 struct node{
     ] , fail;
     bool get;
 }Trie[MAXN];
  , N , M , dp[][][];
 char s[MAXN];

 void insert(){
      , L = strlen(s + );
      ; i <= L ; ++i){
         if(!Trie[t].ch[s[i] - 'A'])
             Trie[t].ch[s[i] - 'A'] = ++cntN;
         t = Trie[t].ch[s[i] - 'A'];
     }
     Trie[t].;
 }

 void init(){
     queue < int > q;
     Trie[].fail = ;
      ; i <  ; ++i)
         ].ch[i]){
             Trie[Trie[].ch[i]].fail = ;
             q.push(Trie[].ch[i]);
         }
         else
             Trie[].ch[i] = ;
     while(!q.empty()){
         int t = q.front();
         q.pop();
          ; i <  ; ++i)
             if(Trie[t].ch[i]){
                 Trie[Trie[t].ch[i]].fail = Trie[Trie[t].fail].ch[i];
                 Trie[Trie[t].ch[i]].get |= Trie[Trie[Trie[t].fail].ch[i]].get;
                 q.push(Trie[t].ch[i]);
             }
             else
                 Trie[t].ch[i] = Trie[Trie[t].fail].ch[i];
     }
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     freopen("out","w",stdout);
 #endif
     N = read();
     M = read();
      ; i <= N ; ++i){
         scanf();
         insert();
     }
     init();
     dp[][][] = ;
      ; i < M ; ++i)
          ; j <= cntN ; ++j)
              ; k <=  ; ++k)
                 if(dp[i][j][k])
                      ; p <  ; ++p)
                         (dp[i + ][Trie[j].ch[p]][k | Trie[Trie[j].ch[p]].get] += dp[i][j][k]) %= MOD;
     ;
      ; i <= cntN ; ++i)
         sum = (sum + dp[M][i][]) % MOD;
     cout << sum;
     ;
 }

1030 文本生成器

1031 字符加密

倍长然后SA计算每一个串之间的顺序

 #include<bits/stdc++.h>
 using namespace std;

 ;
 char s[MAXN];
 ] , tp[MAXN << ] , pot[MAXN] , sa[MAXN] , h[MAXN];
 int maxN , L;

 void sort(int p){
     memset(pot ,  , ));
      ; i <= L ; ++i)
         ++pot[rk[i]];
      ; i <= maxN ; ++i)
         pot[i] += pot[i - ];
      ; i <= L ; ++i)
         sa[++pot[rk[tp[i]] - ]] = tp[i];
     swap(rk , tp);
      ; i <= L ; ++i)
         rk[sa[i]] = rk[sa[i - ]] + (tp[sa[i]] != tp[sa[i - ]] || tp[sa[i] + p] != tp[sa[i - ] + p]);
     maxN = rk[sa[L]];
 }

 int main(){
     scanf();
     L = strlen(s + );
      ; i <= L <<  ; ++i)
         s[i] = s[i - L];
     s[] = s[L];
     L <<= ;
     maxN = ;
      ; i <= L ; ++i){
         rk[i] = s[i];
         tp[i] = i;
     }
     sort();
      ; i <= L && maxN < L ; i <<= ){
         ;
          ; j <= i ; ++j)
             tp[++cnt] = L - i + j;
          ; j <= L ; ++j)
             if(sa[j] > i)
                 tp[++cnt] = sa[j] - i;
         sort(i);
     }
     /*for(int i = 1 ; i <= L ; ++i){
       if(rk[i] == 1)
       continue;
             int t = rk[i];
             h[t] = max(0 , h[rk[i - 1]] - 1);
             while(s[sa[t] + h[t]] == s[sa[t - 1] + h[t]])
             ++h[t];
             }*/
      ; i <= L ; ++i)
         )
             putchar(s[sa[i] - ]);
 }

1031 字符加密

1034 泡泡堂

看着很像田忌赛马,贪心策略:①最强的能打过就打,不能跳②;②最弱的能打过就打,不能跳③;③己方最弱送对方最强,看是否平局

有②的原因是有可能当前最强的能够打平,打平之后己方全都满足①,这样就没有必要用最弱的送对方最强了

 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<ctime>
 #include<cctype>
 #include<algorithm>
 #include<cstring>
 #include<iomanip>
 #include<queue>
 #include<map>
 #include<set>
 #include<bitset>
 #include<stack>
 #include<vector>
 #include<cmath>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = a *  + c - ;
         c = getchar();
     }
     return f ? -a : a;
 }

 ;
 int zj[MAXN] , cp[MAXN];
 int N;

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     //freopen("out","w",stdout);
 #endif
     N = read();
      ; i <= N ; ++i)
         zj[i] = read();
      ; i <= N ; ++i)
         cp[i] = read();
     sort(zj +  , zj + N + );
     sort(cp +  , cp + N + );
      , t1 = N , h2 =  , t2 = N , sum = ;
      ; i <= N ; ++i)
         if(zj[t1] > cp[t2]){
             --t1;
             --t2;
             sum += ;
         }
         else
             if(zj[t1] < cp[t2]){
                 ++h1;
                 --t2;
             }
             else
                 if(zj[h1] > cp[h2]){
                     ++h1;
                     ++h2;
                     sum += ;
                 }
                 else{
                     if(zj[h1] == cp[t2])
                         ++sum;
                     ++h1;
                     --t2;
                 }
     cout << sum << ' ';
     swap(cp , zj);
     h1 =  , t1 = N , h2 =  , t2 = N , sum = ;
      ; i <= N ; ++i)
         if(zj[t1] > cp[t2]){
             --t1;
             --t2;
             sum += ;
         }
         else
             if(zj[t1] < cp[t2]){
                 ++h1;
                 --t2;
             }
             else
                 if(zj[h1] > cp[h2]){
                     ++h1;
                     ++h2;
                     sum += ;
                 }
                 else{
                     if(zj[h1] == cp[t2])
                         ++sum;
                     ++h1;
                     --t2;
                 }
     cout << N *  - sum;
     ;
 }

1034 泡泡堂

1036 树的统计

树剖裸题

 #include<bits/stdc++.h>
 #define MAXN 30001
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 struct node{
     int l , r , sum , maxN;
 }Tree[MAXN << ];
 struct Edge{
     int end , upEd;
 }Ed[MAXN << ];
 int head[MAXN] , val[MAXN] , size[MAXN] , dep[MAXN] , son[MAXN] , fa[MAXN];
 int N , Q , cntEd , ts , top[MAXN] , ind[MAXN] , rk[MAXN];

 inline int max(int a , int b){
     return a > b ? a : b;
 }

 inline void addEd(int a , int b){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     head[a] = cntEd;
 }

 void dfs1(int dir , int father , int depth){
     size[dir] = ;
     dep[dir] = depth;
     fa[dir] = father;
     for(int i = head[dir] ; i ; i = Ed[i].upEd)
         if(Ed[i].end != father){
             dfs1(Ed[i].end , dir , depth + );
             size[dir] += size[Ed[i].end];
             if(size[Ed[i].end] > size[son[dir]])
                 son[dir] = Ed[i].end;
         }
 }

 void dfs2(int dir , int t){
     top[dir] = t;
     ind[dir] = ++ts;
     rk[ts] = dir;
     if(!son[dir])
         return;
     dfs2(son[dir] , t);
     for(int i = head[dir] ; i ; i = Ed[i].upEd)
         if(son[dir] != Ed[i].end && fa[dir] != Ed[i].end)
             dfs2(Ed[i].end , Ed[i].end);
 }

 inline void pushup(int dir){
     Tree[dir].sum = Tree[dir << ].sum + Tree[dir <<  | ].sum;
     Tree[dir].maxN = max(Tree[dir << ].maxN , Tree[dir <<  | ].maxN);
 }

 void init(int dir , int l , int r){
     Tree[dir].l = l;
     Tree[dir].r = r;
     if(l == r)
         Tree[dir].sum = Tree[dir].maxN = val[rk[l]];
     else{
         init(dir <<  , l , l + r >> );
         init(dir <<  |  , (l + r >> ) +  , r);
         pushup(dir);
     }
 }

 void change(int dir , int poi , int mark){
     if(Tree[dir].l == Tree[dir].r){
         Tree[dir].maxN = Tree[dir].sum = mark;
         return;
     }
     Tree[dir].l + Tree[dir].r >>  >= poi ? change(dir <<  , poi , mark) : change(dir <<  |  , poi , mark);
     pushup(dir);
 }

 int Query_Max(int dir , int l , int r){
     if(Tree[dir].l >= l && Tree[dir].r <= r)
         return Tree[dir].maxN;
     ;
     )
         maxN = max(maxN , Query_Max(dir <<  , l , r));
     )
         maxN = max(maxN , Query_Max(dir <<  |  , l , r));
     return maxN;
 }

 int Query_Sum(int dir , int l , int r){
     if(Tree[dir].l >= l && Tree[dir].r <= r)
         return Tree[dir].sum;
     ;
     )
         sum = Query_Sum(dir <<  , l , r);
     )
         sum += Query_Sum(dir <<  |  , l , r);
     return sum;
 }

 inline void work1(int x , int y){
     change( , ind[x] , y);
 }

 inline int work2(int x , int y){
     ;
     while(fx - fy)
         if(dep[fx] >= dep[fy]){
             maxN = max(maxN , Query_Max( , ind[fx] , ind[x]));
             x = fa[fx];
             fx = top[x];
         }
         else{
             maxN = max(maxN , Query_Max( , ind[fy] , ind[y]));
             y = fa[fy];
             fy = top[y];
         }
      , ind[x] , ind[y])) : max(maxN , Query_Max( , ind[y] , ind[x]));
 }

 inline int work3(int x , int y){
     ;
     while(fx - fy)
         if(dep[fx] >= dep[fy]){
             sum += Query_Sum( , ind[fx] , ind[x]);
             x = fa[fx];
             fx = top[x];
         }
         else{
             sum += Query_Sum( , ind[fy] , ind[y]);
             y = fa[fy];
             fy = top[y];
         }
      , ind[x] , ind[y]) : sum + Query_Sum( , ind[y] , ind[x]);
 }

 ];

 int main(){
     N = read();
      ; i < N ; i++){
         int a = read() , b = read();
         addEd(a , b);
         addEd(b , a);
     }
      ; i <= N ; i++)
         val[i] = read();
     dfs1( ,  , );
     dfs2( , );
     init( ,  , N);
     for(int Q = read() ; Q ; Q--){
         scanf("%s" , s);
         int a = read() , b = read();
         ] == 'C')
             work1(a , b);
         else
             ] == 'M')
                 printf("%d\n" , work2(a , b));
             else
                 printf("%d\n" , work3(a , b));
     }
     ;
 }

1036 树的统计

1037 生日聚会

设$f_{i,j,k,l}$表示放好了$i$个男生、$j$个女生、当前后缀男生-女生最大值为$k$、女生-男生最大值为$l$的方案数

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     ;
     char c = getchar();
     while(c != EOF && !isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(c != EOF && isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ;
 ][][][];

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("2592.in" , "r" , stdin);
     //freopen("2592.out" , "w" , stdout);
 #endif
     int N = read() , M = read() , K = read();
     dp[][][][] = ;
      ; i <= N ; ++i)
          ; j <= M ; ++j)
              ; k <= K ; ++k)
                  ; l <= K ; ++l)
                     if(dp[i][j][k][l]){
                         if(i < N && k < K)
                             (dp[i + ][j][k + ][max(l -  , )] += dp[i][j][k][l]) %= MOD;
                         if(j < M && l < K)
                             (dp[i][j + ][max(k -  , )][l + ] += dp[i][j][k][l]) %= MOD;
                     }
     ;
      ; i <= K ; ++i)
          ; j <= K ; ++j)
             sum = (sum + dp[N][M][i][j]) % MOD;
     cout << sum;
     ;
 }

1037 生日聚会

1038 瞭望塔

显然塔顶位置要在所有山坡对应直线的半平面交内,而山坡和半平面交边界都是折线,所以最优点的塔的横坐标一定是山坡折点和半平面交折点之一,通过二分求高度。

 #include<iostream>
 #include<cstdio>
 #include<algorithm>
 #include<cstring>
 #include<cmath>
 #include<vector>
 #include<iomanip>
 #define eps 1e-12
 //This code is written by Itst
 using namespace std;

 #define ld long double
 bool cmp(ld a , ld b){return a - eps < b && a + eps > b;}

 struct comp{
     ld x , y;
     comp(ld _x =  , ld _y = ) : x(_x) , y(_y){}
     comp operator +(comp a){return comp(x + a.x , y + a.y);}
     comp operator -(comp a){return comp(x - a.x , y - a.y);}
     comp operator *(ld a){return comp(x * a , y * a);}
     ld operator *(comp a){return x * a.x + y * a.y;}
     ld operator %(comp a){return x * a.y - y * a.x;}
     ld dir()const{return atan2(y , x);}
     bool operator <(const comp a)const{return dir() < a.dir();}
     bool operator ==(const comp a)const{return cmp(dir() , a.dir());}
 }now[] , inter[];

 struct line{
     comp pos , dir;
     ;}
 }cur[];
 ];

 comp intersect(line a , line b){
     ld t = (b.dir % (a.pos - b.pos)) / (a.dir % b.dir);
     return a.pos + a.dir * t;
 }

 bool chk(line a , line b , line c){
     ;
 }

 void create(){
     hd = tl = ;
     que[] = ;
      ; i < N ; ++i){
         ].dir) continue;
         ]] , cur[i]))
             --tl;
         ]] , cur[i]))
             ++hd;
         que[++tl] = i;
     }
     ]] , cur[que[hd]]))
         --tl;
      ; i <= tl ; ++i)
         inter[i] = intersect(cur[que[i]] , cur[que[i - ]]);
 }

 ld calc(line a , ld b){
     ) , comp( , )}).y;
 }

 ld search(ld pos){
     int L = hd , R = tl;
     while(L < R){
         ;
         inter[mid + ].x <= pos ? L = mid +  : R = mid;
     }
     return calc(cur[que[L]] , pos);
 }

 int binary(ld pos){
      , R = N;
     while(L < R){
         ) >> ;
         now[mid].x >= pos ? R = mid -  : L = mid;
     }
     return L;
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     //freopen("out","w",stdout);
 #endif
     cin >> N;
      ; i <= N ; ++i)
         cin >> now[i].x;
      ; i <= N ; ++i)
         cin >> now[i].y;
      ; i < N ; ++i){
         cur[i].pos = now[i];
         cur[i].dir = now[i + ] - now[i];
     }
     sort(cur +  , cur + N);
     create();
     vector < long double > vec;
      ; i <= N ; ++i)
         vec.push_back(now[i].x);
      ; i <= tl ; ++i)
         vec.push_back(inter[i].x);
     sort(vec.begin() , vec.end());
     ld ans = 1e20;
      ; i < vec.size() ; ++i){
         ld t = vec[i];
         int pos = binary(t);
         ans = min(ans , search(t) - calc((line){now[pos] , now[pos + ] - now[pos]} , t));
     }
     cout << ) << ans;
     ;
 }

1038 瞭望塔

1040-1049

1040 骑士

基环树DP,先把链上的统计好,然后环上单独DP。

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = a *  + c - ;
         c = getchar();
     }
     return f ? -a : a;
 }

 ;
  , dp[MAXN][] , dp2[MAXN][][];
 int fa[MAXN] , val[MAXN] , in[MAXN] , N;
 bool vis[MAXN] , inCir[MAXN];
 queue < int > q;

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     freopen("out","w",stdout);
 #endif
     N = read();
      ; i <= N ; ++i){
         val[i] = read();
         dp[i][] += val[i];
         fa[i] = read();
         ++in[fa[i]];
     }
      ; i <= N ; ++i)
         if(!in[i])
             q.push(i);
     while(!q.empty()){
         int t = q.front();
         vis[t] = ;
         q.pop();
         dp[fa[t]][] += max(dp[t][] , dp[t][]);
         dp[fa[t]][] += dp[t][];
         if(!--in[fa[t]])
             q.push(fa[t]);
     }
      ; i <= N ; ++i)
         if(!vis[i]){
             int t = i , p = fa[t];
             vis[t] = ;
             dp2[t][][] = dp[t][];
             dp2[t][][] = dp[t][];
             while(p != i){
                 vis[p] = ;
                 dp2[p][][] = dp[p][] + max(dp2[t][][] , dp2[t][][]);
                 dp2[p][][] = dp[p][] + max(dp2[t][][] , dp2[t][][]);
                 dp2[p][][] = dp[p][] + dp2[t][][];
                 dp2[p][][] = dp[p][] + dp2[t][][];
                 t = p;
                 p = fa[t];
             }
             ans += max(dp2[t][][] , max(dp2[t][][] , dp2[t][][]));
         }
     cout << ans;
     ;
 }

1040 骑士

1041 圆上的整点

看完这个就会了

什么?你说没看过这个考场上遇到了怎么办?爆零呗

 #include<bits/stdc++.h>
 #define int long long
 //This code is written by Itst
 using namespace std;

 signed main(){
     #ifndef ONLINE_JUDGE
     //freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
     #endif
      , N;
     cin >> N;
     ))
         N >>= ;
      ; i * i <= N ; ++i)
         ){
             ;
             ){
                 ++cnt;
                 N /= i;
             }
             ) == )
                 times *= (cnt *  + );
         }
     )
         ) == )
             times = times * ;
     cout << times * 4ll;
     ;
 }

1041 圆上的整点

1042 硬币购物

做完全背包,然后容斥哪一些硬币拿出的数量超过限制(容斥还是很难想到的)

 #include<bits/stdc++.h>
 #define int long long
 using namespace std;

 ] = {} , mon[] , e[] , ans;

 void dfs(int num , int cnt , int sum){
     )
         return;
     ){
         ans += (cnt &  ? - : ) * times[sum];
         return;
     }
     dfs(num +  , cnt , sum);
     dfs(num +  , cnt +  , sum - (e[num] + ) * mon[num]);
 }

 main(){
     ios::sync_with_stdio();
     cin.tie();
     cout.tie();
     int tot;
     cin >> mon[] >> mon[] >> mon[] >> mon[] >> tot;
      ; i <  ; i++)
          ; j <=  - mon[i] ; j++)
             times[j + mon[i]] += times[j];
     while(tot--){
         int s;
         cin >> e[] >> e[] >> e[] >> e[] >> s;
         ans = ;
         dfs( ,  , s);
         cout << ans << endl;
     }
     ;
 }

1042 硬币购物

1044 木棍分割

第一问二分,第二问前缀和优化DP,注意转移点

 #include<bits/stdc++.h>
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))
         c = getchar();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return a;
 }

 ;
 ][] , sum[] , num[] , point[] , N , M;

 bool check(int mid){
      , cnt = ;
      ; i <= N ; i++)
         if(num[i] > mid)
             ;
         else
             if(sum + num[i] <= mid)
                 sum += num[i];
             else{
                 sum = num[i];
                 cnt++;
             }
     return cnt <= M;
 }

 int main(){
     N = read();
     M = read();
      ; i <= N ; i++)
         num[i] = read();
      , R = ;
     while(L < R){
         ;
         check(mid) ? R = mid : L = mid + ;
     }
     printf("%d " , L);
      ; i <= N ; i++)
         sum[i] = sum[i - ] + num[i];
      ; i <= N ; i++)
         dp[][i] = dp[][i - ] + (sum[i] <= L);
      , p = ;
      ; i <= N ; i++){
         while(sum[i] - sum[p] > L)
             p++;
         point[i] = p;
     }
     num = dp[][N] - dp[][N - ];
      ; i <= M ; i++){
         now ^= ;
         memset(dp[now] ,  , sizeof(dp[now]));
         for(int j = i ; j <= N ; j++)
             dp[now][j] = (dp[now][j - ] + dp[now ^ ][j - ] - dp[now ^ ][point[j] - ] + MOD) % MOD;
         num = (num + dp[now][N] - dp[now][N - ] + MOD) % MOD;
     }
     cout << num;
     ;
 }

1044 木棍分割

1045 糖果传递

环形均分纸牌

 #include<bits/stdc++.h>
 using namespace std;
 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))    c = getchar();
     ) + (a << ) + (c ^ ') , c = getchar();
     return a;
 }
 inline int abs(int a){
      ? a : -a;
 }
 ];
 int main(){
     int n = read();
     ;
      ; i <= n ; i++)
         sum += S[i] = read();
     sum /= n;
      ; i <= n ; i++)
         S[i] += S[i - ] - sum;
     sort(S +  , S + n + );
      sum = ;
      ; i <= n ; i++)
         sum += abs(S[i] - S[n +  >> ]);
     printf("%lld" , sum);
     ;
 }

1045 糖果传递

1046 上升序列

DP出每一个数字之后能够接的最长的上升序列的长度,对于每一个询问贪心地选择尽可能前面的数字。

 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<ctime>
 #include<cctype>
 #include<algorithm>
 #include<cstring>
 #include<iomanip>
 #include<queue>
 #include<map>
 #include<set>
 #include<bitset>
 #include<stack>
 #include<vector>
 #include<cmath>
 #define INF 0x3f3f3f3f
 #define int long long
 #define PII pair < int , int >
 #define st first
 #define nd second
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ] , maxN[] , num[] , N , cnt;

 signed main(){
 #ifndef ONLINE_JUDGE
     //freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     N = read();
     maxN[] = 1e9;
      ; i <= N ; ++i)
         num[i] = read();
     for(int i = N ; i ; --i){
          , R = cnt;
         while(L < R){
             ) >> ;
             maxN[mid] > num[i] ? L = mid : R = mid - ;
         }
         dp[i] = L + ;
         if(L == cnt)
             ++cnt;
         maxN[L + ] = num[i];
     }
     for(int M = read() ; M ; --M){
         int L = read();
         if(cnt < L)
             puts("Impossible");
         else{
             ;
              ; i <= N && L ; ++i)
                 if(dp[i] >= L && num[bef] < num[i]){
                     cout << num[i] << ' ';
                     bef = i;
                     --L;
                 }
             putchar('\n');
         }
     }
     ;
 }

1046 上升序列

1047 理想的正方形

二维ST表or二维单调队列

 #include<bits/stdc++.h>
 using namespace std;
 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))    c = getchar();
     ) + (a << ) + (c ^ ') , c = getchar();
     return a;
 }
 ][][][] , N , lgN , a , b , poww[] = {};
 inline int max(int a , int b){return a > b ? a : b;}
 inline int min(int a , int b){return a < b ? a : b;}
 int main(){
      ; i <  ; i++)    poww[i] = poww[i - ] << ;
     a = read();    b = read();    N = read();
     lgN = log(N) / log();
      ; i <= a ; i++)
          ; j <= b ; j++)
             ST[i][j][][] = ST[i][j][][] = read();
      ; k <= lgN ; k++)
          ; i <= a - poww[k] +  ; i++)
              ; j <= b - poww[k] +  ; j++){
                 ST[i][j][k][] = max(ST[i][j][k - ][] , max(ST[i][j + poww[k - ]][k - ][] , max(ST[i + poww[k - ]][j + poww[k - ]][k - ][] , ST[i + poww[k - ]][j][k - ][])));
                 ST[i][j][k][] = min(ST[i][j][k - ][] , min(ST[i][j + poww[k - ]][k - ][] , min(ST[i + poww[k - ]][j + poww[k - ]][k - ][] , ST[i + poww[k - ]][j][k - ][])));
             }
     ;
      ; i <= a - N +  ; i++)
          ; j <= b - N +  ; j++)
             minT = min(minT , max(max(max(ST[i][j][lgN][] , ST[i][j + N - poww[lgN]][lgN][]) , ST[i + N - poww[lgN]][j + N - poww[lgN]][lgN][]) , ST[i + N - poww[lgN]][j][lgN][])
             - min(min(min(ST[i][j][lgN][] , ST[i][j + N - poww[lgN]][lgN][]) , ST[i + N - poww[lgN]][j + N - poww[lgN]][lgN][]) , ST[i + N - poww[lgN]][j][lgN][]));
     cout << minT;
     ;
 }

1047 理想的正方形 二维ST表

 #include<bits/stdc++.h>
 using namespace std;
 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))    c = getchar();
     ) + (a << ) + (c ^ ') , c = getchar();
     return a;
 }
 ][];
 deque < ][];
 inline int min(int a , int b){return a < b ? a : b;}
 int main(){
     ;
     a = read();    b = read();    n = read();
      ; i <= a ; i++){
         deque < ];
          ; j <= b ; j++){
             num[i][j] = read();
              ; p <=  ; p++){
                 if(i - q[j][p].front() == n)    q[j][p].pop_front();
                 while(!q[j][p].empty() && (p ^ (num[q[j][p].back()][j] <= num[i][j])))
                     q[j][p].pop_back();
                 q[j][p].push_back(i);
                 if(j - Q[p].front() == n)    Q[p].pop_front();
                 while(!Q[p].empty() && (p ^ (num[q[Q[p].back()][p].front()][Q[p].back()] <= num[q[j][p].front()][j])))
                     Q[p].pop_back();
                 Q[p].push_back(j);
             }
             if(i >= n && j >= n)
                 minT = min(minT , num[q[Q[].front()][].front()][Q[].front()] - num[q[Q[].front()][].front()][Q[].front()]);
         }
     }
     cout << minT;
     ;
 }

1047 理想的正方形 二维单调队列

1048 分割矩阵

记忆化搜索

 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<ctime>
 #include<cctype>
 #include<algorithm>
 #include<cstring>
 #include<iomanip>
 #include<queue>
 #include<map>
 #include<set>
 #include<bitset>
 #include<stack>
 #include<vector>
 #include<cmath>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = a *  + c - ;
         c = getchar();
     }
     return f ? -a : a;
 }

 ][][][][] , sum[][] , N , M , K;
 ][][][][];

 inline int calc(int x1 , int y1 , int x2 , int y2){
     ][y2] - sum[x2][y1 - ] + sum[x1 - ][y1 - ];
 }

 int dfs(int x1 , int y1 , int x2 , int y2 , int k){
     if(vis[x1][y1][x2][y2][k])
         return dp[x1][y1][x2][y2][k];
     vis[x1][y1][x2][y2][k] = ;
     if(!k)
         return dp[x1][y1][x2][y2][k] = calc(x1 , y1 , x2 , y2) * calc(x1 , y1 , x2 , y2);
     dp[x1][y1][x2][y2][k] = 0x3f3f3f3f;
     for(int i = x1 ; i < x2 ; ++i)
          ; j < k ; ++j)
             dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k] , dfs(x1 , y1 , i , y2 , j) + dfs(i +  , y1 , x2 , y2 , k -  - j));
     for(int i = y1 ; i < y2 ; ++i)
          ; j < k ; ++j)
             dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k] , dfs(x1 , y1 , x2 , i , j) + dfs(x1 , i +  , x2 , y2 , k -  - j));
     return dp[x1][y1][x2][y2][k];
 }

 signed main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     //freopen("out","w",stdout);
 #endif
     N = read();
     M = read();
     K = read();
      ; i <= N ; ++i)
          ; j <= M ; ++j)
             sum[i][j] = sum[i - ][j] + sum[i][j - ] - sum[i - ][j - ] + read();
     long double s = sum[N][M] * 1.0 / K;
     cout << ) << sqrt(( ,  , N , M , K - ) -  * sum[N][M] * s + K * s * s) / K);
     ;
 }

1048 分割矩阵

1050-1059

1050 旅行

枚举最小边,从小到大加边,并查集维护连通性

 #include<bits/stdc++.h>
 #define inf 0x7fffffff
 using namespace std;

 struct Edge{
     int start , end , w;
 }Ed[];

 ] , N , M , S , T , ansMax = inf , ansMin = ;

 bool cmp(Edge a , Edge b){
     return a.w < b.w;
 }

 inline int gcd(int a , int b){
     int t = a % b;
     while(t){
         a = b;
         b = t;
         t = a % b;
     }
     return b;
 }

 inline void init(){
      ; i <= N ; i++)
         fa[i] = i;
 }

 int find(int x){
     return fa[x] == x ? x : (fa[x] = find(fa[x]));
 }

 int check(int num){
     init();
     while(num <= M){
         int p = find(Ed[num].start) , q = find(Ed[num].end);
         fa[p] = q;
         if(find(S) == find(T))
             break;
         num++;
     }
     return num;
 }

 int main(){
     cin >> N >> M;
      ; i <= M ; i++)
         cin >> Ed[i].start >> Ed[i].end >> Ed[i].w;
     cin >> S >> T;
     sort(Ed +  , Ed + M +  , cmp);
      ; i <= M ; i++){
         int t = check(i);
         )
             break;
         int nowMax = Ed[t].w , nowMin = Ed[i].w;
         if((double)ansMax / ansMin > (double)nowMax / nowMin){
             ansMax = nowMax;
             ansMin = nowMin;
         }
     }
     if(ansMax / ansMin == inf)
         cout << "IMPOSSIBLE";
     else{
         int t = gcd(ansMax , ansMin);
         cout << ansMax / t;
         if(ansMin != t)
             cout << "/" << ansMin / t;
     }
     ;
 }

1050 旅行

1051 受欢迎的牛

缩点,检查是否为连通DAG且是否有唯一入点,不满足答案为0,满足答案为唯一入点的size

 #include<bits/stdc++.h>
 using namespace std;
 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))    c = getchar();
     ) + a + (c ^ ') , c = getchar();
     return a;
 }
 inline int min(int a , int b){
     return a < b ? a : b;
 }
 ] , dfn[] , low[] , ts , inSCC[] , sizeSCC[] , headStack , headSCC;
 ] , inStack[] , outSCC[];
 vector < ];
 void dfs(int a){
     low[a] = dfn[a] = ++ts;
     Stack[++headStack] = a;
     vis[a] = inStack[a] = ;
      ; i < Ed[a].size() ; i++){
         if(!vis[Ed[a][i]])    dfs(Ed[a][i]);
         else    if(!inStack[a])    continue;
         low[a] = min(low[a] , low[Ed[a][i]]);
     }
     if(low[a] == dfn[a]){
         headSCC++;
         do{
             inStack[Stack[headStack]] = ;
             inSCC[Stack[headStack]] = headSCC;
             sizeSCC[headSCC]++;
         }while(Stack[headStack--] != a);
     }
 }
 int main(){
     for(int M = read() ; M ; M--){
         int a = read() , b = read();
         Ed[a].push_back(b);
     }
      ; i <= N ; i++)    if(!vis[i])    dfs(i);
      ; i <= N ; i++)
          ; !outSCC[inSCC[i]] && j < Ed[i].size() ; j++)
             outSCC[inSCC[i]] = inSCC[Ed[i][j]] != inSCC[i];
     ;
      ; i <= headSCC ; i++)
         if(!outSCC[i]){
             if(!ans)    ans = sizeSCC[i];
             else{
                 cout << ;
                 ;
             }
         }
     cout << ans;
     ;
 }

1051 受欢迎的牛

1053 反素数

由剪枝:答案分解出的质因数一定是$2,3,5,7,11,13,17,19,23,29$这十个质因数中的前若干个,而且次数一定递减,这样可以大大减少搜索时间。

 #include<bits/stdc++.h>
 using namespace std;
 ,,,,,,,,,};
 long long maxN , N , maxYS;
 inline int max(int a , int b){
     return a > b ? a : b;
 }
 void dfs(int k , long long now , int bef , long long q){
     ){
         if(maxYS < q || maxYS == q && maxN > now){
             maxYS = q;
             maxN = now;
         }
         return;
     }
     ;
     while(now <= N && cou <= bef){
         dfs(k +  , now , cou , q * (cou + ));
         cou++;
         now *= dir[k];
     }
 }
 int main(){
     cin >> N;
     dfs( ,  ,  , );
     cout << maxN;
     ;
 }

1053 反素数

1054 移动玩具

压缩状态+BFS

 #include<bits/stdc++.h>
 using namespace std;
 ] = { , } , bef[];
 int main(){
     string s;
      , tar = ;
      ; i >=  ; i--){
         cin >> s;
          ; j >=  ; j--)
             now += (s[ - j] -  << (i << ) + j);
     }
      ; i >=  ; i--){
         cin >> s;
          ; j >=  ; j--)
             tar += (s[ - j] -  << (i << ) + j);
     }
     if(now == tar){
         cout << ;
         ;
     }
     queue < pair < int , int > > q;
     q.push(make_pair(now , ));
     bef[now] = -;
     while(!q.empty()){
         pair < int , int > t = q.front();
         q.pop();
         t.second++;
          ; i <  ; i++)
              ; j <  ; j++)
                  && !(j ==  && i %  == ) && (( << i + dir[j])) ^ ( << i))))){
                      << i) + ( << i + dir[j]);
                     if(!bef[m]){
                         bef[m] = t.first;
                         if(m == tar){
                             cout << t.second;
                             ;
                         }
                         q.push(make_pair(m , t.second));
                     }
                 }
     }
     ;
 }

1054 移动玩具

1055 玩具取名

设$dp_{i,j,k}$表示区间$[i,j]$是否能缩为字母$k$,转移枚举中间点,$O(800^3)$竟然能过

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ] , L;
 ][][] , cg[][][];
 ];

 inline int toInt(char c){
     switch(c){
     case 'W':
         ;
     case 'I':
         ;
     case 'N':
         ;
     case 'G':
         ;
     }
 }

 inline char getc(){
     char c = getchar();
     while(!isupper(c))
         c = getchar();
     return c;
 }

 void input(){
      ; i <  ; ++i)
         num[i] = read();
      ; i <  ; ++i)
          ; j <= num[i] ; ++j){
             char a = getc() , b = getc();
             cg[toInt(a)][toInt(b)][i] = ;
         }
     scanf();
     L = strlen(s + );
      ; i <= L ; ++i)
         dp[i][i][toInt(s[i])] = ;
 }

 void work(){
      ; i ; --i)
          ; j <= L ; ++j)
             for(int k = i ; k < j ; ++k)
                  ; p <  ; ++p)
                     if(dp[i][k][p])
                         ; q <  ; ++q)
                            ][j][q])
                                 ; r <  ; ++r)
                                    if(cg[p][q][r])
                                        dp[i][j][r] = ;
 }

 char toChar(int c){
     switch(c){
     :
         return 'W';
     :
         return 'I';
     :
         return 'N';
     :
         return 'G';
     }
 }

 void output(){
     ;
      ; i <  ; ++i)
         ][L][i]){
             f = ;
             putchar(toChar(i));
         }
     if(!f)
         puts("The name is wrong!");
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     input();
     work();
     output();
     ;
 }

1055 玩具取名

1056 排名系统

把名字Hash掉,然后使用Splay维护。插入的时候相同权值的人排名按照插入时间从小到大,即插入/更新时间较后的人排名较高。

一定要注意:不要偷懒,下面“错误的输出”写法会TLE,应该直接把对应区间框出来然后输出

然后哨兵节点可能要开到INT_MAX

 ;
 void output(int x){
     if(!x) return;
     output(lch);
      || !(Tree[x].val + )) return;
     lltoS(name[x]);
     ) return;
     output(rch);
 }

 void out(int x){
     nm = ;
     find(rt , x -  , );
     output(Tree[rt].ch[]);
 }

错误的输出

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<map>
 //This code is written by Itst
 using namespace std;

 #define ll long long
 ;
 int N , cnt;
 ll val , name[MAXN];
 ];
 map < ll , int > app;

 #define rt Tree[0].ch[0]
 struct node{
     ] , sz;
     ll val;
 }Tree[MAXN];
 #define lch Tree[x].ch[0]
 #define rch Tree[x].ch[1]

 inline ll Stoll(){
     ll cur = ;
     int l = strlen(s);
      ; i < l ; ++i)
         cur = cur *  + s[i] - ;
     return cur;
 }

 inline void lltoS(ll num){
      ; i <  ; ++i){
         s[i] = num % ;
         num /= ;
     }
      ; i >=  ; --i)
         );
     putchar(' ');
 }

 inline ] == x;}

 inline ;}

 inline void rot(int x){
     bool f = son(x);
     ];
     Tree[x].fa = z; Tree[z].ch[son(y)] = x;
     Tree[x].ch[f ^ ] = y; Tree[y].fa = x;
     Tree[y].ch[f] = w; if(w) Tree[w].fa = y;
     up(y);
 }

 void splay(int x , int tar){
     while(Tree[x].fa != tar){
         if(Tree[Tree[x].fa].fa != tar)
             rot(son(x) == son(Tree[x].fa) ? Tree[x].fa : x);
         rot(x);
     }
     up(x);
 }

 void find(int x , int K , int tar){
     if(Tree[lch].sz == K) splay(x , tar);
     else if(Tree[lch].sz > K) find(lch , K , tar);
      , tar);
 }

 void ins(int &x , ll val , int fa){
     if(!x){
         Tree[x = cnt].fa = fa; Tree[x].val = val;
         splay(x , ); return;
     }
     ins(Tree[x].ch[Tree[x].val >= val] , val , x);
 }

 void del(int x){
     splay(x , );
     find(rt , Tree[lch].sz +  , rt);
     Tree[rt = rch].fa = ;
     Tree[Tree[rch].ch[] = lch].fa = rch;
 }

 ); return Tree[lch].sz;}

 void output(int x){
     if(!x) return;
     output(lch);
     lltoS(name[x]);
     output(rch);
 }

 void out(int x){
     find(rt , x -  , );
     find(rt , min(x +  , Tree[rt].sz - ) , rt);
     output(Tree[Tree[rt].ch[]].ch[]);
 }

 inline char getc(){
     char c = getchar();
     while(c == ' ' || c == '\n' || c == '\r')
         c = getchar();
     return c;
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     freopen("out","w",stdout);
 #endif
     cnt = ; ins(rt , 1e18 , );
     cnt = ; ins(rt , - , );
     for(scanf("%d" , &N) ; N ; --N)
         if(getc() == '+'){
             scanf("%s %lld" , s , &val);
             if(app.count(name[++cnt] = Stoll())) del(app[name[cnt]]);
             app[name[cnt]] = cnt;
             ins(rt , val , );
         }
         else{
             scanf("%s" , s);
             ]))
                 printf("%d\n" , getRk(app[Stoll()]));
             else{
                  , l = strlen(s);
                  ; i < l ; ++i)
                     num = num *  + s[i] - ;
                 out(num);
                 putchar('\n');
             }
         }
     ;
 }

1056 排名系统

1057 棋盘制作

第一问最大正方形简单的DP,第二问悬线法+单调栈

话说在Luogu上$O(n^3)$算法能AC,但BZOJ上会TLE(坑了我两次提交)

 #include<bits/stdc++.h>
 using namespace std;
 inline int read(){
     ;
     /*char c = getchar();
     while(!isdigit(c))  c = getchar();
     while(isdigit(c))   a = (a << 3) + (a << 1) + (c ^ '0') , c = getchar();*/
     scanf("%d" , &a);
     return a;
 }
 inline int min(int a , int b){
     return a < b ? a : b;
 }
 inline int max(int a , int b){
     return a > b ? a : b;
 }
 ][];
 ][] , zhan[][] , len[][];
 int main(){
      , maxN2 =  , head =  , N = read() , M = read();
      ; i <= N ; ++i)
          ; j <= M ; ++j){
             vis[i][j] = read();
             DP[i][j] = ;
              && j -  && !(vis[i - ][j - ] ^ vis[i][j]))
                 ][j] ^ vis[i][j]) && (vis[i][j - ] ^ vis[i][j]))
                     DP[i][j] += min(DP[i - ][j] , min(DP[i - ][j - ] , DP[i][j - ]));
             maxN1 = max(maxN1 , DP[i][j]);
         }
     printf("%d\n" , maxN1 * maxN1);
      ; i <= N ; i++)
          ; j <=  ; j++){
              ; k <= M ; k++)
             {
                 ;
                 ))
                     len[k][j]++;
                 else
                     len[k][j] = ;
                 int a = len[k][j];
                 ] > a){
                     maxN2 = max(maxN2 , zhan[head][] * (zhan[head][] + wid));
                     wid += zhan[head--][];
                 }
                 zhan[++head][] = a;
                 zhan[head][] = wid + ;
             }
             while(head){
                 maxN2 = max(maxN2 , zhan[head][] * zhan[head][]);
                 zhan[head - ][] += zhan[head][];
                 --head;
             }
         }
     printf("%d" , maxN2);
     ;
 }

1057 棋盘制作

1058 报表统计

MIN_GAP使用懒惰堆,MIN_SORT_GAP使用平衡树做邻值查找

这题竟然有负数数据

 #include<bits/stdc++.h>
 #define MAXN 500001
 using namespace std;
 inline int read(){
     ;
     ;
     char c = getchar();
     while(!isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }
 ];
 inline void print(int x){
     ;
     )
         fwrite( , stdout);
     else{
         while(x){
                output[--dirN] = x %  + ;
             x /= ;
         }
         fwrite(output + dirN ,  , strlen(output + dirN) , stdout);
     }
     fwrite( ,  , stdout);
 }

 struct Node{
     ] , num;
 }Tree[MAXN << ];
  , N , root = ;
 ];
 priority_queue < int , vector < int > , greater < int > > q , erase;

 inline int abs(int a){
      ? a : -a;
 }

 inline int min(int a , int b){
     return a < b ? a : b;
 }

 inline bool son(int dir){
     ] == dir;
 }

 inline void ZigZag(int dir){
     bool f = son(dir);
     if(Tree[dir].fa == root)
         root = dir;
     Tree[Tree[dir].son[!f]].fa = Tree[dir].fa;
     Tree[Tree[dir].fa].son[f] = Tree[dir].son[!f];
     int x = Tree[Tree[dir].fa].fa;
     Tree[x].son[son(Tree[dir].fa)] = dir;
     Tree[dir].son[!f] = Tree[dir].fa;
     Tree[Tree[dir].fa].fa = dir;
     Tree[dir].fa = x;
 }

 inline void Splay(int dir){
     while(root != dir)
         if(Tree[dir].fa == root)
             ZigZag(dir);
         else{
             if(son(Tree[dir].fa) == son(dir))
                 ZigZag(Tree[dir].fa);
             else
                 ZigZag(dir);
             ZigZag(dir);
         }
 }

 inline void calcMinAll(){
     ];
     if(t){
         ])
             t = Tree[t].son[];
         minAll = min(minAll , Tree[root].num - Tree[t].num);
     }
     t = Tree[root].son[];
     if(t){
         ])
             t = Tree[t].son[];
         minAll = min(minAll , Tree[t].num - Tree[root].num);
     }
 }

 void insert(int num , int &dir , int fa){
     if(!dir){
         dir = ++cntNode;
         Tree[dir].num = num;
         Tree[dir].fa = fa;
         Splay(dir);
         calcMinAll();
         return;
     }
     if(Tree[dir].num == num)
         minAll = ;
     else
         insert(num , Tree[dir].son[Tree[dir].num < num] , dir);
 }

 int main(){
     N = read();
     int M = read();
     num[] = Tree[].num = read();
      ; i <= N ; i++){
         start[i] = num[i] = read();
         if(minAll)
             if(Tree[root].num == num[i])
                 minAll = ;
             else
                 insert(num[i] , Tree[root].son[Tree[root].num < num[i]] , root);
         q.push(abs(num[i] - num[i - ]));
     }
     while(M--){
         scanf("%s" , s);
         ] == 'I'){
             int a = read() , b = read();
             if(a - N){
                 erase.push(abs(num[a] - start[a + ]));
                 while(!erase.empty() && erase.top() == q.top()){
                     erase.pop();
                     q.pop();
                 }
                 q.push(abs(b - start[a + ]));
             }
             q.push(abs(b - num[a]));
             num[a] = b;
             if(minAll)
                 insert(b , Tree[root].son[Tree[root].num < b] , root);
         }
         else
             ] == 'G')
                 print(q.top());
             else
                 print(minAll);
     }
     ;
 }

1058 报表统计

1059 矩阵游戏

考虑到要满足题设条件需要存在$N$个黑块覆盖了所有行和列,于是在所有黑块的行和列之间连一条边,跑完美匹配即可

 #include<bits/stdc++.h>
 using namespace std;
 struct Edge{
     int end , upEd;
 }Ed[];
 ] , match[] , cntEd;
 ];

 inline void add(int a , int b){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     head[a] = cntEd;
 }

 bool dfs(int dir){
     for(int i = head[dir] ; i ; i = Ed[i].upEd)
         if(!vis[Ed[i].end]){
             vis[Ed[i].end] = ;
             if(!match[Ed[i].end] || dfs(match[Ed[i].end])){
                 match[Ed[i].end] = dir;
                 ;
             }
         }
     ;
 }

 int main(){
     int T;
     for(cin >> T ; T ; T--){
         memset(head ,  , sizeof(head));
         memset(match ,  , sizeof(match));
         cntEd = ;
         int N;
         cin >> N;
          ; i <= N ; i++)
              ; j <= N ; j++){
                 int a;
                 cin >> a;
                 if(a)
                     add(i , j);
             }
         ;
          ; f && i <= N ; i++){
             memset(vis ,  , sizeof(vis));
             f = dfs(i);
         }
         cout << (f ? "Yes" : "No") << endl;
     }
     ;
 }

1059 矩阵游戏

1060-1069

1060 时态同步

贪心+树形DP,每一次把对应节点的所有儿子改成同一时间即可

 #include<bits/stdc++.h>
 #define MAXN 500001
 using namespace std;
 inline int read(){
     ;
     ;
     char c;
     fread(&c ,  , stdin);
     while(!isdigit(c)){
         ;
         fread(&c ,  , stdin);
     }
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         fread(&c ,  , stdin);
     }
     return f ? -a : a;
 }
 struct Edge{
     int end , upEd , t;
 }Ed[MAXN << ];
 int head[MAXN] , size[MAXN] , minT[MAXN] , cntEd;
 bool vis[MAXN];

 inline int max(int a , int b){return a > b ? a : b;}

 inline void add(int a , int b , int c){
     Ed[++cntEd].end = b;
     Ed[cntEd].t = c;
     Ed[cntEd].upEd = head[a];
     head[a] = cntEd;
 }
 long long dfs(int dir){
     ;
     vis[dir] = ;
     for(int i = head[dir] ; i ; i = Ed[i].upEd)
         if(!vis[Ed[i].end]){
             sum += dfs(Ed[i].end);
             if(minT[Ed[i].end] + Ed[i].t >= minT[dir])
                 sum += (minT[Ed[i].end] + Ed[i].t - minT[dir]) * size[dir];
             else
                 sum += (-minT[Ed[i].end] - Ed[i].t + minT[dir]);
             minT[dir] = max(minT[dir] , minT[Ed[i].end] + Ed[i].t);
             size[dir]++;
         }
     return sum;
 }

 int main(){
     int N = read() , S = read();
      ; i < N ; i++){
         int a = read() , b = read() , c = read();
         add(a , b , c);
         add(b , a , c);
     }
     cout << dfs(S);
     ;
 }

1060 时态同步

1061 志愿者招募

Here

1063 道路设计

Here

1064 假面舞会

Here

1066 蜥蜴

这种很多人一起跑要求时间最小的题目很多时候使用网络流解决

 #include<bits/stdc++.h>
 #define INF 0x3f3f3f3f
 #define id(i , j) ((i - 1) * C + j)
 //This code is written by Itst
 using namespace std;

  , MAXM = ;
 struct Edge{
     int end , upEd , f , c;
 }Ed[MAXM];
 int head[MAXN] , cur[MAXN] , dep[MAXN];
 ;
 queue < int > q;

 inline ){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     Ed[cntEd].f = c;
     Ed[cntEd].c = d;
     head[a] = cntEd;
 }

 inline bool bfs(){
     while(!q.empty())
         q.pop();
     q.push(S);
     memset(dep ,  , sizeof(dep));
     dep[S] = ;
     while(!q.empty()){
         int t = q.front();
         q.pop();
         for(int i = head[t] ; i ; i = Ed[i].upEd)
             if(Ed[i].f && !dep[Ed[i].end]){
                 dep[Ed[i].end] = dep[t] + ;
                 if(Ed[i].end == T){
                     memcpy(cur , head , sizeof(head));
                     ;
                 }
                 q.push(Ed[i].end);
             }
     }
     ;
 }

 inline int dfs(int x , int mF){
     if(x == T)
         return mF;
     ;
     for(int &i = cur[x] ; i ; i = Ed[i].upEd)
         ){
             int t = dfs(Ed[i].end , min(mF - sum , Ed[i].f));
             if(t){
                 Ed[i].f -= t;
                 Ed[i ^ ].f += t;
                 sum += t;
                 if(sum == mF)
                     break;
             }
         }
     return sum;
 }

 int Dinic(){
     ;
     while(bfs())
         ans += dfs(S , INF);
     return ans;
 }

 inline char getc(){
     char c = getchar();
     while(c == ' ' || c == '\n' || c == '\r')
         c = getchar();
     return c;
 }

 void input(){
     cin >> R >> C >> D;
     T = R * C *  + ;
      ; i <= R ; ++i)
          ; j <= C ; ++j){
             addEd(id(i , j) , id(i , j) + R * C , getc() - );
             addEd(id(i , j) + R * C , id(i , j) , );
         }
      ; i <= R ; ++i)
          ; j <= C ; ++j)
             if(getc() == 'L'){
                 addEd(S , id(i , j) , );
                 addEd(id(i , j) , S , );
                 ++M;
             }
      ; i <= R ; ++i)
          ; j <= C ; ++j){
              , i) , min(C - j +  , j)) <= D){
                 addEd(T , id(i , j) + R * C , );
                 addEd(id(i , j) + R * C , T , INF);
             }
              ; p <= R ; ++p)
                  ; q <= C ; ++q)
                     if(i != p || j != q)
                          <= D){
                             addEd(id(i , j) + R * C , id(p , q) , INF);
                             addEd(id(p , q) , id(i , j) + R * C , );
                         }
         }
 }

 void work(){
     cout << M - Dinic();
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     input();
     work();
     ;
 }

1066 蜥蜴

1067 降雨量

ST表+离散化,两个不相邻的年份之间要加上一个空缺表示没有信息的年份,分类讨论有点多

 #include<bits/stdc++.h>
 #define MAXN 100002
 using namespace std;
 inline int read(){
     ;
     ;
     char c = getchar();
     while(!isdigit(c)){
         ;
         c = getchar();
     }
     ) + (a << ) + (c ^ ') , c = getchar();
     return f ? -a : a;
 }
 inline int max(int a , int b){
     return a > b ? a : b;
 }
 ];
 ];
 inline int Query(int a , int b){
     if(a > b)
         ;
     )] , ST[b - ( << ()) + ][()]);
 }
 inline bool ifNeighbor(int a , int b){
     )] && ifNei[b - ( << ()) + ][()];
 }
 int main(){
     int N = read();
      ; i <= N ; i++){
         num[i] = read();
         ST[i][] = read();
         ifNei[i][] = num[i] - num[i - ] == ;
     }
      ; ( << i) <= N ; i++)
          ; j + ( << i) -  <= N ; j++){
             ST[j][i] = max(ST[j][i - ] , ST[j + ( << i - )][i - ]);
             ifNei[j][i] = ifNei[j][i - ] && ifNei[j + ( << i - )][i - ];
         }
     for(int M = read() ; M ; M--){
         ;
         if(a > b){
             fwrite( ,  , stdout);
             continue;
         }
         if(a == b){
             fwrite( ,  , stdout);
             continue;
         }
          , num + N +  , a) - num , t2 = lower_bound(num +  , num + N +  , b) - num;
         if(num[t2] != b){
             t2--;
             f++;
         }
         if(num[t1] != a)
             f -= ;
         switch(f){
             :
                 fwrite( ,  , stdout);
                 break;
             :
                 ] && Query(t1 +  , t2) != ST[t1][])
                     fwrite( ,  , stdout);
                 else
                     fwrite( ,  , stdout);
                 break;
             :
                 ] && Query(t1 , t2 - ) != ST[t2][])
                     fwrite( ,  , stdout);
                 else
                     fwrite( ,  , stdout);
                 break;
             default:
                 ] >= ST[t2][] && Query(t1 +  , t2) == ST[t2][] && Query(t1 +  , t2 - ) < ST[t2][])
                      , t2))
                         fwrite( ,  , stdout);
                     else
                         fwrite( ,  , stdout);
                 else
                     fwrite( ,  , stdout);
         }
         fwrite( , sizeof(char) , stdout);
     }
     ;
 }
 

1067 降雨量

1068 压缩

想知道std是不是什么$O(n^4)$或者$O(n^5)$的神仙算法……

设$f_{i,j}$表示压缩了串的前$i$个字符,在解压过程中缓冲串为$s_{j,i}$的最小步数,转移枚举放$R$、放$s_i$、放$M$之后放$s_i$

 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<ctime>
 #include<cctype>
 #include<algorithm>
 #include<cstring>
 #include<iomanip>
 #include<queue>
 #include<map>
 #include<set>
 #include<bitset>
 #include<stack>
 #include<vector>
 #include<cmath>
 //This code is written by Itst
 using namespace std;

 ][] , N;
 string s;

 signed main(){
 #ifndef ONLINE_JUDGE
     //freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     cin >> s;
     N = s.size();
     s = " " + s;
     dp[][] = ;
      ; i <= N ; ++i){
          ; j ; --j){
             dp[i][j] = dp[i - ][j] + ;
             ) &&  - j + ) ==  +  , (i + j) /  - j + ))
                 dp[i][j] = min(dp[i][j] , dp[(i + j) / ][j] + );
         }
         dp[i][i] = 1e9;
          ; j < i ; ++j)
             dp[i][i] = min(dp[i][i] , dp[i - ][j]);
         dp[i][i] += ;
     }
     int ans = 1e9;
      ; i <= N ; ++i)
         ans = min(ans , dp[N][i]);
     cout << ans;
     ;
 }

1068 压缩

1069 最大土地面积

Here

1070-1079

1072 排列

暴搜……

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 string s;
 ];

 void dfs(int cur , long long t){
     if(cur > l)
         cnt += t % k == ;
      ; i <  ; ++i)
         if(times[i]){
             --times[i];
             dfs(cur +  , t *  + i);
             ++times[i];
         }
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     freopen("out","w",stdout);
 #endif
     int T;
     for(cin >> T ; T ; --T){
         cin >> s >> k;
         memset(times ,  , sizeof(times));
         cnt = ;
         l = s.size();
          ; i < l ; ++i)
             ++times[s[i] - '];
         dfs( , );
         cout << cnt << endl;
     }
     ;
 }

1072 排列

1073 K短路

A*,每一次将一个状态放入堆中的时候检查当前这个状态是否能够到达终点进行剪枝,这样竟然就能跑得很快……

还有一种奇怪的剪枝:将估价函数定为当前状态到终点的最短路,用平衡树代替堆,当平衡树中点数$> K$时将最后一个决策删掉

但似乎上面这种方法TLE得不行……

 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<ctime>
 #include<cctype>
 #include<algorithm>
 #include<cstring>
 #include<iomanip>
 #include<queue>
 #include<map>
 #include<set>
 #include<bitset>
 #include<stack>
 #include<vector>
 #include<cmath>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = a *  + c - ;
         c = getchar();
     }
     return f ? -a : a;
 }

 struct Edge{
     int end , upEd , w;
 }Ed[] , fan[];
 struct zt{
     string s;
     int dis , qw;
     long long clc;
     bool operator <(const zt a)const{
         return qw == a.qw ? s > a.s : qw > a.qw;
     }
 }now;
 priority_queue < zt > all;
 ] , head[] , hFan[];
 int N , M , K , A , B , cntEd , cntFan;
 queue < int > q;
 ];

 inline void addEd(Edge* Ed , int* head , int& cntEd , int a , int b , int c){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     Ed[cntEd].w = c;
     head[a] = cntEd;
 }

 void SPFA(){
     memset(dis , 0x3f , sizeof(dis));
     dis[B] = ;
     q.push(B);
     while(!q.empty()){
         int t = q.front();
         q.pop();
         vis[t] = ;
         for(int i = hFan[t] ; i ; i = fan[i].upEd)
             if(dis[fan[i].end] > dis[t] + fan[i].w){
                 dis[fan[i].end] = dis[t] + fan[i].w;
                 if(!vis[fan[i].end]){
                     vis[fan[i].end] = ;
                     q.push(fan[i].end);
                 }
             }
     }
 }

 inline bool chk(zt now){
     ];
     if(t == B)
         ;
     long long clc = now.clc;
     while(!q.empty())
         q.pop();
     q.push(t);
     while(!q.empty()){
         t = q.front();
         q.pop();
         for(int i = head[t] ; i ; i = Ed[i].upEd)
             if(!(clc & (1ll << Ed[i].end))){
                 clc |= 1ll << Ed[i].end;
                 if(Ed[i].end == B)
                     ;
                 q.push(Ed[i].end);
             }
     }
     ;
 }

 inline void ist(zt now){
     if(chk(now))
         all.push(now);
 }

 void Astar(){
     ist((zt){ , A) ,  , dis[A] , 1ll << A});
     while(!all.empty()){
         now = all.top();
         all.pop();
         ];
         if(t == B){
             if(!--K){
                  ; i < now.s.size() ; ++i){
                     if(i)
                         putchar('-');
                     cout << (int)now.s[i];
                 }
                 exit();
             }
             continue;
         }
         for(int i = head[t] ; i ; i = Ed[i].upEd)
             if(!(now.clc & (1ll << Ed[i].end)) && dis[Ed[i].end] != 0x3f3f3f3f)
                 ist(zt{now.s +  , Ed[i].end) , now.dis + Ed[i].w , now.dis + Ed[i].w + dis[Ed[i].end] , now.clc | (1ll << Ed[i].end)});
     }
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     //freopen("out","w",stdout);
 #endif
     N = read();
     M = read();
     K = read();
     A = read();
     B = read();
      ; i <= M ; ++i){
         int a = read() , b = read() , c = read();
         addEd(Ed , head , cntEd , a , b , c);
         addEd(fan , hFan , cntFan , b , a , c);
     }
     SPFA();
     Astar();
     puts("No");
     ;
 }

1073 K短路 A*

 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<ctime>
 #include<cctype>
 #include<algorithm>
 #include<cstring>
 #include<iomanip>
 #include<queue>
 #include<map>
 #include<set>
 #include<bitset>
 #include<stack>
 #include<vector>
 #include<cmath>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = a *  + c - ;
         c = getchar();
     }
     return f ? -a : a;
 }

 struct Edge{
     int end , upEd , w;
 }Ed[];
 struct zt{
     string s;
     int dis , qw;
     long long clc;
     bool operator <(const zt a)const{
         return qw == a.qw ? s < a.s : qw < a.qw;
     }
 }now;
 set < zt > all;
 ] , N , M , K , A , B , cntEd;
 ];

 inline void addEd(int a , int b , int c){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     Ed[cntEd].w = c;
     head[a] = cntEd;
 }

 #define PII pair < int , int >
 #define st first
 #define nd second
 priority_queue < PII > q1;
 inline bool chk(zt& now){
     ];
     long long clc = now.clc;
     while(!q1.empty())
         q1.pop();
     q1.push(PII( , t));
     while(!q1.empty()){
         PII x = q1.top();
         q1.pop();
         if(clc & (1ll << x.nd))
             continue;
         clc |= 1ll << x.nd;
         if(x.nd == B){
             now.qw = now.dis + -x.st;
             now.clc |= 1ll << t;
             ;
         }
         for(int i = head[x.nd] ; i ; i = Ed[i].upEd)
             if(!(clc & (1ll << Ed[i].end)))
                 q1.push(PII(x.st - Ed[i].w , Ed[i].end));
     }
     ;
 }

 inline void ist(zt now){
     if(chk(now)){
         all.insert(now);
         if(all.size() > K)
             all.erase(--all.end());
     }
 }

 void Astar(){
     ist((zt){ , A) ,  ,  , });
     while(!all.empty()){
         now = *all.begin();
         all.erase(all.begin());
         ];
         if(t == B){
             if(!--K){
                  ; i < now.s.size() ; ++i){
                     if(i)
                         putchar('-');
                     cout << (int)now.s[i];
                 }
                 exit();
             }
             continue;
         }
         for(int i = head[t] ; i ; i = Ed[i].upEd)
             if(!(now.clc & (1ll << Ed[i].end)))
                 ist(zt{now.s +  , Ed[i].end) , now.dis + Ed[i].w ,  , now.clc});
     }
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     //freopen("out","w",stdout);
 #endif
     N = read();
     M = read();
     K = read();
     A = read();
     B = read();
      ; i <= M ; ++i){
         int a = read() , b = read() , c = read();
         addEd(a , b , c);
     }
     Astar();
     puts("No");
     ;
 }

1073 K短路 带奇怪剪枝的A*(非正解)

1076 奖励关

发现正着推会有后效性(在某一个物品没有吃过的情况下不知道吃还是不吃会更优),所以反着推:设$f_{i,j}$表示前$i$个回合吃过的物品集合为$j$,第$i+1$到$N$个回合吃的物品的价值和期望值,答案为$f_{0,0}$

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     ;
     char c = getchar();
     while(c != EOF && !isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(c != EOF && isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ][ << ];
 ] , need[];

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("2473.in" , "r" , stdin);
     //freopen("2473.out" , "w" , stdout);
 #endif
     int N = read() , K = read();
      ; i < K ; ++i){
         pri[i] = read();
         for(int j = read() ; j ; j = read())
             need[i] |=  << (j - );
     }
     for(int i = N ; i ; --i)
          ; j < K ; ++j)
              ; k <  << K ; ++k)
                 if((k & need[j]) == need[j])
                     dp[i][k] += max(pri[j] + dp[i + ][k | ( << j)] , dp[i + ][k]) / K;
                 else
                     dp[i][k] += dp[i + ][k] / K;
     cout << ) << dp[][];
     ;
 }

1076 奖励关

1078 斜堆

对左偏树理解不够深入……

对于当前状态下最后一个插入的点,一定在不断走左子树的那一条链上,且没有右子树

有可能有很多这样的点,如果其中深度最浅的点的左子树大小不为$1$,那么当前插入的就是这个点,因为如果不是,插入当前点之前这个点只有右子树,不满足斜堆的性质。如果左子树大小为$1$,这两个点在当前状态下是等价的,因为要求字典序最小,那就认为是深度较深那个点是当前插入的点

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 struct node{
     ] , sz;
 }Tree[];
 ];

 int init(int x){
     )
         ;
     ]) + init(Tree[x].ch[]) + ;
 }

 void search(int& x){
     ] == -){
         ){
             ans[++cnt] = Tree[x].ch[];
             Tree[x].ch[] = -;
             --Tree[x].sz;
         }
         else{
             ans[++cnt] = x;
             x = Tree[x].ch[];
         }
         return;
     }
     search(Tree[x].ch[]);
     swap(Tree[x].ch[] , Tree[x].ch[]);
     --Tree[x].sz;
 }

 int main(){
     N = read();
     Tree[].ch[] = Tree[].ch[] = -;
      ; i <= N ; ++i){
         Tree[i].ch[] = Tree[i].ch[] = -;
         int k = read();
         Tree[k >=  ? k -  : k].ch[k >= ] = i;
     }
     init();
      ; i <= N ; ++i)
         search(rt);
      ; i ; --i)
         cout << ans[i] << ' ';
     ;
 }

1078 斜堆

1079 着色方案

因为如果剩余的方块数量一一对应,且上一次填的颜色的数量也是一样的话,那么这两个状态就是一样的,所以使用记搜+Hash跑得飞快

 #include<bits/stdc++.h>
 #define ld long double
 using namespace std;

 ] , pot[] , N , sum;
 map < unsigned long long , int > hash;
 ;

 inline unsigned long long  Hash(int past){
     memcpy(pot , num , sizeof(num));
     sort(pot +  , pot + N + );
     unsigned ;
      ; i <= N ; i++)
         sum = sum *  + pot[i];
      + past;
 }

 int dfs(int all , int past){
     )
         ;
     unsigned long long t = Hash(num[past]);
     if(hash.count(t))
         return hash[t];
     ;
      ; i <= N ; i++)
         if(i != past && num[i]){
             num[i]--;
             (sum += dfs(all -  , i)) %= MOD;
             num[i]++;
         }
     return hash[t] = sum;
 }

 int main(){
     cin >> N;
      ; i <= N ; i++){
         cin >> num[i];
         sum += num[i];
     }
     cout << dfs(sum , );
     ;
 }

1079 着色方案

1080-1089

1081 超级格雷码

BZOJ没有SPJ,可以使用正常格雷码的生成方式AC掉,也可以在Luogu等有SPJ的OJ提交

如果有SPJ其实就随便枚举就可以了

 #include<bits/stdc++.h>
 using namespace std;

 ] , num[] , B , N;

 inline int modify(int ind){
      || add[ind] + num[ind] == B){
         add[ind] *= -;
         modify(ind + );
     }
     else
         num[ind] += add[ind];
 }

 inline void output(){
      ; i >=  ; i--)
         putchar(num[i] <  ? num[i] +  + 'A');
     putchar('\n');
 }

 int main(){
     ;
     cin >> N >> B;
      ; i < N ; i++){
         add[i] = ;
         ans *= B;
     }
     while(ans--){
         output();
         modify();
     }
     ;
 }

1081 超级格雷码

1082 栅栏

二分答案,每一次选择需求的木板中最短的那一些进行搜索看是否能够匹配。

剪枝:如果当前浪费的木板长度加上需求长度大于有的总木板长度就退出

 #include<bits/stdc++.h>
 using namespace std;
 inline int read(){
     ;
     char c = getchar();
     while(!isdigit(c))    c = getchar();
     ) + (a << ) + (c ^ ') , c = getchar();
     return a;
 }
 ] , Have[] , AddNeed[] , t[] , maxN , N , M , sum , waste = ;
 bool dfs(int dir , int now){
     )    ;
     ;
     for(int i = dir ; i <= M ; i++)
         if(t[i] >= Need[now]){
             ])    waste += t[i];
             ] ? i :  , now - ))    ;
             ])    waste -= t[i];
             t[i] += Need[now];
         }
     ;
 }
 inline bool check(){
     ;
     waste = ;
     memcpy(t , Have , sizeof(Have));
      , AtMid);
 }
 int main(){
     M = read();
      ; i <= M ; i++)    sum += Have[i] = read();
     N = read();
      ; i <= N ; i++)    Need[i] = read();
     sort(Have +  , Have + M + );
     sort(Need +  , Need + N + );
      ; i <= N ; i++)
         AddNeed[i] = AddNeed[i - ] + Need[i];
      , r = N;
     while(r - l){
         AtMid = r + l +  >> ;
         if(check())    l = AtMid;
         ;
     }
     cout << r;
     ;
 }

1082 栅栏

1083 繁忙的都市

最小生成树

 #include<bits/stdc++.h>
 using namespace std;
 ][] , minDir[];
 ];
 int main(){
     ios::sync_with_stdio(false);
      , k = ;
     cin >> N >> M;
     memset(num , 0x3f , sizeof(num));
     memset(minDir , 0x3f , sizeof(minDir));
     vis[] = ;
     minDir[] = ;
      ; i < M ; i++)
     {
         int a , b , c;
         cin >> a >> b >> c;
         num[a][b] = num[b][a] = c;
     }
      ; i <= N -  ; i++){
         int minN = 0x3f3f3f3f , minD;
          ; j <= N ; j++)
             if(!vis[j] && minN > (minDir[j] = min(minDir[j] , num[k][j])))
                 minN = minDir[minD = j];
         vis[k = minD] = ;
         maxN = max(maxN , minN);
     }
     cout << N -  << " " << maxN;
     ;
 }

1083 繁忙的都市

1084 最大子矩阵

一直眼瞎看不到$M \leq 2$以为是不可做题

设$f_{i,j,k}$表示现在放了$i$个矩形,第一列考虑了前$j$个,第二列考虑了前$k$个的最大值,枚举转移是在第一列还是第二列,然后枚举转移点即可。时间复杂度$O(KN^3)$

 #include<bits/stdc++.h>
 using namespace std;

 inline int read(){
     ;
     ;
     char c = getchar();
     while(!isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ][] , sum[][] , dp[][][];

 int main(){
     int N = read() , M = read() , K = read();
      ; i <= N ; i++)
          ; j < M ; j++)
             sum[i][j] = (num[i][j] = read()) + sum[i - ][j];
      ; i <= (M ==  ?  : N) ; i++){
          ; j <= N ; j++){
              ; k <= K ; k++)
                 dp[i][j][k] = max(dp[i][j - ][k] , max(dp[i][j][k - ] , i ? dp[i - ][j][k] : ));
              ; k < i ; k++)
                  ; l <= K ; l++)
                     dp[i][j][l] = max(dp[i][j][l] , dp[k][j][l - ] + sum[i][] - sum[k][]);
              ; k < j ; k++)
                  ; l <= K ; l++)
                     dp[i][j][l] = max(dp[i][j][l] , dp[i][k][l - ] + sum[j][] - sum[k][]);
             if(i == j)
                  ; k < j ; k++)
                      ; l <= K ; l++)
                         dp[i][i][l] = max(dp[i][i][l] , dp[k][k][l - ] + sum[i][] - sum[k][] + sum[j][] - sum[k][]);
         }
     }
     ;
      ; j <= N ; j++)
          ; k <= K ; k++)
             all = max(all , dp[M ==  ?  : N][j][k]);
     cout << all;
     ;
 }

1084 最大子矩阵

1085 骑士精神

IDA*模板题

 #include<bits/stdc++.h>
 using namespace std;
 ][] = {"};
 ][] = {,,,-,,,,-,-,-,-,,-,-,-,};
 struct p{
     ][];
     char* operator [](int x){return m[x];}
     int step , est;
     inline void askEst(){
         est = step;
          ; i <  ; i++)
              ; j <  ; j++)
                 est += (ex[i][j] != m[i][j] && m[i][j] != '*');
     }
 }t , f;
 int ans;
 bool dfs(p x , int lasMove){
     ;
     ;
     x.step++;
     x.est++;
      ; i <  ; i++)
          ; j <  ; j++)
             if(x[i][j] == '*'){
                  ; k <  ; k++)
                      && i + dir[k][] >=  && i + dir[k][] <  && j + dir[k][] >=  && j + dir[k][] < ){
                         f = x;
                         f[i][j] = f[i + dir[k][]][j + dir[k][]];
                         if(f[i][j] - ex[i][j])    f.est++;
                         ]][j + dir[k][]] - ex[i + dir[k][]][j + dir[k][]])
                             f.est--;
                         f[i + dir[k][]][j + dir[k][]] = '*';
                         ;
                     }
                 ;
             }
 }
 int main(){
     //freopen("knight.in" , "r" , stdin);
     //freopen("knight.out" , "w" , stdout);
     register int T;
     for(scanf("%d" , &T) ; T ; T--){
          ; i <  ; i++)
              ; j <  ; j++)
                 cin >> t[i][j];
         t.step = ;
         t.askEst();
          ; ans <=  && !dfs(t , -) ; ans++);
         printf( ? - : ans);
     }
     fclose(stdin);fclose(stdout);
     ;
 }

1085 骑士精神

1086 王室联邦

像树上莫队一样分块就行了

 #include<bits/stdc++.h>
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ;
 struct Edge{
     int end , upEd;
 }Ed[MAXN << ];
 int head[MAXN] , s[MAXN] , cap[MAXN] , be[MAXN] , N , B , top , cnt , cntEd;

 inline void addEd(int a , int b){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     head[a] = cntEd;
 }

 void dfs(int x , int p){
     s[++top] = x;
     int bot = top;
     for(int i = head[x] ; i ; i = Ed[i].upEd)
         if(Ed[i].end != p){
             dfs(Ed[i].end , x);
             if(top - bot >= B){
                 cap[++cnt] = x;
                 while(top != bot)
                     be[s[top--]] = cnt;
             }
         }
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     N = read();
     B = read();
      ; i < N ; ++i){
         int a = read() , b = read();
         addEd(a , b);
         addEd(b , a);
     }
     dfs( , );
     if(top < B){
         ;
          ; !root && i <= top ; ++i){
             for(int j = head[s[i]] ; !root && j ; j = Ed[j].upEd)
                 if(be[Ed[j].end]){
                     cap[be[Ed[j].end]] = ;
                     root = be[Ed[j].end];
                 }
         }
         if(!root){
             cout << ;
             ;
         }
         else
              ; i <= top ; ++i)
                 be[s[i]] = root;
     }
     else{
         cap[++cnt] = ;
          ; i <= top ; ++i)
             be[s[i]] = cnt;
     }
     cout << cnt << endl;
      ; i <= N ; ++i)
         cout << be[i] << ' ';
     cout << endl;
      ; i <= cnt ; ++i)
         cout << cap[i] << ' ';
     ;
 }

1086 王室联邦

1087 互不侵犯

状压DP,复杂度最大到$O(n^32^{2n})$竟然跑得飞快,实际上可以直接枚举子集

 #include<bits/stdc++.h>
 #define MOD 1000000009
 using namespace std;
 ] , N , K , tarN , num[];
 ][][] = {{{}}};
 ];
 int main(){
     cin >> N >> K;
     maxN[][][] = ;
      ; i <  << N ; i++)
         ) || i & (i >> ))){
             int k = i;
             while(k){
                 num[i]++;
                 k -= k & -k;
             }
         }
      ; i <=  ; i++){
          ; k <  << N ; k++)
             if(check[k])
                  ; j <  << N ; j++)
                     ) || k & (j << )))
                         for(int q = num[k] ; q + num[j] <= K ; q++)
                             maxN[i][q + num[j]][j] += maxN[i - ][q][k];
     }
     ;
      ; i <  << N ; i++)
         sum += maxN[N][K][i];
     cout << sum;
     ;
 }

1087 互不侵犯

1088 扫雷

DP,设$f_{i,0/1,0/1}$表示填到第$i$格,其中第$i-1$与第$i$个格子是否有放雷的方案数,注意第一格与最后一格的特判。

 #include<bits/stdc++.h>
 using namespace std;
 ][][] , bomb[];
 int main(){
     ios::sync_with_stdio();cin.tie();cout.tie();
     int N;
     cin >> N;
      ; i <= N ; i++)    cin >> bomb[i];
     ]){
         :
             num[][][] = ;
             break;
         :
             num[][][] = num[][][] = ;
             break;
         default:
             num[][][] = ;
     }
      ; i <= N ; i++)
         ]){
             :
                 num[i][][] += num[i - ][][];
                 break;
             :
                 num[i][][] += num[i - ][][];
                 num[i][][] += num[i - ][][];
                 num[i][][] += num[i - ][][];
                 break;
             :
                 num[i][][] += num[i - ][][];
                 num[i][][] += num[i - ][][];
                 num[i][][] += num[i - ][][];
                 break;
             default:
                 num[i][][] += num[i - ][][];
         }
     cout << (bomb[N] ==  ? num[N][][] : bomb[N] ==  ? num[N][][] : num[N][][] + num[N][][]);
     ;
 }

1088 扫雷

1089 严格n元树

DP,设$f_i$表示深度为$i$的严格n元树数量,$sum_i$表示深度在$[0,i]$的n元树数量,转移考虑第$0$层接的$n$个儿子则有

$f_i = sum_{i-1}^n$-$sum_{i-1}+1$

 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<ctime>
 #include<cctype>
 #include<algorithm>
 #include<cstring>
 #include<iomanip>
 #include<queue>
 #include<map>
 #include<set>
 #include<bitset>
 #include<stack>
 #include<vector>
 #include<cmath>
 //This code is written by Itst
 using namespace std;

 struct Bignum{
     ];
     int& operator [](int x){return a[x];}
     Bignum(){
     memset(a ,  , sizeof(a));
     }
     Bignum(int b){
     memset(a ,  , sizeof(a));
     while(b){
         a[++a[]] = b % ;
         b /= ;
     }
     }
     Bignum operator =(int b){
     return *this = Bignum(b);
     }
     void input(){
     string s;
     cin >> s;
     a[] = s.size();
      ; i <= a[] ; ++i)
         a[i] = s[s.size() - i] - ';
     }
     void output(){
     ])
         putchar(');
     ] ; i ; --i)
         putchar(a[i] + ');
     putchar('\n');
     }
     Bignum operator +(Bignum b){
     Bignum c;
     c[] = max(a[] , b[]);
      ; i <= c[] ; ++i)
         ){
         c[i] -= ;
         ++c[i + ];
         }
     ] + ])
         ++c[];
     return c;
     }
     Bignum operator +=(Bignum b){
     return *this = *this + b;
     }
     Bignum operator -(Bignum b){
     Bignum c;
     c[] = max(a[] , b[]);
      ; i <= c[] ; ++i)
         ){
         c[i] += ;
         --c[i + ];
         }
     ] && !c[c[]])
         --c[];
     return c;
     }
     Bignum operator -=(Bignum b){
     return *this = *this - b;
     }
     Bignum operator *(Bignum b){
     ])
         return b;
     Bignum c;
     c[] = a[] + b[] - ;
      ; i <= a[] ; ++i)
          ; j <= b[] ; ++j)
         c[i + j - ] += a[i] * b[j];
      ; i <= c[] ; ++i)
         ){
         c[i + ] += c[i] / ;
         c[i] %= ;
         ])
             ++c[];
         }
     ] && !c[c[]])
         --c[];
     return c;
     }
     Bignum operator *=(Bignum b){
     return *this = *this * b;
     }
     Bignum operator ^(int a){
     Bignum times() , b(*this);
     while(a){
         )
         times *= b;
         b *= b;
         a >>= ;
     }
     return times;
     }
     bool operator >(Bignum b)const{
     ] > b[])
         ;
     ] < b[])
         ;
     ] ; i ; --i)
         if(a[i] > b[i])
         ;
         else
         if(a[i] < b[i])
             ;
     ;
     }
     bool operator >= (Bignum b){
     ] > b[])
         ;
     ] < b[])
         ;
     ] ; i ; --i)
         if(a[i] > b[i])
         ;
         else
         if(a[i] < b[i])
             ;
     ;
     }
     Bignum operator /(Bignum b){
     Bignum c , d = *this , e;
     c[] = a[] - b[] + ;
     ] ; i && d[] ; --i){
         e = b * (Bignum() ^ (i - ));
          ; j <=  ; ++j)
         if(e > d){
             c[i] = j - ;
             break;
         }
         else
             d -= e;
     }
     ] && !c[c[]])
         --c[];
     return c;
     }
     Bignum operator /=(Bignum b){
     return *this = *this / b;
     }
     Bignum operator %(Bignum b){
     return *this - *this / b * b;
     }
     Bignum operator %=(Bignum b){
     return *this = *this % b;
     }
 }dp[] , sum[];

 int N , D;

 int main(){
 #ifndef ONLINE_JUDGE
     //freopen("in","r",stdin);
     //freopen("out","w",stdout);
 #endif
     cin >> N >> D;
     dp[] = ; sum[] = ;
      ; i <= D ; ++i){
     dp[i] = ;
      ; j <= N ; ++j)
         dp[i] *= sum[i - ];
     dp[i] = dp[i] - sum[i - ] + ;
     sum[i] = sum[i - ] + dp[i];
     }
     dp[D].output();
     ;
 }

1089 严格n元树

1090-1099

1090 字符串折叠

区间DP,额外一个转移:暴力判断是否整个串可以被折叠成一个部分。注意数字的位数判断,不要漏了括号

 #include<bits/stdc++.h>
 using namespace std;

 ][];
 string s;

 inline bool pd(string s , int dir){
      , dir);
     for(int i = dir ; i < s.size() ; i += dir)
         if(string(s , i , dir) != s1)
             ;
     ;
 }

 int main(){
     memset(ans , 0x3f , sizeof(ans));
     cin >> s;
     int l = s.size();
      ; i < l ; i++)
         ans[i][i] = ;
      ; i >=  ; i--)
          ; j < l ; j++){
             for(int k = i ; k < j ; k++)
                 ans[i][j] = min(ans[i][j] , ans[i][k] + ans[k + ][j]);
             );
              ; k <= j - i +  ; k++)
                 ) % k ==  && pd(s1 , (j - i + ) / k))
                     ans[i][j] = min(ans[i][j] , ()) +  + ans[i][i + (j - i + ) / k - ]);
         }
     cout << ans[][l - ];
     ;
 }

1090 字符串折叠

1095 捉迷藏

动态点分治,可以去我的学习笔记里看看qaq

 #include<bits/stdc++.h>
 #define INF 0x3f3f3f3f
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     ;
     char c = getchar();
     while(c != EOF && !isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(c != EOF && isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 ;
 struct Edge{
     int end , upEd;
 }Ed[MAXN << ];
 ] , dis[MAXN][] , dep[MAXN] , size[MAXN] , ST[][MAXN << ] , fir[MAXN] , logg2[MAXN << ];
 int nowSize , minSize , minInd , ts , N , cntEd;
 bool vis[MAXN];
 struct pq{
     priority_queue < int > now , del;
     inline void maintain(){
         while(!del.empty() && del.top() == now.top()){
             del.pop();
             now.pop();
         }
     }
     inline void push(int x){
         now.push(x);
     }
     inline void pop(int x){
         del.push(x);
         maintain();
     }
     inline int top(){
         return now.empty() ? -INF : now.top();
     }
     inline int sec(){
         if(now.empty())
             return -INF;
         int t = now.top();
         now.pop();
         maintain();
         int p = now.empty() ? -INF : now.top();
         now.push(t);
         return p;
     }
 }ans , cur[MAXN] , ch[MAXN];

 inline void addEd(int a , int b){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     head[a] = cntEd;
 }

 void init_dfs(int now , int fa){
     fir[now] = ++ts;
     ST[][ts] = now;
     dep[now] = dep[fa] + ;
     for(int i = head[now] ; i ; i = Ed[i].upEd)
         if(Ed[i].end != fa){
             init_dfs(Ed[i].end , now);
             ST[][++ts] = now;
         }
 }

 inline int cmp(int a , int b){
     return dep[a] < dep[b] ? a : b;
 }

 void init_st(){
     logg2[] = -;
      ; i <= N <<  ; ++i)
         logg2[i] = logg2[i >> ] + ;
      ;  << i <= N <<  ; ++i)
          ; j + ( << i) -  <= N <<  ; ++j)
             ST[i][j] = cmp(ST[i - ][j] , ST[i - ][j + ( << (i - ))]);
 }

 inline int LCA(int x , int y){
     x = fir[x];
     y = fir[y];
     if(x < y)
         swap(x , y);
     ];
      << t) + ]);
 }

 void getSize(int x){
     vis[x] = ;
     ++nowSize;
     for(int i = head[x] ; i ; i = Ed[i].upEd)
         if(!vis[Ed[i].end])
             getSize(Ed[i].end);
     vis[x] = ;
 }

 void getRoot(int x){
     vis[x] = size[x] = ;
     ;
     for(int i = head[x] ; i ; i = Ed[i].upEd)
         if(!vis[Ed[i].end]){
             getRoot(Ed[i].end);
             maxN = max(maxN , size[Ed[i].end]);
             size[x] += size[Ed[i].end];
         }
     maxN = max(maxN , nowSize - size[x]);
     if(maxN < minSize){
         minSize = maxN;
         minInd = x;
     }
     vis[x] = ;
 }

 inline int getLen(int x , int y){
     );
 }

 int init_dfz(int x , int pre){
     nowSize = ;
     minSize = INF;
     getSize(x);
     getRoot(x);
     x = minInd;
     vis[x] = ;
     fa[x][] = pre;
      , p = x ; fa[x][i] ; p = fa[x][i++]){
         dis[x][i] = getLen(x , fa[x][i]);
         fa[x][i + ] = fa[fa[x][i]][];
         ch[p].push(dis[x][i]);
     }
     for(int i = head[x] ; i ; i = Ed[i].upEd)
         if(!vis[Ed[i].end])
             cur[x].push(ch[init_dfz(Ed[i].end , x)].top());
     cur[x].push();
     cur[x].push();
     ans.push(cur[x].top() + cur[x].sec());
     vis[x] = ;
     return x;
 }

 inline void init(){
     init_dfs( , );
     init_st();
     init_dfz( , );
 }

 inline void modify(int x){
     vis[x] ^= ;
     if(vis[x]){
         ans.pop(cur[x].top() + cur[x].sec());
         cur[x].pop();
         cur[x].pop();
         ans.push(cur[x].top() + cur[x].sec());
         int p = x;
          ; fa[x][i] ; p = fa[x][i++]){
             ans.pop(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
             cur[fa[x][i]].pop(ch[p].top());
             ch[p].pop(dis[x][i]);
             cur[fa[x][i]].push(ch[p].top());
             ans.push(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
         }
     }
     else{
         ans.pop(cur[x].top() + cur[x].sec());
         cur[x].push();
         cur[x].push();
         ans.push(cur[x].top() + cur[x].sec());
         int p = x;
          ; fa[x][i] ; p = fa[x][i++]){
             ans.pop(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
             cur[fa[x][i]].pop(ch[p].top());
             ch[p].push(dis[x][i]);
             cur[fa[x][i]].push(ch[p].top());
             ans.push(cur[fa[x][i]].top() + cur[fa[x][i]].sec());
         }
     }
 }

 inline int query(){
      ? - : ans.top();
 }

 inline char getc(){
     char c = getchar();
     while(!isupper(c))
         c = getchar();
     return c;
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("1095.in" , "r" , stdin);
     //freopen("1095.out" , "w" , stdout);
 #endif
     N = read();
      ; i < N ; ++i){
         int a = read() , b = read();
         addEd(a , b);
         addEd(b , a);
     }
     init();
     for(int M = read() ; M ; --M)
         if(getc() == 'G')
             printf("%d\n" , query());
         else
             modify(read());
     ;
 }

1095 捉迷藏

1096 仓库建设

设$dp_i$表示满足前$i$个仓库的最小代价,转移$dp_i = \min\limits_{j=1}^{i-1} \{cnt_j \times dep_i + dp_j \ sum_j\} + C_i + sum_i - cnt_i \times dep_i$,其中$dep_i$表示$i$到山脚的距离,$cnt_i$表示前$i$个仓库的产品量总和,$sum_i$表示将前$i$个仓库的产品全运到山脚的代价

显然是个斜率优化。$cnt_i$单调递增,$dep_i$单调递减,可以使用单调队列优化。

 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<ctime>
 #include<cctype>
 #include<algorithm>
 #include<cstring>
 #include<iomanip>
 #include<queue>
 #include<map>
 #include<set>
 #include<bitset>
 #include<stack>
 #include<vector>
 #include<cmath>
 #define int long long
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 #define eps 1e-8
 #define ld long double
 ;
 struct line{
     int K , B;
     line(int k , int b):K(k) , B(b){}
 };
 deque < line > q;
 int sum[MAXN] , cnt[MAXN] , dep[MAXN] , dp[MAXN] , cost[MAXN];
 int N;

 inline int calc(line a , int b){
     return a.K * b + a.B;
 }

 inline ld calcP(line a , line b){
     return 1.0 * (b.B - a.B) / (a.K - b.K);
 }

 signed main(){
 #ifndef ONLINE_JUDGE
     freopen("in" , "r" , stdin);
     //freopen("out" , "w" , stdout);
 #endif
     N = read();
      ; i <= N ; ++i){
         dep[i] = read();
         cnt[i] = read();
         cost[i] = read();
     }
      ; i <= N ; ++i){
         dep[i] = dep[N] - dep[i];
         sum[i] = sum[i - ] + dep[i] * cnt[i];
         cnt[i] += cnt[i - ];
     }
     q.push_back(line( , ));
      ; i <= N ; ++i){
          && calc(q[] , dep[i]) > calc(q[] , dep[i]))
             q.pop_front();
         dp[i] = calc(q.front() , dep[i]) + cost[i] + sum[i] - cnt[i] * dep[i];
         line t(cnt[i] , dp[i] - sum[i]);
         if(q.back().K == cnt[i])
             if(q.back().B < dp[i] - sum[i])
                 continue;
             else
                 q.pop_back();
          && calcP(t , q[q.size() - ]) > calcP(q[q.size() - ] , q[q.size() - ]))
             q.pop_back();
         q.push_back(t);
     }
     cout << dp[N];
     ;
 }

1096 仓库建设

1098 办公楼

就是要找补图中的连通块数量,拿几个队列随便搞搞就行了

 #include<bits/stdc++.h>
 //This code is written by Itst
 using namespace std;

 inline int read(){
     ;
     char c = getchar();
     ;
     while(!isdigit(c) && c != EOF){
         if(c == '-')
             f = ;
         c = getchar();
     }
     if(c == EOF)
         exit();
     while(isdigit(c)){
         a = a *  + c - ;
         c = getchar();
     }
     return f ? -a : a;
 }

  , MAXM = 2e6 + ;
 struct Edge{
     int end , upEd;
 }Ed[MAXM << ];
 int sz[MAXN] , head[MAXN];
 int N , M , cntEd , cnt;
 queue < int > q;
 deque < int > notin , notto , tmp;

 inline void addEd(int a , int b){
     Ed[++cntEd].end = b;
     Ed[cntEd].upEd = head[a];
     head[a] = cntEd;
 }

 int main(){
 #ifndef ONLINE_JUDGE
     freopen("in","r",stdin);
     freopen("out","w",stdout);
 #endif
     N = read();
     M = read();
      ; i <= M ; ++i){
         int a = read() , b = read();
         addEd(a , b);
         addEd(b , a);
     }
      ; i <= N ; ++i)
         notin.push_back(i);
     while(!notin.empty()){
         int t = notin.front();
         notin.pop_front();
         ++cnt;
         q.push(t);
         while(!q.empty()){
             int t = q.front();
             q.pop();
             ++sz[cnt];
             notto.clear();
             for(int i = head[t] ; i ; i = Ed[i].upEd)
                 notto.push_back(Ed[i].end);
             sort(notto.begin() , notto.end());
             tmp.clear();
             while(!notin.empty())
                 if(!notto.empty() && notto.front() == notin.front()){
                     tmp.push_back(notto.front());
                     notto.pop_front();
                     notin.pop_front();
                 }
                 else
                     if(notto.empty() || notin.front() < notto.front()){
                         q.push(notin.front());
                         notin.pop_front();
                     }
                     else
                         notto.pop_front();
             notin = tmp;
         }
     }
     cout << cnt << '\n';
     sort(sz +  , sz + cnt + );
      ; i <= cnt ; ++i)
         cout << sz[i] << ' ';
     ;
 }

1098 办公楼

上一篇:Java EE之JSP


下一篇:API的设计与安全