首页 > 其他分享 >11.9总结

11.9总结

时间：2022-11-09 19:26:03浏览次数：38  
标签：总结 ch return 11.9 int sum long fa

11.9 GZEZ NOIP2022模拟测试赛（五十七）

PROBLEM A : [精神焕发（huan）]

题面描述：

给你一颗树，每个点可以回血，经过一次回血\(w[i]\)(有正有负)

\(q\)次询问:给出\(x , s , t\) 问初始血量为\(x\)是否能从\(s\)到达\(t\)

Solution:

先考虑一个特殊情况为若\(s\)到\(t\)时不是走最短路径而是走到一个无限回血点，那么必然经过一条两端权值和为正数的。

  • 1.从\(s\)走到无限回血点再走到\(t\),我们需要统计\(s\)到\(t\)上的前缀最小值，可以发现前缀最小值是是个路径的回血或者是整个路径除去t点，否则\(s\)到\(t\)上一定有无限回血点。用倍增维护即可
  • 2.从\(s\)直接走到\(t\)的最短路径通过 \(up\ and\ down\ DP\) 维护从每个点最少需要多少血才能到达一个无限血点。
Code:
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
namespace fast_IO
{
    #define FAST_IO
    #define IOSIZE 100000
    typedef long long ll;
    typedef double db;
    typedef long double ldb;
    typedef __int128_t i128;
    char ibuf[IOSIZE], obuf[IOSIZE];
    char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
    #ifdef ONLINE_JUDGE
        #define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
        #define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
    #endif//fread in OJ, stdio in local

    #define isdigit(ch) (ch>47&&ch<58)
    #define isspace(ch) (ch<33&&ch!=EOF)
    
    struct fast_IO_t{
        ~fast_IO_t(){
            fwrite(obuf, p3-obuf, 1, stdout);
        }
        bool flag = false;
        operator bool() {
            return flag;
        }
    }io;
    
    template<typename T> inline T read() {
        T s = 0; int w = 1; char ch;
        while(ch=getchar(), !isdigit(ch)&&(ch!=EOF))
            if(ch == '-') w = -1;
        if(ch == EOF) return 0;
        while(isdigit(ch))
            s = s*10+ch-48, ch=getchar();
        if(ch == '.') {
            ll flt = 0; int cnt = 0;
            while(ch=getchar(), isdigit(ch))
                if(cnt < 18) flt=flt*10+ch-48, cnt++;
            s += (db)flt/pow(10,cnt);
        }
        return s *= w;
    }
    template<typename T> inline bool read(T &s) {
        s = 0; int w = 1; char ch;
        while(ch=getchar(), !isdigit(ch)&&(ch!=EOF))
            if(ch == '-') w = -1;
        if(ch == EOF) return false;
        while(isdigit(ch))
            s = s*10+ch-48, ch=getchar();
        if(ch == '.') {
            ll flt = 0; int cnt = 0;
            while(ch=getchar(), isdigit(ch))
                if(cnt < 18) flt=flt*10+ch-48, cnt++;
            s += (db)flt/pow(10,cnt);
        }
        return s *= w, true;
    }
    inline bool read(char &s) {
        while(s = getchar(), isspace(s));
        return s != EOF;
    }
    inline bool read(char *s) {
        char ch;
        while(ch=getchar(), isspace(ch));
        if(ch == EOF) return false;
        while(!isspace(ch))
            *s++ = ch, ch=getchar();
        *s = '\000';
        return true;
    } 
    template<typename T> void print(T x) {
        static int t[20]; int top = 0;
        if(x < 0) putchar('-'), x = -x;
        do { t[++top] = x%10; x /= 10; } while(x);
        while(top) putchar(t[top--]+48);
    }
    struct null_type{}; int pcs = 8;
    null_type setpcs(int cnt)
    {
        pcs = cnt;
        return null_type();
    }
    inline void print(null_type x){}
    inline void print(double x) {
        if(x < 0) putchar('-'), x = -x;
        x += 5.0 / pow(10,pcs+1);
        print((ll)(x)); x -= (ll)(x); putchar('.');
        for(int i = 1; i <= pcs; i++)
            x *= 10, putchar((int)x+'0'), x -= (int)x;
    }
    inline void print(float x) {
        if(x < 0) putchar('-'), x = -x;
        x += 5.0 / pow(10,pcs+1);
        print((ll)(x)); x -= (ll)(x); putchar('.');
        for(int i = 1; i <= pcs; i++)
            x *= 10, putchar((int)x+'0'), x -= (int)x;
    }
    inline void print(long double x) {
        if(x < 0) putchar('-'), x = -x;
        x += 5.0 / pow(10,pcs+1);
        print((i128)(x)); x -= (i128)(x); putchar('.');
        for(int i = 1; i <= pcs; i++)
            x *= 10, putchar((int)x+'0'), x -= (int)x;
    }
    inline void print(char x) {
        putchar(x);
    }
    inline void print(char *x) {
        for(int i = 0; x[i]; i++)
            putchar(x[i]);
    }
    inline void print(const char *x) {
        for(int i = 0; x[i]; i++)
            putchar(x[i]);
    }
    #ifdef _GLIBCXX_STRING//string
        inline bool read(std::string& s) {
            s = ""; char ch;
            while(ch=getchar(), isspace(ch));
            if(ch == EOF) return false;
            while(!isspace(ch))
                s += ch, ch = getchar();
            return true;
        }
        inline void print(std::string x) {
            for(auto i = x.begin(); i != x.end(); i++)
                putchar(*i);
        }
        inline bool getline(fast_IO_t &io, string s)
        {
            s = ""; char ch = getchar();
            if(ch == EOF) return false;
            while(ch != '\n' and ch != EOF)
                s += ch, ch = getchar();
            return true;
        }
    #endif
    template<typename T, typename... T1>
    inline int read(T& a, T1&... other) {
        return read(a)+read(other...);
    }
    template<typename T, typename... T1>
    inline void print(T a, T1... other) {
        print(a); print(other...);
    }
    template<typename T>
    fast_IO_t& operator >> (fast_IO_t &io, T &b){
        return io.flag=read(b), io;
    }
    template<typename T>
    fast_IO_t& operator << (fast_IO_t &io, T b) {
        return print(b), io;
    }
    #define cout io
    #define cin io
    #define endl '\n'
}
using namespace fast_IO;
const int SIZE = 1e6+1000 ;
struct node{
    int nxt ;
    int to ;
}e[SIZE<<2] ;
ll w[SIZE] ;
int dep[SIZE],fa[SIZE][22];
int head[SIZE];
ll dis[SIZE] ;
ll smaller[SIZE][22],bigger[SIZE][22] ;
ll sum[SIZE] ;
int n , m , q ;
int tot ;

inline void add(int x , int y){
    e[++tot] = (node) {head[x] , y} , head[x] = tot ;
    e[++tot] = (node) {head[y] , x} , head[y] = tot ;
}
inline void dfs(int now , int f){
    dep[now] = dep[f] + 1 , fa[now][0] = f ;
    smaller[now][0] = bigger[now][0] = w[now] ;
    dis[now] = w[now] + dis[f] ;
    for(int i = 1 ; i <= 20 ; i += 1){
        fa[now][i] = fa[fa[now][i-1]][i-1] ;
        smaller[now][i] = min(smaller[now][i-1] , dis[now] - dis[fa[now][i-1]] + smaller[fa[now][i-1]][i-1]) ;
        bigger[now][i] = max(bigger[now][i-1] , dis[now] - dis[fa[now][i-1]] + bigger[fa[now][i-1]][i-1]) ;
    }
    for(int i = head[now] ; i ; i = e[i].nxt){
        int v = e[i].to ;if(v == f) continue ;
        dfs(v , now) ;
    }
}
inline int LCA(int x , int y){
    if(dep[x] < dep[y]) swap(x , y) ;
    for(int i = 20 ; i >= 0 ; i -= 1){
        if(dep[fa[x][i]] >= dep[y]){
            x = fa[x][i] ;
        }
    } 
    if(x == y) return x ;
    for(int i = 20 ; i >= 0 ; i -= 1){
        if(fa[x][i] != fa[y][i]){
            x = fa[x][i] ;
            y = fa[y][i] ;
        }
    }
    return fa[x][0] ;
}

inline ll get(int x , int y){
    int lca = LCA(x , y) ;
    ll d = 0 , ans = 1e9 ;
    for(int i = 20 ; i >= 0 ; i -= 1){
        if(dep[fa[x][i]] >= dep[lca]){
            ans = min(ans , d + smaller[x][i]) ;
            d += dis[x] - dis[fa[x][i]] ;
            x = fa[x][i] ;
        }
    }
    ans = min(ans , w[lca] + d) ;
    d += dis[y] - dis[lca] + w[lca] ;
    ans = min(ans , d) ;
    for(int i = 20 ; i >= 0 ; i -= 1){
        if(dep[fa[y][i]] >= dep[lca]){
            ans = min(ans , d - bigger[y][i]) ;
            d -= dis[y] - dis[fa[y][i]] ;
            y = fa[y][i] ;
        }
    }
    return ans ;
}

inline void dfs1(int x , int fa){
    if(w[x] + w[fa] > 0ll){
        sum[x] = min(sum[x] , -w[x]) ;
        sum[x] = max(sum[x] , 0ll) ;
        sum[fa] = min(sum[fa] , -w[fa]) ;
        sum[fa] = max(sum[fa] , 0ll) ;
    }
    for(int i = head[x] ; i ; i = e[i].nxt){
        int v = e[i].to ; if(v == fa) continue ;
        dfs1(v , x) ;
        sum[x] = min(sum[x] , sum[v] - w[x]) ;
        sum[x] = max(sum[x] , 0ll) ;
    }
}

inline void dfs2(int x , int fa){
    for(int i = head[x] ; i ; i = e[i].nxt){
        int v = e[i].to ; if(v == fa) continue ;
        sum[v] = min(sum[v] , sum[x] - w[v]) ;
        sum[v] = max(sum[v] , 0ll) ;
        dfs2(v , x) ;
    }
}

signed main(){
    int n , q ;
    cin >> n >> q ;
    for(int i = 1 ; i <= n ; i += 1) cin >> w[i] ;
    for(int i = 1 ; i <= n - 1 ; i += 1){
        int x , y ; cin >> x >> y ;
        add(x , y) ;
    }
    dfs(1 , 0) ;
    memset(sum , 0x3f , sizeof sum) ;
    dfs1(1 , 0) , dfs2(1 , 0) ;
    
    for(int i = 1 ; i <= q ; i += 1){
        ll x ;
        int y , z ; cin >> x >> y >> z ;
        if(sum[y] <= x || -get(y , z) <= x){
            puts("Yes") ;
        }
        else puts("No") ;
    }
}

PROBLEM B : [顺逆序对（luan）]

题面描述：

对于一个 \(1,\dots,n\) 的排列 \(a_1,\dots,a_n，\)定义 \(i\) 处的顺序对数 \(f(i)\) 为满足 \(1\leq j<i\) 且 \(a_j<a_i\) 的 jj 的数量，定义$ i\(处的逆序对数\) g(i)$ 为满足 \(i<j\leq n\)且 \(a_j<a_i\)的 \(j\) 的数量。

给定 \(n\)，对于每个$ k=0,1,\dots,n-1$，求出满足 \(\max_{i=1}^n|f(i)-g(i)|=k\)的 \(a_1,\dots,a_n\)的数量模 \(10^9+7\) 的值。

Solution:

先转化成对于每个\(k=0,1,\dots,n-1\)求\(max_{i-1}^{n}{\mid f\left(i\right) - g\left(i\right)\mid} \le k\)

考虑构造的过程是往序列里插数，在插第\(i+1\)个数时若放在第\(p\)和第\(p+1\)个数之间，\(f\left(i+1 \right) = p , g\left(i\right)=i-p\)现在只需要保证\(\mid p-\left(i-p\right)\mid \le k\)即可

设\(num\left(i\right)\)为\(\texttt{插入}i+1\)时满足条件的p的个数，显然可得：

\[c(i)=\left\{\begin{array}{ll} i+1 & i<k \\ k+[i \equiv k(\bmod 2)] & i \geq k \end{array}\right. \]

然后转化成求\(\prod \limits_{i=0}^{n-1}num\left(i\right)=k! \prod \limits_{i=k}^{n-1}\left(k+\left[i\equiv k \left(mod\ 2\right)\right]\right)\)

Code:
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const ll mod = 1e9+7 ;

ll n , m ;

inline ll ksm(ll a , ll b){
    ll res = 1 ;
    for( ; b ; b >>= 1 , a = a * a % mod){
        if(b & 1) res = res * a % mod ;
    }
    return res ;
}
ll ans1 , ans2 ;
int main(){
    cin >> n ;
    ll fac = 1 ;
    for (int k = 0; k < n; k++, fac = (fac * (k + !k) % mod))
    {
        ans1 = (fac * ksm(k, (n - k) >> 1) % mod * ksm(k + 1, (n - k + 1) >> 1) % mod) % mod ;
        cout << (ans1 - ans2 + mod) % mod << ' ';
        ans2 = ans1;
    }
    return 0 ;
}

PROBLEM C : [串串（chuan）]

题面描述：

现在有一个长度为 \(n\)的字符串 \(S\)与一个长度为 \(m\) 的字符串$ T$定义字符串 \(S_i\) 表示将从$ S$ 的第 \(i\)个字符后断开得到 \(A\),\(B\)，将\(B\) 从尾到头形成的字符串设为 \(B'\)，将 $B' $接在 \(A\)后面得到的字符串。对于每个 \(i\)，\(\texttt{FAT}\)想知道 TT 在 \(S_i\)中出现的次数。

Solution:

\(T\)在 \(Si=AB\)中的出现次数是 \(T\) 在\(A\)中的出现次数 \(+T\texttt{在}B\) 中的出现次数 \(+ T \texttt{跨过} A \texttt{和} B\) 的出现次数 , 前两个很好处理，考虑最后一个\(T\) 的一个后缀要与 \(B\)的前缀匹配，剩余的前缀要与\(A\)的后缀匹配 , 可以先处理出所有跟 \(B\)的前缀匹配的\(T\)后缀，然后询问它们剩的前缀有多少个是\(A\)的后缀

可以建出 \(KMP\) 的 \(fail\ tree\) 解决

时间复杂度 \(O(nlogn)\)

Code:
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e6+10;
 
int n, m;
char s[N], t[N];
int nxt[N], len[N];
int ans[N], suf[N];
int ldfn[N], rdfn[N], cnt;
vector<int> ver[N];
void dfs(int x)
{
    ldfn[x] = ++cnt;
    for(auto y : ver[x]) dfs(y);
    rdfn[x] = ++cnt;
}
void get_next(char *s, int *nxt);
 
namespace bit {
    int a[N];
    #define lowbit(i) (i&-i)
    void add(int x, int v) 
	{ for(; x <= cnt; x += lowbit(x)) a[x] += v; }
    int query(int x) 
	{ int ans = 0; for(; x >= 1; x -= lowbit(x)) ans += a[x]; return ans; }
}
 
int main()
{
    cin >> (s+1) >> (t+1);
    n = strlen(s+1);
    m = strlen(t+1);
     
    get_next(t, nxt);
     
    for(int i = 1, j = 0; i <= n; i++)
    {
        while(j and t[j+1] != s[i]) j = nxt[j];
        if(t[j+1] == s[i]) j++;
        len[i] = j;
        ans[i] = ans[i-1]+(j==m);
    }
     
    for(int i = 1; i <= m; i++)
        ver[nxt[i]].push_back(i);
    dfs(0);
    reverse(t+1, t+m+1);
    get_next(t, nxt);
    int j = 0;
    for(int i = 1; i <= n; i++)
    {
        while(j and t[j+1] != s[i]) j = nxt[j];
        if(t[j+1] == s[i]) j++;
        if(j == m) suf[i-m+1] = 1;
    }
    if(j == m) j = nxt[j];
     
    vector<int> f;
    for(; j; j = nxt[j])
        f.push_back(j);
    for(int i = n; i >= 1; i--)
    {
        while(!f.empty() and i+f.back() <= n)
        {
            bit::add(ldfn[m-f.back()], 1);
            bit::add(rdfn[m-f.back()]+1, -1);
            f.pop_back();
        }
         
        suf[i] += suf[i+1];
        ans[i] += bit::query(ldfn[len[i]]);
    }
     
    for(int i = 1; i <= n; i++)
        cout << ans[i]+suf[i+1] << "\n";
}
 

 
void get_next(char *s, int *nxt)
{
    int n = strlen(s+1);
    nxt[1] = 0;
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j and s[j+1] != s[i]) j = nxt[j];
        if(s[j+1] == s[i]) j++;
        nxt[i] = j;
    }
}

PROBLEM D : [烦死出题人的排列（fan）]

题面描述：

有 \(m\)个长度为$ n$排列 \(q_1,\dots,q_m\)，现在你需要自己定义 \(k\)个置换，使得对于任意一个 \(q_i\)，都可以从初始排列 \((1,2,\dots,n)\)以某种顺序应用这 \(k\) 个置换若干次得到。求 \(k\)的最小值是多少，并给出构造方案。

Solution:

什么东西

标签：总结,ch,return,11.9,int,sum,long,fa
From： https://www.cnblogs.com/guier/p/16874860.html

相关文章

  • javascript初识以及总结
    今天主要学习了js的概述,书写的三种位置(和css一样内嵌外联和内联三种)以及变量的定义,变量的定义用的是var来定义的并且学了五种数据类型 有number数值型strin......
  • 系统调优总结
    一、算法调优1、分而治之和预处理：以前有一个程序为了生成月报表，每次都需要计算很长的时间，有时候需要花将近一整天的时间。于是我们把我们找到了一种方法可以把这个算法发......
  • LINQ编程总结
        LINQtoSQL查询表达式适用于关系数据库，查询表达式是基于对象的，它要求将数据库表和试图映射到实体，LINQTOSQL让数据库的操作变得更加的简单，完全弱化了数据库......
  • UML基础总结
    ......
  • 11月9日学习归纳总结
    11月9日学习归纳总结目录11月9日学习归纳总结一、单例模式实现的多种方式二、pickle序列化模块三、选课系统需求分析3.1整体需求3.2功能提炼3.3选课系统架构设计3.4选......
  • WPF总结
        WPF是WindowsPresentationFoundation的简称，是专门用于编写程序表示层的技术和工具，表示开发层的技术非常多，最初的ASP.NET,Winform，Sliverlight以及WPF，最近流行......
  • Python阶段性总结：面向对象之选课系统需求分析及目录搭建
    目录面向对象之选课系统一、选课系统需求分析二、功能提炼三、选课系统架构设计四、选课系统目录搭建五、选课系统功能搭建面向对象之选课系统一、选课系统需求分析1、......
  • 2022赛季的第一次总结
    CSP2022总结：T1由于题看错了，导致浪费了一部分时间，所以在做题之前应该要确保把题意完全弄明白。T1最后分数也没拿满的原因是自己写的时候脑子抽，本来是想排序然后找到合法的......
  • 2022 年了，我才开始学 TypeScript ，晚吗？（7.5k字总结）
    2022年了，我才开始学TypeScript，晚吗？（7.5k字总结）原文地址https://mp.weixin.qq.com/s/sbt8SDmke7QoSXtwYucDcA前言其实早在初学前端时，就有大致了解过typescript,但后......
  • django-cors-headers实现跨域的方法总结
    django-cors-headers实现跨域的方法总结在setting.py中配置INSTALLED_APPS=['django.contrib.admin','django.contrib.auth','django.contrib.contenttypes','django.cont......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99