首页 > 其他分享 >2022NOIPA层联测7之only部分分

2022NOIPA层联测7之only部分分

时间：2022-10-11 15:58:40浏览次数：46  
标签：ch 2022NOIPA int while long only maxn 联测 dr

问题 A: 【2022NOIP联测710月11日】找（a）

一看到是个数学题还感觉挺恐怖，把式子写出来才发现它很水。

没开long long大样例跑不出来还以为T1又没了……然而幸好及时发现问题。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 8;
const ll mod = 998244353;

int n;
ll suma, sumb, sx1, sx2, fa[maxn], fb[maxn], ans, a[maxn], b[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    n = read();
    for(int i=1; i<=n; i++)
    {
        a[i] = read(); b[i] = read();
        fa[i] = a[i]*a[i]%mod; fb[i] = b[i]*b[i]%mod;
        suma = (suma + a[i]) % mod; sumb = (sumb + b[i]) % mod;
    }
    for(int i=1; i<=n; i++)
    {
        sx1 = (sx1 + fa[i]) % mod; sx2 = (sx2 + fb[i]) % mod;
    }
    for(int i=1; i<=n; i++)
    {
        ans = ((n-2)*fa[i]%mod + (n-2)*fb[i]%mod) % mod;
        ans = (ans + sx1 + sx2) % mod;
        ll del = (2*a[i]%mod*(suma-a[i]+mod)%mod+2*b[i]%mod*(sumb-b[i]+mod)%mod)%mod;
        ans = (ans+mod-del)%mod;
        printf("%lld\n", ans);
    }
    
    return 0;
}
View Code

 

问题 B: 【2022NOIP联测710月11日】女（b）

第一版暴力是把所有黑点的集合记下来，对每一个是黑点的点求距离，找距离最小的。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 6;
const int inf = 0x3f3f3f3f;

int n, q, dep[maxn], siz[maxn], son[maxn], fa[maxn], top[maxn];
set<int> s;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct node 
{
    int next, to;
}a[maxn<<1];
int head[maxn], len;

void add(int x, int y)
{
    a[++len].to = y; a[len].next = head[x];
    head[x] = len;
}

void find_heavy_edge(int u, int fat, int depth)
{
    dep[u] = depth;
    fa[u] = fat;
    son[u] = 0;
    siz[u] = 1;
    int maxsize = 9;
    for(int i=head[u]; i; i=a[i].next)
    {
        int v = a[i].to;
        if(dep[v]) continue;
        find_heavy_edge(v, u, depth+1);
        siz[u] += siz[v];
        if(siz[v] > maxsize)
        {
            maxsize = siz[v];
            son[u] = v;
        }
    }
}

void connect_heavy_edge(int u, int ancestor)
{
    top[u] = ancestor;
    if(son[u])
    {
        connect_heavy_edge(son[u], ancestor);
    }
    for(int i=head[u]; i; i=a[i].next)
    {
        int v = a[i].to;
        if(v == fa[u] || v == son[u]) continue;
        connect_heavy_edge(v, v);
    }
}

int LCA(int x, int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    return x;
}

int main()
{   
    n = read(); q = read();
    for(int i=1; i<n; i++)
    {
        int x = read(), y = read();
        add(x, y); add(y, x);
    }
    find_heavy_edge(1, 1, 1);
    connect_heavy_edge(1, 1);
    while(q--)
    {
        int opt = read();
        if(opt == 1)
        {
            int x = read();
            if(s.find(x) != s.end()) s.erase(x);
            else s.insert(x);
        }
        else 
        {
            int x = read(); 
            if(s.empty()) {printf("-1\n"); continue;}
            int ans = inf;
            for(int y : s)
            {
                ans = min(ans, dep[x]+dep[y]-2*dep[LCA(x,y)]);
            }
            printf("%d\n", ans);
        }
    }
    
    return 0;
}
TLE 10

比较优化的暴力是把子树的最优解放进set里，然后直接跳father：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 6;
const int inf = 0x3f3f3f3f;

int n, q, fa[maxn], ans;
bool vis[maxn];
multiset<int> s[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct node 
{
    int next, to;
}a[maxn<<1];
int head[maxn], len;

void add(int x, int y)
{
    a[++len].to = y; a[len].next = head[x];
    head[x] = len;
}

void dfs(int x, int f)
{
    fa[x] = f;
    for(int i=head[x]; i; i=a[i].next)
    {
        int y = a[i].to;
        if(y == fa[x]) continue;
        dfs(y, x);
    }
}

void update0(int x)
{
    int tp = 0;
    while(x)
    {
        s[x].erase(s[x].find(tp));
        tp++; x = fa[x];
    }
}

void update1(int x)
{
    int tp = 0;
    while(x)
    {
        s[x].insert(tp);
        tp++; x = fa[x];
    }
}

void query(int x)
{
    int tp = 0; ans = inf;
    while(x)
    {
        if(s[x].size()) ans = min(ans, (*s[x].begin())+tp);
        x = fa[x]; tp++;
    }
    if(ans == inf) ans = -1;
}

int main()
{
    n = read(); q = read();
    for(int i=1; i<n; i++)
    {
        int x = read(), y = read();
        add(x, y); add(y, x);
    }
    dfs(1, 0);
    while(q--)
    {
        int opt = read();
        if(opt == 1)
        {
            int x = read();
            if(vis[x] == 1) {vis[x] = 0; update0(x);}
            else {vis[x] = 1; update1(x);}
        }
        else 
        {
            int x = read();
            query(x);
            printf("%d\n", ans);
        }
    }
    
    return 0;
}
TLE 40

 

问题 C: 【2022NOIP联测710月11日】朋（c）

每一个左边的点都能找到匹配，所以对左边的点的匹配生成排列，判断一下and和是谁：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 109;
const int inf = 0x3f3f3f3f;

int n, m, ext[133], num;
bool vis[maxn];
vector<int> v[maxn], w[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

void dfs(int a, int n)
{
    if(a > n)
    {
        if(num <= 127) ext[num] = 1;
        return;
    }
    int sz = v[a].size();
    for(int i=0; i<sz; i++)
    {
        int to = v[a][i];
        if(vis[to]) continue;
        vis[to] = 1;
        int now = num;
        if(a == 1) num = w[a][i];
        else num &= w[a][i];
        dfs(a+1, n);
        vis[to] = 0;
        num = now;
    }
}

int main()
{
    n = read(); m = read();
    for(int i=1; i<=m; i++)
    {
        int x = read(), y = read(), z = read();
        v[x].push_back(y); w[x].push_back(z);
    }
    dfs(1, n);
    for(int i=0; i<=127; i++)
    {
        printf("%d", ext[i]);
    }
    
    return 0;
}
TLE 20

 

问题 D: 【2022NOIP联测710月11日】友（d）

对每一个点维护以它为根的子树的合法决策放进set，合法的条件是a递减b也递减，这里的a,b是求和之后的也就是suma,sumb，子树向上合并时先满足b递减的条件，如果前驱(b更大)而a更小不满足单调性，当前决策不优，删掉，如果后继(b更小)而a更大那么这个后继不优，删掉，继续找下一个后继直到找到一个不用被删了的为止。

最后b最大的s[x].begin()就是以x为根的答案。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1003;
const int inf = 0x3f3f3f3f;

int n, m, a[maxn], b[maxn];
ll ans;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct node 
{
    int next, to;
}e[maxn<<1];
int head[maxn], len;

void add(int x, int y)
{
    e[++len].to = y; e[len].next = head[x];
    head[x] = len;
}

struct cho 
{
    ll a, b;
    bool operator < (const cho &T) const 
    {
        return b > T.b;
    }
};
vector<cho> ve;
set<cho> s[maxn], sp;
set<cho>::iterator it;

void dfs(int x, int fa)
{
    s[x].insert((cho){a[x], b[x]});
    for(int i=head[x]; i; i=e[i].next)
    {
        int y = e[i].to;
        if(y == fa) continue;
        dfs(y, x);
        sp.clear();
        for(auto p : s[x])
        {
            sp.insert(p);
        }
        for(auto p : sp)
        {
            for(auto q : s[y])
            {
                if(p.a + q.a > m) continue;
                cho r = (cho){p.a+q.a, p.b+q.b};
                s[x].insert(r);
                it = s[x].lower_bound(r);
                if(it != s[x].begin())
                {
                    auto dr = it; dr--;
                    if((*it).a > (*dr).a) s[x].erase(it);
                    else 
                    {
                        dr++; dr++;
                        for(; dr!=s[x].end(); dr++)
                        {
                            if((*it).a < (*dr).a) ve.push_back(*dr);
                            else break;
                        }
                        if(ve.size())
                        {
                            for(auto f : ve) s[x].erase(f);
                            ve.clear();
                        }
                    }
                }
                else 
                {
                    auto dr = it; dr++;
                    for(; dr!=s[x].end(); dr++)
                    {
                        if((*it).a < (*dr).a) ve.push_back(*dr);
                        else break;
                    }
                    if(ve.size())
                    {
                        for(auto f : ve) s[x].erase(f);
                        ve.clear();
                    }
                }
            }
        }
    }
    it = s[x].begin();
    ans = max(ans, (*it).b);
}

int main()
{
    n = read(); m = read();
    for(int i=1; i<=n; i++)
    {
        a[i] = read(); b[i] = read();
    }
    for(int i=1; i<n; i++)
    {
        int x = read(), y = read();
        add(x, y); add(y, x);
    }
    dfs(1, 0);
    printf("%lld\n", ans);
    
    return 0;
}
TLE 60

 

标签：ch,2022NOIPA,int,while,long,only,maxn,联测,dr
From： https://www.cnblogs.com/Catherine2006/p/16779484.html

相关文章

  • 使用HttpOnly缓解最常见的XSS攻击
    什么是HttpOnlyHttpOnly是包含在http返回头Set-Cookie里面的一个附加的flag，所以它是后端服务器对cookie设置的一个附加的属性，在生成cookie时使用HttpOnly标志有助于减轻客......
  • 2022NOIPA层联测6
    设密码比较失败，所以，A.构造字符串（str）并查集维护一下相同的位置，注意到$LCP+1$位置不同，于是每个集合取出来最靠前的为代表，两个集合不同，大集合向小集合连边，每次集合复......
  • 2022NOIP联测5
    T1挑战题意：有两行字符串，有\(*\)和\(.\)两种字符，你可以进行一种操作，将一个格子的\(*\)推到相邻的格子，如果推到一个有\(*\)的格子，那么将\(*\)合并，求最后把所有......
  • go: can only use path@version syntax with 'go get' and 'go install' in module-aw
    一:非gomod模式需要在go文件目录下的src创建代码但是后面的版本一般做项目部管理不适用上述方法也不会出现go:canonlyusepath@versionsyntaxwith'goget'and......
  • 如何在 CentOS 及其衍生版上安装 ONLYOFFICE 文档 v7.2
     使用社区版，您可以在本地服务器上安装 ONLYOFFICE文档，并将在线编辑器与 ​​ONLYOFFICE协作平台​​或​​其他热门系统​​集成在一起。ONLYOFFICE文档是什么ONLYOFFI......
  • 2022NOIPA层联测4
    正手一个[南猪入侵]，反手一个[万箭齐发]，我的[桃]真的快用完了……OI啊(MP)，我(ZP)劝你出手前考虑一下，如果我DEAD了，你可就没牌了……话说难道我没有跳过忠吗？？ 问题A:【202......
  • 多校联测4
    三个字符串可还行T1.字符串还原我一开始读错题了，以为是要不断拆分，回头一看发现只用拆依次，这不就枚举断点，然后用\(hash\)判断不就行了吗。不过这样你会得到80分，原因是不同......
  • Codeforces Beta Round #87 (Div. 1 Only) A. Party（树的深度+dfs）
    https://codeforces.com/contest/115/problem/A题目大意：给定n个节点，每个节点都有一个不同于自己的数值，表示自己的老板，-1表示自己就是老板。现在玩游戏需要组队，一组队......
  • 如何将ONLYOFFICE 桌面编辑器 v7.2 连接到 Seafile 服务器
    ​​ONLYOFFICE桌面编辑器​​是免费开源的办公套件，包括文本文档、电子表格、演示文稿和表单编辑器。您可以离线编辑文件，而且，您也可以将应用程序连接到云端（ONLYOFFICE、Next......
  • 备库状态为read only with apply 但v$managed_standby却未见rfs进程信息
    问题描述：备库状态为readonlywithapply,但查看v$managed_standby视图却未见rfs进程信息,如下所示.SQL>selectopen_modefromv$database;OPEN_MODE--------------------......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99