A,B pass
C. Prob No. 069A : 젖소 길 건너기 [CH04.3. USACO(Bronze)]
http://koistudy.net/?mid=contest_prob_page&NO=1690&ContestID=50c3d7614917b24303ee6a220679dab3
ai와 bi를 pair로 묶어 sort를 하면 ai가 오름 차순으로 정렬된다. 충돌을 하지 않는 소의 후보가 될 수 있는 것은
1부터 현재 i번째 소까지 볼때 b1~bi-1보다 bi 값이 큰 갱신되는 소이다.
그 후보에 대하여 스택을 이용하여 k:[i+1,n]에서 bi보다 작은 bk가 없는지 본다.
스택에 push,pop이 한 번씩 되므로 O(n) 이다.
#include <bits/stdc++.h>
#define N 100005
#define INF 987654321
using namespace std;
pair<int,int> s[N];
stack<int> S;
int n,a[N],b[N];
int main()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++){
scanf("%d %d",&a[i],&b[i]);
s[i].first=a[i];s[i].second=b[i];
}
sort(s+1,s+1+n);
int mx=-INF;
for(i=1;i<=n;i++){
if(mx<s[i].second) S.push(s[i].second),mx=s[i].second;
else{
while(!S.empty()){
if(S.top()>s[i].second) S.pop();
else break;
}
}
}
printf("%d",S.size());
}
정렬 : O(nlogn)
stack : O(n)
Prob No. 0196 : 커피 전문점 [CH04.1.Competition(GTPC10)]
http://koistudy.net/?mid=prob_page&NO=406&SEARCH=0
///풀이 설명 : A-B , B-C의 최단 거리위 점들이 후보지가 된다. C-A는 할 필요 없다.
/// 틀린이유 배열을 작게 잡음
#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n;
vector<int> V[N];
queue<int> Q;
struct egde{
int u,v;
} e[N+9];
int s[5],q[20005],m,num[N],visit[N],cc,used[N],best[N];
int dfs(int from,int to)
{
used[from]=1;
if(from==to){
best[from]=1;return 1;
}
else{
for(int i=0;i<V[from].size();i++)
if(!used[V[from][i]])
if(dfs(V[from][i],to)){
best[from]=1;return 1;
}
}
return 0;
}
int main()
{
scanf("%d",&n);
int i;
for(i=1;i<n;i++)scanf("%d%d",&e[i].u,&e[i].v),V[e[i].u].push_back(e[i].v),V[e[i].v].push_back(e[i].u);
scanf("%d%d%d%d",&s[1],&s[2],&s[3],&m);
dfs(s[3],s[2]);memset(used,0,sizeof(used));dfs(s[1],s[3]);
for(i=1;i<=n;i++)
if(best[i])Q.push(i),num[i]=i,visit[i]=1,++cc;
while(!Q.empty()){
int v=Q.front();Q.pop();
for(i=0;i<V[v].size();i++)if(!visit[V[v][i]])num[V[v][i]]=num[v],Q.push(V[v][i]),visit[V[v][i]]=1;
}
printf("%d\n",cc);
for(i=1;i<=m;i++)scanf("%d",&q[i]),printf("%d\n",num[q[i]]);
}
E. Prob No. 0414 : 병원균 퇴치 [CH02.2.Algorithm(Design)]
http://koistudy.net/?mid=prob_page&NO=1044
Bridge,(절선),Articualtion point(절점) <- graph 필수 이론
절선 점점 찾기 : http://gs16024.blogspot.kr/2017/02/bridge-articualtion-point.html
이 문제는 절점을 이용하는 문제!
절선을 이용하는 문제는 koi 공중 도시 가 있다.
1. 일단 그래프가 분리되어 있는 것들에 그룹 번호를 매겨준다.(Union 함수)
2. 이후 절점을 찾는다.(dfs 함수)
일단 편의를 위해 모든 정점이 연결되어 있다고 하자 .어떤 절점 v을 없앴을 때 남겨지는 그래프는 dfn[v]<=bac[u] (u는 v의 자식)를 만족하는 u 밑에 딸려 있는 그래프이거나 이런 서브트리들을 제외한 나머지 그래프이다. 그런데 나머지 그래프가 하나인 것을 알 수 있다. 따라서 자식으로 부터 노드의 갯수를 반환 받으면 코딩을 쉽게 할 수 있다!!
corner case :
1. 분리되어 있는 여러개의 그래프
2. 정점이 하나 입력
3. 절점을 없앨 때 값이 정답이 아닐 때
///절점 찾기
#include <bits/stdc++.h>
using namespace std;
const int N=100004;
const int oo=987654321;
struct edge{
int from,to;
bool operator <(edge R)const{
return from<R.from;
}
} e[600004];
int n,m,st[N],ed[N],groupnum[N],groupcnt[N],gcnt,dfn[N],bac[N],cnt,root,ansmin=oo,subtreecnt[N],submx[N];
/// 그룹원수 그룹갯수 루트, 정답, 총 자식 수, 자식수중 최대 ;
bool used[N],art[N];
/// 절점 인가?
pair<int,int> groupsrt[N];
void input()
{
freopen("input.txt","r",stdin);
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=m;i++){
scanf("%d %d",&e[i*2-1].from,&e[i*2-1].to);
e[i*2].from=e[i*2-1].to,e[i*2].to=e[i*2-1].from;
}
sort(e+1,e+1+2*m);
for(i=1;i<=m*2;i++) ed[e[i].from]=i;
for(i=2*m;i>=1;i--) st[e[i].from]=i;
}
void Union(int v,int t){
used[v]=true;
groupnum[v]=t;
groupcnt[t]++;
int i;
for(i=st[v];i!=0 && i<=ed[v];i++){
if(!used[e[i].to]) Union(e[i].to,t);
}
}
void dfs(int v,int parent)
{
used[v]=true;
bac[v]=dfn[v]=++cnt;
int i,to,sum;
vector<int> G;
for(i=st[v];i!=0 && i<=ed[v];i++){
if(!used[e[i].to]){
dfs(e[i].to,v);
G.push_back(e[i].to);
subtreecnt[v]+=subtreecnt[e[i].to];
if(v!=root && bac[e[i].to]>=dfn[v]){
// printf("절점 %d",v);
art[v]=true;
}
bac[v]=min(bac[v],bac[e[i].to]);
}
else{
bac[v]=min(bac[v],dfn[e[i].to]);
}
}
if(v==root && ed[v]-st[v]>=1) art[v]=true;
subtreecnt[v]++;
if(art[v]){
sum=0;
for(i=0;i<G.size();i++){
to=G[i];
if(bac[to]>=dfn[v]) submx[v]=max(submx[v],subtreecnt[to]),sum+=subtreecnt[to];
}
submx[v]=max(submx[v],groupcnt[groupnum[v]]-1-sum);
}
}
void process()
{
int i,mx;
for(i=1;i<=n;i++){
if(!used[i]){
Union(i,++gcnt);
groupsrt[gcnt].first=groupcnt[gcnt];
groupsrt[gcnt].second=gcnt;
}
}
sort(groupsrt+1,groupsrt+1+gcnt);
memset(used,0,sizeof(used));
for(i=1;i<=n;i++){
if(!used[i]){
root=i;
dfs(i,0);
}
}
for(i=1;i<=n;i++){
mx=0;
if(!art[i]){
if(groupsrt[gcnt].second==groupnum[i]) mx=max(groupsrt[gcnt].first-1,groupsrt[gcnt-1].first);
else mx=groupsrt[gcnt].first;
ansmin=min(ansmin,mx);
}
else{
if(groupsrt[gcnt].second==groupnum[i]) mx=max(submx[i],groupsrt[gcnt-1].first);
else mx=groupsrt[gcnt].first;
ansmin=min(ansmin,mx);
}
}
printf("%d",ansmin);
}
int main()
{
input();
process();
}
F. Prob No. 01F7 : Traveling Ship [CH02.1.Algorithm(Exist#A)]
걍 강한 연결 성분(SCC) 돌려서 DAG 만들고
#include <bits/stdc++.h>
#define N 10005
using namespace std;
queue<int> Q;
vector<int> v[N],rv[N],vs,gv[N];
int n,m,s,t,c[N],to,from,k,g[N],eu[100005],ev[100005],num[N],ck[N],ind[N];
bool us[N];
void dfs(int from){
int to,i;
c[from]=1;
for(i=0;i<v[from].size();i++){
to=v[from][i];
if(c[to]==0) dfs(to);
}
vs.push_back(from);
}
void rdfs(int from){
int to,i;g[from]=k;num[k]++;c[from]=1;
for(i=0;i<rv[from].size();i++){
to=rv[from][i];
if(c[to]==0) rdfs(to);
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
int i;
for(i=1;i<=m;i++){
scanf("%d %d",&eu[i],&ev[i]);
v[eu[i]].push_back(ev[i]);
rv[ev[i]].push_back(eu[i]);
}
for(i=1;i<=n;i++) if(c[i]==0)dfs(i);
memset(c,0,sizeof(c));
for(i=vs.size()-1;i>=0;i--)
if(c[vs[i]]==0)k++,rdfs(vs[i]);
for(i=1;i<=m;i++){
if(g[eu[i]]!=g[ev[i]])
gv[g[eu[i]]].push_back(g[ev[i]]),ind[g[ev[i]]]++;
}
memset(c,0,sizeof(c));
for(i=1;i<=k;i++)
if(ind[i]==0)
Q.push(i);
c[g[s]]=num[g[s]];
us[g[s]]=1;
while(!Q.empty())
{
from=Q.front();Q.pop();
for(i=0;i<gv[from].size();i++){
to=gv[from][i];
if(us[from]==1 && c[to]<c[from]+num[to])
c[to]=c[from]+num[to],us[to]=1;
ind[to]--;
if(ind[to]==0) Q.push(to);
}
}
printf("%d",c[g[t]]);
}
G. Prob No. 0362 : Sub-string Virus [CH04.3.Competition(Codeforces)]
문제 안 읽어봄
http://koistudy.net/?mid=prob_page&NO=866
H. Prob No. 02F9 : 2137년 우주선 긴급출동 [CH02.2.Algorithm(Design)]
이문제는 정수론의 뤼카의 정리를 활용하는 문제이다.
http://koistudy.net/?mid=prob_page&NO=761&SEARCH=0
위키 피디아 뤼카의 정리 설명 :
https://ko.wikipedia.org/wiki/%EB%A4%BC%EC%B9%B4%EC%9D%98_%EC%A0%95%EB%A6%AC
뤼카의 정리로 푸는 다른 문제 : http://koistudy.net/?mid=prob_page&NO=725
댓글 없음:
댓글 쓰기