C Game Map
题意：
给你一个无向连通图，每个点具有点边数为k，问你最长的k下降道路有多长
思路：
用vector数组来存每个点的后继，用sum数组记录每个点的边数k
dp[i]数组表示从i开始的最长k下降的道路长度
写一个记忆化搜索即可
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 300000 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef long long ll ;
//不开longlong见祖宗！
//
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int n, m, x, y;
vector<int>tr[MAX];//存点的后继
int dp[MAX], sum[MAX];
int calc(int x){//记忆化搜索
if(dp[x] != 0){//如果有值就返回
return dp[x];
}
dp[x] = 1;//保底为自己，所以是1
for(int i = 0; i < tr[x].size(); ++i){//去搜每个点的后继
if(sum[x] > sum[tr[x][i]])
dp[x] = max(dp[x], calc(tr[x][i]) + 1);
}
return dp[x];
}
int main(){
io;
cin>>n>>m;
for(int i = 1; i <= m; ++i){
cin>>x>>y;
tr[x].push_back(y);
tr[y].push_back(x);
sum[x]++;
sum[y]++;
}
for(int i = 0; i < n; ++i)calc(i);
int maxn = -1;
for(int i = 0; i <= n; ++i){
maxn = max(maxn, dp[i]);
// cout<<dp[i]<<' ';
}
cout<<maxn<<endl;
return 0;
}
这其实也可以写个dp滴(^ O ^)
#Philosopher‘s Walk
传送门
题意：
给你n和m，问你n*n的矩形中，数字m的位置
思路：
递归？！
有点分块的意思其实o(︶︿︶)o
对一个大的正方形，分成上下左右的四个部分，你需要确定m在哪个块里面，然后对这个块再次进行分块，一直找到最后
写成递归的形式，递归的变量是此时的正方形边长n，和对于n*n的正方形我们需要找到的数m，对于每次找到了数m所在的小正方形，我们就可以进行下一次递归，递归的变量是要缩小的，所以再递归后面得把数据加回来，这样等return的时候就一步步加出答案
现在我们来确定递归的结束条件：
当n=2，也就是分块分到最后剩下一个正方形，此时我们就可以根据此时的m确定是四个小正方形的哪一个，有了小正方形的位置，我们就可以看图知道其x和y，就开始return了
再来确定递归的四种情况：
首先，我们观察图可以发现，数其实有一个大的方向，就是从（1，1，）->（1，2）->（2，2）->（2，1）数再变大，且分割点是与n*n对应的四等分点
情况一：
m <= n * n / 4，此时点大概在图形的左下角，我们就应该去dfs左下角，对于dfs的第一个变量n是原来的n / 2，第二个变量m有点不同¯ \ _ (ツ) _ / ¯，
我们看图说话
n每放大一倍，第一象限和第四象限就会逆时针旋转90度，所以我们得处理这个m，新的m = （别问，问就是看题解抄的公式(>_<)）
所以对于第一象限的我们需要
dfs(n / 2, n * n / 4 - m + 1);
到这里我们就进入了下层递归，在上面说了，我们改变了m的值，其对于的x和y的值也改变了，我们得改回来
这个图案是相当于原地旋转90度，由(x0,y0)变到(x0',y0')，这里先给出求旋转后的坐标的方法：
先互换x和y的坐标，新的坐标的x0' = y0, y0' = 边长 + 1 - x
现在给出证明：
我们对这个正方形进行原地旋转，我们设左上角的点为（x0， y0），则旋转后的为点（x0', y0')，看图我们可以发现，原来的y轴经由平移后就是新的x轴，也就是原来的纵坐标等于现在的横坐标。而现在的纵坐标加上原来的横坐标等于边长
所以x0' = y0, y0' = 变长 + 1 - x0
就可以写成这个样子：
dfs(n/2,n*n/4-m+1); swap(x,y); y=n/2+1-y;
情况二：
n * n / 4< m <= n * n / 2,也就是左上角的第二象限，看图可以发现，其形状没有变化，没有出现像第一种情况的旋转，我们就可以当作把他向下平移到左下角，此时m的变化就很简单了，直接减去第一象限的数即可，也就是直接dfs(n / 2, m - n * n / 4)，因为相当于向下平移，x值不变，y值减少了n / 2，所以得加回来
dfs(n/2,m-n*n/4);y+=n/2;
情况三：
n * n / 2 < m <= n * n * 3 / 4, 也就是右上角第三象限，同样的看图发现形状没有变化，同情况二
dfs(n/2,m-n*n/2);x+=n/2;y+=n/2;
情况四：
n * n * 3 / 4 < m <= n * n ,也就是右下角，看图可以发现，是将n / 2为边长的图形逆时针原地旋转90度，和情况一类似，不过这次是
dfs(n / 2, n * n - m + 1)
y0' = x0, x0' = 边长 + 1 - y0
dfs(n/2,n*n-m+1);swap(x,y);x=n/2+1-x;x+=n/2;
给出标程码：
#include <bits/stdc++.h>
using namespace std;
int x,y;
void dfs(int n,int m)
{
if (n==2)
{
if (m==1) x=y=1;
else if (m==2){ x=1;y=2;}
else if (m==3) {x=y=2;}
else {x=2;y=1;}
cout<<x<<' '<<y<<endl;
return;
}
if (m<=n*n/4){dfs(n/2,n*n/4-m+1);swap(x,y);y=n/2+1-y;cout<<x<<' '<<y<<endl;}
else if (m<=n*n/2) {dfs(n/2,m-n*n/4);y+=n/2; cout<<x<<' '<<y<<endl;}
else if (m<=n*n/4*3){ dfs(n/2,m-n*n/2);x+=n/2;y+=n/2;cout<<x<<' '<<y<<endl;}
else {dfs(n/2,n*n-m+1);swap(x,y);x=n/2+1-x;x+=n/2;cout<<x<<' '<<y<<endl;}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
dfs(n,m);
printf("%d %d\n",x,y);
return 0;
}
这题折磨了我一个晚上，脑子里全是递归，旋转，坐标(╥﹏╥)
I Slot Machines
传送门
题目描述：
题意：
给你n个数字，其中有
$$
k以后的数字是有周期p的
问你k + p的和最小时的k和p，如果k 和 p的和相同，就输出p最小的情况
思路：
我们分析一下就可以知道，他要求的是扔掉前k个数字后的最小循环子串的长度
那我们先来了解一下什么是最小循环子串，以及如何求得最小循环子串，戳这里o(≧v≦)o
看完了就会明白，串s的最小循环子串的长度为 len - next[len]，这里不具体证明
所以对于这个题，我们需要将数组倒序，从后往前求最长循环子串的p，同时计算出此时的k，然后找到符合题意的即可
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1500000 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
int n, m;
int tr[MAX], next1[MAX];
struct ran{//定义结构体，用来存每个p和k的值
ll p, k, sum;//sum表示p + k
}ar[MAX];
bool cmp(ran x, ran y){//写个结构体排序，用于找题意所求的
if(x.sum != y.sum)return x.sum < y.sum;
else return x.p < y.p;
}
void getnext(){//构造next数组
int j, k;
j = 0;k = -1;
next1[0] = -1;
while(j < m)
{
if(k == -1 || tr[j] == tr[k])
next1[++j] = ++k;
else
k = next1[k];
}
}
int main(){
cin>>n;
m = n;
for(int i = 0; i < n; ++i){
tr[i] = IntRead();
}
reverse(tr, tr + n);//反转容器
getnext();//构造
for(int i = 1; i <= n; ++i){
ar[n - i + 1].k = n - i;//从后往前算，所以是n - i
ar[n - i + 1].p = i - next1[i];//循环串的长度p
ar[n - i + 1].sum = n - next1[i];//算和
}
sort(ar + 1, ar + 1 + n, cmp);//排序
cout<<ar[1].k<<' '<<ar[1].p<<endl;
return 0;
} 
京公网安备 11010502036488号