铺地毯

朴素方法：定义一个二维数组表示地面，对于每块地毯，将给定范围内的数组区域填充为该地毯的编号，最后输出a[x][y]的值即可。然而，考虑到数据范围，这种做法肯定会超时，且我们只关心(x,y)这个点，并不关心其他点，算法可以优化。

正确解法：首先将每块地毯的范围存入数组中，再输入需要求的地面点的坐标，随后从后往前枚举每块地毯，一旦发现有块地毯包含这个点，便输出该地毯的编号。如果枚举完了还没有找到，输出-1。

代码如下：

#include<cstdio>
int n,q,w;
int x[10010],y[10010],a[10010],b[10010];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d%d%d",&x[i],&y[i],&a[i],&b[i]);
scanf("%d%d",&q,&w);
for(int i=n;i>=1;i--)
{
if(q>=x[i]&&q<=x[i]+a[i]&&w>=y[i]&&w<=y[i]+b[i])
{
printf("%d",i);
return 0;
}
}
printf("-1");
return 0;
}

约瑟夫问题

数组解法：

按照题意去做，用visit记录下已经出队了的人，然后模拟，一个个的加就行了。

还要注意，一开始，加的数要赋值为0。还有visit数组要开始全部赋值为0。

代码如下：

#include<cstdio>
using namespace std;
int main()
{
int n,m,s=0;
scanf("%d%d",&n,&m);
bool visit[200]= {0};
for(int k=0; k<n; k++) //总共要出队n次
{
for(int i=0; i<m; i++)
{
s++;
if(s>n) s=1;    //类似取模，而因为序列是从1开始的，所以不取模，加判断；若visit过，则i--，使其继续循环
if(visit[s]) i--;
}
printf("%d ",s);
visit[s]=1;//输出，记录已出队
}
return 0;
}

链表解法：

数组解法虽然简单，但会浪费一些时间。本题可以用循环双链表模拟，出圈即为一个链表的删除操作。

定义next[]表示结点的后继，last表示结点的前驱，首先初始化两个数组。

再定义now表示当前是哪个人报数，num表示报数到了几，每次now=next[now]，num++，若num==m，则开始出圈，进行双链表的删除操作，同时将n--，当n减到0时退出循环。

代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
​
int main()
{
int next[110],last[110];
int n,m;
int now=1,num=1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
if(i!=n) next[i]=i+1;
else next[i]=1;
if(i!=1) last[i]=i-1;
else last[i]=n;
}
if(m==1)
{
for(int i=1;i<=n;i++) printf("%d ",i);
return 0;
}
while(n)
{
now=next[now]; num++;
if(num==m)
{
next[last[now]]=next[now];
last[next[now]]=last[now];
n--; num=1;
printf("%d ",now);
now=next[now];
}
}
return 0;
}

最大子段和

一个简单的动态规划问题，定义dp[i]，表示在1~i这段序列中，包含编号为i的数的最大子段和。

容易得到转移方程dp[i]=max(dp[i-1]+a[i],a[i])，如果加上其他的数得到的结果还没有单独自己一个数的好，自然不会和其它的数一起。

比如样例2 -4 3 -1 2 -4 3，dp数组为2 -2 3 2 4 0 3。再在dp数组中找出最大值，即为答案。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[200010],dp[200010],maxx=-2100000000;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) dp[i]=max(dp[i-1]+a[i],a[i]),maxx=max(dp[i],maxx);
printf("%d",maxx);
return 0;
}

N皇后问题

一个经典的递归问题，本身有一定难度，但是大多数同学都已经做过该题，希望借此机会让大家再次复习递归算法。

递归时我们的参数选择为行号，即在一次dfs中，我们要确定在这一行棋子放在哪一列。只要能避免冲突，就是一种可行的放法，我们要枚举到每一种放法；如果不管怎么放都有冲突，则回溯，将上一行的棋子挪动位置，再来尝试下一行放在哪一列。如果所有行都确定了位置，即行号到达n+1，这时候便可以输出答案并return。

为了确定放在某个位置是否可行，我们要考虑行不发生冲突，列不发生冲突，向左斜和向右斜的对角线不发生冲突。对于每一行我们依次枚举位置，必然不会冲突；对于每一列，可以用一个数组简单的标记；对于斜对角线，容易发现，对于一条从右上到左下的对角线，其上的棋子坐标应满足x+y为一定值；对于一条从左上到右下的对角线，其上的棋子坐标应满足x-y为一定值（为了避免负数的产生，代码中用x-y+20来储存），所以也可以用数组做标记。

其实递归算法的思想就是一个一个试，但要保证试的方法是可行的，如果明显产生了冲突，就没必要再往下试了。把每种情况都枚举到之后，便可以得到最终答案。对于这道题，主函数中调用dfs(1)，表示从第一行开始试，随意指定第一行放在哪一列之后再去试下一行，依次试完一遍便得到了最终答案。

需要注意，回溯时务必清除之前的标记。

代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,ans;
int f[20];//存储结果
bool l[110],zx[110],yx[110];//列左斜右斜
void dfs(int k)
{
if(k==n+1)
{
ans++;
if(ans<=3)
{
for(int i=1;i<=n;i++) printf("%d ",f[i]);
printf("\n");
}
return;
}
for(int i=1;i<=n;i++)
{
if(l[i]==0&&zx[i+k]==0&&yx[k+20-i]==0)
{
l[i]=1; zx[i+k]=1; yx[k+20-i]=1; f[k]=i;
dfs(k+1);
l[i]=0; zx[i+k]=0; yx[k+20-i]=0;
}
}
}
int main()
{
scanf("%d",&n);
dfs(1);
printf("%d\n",ans);
return 0;
}