2018牛客多校第三场个人总结

A PACM Team

背包dp经典题，也不算是太复杂的变形，直接dp就行了，注意卡空间，用short

 #include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define For(i,a,b) for(int i = (a); i < (b); ++i)
#define IOS ios::sync_with_stdio(false)
using namespace std;

const int maxn = 40;
short  F[maxn][maxn][maxn][maxn][maxn];
short a[maxn], b[maxn],c[maxn],d[maxn];
short v[maxn];
short vv[maxn];
bool  dp[maxn][maxn][maxn][maxn][maxn];
int main(void)
{
   int n;
   cin>>n;
  short  A,B,C,D;
   for(int i = 1;i <= n; ++i)
      cin>>a[i]>>b[i]>>c[i]>>d[i]>>v[i];
   cin>>A>>B>>C>>D;
   me(F);
   For(i,1,n+1){
        For(aa,0,A+1){
            For(bb,0,B+1){
                For(cc,0,C+1){
                    For(dd,0,D+1){
                        F[i][aa][bb][cc][dd] = F[i-1][aa][bb][cc][dd];
                        if(aa >= a[i]&&bb >= b[i]&&cc >= c[i]&&dd >= d[i])
                        F[i][aa][bb][cc][dd] =  max((int)F[i][aa][bb][cc][dd],F[i-1][aa-a[i]][bb - b[i]][cc-c[i]][dd-d[i]]+v[i]);
                       }
                   }
               }
           }
         }
    short   Aa = A,Bb = B,Cc = C,Dd = D;
    short   Max = 0;
   for(int aa=0;aa <= A; ++aa){
            for(int bb = 0;bb <= B;++bb){
                for(int cc = 0;cc <= C; ++cc){
                    for(int dd = 0; dd <= D; ++dd ){
                        if(F[n][aa][bb][cc][dd] > Max){
                            Aa  = aa,Bb = bb,Cc = cc,Dd = dd;
                            Max = F[n][aa][bb][cc][dd];
                        }
                    }
                }
            }
        }
    int tot = 0;
    for(int i = n; i > 0;--i){
        if(Aa >= a[i]&&Bb >= b[i]&&Cc >= c[i]&&Dd >= d[i])
        {
            if(F[i][Aa][Bb][Cc][Dd] == F[i-1][Aa-a[i]][Bb-b[i]][Cc-c[i]][Dd-d[i]]+v[i]){
             vv[tot++] = i,Aa -=a[i],Bb -= b[i], Cc -= c[i],Dd -= d[i];
             }
     }
    }  
    cout<<tot<<endl;
    for(int i = tot-1;i >= 0; --i){
         cout<<vv[i]-1; if(i)putchar(' ');
    }
   return 0;
}

2 B Expected Number of Nodes

概率题+dp题，有空补题

3 C Shuffle Cards

伸展树或者rope的应用

D Encrypted String Matching

FFT 的应用

E Sort String

kmp或者hash求最小循环节

F Sum Of Digit

数学+ 数据结构

G Coloring Tree

数学 + BFS

H Diff-prime Pairs

数论打表+简单计数
假设gcd(i,j) = d,我们e枚举d的值，
s u m [ i ] 表示到i共有多少个素数
a n s = <munderover> ∑ i = 1 i = N </munderover> s u m [ i ] ∗ ( s u m [ i ] − 1 ) 2

I Expected Size of Random Convex Hull

Geometry, Random algo 几何题，随机算法

J Distance to Work

求简单多边形和圆相交的面积 + 二分，直接套板子
参考代码