A.Ian Visits Mary
算法本质
思维
题目大意
已知a b
从(0,0)最多跳2次到(a,b)点，要求每次跳跃的dx dy互质。
思路推演
1与所有数互质，只需要先填x轴再跳y轴就可以了。
B.Grid Reconstruction
算法本质
思维
题目大意
给定偶数n，在2*n的地图上，将1~2n的数字填入其中。当走到x+y为偶数的格子会使得成本加上当前格子的数字，反之减去。
现在小明要从左上角走到右下角，他会选择成本最小的路。
现在需要你构造这个地图，最大化小明的行走成本。
思路推演
已知有n个格子是增加成本的，有n个格子是减少成本的。自然用大数填充前面的，小数填充后面的。
另外起点和终点是必然经过的，其他点都是可能不经过的，所以起点终点需要填2n 2n-1。
接下来探讨中间格子填什么，当小明已知地图要求最少成本路径时，是用的dp来求。
而我们已经确定格子的数字大小，只能做调换的时候：让每个格子从上面2种可能状态转移过来的成本尽可能相近是显然的正解。
观察一下样例蕴含的规律。
C.Ian and Array Sorting
算法本质
思维
题目大意
给定长度n的数组a[]，你可以进行任意次以下操作，目标是使得a[]非递减排序，检查是否可能：
- 选择
a[i] a[i+1]都+1或者-1
思路推演
稍加模拟扩展，可以发现，对任意差距为偶数的元素，可以做到+1 -1，即元素值的转移。
这是一个很好的结论，这意味我们可以把元素分为奇数下标、偶数下标两组。这两组元素内部可以转移值，所以必然可以构造非递减。
那现在的情况就是，需要构造两组元素之间的非递减。
- 若元素个数为偶数
可行的结果显然是：偶数下标组和 >= 奇数下标组和 - 若元素个数为奇数
则奇数组多了一个元素，可操作性就大很多了。模拟一下，必然成立。
D.Sum Graph
算法本质
思维（交互题）
题目大意
存在一个长度n且未知的排列、一个有n个节点的空图，现在你可以进行至多2n次以下操作之一，最后需要猜测排列2次：
- 建图：输入
x，图中编号之和为x的节点连接一条边 - 查询：输入
i j，返回图中编号为p[i] p[j]的最短距离（无法抵达输出-1）
最后可以猜测排列2次，其中一次正确即为正解。
思路推演
先拿到这个题还是有点蒙。
仔细查看查询操作，其依赖于建立好的图，所以建立好图非常关键。
模拟一下建图，显然第一次操作的最有解为x=n+1，每个点都是平等的，这样可以多建边。
已当前图为例，我们可以用n-1次操作得到相连的2个点，显然信息不够的。最大的一个问题是，没有利用好距离，只利用了是否可达。
于是我们再次尝试，x=n，将所有图连接成一条线。
这次很好解决了问题，如果我们随机选择一点让其查询其他所有点，而且对于同一点来说：相同距离表示的点至多有2个点。
但是正是这不确定性，让我们没办法用剩下的n-1次查询搞定。
为了解决这种不确定性，查询点在线边缘即可解决，我们可以找到距离随机点最远的点，其一定是边缘点。
然后通过边缘点，查询其他所有点。
但是边缘点本身在左在右不确定后，对应了题目最后允许猜测2次。
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int a[maxn], ans1[maxn], ans2[maxn];
int dis[maxn];
inline void solve()
{
//init
int x;
cin>>n;
int l=1, r=n;
cout<<"+ "<<1+n<<endl; // 建图
cin>>x;
cout<<"+ "<<2+n<<endl;
cin>>x;
for (int i=1; i<=n; i++) // 记录建图之后的顺序、节点值
{
if (i%2)
a[i] = l++;
else
a[i] = r--;
}
for (int i=2; i<=n; i++) // 找个随机点p[1]，询问与其他点的距离
{
cout<<"? 1 "<<i<<endl;
cin>>dis[i];
}
int s=2; // s为边缘点
for (int i=2; i<=n; i++) // 距离最远的肯定是边缘点
if (dis[i] > dis[s])
s = i;
//cal
ans1[s] = a[1]; // 可能是左边缘
ans2[s] = a[n]; // 可能是右边缘
for (int i=1; i<=n; i++)
{
int w;
if (i==s) continue; // 自己和自己不需要询问
else
{
cout<<"? "<<s<<" "<<i<<endl; // 询问距离，通过距离推断
cin>>w;
}
ans1[i] = a[1+w];
ans2[i] = a[n-w];
}
cout<<"! "; // 猜测答案
for (int i=1; i<=n; i++)
cout<<ans1[i]<<" ";
for (int i=1; i<=n; i++)
cout<<ans2[i]<<" \n"[i==n];
cin>>x;
return;
}E.Between
算法本质
思维
题目大意
给定n m，有编号1~n的节点，需要你构造一个尽可能长的序列（可能是无限），满足以下条件：
- 序列的元素是某个节点
- 节点1只有一个
- 接下来会给出
m对i j，表示序列每两个i节点中至少存在一个j节点
若序列无限输出“无限”
否则输出序列
n <= 1.5e3思路推演-数目
稍加模拟发现这是一个需要用图来思考的题：i j其实是j-->i的边，点x的最大数目 == min( 所有指向x点节点的最大数目中 ) + 1
顺带可以发现，当某个点不受限制时，变存在无限长的情况。
结合题目性质，想当然认为这是topo排序。经过模拟，成环情况下，其实也并不影响节点数目的判断，类似于最短路，到节点1的最短路。
那么现在节点可行的最大数目都求得，接下来需要考虑怎么排序才能满足其中的“夹”条件。
思路推演-构造-1
首先肯定得优先用数目多的节点，然后接着用其指向的节点，大致思路是这样的。所以把边反向：即数目多的点 --> 数目少的点。
这样更好思考。
我们观察节点的连接情况，其指向的其他节点的数目，都是>=当前数目-1的。
其中数目少的节点x --> 数目多的节点y其实也可以看作y-->x。（相同数目也可行）
通过这个操作，重新改变节点边关系，可以保证无环。
然后可以用稍加改造的topo来搞定：
- 入度0的点入队
- 若队头的节点数目还有，输出一次，队头节点数目--
- 弹出队头节点，其指向节点入度--，若入度为0则入队
这样重复多次直到所有节点数目为0即可。
思路推演-构造-2（超越答案思路）
但是之前的做法有些麻烦，需要修改边，然后再度topo，继续思考：
- 对于当前
数目多节点 --> 数目少节点的情况，指向一个节点也是指，指向多个也是指（最坏情况就是全部指） - 让数目多节点 --> 所有数目比其少的节点
- 则可以省略修改边的过程，topo排列也变的简单无比
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
int num[maxn];
vector<int> g[maxn];
void cls()
{
for (int i=1; i<=n; i++)
g[i].clear(), num[i]=-1;
}
inline void solve()
{
//init
cin>>n>>m;
cls();
while (m--)
{
int u, v;
cin>>u>>v;
g[v].push_back(u);
}
//cal
num[1] = 1;
queue<int> q;
q.push(1);
int cnt=0; // 记录遍历的点数
while (q.size()) // 最短路bfs
{
int u=q.front(); q.pop();
cnt++;
for (int v:g[u])
{
if (num[v] == -1)
{
num[v] = num[u] + 1;
q.push(v);
}
}
}
if (cnt!=n) // 存在不走到1的节点
{
cout<<"INFINITE"<<endl;
return;
}
// 否则一定可行
int len=0;
for (int i=1; i<=n; i++)
len += num[i];
cout<<"FINITE"<<endl;
cout<<len<<endl;
vector<int> v; // topo排序输出
rep(i,1,n) v.push_back(i);
sort(v.begin(), v.end(), [](int a, int b){return num[a] > num[b];});
while (num[v[0]])
{
for (int u:v)
{
if (num[u]==0) break;
cout<<u<<" ";
num[u]--;
}
}
cout<<endl;
return;
}
评论 (0)