6月24日 Lydsy1806月赛
题目链接:https://www.lydsy.com/JudgeOnline/contest.php?cid=1014

A – 字符串大师II

思路:
其实没有什么思路的。border数组就是是KMP中的next,然后就打表找一下规律,就发现了结论:$ans=p-2^{log2(k)}$。

但是要注意一点,当k很大时$log2(k)$会被卡精度。开一个数组sec记录$log2(k)$为多少就好了。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define LL long long
using namespace std;

LL t, k, p, sec[100], temp;

int main()
{
    scanf("%lld", &t);
    sec[0]=1;
    for(int i=1; i<=60; i++) sec[i]=sec[i-1]*2;
    for(int i=1; i<=t; i++)
    {
        scanf("%lld%lld", &k, &p);
        for(int j=1; j<=60; j++)
        {
            if(p>=sec[j-1] && p<sec[j])
            {
                temp=j-1;
                break;
            }
        }
        printf("%lld\n", p-((LL)1<<temp));
    }
}

B – 超速摄像头

思路:
由于道路是树的结构,所以越外层节点数越多,因此我们尽量选外层的节点装摄像头。

然后直接模拟,所有入度为1的节点为最外层,然后删掉最外层节点并k-2。重复此操作直到k<=2,如果最后k=1时,则再可以给任意一个节点装摄像头。最后统计一下答案就好了。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#define LL long long
#define rint register int
#define MAXN 1000005
using namespace std;

int n, k, ans, cnt, top1, top2, head[MAXN], deg[MAXN], sta[MAXN], temp[MAXN];
bool vis[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    deg[to]++;
    head[from]=cnt;
}

int main()
{
    int x, y;
    scanf("%d%d", &n, &k);
    if(k==1) {printf("1\n"); return 0;}
    for(int i=1; i<n; i++)
    {
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    for(int i=1; i<=n; i++) if(deg[i]==1) sta[++top1]=i, vis[i]=1;
    k-=2;
    while(k>=2 && top1>0)
    {
        for(int j=1; j<=top1; j++)
        {
            int x=sta[j];
            for(int i=head[x]; i; i=edge[i].next)
            {
                int to=edge[i].to;
                if(vis[to]) continue;
                deg[to]--;
                if(deg[to]==1) temp[++top2]=to;
            }
        }
        top1=top2;
        for(int i=1; i<=top2; i++) sta[i]=temp[i], vis[temp[i]]=1;
        k-=2; top2=0;
    }
    for(int i=1; i<=n; i++)
    {
        if(vis[i]) ans++;
        else if(k>0) k--, ans++;
    }
    printf("%d\n", ans);
}

C – 质数拆分

思路:
比较暴力的枚举吧。设f[i]为两个质数和为i的方案数,通过枚举计算出f数组。答案就是i从1到n $f[i]*f[n-i]$的和

代码:

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

int n, tot, prime[150005], f[150005], check[150005];
long long ans;

int main()
{
    scanf("%d", &n);
    for(int i=2; i<=n; i++)
    {
        if(!check[i]) prime[++tot]=i;
        for(int j=1; j<=tot && i*prime[j]<=n; j++)
        {
            check[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
    for(int i=1; i<=tot && prime[i]*2<=n; i++)
    {
        f[prime[i]*2]++;
        for(int j=i+1; j<=tot && prime[i]+prime[j]<=n; j++) f[prime[i]+prime[j]]+=2;
    }
    for(int i=1; i<=n/2; ++i) ans+=f[i]*f[n-i]*2;
    if(n%2==0) ans-=f[n/2]*f[n/2];
    printf("%lld\n", ans);
}

E – 比例查询

思路:
特别好的一道题。对于这种序列问题,不能够区间合并,离线可能是一种做法。这道题的离线思想和BZOJ1878 HH的项链有点像。

设f[i]为数i最近的位置,g[i]为比例为i的两个数最近的位置。先将询问的右端点排序,然后从左向右扫。每扫到一个数找它的约数,用这个来跟新f[i],g[i],如果有询问的右端点在扫到的位置上,就根据g[i]回答询问。

但要注意,我们从左到右扫是是默认了右边的数为左边的数的b倍,因此我们需要再从右向左扫一遍。

代码:

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

int n, m, a[MAXN], f[MAXN], g[MAXN], ans[MAXN];

struct Q {int l, r, b, pos;} q[MAXN];

bool CMP(Q x, Q y) {return x.r<y.r;}

void solve()
{
    sort(q+1, q+m+1, CMP);
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    for(int i=1, j=1; i<=n; i++)
    {
        for(int k=1; k*k<=a[i]; k++)
        {
            if(a[i]%k) continue;
            g[k]=max(g[k], f[a[i]/k]);
            g[a[i]/k]=max(g[a[i]/k], f[k]);
        }
        f[a[i]]=i;
        for(; q[j].r==i; j++) if(g[q[j].b]>=q[j].l) ans[q[j].pos]=1;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)  scanf("%d", &a[i]);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].b);
        q[i].pos=i;
    }
    solve();
    reverse(a+1, a+n+1);
    for(int i=1; i<=m; i++)
    {
        q[i].l=n-q[i].l+1;
        q[i].r=n-q[i].r+1;
        swap(q[i].l, q[i].r);
    }
    solve();
    for(int i=1; i<=m; i++)
    {
        if(ans[i]) printf("Yes\n");
        else printf("No\n");
    }
}

G – 最长公共子序列

思路:
一道结论题,当T全为一个字母时是最优的,因此答案就是出现次数最少的字母的出现数。(凭感觉吧,不太会证明

代码:

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

int num[30], ans=1e9, len;
char s[1000005];

int main()
{
    scanf("%s", s);
    len=strlen(s);
    for(int i=0; i<len; i++) num[s[i]-'a']++;
    for(int i=0; i<26; i++) ans=min(ans, num[i]);
    printf("%d\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注