首页 > 其他分享 >猜数游戏[USACO2008] Haybale Guessing G

猜数游戏[USACO2008] Haybale Guessing G

时间:2024-02-04 20:13:36浏览次数:29  
标签:Guessing le return int mid USACO2008 Haybale 奶牛 干草

$ Haybale \ Guessing \ G $ (猜数游戏) 解题报告

\(Diffculty:\) \(\color{purple}省选/NOI-\)

传送门1:(HZOIER)

传送门2:(vjudge)

传送门3:(luogu)


题面

为了提高自己低得可怜的智商,奶牛们设计了一个新的猜数游戏,来锻炼她们的逻辑推理能力。 游戏开始前,一头指定的奶牛会在牛棚后面摆\(N\)
(\(1 \le N \le 1000000\)) 堆干草,每堆有若干捆,并且没有哪两堆中的草一样多。所有草堆排成一条直线,从左到右依次按1..N编号,每堆中草的捆数在 $ 1 \ ... \ 1000000000$ 之间。 然后,游戏开始。另一头参与游戏的奶牛会问那头摆干草的奶牛 \(Q\)(\(1 \le Q \le 25000\))个问题,问题的格式如下: 编号为 $ Ql...Qh $ ( $ 1 \le Ql \le Qh \le N $ )的草堆中,最小的那堆里有多少捆草?

对于每个问题,摆干草的奶牛回答一个数字\(A\),但或许是不想让提问的奶牛那么容易地得到答案,又或许是她自己可能记错每堆中干草的捆数,总之,她的回答不保证是正确的。 请你帮助提问的奶牛判断一下,摆干草的奶牛的回答是否有自相矛盾之处。

注意:如果有冲突出现输出一个数\(m\),使得前\(m-1\)个命题不冲突。


输入格式

第\(1\)行: \(2\)个用空格隔开的整数:\(N\) 和 \(Q\)

第 $ 2...Q+1$ 行: 每行为\(3\)个用空格隔开的整数\(Ql、Qh、A\),描述了一个问题以及它对应的回答

输出格式

第\(1\)行: 如果摆干草的奶牛有可能完全正确地回答了这些问题(也就是说,能 找到一种使得所有回答都合理的摆放干草的方法),输出\(0\),否则输出 \(1\) 个 \(1...Q\) 中的数,表示这个问题的答案与它之前的那些回答有冲突之处

样例输入

20 4
1 10 7
5 19 7
3 12 8
11 15 12

样例输出

3

题解

注意到\(m\)(输出)只与前\(m-1\)个数有关。

因此这么考虑:

  1. 如果\(m\)是一个可能错的节点,那么真正的输出的$ \ \ ans$ $ \ \le \ m $

  2. 如果\(m\)此时完全有理由正确,那么 $ \ ans \ge m $

一眼的 \(\bf{二分答案}\)

再考虑\(check\)函数的写法(难点)

  1. 如何使得当前的\(m\)与之前的关系是合法的?

首先考虑什么时候不合法:

·1.当存在两个询问出的最大值相等且不存在交集时

·2.当此询问所在的区间最小值已经确定,\(dam\)存在一个子集合最小值小于其最小值。

  1. 如何解决这两种问题?

·1:在\(check\)函数中将目前的前面的询问按从大到小进行排序,并处理\(v\)相等的情况。

在此过程中判断所有的询问是否有交集,若没有,则不合法

·2:求一下交集的区间内是否都被动过,若返回值等于\(1\)(被使用了,且最小值大于此时说的最小值)

问题:如何求交集的区间是否全被动了?

我们可以设被破了的是1,处是0 ... 咳咳咳, 设被求过的是\(0\),被求过了的是\(1\)

用线段树赋值\(0\)和\(1\),求是否这一段区间是否全是一,只要用区间查询求出的值是否等于区间长就好了。

\(\bf最后注意:多次调用要清零!\)

\(code\)

#include<bits/stdc++.h>
#define int long long
using namespace std ; 
const int N = 1e6 + 100 ; 
struct lic
{
    int x , y , v ; 
}a[ N ] ; 
int n , m ; 
bool cmp ( lic a , lic b )
{
    return a.v > b.v ; 
}
inline int read( )
{
    int x = 0 , f = 1 ; 
    char c = getchar( ) ; 
    while ( c < '0' || c > '9' )
    {
        if( c == '-' )
        {
            f = -1 ; 
        }
        c = getchar( ) ; 
    }
    while ( c >= '0' && c <= '9' )
    {
        x = x * 10 + c - '0' ; 
        c = getchar( ) ;  
    }
    return x * f ; 
}
namespace Segment_Tree_Double_interval
{
    #define lson ( id << 1 )
    #define rson ( id << 1 | 1 )
    int t[ N << 2 ] , lazy[ N << 2 ] ;
    inline void Clear( )
    {
        memset( t , 0 , sizeof( t ) ) ; 
        memset( lazy , 0 , sizeof( lazy ) ) ; 
    } 
    inline void push_up( int id )
    {
        t[ id ] = t[ lson ] + t[ rson ] ; 
        return ; 
    }
    inline void paint( int id , int l , int r )
    {
        t[ id ] = r - l + 1 ; 
        lazy[ id ] = 1 ; 
        return ; 
    } 
    inline void push_down( int id , int l , int r )
    {
        if( lazy[ id ] )
        {
            int mid = ( l + r ) >> 1 ; 
            if( l <= mid ) paint( lson , l , mid ) ; 
            if( r > mid )  paint( rson , mid + 1 , r ) ; 
            lazy[ id ] = 0 ; 
        } 
        return ; 
    } 
    void updata( int id , int l , int r , int x, int y )
    {
        if ( x <= l && r <= y )
        { 
            paint( id , l , r ) ; 
            return ; 
        } 
        push_down( id , l , r ) ; 
        int mid = ( l + r ) >> 1 ; 
        if( x <= mid ) updata( lson , l , mid , x , y ) ; 
        if( y > mid ) updata( rson , mid + 1 , r , x , y ) ; 
        push_up( id ) ; 
    } 
    int query( int id , int l , int r , int x , int y )
    {
        if( x <= l && r <= y )
        {
            return t[ id ] ; 
        }
        push_down( id , l , r ) ; 
        int mid = ( l + r ) >> 1 ; 
        int ans = 0 ; 
        if( x <= mid ) ans += query( lson , l , mid , x , y ) ; 
        if( y > mid ) ans += query( rson , mid + 1 , r , x , y ) ; 
        return ans ; 
    } 
}
using namespace Segment_Tree_Double_interval ; 
lic alpha[ N ] ; 
bool check( int mid )
{
    Clear( ) ; 
    memset( alpha , 0 ,sizeof( alpha ) ) ; 
    for( int i = 1 ; i <= mid ; ++ i )
    {
        alpha[ i ] = a[ i ] ;   
    }
    sort( alpha + 1 , alpha + mid + 1 , cmp ) ; 
    int j , l1 , l2 , r1 , r2 ; 
    for( int i = 1 ; i <= mid ; i = j )
    {
        j = i ; 
        while( alpha[ i ].v == alpha[ j ].v && j <= mid ) j ++ ; 
        l1 = l2 = alpha[ i ].x ; 
        r1 = r2 = alpha[ i ].y ; 
        for( int k = i + 1 ; k < j ; k ++ )
        {
            l1 = min ( l1 , alpha[ k ].x ) ; 
            l2 = max ( l2 , alpha[ k ].x ) ; 
            r1 = max ( r1 , alpha[ k ].y ) ; 
            r2 = min ( r2 , alpha[ k ].y ) ; 
        }
        if( l2 > r2 ) return 0 ; 
        if( query( 1 , 1 , n , l2 , r2 ) == r2 - l2 + 1 ) return 0 ; 
        updata( 1 , 1 , n , l1 , r1 ) ; 
    }
    return 1 ; 
}
signed main( )
{
    #ifndef ONLINE_JUDGE
    {
        freopen( "1.in" , "r" , stdin ) ; 
        freopen( "1.out" , "w" , stdout ) ; 
    }
    #endif
    n = read( ) ; m = read( ) ; 
    Clear( ) ; 
    for( int i = 1 ; i <= m ; ++ i )
    {
        a[ i ].x = read( ) ; a[ i ].y = read( ) ; a[ i ].v = read( ) ;  
    }
    int left = 1 , right = m ; 
    int ansl = 0 ; 
    while ( left <= right )
    {
        //cout << left << ' ' << right << '\n' ; 
        int mid = ( left + right ) >> 1 ; 
        if( check ( mid ) )
        {
            left = mid + 1 ; 
        }
        else
        {
            right = mid - 1 ; 
            ansl = mid ; 
        } 
    } 
    cout << ansl ; 
}

结尾撒花 \(\color{pink}✿✿ヽ(°▽°)ノ✿\)

标签:Guessing,le,return,int,mid,USACO2008,Haybale,奶牛,干草
From: https://www.cnblogs.com/hangry/p/18006907

相关文章

  • P2898 [USACO08JAN] Haybale Guessing G 题解
    题目传送门前置知识二分答案|并查集解法对条件的合法性判断其他题解已经讲得很明白了,这里不再赘述。这里主要讲一下用并查集实现黑白染色问题。以下内容称被覆盖为黑色,不被覆盖为白色。本题因为是单向染色,即从白到黑,故可类似luoguP1840ColortheAxis和D的并查集或......
  • Codeforces Global Round 17 A. Anti Light's Cell Guessing
    给一个\(n\timesm\)的网格,里面藏了一个炸弹\((x_0,y_0)\)。你可以选择\(k\)个坐标\((x_1,y_1),(x_2,y_2),\cdots,(x_k,y_k)\)。第\(i\)次选择计算机会回复你一个数\(d_i=|x_0-x_i|+|y_0-y_i|\)。至少需要选出多少个坐标才能确定\((x_0,y_0)\)的位......
  • 北大ACM poj3589 Number-guessing Game
    Number-guessingGameTimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:5805 Accepted:4204DescriptionLarrylikesplayingthenumber-guessinggame.Twoplayersareneededinagame.SupposetheyareXandY,andXpresentsanumberforYtogu......
  • Fixed Point Guessing (交互题, 贪心,奇偶)
    思路: 保存有用信息,删除多余信息, 每一次查询会给出L,R内的所有数,那么如何利用这个条件,->统计在L,R区间的数的个数进一步发现,只有位置不变的数会在这个区间内, 统计在L,R区间的数的个数才会奇数,其他情况都是偶数这里可以去分类讨论一下因此以此来二分即......
  • CF1780D Bit Guessing Game
    题目链接-https://codeforces.com/contest/1780/problem/D终端有一个需要猜的数\(x\),\(x\leq10^9\),每轮终端会给你返回一个数\(a\)表示\(x\)在二进制下有多少个......
  • CF1780E Bit Guessing Game
    题目链接-https://codeforces.com/contest/1780/problem/E给定一张无向图,其中有\(R-L+1\)个点,编号从\(L\)到\(R\),每两个点\(u\),\(v\)间连一条边,边权为\(gc......
  • CF 1780-D. Bit Guessing Game_Codeforces Round #846 (Div. 2) D
    一道交互题有一个数字a(1<=a<=1e9),给出它的二进制表示中'1'的数目最多30次询问,每次询问输出"-x",之后给出a-x后的二进制表示中'1'的数目,最后以这样的形式"!ans"输出原数字......
  • CodeForces - 1698D Fixed Point Guessing
    CodeForces-1698DFixedPointGuessing题解:二分+交互题题目给出询问次数为15次,而\(3<=n<10^4\),很明显是二分题目想要我们找出在数组长度n为奇数的情况下,交换\(\fra......
  • AcWing340通信道路/ USACO2008 Telephone Line S
    AcWing题目洛谷题目解题思路首先可以得到一个很容易得到的贪心策略,将一条路径上最贵的(边权最大)的\(K\)条边删去,那么我们剩下的路径中最贵(边权最大)的路就是原本这条路径......
  • 题解 AGC059C【Guessing Permutation for as Long as Possible】
    problem小明有一个隐藏的排列\(p\),小红想要猜出来。现在允许小红提问,每次提问的形式是\(a_i\)和\(b_i\),然后小明会告诉小红谁大谁小。小红是个老实的人,她的询问顺序......