[TIOJ] 1777. 房屋運動(HOU12)

題目連結:http://tioj.infor.org/problems/1777
先說本題需要寫個大數，要有減法運算跟比大小的運算，因為我有點懶(?所以就抄了日月掛長大大的模板 正題:其實不難發現兩人相撞後其實就是兩然交換往哪邊滾動的工作，其他位置什麼的都沒變，而題目也只要求最少需要多久，沒問說誰是最後一個完成的，所以我們其實就直接找離終點最遠的那位就好了，不過值得注意的是如果他兩個方向都可以就要選比較小的那個，大概就醬吧 
#include <bits/stdc++.h>
using namespace std;

#ifndef SUN_MOON_BIG_INT
#define SUN_MOON_BIG_INT
#define SM_BASE 1000000000
#define SM_BASE_DIGITS 9
/*SM_BASE 0 的個數為SM_BASE_DIGITS*/
#include<vector>
#include<iostream>
#include<iomanip>
#include<string>
#include<utility>/*for pair*/
class bigN{
	private:
	std::vector<int>s;
	char sign;
	inline void trim(){
		while(!s.empty()&&!s.back())s.pop_back();
		if(s.empty())sign=1;
	}
	inline char cmp(const bigN &v,bool is=1)const{
		if(is){
			if(sign>v.sign)return 1;
			if(sign<v.sign)return -1;
		}
		char d=sign>0||!is?1:-1;
		if(s.size()>v.s.size())return d;
		if(s.size()<v.s.size())return -d;
		for(int i=s.size()-1;i>=0;i--){
			if(s[i]>v.s[i])return d;
			if(s[i]<v.s[i])return -d;
		}
		return 0;
	}
	inline std::vector<int> convert_base(const std::vector<int> &a,int old_digits,int new_digits)const{
		std::vector<long long> p(std::max(old_digits,new_digits)+1);
		p[0]=1;
		for(int i=1;i<(int)p.size();++i)p[i]=p[i-1]*10;
		std::vector<int> ans;
		long long cur=0;
		int cur_digits=0;
		for (int i=0;i<(int)a.size();++i){
			cur+=a[i]*p[cur_digits];
			cur_digits+=old_digits;
			while(cur_digits>=new_digits){
				ans.push_back(cur%p[new_digits]);
				cur/=p[new_digits];
				cur_digits-=new_digits;
			}
		}
		ans.push_back((int)cur);
		while (!ans.empty()&&!ans.back())ans.pop_back();
		return ans;
	}
	inline std::vector<long long> karatsuba(const std::vector<long long> &a,const std::vector<long long> &b)const{
		int n=a.size();
		std::vector<long long> res(n*2);
		if(n<=32){
			for(int i=0;i<n;++i)
				for(int j=0;j<n;++j)
					res[i+j]+=a[i]*b[j];
			return res;
		}
		int k=n/2;
		std::vector<long long> a1(a.begin(),a.begin()+k);
		std::vector<long long> a2(a.begin()+k,a.end());
		std::vector<long long> b1(b.begin(),b.begin()+k);
		std::vector<long long> b2(b.begin()+k,b.end());

		std::vector<long long> a1b1=karatsuba(a1,b1);
		std::vector<long long> a2b2=karatsuba(a2,b2);

		for(int i=0;i<k;++i)a2[i]+=a1[i];
		for(int i=0;i<k;++i)b2[i]+=b1[i];

		std::vector<long long> r=karatsuba(a2,b2);
		for(int i=0;i<(int)a1b1.size();++i)r[i]-=a1b1[i];
		for(int i=0;i<(int)a2b2.size();++i)r[i]-=a2b2[i];

		for(int i=0;i<(int)r.size();++i)res[i+k]+=r[i];
		for(int i=0;i<(int)a1b1.size();++i)res[i]+=a1b1[i];
		for(int i=0;i<(int)a2b2.size();++i)res[i+n]+=a2b2[i];
		return res;
	}
	public:
	/*初始化*/
	bigN():sign(1){}
	bigN(const long long &v){
		*this=v;
	}
	bigN(const std::string &v){
		*this=v;
	}
	/*等於運算子重載*/
	inline void operator=(const bigN &v){
		sign=v.sign;
		s=v.s;
	}
	inline void operator=(long long v){
		sign=1;s.clear();
		if (v < 0)sign=-1,v=-v;
		for(;v;v/=SM_BASE)s.push_back(v%SM_BASE);
	}
	inline void operator=(const std::string &v){
		sign=1;s.clear();
		int len=0;
		for(;len<(int)v.size()&&(v[len]=='-'||v[len]=='+');len++)
		if(v[len]=='-')sign=-1;
		for(int i=v.size()-1;i>=len;i-=SM_BASE_DIGITS){
			int x=0;
			for(int j=std::max(len,i-SM_BASE_DIGITS+1);j<=i;j++)
			x=x*10+v[j]-'0';
			s.push_back(x);
		}
		trim();
	}
	/*加減運算子重載*/
	inline bigN operator+(const bigN &v)const{
		if(sign==v.sign){
			bigN ans=v;
			int len=std::max(s.size(),v.s.size());
			for(int i=0,is=0;i<len||is;i++){
				if(i==(int)ans.s.size())ans.s.push_back(0);
				ans.s[i]+=is+(i<(int)s.size()?s[i]:0);
				is=ans.s[i]>=SM_BASE;
				if(is)ans.s[i]-=SM_BASE;
			}
			return ans;
		}else return *this-(-v);
	}
	inline bigN operator-(const bigN &v)const{
		if(sign==v.sign){
			if(~cmp(v,0)){
				bigN ans=*this;
				for(int i=0,is=0;i<(int)v.s.size()||is;i++){
					ans.s[i]-=is+(i<(int)v.s.size()?v.s[i]:0);
					is=ans.s[i]<0;
					if(is)ans.s[i]+=SM_BASE;
				}
				ans.trim();
				return ans;
			}else return -(v-*this);
		}else return *this+(-v);
	}
	/*乘法運算子重載*/
	inline bigN operator*(const bigN &v)const{
		std::vector<int> a6=convert_base(s,SM_BASE_DIGITS,6);
		std::vector<int> b6=convert_base(v.s,SM_BASE_DIGITS,6);
		std::vector<long long> a(a6.begin(),a6.end());
		std::vector<long long> b(b6.begin(),b6.end());
		while(a.size()<b.size())a.push_back(0);
		while(b.size()<a.size())b.push_back(0);
		while(a.size()&(a.size()-1))a.push_back(0),b.push_back(0);
		std::vector<long long> c=karatsuba(a,b);
		bigN ans;
		ans.sign=sign*v.sign;
		for(int i=0,carry=0;i<(int)c.size();++i){
			long long cur=c[i]+carry;
			ans.s.push_back((int)(cur%1000000));
			carry=(int)(cur/1000000);
		}
		ans.s=convert_base(ans.s,6,SM_BASE_DIGITS);
		ans.trim();
		return ans;
	}
	/*對整數的乘除做支援運算*/
	inline void operator*=(int v){
		if(v<0)sign=-sign,v=-v;
		for(int i=0,is=0;i<(int)s.size()||is;i++){
			if(i==(int)s.size())s.push_back(0);
			long long a=s[i]*(long long)v+is;
			is=(int)(a/SM_BASE);
			s[i]=(int)(a%SM_BASE);
		}
		trim();
	}
	inline bigN operator*(int v){
		bigN ans=*this;
		ans*=v;
		return ans;
	}
	inline void operator/=(int v){
		if(v<0)sign=-sign,v=-v;
		for(int i=s.size()-1,rem=0;i>=0;i--){
			long long a=s[i]+rem*(long long)SM_BASE;
			s[i]=(int)(a/v);
			rem=a%v;
		}
		trim();
	}
	inline bigN operator/(int v){
		bigN ans=*this;
		ans/=v;
		return ans;
	}
	inline int operator%(int v){
		if(v<0)v=-v;
		int m=0;
		for(int i=s.size()-1;i>=0;i--)
		m=(s[i]+m*(long long)SM_BASE)%v;
		return m*sign;
	}
	/*除法，商為first，餘為second*/
	inline friend std::pair<bigN,bigN>divmod(const bigN &a,const bigN &b){
		int norm=SM_BASE/(b.s.back()+1);
		bigN x=a.abs()*norm;
		bigN y=b.abs()*norm;
		bigN q,r;
		q.s.resize(x.s.size());
		for(int i=x.s.size()-1;i>=0;i--){
			r*=SM_BASE;
			r+=x.s[i];
			int s1=r.s.size()<=y.s.size()?0:r.s[y.s.size()];
			int s2=r.s.size()<=y.s.size()-1?0:r.s[y.s.size()-1];
			int d=((long long)SM_BASE*s1+s2)/y.s.back();
			r-=y*d;
			while(r.cmp(0,1)==-1)r+=y,--d;
			q.s[i]=d;
		}
		q.sign=a.sign*b.sign;
		r.sign=a.sign;
		q.trim();
		r.trim();
		return std::make_pair(q,r/norm);
	}
	inline bigN operator/(const bigN &v)const{
		return divmod(*this,v).first;
	}
	inline bigN operator%(const bigN &v)const{
		return divmod(*this,v).second;
	}
	/*數學指派運算子重載*/
	inline void operator+=(const bigN &v){
		*this=*this+v;
	}
	inline void operator-=(const bigN &v){
		*this=*this-v;
	}
	inline void operator*=(const bigN &v){
		*this=*this*v;
	}
	inline void operator/=(const bigN &v){
		*this=*this/v;
	}
	inline void operator%=(const bigN &v){
		*this=*this%v;
	}
	/*比較運算子重載*/
	inline bool operator<(const bigN &v)const{
		return cmp(v)<0;
	}
	inline bool operator>(const bigN &v)const{
		return cmp(v)>0;
	}
	inline bool operator<=(const bigN &v)const{
		return cmp(v)<=0;
	}
	inline bool operator>=(const bigN &v)const{
		return cmp(v)>=0;
	}
	inline bool operator==(const bigN &v)const{
		return !cmp(v);
	}
	inline bool operator!=(const bigN &v)const{
		return cmp(v)!=0;
	}
	/*數學運算子重載*/
	inline bigN abs()const{
		bigN ans=*this;
		ans.sign*=ans.sign;
		return ans;
	}
	inline bigN operator-()const{
		bigN ans=*this;
		ans.sign=-sign;
		return ans;
	}
	/* >>、<<運算子重載 */
	friend std::istream& operator>>(std::istream &stream,bigN &v) {
		std::string s;
		stream>>s;
		v=s;
		return stream;
	}
	friend std::ostream& operator<<(std::ostream &stream,const bigN &v) {
		if(v.sign==-1)stream<<'-';
		stream<<(v.s.empty()?0:v.s.back());
		for(int i=(int)v.s.size()-2;i>=0;i--)
		stream<<std::setw(SM_BASE_DIGITS)<<std::setfill('0')<<v.s[i];
		return stream;
	}
	/*是否為0*/
	inline bool iszero(){
		return !s.size()||(s.size()==1&&!s[0]);
	}
	/*形態重載*/
	inline operator std::string(){
		std::string ans,x;
		if(s.empty())return "0";
		if(sign==-1)ans+='-';
		int o=s[s.size()-1];
		while(o)x+=o%10+'0',o/=10;
		for(int i=x.size()-1;i>=0;i--)ans+=x[i];
		for(int i=s.size()-2;i>=0;i--){
			std::string t;
			int p=s[i];
			for(int j=0;j<SM_BASE_DIGITS;j++){
				t+=p%10+'0';p/=10;
			}
			for(int j=SM_BASE_DIGITS-1;j>=0;j--)ans+=t[j];
		}
		return ans;
	}
};
#endif
#undef SM_BASE
#undef SM_BASE_DIGITS

#ifdef __linux__
#define gc getchar_unlocked
#elif _WIN32
#define gc getchar
#elif __APPLE__
#define gc getchar
#endif
template<typename T>
inline void gn(T &_){T __=1;char c=gc();_=0;while((c<'0'||c>'9')&&c!='-')c=gc();if(c=='-')__=-1,c=gc();while(c>='0'&&c<='9')_=_*10+c-'0',c=gc();_*=__;}
template <typename T, typename ...Args>
inline void gn(T &x, Args& ...args){gn(x);gn(args...);}

int main(){
	cin.tie(0);ios::sync_with_stdio();
	int n;
	gn(n);
	bigN l, r;
	cin>>l>>r;
	bigN ans=0;
	for(int i=0;i<n;i++){
		bigN pos;
		cin>>pos;
		int dir;
		gn(dir);
		if(dir==0){
			if(pos-l < r-pos){
				if(pos-l > ans){
					ans=pos-l;
				}
			}else{
				if(r-pos > ans){
					ans=r-pos;
				}
			}
		}else if(dir==1){
			if(pos-l > ans){
				ans=pos-l;
			}
		}else{
			if(r-pos > ans){
				ans=r-pos;
			}
		}
	}
	cout<<ans;
	return 0;
}

留言

張貼留言

這個網誌中的熱門文章

[NPSC] 2009初賽 E. 檸檬汽水傳說

題目連結: http://contest.cc.ntu.edu.tw/npsc2009/2009sen.pdf 不 本題複雜度大概要做到$O(n)$或$O(n \log n)$，所以明顯naive的枚舉點對做法是不可能會好的，不妨思考其實每個人都只要往一邊看就好了，而且當看到一個比自己大的數就可以停了，那應該可用stack做，而明顯要用stack做的話，要有一定的單調性，想想後發現遞減的是好的，每次都pop掉比自己小的人並把pop了幾個加上去，不過值得注意的是如果是pop掉跟自己一樣的人的話，記得要把他原本的size記錄下來，之後要擺回去，因為其他人都還是可以跟你做匹配之類的，此外因為每個人都還可以跟隔壁的人溝通，所以當隔壁有人時記得多加一。 #include <bits/stdc++.h> using namespace std; class knight{ private: int __val; long long __size; public: knight(int a,int b){__val=a;__size=b;} int operator++(int a){if(a==0)return __size++;} bool operator<=(int a){return __val<=a;} bool operator==(int a){return __val==a;} friend void operator+=(long long &a, knight b){a+=b.__size;} }; stack<knight> ss; int main(){ int t; scanf("%d",&t); while(t--){ int sz; long long ans=0; scanf("%d",&sz); while(!ss.empty())ss.pop(); for(int i=0;i<sz;i++){ int aaa; scanf("%d",&aaa); long long kk=1; while(!ss.empty()&
閱讀完整內容

[TIOJ] 1902. 「殿仁．王，不認識，誰啊？」，然後他就死了……

題目連結: https://tioj.infor.org/problems/1902 直接回滾莫隊後套個 trie 來查區間 xor 最大值，複雜度 $O((N^2/K + QK) \log C)$ 之類的(沒仔細算)，$K$好好挑一下就會過。 p.s. 好像好多古代人的解都是 $O(N^2 + Q)$ 😥 #include <algorithm> #include <functional> #include <iostream> #include <iterator> #include <numeric> #include <utility> #include <vector> int main() { std::cin.tie(nullptr)->sync_with_stdio(false); auto maxi = [](auto &a, auto b) { a = std::max(a, b); }; int n, q; std::cin >> n >> q; std::vector<uint32_t> a(1); std::copy_n(std::istream_iterator<int>(std::cin), n, std::back_inserter(a)); std::partial_sum(a.begin(), a.end(), a.begin(), std::bit_xor()); struct Q { int l, r, id; Q(int l_, int r_, int id_) : l(l_), r(r_), id(id_) {} }; static constexpr int K = 128; std::vector<std::vector<Q>> qs((n + K - 1) / K); for (int i = 0; i < q; ++i) { int l, r; std::cin >> l >> r; --l; qs[l / K
閱讀完整內容

[AtCoder] [經典競程 90 題] 024 - Select +／- One（★2）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_x 題目大意: 給定兩個序列 $A$, $B$，每次操作可以把$A$中任意元素$A_i$變成$A_i-1$或$A_i+1$，問可不可以恰$K$次後把$A$變成$B$。 隨手用python寫了一個XD 總之想法就是如果$A_i$比$B_i$小，那我們一定至少要花$B_i-A_i$次把$A_i$變成$B_i$，比較大的 case 也差不多，於是我們就有了一個基礎的下界$\sum |A_i-B_i|$，如果$K$比這個下界少，那一定不可能可以讓$A$跟$B$一樣。而若超過這個下界的話，實際上我們也可以透過一連串的$+1$跟$-1$操作來刻意浪費那些多出來的步數，所以再多判一下奇偶性就可以知道是不是一定可以有解了。(奇偶性一樣就可以靠前面說的方式構造，不同的話則因為我們每一步對應的奇偶性都是固定的，所以不同則一定構不出來) n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) s = 0 for i in range(n): s += abs(a[i] - b[i]) print("Yes" if s <= k and s % 2 == k % 2 else "No")
閱讀完整內容