首页 > 其他分享 >[USACO03Open] Lost Cows(二分加树状数组)

[USACO03Open] Lost Cows(二分加树状数组)

时间:2024-09-29 17:25:17浏览次数:9  
标签:typedef vector Lost int unsigned long USACO03Open Cows

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 1e4;
int a[N],b[N];
int n;
template <class T>
struct BIT
{
	T c[N];
	int sz;
	void init(int s)
	{
		sz = s;
		for(int i=1;i<=sz;++i) c[i] = 0;
	}
	T lowbit(int x)
	{
		return x&-x;
	}
	T sum(int x) 
	{
		assert(x <= sz);
		T res=0;
		while(x) res+=c[x],x-=lowbit(x);
		return res;
	}
	T query(int L, int R)
    {
        return sum(R) - sum(L-1);
    }
	void update(int x,int y) 
	{
		assert(x != 0);
		while(x<=sz) c[x]+=y,x+=lowbit(x);
	}
};
BIT<int> A;
void solve()
{
    cin>>n;
	A.init(n);
	for(int i=2;i<=n;++i) cin>>a[i];
	b[n] = a[n]+1;
	A.update(b[n],1);
	for(int i=n-1;i;--i)
	{
		int L = 0, R = n+1;
		while(L+1<R)
		{
			int M = (L+R)/2;
			//M-1为前面至多有多少小于M,-A.sum(M-1)是后面出现过的数
			if(M-1-A.sum(M-1)<=a[i]) L = M;
			else R = M;
		}
		b[i] = L;
		A.update(b[i],1);
	}
	for(int i=1;i<=n;++i) cout<<b[i]<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}

标签:typedef,vector,Lost,int,unsigned,long,USACO03Open,Cows
From: https://www.cnblogs.com/ruoye123456/p/18440446

相关文章

  • SQLSTATE[HY000] [2013] Lost connection to MySQL server at 'reading initial commu
    错误信息 SQLSTATE[HY000][2013]LostconnectiontoMySQLserverat'readinginitialcommunicationpacket',systemerror:111 表示在尝试与MySQL服务器建立连接时出现了问题,具体来说是在读取初始通信包时失去了与MySQL服务器的连接,系统错误码为111,这通常表示连接被拒绝......
  • SQLSTATE[HY000] [2013] Lost connection to MySQL server at 'reading initial commu
    错误信息 SQLSTATE[HY000][2013]LostconnectiontoMySQLserverat'readinginitialcommunicationpacket',systemerror:111 翻译成中文为:在读取初始化数据包时失去到MySQL服务器的连接,系统错误111。通讯包初始化失败,估计是不允许连接访问引起的。解决办法以下是......
  • 题解:[USACO07DEC] Sightseeing Cows G
    洛谷P2868题目大意有个nnn个点,mmm条边的有向图,点有点权,边有边......
  • 题解:洛谷 P10497 [USACO03Open] Lost Cows
    原题链接思路+算法首先,考虑读入到\(a_i\)时,如果要得到此时的最优解(指所有牛的编号不重不漏地覆盖\([1,i]\)的所有编号),对于第\(i\)头奶牛,因为在它前面有\(a_i\)头奶牛的编号小于它,所以第\(i\)头奶牛的编号应当为\(a_i+1\)。如果有一头新的奶牛\(i+1\)加入到这个......
  • 题解:P9944 [USACO21FEB] Comfortable Cows B
    思路由于每次输入\(x\)和\(y\)只改变其上下左右的值,所以每次只要更新其相邻的值即可。当某个位置相邻的奶牛数达到\(3\)时,舒适度加一。当某个位置相邻的奶牛数达到\(4\)时,舒适度减一。注意:每增加一头奶牛以后,如果该位置相邻正好有三头奶牛,则舒适度也要加一。ACcod......
  • K11505 The Lost cow[USACO-2017-USOpen-B]
    题目描述FarmerJohn最珍贵的奶牛Bessie丢了,他需要把它找回来。幸运的是,农场里只有一条长长的直路,他知道Bessie肯定在这条路上的某个地方。如果我们把这条路看成数轴,假设FarmerJohn所在位置是x,Bessie所在的位置是y(对于John是未知的),如果FarmerJohn知道Bessie的位置,那么他就......
  • [USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包
    凸包,顾名思义,就是凸多边形包围,具体定义见OI-wiki(既是周长最小也是面积最小)有Graham算法和Andrew算法,后者精度更高常数更小(因为不涉及求角度)Andrew算法:1.将点排序(横坐标为第一关键字,纵坐标为第二关键字)2.从左到右维护上半部分,再从右到左维护下半部分。具体见OI-wiki。最后说的......
  • 将 python 脚本的 stdin 重定向到 fifo 会导致 RuntimeError: input():lost sys.stdin
    我有这个python脚本,它的作用是充当服务器,它从重定向到fifo的stdin读取命令:test.py:whileTrue:try:line=input()exceptEOFError:breakprint(f'Received:{line}')在bash中运行命令:mkfifotestfifotest.py<testfifo......
  • 题解:P10733 [NOISG2019 Prelim] Lost Array
    题解:P10733[NOISG2019Prelim]LostArray思路对于任意\(\min(X_{A_{i}},X_{B_{i}})=C_{i}\)。只要让\(X_{A_{i}}\)与\(C_{i}\)取\(\max\)值。\(X_{B_{i}}\)与\(C_{i}\)取\(\max\)值。这样可以让\(\min(X_{A_{i}},X_{B_{i}})\)绝对是\(C_{i}\)。对于为赋值......
  • Cows in a Skyscraper G
    dfs版本#include<algorithm>#include<iostream>usingnamespacestd;constintN=2e1;intcat[N],cab[N];intn,w;intans;boolcmp(inta,intb){returna>b;}voiddfs(intnow,intcnt){if(cnt>=ans){re......