1 条题解

  • 0
    @ 2025-3-8 15:39:01

    很简单的题目，一眼set。

    #include<bits/stdc++.h>
#define code using
#define by namespace
#define langmou std;
#define int long long
#define un unsigned
code by langmou
#define maxn 100010
#define inf 0x3f3f3f3f3f3f3f3f
int read()
{
	int x = 0,y = 1;
	char ch = getchar();
	while(ch < '0'||ch > '9')
	{
		if(ch == '-') y = -1;
		ch = getchar();
	}
	while(ch >= '0'&&ch <= '9')
	{
		x = x*10+ch-48;
		ch = getchar();
	}
	return x*y;
}
void print(int x)
{
	static int sta[50];
	int top = 0;
	do
	{
		sta[top++] = x % 10, x /= 10;
	}
	while (x);
	while (top) putchar(sta[--top] + 48);
}
set<int>mp;
struct ship
{
	int t,k;
	set<int>x;
} a[maxn];
int n;
int f[maxn];
int tp=1;
signed main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		f[i]=i;
		a[i].t=read(),a[i].k=read();
		for(int j=1;j<=a[i].k;++j) a[i].x.insert(read());
	}
	for(int i=1;i<=n;++i)
	{
		if(a[i].t==a[f[i-1]].t)
		{
			f[i]=f[i-1];
			for(int ii:a[i].x) a[f[i]].x.insert(ii);
		}
	}
	for(int i=1;i<=n;++i)
	{
		
		for(int j:a[f[i]].x) mp.insert(j);
		print(mp.size()),putchar(10);
	}
	return 0;
}

    然后发现超过一天的不计入，于是换成map。

    #include<bits/stdc++.h>
#define code using
#define by namespace
#define langmou std;
#define int long long
#define un unsigned
code by langmou
#define maxn 100010
#define inf 0x3f3f3f3f3f3f3f3f
int read()
{
	int x = 0,y = 1;
	char ch = getchar();
	while(ch < '0'||ch > '9')
	{
		if(ch == '-') y = -1;
		ch = getchar();
	}
	while(ch >= '0'&&ch <= '9')
	{
		x = x*10+ch-48;
		ch = getchar();
	}
	return x*y;
}
void print(int x)
{
	static int sta[50];
	int top = 0;
	do
	{
		sta[top++] = x % 10, x /= 10;
	}
	while (x);
	while (top) putchar(sta[--top] + 48);
}
map<int,int>mp;
struct ship
{
	int t,k;
	set<int>x;
} a[maxn];
int n;
int f[maxn];
int tp=1;
signed main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		f[i]=i;
		a[i].t=read(),a[i].k=read();
		for(int j=1;j<=a[i].k;++j) a[i].x.insert(read());
	}
	for(int i=1;i<=n;++i)
	{
		if(a[i].t==a[f[i-1]].t)
		{
			f[i]=f[i-1];
			for(int ii:a[i].x) a[f[i]].x.insert(ii);
		}
	}
	for(int i=1;i<=n;++i)
	{
		while(1)
		{
			if(tp>n) break;
			else if(a[f[i]].t-86400>=a[f[tp]].t)
			{
				for(int i:a[f[tp]].x)
				{
					auto m=&mp[i];
					--m;
				}
				++tp;
			}
			else break;
		}
    for(auto j:mp) if(j.second==0)mp.erase(j.first);
		for(int j:a[f[i]].x) ++mp[j];
		print(mp.size()),putchar(10);
	}
	return 0;
}

    但是超时了，一看发现 O(n2logn)O(n^2log n) ,于是把map头文件搬出来,把 '[]' 操作返回值从 (__i).second 改成 (__i) 然后发现和std::map冲突,于是删除所有和map有关的头文件,AC代码如下

    很简单的题目，一眼set。
```c++
#include<bits/stdc++.h>
#define code using
#define by namespace
#define langmou std;
#define int long long
#define un unsigned
code by langmou
#define maxn 100010
#define inf 0x3f3f3f3f3f3f3f3f
int read()
{
	int x = 0，y = 1;
	char ch = getchar();
	while(ch < '0'||ch > '9')
	{
		if(ch == '-') y = -1;
		ch = getchar();
	}
	while(ch >= '0'&&ch <= '9')
	{
		x = x*10+ch-48;
		ch = getchar();
	}
	return x*y;
}
void print(int x)
{
	static int sta[50];
	int top = 0;
	do
	{
		sta[top++] = x % 10， x /= 10;
	}
	while (x);
	while (top) putchar(sta[--top] + 48);
}
set<int>mp;
struct ship
{
	int t，k;
	set<int>x;
} a[maxn];
int n;
int f[maxn];
int tp=1;
signed main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		f[i]=i;
		a[i].t=read()，a[i].k=read();
		for(int j=1;j<=a[i].k;++j) a[i].x.insert(read());
	}
	for(int i=1;i<=n;++i)
	{
		if(a[i].t==a[f[i-1]].t)
		{
			f[i]=f[i-1];
			for(int ii:a[i].x) a[f[i]].x.insert(ii);
		}
	}
	for(int i=1;i<=n;++i)
	{
		
		for(int j:a[f[i]].x) mp.insert(j);
		print(mp.size())，putchar(10);
	}
	return 0;
}

    然后发现超过一天的不计入，于是换成map。

    #include<bits/stdc++.h>
#define code using
#define by namespace
#define langmou std;
#define int long long
#define un unsigned
code by langmou
#define maxn 100010
#define inf 0x3f3f3f3f3f3f3f3f
int read()
{
	int x = 0，y = 1;
	char ch = getchar();
	while(ch < '0'||ch > '9')
	{
		if(ch == '-') y = -1;
		ch = getchar();
	}
	while(ch >= '0'&&ch <= '9')
	{
		x = x*10+ch-48;
		ch = getchar();
	}
	return x*y;
}
void print(int x)
{
	static int sta[50];
	int top = 0;
	do
	{
		sta[top++] = x % 10， x /= 10;
	}
	while (x);
	while (top) putchar(sta[--top] + 48);
}
map<int，int>mp;
struct ship
{
	int t，k;
	set<int>x;
} a[maxn];
int n;
int f[maxn];
int tp=1;
signed main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		f[i]=i;
		a[i].t=read()，a[i].k=read();
		for(int j=1;j<=a[i].k;++j) a[i].x.insert(read());
	}
	for(int i=1;i<=n;++i)
	{
		if(a[i].t==a[f[i-1]].t)
		{
			f[i]=f[i-1];
			for(int ii:a[i].x) a[f[i]].x.insert(ii);
		}
	}
	for(int i=1;i<=n;++i)
	{
		while(1)
		{
			if(tp>n) break;
			else if(a[f[i]].t-86400>=a[f[tp]].t)
			{
				for(int i:a[f[tp]].x)
				{
					auto m=&mp[i];
					--m;
				}
				++tp;
			}
			else break;
		}
    for(auto j:mp) if(j.second==0)mp.erase(j.first);
		for(int j:a[f[i]].x) ++mp[j];
		print(mp.size())，putchar(10);
	}
	return 0;
}

    但是超时了，一看发现 O(n2logn)O(n^2log n) ，于是把map头文件搬出来，把 '[]' 操作返回值从 (__i).second 改成 (__i) 然后发现和std::map冲突，于是删除所有和map有关的头文件，AC代码如下

    #include<iostream>
#include<cmath>
#include<bits/stl_tree.h>
#include<set>
#define code using
#define by namespace
#define langmou std;
#define int long long
#define un unsigned
code by langmou
#define maxn 100010
#define inf 0x3f3f3f3f3f3f3f3f
int read()
{
	int x = 0，y = 1;
	char ch = getchar();
	while(ch < '0'||ch > '9')
	{
		if(ch == '-') y = -1;
		ch = getchar();
	}
	while(ch >= '0'&&ch <= '9')
	{
		x = x*10+ch-48;
		ch = getchar();
	}
	return x*y;
}
void print(int x)
{
	static int sta[50];
	int top = 0;
	do
	{
		sta[top++] = x % 10， x /= 10;
	}
	while (x);
	while (top) putchar(sta[--top] + 48);
}
#ifndef _STL_MAP_H
#define _STL_MAP_H 1

#include <bits/functexcept.h>
#include <bits/concept_check.h>
#if __cplusplus >= 201103L
#include <initializer_list>
#include <tuple>
#endif

namespace std _GLIBCXX_VISIBILITY(default)
{
	_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
	template <typename _Key， typename _Tp， typename _Compare = less<_Key>，
	         typename _Alloc = allocator<pair<const _Key， _Tp> > >
	class map
	{
		public:
			typedef _Key                                          key_type;
			typedef _Tp                                           mapped_type;
			typedef pair<const _Key， _Tp>                    value_type;
			typedef _Compare                                      key_compare;
			typedef _Alloc                                        allocator_type;

		private:
			// concept requirements
			typedef typename _Alloc::value_type                   _Alloc_value_type;
			__glibcxx_class_requires(_Tp， _SGIAssignableConcept)
			__glibcxx_class_requires4(_Compare， bool， _Key， _Key，
			                          _BinaryFunctionConcept)
			__glibcxx_class_requires2(value_type， _Alloc_value_type， _SameTypeConcept)

		public:
			class value_compare
				: public binary_function<value_type， value_type， bool>
			{
					friend class map<_Key， _Tp， _Compare， _Alloc>;
				protected:
					_Compare comp;

					value_compare(_Compare __c)
						: comp(__c) { }

				public:
					bool operator()(const value_type& __x， const value_type& __y) const
					{
						return comp(__x.first， __y.first);
					}
			};

		private:
			/// This turns a red-black tree into a [multi]map.
			typedef typename _Alloc::template rebind<value_type>::other
			_Pair_alloc_type;

			typedef _Rb_tree<key_type， value_type， _Select1st<value_type>，
			        key_compare， _Pair_alloc_type> _Rep_type;

			/// The actual tree structure.
			_Rep_type _M_t;

		public:
			typedef typename _Pair_alloc_type::pointer         pointer;
			typedef typename _Pair_alloc_type::const_pointer   const_pointer;
			typedef typename _Pair_alloc_type::reference       reference;
			typedef typename _Pair_alloc_type::const_reference const_reference;
			typedef typename _Rep_type::iterator               iterator;
			typedef typename _Rep_type::const_iterator         const_iterator;
			typedef typename _Rep_type::size_type              size_type;
			typedef typename _Rep_type::difference_type        difference_type;
			typedef typename _Rep_type::reverse_iterator       reverse_iterator;
			typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
			map()
				: _M_t() { }
			explicit
			map(const _Compare& __comp，
			    const allocator_type& __a = allocator_type())
				: _M_t(__comp， _Pair_alloc_type(__a)) { }
			map(const map& __x)
				: _M_t(__x._M_t) { }

#if __cplusplus >= 201103L
			map(map&& __x)
			noexcept(is_nothrow_copy_constructible<_Compare>::value)
				: _M_t(move(__x._M_t)) { }
			map(initializer_list<value_type> __l，
			    const _Compare& __comp = _Compare()，
			    const allocator_type& __a = allocator_type())
				: _M_t(__comp， _Pair_alloc_type(__a))
			{
				_M_t._M_insert_unique(__l.begin()， __l.end());
			}
#endif
			template<typename _InputIterator>
			map(_InputIterator __first， _InputIterator __last)
				: _M_t()
			{
				_M_t._M_insert_unique(__first， __last);
			}
			template<typename _InputIterator>
			map(_InputIterator __first， _InputIterator __last，
			    const _Compare& __comp，
			    const allocator_type& __a = allocator_type())
				: _M_t(__comp， _Pair_alloc_type(__a))
			{
				_M_t._M_insert_unique(__first， __last);
			}
			map&
			operator=(const map& __x)
			{
				_M_t = __x._M_t;
				return *this;
			}

#if __cplusplus >= 201103L
			map&
			operator=(map&& __x)
			{
				// NB: DR 1204.
				// NB: DR 675.
				this->clear();
				this->swap(__x);
				return *this;
			}
			map&
			operator=(initializer_list<value_type> __l)
			{
				this->clear();
				this->insert(__l.begin()， __l.end());
				return *this;
			}
#endif

			/// Get a copy of the memory allocation object.
			allocator_type
			get_allocator() const _GLIBCXX_NOEXCEPT
			{
				return allocator_type(_M_t.get_allocator());
			}
			iterator
			begin() _GLIBCXX_NOEXCEPT
			{ return _M_t.begin();}
			const_iterator
			begin() const _GLIBCXX_NOEXCEPT
			{
				return _M_t.begin();
			}
			iterator
			end() _GLIBCXX_NOEXCEPT
			{ return _M_t.end();}
			const_iterator
			end() const _GLIBCXX_NOEXCEPT
			{
				return _M_t.end();
			}
			reverse_iterator
			rbegin() _GLIBCXX_NOEXCEPT
			{ return _M_t.rbegin();}
			const_reverse_iterator
			rbegin() const _GLIBCXX_NOEXCEPT
			{
				return _M_t.rbegin();
			}
			reverse_iterator
			rend() _GLIBCXX_NOEXCEPT
			{ return _M_t.rend();}
			const_reverse_iterator
			rend() const _GLIBCXX_NOEXCEPT
			{
				return _M_t.rend();
			}

#if __cplusplus >= 201103L
			const_iterator
			cbegin() const noexcept
			{
				return _M_t.begin();
			}
			const_iterator
			cend() const noexcept
			{
				return _M_t.end();
			}
			const_reverse_iterator
			crbegin() const noexcept
			{
				return _M_t.rbegin();
			}
			const_reverse_iterator
			crend() const noexcept
			{
				return _M_t.rend();
			}
#endif
			bool
			empty() const _GLIBCXX_NOEXCEPT
			{
				return _M_t.empty();
			}

			/** Returns the size of the %map.  */
			size_type
			size() const _GLIBCXX_NOEXCEPT
			{
				return _M_t.size();
			}

			/** Returns the maximum size of the %map.  */
			size_type
			max_size() const _GLIBCXX_NOEXCEPT
			{
				return _M_t.max_size();
			}
			value_type&
			operator[](const key_type& __k)
			{
				// concept requirements
				__glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)

				iterator __i = lower_bound(__k);
				// __i->first is greater than or equivalent to __k.
				if (__i == end() || key_comp()(__k， (*__i).first))
#if __cplusplus >= 201103L
					__i = _M_t._M_emplace_hint_unique(__i， piecewise_construct，
					                                  tuple<const key_type&>(__k)，
					                                  tuple<>());
#else
					__i = insert(__i， value_type(__k， mapped_type()));
#endif
				return (*__i);
			}

#if __cplusplus >= 201103L
			mapped_type&
			operator[](key_type&& __k)
			{
				// concept requirements
				__glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)

				iterator __i = lower_bound(__k);
				// __i->first is greater than or equivalent to __k.
				if (__i == end() || key_comp()(__k， (*__i).first))
					__i = _M_t._M_emplace_hint_unique(__i， piecewise_construct，
					                                  forward_as_tuple(move(__k))，
					                                  tuple<>());
				return (*__i);
			}
#endif
			mapped_type&
			at(const key_type& __k)
			{
				iterator __i = lower_bound(__k);
				if (__i == end() || key_comp()(__k， (*__i).first))
					__throw_out_of_range(__N("map::at"));
				return (*__i).second;
			}

			const mapped_type&
			at(const key_type& __k) const
			{
				const_iterator __i = lower_bound(__k);
				if (__i == end() || key_comp()(__k， (*__i).first))
					__throw_out_of_range(__N("map::at"));
				return (*__i).second;
			}

			// modifiers
#if __cplusplus >= 201103L
			template<typename... _Args>
			pair<iterator， bool>
			emplace(_Args&&... __args)
			{
				return _M_t._M_emplace_unique(forward<_Args>(__args)...);
			}
			template<typename... _Args>
			iterator
			emplace_hint(const_iterator __pos， _Args&&... __args)
			{
				return _M_t._M_emplace_hint_unique(__pos，
				                                   forward<_Args>(__args)...);
			}
#endif
			pair<iterator， bool>
			insert(const value_type& __x)
			{
				return _M_t._M_insert_unique(__x);
			}

#if __cplusplus >= 201103L
			template<typename _Pair， typename = typename
			enable_if<is_constructible<value_type，
			          _Pair&&>::value>::type>
			pair<iterator， bool>
			insert(_Pair&& __x)
			{
				return _M_t._M_insert_unique(forward<_Pair>(__x));
			}
#endif

#if __cplusplus >= 201103L
			void
			insert(initializer_list<value_type> __list)
			{
				insert(__list.begin()， __list.end());
			}
#endif
			iterator
#if __cplusplus >= 201103L
			insert(const_iterator __position， const value_type& __x)
#else
			insert(iterator __position， const value_type& __x)
#endif
			{
				return _M_t._M_insert_unique_(__position， __x);
			}

#if __cplusplus >= 201103L
			template<typename _Pair， typename = typename
			enable_if<is_constructible<value_type，
			          _Pair&&>::value>::type>
			iterator
			insert(const_iterator __position， _Pair&& __x)
			{
				return _M_t._M_insert_unique_(__position，
				                              forward<_Pair>(__x));
			}
#endif

			template<typename _InputIterator>
			void
			insert(_InputIterator __first， _InputIterator __last)
			{
				_M_t._M_insert_unique(__first， __last);
			}

#if __cplusplus >= 201103L
			iterator erase(const_iterator __position)
			{
				return _M_t.erase(__position);
			}

			// LWG 2059.
			iterator erase(iterator __position)
			{
				return _M_t.erase(__position);
			}
#else
			void erase(iterator __position)
			{
				_M_t.erase(__position);
			}
#endif
			size_type
			erase(const key_type& __x)
			{
				return _M_t.erase(__x);
			}

#if __cplusplus >= 201103L
			iterator
			erase(const_iterator __first， const_iterator __last)
			{
				return _M_t.erase(__first， __last);
			}
#else
			void
			erase(iterator __first， iterator __last)
			{
				_M_t.erase(__first， __last);
			}
#endif
			void
			swap(map& __x)
			{
				_M_t.swap(__x._M_t);
			}
			void
			clear() _GLIBCXX_NOEXCEPT
			{ _M_t.clear();}
			key_compare
			key_comp() const
			{
				return _M_t.key_comp();
			}
			value_compare
			value_comp() const
			{
				return value_compare(_M_t.key_comp());
			}
			iterator
			find(const key_type& __x)
			{
				return _M_t.find(__x);
			}
			const_iterator
			find(const key_type& __x) const
			{
				return _M_t.find(__x);
			}
			size_type
			count(const key_type& __x) const
			{
				return _M_t.find(__x) == _M_t.end() ? 0 : 1;
			}
			iterator
			lower_bound(const key_type& __x)
			{
				return _M_t.lower_bound(__x);
			}
			const_iterator
			lower_bound(const key_type& __x) const
			{
				return _M_t.lower_bound(__x);
			}
			iterator
			upper_bound(const key_type& __x)
			{
				return _M_t.upper_bound(__x);
			}
			const_iterator
			upper_bound(const key_type& __x) const
			{
				return _M_t.upper_bound(__x);
			}

			pair<iterator， iterator>
			equal_range(const key_type& __x)
			{
				return _M_t.equal_range(__x);
			}
			pair<const_iterator， const_iterator>
			equal_range(const key_type& __x) const
			{
				return _M_t.equal_range(__x);
			}

			template<typename _K1， typename _T1， typename _C1， typename _A1>
			friend bool
			operator==(const map<_K1， _T1， _C1， _A1>&，
			           const map<_K1， _T1， _C1， _A1>&);

			template<typename _K1， typename _T1， typename _C1， typename _A1>
			friend bool
			operator<(const map<_K1， _T1， _C1， _A1>&，
			          const map<_K1， _T1， _C1， _A1>&);
	};
	template<typename _Key， typename _Tp， typename _Compare， typename _Alloc>
	inline bool
	operator==(const map<_Key， _Tp， _Compare， _Alloc>& __x，
	           const map<_Key， _Tp， _Compare， _Alloc>& __y)
	{
		return __x._M_t == __y._M_t;
	}
	template<typename _Key， typename _Tp， typename _Compare， typename _Alloc>
	inline bool
	operator<(const map<_Key， _Tp， _Compare， _Alloc>& __x，
	          const map<_Key， _Tp， _Compare， _Alloc>& __y)
	{
		return __x._M_t < __y._M_t;
	}

	/// Based on operator==
	template<typename _Key， typename _Tp， typename _Compare， typename _Alloc>
	inline bool
	operator!=(const map<_Key， _Tp， _Compare， _Alloc>& __x，
	           const map<_Key， _Tp， _Compare， _Alloc>& __y)
	{
		return !(__x == __y);
	}

	/// Based on operator<
	template<typename _Key， typename _Tp， typename _Compare， typename _Alloc>
	inline bool
	operator>(const map<_Key， _Tp， _Compare， _Alloc>& __x，
	          const map<_Key， _Tp， _Compare， _Alloc>& __y)
	{
		return __y < __x;
	}

	/// Based on operator<
	template<typename _Key， typename _Tp， typename _Compare， typename _Alloc>
	inline bool
	operator<=(const map<_Key， _Tp， _Compare， _Alloc>& __x，
	           const map<_Key， _Tp， _Compare， _Alloc>& __y)
	{
		return !(__y < __x);
	}

	/// Based on operator<
	template<typename _Key， typename _Tp， typename _Compare， typename _Alloc>
	inline bool
	operator>=(const map<_Key， _Tp， _Compare， _Alloc>& __x，
	           const map<_Key， _Tp， _Compare， _Alloc>& __y)
	{
		return !(__x < __y);
	}

	/// See map::swap().
	template<typename _Key， typename _Tp， typename _Compare， typename _Alloc>
	inline void
	swap(map<_Key， _Tp， _Compare， _Alloc>& __x，
	     map<_Key， _Tp， _Compare， _Alloc>& __y)
	{
		__x.swap(__y);
	}

	_GLIBCXX_END_NAMESPACE_CONTAINER
}

#endif /*_STL_MAP_H*/
map<int，int>mp;
struct ship
{
	int t，k;
	set<int>x;
} a[maxn];
int n;
int f[maxn];
int tp=1;
signed main()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		f[i]=i;
		a[i].t=read()，a[i].k=read();
		for(int j=1;j<=a[i].k;++j) a[i].x.insert(read());
	}
	for(int i=1;i<=n;++i)
	{
		if(a[i].t==a[f[i-1]].t)
		{
			f[i]=f[i-1];
			for(int ii:a[i].x) a[f[i]].x.insert(ii);
		}
	}
	for(int i=1;i<=n;++i)
	{
		while(1)
		{
			if(tp>n) break;
			else if(a[f[i]].t-86400>=a[f[tp]].t)
			{
				for(int i:a[f[tp]].x)
				{
					auto m=&mp[i];
					--m->second;
					if(m->second<=0) mp.erase(m->first);
				}
				++tp;
			}
			else break;
		}
		for(int j:a[f[i]].x) ++mp[j].second;
		print(mp.size())，putchar(10);
	}

	return 0;
}
    • 1

    海港

    信息

    ID
    433
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    49
    已通过
    16
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. 版权申诉
    6. Language
    7. 兼容模式
    8. 主题
    2. © 2021-2025 Hydro.ac
    5. Worker 2 in 44ms
    6. Hydro v5.0.0-alpha.0-4421f98-dirty Professional