北京师范大学第十六届程序设计竞赛决赛-重现赛&补题-白红宇的个人博客

北京师范大学第十六届程序设计竞赛决赛-重现赛&补题

发布日期：2021-05-14 13:34:48 浏览次数：21 分类：精选文章

本文共 5167 字，大约阅读时间需要 17 分钟。

今天打了北师的校内比赛？官方说是个人赛，我们组队打才过5个。。。北师果然强。

今天他需要补的题很多，主要是：

D雷电爆裂之力；F汤圆防漏理论；E可以来拯救吗；

首先是D雷电爆裂之力（比赛的时候没什么思路，就交给队友了，赛后看题解发现真的不难。。。）

链接：https://www.nowcoder.com/acm/contest/117/D

来源：牛客网

题目描述

听说导体切割磁感线可以发电？

今天，zhuaiballl想要做切割磁感线运动，感受雷电的力量。

南北方向有四条马路，从西到东依次是京师路，木铎路，金声路和新街口外大街，可以看成是四条平行的数轴，且相邻的两条数轴之间距离为1m。东西走向有许多小道连接了相邻的马路。假设地磁南极和地理北极重合，地磁北极和地理南极重合。现在zhuaiballl位于京师路的某个位置，想要出发前往新街口外大街，速度为1m/s。由于可能没有一条路径从西到东一直连向新街口外大街，所以每次遇到丁字路口时，zhuaiballl需要选择是往左走还是往右走，样例如下图所示。

zhuaiballl想要感受尽可能强的雷电力量，所以希望从他开始往东走时开始，到他到达新街口外大街所需要的时间尽可能短。

现在，给你附近的地图，你能否求出从zhuaiballl开始往东走时开始，到他到达新街口外大街的最短时间？

输入描述:

第一行是一个正整数T(≤ 20)，表示测试数据的组数，

对于每组测试数据，

第一行是一个整数n,m,k(1≤ n,m,k ≤ 100000)，分别表示连接京师路与木铎路，木铎路与金声路，金声路与新街口外大街的道路个数，

第二行包含n个以空格分隔的整数a1,a2,...,an，表示连接京师路与木铎路的各个小道的南北方向坐标（单位：m），

第三行包含m个以空格分隔的整数b1,b2,...,bm，表示连接木铎路与金声路的各个小道的南北方向坐标（单位：m），

第四行包含k个以空格分隔的整数c1,c2,...,ck，表示连接金声路与新街口外大街的各个小道的南北方向坐标（单位：m），

保证每行坐标按严格递增的顺序给出，并且坐标绝对值不超过109。

输出描述:

对于每组测试数据，输出一行，包含一个整数，表示答案（单位：s）。

示例1

输入

3 3 2

-1 1 4

-3 2 4

-1 1

输出

题意：有三个长度分别为 n, m, k 的元素值严格递增的整数数组

a, b, c。求 min(abs(a_i − b_j) +abs(b_j − c_p)) + 3 的值，其中

1 ≤ i ≤ n, 1 ≤ j ≤ m, 1 ≤ p ≤ k。

做法：一个比较简单的思路是枚举 b_j，找到距离b_j 最近的 a_i 和c_p，更新答案。

#include
    
     #include
     
      using namespace std;typedef long long ll;const ll mod =1000000007;int t;int n,m,k;int a[100005],b[100005],c[100005];int main(){    cin>>t;    while(t--){        cin>>n>>m>>k;        for(int i=1;i<=n;i++){            scanf("%d",a+i);        }        for(int i=1;i<=m;i++){            scanf("%d",b+i);        }        for(int i=1;i<=k;i++){            scanf("%d",c+i);        }        ll ans=1000000000005LL;        int i=1,z=1;        for(int j=1;j<=m;j++){            while(i

F汤圆防漏理论

    题目链接 
http://www.bnuoj.com/v3/contest_show.php?cid=9358#problem/F 
题目 
Time Limit: 1000msMemory Limit: 262144KB 64-bit integer IO format: %lld Java class name: Main  
Submit Status PID: 53076  
ghc很喜欢吃汤圆，但是汤圆很容易被粘(zhān)漏。 
根据多年吃汤圆经验，ghc总结出了一套汤圆防漏理论： 
互相接触的汤圆容易粘(zhān)在一起，并且接触面积不同，粘(zhān)在一起的粘(nián)度也不同。 
当ghc要夹起一个汤圆时，这个汤圆和现在碗里与这个汤圆接触的所有汤圆之间的粘(nián)度的和，如果大于汤圆的硬度，这个汤圆就会被粘(zhān)漏。 
今天ghc又要煮汤圆啦，今天要煮n个汤圆，并且摆盘的方法已经设计好： 
汤圆按照1, 2, \dots , n编号，有m对汤圆互相接触，用x_i, y_i, z_i表示编号为x_i和y_i的两个汤圆互相接触，粘(nián)度为z_i。 
汤圆当然是越软越好吃，但是ghc的厨艺只允许把所有汤圆煮成同样的硬度。那么，汤圆的硬度最小可以是多少，可以满足吃的过程中，存在一种夹汤圆的顺序，使得没有汤圆会被粘(zhān)漏呢？ 
注意： 
不考虑汤圆的重力作用； 
不能同时夹多个汤圆； 
吃完汤圆一定要喝点汤。 
Input 
第一行是一个正整数T(\leq 5)，表示测试数据的组数， 
对于每组测试数据， 
第一行是两个整数n,m(1\leq n,m\leq 100000)， 
接下来m行，每行包含三个整数x_i, y_i, z_i(1\leq x_i, y_i \leq n, x_i \neq y_i, 1 \leq z_i \leq 1000000)， 
同一对汤圆不会出现两次。 
Output 
对于每组测试数据，输出一行，包含一个整数，表示汤圆硬度的最小值。 
Sample Input 
1  
4 6  
1 2 2  
1 3 2  
1 4 2  
2 3 3  
2 4 3  
3 4 5 
Sample Output 
6 
分析 
这道题目思路没错，但是当时程序实现的有些问题 
用一个有序集合set来维护汤圆，set里面存放一个二元组<粘度和，汤圆编号>。

    每次取出set的第一个元素，也就是粘度和最小的汤圆，然后修改与该汤圆所有相接触的汤圆的粘度和。

    set本身是不支持修改集合内元素的功能的，但是可以通过删除原有元素、插入修改后元素来实现。

只需遍历一遍汤圆和所有边，所有时间复杂度为O( (n+m)logn).

#include 
    
     using namespace std;const int maxn=1e5+100;typedef long long ll;typedef pair
     
       pa;set
      
        s; //set自动排序，按第一个关键字vector
       
         g[maxn];ll nd[maxn]; //汤圆的粘度ll vis[maxn];void init(){    memset(nd,0,sizeof(nd));    for(int i=0;i
        
         >T;    while(T--)    {        init();        ll n,m;        cin>>n>>m;        for(int i=1;i<=m;i++)        {            int x,y,z;            cin>>x>>y>>z;            g[x].push_back(pa(y,z));            g[y].push_back(pa(x,z));            nd[x]+=z;            nd[y]+=z;        }        //将所有汤圆放入集合        for(int i=1;i<=n;i++) s.insert(make_pair(nd[i],i));        //一个一个取汤圆        ll ans=0;        while(!s.empty())        {            set
         
          ::iterator it; it=s.begin(); pa now=*it; ans=max(ans,now.first); s.erase(it); //更新粘度 ll u=now.second; vis[u]=1; for(ll i=0;i

E可以来拯救吗

链接：https://www.nowcoder.com/acm/contest/117/E

来源：牛客网

题目描述

quailty is BNU's red sun.

quailty非常喜欢给同学讲题，一天，他又拉着SK给他讲题。

quailty：给一个长为n的序列，求给定子序列的和，会吗？

SK：。。

quailty：给一个长为n的序列，求给定子序列的和的平方，会吗？

SK：。。。

quailty：给一个长为n的序列，求所有子序列的和的平方和，会吗？

SK：。。。。。

quailty：给一个长为n的序列，求所有长为k的子序列的和的平方和，会吗？

SK：。。。。。。。。

quailty：给一个长为n的序列，求所有长为k的子序列的和的平方的异或和，会...

SK：我^(^&*((^%^#……

SK拔出了他的40m长刀，场面就快控制不住了，请你赶快来做出这道题，拯救一下quailty。

quailty is BNU's red sun.

输入描述:

第一行是一个正整数T(≤ 10)，表示测试数据的组数，

对于每组测试数据，

第一行是两个正整数n,k(k ≤ n ≤ 100000)，分别表示序列长度和需要考虑的子序列长度，

接下来一行包含n个不超过1000的正整数，表示序列的n个元素，

为了简化问题，保证，也就是说，需要考虑的子序列不超过100000个。

输出描述:

对于每组测试数据，输出一行，包含一个整数，表示所有长为k的子序列的和的平方的异或和。

示例1

输入

4 2

1 2 3 4

输出

说明

对于样例，长度为2的子序列有[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]，所以答案是9^16^25^25^36^49=12（这里'^'是C++中的异或运算符）。

题意：给一个长为 n 的序列需要对所有长为 k 的子序列求和的平方的异或和，保证 Ck ≤ 105。

做法：dfs 枚举。一个 trick 是，n 和 k 都可能很大，比如

n = 100000, k = 99999，此时正常的枚举子序列会严重超时。解决办法是当 k ≥ n/2 时，令 k = n − k，然后枚举反面即可。

#include 
    
     #define LL long longusing namespace std;const int N=100005;LL ans,sum;int n,k,a[N];bool f;void dfs(int t,int x,LL he){    if (n-t+1
     
      n || x==k)    {        if (x==k && f) ans^=(sum-he)*(sum-he);        else if (x==k) ans^=he*he;        return;    }    dfs(t+1,x,he);    dfs(t+1,x+1,he+(LL)a[t]); }int main(){    int T;scanf("%d",&T);    while (T--)    {        ans=0;f=0;        scanf("%d%d",&n,&k);if (k>n/2) k=n-k,f=1;sum=0;        for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=(LL)a[i];        dfs(1,0,0);        printf("%lld\n",ans);    }}

上一篇：训练总结报告

下一篇：省赛练习2——第八届福建省大学生程序设计竞赛 &补题

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章