OK 啊,这就是普通的 a+ba+ba+b 嘛
这是一道十分淼的题目,乍一看,这不就是dijstra堆优化的模板题吗?
首先,建立三个节点,两条线
行,OK 开始 Code
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <bits/stdc++.h>using namespace std;const long long N = 99999, M = 999999;typedef pair<long long, long long> PII;priority_queue<PII, vector<PII>, greater<PII> > q;long long n, p, c, k, x, y, l;long long pre[N];//链表头long long d[N];//dis距离数组bool f[N];//标记数组struct Node { long long v, ne ...
题目描述:
对于一群要互送礼物的朋友,你要确定每个人送出的礼物比收到的多多少(and vice versa for those who view gift giving with cynicism)。
在这一个问题中,每个人都准备了一些钱来送礼物,而这些钱将会被平均分给那些将收到他的礼物的人。
然而,在任何一群朋友中,有些人将送出较多的礼物(可能是因为有较多的朋友),有些人有准备了较多的钱。
给出一群朋友, 没有人的名字会长于 14 字符,给出每个人将花在送礼上的钱,和将收到他的礼物的人的列表,
请确定每个人收到的比送出的钱多的数目。
输入
第 1 行: 人数NP,2<= NP<=10
第 2到 NP+1 行: 这NP个在组里人的名字 一个名字一行
第NP+2到最后: 这里的NP段内容是这样组织的: 第一行是将会送出礼物人的名字。 第二行包含二个数字: 第一个是原有的钱的数目(在0到2000的范围里),第二个NGi是将收到这个送礼者礼物的人的个数 如果 NGi 是非零的, 在下面 NGi 行列出礼物的接受者的名字,一个名字一行。
输出
输出 NP 行
每行是一个的名字加 ...
题意
给出正整数 nnn 和 kkk,定义一个长度为 n×kn \times kn×k,由 1∼n1 \thicksim n1∼n 组成的字符串,当 1∼n1 \thicksim n1∼n 中每个数出现的次数为 kkk,那么这个字符串就为“好串”,令 sss 为好串的个数,问按字典序升序排列后第 ⌈s2⌉\lceil \frac{s}{2} \rceil⌈2s⌉ 个“好串” 是什么?
解题思路
首先我们可以想到:
先打一个全排列枚举每一个“好串”,然后输出即可。但是我们发现,我们的全排列时间复杂度为 O(nnk)\mathcal O(n^{nk})O(nnk),肯定过不了,于是我们用它打表找规律。
n/kn/kn/k
1
2
3
4
5
6
111
111
1,21,21,2
2,1,32,1,32,1,3
2,4,3,12,4,3,12,4,3,1
3,2,5,4,13,2,5,4,13,2,5,4,1
3,6,5,4,2,13,6,5,4,2,13,6,5,4,2,1
222
1,11,11,1
1,2,2,11,2,2,11,2,2,1
2,2,1,3, ...