How to AK ABC240

__vector__ · 2022-02-26 19:02:04 · 个人记录

A - Edge Checker

题目大意：

1 到 10 按顺序组成一个环（1 和 10 首尾连接）
给定两个数，问是否相邻。

题目分析：

签到题不需要分析。

\color{green}\text{AC代码：}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if((a==1&&b==10)||(a==10&&b==1))
    {
        cout<<"Yes";
        return 0;
    }
    if(abs(a-b)<=1)cout<<"Yes";
    else cout<<"No";
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

B - Count Distinct Integers

题目大意：

给定一个长度为 n 的数组，问有多少不同的数字。

题目分析：

签到题不需要分析。

\color{green}\text{AC代码：}

#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
int a[maxn];
map<int,int> im;
int main()
{
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(!im[a[i]])ans++;
        im[a[i]]=1;
    }
    cout<<ans;
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

C - Jumping Takahashi

题目大意：

某人的起始坐标为0（向左为负向右为正）。给定两个长度为 N 的数组，a 和 b，这个人第 i 次跳可以向右移动 ai 个单位或 bi 个单位。问经过 n 次跳跃之后是否能到达点 X（必须跳 N 次）。

1 \le N \le 100

题目分析：

由于本人太菜，只会 O(2^n) 的爆搜，所以就来说一下怎么写爆搜过题，正确算法等我看了官方题解之后再放上来。
首先，朴素的爆搜肯定大家都会写，但是 O(2^n) 的复杂度就算评测机能 n^2 过百万也不行。所以要加剪枝，现在来讲一下怎么写剪枝。
剪枝一：如果当前搜到的数总和超过了 X ,那么返回。
剪枝二：如果当前搜到的数字总和，后面即使每次都选最大的数，总和仍然比 X 小，那么返回。
剪枝三：如果当前搜到的数字总和，后面即使每次都选最小的数，总和仍然比 X 大，那么返回。来看一看效果：

可见剪枝效果显著，但是仍然无法通过此题。
怎么办？
为了 AC，我加了一个错误的剪枝：
如果递归超过 2000万次还没有搜到结果，那么有解的可能很小（随机数据下），那么直接输出 No。
但是这个是错的，我自己就能 hack 掉。但是 At 的数据太水了所以过了。
正确做法我看完官方题解再放上来。
~~（还好不是 CF 赛制）~~

\color{red}\text{错误} \color{blue}\text{但是}\color{green}\text{AC的代码：}

#include <bits/stdc++.h>
using namespace std;
const int maxn=105;
int a[maxn];
int b[maxn];
int qzh[maxn];
int qzh2[maxn];
int n,x;
int cnt=0;
bool dfs(int i,int col)
{
    if(++cnt>=20000000)return 0;
 //   cout<<"i: "<<i<<" col"<<col<<endl;
    if(col==x&&i==n+1)return 1;
    if(i==n+1)return 0;
    if(col>x)return 0;
//    cout<<"qzh"<< qzh[n]-qzh[i]<<endl;
//    cout<<"qzh"<< qzh2[n]-qzh2[i]<<endl;
//cout<<col+(qzh[n]-qzh[i])<<endl;
//cout<<col+(qzh2[n]-qzh2[i])<<endl;
    if(col+(qzh[n]-qzh[i])>x)return 0;
    if(col+(qzh2[n]-qzh2[i])<x)return 0;
 //   cout<<"i: "<<i<<endl;
    if(dfs(i+1,col+a[i+1]))return 1;
    if(dfs(i+1,col+b[i+1]))return 1;
    return 0;
}

int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        qzh[i]=qzh[i-1]+min(a[i],b[i]);
        qzh2[i]=qzh2[i-1]+max(a[i],b[i]);
    }
    if(dfs(1,a[1])||dfs(1,b[1]))cout<<"Yes";
    else cout<<"No";
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

D - Strange Balls

题目大意：

有 n 个球，每个球都有一个数值 a_i。
这些球按照顺序从第 1 个到第 n 个依次放入一个瓶子里。放入一个球后如果出现了有连续 a_i 个球的数值为 a_i。那么这连续 a_i 个球都会消失。
问每放入一个球之后瓶子里有多少球。

题目分析：

可以创建一个栈 sta，对于每一块连续的球都用一个节点 sta_i 表示。对于每个节点 sta_i 存储当前块有多少个球，以及当前块存的球的数值。
插入一个球之后，如果这个球数值与栈顶节点不一样，那么新建一个节点插入栈顶。如果一样，那么栈顶节点 sta_{top} 存储的球数 +1，如果发现 sta_{top} 存储的球数 = sta_{top}的数值，那么删除 sta_top 即可。

\color{green}\text{AC代码：}

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n;
int a[maxn];
int top;
struct Sta
{
    int size;
    int val;
}sta[maxn];
int ans=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=sta[top].val)
        {
            sta[++top]={1,a[i]};
            ans++;
            printf("%d\n",ans);
        }
        else
        {
            sta[top].size++;
            ans++;
            if(sta[top].size==a[i])
            {
                ans-=sta[top].size;
                top--;
            }
            printf("%d\n",ans);
        }
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

E - Ranges on Tree

题目大意：

[l,r] = l,l+1,l+2.......r-1,r

给定一棵树。树上的每个点都有两个值 (l_i,r_i)。
设第 i 个节点的子树为集合 s_i。
每个点的值应满足一下要求：
一、如果点 a 是点 b 的子节点，那么 [l_a,r_a] 应包含在 [l_b,r_b] 中。
二、如果点 a 和点 b 是独立的两棵树，那么 [l_a,r_a] 应和 [l_b,r_b] 无交集。
对每个节点安排它的 (l,r)，使得 max(l_1,l_2,l_3......l_n,r_1,r_2,r_3......r_n) 最小。

题目分析

大力 dfs!
首先确定叶子节点的值，然后，每个节点的 father 节点的值也就是 (min({{s_i}_j}.l),max({{s_i}_j}.r))
注： {{s_i}_j} 代表 s_i 的第 j 个元素。
如何确定叶子结点的值呢？定义一个变量 sum ，当前点每搜到一个子节点点就 sum++。（为了避免误差，每个点搜到第一个子节点时不用增加 sum）
对于搜到的每个点首先把这个点的 l 设为 sum，从这个点搜完它的所有子节点之后，再把它的 r 设为 sum。
这样就完成了。

\color{green}\text{AC代码：}

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int head[maxn<<1];
struct EDGE
{
    int to,nxt;
}edge[maxn<<1];
int tot;
inline void add(int u,int to)
{
    edge[++tot].to=to;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
int n;
int rd[maxn];//存储入度
struct Val
{
    int l,r;
}val[maxn];//存储每个点的取值范围
int dbg;
bool vis[maxn];
int sum=1;
void dfs(int u)
{
    val[u].l=sum;
    vis[u]=1;
    bool flag=0;
    //因为如果当前点有子树的话
    //统计答案会多统计1
    //在此需要标明以来
    //减去这个误差
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(vis[to])continue;
        if(flag)sum++;
        flag|=1;
        dfs(to);
    }
    val[u].r=sum;
}
int main()
{
    scanf("%d",&n);
    int ut,vt;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&ut,&vt);
        add(ut,vt);
        add(vt,ut);
        rd[ut]++;
        rd[vt]++;
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        printf("%d %d\n",val[i].l,val[i].r);
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}