小白月赛6-题解整理

A-典型的追击问题，较多的坑点，回游有很多种情况，注意分类

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main(){
  double l,k,a,b;
  cin>>l>>k>>a>>b;
  printf("%.2f\n",l/b-l/a);
  return 0;
}

View Code

B-水题，模拟就行

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int a[1000006];
int main(){
  int n;
  while(~scanf("%d",&n)){
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int flag=2;
    int cnt=0;
    for (int i=1;i<n;i++){
        if (flag==2){
            if (a[i]<a[i+1]){
                flag=1;
            }
            if (a[i]>a[i+1]){
                flag=3;
            }
            continue;
        }
        if( flag==1 &&a[i]>a[i+1]){
            flag=3;
            cnt++;
            continue;
        }
        if ( flag==3 && a[i]<a[i+1]){
            flag=1;
            continue;
        }
    }
    printf("%d\n",cnt);
  }
  return 0;
}

View Code

C-典型的树的直径问题-两遍DFS

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 1e9+7
using namespace std;
const int MAXN = 2000000;
const int MAXM = 2000000;
int n,m;
struct EDGE
{
    int v,next,w;
}edge[MAXN];
int head[MAXN],e;
int q[MAXN],vis[MAXN],d[MAXN];
void init()
{
    e=0;
    memset(head,-1,sizeof(head));
}
void add(int u,int v,int w)//链式前向星部分
{
    edge[e].v=v;
    edge[e].w=w;//权重
    edge[e].next=head[u];//下一条边
    head[u]=e++;//u为节点边的头节点
}
void bfs(int src)
{
    for(int i=1;i<=n;i++)vis[i]=0,d[i]=INF;
    int h=0,t=0;
    q[t++]=src;
    vis[src]=1;
    d[src]=0;
    while(h<t)
    {
        int u=q[h++];
        for (int i=head[u];i!=-1;i=edge[i].next)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (d[u]+w<d[v]){
                d[v]=d[u]+w;
                if (!vis[v])
                {
                    q[t++]=v;
                    vis[v]=1;
                }
            }
        }
    }
}
int main(){
 int u,v,w;
 char k;
 scanf("%d",&n);
 init();
 for(int i=1;i<=n-1;i++)
 {
     scanf("%d%d",&u,&v);
     add(u,v,1);
     add(v,u,1);
 }
 bfs(1);
 int pos=-1,mx=-1;
 for (int i=1;i<=n;i++)
    if (d[i]>mx)
 {
     mx=d[i];
     pos=i;
 }
 bfs(pos);
 mx=-1;
 for (int i=1;i<=n;i++)
    if (d[i]>mx)mx=d[i];
 printf("%d\n",mx+1);
 return 0;
}

View Code

D-水题

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
char a[1000006];
int pre[1000006];
int main(){
  int n,m;
  map<char,int> p;
  while(~scanf("%d%d",&n,&m)){
    p.clear();
    scanf("%s",a);
    int lena=strlen(a);
    for (int i=0;i<lena;i++){
       p[a[i]]++;
       pre[i+1]=p[a[i]];
    }
    int tmp;
    for (int i=1;i<=m;i++){
        scanf("%d",&tmp);
        printf("%d\n",pre[tmp]);
    }
  }
  return 0;
}

View Code

E-很好的简单搜索

#include<iostream>
#include<stdio.h>
#include<string.h>
#define rep(i,j,k) for(int i=j;i<=k;++i)
using namespace std;
int vis[1005][1005];
int dx[10]={0,0,1,-1,1,-1,1,-1};
int dy[10]={1,-1,0,0,1,-1,-1,1};
int n,m;
bool dfs(int x,int y,int z){
    vis[x][y]=z;
    int xx,yy;
    int cnt;
    for (int i=0;i<=7;i++){
        xx=x;
        yy=y;
        if(i%2==0)
        cnt=1;
        for (int j=0;j<=3;j++){
           xx=xx+dx[i];
           yy=yy+dy[i];
        //   cout<<xx<<" "<<yy<<" ";
           if (xx<1 || yy<1 || xx>n || yy>n || vis[xx][yy]!=z){
            break;
           }
           cnt++;
        }
        if (cnt>=5){
            return 1;
        }
    }
    return 0;
}
int main()
    {
 
        while(~scanf("%d %d",&n,&m))
        {
 memset(vis,-1,sizeof(vis));
        int id=-1,x,y;
        rep(i,1,m)
        {
            scanf("%d %d",&x,&y);
            if(id==-1)
            {
                if(dfs(x,y,i%2))
                    id=i;
            }
        }
         if(id==-1)
            printf("UNK %d\n",m);
        else if(id%2)
            printf("HtBest %d\n",id);
        else
            printf("WHZ %d\n",id);
        }
        return 0;
    }

View Code

F-树状数组，把维护区间和改为维护区间乘积就行

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dx[10]={1,-1,1,-1,0,0,-1,1};
int dy[10]={1,-1,0,0,-1,1,1,-1};
int vis[1004][1004];
int n,m;
bool dfs(int x,int y,int z){
   vis[x][y]=z;
   int xx,yy,cnt;
   for (int i=0;i<=7;i++){
      xx=x;
      yy=y;
      if (i%2==0){
        cnt=1;
      }
      for(int j=0;j<=3;j++){
         xx+=dx[i];
         yy+=dy[i];
         if (xx<1 || yy<1 || xx>n || yy>n || vis[xx][yy]!=z){
            break;
         }
         cnt++;
      }
      if (cnt>=5){
        return 1;
      }
   }
   return 0;
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
        int x,y;
        int flag=-1;
        memset(vis,-1,sizeof(vis));
        for (int i=1;i<=m;i++){
           scanf("%d%d",&x,&y);
           if (flag==-1){
              if (dfs(x,y,i%2)){
                  flag=i;
              }
           }
        }
        if (flag==-1){
            printf("UNK %d\n",m);
        }else if (flag%2==0){
            printf("WHZ %d\n",flag);
        }else if (flag%2==1){
            printf("HtBest %d\n",flag);
        }
    }
    return 0;
}

View Code

G-重载set内部排序就行

#include<bits/stdc++.h>
using namespace std;
int m,k;
struct cmp
{
    bool operator() (int a,int b)
    {
        if(abs(a-b)<=k) return false;
        return a<b;
    }
};
set<int,cmp>s;
int main()
{
    scanf("%d%d",&m,&k);
    int x;
    char op[8];
    while(m--)
    {
        scanf("%s%d",op,&x);
        if(op[0]=='a')
        {
            if(s.find(x)==s.end())
            {
                s.insert(x);
            }
        }
        else if(op[0]=='d')
        {
            s.erase(x);
        }
        else
        {
            if(s.find(x)!=s.end()) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

View Code

H-裸题最小生成树

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct node{
  int u,v,w;
}a[500006];
int p[100006];
int r[100006];
int n,m;
int find(int x){return p[x] == x ? x : p[x] = find(p[x]);}//不是根节点
int cmp(node x,node y)
{
    return x.w<y.w;
}
int Kruskal(){
        int ans=0;
        int num=0;
        for (int i=1; i<=n; i++)p[i]=i;
        sort(a+1,a+1+m,cmp);
        for (int i=1; i<=m; i++)
        {
            int x=find(a[i].u);//出发点的根节点
            int y=find(a[i].v);//到达点的根节点
            if (x!=y)//不是一个根节点
            {
                ans+=a[i].w;//连接
                p[x]=y;//y是x的父亲节点
                num++;//建立好了n-1条边
            }
            if (num==n-1){
                break;
            }
        }
    return ans;
}
int main()
{
    int tmp1,tmp2,tmp3;
    while(~scanf("%d%d",&n,&m))
    {
        for (int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
        }
        printf("%d\n",Kruskal());
    }
    return 0;
}

View Code

I-裸的最短路问题

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
int a[1005][1005];//邻接表点
ll d[1005];//到出发点距离
int vis[10005];//是否访问过
int n,m,s,t;
void Dijkstra(int st)
{
    int minn;//最小值
    int p;//边
    for (int i=1; i<=n; i++)d[i]=a[st][i];//初始化 每个点到出发点的距离
    vis[st]=1;
    d[st]=0;
    for (int i=1; i<=n-1; i++)
    {
        minn=INF;
        for (int j=1; j<=n; j++)
            if (!vis[j] && minn>d[j]) //如果未被访问过 并且到目前点的距离比min更小
            {
                p=j;//更新边
                minn=d[j];//更新新的距离
            }
            //循环下来 我们找到了最小的一条边
        vis[p]=1;//走过
        for (int j=1; j<=n; j++)
        {
            if (!vis[j] && d[p]+a[p][j]<d[j])
                d[j]=d[p]+a[p][j];
        }
    }
    if (d[t]!=INF)
        printf("%d\n",d[t]);
    else
        printf("-1\n");
}
  
int main()
{
    int tmp1,tmp2,tmp3;
    while (~scanf("%d%d%d%d",&n,&m,&s,&t))
    {
        memset(vis,0,sizeof(vis));
        memset(a,0x3f,sizeof(a));
        for (int i=0; i<m; i++)
        {
            scanf("%d%d%d",&tmp1,&tmp2,&tmp3);
            if (tmp3<a[tmp1][tmp2]){
            a[tmp1][tmp2]=tmp3;
            a[tmp2][tmp1]=tmp3;
            }
        }
        Dijkstra(s);
    }
    return 0;
}

View Code

J-一阶线性递推+逆元/矩阵快速幂

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#define ll long long
using namespace std;;
const ll mod = 1e9+7;
ll pow(ll a,ll b)
{
    ll ans = 1;
    while(b)
    {
        if (b&1)
        {
            ans = ans*a%mod;
        }
        a = a*a%mod;
        b/=2;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    ll n,k,p;
    ll ans=0;
    while(~scanf("%lld%lld%lld",&n,&k,&p))
    {
        if (k==1)
        {
             ans=(n*(n-1)%mod/2*p+n)%mod;
             printf("%lld\n",ans);
        }
        else
        {
            ll inv=pow(k-1,mod-2);
            ans=(1+p*inv%mod)%mod*((pow(k,n)-1+mod)%mod)%mod*inv%mod;
            ans=(ans-p*inv%mod*n%mod+mod)%mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}