[TIOJ] 1948. 小向的試煉 2-1：洞穴(Cave)

題目連結:http://tioj.infor.org/problems/1948
首先可以發現反彈其實就是兩個人交換工作而已，所以其實時間不會改變，再來就是若由左到右有abc三人，則a或c一定比b早出來，甚至ac都出來了，b才出來，由這兩個性質可以$O(1)$得出是誰先出來的，只要先對位置排序，然後從左往右掃紀錄往左的人，並從右往左掃，紀錄往右的人，然後每次比他們兩個最外面的那個人的距離如果右邊比較小，則讓整個隊列右邊的人出去(代表是他幫忙做完事情)，反之亦然，直到整串隊伍剩下一個人為止，它就是最晚出來的那個 
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define N 1000000
#define xianL 0
#define xianR 1

struct dg{
	lld pos,xian,id;
};
dg dragon[N + 5];
bool cmp(dg a,dg b){return a.pos<b.pos;}

int main(){
	lld n,l;
	scanf("%lld%lld",&n,&l);
	for(int i=0;i<n;i++){
		scanf("%lld%lld",&dragon[i].pos,&dragon[i].xian);
		dragon[i].id=i;
	}
	sort(dragon,dragon+n,cmp);
	queue<lld> ll,rr;
	for(int i=0;i<n;i++)
		if(dragon[i].xian==xianL)ll.push(dragon[i].pos);
	for(int i=n-1;i>=0;i--)
		if(dragon[i].xian==xianR)rr.push(l-dragon[i].pos);
	int dgL=0,dgR=n-1;
	while(dgR!=dgL){
		if(ll.empty()){
			dgR--;
			rr.pop();
		}else if(rr.empty()){
			dgL++;
			ll.pop();
		}else{
			if(rr.front()<ll.front()){
				dgR--;
				rr.pop();
			}else{
				dgL++;
				ll.pop();
			}
		}
	}
	printf("%lld",dragon[dgR].id);
	return 0;
}

留言

張貼留言

這個網誌中的熱門文章

[TIOJ] 1094. C.幼稚國王的獎賞

題目連結: http://tioj.infor.org/problems/1094 這題有三種作法，一種是我看完馬上想到的砍半枚舉後套trie #include <bits/stdc++.h> using namespace std; const int LOG_C = 20; const int N = 30 + 5; inline int two(int x){return 1<<x;} class Trie{ private: static constexpr int MEM = 5000000; struct node{ int lc, rc; node(): lc(0), rc(0){} } nodes[MEM]; int mem_, root; inline int new_node(){ assert(mem_ < MEM); nodes[mem_] = node(); return mem_++; } void insert(int x, int& cur, int d){ if(!cur) cur = new_node(); if(d == -1) return; if(x & two(d)) insert(x, nodes[cur].rc, d-1); else insert(x, nodes[cur].lc, d-1); } int query(int x, int cur, int d){ if(d == -1) return 0; if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); int ret = 0; if(nodes[cur].rc) ret = query(x, nodes[cur].rc, d-1) + two(d); else ret = query(x, nodes[cur].lc, d-1); if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); return ret; } public: void init(){
閱讀完整內容

[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
閱讀完整內容

[IOJ] 19. 啦啦啦

題目連結: http://ioj.infor.org/problems/19 因為$xor$有神奇(?的性質$a \oplus b = c \Longrightarrow a \oplus c = b$，所以就$O(n)$掃過去建好表，再$O(n)$掃一遍加起來，值得注意的是因為$a \oplus 0 = a$，所以若$x=0$，那要再減掉所有數的個數(自己不能算) #include <stdio.h> void gn(int &_){ _=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar(); } int MiccWan[100000 + 10]; int wayneTu[1000000 + 10] = {0}; int main(){ int t,x; long long edisonhello=0; gn(t);gn(x); for(int i=0;i<t;i++){ gn(MiccWan[i]); wayneTu[MiccWan[i]^x]++; } for(int i=0;i<t;i++){ edisonhello+=wayneTu[MiccWan[i]]; } if(x==0) edisonhello-=t; printf("%lld",edisonhello>>1); return 0; }
閱讀完整內容