[kuangbin 이 너 를 데 리 고 날 아 간다] 주제 5 [병 찰 집] [- 끝 -]
A - Wireless Network
POJ - 2236
AC 코드:
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1005;
int n, d;
int rep[maxn], x[maxn], y[maxn], f[maxn];
void init()
{
for(int i = 1; i <= n; ++i)
{
f[i] = i;
rep[i] = 0;
}
}
int getf(int v)
{
if(f[v] != v)
f[v] = getf(f[v]);
return f[v];
}
int dis(int u, int v)
{
int t1 = x[u] - x[v];
int t2 = y[u] - y[v];
if(t1*t1+t2*t2 <= d*d) return 1;
return 0;
}
int main()
{
char ch;
int tem, tem1, tem2;
int k1, k2;
scanf("%d%d",&n, &d);
init();
for(int i = 1; i <= n; ++i)
scanf("%d%d",&x[i],&y[i]);
while(cin >> ch)
{
if(ch == 'O')
{
scanf("%d",&tem);
rep[tem] = 1; // ,
for(int i = 1; i <= n; ++i)
{
if(i != tem && rep[i] && dis(tem, i))
{
k1 = getf(tem);
k2 = getf(i);
f[k1] = k2;
}
}
}
if(ch == 'S')
{
scanf("%d%d",&tem1,&tem2);
k1 = getf(tem1);
k2 = getf(tem2);
//cout << k1 << endl;
//cout << k2 << endl;
if(k1 == k2) cout << "SUCCESS" << endl;
else cout << "FAIL" << endl;
}
}
return 0;
}
B - The Suspects
POJ - 1611
AC 코드:
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 30005;
int f[MAX], num[MAX];
int ran[MAX];//
int n, m;
void init()
{
for(int i = 0; i < n; ++i)
{
f[i] = i;
num[i] = 1;
}
}
int getf(int v)
{
if(f[v] != v)
f[v] = getf(f[v]);
return f[v];
}
void merg(int u, int v)
{
int t1 = getf(u);
int t2 = getf(v);
if(t1 == t2) return ;
if(ran[t1] > ran[t2])
{
//
f[t2] = t1;
num[t1] += num[t2];
}
else
{
// t2
if(ran[t1] == ran[t2]) ran[t2]++;
f[t1]= t2;
num[t2] += num[t1];
}
}
int main()
{
int t, tem, tem2;
while(scanf("%d%d",&n,&m) && (n||m))
{
init();
memset(ran, 0, sizeof(ran));
while(m--)
{
scanf("%d",&t);
scanf("%d",&tem);
t--;
while(t--)
{
scanf("%d",&tem2);
merg(tem, tem2);
}
}
int ans = getf(0);
cout << num[ans] << endl;
}
return 0;
}
C - How Many Tables
HDU - 1213
AC 코드:
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1005;
int n, m;
int f[maxn];
void init() // init() n
{
for(int i = 1; i <= n; ++i)
f[i] = i;
}
int getf(int v)
{
if(f[v] != v)
f[v] = getf(f[v]);
return f[v];
}
void merg(int u, int v)
{
int t1 = getf(u);
int t2 = getf(v);
if(t1 != t2)
f[t1] = t2;
}
int main()
{
int t, ans, a, b;
while(~scanf("%d",&t))
{
while(t--)
{
scanf("%d%d",&n,&m);
init();
ans = 0;
while(m--)
{
scanf("%d%d",&a,&b);
merg(a, b);
}
for(int i = 1; i <= n; ++i)
if(f[i] == i) ans++;
cout << ans << endl;
}
}
return 0;
}
D - How Many Answers Are Wrong
HDU - 3038
AC 코드:
#include
#include
#include
#include
#include
using namespace std;
const int N = 200005;
int f[N], sum[N];
int n, m;
int getf(int v)
{
if(f[v] == v) return v;
int t = f[v];
f[v] = getf(f[v]);
sum[v] += sum[t];
return f[v];
}
void merg(int x, int y, int u, int v, int w)
{
if(x > y)
{
f[y] = x;
sum[y] = sum[u] - sum[v] - w;
}
else
{
f[x] = y;
sum[x] = w + sum[v] - sum[u];
}
}
void init()
{
for(int i = 0; i <= n; ++i)
{
f[i] = i;
sum[i] = 0;
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
int u, v, w, ans = 0;
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
u--;
int x = getf(u);
int y = getf(v);
if(x == y && sum[u] != sum[v] + w)
ans++;
else if(x != y)
merg(x, y, u, v, w);
}
cout << ans << endl;
}
return 0;
}
E - 먹이 사슬
POJ - 1182
AC 코드:
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 100005;
int f[150000];
int x[maxn], y[maxn], t[maxn];
int n, k;
void init(int n)
{
for(int i = 0; i < n; ++i)
f[i] = i;
}
int getf(int v)
{
if(f[v] != v)
f[v] = getf(f[v]);
return f[v];
}
void merg(int u, int v)
{
int t1 = getf(u);
int t2 = getf(v);
if(t1 != t2)
f[t1] = t2;
}
int same(int u, int v)
{
return getf(u) == getf(v);
}
int main()
{
scanf("%d%d",&n,&k);
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
memset(t, 0, sizeof(t));
for(int i = 0; i < k; ++i)
scanf("%d%d%d",&t[i],&x[i],&y[i]);
init(3 * n); // x,x+n,x+2*n x-A,x-B,x-C
int ans = 0;
for(int i = 0; i < k; ++i)
{
int tt = t[i]; //
int xx = x[i] - 1;
int yy = y[i] - 1;
if(xx < 0 || xx >= n || yy < 0 || yy >= n) //
{
ans++;
continue;
}
if(tt == 1) //
{
if(same(xx, yy+n) || same(xx, yy+2*n))
ans++;
else
{
merg(xx, yy);
merg(xx+n, yy+n);
merg(xx+2*n, yy+2*n);
}
}
else //
{
if(same(xx, yy) || same(xx, yy+2*n))
ans++;
else
{
merg(xx, yy+n);
merg(xx+n, yy+2*n);
merg(xx+2*n, yy);
}
}
}
cout << ans << endl;
return 0;
}
F - True Liars
POJ - 1417
※ AC 코드:
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 1000;
int f[MAX];
int ran[MAX];
int sum[2][MAX];
int DP[MAX][MAX];
int vis[MAX][MAX];
void init()
{
memset(ran, 0, sizeof(ran));
for(int i = 0; i < MAX; ++i)
{
f[i] = i;
sum[0][i] = 1;
sum[1][i] = 0;
}
}
int getf(int v)
{
if(f[v] == v) return v;
int tem = f[v];
f[v] = getf(f[v]);
ran[v] = ran[v] ^ ran[tem];
return f[v];
}
void merg(int u, int v, int k)
{
int t1 = getf(u);
int t2 = getf(v);
if(t1 == t2) return ;
f[t2] = t1;
ran[t2] = k ^ ran[u] ^ ran[v];
sum[0][t1] += sum[0^ran[t2]][t2];
sum[1][t1] += sum[1^ran[t2]][t2];
}
int main()
{
int n, p1, p2;
int x, y;
string s;
while(~scanf("%d%d%d",&n,&p1,&p2) && (n||p1||p2))
{
init();
while(n--)
{
scanf("%d%d",&x,&y);
cin >> s;
if(s == "yes")
merg(x, y, 0);
else
merg(x, y, 1);
}
int w1[MAX], w2[MAX], p[MAX];
memset(w1, 0, sizeof(w1));
memset(w2, 0, sizeof(w2));
int cou = 1;
int suma = p1 + p2;
for(int i = 1; i <= suma; ++i)
{
if(i == getf(i))
{
w1[cou] = sum[0][i];
w2[cou] = sum[1][i];
p[cou] = i;
cou++;
}
}
memset(vis, 0, sizeof(vis));
memset(DP, 0, sizeof(DP));
DP[0][0] = 1;
for(int i = 1; i < cou; ++i)
{
for(int t = p1; t >= w1[i]; --t)
{
if(DP[i-1][t-w1[i]])
{
DP[i][t] += DP[i-1][t-w1[i]];
vis[i][t] = 0;
}
}
for(int t = p1; t >= w2[i]; --t)
{
if(DP[i-1][t-w2[i]])
{
DP[i][t] += DP[i-1][t-w2[i]];
vis[i][t] = 1;
}
}
}
// ,
if(DP[cou-1][p1] != 1)
cout << "no" << endl;
else
{
int ans[MAX];
int tot = 0;
cou--;
while(cou > 0)
{
int cur = vis[cou][p1];
int roo = p[cou];
for(int i = 1; i <= suma; ++i)
{
if(getf(i) == roo && ran[i] == cur)
ans[tot++] = i;
}
if(!cur)
p1 -= w1[cou];
else
p1 -= w2[cou];
cou--;
}
sort(ans, ans + tot);
for(int i = 0; i < tot; ++i)
cout << ans[i] << endl;
cout << "end" << endl;
}
}
return 0;
}
G - Supermarket
POJ - 1456
AC 코드 1 (이전에 풀 었 던 문제 의 코드 를 고 쳐 서 제출 했 습 니 다. 사용 하지 않 고 집합 을 찾 았 지만 시간 복잡 도가 좀 높 은 것 같 습 니 다. 157 MS):
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 10005;
int a[10005];
struct node
{
int sco, ded;
};
int cmp(node x, node y)
{
if(x.sco == y.sco)
return x.ded < y.ded;
return x.sco > y.sco;
}
int main()
{
int t, n;
while(~scanf("%d",&n))
{
long long sum = 0;
node f[maxn];
for(int i = 0; i < n; ++i)
{
scanf("%d",&f[i].sco);
scanf("%d",&f[i].ded);
sum += f[i].sco;
}
sort(f, f+n, cmp);
long long ans = 0;
memset(a, 0, sizeof(a));
for(int i = 0; i < n; ++i)
{
int tem;
for(tem = f[i].ded; tem > 0; --tem)
{
if(a[tem] == 0)
{
a[tem] = 1;
break;
}
}
if(tem == 0)
ans += f[i].sco;
}
cout << sum - ans << endl;
}
return 0;
}
AC 코드 (집합, 63MS):
/*************************************************************************
:
1. (
2.
// , f[i]==i, ,
// --,
// ,
// 0,
//
*************************************************************************/
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 1e4 + 5;
int f[MAX];
struct node
{
int value;
int time;
};
bool cmp(node a, node b)
{
if(a.value == b.value) return a.time > b.time;
return a.value > b.value;
}
void init()
{
for(int i = 0; i < MAX; ++i)
f[i] = i;
}
int getf(int v)
{
if(f[v] != v)
f[v] = getf(f[v]);
return f[v];
}
int main()
{
int n;
while(~scanf("%d",&n))
{
init();
node que[MAX];
for(int i = 0; i < n; ++i)
{
scanf("%d%d",&que[i].value,&que[i].time);
}
sort(que, que + n, cmp);
int ans = 0;
for(int i = 0; i < n; ++i)
{
int tem = que[i].time;
int xx = getf(tem);
if(xx > 0)
{
f[xx]--;
ans += que[i].value;
}
}
cout << ans << endl;
}
return 0;
}
H - Parity game
POJ - 1733
※ AC 코드:
#include
#include
#include
#include
#include
using namespace std;
const int N = 5005;
int a[N*2], n, q, cnt;
int f[N*2], r[N*2];
struct node
{
int u, v;
char str[10];
} que[N];
void init()
{
for(int i = 0; i < cnt; ++i)
{
f[i] = i;
r[i] = 0;
}
}
int getf(int v)
{
if(v != f[v])
{
int tem = f[v];
f[v] = getf(f[v]);
r[v] = r[v] ^ r[tem];
}
return f[v];
}
int bin(int v)
{
int low = 0;
int high = cnt - 1;
int mid;
while(low <= high)
{
mid = (low + high) / 2;
if(a[mid] == v) return mid;
if(a[mid] < v) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int main()
{
while(~scanf("%d",&n))
{
scanf("%d",&q);
cnt = 0;
for(int i = 0; i < q; ++i)
{
//
scanf("%d%d%s",&que[i].u,&que[i].v,&que[i].str);
que[i].u--;
a[cnt++] = que[i].v;
a[cnt++] = que[i].u;
}
sort(a, a+cnt);
cnt = unique(a, a+cnt) - a;
init();
int ans = 0;
for(int i = 0; i < q; ++i)
{
// merg
int u = bin(que[i].u);
int v = bin(que[i].v);
int t1 = getf(u);
int t2 = getf(v);
if(t1 == t2)
{
if(r[u] == r[v] && que[i].str[0] == 'o') break;
if(r[u] != r[v] && que[i].str[0] == 'e') break;
ans++;
}
else
{
if(que[i].str[0] == 'o')
{
f[t1] = t2;
r[t1] = r[u] ^ r[v] ^ 1;
}
else
{
f[t1] = t2;
r[t1] = r[u] ^ r[v];
}
ans++;
}
}
cout << ans << endl;
}
return 0;
}
I - Navigation Nightmare
POJ - 1984
※ AC 코드:
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 4e4 + 5;
const int MMM = 1e4 + 5;
int n, m, k;
int f[MAX], ans[MMM];
int x[MAX], y[MAX]; //
int dx[MAX], dy[MAX]; // ( )
int rx[MAX], ry[MAX]; //
struct node //
{
int x, y, idx; //x,y ,idx
int n; // ,
}F[MMM];
//
bool cmp(node u, node v)
{
return u.idx < v.idx;
}
void init()
{
for(int i = 0; i <= n; ++i)
{
f[i] = i;
rx[i] = ry[i] = 0;
}
}
int getf(int v)
{
if(f[v] == v) return v;
int tem = f[v];
f[v] = getf(f[v]);
rx[v] += rx[tem];
ry[v] += ry[tem];
return f[v];
}
void merg(int u, int v, int tt)
{
int t1 = getf(u);
int t2 = getf(v);
f[t2] = t1;
rx[t2] = rx[u] - rx[v] - dx[tt];
ry[t2] = ry[u] - ry[v] - dy[tt];
return ;
}
int main()
{
int w, T;
char ch;
scanf("%d%d",&n,&m);
init();
for(int i = 1; i <= m; ++i)
{
scanf("%d%d%d %c",&x[i], &y[i], &w, &ch);
switch(ch)
{
case 'E': dx[i] = w; dy[i] = 0; break;
case 'W': dx[i] = -w; dy[i] = 0; break;
case 'N': dx[i] = 0; dy[i] = w; break;
case 'S': dx[i] = 0; dy[i] = -w; break;
}
}
scanf("%d",&T);
for(int i = 1; i <= T; ++i)
{
scanf("%d%d%d",&F[i].x,&F[i].y,&F[i].idx);
F[i].n = i;
}
sort(F+1, F+T+1, cmp); //
for(int i = 1; i <= T; ++i)
{
// , F[i].idx
for(int j = F[i-1].idx; j <= F[i].idx; ++j)
{
merg(x[j], y[j], j);
}
if(getf(F[i].x) != getf(F[i].y)) //
ans[F[i].n] = -1;
else //
ans[F[i].n] = abs(rx[F[i].x] - rx[F[i].y]) + abs(ry[F[i].x] - ry[F[i].y]);
}
for(int i = 1; i <= T; ++i)
cout << ans[i] << endl;
return 0;
}
J - A Bug's Life
POJ - 2492
AC 코드:
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 4005;
int f[MAX];
int n, m;
void init(int n)
{
for(int i = 1; i <= n; ++i)
f[i] = i;
}
int getf(int v)
{
if(f[v] != v)
f[v] = getf(f[v]);
return f[v];
}
void merg(int u, int v)
{
int t1 = getf(u);
int t2 = getf(v);
if(t1 != t2)
f[t1] = t2;
}
bool same(int u, int v)
{
return getf(u) == getf(v);
}
int main()
{
int T;
bool flag;
int x, y;
scanf("%d",&T);
for(int i = 1; i <= T; ++i)
{
flag = true;
printf("Scenario #%d:
", i);
scanf("%d%d",&n,&m);
init(2*n);
while(m--)
{
scanf("%d%d",&x, &y);
if(same(x, y))
{
flag = false;
}
else
{
merg(x, y+n);
merg(y, x+n);
}
}
if(flag)
printf("No suspicious bugs found!
");
else
printf("Suspicious bugs found!
");
//if(i != 1) PE , PE
cout << endl;
}
return 0;
}
K - Rochambeau
POJ - 2912
※ AC 코드:
#include
#include
#include
#include
#include
using namespace std;
const int N = 505;
const int M = 2005;
int n, m;
bool flag;
int f[N], r[N], error[N];
struct Node
{
int u, v, k;
} a[M];
void init()
{
for(int i = 0; i < n; ++i)
{
f[i] = i;
r[i] = 0;
}
}
int getf(int v)
{
if(v != f[v])
{
int tem = f[v];
f[v] = getf(f[v]);
r[v] = (r[v] + r[tem]) % 3;
}
return f[v];
}
// && (
/*void merg(int i, int j, int x, int y, int z)
{
if(i == x || i == y) return ;
int t1 = getf(x);
int t2 = getf(y);
if(t1 == t2)
{
if(z==0 && r[x] != r[y])
{
error[i] = j + 1;
flag = true;
return ;
}
if(z==1 && (r[x]+1)%3 != r[y])
{
error[i] = j + 1;
flag = true;
return ;
}
if(z==2 && (r[x]+2)%3 != r[y])
{
error[i] = j + 1;
flag = true;
return ;
}
}
else
{
f[t2] = t1;
r[t2] = (r[x] - r[y] + 3 + z + r[t1]) % 3;
}
}*/
int main()
{
char ch;
while(~scanf("%d%d",&n,&m))
{
flag = false;
for(int i=0; i 1) puts("Can not determine");
else printf("Player %d can be determined to be the judge after %d lines
",a1,a2);
}
return 0;
}
L - Connections in Galaxy War
ZOJ - 3261
※ AC 코드:
#include
#include
#include
#include
#include
#include
M - 소희 의 미로
HDU - 1272
AC 코드:
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 1e5 + 5;
int f[MAX];
bool vis[MAX];
int n, m;
void init()
{
for(int i = 0; i < MAX; ++i)
{
f[i] = i;
vis[i] = false;
}
}
int getf(int v)
{
if(f[v] != v)
f[v] = getf(f[v]);
return f[v];
}
bool merg(int u, int v)
{
int t1 = getf(u);
int t2 = getf(v);
if(t1 != t2)
{
f[t1] = t2;
return true;
}
return false; // ——
}
int main()
{
while(scanf("%d%d",&n,&m) && (n != -1 || m != -1))
{
if(!n && !m) // 0 0
{
cout << "Yes" << endl;
continue;
}
init();
//
vis[n] = vis[m] = true;
bool flag = merg(n, m);
while(scanf("%d%d",&n,&m) && (n || m))
{
vis[n] = vis[m] = true;
if(!merg(n, m)) flag = false;
}
int cou = 0;
if(!flag)
{
cout << "No" << endl;
continue;
}
else
{
for(int i = 0; i < MAX; ++i)
if(vis[i] && f[i] == i) cou++;
}
if(cou > 1)
{
cout << "No" << endl;
continue;
}
cout << "Yes" << endl;
}
return 0;
}
N - Is It A Tree?
POJ - 1308
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 1e5 + 5;
int f[MAX];
bool vis[MAX];
int n, m;
void init()
{
for(int i = 0; i < MAX; ++i)
{
f[i] = i;
vis[i] = false;
}
}
int getf(int v)
{
if(f[v] != v)
f[v] = getf(f[v]);
return f[v];
}
bool merg(int u, int v)
{
int t1 = getf(u);
int t2 = getf(v);
if(t1 != t2)
{
f[t1] = t2;
return true;
}
return false; // ——
}
int main()
{
int cas = 0;
while(scanf("%d%d",&n,&m) && (n != -1 || m != -1))
{
if(!n && !m) // 0 0
{
printf("Case %d is a tree.
", ++cas);
continue;
}
init();
//
vis[n] = vis[m] = true;
bool flag = merg(n, m);
while(scanf("%d%d",&n,&m) && (n || m))
{
vis[n] = vis[m] = true;
if(!merg(n, m)) flag = false;
}
int cou = 0;
if(!flag)
{
printf("Case %d is not a tree.
", ++cas);
continue;
}
else
{
for(int i = 0; i < MAX; ++i)
if(vis[i] && f[i] == i) cou++;
}
if(cou > 1)
{
printf("Case %d is not a tree.
", ++cas);
continue;
}
printf("Case %d is a tree.
", ++cas);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.