暑假集训热身赛

 完成度 （8 / 10）

Problem A

题目大意

　　给定 m，n，询问二元组（x,y）( 1 <= x <= m , 1 <= y <= n) 满足 ( x + y ) % 5 = 0 的组数。

解题分析

　　直接枚举x与y的模余

参考程序

#include <cstdio>

int m,n;
int a[6],b[6];

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=5;i++) a[i]=(n-i+5) / 5 ;
    for (int i=1;i<=5;i++) b[i]=(m-i+5) / 5 ; 
 
    long long ans=0;
    for (int i=1;i<=4;i++) ans+=(long long)a[i]*b[5-i];
    ans+=(long long)a[5]*b[5];
    
    printf("%I64d",ans);
    return 0;
}

 

Problem B

题目大意

　　给定一个序列，可以任意减小某个元素，使得最小不出现的自然数最大。

解题分析

　　排序之后贪心扫一遍。

参考程序

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

#define maxn 100008
int a[maxn];
int n;

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    //for (int i=1;i<=n;i++) printf("%d ",a[i]);
    int ans=1;
    for (int i=1;i<=n;i++)
        if (a[i]>=ans) ans++;
    printf("%d\n",ans);
    return 0;

}

 

Problem C

题目大意

　　给一棵树,如果这个节点u与它的一个子节点v dist(u,v)>=a[u] 那么这个节点就是sad节点

　　每次操作可以去掉一个叶子节点，问最少去掉多少个节点才能使这棵树没有sad节点;

解题分析

　　dfs一遍，记录从根节点开始到该节点的最长路径，若大于某个节点，则去掉给节点及其子树。

参考程序

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 100008
#define maxm 200008

struct line
{
    int u,v,nt;
    long long w;
}eg[maxm];

int v[maxn],lt[maxn],son[maxn];
int n,sum=1,ans=0;

void add(int u,int v,int w)
{
    eg[++sum].u=u; eg[sum].v=v; eg[sum].w=w; 
    eg[sum].nt=lt[u]; lt[u]=sum;
}

void dfs(int u,int fa,long long dist)
{
    if (dist>v[u]) return;
    son[u]=1;
    for (int i=lt[u];i;i=eg[i].nt)
        if (eg[i].v!=fa)
        {
            dfs(eg[i].v,u,max(0LL,dist+eg[i].w));
            son[u]+=son[eg[i].v];
        }

}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&v[i]);

    int x,y;
    for (int i=2;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        add(i,x,y);
        add(x,i,y);
    }

    dfs(1,0,0);

    printf("%d\n",n-son[1]);
    return 0;
}

 

Problem D

题目大意

　　给定两个长度均小于等于1000的字符串S,T，在S串中找k个连续的子串，并且这些字串在T串中均出现且顺序相同，问这些字串最大的长度和。

解题分析

　　最长公共子序列的拓展。

　　令f[i,j] 表示S串第i位 T串第j位 往前最多几位相同

　　dp[i,j,k] 表示匹配到S串第i位 T串第j位 k个序列的最长匹配长度

　　那么dp[i,j,k]=max{ dp[i-f[i,j]][j-f[i,j]][k-1]+f[i,j],dp[i-1,j,k] , dp[i,j-1,k] }

参考程序

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

#define maxn 1008
#define maxk 15

char s[maxn],t[maxn];
int f[maxn][maxn],dp[maxn][maxn][maxk];

int n,m,len;
int max(int a,int b,int c){
    if (a>=b && a>=c) return a;
    if (b>=a && b>=c) return b;
    if (c>=a && c>=b) return c;
}
int main(){
    scanf("%d%d%d",&m,&n,&len);
    scanf("%s",s+1);
    scanf("%s",t+1);

    for (int i = 1;i <= m;i++)
        for (int j = 1;j <= n;j++)
            if (s[i] == t[j]) 
                f[i][j] = f[i - 1][j -1 ] + 1;
            else f[i][j] = 0;

    for (int k = 1;k <= len;k++)
        for (int i = 1;i <= m;i++)
            for (int j = 1;j <= n ; j ++)
                dp[i][j][k] =max(dp[i - f[i][j]][j - f[i][j]][k - 1] + f[i][j] , dp[i - 1][j][k] , dp[i][j - 1][k]);
                
    printf("%d\n",dp[m][n][len]);

}

 

Problem E

题目大意

题目分析

参考程序

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

int n;
char s[20];
int x[]={4,1,1,1,2,2,2,3,3,3};
int y[]={2,1,2,3,1,2,3,1,2,3};
int ok[20][20];
bool pd;

int main()
{
    memset(ok,0,sizeof(ok));
    for (int i=0;i<=9;i++)
        ok[x[i]+5][y[i]+5]=1;

    scanf("%d%s",&n,s+1);

    pd=false;
    int i,j;
    for (i=0;i<=9;i++) if (i!=s[1]-'0')
    {
        int tx=x[i];
        int ty=y[i];
        for (j=2;j<=n;j++)
        {    
            tx+=x[s[j]-'0']-x[s[j-1]-'0'];
            ty+=y[s[j]-'0']-y[s[j-1]-'0'];
            if (!ok[tx+5][ty+5]) break;
        }
        if (j==n+1) pd=true;
    }
    if (pd==true) printf("NO"); else printf("YES");

}

 

Problem F

题目大意

题目分析

参考程序

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

#define maxn 200008
#define INF 1000000000;
 
int n;
int dist[maxn],pd[maxn];


struct line{
    int u,v,w,nt;
}eg[maxn*4];
int lt[maxn],sum = 1;
void adt(int u,int v,int w){
    eg[++sum].u = u; eg[sum].v = v; eg[sum].w = w; eg[sum].nt = lt[u]; lt[u] = sum;
}
void add(int u,int v,int w){
    adt(u,v,w);
    adt(v,u,w);
}

void spfa(){
    memset(pd,0,sizeof(pd));
    for (int i = 1;i <= n;i++) dist[i]=INF;
    queue<int> Q;
    dist[1] = 0; Q.push(1); pd[1] = 1;
    while (!Q.empty()){
        int u = Q.front();
        for (int i = lt[u];i;i = eg[i].nt){
            int v = eg[i].v;
            if (dist[u] + eg[i].w < dist[v]){
                dist[v] = dist[u] + eg[i].w;
                if (!pd[v]){
                    Q.push(v);
                    pd[v] = 1;
                }
            }
        }
        Q.pop();
        pd[u]=0;
    }
    for (int i=1;i<=n;i++) printf("%d ",dist[i]);
    printf("\n");
}

int main(){
    memset(lt,0,sizeof(lt));
    scanf("%d",&n);
    for (int i = 1;i <= n;i++){
        int j;
        scanf("%d",&j);
        if (i != n) add(i,i+1,1);
        adt(i,j,1);
    }
    spfa();
}

 

Problem G

题目大意

题目分析

参考程序

#include <cstdio>

long long m;

long long check(long long x){
    long long sum=0;
    for (long long i = 2;i * i * i <= x;i++)
        sum += x / (i * i * i);    
    return sum;
}

int main(){
    scanf("%I64d",&m);
    long long l = 1,r = 1e16,mid,res = -1;
    while (l <= r){
        mid = (l + r) /2;
        if (check(mid) >= m){
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1; 
    }
    if (check(res) == m) printf("%I64d\n",res); else printf("-1");
}

 

Problem H

题目大意

题目分析

参考程序

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

#define maxn 200008
#define len 20
int n;
int a[maxn],b[maxn];
int fa[maxn][len],fb[maxn][len];

void rmq_inita(){
    for (int i = 1; i <= n;i++)
        fa[i][0] = a[i];
    for (int j = 1; (1 << j) <= n;j++)
        for (int i = 1;i + (1 << j) - 1 <= n;i++)
            fa[i][j] = max(fa[i][j - 1] , fa[i + (1 << j - 1)][j - 1]);
}

int rmqa(int l,int r){
    int k = 0;
    while (1 << (k+1) <= r - l + 1) k++;
    return max(fa[l][k] , fa[r - (1 << k) + 1][k]);
}


void rmq_initb(){
    for (int i = 1; i <= n;i++)
        fb[i][0] = b[i];
    for (int j = 1; (1 << j) <= n;j++)
        for (int i = 1;i + (1 << j) - 1 <= n;i++)
            fb[i][j] = min(fb[i][j - 1] , fb[i + (1 << j - 1)][j - 1]);
}

int rmqb(int l,int r){
    int k = 0;
    while (1 << (k+1) <= r - l + 1) k++;
    return min(fb[l][k] , fb[r - (1 << k) + 1][k]);
}

int main(){
    scanf("%d",&n);
    for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
    for (int i = 1;i <= n;i++) scanf("%d",&b[i]);
    rmq_inita();
    rmq_initb();
    int L;
    long long ans=0;
    for (L = 1;L <= n;L++){
        int l,r,mid,res1=0,res2=0;
        l = L; r = n ;
        while (l <= r){
            mid = (l + r) / 2;
            if (rmqb(L,mid) - rmqa(L,mid) >= 0){
                res1 = mid;
                l = mid + 1;
            } 
            else     
                r = mid - 1;
        }

        l = L; r = n ;
        while (l <= r){
            mid = (l + r) / 2;
            if (rmqa(L,mid) - rmqb(L,mid) >= 0){
                res2 = mid;
                r = mid - 1;
            } 
            else     
                l = mid + 1;
        }
        if (rmqa(L,res1) == rmqb(L,res1) && rmqa(L,res2) == rmqb(L,res2) )ans += res1 - res2 +1;
    }
    printf("%I64d\n",ans);
    return 0;
}

 

Problem I

题目大意

题目分析

参考程序

 

Problem J

题目大意

题目分析

参考程序