第二题 扩充序列
题目地址
题意就是让[1]这个序列不断扩充,然后输出第k个字符
暴力求解的话,会导致MLE,递归的层数过多,如果先求出序列的话,也会超时
暴力
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n,k;
string dfs(int u)
{
if(u == 0)return "1";
else
{
auto c = dfs(u - 1);
return c + char(u + 1 + '0') + c;
}
}
int main()
{
cin >> n >> k;
string str = dfs(n - 1);
cout << str[k - 1] << endl;
return 0;
}
正解
通过画图的方式,判断出有三种情况;
当 k == 1LL << n - 1的时候,说明直接输出n即可
当 k < 1LL << n - 1的时候,说明这个答案肯定在上一层继续递归dfs(n - 1,k)即可
当 k > 1LL << n - 1的时候,说明答案在右边,可是由于是对称过来的,因此需要减去一个偏移量dfs(n - 1,k - (1LL << n - 1))
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
LL k;
LL dfs(int n,LL k)
{
if(k == 1LL << n - 1)return n;
if(k < 1LL << n - 1)return dfs(n - 1,k);
return dfs(n - 1,k - (1LL << n - 1));
}
int main()
{
cin >> n >> k;
cout << dfs(n,k) << endl;
return 0;
}
第三题 构造有向无环图
题意:判断当前这个图能否构造成有向无环图,图中的部分边是有向边,部分边是无向边
怎么判断能否构成呢?
如果当前的有向边已经构成了环的话,说明肯定无解
反之恒定有解,怎么判断是否是有无环呢?拓扑排序
之后只需要从小到大输出无向边里的点即可(必须要按照拓扑序的顺序来,因此需要记录拓扑序的下标位置,如果不在其中的话,说明
不管怎么添加都不会影响)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 200010, M = 200010;
int h[N],e[M],ne[M],idx;
int n,m,k;
int d[N],q[N],pos[N];
struct Edge{
int a,b;
}edge[N];
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
bool topsort()
{
int hh = 0,tt = -1;
for(int i = 1;i <= n; i ++)
if(!d[i])
q[++tt] = i;
while(hh <= tt)
{
auto t = q[hh++];
for(int i = h[t];~i;i = ne[i])
{
int j = e[i];
if(-- d[j] == 0)
q[++tt] = j;
}
}
return tt == n - 1;
}
int main()
{
int T;
scanf("%d",&T);
while(T --)
{
scanf("%d%d",&n,&m);
for(int i = 0;i < n + 1;i ++)h[i] = -1,d[i] = 0;
idx = k = 0;
while(m --)
{
int t,a,b;
scanf("%d%d%d",&t,&a,&b);
if(!t)edge[k ++] = {a,b};
else
{
add(a,b);
d[b] ++;
}
}
if(!topsort())puts("NO");
else
{
puts("YES");
for(int i = 1;i <= n;i ++)
for(int j = h[i]; ~j; j = ne[j])
printf("%d %d\n",i,e[j]);
for(int i = 0;i < n;i ++)pos[q[i]] = i;
for(int i = 0;i < k;i ++)
{
int a = edge[i].a, b = edge[i].b;
if(pos[a] > pos[b])swap(a,b);
printf("%d %d\n",a,b);
}
}
}
return 0;
}