首页 > 其他分享 >2023年暑假集训总结/7.3

2023年暑假集训总结/7.3

时间：2023-07-03 19:44:46浏览次数：45  
标签：10 int house ll 7.3 v3 2023 集训 define

2023年暑假集训总结/7.3

预估成绩：100+50+40+20=210

实际成绩：100+25+24+25=174

T1房

题意：有n个已知中心和长度且互不重合的区间，问有多少个长度为t的区间恰好与其中一个区间的一个端点相等，且不与所有区间重合

思路&做法：

　　签到题，注意到答案上界为2n，只需要依次枚举接在每个区间左右的长度为t的区间是否与其他区间重合即可。

　　在考场上只花了10分钟就做出来了，但仍有一些坑点：

　　　　1.给定的区间中点不是按照大小排序的，需要自己排序

　　　　2.左右边界有可能是小数，需要手动乘2或开double

std：

#include <bits/stdc++.h>
typedef long long ll;
using std::min; using std::max;
#define INF 1e18
#define pE() puts("")
#define W(x) write(x)
#define rd() read<ll>()
#define lowbit(x) -x & x
#define pS() putchar(' ')
#define E(i, l, r) for (int i = l; i <= r; ++ i)
template <typename T>
inline T read() {
    T x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x / 10) write(x / 10);
    putchar((x % 10) ^ 48);
}
const int N = 1e5 + 5;
struct Node {
    ll x, a;
    friend bool operator < (Node lhs, Node rhs) {
        return lhs.x < rhs.x;
    }
} house[N];
int n, t;
ll res[N * 2], cnt;
int main() {
    freopen("house.in", "r", stdin);
    freopen("house.out", "w", stdout);
    n = rd();
    t = rd();
    E(i, 1, n) {
        house[i].x = rd() * 2;
        house[i].a = rd() * 2;
    }
    std::sort(house + 1, house + n + 1);
    E(i, 1, n) {
        if (i == 1 || house[i].x - house[i].a / 2 - 2 * t >= house[i - 1].x + house[i - 1].a / 2)
            res[++ cnt] = house[i].x - house[i].a / 2 - t;
        if (i == n || house[i].x + house[i].a / 2 + 2 * t <= house[i + 1].x - house[i + 1].a / 2)
            res[++ cnt] = house[i].x + house[i].a / 2 + t;
    }
    std::sort(res + 1, res + cnt + 1);
    int ans = std::unique(res + 1, res + cnt + 1) - res - 1;
    W(ans);
    return 0;
}

T2车

题意：有一个n个点的环，给定k个询问，每个询问给定一个v，从一个点出发加一次油可以到距离小于v的最远点，求从任一点出发跑完整个环需要加油的最小次数。

思路&做法：

　　考场上先胡了一个kn^2的50分做法，剩下的点打了一个随机化，结果没开longlongWA了25分。

　　容易证明从一个点出发顺时针和逆时针跑的代价是相等的。

　　实际上对于每一个询问，将环断为链再复制一份拼接在后面，就可以双指针O(n)处理处从i开始加一次油能跑到的最远距离，再借此转移出从j到2n所需的加油次数，然后用并查集维护即可。

std：

#include <bits/stdc++.h>
typedef long long ll;
using std::min; using std::max;
#define INF 1e18
#define pE() puts("")
#define W(x) write(x)
#define rd() read<ll>()
#define lowbit(x) -x & x
#define pS() putchar(' ')
#define E(i, l, r) for (int i = l; i <= r; ++ i)
template <typename T>
inline T read() {
    T x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x / 10) write(x / 10);
    putchar((x % 10) ^ 48);
}
const int N = 1e5 + 5;
ll n, k, w[N], sum[N], ans;
ll fa[N], R[N], Sum[N];
int getfa(int x) {
    if (fa[x] == x)
        return x;
    return fa[x] = getfa(fa[x]);
}
int main() {
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);
    n = rd();
    k = rd();
    E(i, 1, n) {
        w[i] = rd();
        w[i + n] = w[i];
    }
    E(i, 1, 2 * n)
        sum[i] = sum[i - 1] + w[i];
    while (k --) {
        int r = 0;
        ll v = rd();
        bool flag = 0;
        E(i, 1, n)
            if (w[i] > v) {
//                std::cout << w[i] << ' ' << v << '\n';
                flag = 1;
                W(-1); pE();
                break;
            }
        if (flag) continue;
        E(i, 1, 2 * n)
            fa[i] = i;
        E(i, 1, 2 * n) {
            while (sum[r] - sum[i - 1] <= v && r + 1 <= n * 2)
                ++ r;
            R[i] = r;
        }
        Sum[n * 2] = 0;
        for (int i = n * 2 - 1; i; -- i)
            Sum[i] = Sum[R[i]] + 1;
        ans = 1e9;
        E(i, 1, 2 * n - 1) {
            fa[getfa(i)] = getfa(R[i]);
            if (i >= n) {
                int tmp = i - n + 1;
                ans = min(ans, Sum[tmp] - Sum[getfa(tmp)]);
            }
        }
        W(ans); pE();
    }
    return 0;
}

T3家

题意：有一个有n个节点的树，对于一个1-n的排列p，满足pi≠i，定义它的代价为i到pi的距离之和，求出最小或最大代价及其对应的排列

思路&做法：

　　考场上先无脑把n≤10的dfs打出来，然后考虑部分分，对于树是一条链求最小值的情况，贪心地将1与2交换，3与4交换，以此类推，若n为奇数则将最后三个点顺次交换即可。对于树是菊花图求最大值的情况，将中心节点找出与随意一个节点交换，其他点也随意交换即可。打完这些我再去考虑一般情况，可以发现当求最大值时是可以模拟退火的，而求最小值时则因数据太过分散不行，考虑贪心地在树上交换，可惜打完模拟退火就没有时间打贪心，模拟退火也超时了，得不偿失。

　　考虑正解。

　　最小时，那么就是在树上贪心，如果我们从子树到某个点 x，留下来大于等于两 个点还要往上，肯定不优，所以大致就是直接贪心的进行匹配就可以了，具体的，只能 留下一个点去匹配。

　　最大时，通过推导重心，只要某个子树内的点都不走到它子树内就是可行的，然后每次选两个距离较大的节点进行匹配就行了。

std：

　　这道题理解起来不容易，码量也大（我打了5k左右），还没有调出来，只能暂时放别人的代码。

#include <bits/stdc++.h>
#define int long long
#define pb push_back 
using namespace std;
const int INF=1e6+5;
int n;
namespace S{
    int sz[INF],rt,Max1,ans[INF],res,p[INF];
    vector <int> e[INF],v3[INF];
    void DFS(int x,int fa) {
        sz[x]=1;
        for (int v:e[x]) {
            if (v==fa) continue;
            DFS(v,x);
            sz[x]+=sz[v];
            res+=min(sz[v],n-sz[v]);
        }
    }
    void DFS2(int x,int fa) {
        int Max=0;
        for (int v:e[x]) {
            if (v==fa) continue;
            DFS2(v,x);
            Max=max(Max,sz[v]);
        }
        Max=max(Max,n-sz[x]);
        if (Max<Max1) Max1=Max,rt=x;
    }
    void DFS3(int x,int fa,int t) {
        v3[t].pb(x);
        for (int v:e[x]) {
            if (v==fa) continue;
            DFS3(v,x,t);
        }
    }
    struct _node_queue {
        int pos,dis_v;
        bool operator < (const _node_queue &x) const {
            return x.dis_v>dis_v;
        }
    };
    priority_queue < _node_queue >q;
    void solve() {
        for (int i=1;i<n;i++) {
            int x=0,y=0;cin>>x>>y;
            e[x].pb(y);e[y].pb(x);
        }
        Max1=1e9;
        DFS(1,0);
        DFS2(1,0);
        int cnt=0;
        for (int v:e[rt]) {
            cnt++;
            DFS3(v,rt,cnt);
        }
        for (int i=1;i<=cnt;i++) p[i]=i;
        for (int i=1;i<=cnt;i++) q.push({i,v3[i].size()});
        while (q.size()>1) {
            auto it=q.top();q.pop();
            auto it2=q.top();q.pop();
            int l=it.pos,r=it2.pos;
            p[l]=l;p[r]=r;
            if (v3[p[l]].size() && v3[p[r]].size()) {
                ans[v3[p[l]].back()]=v3[p[r]].back();
                ans[v3[p[r]].back()]=v3[p[l]].back();
                v3[p[l]].pop_back();v3[p[r]].pop_back();
            }
            if (v3[l].size()) q.push({l,v3[l].size()});
            if (v3[r].size()) q.push({r,v3[r].size()});
        }
        if (n%2==0) {
            int l=q.top().pos;
            if (v3[l].size()) {
                ans[v3[l].back()]=rt;
                ans[rt]=v3[l].back();
            }
        }
        else {
            ans[rt]=2;
            ans[ans[2]]=rt;
        }
        cout<<res*2<<"\n";
        for (int i=1;i<=n;i++) cout<<ans[i]<<" ";
        cout<<"\n";
    }
}
namespace S1{
    const int INF=1e6+5;
    struct _node_edge{
        int to_,next_;
    }edge[INF<<1];
    int tot,head[INF],vis[INF],cnt[INF],ans,ans2[INF];
    void add_edge(int x,int y) {
        edge[++tot]={y,head[x]};
        head[x]=tot;
    }
    void DFS(int x,int fa) {
        for (int i=head[x];i;i=edge[i].next_) {
            int v=edge[i].to_;
            if (v==fa) continue;
            DFS(v,x);
        }
        cnt[0]=0;
        for (int i=head[x];i;i=edge[i].next_) {
            int v=edge[i].to_;
            if (v==fa) continue;
            if (vis[v]) cnt[++cnt[0]]=vis[v],ans++;
        }
        cnt[++cnt[0]]=x;
        for (int i=1;i+1<=cnt[0];i+=2)
            ans2[cnt[i]]=cnt[i+1],ans2[cnt[i+1]]=cnt[i];
        if (cnt[0]&1) {
            if (cnt[0]==1) {
                if (x==1) {
                    for (int i=head[x];i;i=edge[i].next_) {
                        int v=edge[i].to_;
                        ans2[x]=ans2[v];ans2[v]=1;
                        break;
                    }
                    ans++;
                }
                else vis[x]=cnt[cnt[0]];
            }
            else {
                ans2[cnt[cnt[0]-2]]=cnt[cnt[0]-1];
                ans2[cnt[cnt[0]-1]]=cnt[cnt[0]];
                ans2[cnt[cnt[0]]]=cnt[cnt[0]-2];
            }
        }
    }
    void solve(){
         for (int i=1;i<n;i++) {    
            int x=0,y=0;cin>>x>>y;
            add_edge(x,y);add_edge(y,x);
        }
        DFS(1,0);
        cout<<ans*2<<"\n";
        for (int i=1;i<=n;i++) cout<<ans2[i]<<" "; cout<<"\n"; 
    }
}
signed main()
{
    // freopen("data.in","r",stdin);
    ios::sync_with_stdio(false);
    int t=0;
    cin>>n>>t;
    if (t==2) S::solve();
    else S1::solve();
    return 0;
}

T4数

题意：给定n、k，问1至n中有多少数的各位数字和等于其乘k之后的各位数字和。

思路&做法：

　　对于n≤1e6，可以直接枚举，能拿20分（实际上可以卡到25分），对于更大的情况就需要找规律，发现若k模3不余1的情况下所有满足条件的数都是9的倍数，或许可以进行优化，之后在考场上我就不能推出更多有用的结论。

　　正解是数位dp，从低位往高位 dp，记录进位，以及 f(x × k) 和 f(x) 的值，然 后发现不行，那么记录两个差值就好了。

std：

#include <bits/stdc++.h>
#define int long long
typedef long long ll;
using std::min; using std::max;
#define INF 1e18
#define pE() puts("")
#define W(x) write(x)
#define rd() read<ll>()
#define lowbit(x) -x & x
#define pS() putchar(' ')
#define E(i, l, r) for (int i = l; i <= r; ++ i)
template <typename T>
inline T read() {
    T x = 0; bool f = 0; char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x / 10) write(x / 10);
    putchar((x % 10) ^ 48);
}
ll n, k, ans;
ll g[335];
ll f[21][335][1005][3];
signed main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
    n = rd();
    k = rd();
    int tmp = n;
    int N = 165;
    while (tmp) {
        g[++ g[0]] = tmp % 10;
        tmp /= 10;
    }
    E(i, 0, 9) {
        int opt = 0;
        if (i < g[1])
            opt = 0;
        else if (i == g[1])
            opt = 1;
        else opt = 2;
        ++ f[1][i * k % 10 - i + N][i * k / 10][opt];
    }
    E(i, 2, g[0])
        E(j, -N, N)
            E(l, 0, 999)
                E(p, 0, 2) {
                    E(p1, 0, 9) {
                        int p2 = p;
                        if (p1 > g[i])
                            p2 = 2;
                        else if (p1 < g[i])
                            p2 = 0;
                        f[i][(p1 * k + l) % 10 - p1 + j + N][(l + p1 * k) / 10][p2] += f[i - 1][j + N][l][p];
                    }
                }
    ll res = 0;
    E(j, -N, N)
        E(l, 0, 999) {
            ll tmp = l, sum = 0;
            while (tmp) {
                sum += tmp % 10;
                tmp /= 10;
            }
            if (j + sum == 0)
                res += f[g[0]][j + N][l][0] + f[g[0]][j + N][l][1];
        }
    W(res - 1);
    return 0;
}

标签：10,int,house,ll,7.3,v3,2023,集训,define
From： https://www.cnblogs.com/determination/p/17523822.html

相关文章

  • 暑假周记（7.3）
    今日周一，又是新的一周、新的一天，昨天那么多愁善感那是我么？当然是，但是那又有什么关系，负面情绪就是要那样发泄出来，今天的我又是新的我。七月三号了，距离去补习班上班还有不到一周，去教四五年级的小朋友们英语，正好上这个班又可以让我的作息更加规律有效帮助我大二的作息，只要回学校的时......
  • 7.3总结
    上午起床之后送妹妹上学，回来后在床上躺了会，然后做pta，现在对于20分的题做起来很吃力，但是要是把题一点一点看明白，还是能够做得出来，中午闲着在床上看了几页的《大道至简》，感觉很有意思，但是电子版看起来不是很舒服，然后就睡了一会，下午就开始慢慢把做过的pta整理到报告中，先扩充了目录，让......
  • 2023.7.3
    ##输入带空格的字符串~~~c++1.#include<string.h>strings;getline(cin,s);2.#include<cstring>#include<stdio.h>chara[1024];gets(a);intlen=strlen(a);//得到数组的实际长度~~~##填充输入~~~javasetw(intn)//用来控制输出间隔//例：cout<<'s&......
  • Silhouette 2023.0.1 CE 影视后期ROTO跟踪抠像合成软件 支持AE/PR/达芬奇/VEGAS/OFX插
    Silhouette是一款被广泛应用于影视剧中Roto、抠像、擦威亚的特效合成辅助软件，正所谓术业有专攻，它就是为了应对这些脏活累活而诞生的。之前还有一款软件CommotionPro，但是已经停止开发，目前已经被这款Silhouette所替代，目前它也属于BorisFX家族的一员。软件下载Silhouette2023.......
  • day81（2023.7.3）
    1.依赖冲突调解_最短路径优先原则 2.依赖冲突调解_最先声明原则3.依赖冲突调解_排除依赖、锁定版本 4.Maven聚合开发_聚合关系 5.Maven聚合开发_继承关系6.Maven聚合案例_搭建父工程7.Maven聚合案例_搭建dao模块8.Mave......
  • 2023/7/03
    今天学习了Java中的inal，多态抽象类和接口final相当于C++中的const，对于用final声明的变量，一旦被设定，就不能改变改变量的值，一对象的引用被final修饰后，他就只能恒定指向一个对象无法使其指向另一个对象。在父类中被final修饰的方法不能在子类中被隐藏，被final修饰的类是不能被继承的......
  • 记一次.net加密神器 Eazfuscator.NET 2023.2 最新版 使用尝试
    合集-.net代码混淆加密产权保护(2) 1.记一次.net加密神器Eazfuscator.NET2023.2最新版使用尝试06-272.将SmartAssembly与单文件可执行文件一起使用（.NETCore6）06-27收起 很多人看到这个Eazfuscator.NET还不知是什么东东。。。首先介绍下。什么是Eazfu......
  • C++面试记录——2023.7.3
    1、什么是虚函数？（基础反而卡住了，往多态方面说了）  2、虚函数实现原理？（不知道） 3、什么是完美转发？（没学深，浅浅说了跟右值引用相关） 4、构造函数有哪些？（默认、带参、拷贝、移动） 5、现有一个右值变量，如何调用移动构造函数？（麻了，不会） 6、知道lambda表达式吗？（C++11特性，匿......
  • SketchUp Pro 2023-草图大师3D设计软件mac/win版
    SketchUpPro2023是一款领先的3D建模和设计软件，广泛应用于建筑、室内设计、景观规划、工业设计等领域。它以其直观易用的特点而受到许多设计师和建筑专业人士的青睐。→→↓↓载SketchUpPro2023mac/win版 SketchUpPro2023拥有用户友好的界面和简单直观的工作流程，使得从......
  • 20230703赛后复盘
    复盘时间安排8:00~8:30写&调试T1正解，过样例8:30~8:50想写T2正解，然而胡错了（所以又重写了）8:50~9:10写T2的\(O(kn^2)\)部分分然后瞟了眼T3感觉不会，跳过去看T49:10~9:40推T4的正解。推了一半，卡在进位的处理上（悲）9:40~9:50爬去写暴力9:50~10:00回头写了个T3部分分最后一个多......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99