锐客网

  1. 首页 > it技术 > >

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

ACM

今天打了北师的校内比赛？官方说是个人赛，我们组队打才过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
输入


1
3 3 2
-1 1 4
-3 2 4
-1 1
输出

5
【北京师范大学第十六届程序设计竞赛决赛-重现赛&补题】
题意：有三个长度分别为 n, m, k 的元素值严格递增的整数数组
a, b, c。求 min(abs(ai ? bj) +abs(bj ? cp)) + 3 的值，其中
1 ≤ i ≤ n, 1 ≤ j ≤ m, 1 ≤ p ≤ k。
做法：一个比较简单的思路是枚举bj，找到距离bj 最近的 ai 和cp，更新答案。

#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
输入


1
4 2
1 2 3 4
输出

12
说明

对于样例，长度为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 long using 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+1n || 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); } }




    推荐阅读


    上一篇：utils|对象拷贝工具类（深拷贝）

    下一篇：Linux C中字符拼接函数strcat()（拼接字符串）