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;
}