南京信息工程大学2019 届新生程序设计大赛题解
A – 搭梯子
可知任意一根木条均可作为梯子的阶，所以为了搭出最多的阶数，我们可将最长的两根木条 $(a_{max_1},a_{max_2})$ 作为梯子两侧的边。由此，我们可知 $min(a_{max_2}-1 , n-2)$ 为此题的解。
求解第二长木条有多种方法：
1.整体扫描记录第一长与第二长，$O(n)$ 时间。
#include <iostream>
#include <algorithm>
using namespace std;
int inp[100010];
int main(){
int t;
cin >> t;
while(t--){
int n, max1 = 0, max2 = 0;
cin >> n;
for(int i = 0; i < n; i ++){
cin >> inp[i];
if(inp[i] >= max1){
max2 = max1;
max1 = inp[i];
}
else if(inp[i] > max2){
max2 = inp[i];
}
}
cout << min(max2-1, n-2) << endl;
}
return 0;
}
2.排序后取第二长。快排$O(n\cdot \log (n))$可过，冒泡、选择排序与劣质手写快排不可过。
#include <iostream>
#include <algorithm>
using namespace std;
int inp[100010];
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 0; i < n; i ++){
cin >> inp[i];
}
sort(inp, inp+n);
cout << min(inp[n-2]-1, n-2) << endl;
}
return 0;
}
B – Tree on Graph
建反边:
$ed$ 能连接到 $k$ 个点, 则总共有 $k-1$ 条边；
在最短路径确定的情况下，共享的路径长度越长越好，等价于每个点的前驱边越短越好；
综上，对于每个点，每次更新 $ed$ 到它的最短距离时，顺便更新前驱边。
C – 欢迎来到算法至上主义的比赛
ctrl+cctrl+v
D – 键值数据库
暴力做法
用一个 $500000$ 的数组作为表，查找、添加、删除键值对都是 $O(1)$.
弹出具有最大价值的所有键，遍历一次数据表，找出最大值，再升序遍历一次，删除对应键，将对应键存储到另一个数组中，最后输出。时间复杂度 $O(M)$，其中 $M = 500000$.
查询中位数键对应的值，同样遍历一次数据表，存储所有有效键，直接找到中位数键，并输出对应值，时间复杂度 $O(M)$.
总体时间复杂度 $O(qM)$
优化1：用 vector<int> 存储所有有效键，查询中位数键前先排序一遍，时间复杂度降为 $O(q(n+q)log(n+q))$。
优化2：用 vector<int> 存储所有有效键，插入时用二分查找保证有序性，时间复杂度降为 $O(q(n+q))$.
正解
对于第一种操作，至少需要一个 map<key, value> 来存储。
对于第二种操作，需要有序反向映射，即 map<value, set<key> >。
对于第三种操作，容易想到对顶堆，然而 priority_queue 不支持删除，可删堆又不支持查找，什么结构可用呢？
set<key>: 那当然是……
map<key, value>: 当然是我了
map<int, set<int>, greater<int> > vk_map; map<int, int> heap[2];
用两个 map<key, value> 模拟对顶堆，同步维护反向映射。
第一种操作：若没有该键，直接加入对顶堆，同步更新反向映射，若有，先删除原键值对，再加入新键值对。复杂度 $O(log(len))$，其中 $len$ 为数据库中键的个数。
第二种操作：取反向映射中的第一个，即最大值，输出集合中所有键，同步从对顶堆中删除键，然后从反向映射中删除最大值。最坏情况：一次删除所有键，复杂度 $O(len\cdot log(len))$，由于所有删除的键的数量不会超过 $n + q$，所以整体复杂度 $O((n+q)log(n+q))$。
第三种操作：从对顶堆中查找中位数键，输出对应值。复杂度 $O(log(len))$。
最终整体复杂度 $O((n+q)log(n+q))$。
E – 后四位
如题目所示
$$
25 = 1\cdot{2^4}+1\cdot{2^3}+0\cdot{2^2}+0\cdot2^1+1\cdot2^0\
3^{25} =3^{1\cdot2^4}\cdot 3^{1\cdot2^3} \cdot 3^{0\cdot2^2} \cdot 3^{0\cdot2^1} \cdot 3^{1\cdot2^0}\
\ \ \ \ \ =3^{1\cdot2^0}\cdot 3^{0\cdot2^1} \cdot 3^{0\cdot2^2} \cdot 3^{1\cdot2^3} \cdot 3^{1\cdot2^4}\
3^{2^4} = 3^{2^3}\cdot 3^{2^3}\
\cdots\
3^{2^1} = 3^{2^0}\cdot 3^{2^0}\
$$
用一个循环来依次得到 $\huge 3^{2^0},3^{2^1},\cdots,3^{2^{\lfloor \log_{2}{(n)}+1\rfloor}}$
int a = 3;
for(int i = 0;i < n;i++)
{
a;//所求序列
a *= a;
}
利用 c 的位运算,分解 $n$为其二进制的每一位
void pow(unsigned int n)
{
while(n)
{
n&1;//所求的二进制序列
n>>=1;
}
}
综合起来
unsigned int pow(unsigned int base,unsigned int n)
{
unsigned int ans = 1;
while(n)
{
if(n&1)
{
ans*=base;
}
base*=base;
n>>=1;
}
return ans;
}
这道题目要求保留后四位,那也就是对 $10^4$取模
因此
unsigned int pow(unsigned int base,unsigned int n)
{
const unsigned int MOD = 10000;
unsigned int ans = 1;
while(n)
{
if(n&1)
{
ans*=base;
ans%=MOD;
}
base*=base;
base%=MOD
n>>=1;
}
return ans%MOD;
}
F – 传送门
针对 OIer
- 建立空图 $G$
DFS找出连通块 作为 $G$ 的节点- 暴力搜索 , 图上建边
- 注意有的连通块完全不靠墙, 尤其是出发的块
- 这一部分可以做到 $O(n^2)$ 标程中未给出,请自行考虑具体实现
- 图上找最短路
- $\textrm{最短路径长}+1$ 即为所求答案
- 最短路长为 $0$ 即 用户和出口在同一块地面时,输出
0
- 最短路长为 $0$ 即 用户和出口在同一块地面时,输出
针对新手
连通块
可以看出,这题的结果与每一块 ‘可以自由走动的地面‘ 的大小及形状没有关系
有影响的,是这些 ‘可以自由走动的地面‘ 之间的关系,即
- 从 某一片 ‘可以自由走动的地面‘ 可不可以传送到 另一片 ‘可以自由走动的地面‘ 上
为了方便描述, 定义 一片 ‘可以自由走动的地面‘ 为 一块 连通块
首先,为了了解 连通块 之间的关系, 我们希望计算出
- 有多少连通块
- 每片地面属于哪一块连通块
为了存储这两个问题的答案,我们声明两个变量
int connectedBlockCount = 0;
int theBlockGroundBelongsTo[n][m] = {-1};
约定,
theBlockGroundBelongsTo[i][j]代表 $(i,j)$ 这片地面所对应的 连通块 的序号,为 $[0,connectedBlockCount)$ 中的正整数connectedBlockCount代表所有已知的 连通块的数量
然后,我们对于所有的格子进行检查
- 是地面吗?
- 还没有编号吗?
如果满足这两个条件,就 connectedBlockCount++; , 并且为这块路面 赋予编号
在给一个格子赋予编号之后,检查其相邻的格子,如果也满足以上两个条件,则也赋予相同的编号并进行这个检查
这是递归哦,为了不无限递归,记得先赋予编号
传送的可能性
直接对于每个坐标,暴力查找其各个方向所对的墙壁是否宜于传送.
但是有几个地方需要注意
- 某些连通块可能不靠墙,也就无法传送离开
- 真正有用的信息是 : 从 $x$ 号连通块可以传送到 $y$ 号连通块
如何传送
这一部分其实就是在一张有向图上找最短路.
简单来说,对于任意的连通块,保存一个列表来记录从这个连通块可以直接到达的连通块的 序号
实现上来说,可以是二维数组,也可以是 std::vector<std::vector<size_t> >
然后顺这这个关系开展搜索,每个连通块记录其已知的最短距离并在搜索过程中更新.
- $\textrm{最短路径长}+1$ 即为所求答案
- 最短路长为 $0$ 即 用户和出口在同一块地面时,输出
0
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
//#define DEBUG
const int MAX_M = 100;
const int MAX_N = 100;
const int DIR[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
using BlockID = int;
const BlockID VOIDBLOCK = -1;
struct coordinate
{
int x, y;
};
inline coordinate operator+(const coordinate pos,int dir)
{
return {pos.x+DIR[dir][0],pos.y+DIR[dir][1]};
}
class Block
{
public:
Block() : ableToLeaveViaPortal(false), vistied(false), portalCount(-1), portalFrom(VOIDBLOCK) {}
std::vector<coordinate> member;
std::set<BlockID> edge;
bool ableToLeaveViaPortal;
bool vistied;
int portalCount;
BlockID portalFrom;
};
std::vector<Block> blocks;
BlockID theBlockGroundBelongsTo[MAX_M][MAX_N];
bool passable[MAX_M][MAX_N];
bool visibility[MAX_M][MAX_N];
//+--------->y/n
//|
//|
//|
//|
//v
//x/m
inline bool isUnidedGround(int m, int n)
{
return passable[m][n] && theBlockGroundBelongsTo[m][n] == VOIDBLOCK;
}
inline int setBlockID(coordinate pos,BlockID id)
{
return theBlockGroundBelongsTo[pos.x][pos.y]=id;
}
int getBlockID(int m, int n)
{
if (isUnidedGround(m, n))
{
int currentID = blocks.size();
blocks.push_back(Block());
std::queue<coordinate> que;//BFS based on queue;
que.push({ m, n });
while (!que.empty())
{
coordinate curPos = que.front();
que.pop();
setBlockID(curPos,currentID);
blocks[currentID].member.push_back(curPos);
for (size_t i = 0; i < 4; i++)
{
if (isUnidedGround(curPos.x + DIR[i][0], curPos.y + DIR[i][1]))
{
que.push(curPos+i);
setBlockID(curPos+i,currentID);
}
}
}
return currentID;
}
else
{
return theBlockGroundBelongsTo[m][n];
}
}
inline int getBlockID(coordinate pos)
{
return getBlockID(pos.x, pos.y);
}
std::set<BlockID>& getPossiblePortal(coordinate pos, std::set<BlockID>& ans)
{
if (visibility[pos.x][pos.y])
{
for (int i = 0; i < 4; i++)
{
int dis = 1;
while (visibility[pos.x + dis * DIR[i][0]][pos.y + dis * DIR[i][1]])
{
++dis;
}
--dis;
if (passable[pos.x + dis * DIR[i][0]][pos.y + dis * DIR[i][1]])
{
ans.insert(getBlockID(pos.x + dis * DIR[i][0], pos.y + dis * DIR[i][1]));
}
}
}
return ans;
}
inline bool nextToWall(coordinate pos)
{
if (passable[pos.x][pos.y])
{
for (int i = 0; i < 4; i++)
{
if (!visibility[pos.x + DIR[i][0]][pos.y + DIR[i][1]])
{
return true;
}
}
}
return false;
}
int main(void)
{
long T = 0;
int m, n, sx = 0, sy = 0, tx = 0, ty = 0, ans = -1;
BlockID sBlock, tBlock;
//std::ios::sync_with_stdio(false);
std::cin >> T;
// std::cout<<0<<std::endl;
// std::cout<<T<<std::endl;
while(T--)
//while (std::cin >> m >> n)
{
//input
{
std::cin >> m >> n;
}
//ini
{
blocks.clear();
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
theBlockGroundBelongsTo[i][j] = VOIDBLOCK;
passable[i][j] = false;
visibility[i][j] = false;
}
}
}
//read map
{
for (int i = 0; i < m; i++)
{
std::string input;
std::cin >> input;
for (int j = 0; j < n; j++)
{
switch (input[j])
{
case '.':
visibility[i][j] = true;
passable[i][j] = false;
break;
case 'w':
visibility[i][j] = false;
passable[i][j] = false;
break;
case 'g':
visibility[i][j] = true;
passable[i][j] = true;
break;
case 'p':
visibility[i][j] = true;
passable[i][j] = true;
sx = i;
sy = j;
break;
case 'e':
visibility[i][j] = true;
passable[i][j] = true;
tx = i;
ty = j;
break;
default:
break;
}
}
}
}
//BFS for connected Block
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
getBlockID(i, j);
}
}
}
//search for edges
{
for (BlockID id = 0; id < (int)blocks.size(); id++)
{
Block& currentBlock = blocks[id];
for (coordinate pos : currentBlock.member)
{
if (nextToWall(pos))
{
currentBlock.ableToLeaveViaPortal = true;
break;
}
}
if (blocks[id].ableToLeaveViaPortal)
{
for (coordinate pos : currentBlock.member)
{
getPossiblePortal(pos, currentBlock.edge);
}
}
}
}
//BFS for route
{
sBlock = getBlockID(sx, sy);
tBlock = getBlockID(tx, ty);
if (sBlock != tBlock)
{
if (blocks[sBlock].ableToLeaveViaPortal)
{
std::queue<BlockID> que;
que.push(sBlock);
blocks[sBlock].portalCount = 1;
blocks[sBlock].vistied = true;
while (!que.empty())
{
BlockID curBlockID = que.front();
Block& curBlock = blocks[curBlockID];
for (BlockID id : curBlock.edge)
{
if (!blocks[id].vistied)
{
blocks[id].portalFrom = curBlockID;
blocks[id].portalCount = curBlock.portalCount + 1;
blocks[id].vistied = true;
que.push(id);
}
}
que.pop();
}
ans = blocks[tBlock].portalCount;
}
else
{
ans = -1;
}
}
else
{
ans = 0;
}
}
//output result
{
std::cout << ans;
//if(T)
{
std::cout<<std::endl;
}
}
//std::cout<<0<<std::endl;
// {
// std::clog << "Report:" << std::endl;
// }
// {
// std::clog << "BlockID:" << std::endl;
// for (int i = 0; i < m; i++)
// {
// for (int j = 0; j < n; j++)
// {
// std::clog << std::setw(3) << getBlockID(i, j) << ' ';
// }
// std::clog << std::endl;
// }
// }//check connectedBlock
// {
// std::clog << "Edges:" << std::endl;
// for (BlockID id = 0; id < (int)blocks.size(); id++)
// {
// std::clog << "BlockID:" << std::resetiosflags(std::ios::left | std::ios::right) << std::setiosflags(std::ios::left) << std::setw(3) << id << std::setiosflags(std::ios::right);
// std::clog << "PortalCount:" << std::setw(3) << blocks[id].portalCount;
// std::clog << "From:" << std::setw(3) << blocks[id].portalFrom;
// std::clog << "Portal to:";
// for (BlockID edge : blocks[id].edge)
// {
// std::clog << std::setw(3) << edge;
// }
// std::clog << std::endl;
// }
// }//check edge
}
return 0;
}
H – 假·签到题
判断一个数字有几个因子可以在 $O(n)$ 时间内处理，即穷举 $i\in [1,n]$ ,判断 $i$ 是否为 $n$ 的因子。这样可以用两重循环把结果统计出来。最终复杂度 $O(n^2)$ 。
#include <iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
int cnt=0;
for(int j=1;j<=i;j++){
if(i%j==0){
cnt++;
}
}
if(cnt==4){
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}
G – 真·签到题
这个题目和上一个题目唯一的区别是数据范围扩充到了 $10^9$ , 如果还是用 $O(n^2)$ 的算法大概要算 $10^{10}$ 秒，也就是 $317$年左右……
所有我们要想办法降低时间复杂度。考虑任何一个 $4$ 因子数，只有两种情况，一种是立方数，一种是有且仅有两个素因子。立方数很好处理，数量就是 $^{3}\sqrt{n}$ 。 接下来我们要找出 $[1,n]$ 内所有有且仅有两个素因子的数的个数。 对于任意一个满足条件的数字，我们不妨记为 $a$ ，满足：
$$a = p\times\ q$$
其中 $p,q$ 均为素数。由 $p \neq q$ ，不妨设 $p < q$ ，对于任意确定的 $p$ , 我们要统计所有的 $a$ 满足 $a\leq n$。即 $q \leq floor(\frac{n}{p})$ , 则 $q$ 满足:
$$p < q\leq floor(\frac{n}{p})$$
$q$的个数即为区间内素数的个数。我们考虑所有的素数 $p$ 满足 $p\in [2,sqrt(n)]$ , 求解对应 $q$ 的个数即可。我们预处理 $f(n)$ 表示小于等于 $n$ 的素数的个数，从而可以在 $O(sqrt(n))$ 的时间复杂度里解决问题。
接下来我们要处理的问题，就是低于线性时间的将 $f(n)$ 求出来。线性时间的话线性筛一下就做出来了。但是线性时间还不够快，要低于线性时间，我们引入一个算法洲阁筛，可以在 $O(\frac{n^\frac{3}{4}}{\ln n})$ 时间里预处理出来。考虑到大部分同学没有数论方面的基础，可以查看如下链接
一般来说该算法处理问题的上限在 $10^{11}$ 左右，但是为了防止被看出是模板题并且简化题目，所以题目里用了 $10^9$。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const ll maxm = 1e11;
const ll maxp = sqrt(maxm) + 10;
ll f[maxp],g[maxp];
bool isprime[maxn];
int prime[maxn];
int tot = 0;
void init()
{
for(int i = 2; i < maxn; i ++) isprime[i] = true;
for(int i = 2; i < maxn; i++){
if(isprime[i]) prime[tot++] = i;
for(int j = 0; j < tot && i * prime[j] < maxn; j++){
isprime[i * prime[j]] = false;
if(i % prime[j] == 0) break;
}
}
}
ll solve(ll n)
{
ll i,j,m;
for(m = 1; m * m <= n; m++) f[m] = n/m - 1;
for(i = 1;i <= m; i++) g[i] = i-1;
for(i = 2; i <= m; i++){
if(g[i] == g[i-1]) continue;
for(j = 1; j <= min(m - 1, n/i/i); j++){
if(i * j < m) f[j] -= f[i * j] - g[i - 1];
else f[j] -= g[n/i/j] - g[i-1];
}
for(j = m;j >= i * i; j--) g[j] -= g[j / i] - g[i - 1];
}
ll ans = 0;
for(int i = 2; i < m; i++){
if(g[i] == g[i - 1]) continue;
ans += f[i] - g[i];
}
return ans;
}
int main (void)
{
int t;
cin>>t;
init();
while(t--){
ll n;scanf("%lld", &n);
ll ans = 0;
for(int i = 0; i < tot; i++){
if(prime[i] * 1LL * prime[i] * prime[i] > n) break;
ans++;
}
printf("%lld\n", ans + solve(n));
}
return 0;
}
I – 格蕾亲真可爱
首先，标题很正确，很给力，但是和题目内容没关系。
这道题是一个披着外衣的 01 背包问题（动态规划）。（ACM中会有很多题目穿着各种奇怪的外衣，比如晕头的蚂蚁。）这道题目的难点显然在于，选的顺序不同，那么产生的影响也会不同（比如样例），因此对暴力算法造成了难度，思考起来也颇为复杂。但是，不管顺序怎么变，选定的宝石固定了，有一点是不变的，那就是会消耗多少宝石。
下面进入正文，拨开这个动态规划题的外衣。
先说结论：只要我们选取的 $k$ 个宝石所消耗的 $k+\sum B_i$颗宝石（本身和后面的宝石），不超过总数 $n$ ，那么一定可以找到一种方法来进行魔术。
利用这个结论，我们令 $W_i=B_i+1$（物品重量）， $V_i=A_i$（物品价值），就变成了一个 $n$ 个物品 $n$ 承重的 01 背包问题。（没学过动态规划和 01 背包的需要先进行学习）有了结论，学过 01 背包的谁都会做，那么怎么得到这个结论呢？
证明如下：
利用反证法：
首先我们假设不能找到一个宝石，使得利用它发动魔术的时候不会让其他被选中的宝石消失。
那么对任意一个被选中的宝石 $x$，找它后面的离它最近的另一个被选中的宝石 $y$（可以为 $x$ 本身，当只选一个宝石的时候），
$$\textrm{if}（y > x) \lbrace D=y-x\rbrace;\textrm{else}\lbrace D=n+x-y;\rbrace$$
( $D$ 表示 $x$ 到 $y$ 相距多少个宝石）
有式一: $latex D_x < B_x+1$;
对选中的 $k$ 个宝石，共有 $k$ 对这样的相邻的被选中的宝石（若 $k$ 为 $1$，则有其本身构成的一对宝石），能写出 $k$ 个式一，对写出的 $latex k$ 个式一，小于号左右两边分别累加得，
$\sum D_x < \sum (b_x+1)$,
化简得， $n < k + \sum b_i$,与条件矛盾。
所以，一定可以找到一个被选中的宝石，使得利用它发动魔术的时候不会让其他被选中的宝石消失。
之后，也一定可以找到第二个被选中的宝石，以此类推，最终可以实现。
笔者出题的本心是希望大家看到题目能多多思考，考察研究模型。不要直接考虑xxx能不能用。
以上。
最后，格蕾亲真可爱，格蕾亲真可爱，格蕾亲真可爱。嘿嘿嘿。
#include<iostream>
#include<stdio.h>
using namespace std;
long long w[1005],v[1005];
long long dp[1005][1005];
int main(){
long long i,j,n;
scanf("%lld",&n);
for(i=1;i<=n;i++)
{
scanf("%lld%lld",&v[i],&w[i]);
w[i]++;
}
for(i=1;i<=n;i++)
{
for(j=n;j>=0;j--)
{
if(j>=w[i])
{
dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);
}
else dp[i][j]=dp[i-1][j];
}
}
printf("%lld\n",dp[n][n]);
return 0;
}
Views: 437
