终于又回到熟悉的Round了

 

数学 

设个未知数，解方程，还好没有hack点

#include 
     
      typedef long long ll;const int N = 1e5 + 5;const double PI = acos (-1.0);int main() {    double d, h, v, e; scanf ("%lf%lf%lf%lf", &d, &h, &v, &e);    double V = PI * (d / 2.0) * (d / 2.0) * h;    double addv = PI * (d / 2.0) * (d / 2.0) * e;    if (addv > v) {        puts ("NO");    } else {        double t = -V / (addv - v);        puts ("YES");        printf ("%.8f\n", t);    }    return 0;}
     

数学 

题意：求增加最小长度的一根木棍，使得构成一个多边形。

分析：那么构成三角形，原来n条木棍分成A，B两边，A和B接近(A<=B)，那么另一条边满足A + C > B，即C = B +１ - A

#include 
     
      typedef long long ll;const int N = 1e5 + 5;int a[N];int main() {    int n; scanf ("%d", &n);    ll sum = 0;    for (int i=0; i
     

DP 

题意：问后缀由若干个长度为2或3的子串构成，且相邻的子串不能相同。

分析：The only restriction — it is not allowed to append the same string twice in a row! 英语太渣不知道这是连续，相邻的意思。那么dp[i][0]表示i开始长度为2的子串能否可行，如果可行，那么dp[i-3][1]一定可行，因为长度不相等；还有如果长度相等的判断一下，即dp[i-2][0]。

#include 
     
      const int N = 1e4 + 5;bool dp[N][2];int main() {    std::string str;    std::cin >> str;    int n = str.length ();    dp[n-2][0] = dp[n-3][1] = true;    std::set
      
        ans;    for (int i=n-1; i>=5; --i) {        if (dp[i][0]) {            ans.insert (str.substr (i, 2));            dp[i-3][1] = true;            if (str.substr (i-2, 2) != str.substr (i, 2)) {                dp[i-2][0] = true;            }        }        if (dp[i][1]) {            ans.insert (str.substr (i, 3));            dp[i-2][0] = true;            if (str.substr (i-3, 3) != str.substr (i, 3)) {                dp[i-3][1] = true;            }        }    }    std::cout << ans.size () << '\n';    for (auto s: ans) {        std::cout << s << '\n';    }    return 0;}
      
     

图论 

题意：找4个点按照顺序走，a->b->c->d，每次点到下一个点走的是最短路，问走的长度总和最大是多少。

分析：先计算dis(u, v)，枚举b和c，对于b来说在反向图中找距离最远的点，因为a!=b a!=c，所以存最优的前3个点；对于c来说在原图中找距离最远的点，存最优的前4个点。

#include 
     
      const int N = 3e3 + 5;const int M = 5e3 + 5;const int INF = 0x3f3f3f3f;int dis[N][N];std::vector
      
        G[N], rG[N];std::vector
       
        
          > bin[N], bout[N];bool vis[N];int n, m;void BFS() {    memset (dis, INF, sizeof (dis));    for (int i=1; i<=n; ++i) {        std::queue
         
           que;        dis[i][i] = 0;        que.push (i);        while (!que.empty ()) {            int u = que.front (); que.pop ();            for (auto v: G[u]) {                if (dis[i][v] > dis[i][u] + 1) {                    dis[i][v] = dis[i][u] + 1;                    que.push (v);                }            }        }    }}void sort_out() {    for (int i=1; i<=n; ++i) {        memset (vis, false, sizeof (vis));        vis[i] = true;        bout[i].push_back (std::make_pair (0, i));        std::queue
          
           
             > que; que.push (std::make_pair (0, i)); while (!que.empty ()) { std::pair
            
              pu = que.front (); que.pop (); for (auto v: G[pu.second]) { if (!vis[v]) { vis[v] = true; bout[i].push_back (std::make_pair (pu.first + 1, v)); que.push (std::make_pair (pu.first + 1, v)); } } } std::sort (bout[i].begin (), bout[i].end (), std::greater
             
              
                > ()); //dis[i][v], v if (bout[i].size () > 4) { bout[i].resize (4); } }}void sort_in() { for (int i=1; i<=n; ++i) { memset (vis, false, sizeof (vis)); vis[i] = true; bin[i].push_back (std::make_pair (0, i)); std::queue
               
                
                  > que; que.push (std::make_pair (0, i)); while (!que.empty ()) { std::pair
                 
                   pu = que.front (); que.pop (); for (auto v: rG[pu.second]) { if (!vis[v]) { vis[v] = true; bin[i].push_back (std::make_pair (pu.first + 1, v)); que.push (std::make_pair (pu.first + 1, v)); } } } std::sort (bin[i].begin (), bin[i].end (), std::greater
                  
                   
                     > ()); //dis[v][i], v if (bin[i].size () > 3) { bin[i].resize (3); } }}int main() { scanf ("%d%d", &n, &m); for (int u, v, i=0; i
                    
                     =0; --ii) { int tot = dis[i][j]; std::pair
                     
                       &x = bin[i][ii]; if (x.second != i && x.second != j) { k = x.second; tot += x.first; for (int jj=bout[j].size ()-1; jj>=0; --jj) { std::pair
                      
                        &y = bout[j][jj]; if (y.second != i && y.second != j && y.second != k) { l = y.second; tot += y.first; if (best < tot) { best = tot; a = k; b = i; c = j; d = l; } tot -= y.first; } } } } } } printf ("%d %d %d %d\n", a, b, c, d); return 0;}
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

组合数学 (div 1)

题意：给一个串，长度为 l，问它扩展成长度n的串有多少个（其中长度l的原串相当于变成长度n的子序列）

分析：对于长度为 l 的子序列，n 的答案是

因为 l 的总和不超过 10^5​​，所以 l 不同的取值只有最多 2 sqrt(10^5)​​​​​ 种。对于每个 l，前缀和预处理所有 n 的答案。

令，则

#include 
     
      typedef long long ll;const int N = 1e5 + 5;const int MOD = 1e9 + 7;int fac[N], inv_fac[N];char s[N];int ans[N];std::vector
      
       
         > query[N]; //len, nint pow_mod(int x, int n) {    int ret = 1;    while (n) {        if (n & 1) {            ret = (ll) ret * x % MOD;        }        x = (ll) x * x % MOD;        n >>= 1;    }    return ret;}int binom(int n, int m) {    if (m > n) {        return 0;    } else {        return (ll) fac[n] * inv_fac[m] % MOD * inv_fac[n-m] % MOD;    }}void prepare(int len, int maxn) {    int base = 1;    //g(n)    for (int i=0; i<=maxn; ++i) {        ans[i] = i < len ? 0 : (ll) binom (i - 1, len - 1) * base % MOD;        if (i >= len) {            base = (ll) base * 25 % MOD;        }    }    //f(n+1) = g(n+1) + f(n+1) * 26    for (int i=0; i
        
         = MOD) {            ans[i] -= MOD;        }        ans[i+1] += (ll) ans[i] * 26 % MOD;    }    if (ans[maxn] >= MOD) {        ans[maxn] -= MOD;    }}int main() {    fac[0] = 1;    for (int i=1; i
         
          =0; --i) {        inv_fac[i] = (ll) inv_fac[i+1] * (i + 1) % MOD;    }    std::vector
          
            query; int m; scanf ("%d", &m); scanf ("%s", s); int len = strlen (s); int maxn = -1; for (int i=0; i