# 第一週:Data structure
題目:[大善人老闆救濟東南亞兒童](https://neoj.sprout.tw/problem/19/)`
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,a;
cin>>n;
int arr[n];
for(int i=1; i<=n; i++){
arr[i-1]=i;
}
int ans[n];
for(int i=0; i<n; i++){
cin>>a;
ans[i]=a;
}
stack<int> st;
int k=0;
for(int i=0; i<n; i++){
if(arr[i]==ans[k]){
k++;
}
else if(arr[i]!=ans[k]){
st.push(arr[i]);
}
while(!st.empty() and ans[k]==st.top()){
st.pop();
k++;
}
}
if(k==n){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
}
}
```
題目:[中國人排隊問題](https://neoj.sprout.tw/problem/20/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
#define x first
#define y second
using namespace std;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t,r=1;
cin>>t;
while(t--){
vector<int> vec(1000001,0);
int n;
cin>>n;
for(int i=1; i<=n; i++){
int k;
cin>>k;
for(int j=0; j<k; j++){
int o;
cin>>o;
vec[o]=i;
}
}
vector<queue<int>> v(n+5);
int m,p=0,e=0;
cin>>m;
cout<<"Line #"<<r<<endl;
r++;
int arr[n+5]={};
queue<int> q;
while(m--){
string s;
int a;
cin>>s;
if(s=="ENQUEUE"){
cin>>a;
if(!arr[vec[a]] or vec[a]==0){
q.push(vec[a]);
arr[vec[a]]=1;
}
v[vec[a]].push(a);
}
if(s=="DEQUEUE"){
long long tmp=q.front();
cout<<v[tmp].front()<<endl;
v[tmp].pop();
if(v[tmp].empty() or tmp==0){
q.pop();
arr[tmp]=0;
}
}
}
}
}
```
題目:[陸行鳥大賽車](https://neoj.sprout.tw/problem/21/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
#define x first
#define y second
using namespace std;
int main(){
int n;
cin>>n;
int m;
cin>>m;
map<int,int> player;
map<int,int> ord;
for(int i=1; i<=n; i++){
player[i]=i,ord[i]=i;
}
while(m--){
int a,b;
cin>>a>>b;
if(a==0){
ord.erase(player[b]);
player.erase(b);
}
else{
auto now = ord.find(player[b]);
if(now==ord.begin()) continue;
auto pre=prev(now,1);
int tmp=now->y;
now->y=pre->y;
pre->y=tmp;
player[now->y]=now->x;
player[pre->y]=pre->x;
}
}
for(auto p=ord.begin(); p!=ord.end(); p++){
if(p!=ord.begin()){
cout<<" ";
}
cout<<p->y;
}
cout<<endl;
}
```
題目:[stack 練習](https://neoj.sprout.tw/problem/36/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int main(){
int t;
cin>>t;
stack<int> st;
while(t--){
int a;
cin>>a;
if(a==1){
int b;
cin>>b;
st.push(b);
}
else if(a==2){
if(!st.empty()){
cout<<st.top()<<endl;
st.pop();
}
else{
cout<<"empty!"<<endl;
}
}
}
}
```
題目:[queue 練習](https://neoj.sprout.tw/problem/37/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin>>t;
queue<int> st;
while(t--){
int a;
cin>>a;
if(a==1){
int b;
cin>>b;
st.push(b);
}
else if(a==2){
if(!st.empty()){
cout<<st.front()<<endl;
st.pop();
}
else{
cout<<"empty!"<<endl;
}
}
}
}
```
# 第二週:Complexity、Tree
題目:[二元搜尋樹](https://neoj.sprout.tw/problem/48/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct node{
int val=0;
node *lc;
node *rc;
};
node *root=nullptr;
void insert(int x,node *&root){
if(root == nullptr){
root = new node;
root -> val=x;
root -> lc = nullptr;
root -> rc = nullptr;
}
else if(x < root->val ){
insert(x,root->lc);
}
else{
insert(x,root ->rc);
}
}
void dfs(node *&root){
if(root==nullptr) return;
dfs(root->lc);
dfs(root->rc);
cout<<root->val<<endl;
}
int main(){
int n;
cin>>n;
while(n--){
int a;
cin>>a;
insert(a,*&root);
}
dfs(*&root);
}
```
題目:[1d-kd-tree](https://neoj.sprout.tw/problem/47/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
#define f first
#define s second
using namespace std;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
map<int,int> mp;
int n;
cin>>n;
while(n--){
string s;
int a;
cin>>s>>a;
if(s=="insert"){
mp[a]=a;
}
else if(s=="delete"){
mp.erase(a);
}
else if(s=="query"){
auto k=mp.lower_bound(a);
auto pre=prev(k,1);
int c=abs((k->s)-a),b=abs((pre->s)-a);
if(c==b){
if(k->s<pre->s){
cout<<k->s<<" "<<pre->s<<endl;
}
else{
cout<<pre->s<<" "<<k->s<<endl;
}
}
else if(c>b){
cout<<pre->s<<endl;
}
else{
cout<<k->s<<endl;
}
}
}
}
```
# 第三週: Flood fill、Heap、Basic graph
題目:[庭院裡的水池](https://neoj.sprout.tw/problem/42/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct nape{
int x;
int y;
int len;
};
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
queue<nape> q;
int n,m,a=0,b=0;
cin>>n>>m;
char t[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin>>t[i][j];
}
}
int c=0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if (t[i][j]=='#') continue;
c++;
nape tmp;
tmp.len=0;
tmp.x=j;
tmp.y=i;
q.push(tmp);
while(!q.empty()){
nape cur=q.front();
q.pop();
if(t[cur.y][cur.x]=='#') continue;
t[cur.y][cur.x]='#';
cur.len++;
tmp.len=cur.len;
for(int i=0; i<4; i++){
tmp.x=cur.x+dx[i];tmp.y=cur.y+dy[i];
if(tmp.x<m and tmp.y<n and tmp.x>=0 and tmp.y>=0 and t[tmp.y][tmp.x]!='#'){
q.push(tmp);
}
}
}
}
}
cout<<c<<endl;
}
}
```
題目:[喵喵抓老鼠](https://neoj.sprout.tw/problem/44/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct nape{
int x;
int y;
int len;
};
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
queue<nape> q;
int n,m,a=0,b=0;
cin>>n>>m;
char t[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin>>t[i][j];
if(t[i][j]=='K'){
a=i;
b=j;
}
}
}
nape tmp;
tmp.len=0;
tmp.x=b;
tmp.y=a;
int c=0;
q.push(tmp);
while(!q.empty()){
nape cur=q.front();
if(t[cur.y][cur.x]=='@'){
cout<<cur.len<<endl;
c++;
break;
}
q.pop();
if(t[cur.y][cur.x]=='#') continue;
t[cur.y][cur.x]='#';
cur.len++;
tmp.len=cur.len;
for(int i=0; i<4; i++){
tmp.x=cur.x+dx[i];tmp.y=cur.y+dy[i];
if(tmp.x<m and tmp.y<n and tmp.x>=0 and tmp.y>=0 and t[tmp.y][tmp.x]!='#'){
q.push(tmp);
}
}
}
if(c==0){
cout<<"= =\""<<endl;
}
}
}
```
題目:[heap 練習](https://neoj.sprout.tw/problem/59/)
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin>>n;
priority_queue<int> pq;
while(n--){
int a;
cin>>a;
if(a==1){
int b;
cin>>b;
int c=-b;
pq.push(c);
}
if(a==2){
if(!pq.empty()){
int e=-pq.top();
cout<<e<<endl;
pq.pop();
}
else{
cout<<"empty!"<<endl;
}
}
}
}
```
# 第四週: Enumeration
題目:[Lotto](https://neoj.sprout.tw/problem/63/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
vector<int> v;
void dfs(vector<bool> &u, int cur=0, int cnt=0){
int vz=v.size();
if(cur>vz) return;
if(vz-cur<6-cnt) return;
if(cnt==6){
int i=0,e=0;
for(;i<vz; i++){
if(u[i]){
cout<<v[i];
e++;
if(e<=5) cout<<" ";
}
}
cout<<endl;
return;
}
u[cur]=1;
dfs(u,cur+1,cnt+1);
u[cur]=0;
dfs(u,cur+1,cnt);
}
int main(){
int t;
cin>>t;
while(t--){
int k;
cin>>k;
v.assign(k,0);
for(auto &i:v) cin>>i;
vector<bool> u(k,0);
dfs(u);
}
}
```
題目:[田忌賽馬](https://neoj.sprout.tw/problem/69/)
```cpp=
#include<bits/stdc++.h>
#define w 100000000
using namespace std;
long long int a[10000],b[10000],c[10000],checke[10000];
int check(int o,int u){
for(int i=0; i<u; i++) checke[i]=a[i]+b[i]*o;
sort(checke,checke+u);
long long* pos,count=0;
pos=upper_bound(checke,checke+u,c[0]);
if(pos==checke+u) return 0;
int j=pos-checke;
for(int i=0; i<u; i++){
if(j>=u) break;
while(checke[j]<=c[i] and j<u) j++;
if(j>=u) break;
j++;
count++;
}
return count;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t,rt;
cin>>t;
while(t--){
int rd=-1,n,k;
cin>>n>>k;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(int i=0; i<n; i++){
cin>>a[i]>>b[i];
}
for(int i=0; i<n; i++)cin>>c[i];
sort(c,c+n);
int l=0,r=w,m=(l+r)>>1;
while(l<=r){
rt=check(m,n);
if(rt<k) l=m+1;
else{
rd=m;
r=m-1;
}
m=(l+r)>>1;
}
cout<<rd<<endl;
}
}
```
# 第五週: Greedy
題目:[誰先晚餐](https://neoj.sprout.tw/problem/89/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
#define f first
#define s second
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,y;
cin>>y;
while(y--){
cin>>n;
if(n==0) break;
priority_queue<pair<long long ,long long> > pq;
for(int i=0; i<n; i++){
long long t,e;
cin>>t>>e;
pq.push(make_pair(e,t));
}
long long pre=0,ans=0;
while(!pq.empty()){
pre+=pq.top().s;
ans=max(ans,pre+pq.top().f);
pq.pop();
}
cout<<ans<<endl;
}
return 0;
}
```
題目:[Add all](https://neoj.sprout.tw/problem/70/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
priority_queue<long long> pq;
for(int i=0; i<n; i++){
int a;
cin>>a;
pq.push(-a);
}
long long sum=0;
while(pq.size()>1){
long long a=-pq.top();
pq.pop();
long long b=-pq.top();
pq.pop();
long long c=a+b;
sum+=c;
pq.push(-c);
}
cout<<sum<<endl;
}
}
```
# 第六週 Divide and conquer
題目:[逆序數對](https://neoj.sprout.tw/problem/125/)
```cpp=
#include<iostream>
#include<vector>
#define endl '\n'
using namespace std;
long long sum=0;
const int mod=10000019;
vector<int> vec;
inline long long merge(int l, int m, int r){
vector<int>left(vec.begin()+l,vec.begin()+m+1),right(vec.begin()+m+1,vec.begin()+r+1);
left.emplace_back(0);
right.emplace_back(0);
long long ret=0,tmp=0,c=0;
int indl=0,indr=0,sz=left.size();
for(int i=l; i<=r; i++){
if(left[indl]>=right[indr]){
if(left[indl]==right[indr]) c++;
else{
tmp=(tmp+left[indl])%mod;
vec[i]=left[indl++];
}
}
else{
vec[i]=right[indr++];
ret=(ret+tmp+(indl-c)*vec[i])%mod;
}
}
return ret%mod;
}
inline long long solve(int l,int r){
long long ret=0;
if(l<r){
int mid=(l+r)>>1;
return (solve(l,mid)+solve(mid+1,r)+merge(l,mid,r))%mod;
}
return 0;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin>>n;
vec.assign(n,0);
for(int i=0; i<n; i++){
cin>>vec[i];
}
n--;
cout<<solve(0,n)%mod<<endl;
}
```
題目:[最近點對](https://neoj.sprout.tw/problem/795/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
#define F first
#define S second
#define ll long long
using namespace std;
vector<pair<ll,ll> > v;
inline ll dis(pair<ll,ll> &a,pair<ll,ll> &b){
return (a.F-b.F)*(a.F-b.F)+(a.S-b.S)*(a.S-b.S);
}
inline ll brige(int l, int r){
long long ret=LONG_MAX;
for(int i=l; i<=r; i++){
for(int j=i+1; j<=r; j++){
ret=min(ret,dis(v[i],v[j]));
}
}
sort(v.begin()+l,v.begin()+r+1,[](pair<ll,ll> &a,pair<ll,ll> &b){
return a.S<b.S;
}
);
return ret;
}
inline ll slove(const int l,const int r){
if(r-l<=20) return brige(l,r);
const int mid=(l+r)>>1;
ll midx=v[mid].F;
ll ans=min(slove(l,mid),slove(mid+1,r)),disx=ceil(sqrt(ans));
vector<pair<ll,ll> > tmp(r-l+1);
merge(
v.begin()+l,v.begin()+mid+1,
v.begin()+mid+1,v.begin()+r+1,
tmp.begin(),[](pair<ll,ll> &a,pair<ll,ll> &b){
return a.S<b.S;
}
);
for(int i=l; i<=r; i++){
v[i]=tmp[i-l];
}
tmp.clear();
for(int i=l; i<=r; i++){
if(abs(v[i].F-midx)<disx){
tmp.push_back(v[i]);
}
}
for(int i=0; i<tmp.size(); i++){
for(int j=i+1; j<tmp.size() and tmp[j].S-tmp[i].S<(ll) ceil(sqrt(ans));j++){
ans=min(ans,dis(tmp[i],tmp[j]));
}
}
return ans;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n;
while(cin>>n){
v.resize(n);
for(auto & i : v){
cin>>i.F>>i.S;
}
sort(v.begin(),v.end());
ll o=slove(0,n-1);
cout<< o<<endl;
}
}
```
題目:[太陽軍團](https://neoj.sprout.tw/problem/127/)
```cpp=
#include<bits/stdc++.h>
using namespace std;
vector<int> ans;
void ed(int l,int r, int u, int d){
int mid=u+d>>1,pos=l,mxm=INT_MIN;
if(u>d or ans[mid]) return;
for(int i=l ;i<=r; i++){
if(GetVal(mid,i)>mxm){
pos=i,
mxm=GetVal(mid,i);
}
}
ans[mid]=pos;
if(u !=d ) {
ed(l,pos-1,u,mid-1);
ed(pos+1,r,mid+1,d);
}
}
void solve(int n,int m){
ans.assign(n+1,0);
int mid=n>>1,pos=1,mxm=INT_MIN;
for(int i=1; i<=m; i++){
if(GetVal(mid,i)>mxm){
pos=i;
mxm=GetVal(mid,i);
}
}
ans[mid]=pos;
ed(1,pos-1,1,mid-1);
ed(pos+1,m,mid+1,n);
for(int i=1; i<=n; i++){
if(!ans[i]){
pos=1;
mxm=INT_MAX;
for(int j=1; j<=m; j++){
if(GetVal(i,j)>mxm){
pos=j;
mxm=GetVal(i,j);
}
}
ans[i]=pos;
}
Report(ans[i]);
}
}
```
# 第七週:Dynamic Programming 1
題目:[円円數磁磚](https://neoj.sprout.tw/problem/138/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int mod=1000007, n=5e4+5;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t,dp[n];
cin>>t;
dp[0]=0;
dp[1]=3;
dp[2]=11;
for(int i=3; i<n; i++){
dp[i]=((dp[i-1]<<2)-dp[i-2]+mod)%mod;
}
while(t--){
int a;
cin>>a;
cout<<(a%2==1?0:dp[a>>1])<<endl;
}
}
```
題目:[取數字1](https://neoj.sprout.tw/problem/141/)
```cpp=
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int main(){
int t=0;
cin>>t;
while(t--){
int n,arr[100005];
cin>>n;
int dp[10005];
memset(dp,0,sizeof(dp));
memset(arr,0,sizeof(arr));
for(int i=1;i<=n;i++) cin>>arr[i];
dp[1] = arr[1];dp[2] = arr[2];dp[3] = arr[1]+arr[3];
for(int i=4;i<=n+1;i++){
dp[i] = max(dp[i-2],dp[i-3])+arr[i];
}
cout<<max(dp[n],dp[n-1])<<endl;
}
}
```
# 第八週: 第一階段認證考
# 第九週: Dynamic Programming 2
題目:[高棕櫚農場](https://neoj.sprout.tw/problem/157/)
```cpp=
#include <bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
int t;
cin>>t;
while(t--){
long long n, lim, vol[105];
cin >> n >> lim;
long long val[100005], dp[100005];
for(int i=1; i<=n; i++) cin>>val[i]>>vol[i];
memset(dp,INF,sizeof(dp));
dp[0]=0;
for(int i=1; i<=n; i++)
for (int j = 10000; j >=vol[i]; j--)
dp[j] = min(dp[j], dp[j-vol[i]] + val[i]);
long long ans=0;
for(int i=0; i<=10000; i++)
if(dp[i]<=lim and i>ans) ans=i;
cout<<ans<<endl;
}
}
```
題目:[高棕櫚農場2](https://neoj.sprout.tw/problem/158/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t;
cin>>t;
while(t--){
int n,m,k;
cin>>n>>m>>k;
int v[105],w[10005];//v=價值 w=重量
for(int i=1; i<=n; i++) cin>>w[i]>>v[i];
int dp[1005][105];
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; i++)
for(int j=m; j>=w[i];j--)
for(int l=1; l<=k; l++)
dp[j][l]=max(dp[j][l],dp[j-w[i]][l-1]+v[i]);
cout<<dp[m][k]<<endl;
}
}
```
題目:[玩電梯](https://neoj.sprout.tw/problem/416/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int mod=1e9+7;
long long n,a,b,k,dp[2][2005];
inline int modd(int x){
return (x%mod+mod)%mod;
}
inline void mix(long long l,long long r,long long v,long long id){
l=max(l,(long long)1);
r=min(r,n);
dp[(id+1)&1][l]=modd(dp[(id+1)&1][l]+v);
dp[(id+1)&1][r+1]=modd(dp[(id+1)&1][r+1]-v);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin>>n>>a>>b>>k;
dp[0][a]=1;
for(int i=0; i<k; i++){
for(int j=1; j<=n; j++){
long long d=abs(b-j)-1;
mix(j-d,j-1,dp[i&1][j],i);
mix(j+1,j+d,dp[i&1][j],i);
}
for(int j=1; j<=n; j++){
dp[(i+1)&1][j]+=dp[(i+1)&1][j-1];
dp[(i+1)&1][j]=modd(dp[(i+1)&1][j]);
}
for(int j=1; j<=n; j++) dp[(i)&1][j]=0;
}
long long ans=0;
for(int i=1; i<=n; i++){
ans+=dp[k&1][i];
ans=modd(ans);
}
cout<<ans<<endl;
}
```
題目:[取名字好困難QQ](https://neoj.sprout.tw/problem/421/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
constexpr int mod=1e9+7;
inline void solve(){
int n,m;
cin>>n>>m;
vector<long long> vec;
for(int i=0; i<n; i++){
long long tmp;
cin>>tmp;
if((tmp<<1)<m) continue;
else if(tmp<m){
tmp<<=1;
vec.push_back(tmp);
}
else{
vec.push_back(tmp<<1);
vec.push_back(tmp);
}
}
if(vec.size()<1){
cout<<0<<endl;
return;
}
vector<long long> lis;
long long len=vec.size();
lis.push_back(vec[0]);
for(int i=1; i<len; i++){
if(lis.back()<=vec[i])
lis.push_back(vec[i]);
else *upper_bound(lis.begin(),lis.end(),vec[i])=vec[i];
}
cout<<lis.size()<<endl;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t;
cin>>t;
while(t--)
solve();
}
```
# 第十週: Geometry
題目:[向量加法](https://neoj.sprout.tw/problem/398/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const double eps=1e-15;
bool f(long double x,long double y,long double z){
if(fabs((x+y)-z)<=eps) return true;
return false;
}
int main(){
int n,cnt=0;
cin>>n;
long double arr[n];
for(int i=0; i<n; i++) cin>>arr[i];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
for(int k=0; k<n; k++){
if(f(arr[i],arr[j],arr[k])==true)
cnt++;
}
}
}
cout<<cnt<<endl;
}
```
題目:[等長線段對](https://neoj.sprout.tw/problem/399/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
map<long long,long long> mp;
inline long long distance(pair<long long,long long> x,pair<long long,long long> y){
return (x.first-y.first)*(x.first-y.first)+(x.second-y.second)*(x.second-y.second);
}
int main(){ ios::sync_with_stdio(0);cin.tie(0);
long long n,cnt=0;
cin>>n;
vector<pair<long long,long long> > v(n);
for(int i=0; i<n; i++) cin>>v[i].first>>v[i].second;
for(int i=0; i<v.size()-1; i++)
for(int j=i+1; j<v.size(); j++)
mp[distance(v[i],v[j])]++;
for(auto i:mp){
if(i.second>=2){
cnt+=(i.second*(i.second-1)/2);
}
}
cout<<cnt<<endl;
}
```
題目:[向左轉向右轉](https://neoj.sprout.tw/problem/400/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
#define pii pair<int,int>
#define int long long
using namespace std;
const double eps=1e-9;
struct pt{
int x,y;
bool operator <(pt b){
if(x==b.x) return y<b.y;
return x<b.x;
}
bool operator >(pt b){
if(x==b.x) return y>b.y;
return x<b.x;
}
bool operator ==(pt b){
if(x-b.x<=eps and y-b.y<=eps) return true;
return false;
}
pt operator+(pt b) {return {x + b.x, y + b.y};}
pt operator-(pt b) {return {x - b.x, y - b.y};}
int operator^(pt b) {return x * b.y - y * b.x;}
int operator*(pt b) {return x * b.x + y * b.y;}
};
vector<pt> a;
int d(pt a,pt b, pt o){
int cross=(a-o)^b-o;
if(fabs(cross)<=eps) return 0;
return cross > 0 ? 1 : -1;
}
int n,t;
signed main(){
cin.tie(0);ios::sync_with_stdio(0);
cin>>n;
a.resize(n+2);
for(int i=1; i<=n; i++) cin>>a[i].x>>a[i].y;
int r=0,l=0,tu=0;
pt pre=a[1],from=a[2];
for(int i=3; i<=n; i++){
int ori=d(a[i],from,pre);
if(ori==1) r++;
else if(ori==-1) l++;
else if(ori==0 and ((a[i]-from)*(from-pre))<0) tu++;
pre=from;from=a[i];
}
cout<<l<<" "<<r<<" "<<tu<<endl;
}
```
題目:[線段相交](https://neoj.sprout.tw/problem/401/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const double esp=1e-7;
double operator ^(const pair<int,int> &x,const pair<int,int> &y){
return x.first*y.second-x.second*y.first;
}
pair<int,int> operator -(const pair<int,int> &x,const pair<int,int> &y){
return pair<int,int>(x.first-y.first,x.second-y.second);
}
double operator*(const pair<int,int> &x,const pair<int,int> &y){
return x.first*y.first+x.second*y.second;
}
int sign(double a){
if(fabs(a)<esp) return 0;
return a>0? 1 : -1 ;
}
int ori(const pair<int,int> &o,const pair<int,int> &a,const pair<int,int> &b){
double cross=((a-o) ^ (b-o));
return sign(cross);
}
bool btw(const pair<int,int> &a, const pair<int,int> &b,const pair<int,int> &c){
if(ori(a,b,c) != 0 ) return 0;
return sign((c-a)*(c-b)) <= 0;
}
bool banana(const pair<int,int> &p1,const pair<int,int> &p2,const pair<int,int> &p3,const pair<int,int> &p4){
int a123=ori(p1,p2,p3);
int a124=ori(p1,p2,p4);
int a341=ori(p3,p4,p1);
int a342=ori(p3,p4,p2);
if (a123==0 and a124==0)
return btw(p1,p2,p3) or btw(p1,p2,p4) or btw(p3,p4,p1) or btw(p3,p4,p2);
return a123*a124<=0 and a341*a342<=0;
}
signed main(){
int t;
cin>>t;
while(t--){
pair<int,int> p1,p2,q1,q2;
cin>>p1.first>>p1.second>>p2.first>>p2.second>>q1.first>>q1.second>>q2.first>>q2.second;
if(banana(p1,p2,q1,q2)){
cout<<"Yes"<<endl;
}
else cout<<"No"<<endl;
}
}
```
# 第十一週: Trie、KMP
# 第十二週: Topological、Minimum spanning tree、Shortest Path
題目:[陣線推進](https://neoj.sprout.tw/problem/165/)
```cpp=
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
int ans[N],cnt=0;
int deg[N];
int main(){
int t;
cin>>t;
while(t--){
memset(deg,0,sizeof(deg));
memset(ans,0,sizeof(ans));
cnt=0;
int n,m;
vector<int> e[N];
cin>>n>>m;
for(int i=0; i<m; i++){
int a,b;
cin>>a>>b;
e[a].push_back(b);
deg[b]++;
}
priority_queue<int,vector<int>,greater<int> > pq;
for(int i=0; i<n; i++)
if(deg[i]==0)
pq.push(i);
while(!pq.empty()){
int cur=pq.top();
pq.pop();
ans[cnt++]=cur;
int len=e[cur].size();
for(int i=0; i<len; i++){
deg[e[cur][i]]--;
if(deg[e[cur][i]]==0)
pq.push(e[cur][i]);
}
}
if(cnt==n){
cout<<ans[0];
for(int i=1; i<n; i++) cout<<" "<<ans[i];
cout<<endl;
}
else cout<<"QAQ"<<endl;
}
}
```
題目:[可魚果運輸問題](https://neoj.sprout.tw/problem/391/)
```cpp=
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define N 105
#define FOR(i,n) for(int i=0;i<n;i++)
#define pii pair<int,int>
using namespace std;
void solve(){
vector<pii> edge[N]; //存圖
int n,m,s,e,f;cin>>n>>m>>s>>e>>f;
int dis[N];fill(dis,dis+N,1e16);
bool visit[N]; //城市數n、方案數m、s起、e終、f箱數
memset(visit,0,sizeof(visit));
for(int i=0;i<m;i++){
int a,b,c,d,e;cin>>a>>b>>c>>d>>e;
//一條由a連到b的邊，權重c，流量超過d，則改權重c
int val = (f>d?c*d+e*(f-d):c*f);
edge[a].push_back({b,val});
}
//Dijkstra
priority_queue<pii,vector<pii>,greater<pii>> pq; //(距離,點)
pq.push({0,s});
dis[s] = 0;
while(!pq.empty()){
int cur = pq.top().second;
pq.pop();
if(visit[cur])continue;
for(auto i:edge[cur]){
int next = i.first,weight = i.second;
if(dis[cur]+weight<dis[next]){
dis[next] = dis[cur]+weight;
pq.push({dis[next],next});
}
}
visit[cur] = 1;
}
cout<<dis[e]<<endl;
}
signed main(){
ios;
int t;cin>>t;
while(t--){
solve();
}
}
```
題目:[江神與他的小火車](https://neoj.sprout.tw/problem/431/)
```cpp=
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define IO ios::sync_with_stdio(0),cin.tie(0)
#define FOR(i,n) for(int i=0;i<n;i++)
#define pii pair<int,int>
using namespace std;
int n,m,q;
const int N=200005;
bool vst[N];
vector<pii> edge[2][N];
//edge[0]->normal,edge[1]->opposite
vector<int> Dijkstra(int start,int end,bool is_nor){
memset(vst,0,sizeof(vst));
vector<int> dis(n+2,1e16);
priority_queue<pii,vector<pii>,greater<pii>> pq;
dis[start] = 0;
pq.push({0,start});
while(!pq.empty()){
int cur = pq.top().second;
pq.pop();
if(vst[cur])continue;
vst[cur] = 1;
for(auto i : edge[is_nor][cur]){
int next = i.first,weight = i.second;
if(dis[next] > dis[cur] + weight){
dis[next] = dis[cur] + weight;
pq.push({dis[next],next});
}
}
}
return dis;
}
void solve(){
cin>>n>>m>>q;
for(int i=0;i<m;i++){
int a,b,w;cin>>a>>b>>w;
edge[0][a].push_back({b,w});
edge[1][b].push_back({a,w});
}
vector<int> normal,opposite;
normal = Dijkstra(1,n,0);
opposite = Dijkstra(n,1,1);
while(q--){
int a,b;cin>>a>>b;
cout<<min(normal[a]+opposite[b]+1,normal[n])<<endl;
}
}
signed main(){
IO;
int t;t = 1;
while(t--){
solve();
}
}
```
題目:[最小生成樹](https://neoj.sprout.tw/problem/734/)
```cpp=
#include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
const int N=200005;
int n,m,num[N],ss[N];
struct Node{
int x,y,w;
}edge[N];
bool cmp(Node a, Node b){
return a.w < b.w;
}
int findboss(int a){
if(a==ss[a])return a;
return ss[a]=findboss(ss[a]);
}
signed main(){
ios;
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>edge[i].x>>edge[i].y>>edge[i].w;
}
for(int i=0;i<n;i++){
num[i] = 1;
ss[i] = i;
}
sort(edge,edge+m,cmp);
int result = 0,num_edge = 0;
for(int i=0;i<m and num_edge<n;i++){
int a = findboss(edge[i].x),b = findboss(edge[i].y);
if(a!=b){
if(num[a]>=num[b]){
ss[b] = a;
num[a]+=num[b];
}
else{
ss[a] = b;
num[b]+=num[a];
}
result+=edge[i].w;
num_edge++;
}
}
cout<<result<<endl;
}
```
# 第十三週 Random_inclass
題目:[欸迪的字串](https://neoj.sprout.tw/problem/265/)
```cpp=
#include <bits/stdc++.h>
#define int unsigned long long int
#define endl '\n'
using namespace std;
const int mod=1e9+7,N=500005;
int power[N],hash_func[N],charc[30],n,m,C = 137;
char target[N],a[N];
vector<int> vec;
void init(){
power[0] = 1;
srand(time(NULL));
for(int i=1;i<=m;i++){
power[i] = ((power[i-1]*C)+mod)%mod;
}
for(int i=0;i<30;i++){
int temp = rand();
charc[i] = temp;
}
}
signed main(){
scanf("%s\n%s",target+1,a+1);
m = strlen(target+1);
n = strlen(a+1);
init();
hash_func[0] = 0;
for(int i=1;i<=n;i++){
hash_func[i] = ((C*hash_func[i-1]+(charc[a[i]-'a']))+mod)%mod;
}
int sum = 0;
for(int i=1;i<=m;i++){
sum = ((sum*C+(charc[target[i]-'a']))+mod)%mod;
}
for(int i=0;i<=n-m;i++){
if(sum == ((hash_func[i+m]-((hash_func[i]*power[m])+mod)%mod)+mod)%mod)
vec.push_back(i);
}
int len = vec.size();
if(len>0)printf("%llu",vec[0]);
for(int i=1;i<len;i++){
printf(" %llu",vec[i]);
}
cout<<endl; //這一行是毒瘤
}
```
題目:[溫力的故事](https://neoj.sprout.tw/problem/266/)
```cpp=
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int C=13331,N=105;
int n,m;
unsigned long long p[N];
void init(){
p[0]=1;
for(int i=1; i<=N; i++)
p[i]=p[i-1]*C;
}
int func(string s){
unsigned long long len=s.size(),sum=0;
for(int i=1; i<=len; i++)
sum+=((int) s[i-1]*p[len-i]);
return sum;
}
int main(){
init();
multiset<int> ss;
cin>>n>>m;
for(int i=0; i<n; i++){
string s;
cin>>s;
unsigned long long tmp=func(s);
ss.insert(tmp);
}
for(int i=0; i<m; i++){
string s;
cin>>s;
unsigned long long tmp=func(s);
cout<<ss.count(tmp)<<endl;
}
}
```
題目:[想不到題目標題QQ](https://neoj.sprout.tw/problem/793/)
```cpp=
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define int long long int
#define N 500005
#define mod 1000000007
using namespace std;
int n,k,m,arr[N],times[N],f[N],value[N],pre[N];
void init(){
memset(times, 0, sizeof(times));
srand(time(NULL));
pre[0] = 0;
for(int i=0;i<=N;i++){
int temp = rand()%mod;
f[i] = temp;
}
}
signed main(){
ios;
init();
cin>>n>>k>>m;
for(int i=1;i<=n;i++){
cin>>arr[i];
times[arr[i]]++;
if(times[arr[i]]%k==0){
value[i] = -(k-1)*f[arr[i]];
}
else{
value[i] = f[arr[i]];
}
pre[i] = (pre[i-1]+value[i]);
}
for(int i=1;i<=m;i++){
int l,r,sum=0;cin>>l>>r;
sum = pre[r]-pre[l-1];
if(sum==0)cout<<1;
else cout<<0;
}
cout<<endl;
}
```
# 第十四週: Connectivity
題目:[謠言問題](https://neoj.sprout.tw/problem/179/)
```cpp=
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=30001;
int n,m,root,lv[N],low[N],tree_cnt[N],es = 1;
bool visit[N],ans[N];
vector<int> edge[N];
int DFS(int now,int father){
visit[now] = 1;
lv[now] = es;
low[now] = es++;
int len = edge[now].size(),sum=1;
for(int i=0;i<len;i++){
int next = edge[now][i];
if(!visit[next]){
int temp = DFS(next,now);
sum += temp;
if(low[next] >= lv[now] && now!=root){
ans[now] = 1;
tree_cnt[now] += temp;
}
}
if(next!=father)low[now] = min(low[now],low[next]);
}
return sum;
}
signed main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y;cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
cin>>root;
memset(ans, 0, sizeof(ans));
memset(visit, 0, sizeof(visit));
memset(tree_cnt, 0, sizeof(tree_cnt));
int sum = DFS(root,root),min_cnt = INT_MAX,min_pos = 0;
for(int i=1;i<=n;i++){
int temp = sum-tree_cnt[i];
if(ans[i] && temp < min_cnt){
min_pos = i;
min_cnt = temp;
}
}
if(min_cnt == INT_MAX)cout<<0<<endl;
else cout<<min_pos<<" "<<min_cnt<<endl;
}
```
題目:[高棕櫚傳遞鏈的逆襲](https://neoj.sprout.tw/problem/184/)
```cpp=
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define int long long
#define N 1000001
using namespace std;
int n,m,lv[N],low[N],timestamp = 1;
bool visit[N];
vector<int> edge[N];
vector<pair<int, int>> ans;
set<pair<int, int>>s;
void DFS(int now,int father){
lv[now] = low[now] = timestamp++;
visit[now] = 1;
int len = edge[now].size();
for(int i=0;i<len;i++){
int next = edge[now][i];
if(!visit[next]){
DFS(next, now);
if(low[next] > lv[now]){
if(next<now)s.insert(make_pair(next,now));
else s.insert(make_pair(now, next));
}
}
if(next!=father)low[now] = min(low[now],low[next]);
}
}
signed main(){
ios;
cin>>n>>m;
for(int i=0;i<m;i++){
int x,y;cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
ans.push_back(make_pair(x, y));
}
memset(visit, 0, sizeof(visit));
for(int i=1;i<=n;i++){
if(!visit[i]){
DFS(i, i);
}
}
for(int i=0;i<m;i++){
pair<int, int> temp = ans[i];
if(s.find(temp)!=s.end()){
cout<<temp.first<<" "<<temp.second<<endl;
}
}
}
```
題目:[芽芽逛大街](https://neoj.sprout.tw/problem/739/)
```cpp=
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
const int N=500002;
int n,m,dfn[N],low[N],es = 1,stk_in[N],vertex_val[N],deg[N];
bool visit[N];
int scc[N],scc_ind = 0,scc_val[N];
int topological_order[N],ind = 0;
struct edg{
int to;
int val;
};
vector<edg> edge[N],new_edge[N];
stack<int> s;
void DFS(int now){
dfn[now] = low[now] = es++;
s.push(now);
stk_in[now] = 1;
visit[now] = 1;
int len = edge[now].size();
for(int i=0;i<len;i++){
int next = edge[now][i].to;
if(!visit[next]){
DFS(next);
low[now] = min(low[now],low[next]);
}
else if(stk_in[next]){
low[now] = min(low[now],dfn[next]);
}
}
if(low[now] == dfn[now]){
stk_in[now] = 0;
scc[now] = ++scc_ind;
scc_val[scc_ind] = vertex_val[now];
while(s.top()!=now){
scc[s.top()] = scc_ind;
stk_in[s.top()] = 0;
scc_val[scc_ind] += vertex_val[s.top()];
s.pop();
}
s.pop();
}
}
signed main(){
ios;
cin>>n>>m;
memset(visit, 0, sizeof(visit));
memset(stk_in, 0, sizeof(stk_in));
memset(deg, 0, sizeof(deg));
for(int i=1;i<=n;i++){
int x;cin>>x;
vertex_val[i] = x;
}
for(int i=0;i<m;i++){
int x,y,val;cin>>x>>y>>val;
edge[x].push_back( edg{y,val} );
}
for(int i=1;i<=n;i++)
if(!visit[i])DFS(i);
for(int i=1;i<=n;i++){
int len = edge[i].size();
for(int j=0;j<len;j++){
int to = edge[i][j].to;
if(scc[to]==scc[i]){
int ind = scc[to];
scc_val[ind]+=edge[i][j].val;
}
else{
new_edge[scc[i]].push_back( edg{scc[to],edge[i][j].val});
deg[scc[to]]++;
}
}
}
queue<int> q;
for(int i=1;i<=scc_ind;i++)
if(deg[i]==0)q.push(i);
while(!q.empty()){
int now = q.front(),len = new_edge[now].size();
topological_order[ind++] = now;
q.pop();
for(int i=0;i<len;i++){
int next = new_edge[now][i].to;
if(--deg[next]==0)q.push(next);
}
}
int dp[ind],ans = 0;
for(int i=1;i<=scc_ind;i++){
dp[i] = scc_val[i];
ans = max(ans, scc_val[i]);
}
for(int i=0;i<ind;i++){
int now = topological_order[i],len = new_edge[now].size();
for(int j=0;j<len;j++){
int next = new_edge[now][j].to;
dp[next] = max(dp[next],scc_val[next]+dp[now]+new_edge[now][j].val);
ans = max(ans, dp[next]);
}
}
cout<<ans<<endl;
}
```
# 第十五週:團體賽
# 第十六週:第二階段認證考
Google Drive
Gist
Clipboard
Sign in with Wallet
