[TOC]
# 8/5 A - Environment-Friendly Travel
::: spoiler
[連結](https://codeforces.com/gym/102501/problem/A)
找出路程低於B的情況下，排放最少co2的排放量。

#include<iostream>
#include<Math.h>
#include<vector>
#include<set>
using namespace std;
#define mp make_pair
typedef pair<int,pair<int,int>> PIII;
#define F first
#define S second

struct Point {
    //cost是路程不是co2排放量
    int x=-1,y=-1,cost=0;
    bool vis;
    vector<pair<int,int> > go_co2;
};

int dis(Point a, Point b) {
	return ceil(sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)));
}

int T,N,B,co2[101];
Point home,des,tans[10001];
//pq拿來做Dijkstra
set<PIII> pq;
vector<PIII> edge;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin>>home.x>>home.y;
	cin>>des.x>>des.y;
	cin>>B>>co2[0]>>T;
	for(int i=1;i<=T;i++) cin>>co2[i];
	
	cin>>N;
	for(int i=0;i<N;i++) {
		int num;
		cin>>tans[i].x>>tans[i].y>>num;
		for(int j=0;j<num;j++) {
			int to,way;
			cin>>to>>way;
			//先把邊存起來，之後等座標位置輸入完後再順便算co2的排放量
			edge.push_back(mp(co2[way],mp(i,to)));
		}
	}
	//我把第N個車站當目的地
	tans[N].x=des.x;
	tans[N].y=des.y;
	
	//把紀錄的邊都放進去
	for(PIII it:edge) {
		int cost=it.F,a=it.S.F,b=it.S.S;
		tans[a].go_co2.push_back(mp(b,cost*dis(tans[a],tans[b])));
		tans[b].go_co2.push_back(mp(a,cost*dis(tans[a],tans[b])));
	}
	//再給每個車站連一條開車到目的地的邊
	for(int i=0;i<N;i++) {
		tans[i].go_co2.push_back(mp(N,co2[0]*dis(tans[i],tans[N])));
	}
	
	//把從家裡開車到每個車站或目的地的路程放進pq，超過B就不放
	for(int i=0;i<=N;i++) {
		int d=dis(home,tans[i]);
		if(d <= B) {
			pq.insert(mp(d*co2[0],mp(d,i)));
		}
	}
	
	//開始Dijkstra
	while(!pq.empty()) {
		//如果走到目的地
		if(pq.begin()->S.S==N) {
			cout<<pq.begin()->F;
			return 0;
		}
		//<int,<int,int>> 是 <co2排放量,<路程,目前所在車站index>>
		int co2=pq.begin()->F,index=pq.begin()->S.S,d=pq.begin()->S.F;
		pq.erase(pq.begin());
		//p是目前車站
		Point &p=tans[index];
		//如果之前曾經看過這個車站，代表之前的排放量較小，這時如果連路程都比之前多那就不用考慮
		//如果路程較小，有可能排放量低的被路程太大給卡住，這時就可以排放量較大但是路程小的再考慮一次
		if(p.vis && d>=p.cost) continue;
		//紀錄路程
		p.cost=d;
		p.vis=true;
		
		
		for(auto i:p.go_co2) {
			int to=i.first,cost=i.second;
			int newd=d+dis(p,tans[to]), newco2=co2+cost;
			//如果條件不符，代表就算朝目的地直走也太遠，所以不用考慮，
			if(newd + dis(tans[to],des) <= B) {
				pq.insert(mp(newco2,mp(newd,to)));
			}
		}
	}
	//出來的話就是沒辦法走到
	cout<<-1;
	return 0;
}

:::
# 8/5 K - Birdwatching
::: spoiler
[連結](https://codeforces.com/gym/102501/problem/K)
設點I能直接通往點T且沒有辦法不經過(I,T)邊而前往點T
找出所有I

#include<iostream>
#include<vector>
using namespace std;

struct Node {
	//back紀錄的是會通往此點的點index
	vector<int> back;
	//若circle為true則代表點有一環同時經過此點和點vis_by
	bool circle=false;
	int vis_by=-1;
}node[100000];

int N,M,T;
//用來記錄走過的點，方便設circle
vector<int> through;

//from是出發點，x是目前點
void dfs(int from,int x) {
	//當此點被走過且不是繞一個圈
	if(from != x && node[x].vis_by!=-1) {
		int origin=node[x].vis_by;
		//當此點不是由此次的出發點經過，且經過的那點和這點有環
		//就可以從點from到x再順著環到origin
		//其他情況代表此點被走過，不用再走
		if(from!=origin && node[origin].vis_by==-1 && node[x].circle) {
			node[origin].vis_by=from;
		} else {
			return;
		}
	}
	
	//當繞了一個圈
	if(from == x) {
		//畫環
		for(int i:through) {
			node[i].circle=true;
		}
		return;
	}else {
		//代表出發點可以走到此點
		node[x].vis_by=from;
	}
	
	for(int to:node[x].back) {
		//不用管T
		if(T == to) continue;
		through.push_back(to);
		dfs(from,to);
		through.pop_back();
	}
	return;
}

int main() {
	cin>>N>>M>>T;
	for(int i=0;i<M;i++) {
		int from,to;
		cin>>from>>to;
		//倒過來存
		node[to].back.push_back(from);
	}
	
	//從每個會走到T的點
	for(int i:node[T].back) {
		//從每個會走到的點
		for(int j:node[i].back) {
			//不用管T
			if(j==T) continue;
			through.clear();
			dfs(i,j);
		}
	}
	
	vector<int> ans;
	for(int i:node[T].back) {
		//沒被走過的會保留初始值
		if(node[i].vis_by==-1) ans.push_back(i);
	}
	cout<<ans.size()<<endl;
	for(int i:ans) cout<<i<<endl;
	
	return 0;
}

:::
# 8/12 A. Find a Number
::: spoiler
[連結](https://codeforces.com/contest/1070/problem/A)
找出可被d整除且位數總和為s的最小正整數

#include<iostream>
#include<queue>
using namespace std;

//mod是當前數字%D的結果，cnt是位數和
struct Str{
	int mod,cnt;
	string s;
	Str(int m,int n,string str) {
		mod=m;
		cnt=n;
		s=str;
	} 
};

int D,S;
//用來確保較小的數字先出來
queue<Str> q;
//因為較小的數會先考慮，所以之後出現的數如果mod和cnt都相同，那就不用考慮
bool visit[501][5001];

int main() {
	cin>>D>>S;
	//初始化
	for(int i=0;i<=D;i++) {
		for(int j=0;j<=S;j++) {
			visit[i][j]=false;
		}
	}
	
	q.push(Str(0,0,""));
	//如果可能性都考慮完了，就代表不可能存在，輸出-1
	while(!q.empty()) {
		Str &x = q.front();
		//條件成立
		if(x.mod==0 && x.cnt==S) {
			cout<<x.s;
			return 0;
		}
		
		for(int i=0;i<=9;i++) {
			//因為要確保從小的開始考慮，所以新數字會放在個位
			int cnt = x.cnt+i, mod = (x.mod*10+i)%D;
			//把不合條件或已經遇過的去掉
			if(cnt <= S && !visit[mod][cnt]) {
				q.push(Str(mod,cnt,x.s+char('0'+i)));
				visit[mod][cnt]=true;
			}
		}
		q.pop();
	}
	cout<<-1;
	
	return 0;
}

:::
# 8/12 C. Cloud Computing
::: spoiler
[連結](https://codeforces.com/contest/1070/problem/C)
給天數，需要的CPU數，方案數，找到最便宜且盡量買滿需求CPU的總花費

#include<iostream>
#include<vector>
#define ll long long int
using namespace std;
//其實也可以用pair<ll,ll>
struct CPU{
	ll price=0,num=0;
	CPU(){};
	CPU(ll c,ll p) {
		price=p;
		num=c;
	}
};
int N,K,M;
//op的index是每個方案的開始提供日期，ed的index是結束日期+1
vector<CPU> op[1000002],ed[1000002];
//tree是紀錄總和的線段樹
CPU tree[4*1000002];
//輸出
ll ans=0;
//l跟r代表價錢，把數量和價錢存入線段樹
void add(int index,int l,int r,ll c,ll p) {
	tree[index].num += c;
	tree[index].price += c * p;
	//l==r代表已經跑到最底了
	if(l==r) return;
	int m=(l+r)/2;
	//p<=m代表要往左邊存，反之往右邊存
	if(p<=m) {
		add(index*2,l,m,c,p);
	} else {
		add(index*2+1,m+1,r,c,p);
	}
}
//找到最便宜的價錢
void go(int index,int l,int r,ll need) {
	//需求大於供給，所以全買了
	if(tree[index].num <= need) {
		ans += tree[index].price;
		return;
	}
	//l==r代表買不完r元的cpu，所以只買需要的量
	if(l==r) {
		ans+= l*need;
		return;
	}
	int m=(l+r)/2;
	//先買便宜的
	go(index*2, l, m, need);
	//不夠再買貴的
	if(tree[index*2].num <need) {
		go(index*2+1, m+1, r, need - tree[index*2].num);
	}
}

int main() {
	cin>>N>>K>>M;
	
	for(int i=0;i<M;i++) {
		int from,to,c,p;
		cin>>from>>to>>c>>p;
		op[from].push_back(CPU(c,p));
		ed[to+1].push_back(CPU(c,p));
	}
	//依序計算每天的花費
	for(int i=1;i<=N;i++) {
		//把每天新增可用的方案加進線段樹
		for(CPU cpu:op[i]) add(1, 1, 1000000, cpu.num, cpu.price);
		//把每天過期不可用的方案移除線段樹
		for(CPU cpu:ed[i]) add(1, 1, 1000000, -cpu.num, cpu.price);
		//計算花費
		go(1,1,1000000,K);
	}
	
	cout<<ans;
	return 0;
}

:::
# 8/12 E. Getting Deals Done
::: spoiler
[連結](https://codeforces.com/contest/1070/problem/E)
每做m件任務需要休息前之前做的m件任務花費時間總和，最多只能花t時間
超過t時間時，接下來的任務都不需考慮
輸出x,d代表只選擇花費d時間以下(含)的任務做，可做x件，找出x最大的情況

#include<iostream>
#include<set>
#include<vector>
#define ll long long int
using namespace std;
ll C,N,M,T,cases[200000];
set<int> st;
vector<int> vec;
pair<int,int> ans;

//計算在d=x下的情況
bool check(int x) {
	// 累計時間 累計工作數 休息計數器 休息時間計數器
	ll time=0,work=0,num=0,need_break=0;
	for(int i=0;i<N;i++) {
		//超過d不考慮
		if(cases[i]>x) continue;
		
		//因為最後一次工作後可以不休息
		//所以當成工作前才考慮休息就可以了
		if(num==M) {
			time+=need_break;
			need_break=0;
			num=0;
		}
		
		need_break+=cases[i];
		time+=cases[i];
		num++;
		
		//時間超過時後面不考慮
		if(time<=T) {
			work++;
		} else {
			break;
		}
	}
	//選較好的答案
	if(ans.first < work) ans = make_pair(work,x);
	
	//如果時間用完代表d太大了，反之則太小
	if(time>T) return false;
	else return true;
}
//二分搜
void two(int l, int r) {
	
	int m=(l+r)/2;
	//搜到底了
	if(l==r) {
		//怕沒搜乾淨
		check(vec[m]);
		return;
	}
	
	
	if(check(vec[m])) {
		two(m+1,r);
	} else {
		//感覺m-1也可以，只是到底的條件可能要改成r<=l
		two(l,m);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>C;
	while(C--) {
		cin>>N>>M>>T;
		ans=make_pair(-1,-1);
		vec.clear();
		st.clear();
		for(int i=0;i<N;i++) {
			cin>>cases[i];
			//大於T的不可能做得完
			if(cases[i] <= T) st.insert(cases[i]);
		}
		for(int i:st) vec.push_back(i);
		
		if(!vec.empty()) two(0,vec.size()-1);
		
		if(ans.first==0 || ans.first==-1) {
			//當-1或0時代表選1~T當d都只能完成0個任務
			cout<<0<<" "<<T<<endl;
		} else {
			cout<<ans.first<<" "<<ans.second<<endl;
		}
	}
	
	return 0;
}

:::
# 8/12 G. Monsters and Potions
::: spoiler
[連結](https://codeforces.com/contest/1070/problem/G)
給一排橫向排列的格子，格子有空地、怪獸、恢復藥三種，其中英雄可能會在空地上
英雄血量小於0時，英雄死亡
求一個集合點，並且以特定順序移動英雄至集合點，使所有英雄不死亡並到達集合點

#include<iostream>
#include<deque>
using namespace std;

int N,M,board[101];
//index是所在位置 first是hp second是英雄的編號
pair<int,int> hero[101];
//用來記錄命令順序
deque<int> ld,rd;

int main() {
	cin>>N>>M;
	for(int i=0;i<=N;i++) hero[i]=make_pair(-1,-1);
	for(int i=1;i<=M;i++) {
		int p,h;
		cin>>p>>h;
		hero[p]=make_pair(h,i);
	}
	for(int i=1;i<=N;i++) {
		cin>>board[i];
	}
	
	//l是最右邊的左側英雄能平安抵達的集合點，r是最左邊的右側
	//mxhp代表當前可能最高血量
	int l=-1,r=N+1,mxhp=-1;
	for(int i=1;i<=N;i++) {
		//代表這格有英雄
		if(board[i] == 0 && hero[i].first != -1) {
			//讓血量高的先出動
			if(mxhp < hero[i].first ) ld.push_front(hero[i].second);
			else ld.push_back(hero[i].second);
			//取血量最高者
			mxhp = max(mxhp,hero[i].first);
		}
		//代表還沒找到第一個英雄
		if(mxhp == -1) continue;
		
		if(board[i] != 0) {
			mxhp+=board[i];
			//英雄死亡
			if(mxhp < 0) {
				break;
			}
		}
		//代表走得到這一格
		l=i;
	}
	mxhp=-1;
	for(int i=N;i>=0;i--) {
		if(board[i] == 0 && hero[i].first != -1) {
			if(mxhp < hero[i].first ) rd.push_front(hero[i].second);
			else rd.push_back(hero[i].second);
			mxhp = max(mxhp,hero[i].first);
		}
		if(mxhp == -1) continue;
		
		if(board[i] != 0) {
			mxhp+=board[i];
			if(mxhp < 0) {
				break;
			}
		}
		r=i;
	}
	//如果左邊的極限和右邊的極限能夠相接，那就有解
	if(r <= l+1) {
		cout<<l<<endl;
		bool vis[101];
		for(int i=0;i<=M;i++) vis[i]=false;
		for(int i:ld) {
			vis[i]=true;
			cout<<i<<" ";
		}
		for(int i:rd) {
			//因為一位英雄只能移動一次
			if(!vis[i]) cout<<i<<" ";
		}
	} else {
		cout<<-1;
	}
	return 0;
} 

:::
# 9/2 A. Augmented Reality Game
::: spoiler
[連結](https://codeforces.com/gym/100257)
給N個點的鑰匙數量(鑰匙可建立一條與其他點的通道)
求最多可產生多少個三角形(三角形的邊不能重複使用，但是同樣的三角形可以有多個)

#include<iostream>
using namespace std;
int N;
int main() {
	cin>>N;
	//sum是鑰匙總數 mx是單點鑰匙的最大值
	int sum=0,mx=-1;
	for(int i=0;i<N;i++) {
		int k;
		cin>>k;
		mx = max(mx,k);
		sum += k;
	}
	//此時無法組成三角形
	if(N==1 || N==2) cout<<0;
	//因為每2 1 0個鑰匙可組一個三角形，所以檢查最多鑰匙的點能否用光鑰匙
	else if(mx <= (sum-mx)*2) cout<<(sum/3);
	//用不完
	else cout<<(sum-mx);
	
	return 0;
}

:::
# 9/2 F. Four Ways to Travel
::: spoiler
[連結](https://codeforces.com/gym/100257)
地上運輸(S)26元，地下運輸(U)28元，
90分鐘內無限地上運輸+1次地下運輸套餐44元
機器會自動查看90分鐘內的紀錄並在使用套餐能省錢時自動使用
求機器判斷所花的錢跟可能的最小值

#include<iostream>
using namespace std;
//d是用來dp的 ans1是機器的 ans2是最佳的
int N,d[60*24+1],keep[60*24],ans1=0,ans2;
int main() {
	cin>>N;
	for(int i=0;i<60*24;i++) {
		keep[i] = -1;
		d[i] = 1e9;
	}
	d[60*24]=1e9;
	d[0]=0;
	for(int i=0;i<N;i++) {
		string s;
		cin>>s;
		//h是時 m是分
		int h = stoi(s.substr(0,s.find(":"))), m = stoi(s.substr(s.find(":")+1,s.size()));
		
		cin>>s;
		//-1代表沒有 0代表地上 1代表地下
		if(s=="S") keep[h*60+m] = 0;
		else if(s=="U") keep[h*60+m] = 1;
	}
	
	//use=-1代表無使用套餐,否則代表結束時間
	int use = -1;
	//subway代表目前套餐有沒有搭過地下運輸
	bool subway = false;
	for(int i=0;i<60*24;i++) {
		//套餐過期
		if(use != -1 && use < i) {
			use = -1;
			subway = false;
		}
		//地上
		if(keep[i] == 0) {
			if (use == -1) {
				bool y=false;
				for(int j=1;j<=90 && i+j<60*24;j++) {
					if(keep[i+j] != -1) y=true;
				}
				//用了會省錢的話就用
				if(y) {
					ans1 += 44;
					use = i+90;
				} else ans1 += 26;
			}
		} else if(keep[i] == 1) {
			//還沒用套餐
			//或套餐還有搭過地下運輸，代表套餐在此刻結束
			if (use == -1 || subway) {
				bool y=false;
				for(int j=1;j<=90 && i+j<60*24;j++) {
					if(keep[i+j] == 1) break;
					else if(keep[i+j] == 0) y=true;
				}
				
				if(y) {
					ans1 += 44;
					use = i+90;
					subway = true;
				} else {
					ans1 += 28;
				}
			} else subway = true;
		}
	}
	
	//d[i]代表0~i-1的時間內最少花多少錢
	for(int i=0;i<60*24;i++) {
		//因為是0~i-1，所以是i+91
		//count是紀錄地下運輸次數 k是如果使用套餐可以更新到的最遠處
		int k = min(60*24,i+91),count=0,add=0;
		for(int j=0;j<=90 && i+j<=60*24;j++) {
			if(keep[i+j] == 1) count++;
			if(count == 2) {
				k=i+j;
				break;
			}
		}
		
		if(keep[i] == 0) add=26;
		else if(keep[i] == 1) add=28;
		//不用套餐
		d[i+1] = min(d[i+1],d[i]+add);
		//用套餐
		d[k] = min(d[k],d[i]+44);
	}
	ans2 = d[60*24];
	cout<<ans1<<" "<<ans2;
	return 0;
}

:::
# 9/2 K. Top K Elements
::: spoiler
[連結](https://codeforces.com/gym/100257)
根據xi = (A · xi−2 + B · xi−1 + C) mod 2^31取得所有x
然後輸出前K大的x

#include<iostream>
#include<algorithm>
#include<vector> 
using namespace std;
//MOD用來mod2^31 mask1用來取前16bits mask2用來取後16bits
unsigned int MOD = (1LL<<31)-1,mask1 = (1LL<<32) - (1LL<<16),mask2 = (1LL<<16)-1;
//front是第K個數的前16bits back是第K個數的後16bits
//keep用來計數
unsigned int N,K,A,B,C,pre,prepre,keep[1<<16],front,back;
vector<unsigned int> ans;

int main() {
	cin>>N>>K>>prepre>>pre>>A>>B>>C;
	
	int p=pre,pp=prepre;
	for(int i=0;i<(1<<16);i++) keep[i]=0;
	for(int i=0;i<N;i++) {
		//if(i%1000000 == 0) cout<<i<<endl;
		unsigned int x = (A*pp) + (B*p) + C;
		x &= MOD;
		pp = p;
		p = x;
		
		x = (x & mask1) >> 16;
		keep[x]++;
	}
	int sum=0,tmp;
	//求第K個數的前16bits
	for(int i=(1<<16)-1;i>=0;i--) {
		sum += keep[i];
		if(sum >= K) {
			front = i<<16;
			tmp = sum - keep[i];
			break;
		}
	}
	
	p=pre,pp=prepre;
	for(int i=0;i<(1<<16);i++) keep[i]=0;
	for(int i=0;i<N;i++) {
		
		unsigned int x = (A*pp) + (B*p) + C;
		x &= MOD;
		pp = p;
		p = x;
		
		if((x & mask1) == front) keep[x & mask2]++;
	}
	sum=tmp;
	//求第K個數的後16bits
	for(int i=(1<<16)-1;i>=0;i--) {
		sum += keep[i];
		if(sum >= K) {
			back = i;
			break;
		}
	}
	
	////第K個數=front+back;
	p=pre,pp=prepre;
	for(int i=0;i<N;i++) {
		unsigned int x = (A*pp) + (B*p) + C;
		x &= MOD;
		pp = p;
		p = x;
		
    	//大於的丟進去
		if(x > front+back) ans.push_back(x);
	}
	//要排序
	sort(ans.rbegin(),ans.rend());
	for(int i:ans) cout<<i<<" ";
	//補上不夠的
	for(int i=ans.size();i<K;i++) cout<<front+back<<" ";
	return 0;
}

:::
# XX/XX XX
::: spoiler
[連結]()

:::