51nod 1055 最长等差数列

Type: 动态规划,双向DP,思维,技巧

题目

N个不同的正整数,找出由这些数组成的最长的等差数列。

例如:1 3 5 6 8 9 10 12 13 14
等差子数列包括(仅包括两项的不列举)
1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
6 8 10 12 14

其中6 8 10 12 14最长,长度为5。

Input

第1行:N,N为正整数的数量(3 <= N <= 10000)。
第2 – N+1行:N个正整数。(2<= A[i] <= 10^9)

Output

最长等差数列的长度。

Input示例

10
1
3
5
6
8
9
10
12
13
14

Output示例

5

题解

数据范围可判是O(N^2)
一开始我一直在想如何把数字,即两个数之间的差用哈希存起来,来方便dp.
然后搜了题解发现是论文题.
被叫做LLAP问题
Length of the Longest Arithmetic Progressio

论文Link:

https://www.geeksforgeeks.org/length-of-the-longest-arithmatic-progression-in-a-sorted-array/

论文解释

这道题可以转化为:

给与一个 排过序 的集合set,我们要求这个集合中的最长等差数列的长度.

标重点: 序列是已排好序的
我们设 dp[i][j] 为以下标 i 和 j 两个元素开头的等差序列最长长度.
我们可以创建一个浮标 j 作为等差数列的中间值

初始化一个 i=j-1,k=j+1.

1.如果 set[i]+set[k] < set[j]*2

k++

2.如果 set[i]+set[k] > set[j]*2

i–

如果 set[i]+set[k]=set[j]*2

则构成等差数列,我们只需要让

dp[i][j]=(dp[j][k]==0)?3:dp[j][k]+1

如果dp[j][k]=0的话,dp[i][j]直接=3就可以了,因为 i,j,k 三个刚好构成等差数列.否则等于 dp[j][k]+1

计算完以后 i–,k++ 继续计算其他以 j 为第二个点的等差数列

倒序计算,正序反过来即可

另外: 还可以 直接将 dp 数组初始化为 2(因为每个数的等差数列至少为2).
dp[i][j]=dp[j][k]+1

另外有一个小技巧: 如果int的取值范围不大,但是数组要开很大的时候,可以用 short int,比如这道题.

Code

#include<bits/stdc++.h>

using namespace std;

const int maxn=10000;

short int dp[maxn][maxn];
int Num[maxn],ans,N;

int main(){
    while(~scanf("%d",&N)){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<N;++i){
            scanf("%d",&Num[i]);
        }
        sort(Num,Num+N);
        ans=0;
        for(int j=N-2;j>=1;--j){
            int i=j-1,k=j+1;
            while(k<N&&i>=0){
                if(Num[i]+Num[k]>2*Num[j]){
                    --i;
                }else if(Num[i]+Num[k]<2*Num[j]){
                    ++k;
                }else{
                    dp[i][j]=(dp[j][k]==0)?3:dp[j][k]+1;
                    ans=max(ans,(int)dp[i][j]);
                    --i;++k;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

51NOD 1241 特殊的排序

Type:动态规划,思维,最长等差数列(简化)

题目

一个数组的元素为1至N的整数,现在要对这个数组进行排序,在排序时只能将元素放在数组的头部或尾部,问至少需要移动多少个数字,才能完成整个排序过程?
例如:
2 5 3 4 1 将1移到头部 =>
1 2 5 3 4 将5移到尾部 =>
1 2 3 4 5 这样就排好了,移动了2个元素。

给出一个1-N的排列,输出完成排序所需的最少移动次数。

Input

第1行:1个数N(2 <= N <= 50000)。
第2 – N + 1行:每行1个数,对应排列中的元素。

Output

输出1个数,对应所需的最少移动次数。

Input示例

5
2
5
3
4
1

Output示例

2

题解

一开始会想到和逆序数有关,排序就是减少逆序数,所以会想到其中非逆序序列中最长的那个不用变化.

然后可以容易地证明剩余的数只需要移动一次即可到达正确的位置上

比如 12346587
可以发现最长等差整数序列是 12345 而我们需要 12345678
第一次: 1234587 6
第二次: 1234586 7
第三次: 1234567 8
OK,往数列前面放的也一样

那么我们的问题就是如何求最长等差数列(等差为1)了,

因为等差为1,所以我们不难想到:
dp[i] 为数字 i 的最长等差数列.
遍历Num[]数组的时候计算 dp 即可
dp[i]=dp[i-1]+1

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+10;

int dp[maxn],N,Num[maxn],max_;

int main(){
    while(cin>>N){
        memset(dp,0,sizeof(dp));
        dp[0]=0;
        max_=1;
        for(int i=1;i<=N;++i){
            cin>>Num[i];
        }
        for(int i=1;i<=N;++i){
            dp[Num[i]]=dp[Num[i]-1]+1;
            max_=max(dp[Num[i]],max_);
            //cout<<i<<" "<<dp[Num[i]]<<endl;
        }
        cout<<N-max_<<endl;
    }
    return 0;
}

51nod 1040 最大公约数之和

Type:欧拉函数,gcd性质,思维

题目

给出一个n,求1-n这n个数,同n的最大公约数的和。比如:n = 6
1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6,加在一起 = 15

Input

1个数N(N <= 10^9)

Output

公约数之和

Input示例

6

Output示例

15

题解

N<=10^9,所以肯定无法暴力枚举
考虑我们要求 lambda(gcd(i,N) | i∈[1,N])

我们可以知道:
对于每个数N,他的约数范围在[1~N]之间,即我们可以将问题转化为(设约数为Ni,1~N中约数为Ni个数为Mi):

lambda(Ni*Mi)

假设我们已经得到了Ni,问题就在于我们如何求出Mi
设i为1~N中任意数:

(1) Mi=count(gcd(i,N)=Ni | i∈[1~N])
=count(gcd(i/Ni,N/Ni)=1 | i∈[1~N])

即我们只需要求出1~N中与N/Ni互素的数的个数即可

即 euler(N/Ni)

(2) Mi=euler(N/Ni)

ans=lambda(Ni*euler(N/Ni))

然后有一个小性质,即 i*i<=N时,我们枚举到sqrt(i)同时求出 N/i ,枚举完所有的 i 即枚举完所有 1~N 内 N 的约数.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL N;

LL euler(LL n){
    LL res=n,a=n;
    for(LL i=2;i*i<=a;++i){
        if(a%i==0){
            res=res/i*(i-1);
            while(a%i==0)a/=i;
        }
    }
    if(a>1)res=res/a*(a-1);
    return res;
}

int main(){
    while(~scanf("%lld",&N)){
        LL ans=0;
        for(LL i=1;i*i<=N;++i){
            if(N%i==0){
                ans+=(i*euler(N/i));
                if(i*i!=N){
                    ans+=((N/i)*euler(i));
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

UVa 11426

Link

https://vjudge.net/problem/UVA-11426

Type: 数论,欧拉函数,递推,思维

题意

输入正整数n,求gcd(1,2)+gcd(1,3)+gcd(2,3)+gcd(1,4)+…+gcd(n-1,n)

保证输出不超过long long

范围: n∈[1,4000000]

题解

首先我们应该清楚

4000000的数据,用暴力 – 对每个gcd求值相加复杂度是i*j*O(gcd) 你懂就行,这么大的复杂度肯定爆炸.

所以我们第一想法肯定是预处理.

我们设 f(n) 为 (1,n)+(2,n)+(3,n)+…+(n-1,n)
则 S(n)=f(1)+f(2)+…+f(n)

通过这个公式我们就可以递推出所有的 S(n)

S(n)=S(n-1)+f(n)

然后我们的问题就转化成了求f(n)

首先我们会自然地想到,与n互素的答案是1.即(k,n)的结果都是n的约数

我们可以按照这个约数来进行分类,

用 g(n,i)表示满足gcd(x,n)=i 且 x\<n 的正整数x的个数
则: f(n)=Sum(i*g(n,i) | i是n的约数,g(n,i)是1~n中gcd(k,n)=i的k的个数)

然后我们注意到:
-gcd(x,n)=i
-则gcd(x/i,n/i)=1
-即x/i与n/i互质

然后我们就可以将 g(n,i) 看做1~n中与 n/i 互质的数的个数,即

g(n,i) = phi(n/i)

然后我们预处理phi[maxn],预处理完以后处理f(n),这里如果用二重循环依然是接受不了的

所以我们沿用筛法的思想对f[maxn]数组进行预处理,遇到i 是 k 的约数时,直接f[k]+=(i*phi[n/i])

最后预处理S[maxn]即可

Code

/*
我们要求:
G=Sigma(i=1~N) Sigma(j=i+1~N) GCD(i,j)
N<=4000000,这样的范围二次循环+GCD肯定是不行的
所以我们考虑
f(n)=Sigma(i=1~n-1) gcd(i,n)
则
G(n)=Sigma(i=1~n) f(i)
=G(n-1)+f(n)
所以我们的问题转换为如何求f(n)

即k都是n的约数
可以按照约数进行分类,用g(n,i)表示满足 (x,n)=i且x<n的正整数x的个数
则 f(n)=sum(i\*g(n,i)|i是n的约数)

再重提: g(n,i)代表满足(x,n)=i,且x<n的正整数x的个数

我们知道,如果 (a,n)=k
则 (a/k,n/k)=1

所以我们可以理解为g(n,i)代表的是x/i与n/i互质的数的个数
即满足条件的x/i 有 phi(n/i)个
g(n,i)=phi(n/i)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=4000000+10;
LL phi[maxn];

LL f[maxn];

LL g[maxn];
void phi_table(){
    for(int i=2;i<maxn;++i) phi[i]=0;
    phi[1]=1;
    for(int i=2;i<maxn;++i){
        if(!phi[i]){
            for(int j=i;j<maxn;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
}

void init(){
    phi_table();
    memset(f,0,sizeof(f));
    for(int i=1;i<maxn;++i){
        for(int j=i*2;j<maxn;j+=i){
            f[j]+=(i*phi[j/i]);
        }
    }
    memset(g,0,sizeof(g));
    for(int i=1;i<maxn;++i) g[i]=g[i-1]+f[i];
}

int main(){
    init();
    int k;
    while(~scanf("%d",&k) && k){
        printf("%lld\n",g[k]);
    }
    return 0;
}

2017 杭电多校训练赛 补题

第一场

1003 Colorful Tree hdoj6035

题意: 给定一棵树,树上各点之间的距离定义为 两点路线上不同颜色的个数。求这课数上n*(n-1)/2(即所有)的路径长度之和。
题解: (来自网络)
** //思路**:Answer = 所有颜色种类 * 所有路径数量 – 每一种颜色有多少路径没有经过 .

一开始假设每条路径都经过了所有颜色,再把每种颜色没经过的路径数减去就行,这个应该很好理解。问题是怎么算没经过的路径数?操作是这样的,如果算颜色1没经过的路径数,我们先把图里所有颜色是1的节点遮起来(假设这个点不存在,图在这个点是断路),图就被分成了很多块,每块的值= 那一块里的顶点数*(那一块里的顶点数-1)/2
所有块的值加起来就是不经过颜色1的所有路径数。

到这里是不是还是很好理解,那么问题来了,怎么实现?…题解里说用虚树什么的…

用一个DFS即可,复杂度O(n)

用Size数组储存以每个节点为根节点的子树大小(即子树里节点的个数),Sum数组…很难解释,大概是表示以每种颜色为根节点的子树的大小和,但不是非常准确,如果以颜色2为根节点的子树里还含有颜色为2的节点,那只要算根节点这个颜色为2的子树大小即可,若在以这个颜色为2的点为根节点的子树之外还有颜色为2的点,那还要加上这个点的值…不知道能不能理解…解释不清楚,大概就这个意思…

以下图颜色2为例,代码里最后的for里(即以根第一个节点计算中)减去的(n-sum[2])*(n-sum[2]-1)/2的那部分减去的是下图橙色圈里的那块,dfs里减去pp那部分是下图里蓝色圈的那块。其他具体的按照自己的理解再思考思考。

#include<bits/stdc++.h>
#define maxn 200005
#define inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
//c[]数组是每个节点的颜色
int c[maxn],head[maxn],len,sum[maxn],size[maxn],vis[maxn];
LL d;
//边表
//邻接表
struct node{
    int v,next;
}p[maxn<<1];

void addedge(int u,int v){
    //有向边指向点的编号
    p[len].v=v;
    //每条边的下一条边是上一次纪录的边的号码
    p[len].next=head[u];
    //邻接表的方法
    //len为当前边的编号

    //只记录当前节点的最后一个边的位置
    head[u]=len++;
}
//对树进行dfs
void dfs(int x,int fa){
    //非这个点为根的所有该颜色的点
    LL pre=sum[c[x]];
    //size数组是当前节点的子节点总数目
    size[x]=1;
    int add=0;
    //通过邻接表对当前节点x进行dfs
    //等于0则退出
    for(int i=head[x];~i;i=p[i].next){
        //如果遇到反向边了,跳过,继续往其他边走
        if(p[i].v==fa)
            continue;
        dfs(p[i].v,x);
        size[x] += size[p[i].v];
        //计算当前节点子树所有和当前节点颜色不同的点的个数
        LL count = size[p[i].v] - sum[c[x]] + pre;
        pre = sum[c[x]];
        //当前子树的不同颜色点的个数
        add += count;
        //假设其他颜色都是白色,d即等于不同颜色所组成的边的总个数
        d += count*(count-1)>>1;
    }
    //计算以x为根节点子树的所有与x不同颜色的点的个数
    sum[c[x]] += add + 1;
}

int main(){
    int n,tcase=1;
    while(~scanf("%d",&n)){
        memset(head,-1,sizeof(head));
        memset(sum,0,sizeof(sum));
        memset(vis,0,sizeof(vis));
        d=len=0;
        LL number = 0;
        for(int i=1;i<=n;++i){
            scanf("%d",&c[i]);
            //记录颜色,颜色范围是[1,n]
            if(!vis[c[i]]){
                vis[c[i]]=1;
                number++;
            }
        }
        for(int i=1;i<n;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        dfs(1,0);
        //ans初始等于(颜色个数)*(所有边的个数)-d(d为每个颜色在每个子树上被减去的不会经过那个颜色的路径的个数)
        LL ans=(number*(n-1)*n>>1)-d;
        for(int i=1;i<=n;++i){
            //不存在的颜色不需要计算,把已存在的颜色计算一下
            if(vis[i]&&i!=c[1]){
                //在根节点中与颜色i不同的颜色的个数
                LL count=n-sum[i];
                //每个颜色的路径数=(n*(n-1)>>1)-(count*(count-1)>>1)
                //以根节点为中心减去不同于当前颜色的路径的个数
                //最终得到的ans即为 每个颜色路径个数 的和
                ans-=count*(count-1)>>1;
            }
        }
        printf("Case #%d: %lld\n",tcase++,ans);
    }
    return 0;
}

1006 Function hdoj6038

这道题似懂非懂的写了出来…
大体是寻找循环节.
我写的代码有点乱…
原式为: f[i]=b[f[a[i]]]
A:{1,0,2} B{0,1}
可组成f: 000 111 110 001
A:{2,0,1} b{0,2,3,1}
可组成f: 000 231 312 123
以i -> a[i] i -> b[i] 为图的边进行Tarjan.
用Tarjan判断a和b各自有几个环(强连通分量),并且记录下每个环的大小.
然后AC代码如下(以后思路清楚了再重新看看…):

//HDU 6038
#include<bits/stdc++.h>

using namespace std;
const int maxn=100000+100;
const int mod=1e9+7;
typedef long long int lli;
vector<int> G[maxn];
//lowlink[u] == 为u及其后代能追溯到的最早(最先被发现)的祖先节点v的pre[v]的值.
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;

int a[maxn],b[maxn];

stack<int> S;
map<int,int> A,B;

//邻接表存储图
void addAdge(int u,int v){
    G[u].push_back(v);
}

inline lli qp(lli aa,lli x){
    if(aa == 0) return 0;
    lli ans = 1;
    for(;x;x>>=1){
        if(x&1) ans = ans*aa % mod;
        aa = aa*aa % mod;
    }
    return ans % mod;
}

void dfs(int u,map<int,int>& T){
    pre[u]=lowlink[u]= ++dfs_clock;
    //边dfs将点入栈边Tarjan
    S.push(u);
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!pre[v]){
            dfs(v,T);
            //回溯时计算lowlink数组
            lowlink[u]=min(lowlink[u],lowlink[v]);
        }else if(!sccno[v]){
            //未回溯时计算low数组需要通过pre数组
            lowlink[u]=min(lowlink[u],pre[v]);
        }
    }
    if(lowlink[u]==pre[u]){
        scc_cnt++;
        int cnt=0;
        for(;;){
            int x=S.top();S.pop();
            sccno[x]=scc_cnt;
            cnt++;
            if(x==u)break;
        }
        T[cnt]++;
    }
}

void Tarjan(int n,map<int,int>& T){
    while(!S.empty()){
        S.pop();
    }
    dfs_clock=scc_cnt=0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i=0;i<n;++i){
        if(!pre[i]) dfs(i,T);
    }
}

int main(){
    int n,m,kase=0;
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<n;++i){
            scanf("%d",&a[i]);
        }
        for(int i=0;i<m;++i){
            scanf("%d",&b[i]);
        }
        //对aTarjan
        for(int i=0;i<n;++i){
            addAdge(i,a[i]);
        }
        Tarjan(n,A);
        for(int i=0;i<n;++i){
            G[i].clear();
        }
        //对bTarjan
        for(int i=0;i<m;++i){
            addAdge(i,b[i]);
        }
        Tarjan(m,B);
        for(int i=0;i<m;++i){
            G[i].clear();
        }

        long long ans=1;
        map<int,int>::iterator it1;
        map<int,int>::iterator it2;
        for(it1=A.begin();it1!=A.end();it1++){
            long long tmp=0;
            for(it2=B.begin();it2!=B.end();it2++){
                if(it1->first%it2->first==0){
                    tmp=tmp+it2->second*it2->first;
                }
                //printf("%d %d : %d %d\n",it1->first,it2->first,it1->second,it2->second);
            }
            ans=ans*qp(tmp,it1->second)%mod;
        }
        printf("Case #%d: %lld\n",++kase,ans);
        A.clear();
        B.clear();
    }
    return 0;
}

1008 Hints of sd0061 hdoj6040

第二场

第三场

第八届ACM省赛 Quadrat 找规律

原题连接: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/problemlist/cid/2164

B题

题意: 求数位为n位的所有数字(0~9..9(n个9))中,各个数位与其平方%10^n所得数的各个数位之差不超过d的数的个数.

注: 所有的数位之差是循环的,比如9和1差2.

首先打表(不过我认为这道题是数位dp,但我不会):

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;

const int num[5]={1,10,100,1000,10000};
int a[15][15];
void init(){
    memset(a, 0, sizeof(a));
    for(int i = 0; i <= 9; ++i){
        for(int j = 0; j <= 9; ++j){
            a[i][j] = abs(i-j);
            if(a[i][j] > 5) a[i][j] = 10 - a[i][j];
        }
    }
}

bool judge(int i,int digit,int d){
    int res=i*i;
    for(int j=1;j<=digit;++j){
        int b=i%10;
        int c=res%10;
        i/=10;res/=10;
        if(a[b][c]>d) return false;
    }
    return true;
}

int check(int nb,int d){
    int cnt=0;
    for(int i=0;i<num[nb];++i){
        if(judge(i,nb,d))
            cnt++;
    }
    return cnt;
}

int main(){
    init();
    for(int i=1;i<=4;++i){
        printf("%d:",i);
        for(int j=0;j<4;++j){
            printf(" %d",check(i,j));
        }
        printf("\n");
    }
    return 0;
}

发现dp[i][j]=dp[i-1][j]*(2*j+1)

Code:

#include<cstdio>
#include<algorithm>
using namespace std;

long long dp[19][4];

void init(){
    dp[1][0]=4;dp[1][1]=4;
    dp[1][2]=8;dp[1][3]=8;
    for(int i=2;i<=18;++i){
        for(int j=0;j<4;++j){
            dp[i][j]=dp[i-1][j]*(2*j+1);
        }
    }
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        int n,d;
        scanf("%d %d",&n,&d);
        printf("%lld\n",dp[n][d]);
    }
    return 0;
}

2017多校训练2 HDU 6047 Maximum Sequence

原题连接: :point_right:Maximum Sequence
题意: 给定一个长度为n的a数组和b数组,要求a[n+1]…a[2*n]的最大总和。 限制条件为ai≤max{aj-j│bk≤j<i}。
题解: 两种方法,一种是线段树,另一种是第一次记录maxv数组,记录每个i到maxindex(A)的最大值,然后动态更新.
github:
1.线段树法: :point_right:1003_Range_Tree.cpp
2.暴力动态更新法: :point_right:1003.cpp

///线段树法
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const int maxnode=2000050;

int b[maxnode],N;
int maxv[maxnode];

void build(int o,int l,int r){
    if(l==r){
        if(l>N) return;///预先分配2*N个结点
        scanf("%d",&maxv[o]);maxv[o]-=l;
        return;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}

int query(int o,int l,int r,int ll,int rr){
    if(l>=ll&&r<=rr) return maxv[o];
    int ma=-1,mid=(l+r)>>1;
    if(mid>=ll) ma=max(ma,query(o<<1,l,mid,ll,rr));
    if(rr>mid) ma=max(ma,query(o<<1|1,mid+1,r,ll,rr));
    return ma;
}

void update(int o,int l,int r,int p,int val){
    if(l==r){
        maxv[o]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)update(o<<1,l,mid,p,val);
    else update(o<<1|1,mid+1,r,p,val);
    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}

int main(){
    while(~scanf("%d",&N)&&N){
        build(1,1,2*N);
        for(int i=1;i<=N;++i) scanf("%d",&b[i]);
        sort(b+1,b+1+N);
        LL ans=0;
        for(int i=N+1;i<=2*N;++i){
            int k=query(1,1,2*N,b[i-N],i-1);
            update(1,1,2*N,i,k-i);
            ans=(ans+k)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

///HDU 6047 暴力动态更新法
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+50;
const int mod=1e9+7;
int N;
int a[maxn],b[maxn],maxa[maxn];

int main(){
    while(~scanf("%d",&N)&&N){
        for(int i=1;i<=N;++i){
            int aa;
            scanf("%d",&aa);
            a[i]=aa-i;
        }
        maxa[N]=a[N];
        for(int i=N-1;i>=1;--i) maxa[i]=max(maxa[i+1],a[i]);
        for(int i=1;i<=N;++i) scanf("%d",&b[i]);
        sort(b+1,b+1+N);
        long long ans=0;
        ans=(ans+maxa[b[1]])%mod;
        int t=maxa[b[1]]-N-1;
        for(int i=2;i<=N;++i){
            maxa[b[i]]=max(maxa[b[i]],t);
            ans=(ans+maxa[b[i]])%mod;
            t=max(t,maxa[b[i]]-N-1);
        }
        printf("%lld\n",ans%mod);
    }
    return 0;
}

LibreOJ 516

【Problem Link】

#516. 「LibreOJ β Round #2」DP 一般看规律

【题意】

输入n个数,m个替换规则,x换成y.输出每次替换后最近的两个相同的数相距多少.如果没有相同的,输出MAX_INT.

【题解】

每个数字只与他的前驱和后继产生贡献。构建n个set,每次将较小的暴力合并到大的上面,通过lower_bound来找到他的前驱和后继。懒得离散化可以用map来存set。

【Source Code】

github: #516 DP一般看规律.cpp


#include<bits/stdc++.h>
using namespace std;
int ans,n,m,num,x,y;
map<int,set<int> > mp;///数字->数字下标集映射

void insert_update(int q,int index){
    set<int> &r=mp[q];
    set<int>::iterator it=r.lower_bound(index);
    if(it!=r.end()) ans=min(ans,*it-index);///右边相邻第一个
    if(it!=r.begin()) it--,ans=min(ans,index-*it);///左边相邻第一个
    r.insert(index);
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        ans=2147483647;mp.clear();
        for(int i=0;i<n;++i){
            scanf("%d",&num);
            insert_update(num,i);
        }
        for(int i=0;i<m;++i){
            scanf("%d%d",&x,&y);
            if(x==y){printf("%d\n",ans);continue;}
            set &r=mp[x],&t=mp[y];
            if(r.size()>t.size())swap(r,t);
            for(set<int>::iterator si=r.begin();si!=r.end();si++)
                insert_update(y,*si);
            r.clear();
            printf("%d\n",ans);
        }
    }
    return 0;
}


LA 3882

【Link】

And Then There Was One

【题解】

假设问题是从n个人编号分别为0…n-1,取第k个,

则第k个人编号为k-1的淘汰,剩下的编号为 0,1,2,3…k-2,k,k+1,k+2…

此时因为从刚刚淘汰那个人的下一个开始数起,因此重新编号

把k号设置为0,则

k 0

k+1 1

0 n-k

1 n-k+1

假设已经求得了n-1个人情况下的最终胜利者保存在f[n-1]中,则毫无疑问,该胜利者还原到原来的真正编号即为 (f[n-1]+k)%n (因为第二轮重新编号的时候,相当于把每个人的编号都减了k,因此重新+k即可恢复到原来编号)。由此,我们可以想象,当最终只剩下一个人的时候,该人即为胜利者,此时重新编号,因为只有一个人,所以此时f[1]=0

这样f[2]=(f[1]+k)%2,这样就可以求出最终胜利者在2个人的时候的情况下的编号,由递推公式f[n]=(f[n-1]+k)%n,可递推到最初编号序列中该胜利者的编号。

因此用这个方法,只需一遍On的扫描,即可求出最终答案

不过该题要求编号从1开始,只要把f[n]+1即可,同时,该题指定了第一个要删除的人必须为编号为m的人,其实也不难,求出f[n]之后,把原本编号为0的位置移到跟m只相距k的位置即可实现第一次删除的编号为m。所以最终 ans=(f[n]+1+m-k);

当然因为m-k可能为负数,导致整个ans为负,这样其实最后+n即可解决。

【Code】

LA 3882.cpp

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10;
int f[maxn];
int main(){
    int n,k,m;
    while(scanf("%d%d%d",&n,&k,&m)==3 && n){
        ///最后一次变换只有一个点,所以最终点设为0
        ///每次去掉一个点以后重新编号,所以%i
        ///从底向上的方法
        f[1]=0;
        for(int i=2;i<=n;++i)f[i]=(f[i-1]+k)%i;
        ///因为是从0编号,而题目要求从1编号,所以+1
        ///因为从0开始,而题目要求从m开始删除第k个
        ///所以第一次删除的下标应该是f[n]-k=第一次的起始下标
        ///0-k+m+1=真正的起始坐标,因为第一次需要将m设为0,从m开始重新编号
        int ans=(m-k+1+f[n])%n;
        ///因为m-k+1可能小于0,所以m-k+1+f[n]也可能小于0
        if(ans<=0) ans+=n;
        printf("%d\n",ans);
    }
    return 0;
}

 

LA 3902

【Link】

Network

【题解】

可将网络看成一棵树,将初始的VOD看做该树的根.距离该根k的叶节点可以忽略不计.其余的叶子结点记录在nodes数组表内,nodes[i]代表深度为i的叶子结点表.covered代表该叶子结点是第i个叶子结点是否可以使用VOD.gr代表邻接表.

最优选择放置服务器的方法是选择距离主机最远(k)的那个服务器上安装VOD即可.

【Code】

LA 3902.cpp

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000+10;
vector<int> gr[maxn],nodes[maxn];
int n,s,k,fa[maxn];
bool covered[maxn];

///无根树转有根树,计算fa数组,根据深度把--叶子节点--插入nodes表中
///u当前节点下标,f,当前节点父节点下标,d深度.
void dfs(int u,int f,int d){
    fa[u]=f;
    int nc=gr[u].size();
    ///距离根节点k距离以内的叶子结点不用记录
    if(nc==1 && d>k) nodes[d].push_back(u);
    for(int i=0;i<nc;++i){
        int v=gr[u][i];
        if(v!=f)dfs(v,u,d+1);
    }
}

void dfs2(int u,int f,int d){
    covered[u]=true;
    int nc=gr[u].size();
    for(int i=0;i<nc;++i){
        int v=gr[u][i];
        if(v!=f&&d<k)dfs2(v,u,d+1);///只覆盖到新服务器不超过k的结点 ///v!=f => 如果从f访问到u,那么就不能再从u回访f.深搜嘛.一路莽到底.
    }
}

int solve(){
    int ans=0;
    memset(covered,0,sizeof(covered));
    for(int d=n-1;d>k;--d){
        for(int i=0;i<nodes[d].size();++i){
            int u=nodes[d][i];
            if(covered[u])continue;///不考虑已经覆盖的点

            int v=u;
            for(int j=0;j<k;++j)v=fa[v];///找到相邻k级祖先,不可能有-1,因为之前已经把离根k的节点忽略了
            dfs2(v,-1,0);///在结点v设置服务器,然后通过对该服务器深搜
                         ///找到所有的叶子结点
            ans++;
        }
    }
    return ans;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&s,&k);///节点数,初始VOD服务器的编号和k
        for(int i=1;i<=n;++i){gr[i].clear();nodes[i].clear();}
        for(int i=0;i<n-1;++i){
            int a,b;
            scanf("%d%d",&a,&b);
            gr[a].push_back(b);
            gr[b].push_back(a);
        }
        dfs(s,-1,0);
        printf("%d\n",solve());
    }
    return 0;
}