1.栅栏密码
题目传送门
题目大意：
给定高度 h 和一行使用栅栏密码加密的密文字符串 s，请你输出一行明文字符串 plain。
即把明文排列成若干个\/\/\/的形状，然后再逐行按从左到右的顺序取出字符，形成密文。
STEP 1.
直观一点，用数字来表示一下：
1###5###9
#2#4#6#8#10
##3###7###11
即可排列出 1 5 9 2 4 6 8 10 3 7 11.
进而发现：
\(1^{+3\curvearrowright}5^{+3\curvearrowright}9\)
\(2^{+2\curvearrowright}4^{+2\curvearrowright}6^{+2\curvearrowright}8^{+2\curvearrowright}10\)
\(3^{+3\curvearrowright}7^{+3\curvearrowright}11\)
再看一组：
1#####7#####13
#2###6#8###12
##3#5###9#11
###4#####10
即可排列出 1 7 13 2 6 8 12 3 5 9 11 4 10.
进而发现：
\(1^{+6\curvearrowright}7^{+6\curvearrowright}13\)
\(2^{+4\curvearrowright}6^{+2\curvearrowright}8^{+4\curvearrowright}12\)
\(3^{+2\curvearrowright}5^{+3\curvearrowright}9^{+2\curvearrowright}11\)
\(4^{+6\curvearrowright}10\)
STEP 2.
可以发现，当 \(h\) 为 \(3\) 时，一共分成了 \(3\) 行，打乱前的\(1\)、\(5\)、\(9\)分别变成了打乱后的第\(1\)、\(2\)、\(3\)个数，相邻两个数之间相差 \(2\space·(h−1)\)，第 \(h\) 行同理。
观察第 \(2\) 行发现，首行和尾行的间隔不变，若行数为 \(i\)，当前数为第 \(2\) 行的第奇数个数的时候，下一个数字下标就多 \(2\space·(h−i)\)，若当前数为第 \(2\) 行的第偶数个数的时候，下一个数字下标就多 \(2\space·(i−1)\)。而且每一行的第一个数字就是这一行的行数。
具体来说，
\( next(x)=\begin{cases} x+2\space·(h-i)\qquad i\%2=1\\ x+2\space·(i-1)\qquad i\%2=0 \end{cases} \)
STEP 3.
根据此思路，我们可以写出代码：
代码（凭良心复制）
#include<bits/stdc++.h>
using namespace std;
string s;
char ans[100080];
int hang=0;
int h,n,x,y;
int main(){cin>>h>>s;n=s.size();s=" "+s;hang=x=y=1;for(int i=1;i<=n;i++){ ans[x]=s[i];if(hang==1||hang==h)x+=(h-1)*2;//在两端else{if(y%2==1)x+=(h-hang)*2; //在奇数列else x+=2*(hang-1); //在偶数列}y++;if(x>n){//超出了x=++hang;//换行y=1;}}for(int i=1;i<=n;i++)cout<<ans[i];return 0;
}2.旅行计划
题目传送门
题目大意：
给定一个有向图，求得以第 i 个节点为终点的最长路径
STEP 1.
看到以第 i 个节点为终点就可以想到需要反向存边，这样终点就变为起点了.
由于只能向一个方向走，所以就为有向图。
STEP 2.
挺简单的，写个 DFS 就可以了
根据此思路，我们可以写出代码：
代码（凭良心复制）
#include<bits/stdc++.h>
using namespace std;
int dis[100005],n,m,x,y;
vector<int> mp[100005];
int dfs(int n){if(dis[n]!=0)return dis[n];dis[n]=1;for(auto it:mp[n]){dis[n]=max(dis[n],dfs(it)+1);}return dis[n];
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y;mp[y].push_back(x);//反着存}for(int i=1;i<=n;i++){dfs(i);}for(int i=1;i<=n;i++){cout<<dis[i]<<'\n';}return 0;
}
2.商务旅行
题目传送门
题目大意：
STEP 1.
STEP 2.
代码（凭良心复制）