티스토리 뷰
A번: (S[N-1]=='o'):"Yes":"No", 단순한 구현 문제이다.
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
using namespace std;
set<pair<int, int>>x;
pair<int, int>arr[200100];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
string s;
cin >> s;
cout << (s[N-1]=='o'?"Yes":"No");
}B번:Pi+'a'-1을 char 형식으로 출력하면 된다.
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
using namespace std;
set<pair<int, int>>x;
pair<int, int>arr[200100];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int i;
for (i = 0; i < 26; i++)
{
int a;
cin >> a;
cout << (char)(a + 'a'-1);
}
}C번:가장 위 점들 중 가장 왼쪽인 점에 대하여 상대적인 위치를 비교하고, 시계 방향으로 돌리는 것을 4번 반복하면 된다.
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
using namespace std;
char arr[201][201];
char arr2[201][201];
char arr3[201][201];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
int i;
for (i = 0; i < N; i++)
{
cin >> arr[i];
}
for (i = 0; i < N; i++)
{
cin >> arr2[i];
}
for (i = 0; i < 4; i++)
{
int j,k;
for (j = 0; j < N; j++)
{
for (k = 0; k < N; k++)
{
arr3[N - 1 - k][j] = arr2[j][k];
}
}
for (j = 0; j < N; j++)
{
for (k = 0; k < N; k++)
{
arr2[j][k] = arr3[j][k];
}
}
set<pair<int, int>>x, y;
pair<int, int>f, s;
f = { -1,-1 };
s = { -1,-1 };
for (j = 0; j < N; j++)
{
for (k = 0; k < N; k++)
{
if (arr[j][k] == '#')
{
if (f.first == -1)
{
f = { j,k };
}
else
{
x.insert({ j - f.first,k - f.second });
}
}
if (arr2[j][k] == '#')
{
if (s.first == -1)
{
s= { j,k };
}
else
{
y.insert({ j - s.first,k - s.second });
}
}
}
}
if (x == y)
{
cout << "Yes";
return 0;
}
}
cout << "No";
}D번: 정점을 순서대로 넣으면서 넣은 정점과 기존 정점을 꼭짓점으로 하는 직사각형이 있는지 set으로 확인해주면 된다.
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
set<pair<int, int>>x;
pair<int, int>arr[200100];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
int i;
int ans = 0;
for (i = 0; i < N; i++)
{
int a, b;
cin >> a >> b;
x.insert({ a,b });
arr[i] = { a,b };
int j;
for (j = 0; j < i; j++)
{
if (a == arr[j].first || b == arr[j].second)
continue;
ans += x.count({ a,arr[j].second }) * x.count({ arr[j].first,b });
}
}
cout << ans;
}E번: 지웠을 때 벌금이 나오는 간선은 포함시켜준 뒤, mst와 같은 방식으로 양수 간선들을 모든 정점이 연결될 때까지 넣어주면 된다. 이는 벌금이 나오는 간선으로 연결된 것들을 한 정점이라고 생각하면 mst가 됨을 보임으로써 증명할 수 있다.
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#define int long long
using namespace std;
int uf[200100];
int f(int n)
{
return uf[n] == n ? n : uf[n] = f(uf[n]);
}
int u(int n, int m)
{
n = f(n);
m = f(m);
if (n == m)
return 0;
uf[n] = m;
return 1;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
int M;
vector<pair<int, pair<int, int>>>x;
cin >> M;
int i;
int ans = 0;
for (i = 1; i <= N; i++)
uf[i] = i;
for (i = 0; i < M; i++)
{
int a, b, c;
cin >> a >> b >> c;
ans += c;
x.push_back({ c,{a,b} });
}
sort(x.begin(), x.end());
for (i = 0; i < M; i++)
{
if (x[i].first <= 0)
{
ans -= x[i].first;
u(x[i].second.first, x[i].second.second);
}
else
{
if (u(x[i].second.first, x[i].second.second))
{
ans -= x[i].first;
}
}
}
cout << ans;
}F번:bfs로 경로를 하나 구한 뒤, 그 경로에 포함되지 않으면 그냥 정답을 출력하고, 포함되지 않으면 bfs를 다시 돌리면 된다.
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#define int long long
using namespace std;
int arr[401];
int bef[401];
int lin[401][401];
pair<int, int>link[200000];
int N;
int poham[401][401];
void bfs()
{
memset(arr, -1, sizeof(arr));
queue<int>x;
x.push(1);
arr[1] = 0;
while (x.size())
{
int a = x.front();
x.pop();
int j;
for (j = 1; j <= N; j++)
{
if (lin[a][j])
{
if (arr[j] == -1)
{
x.push(j);
arr[j] = arr[a] + 1;
bef[j] = a;
}
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
int M;
vector<pair<int, pair<int, int>>>x;
cin >> M;
int i;
for (i = 0; i < M; i++)
{
int a, b;
cin >> a >> b;
lin[a][b] = 1;
link[i] = { a,b };
}
bfs();
if (arr[N]==-1)
{
for (i = 0; i < M; i++)
{
cout << -1 << '\n';
}
}
else
{
int to = N;
while (to != 1)
{
poham[bef[to]][to] = 1;
to = bef[to];
}
int res = arr[N];
int j;
for (i = 0;i<M; i++)
{
if (!poham[link[i].first][link[i].second])
{
cout << res << '\n';
}
else
{
lin[link[i].first][link[i].second] = 0;
bfs();
cout << arr[N] << '\n';
lin[link[i].first][link[i].second] = 1;
}
}
}
}H번: R을 골랐을 때 K의 점수를 더 준다 하면, R이 원하는 만큼 나온 것을 찾을 수 있다. 그런 것을 확실히 찾을 수 있게 하기 위해서, 고정소수점을 구현하고, 각 이웃하는 위치에 대해서 i*i*(1/2^60)의 가중치를 더해주었다.
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <assert.h>
#define int long long
using namespace std;
struct dcm
{
int in, de;
bool operator <(dcm x)
{
if (in != x.in)
{
return in < x.in;
}
else
{
return de < x.de;
}
}
dcm operator+(dcm x)
{
dcm res = { x.in + in,x.de + de };
while (res.de >= (1LL << 60))
{
res.de -= (1LL << 60);
res.in++;
}
return res;
}
};
dcm arr[200100];
dcm dp[200100][2];
int c[200100][2];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N,R;
cin >> N>>R;
int s = -1LL << 40;
int e = 1LL << 40;
int i;
for (i = 1; i < N; i++)
{
int a;
cin >> a;
arr[i].in = a;
arr[i].de = i*3;
}
while (s != e)
{
int m = (s + e+1) / 2;
if (s + 1 == e)
{
m = e;
}
dcm rp = { m,0 };
dp[0][1] = rp;
c[0][1] = 1;
for (i = 1; i < N; i++)
{
dp[i][0] = dp[i - 1][1] + arr[i];
c[i][0] = c[i - 1][1];
if (dp[i][0] < dp[i - 1][0])
{
c[i][0] = c[i - 1][0];
dp[i][0] = dp[i - 1][0];
}
dp[i][1] = dp[i - 1][1] + rp;
c[i][1] = c[i - 1][1]+1;
if (dp[i][1] < dp[i - 1][0] + rp + arr[i])
{
c[i][1] = c[i - 1][0]+1;
dp[i][1] = dp[i - 1][0] + rp + arr[i];
}
}
int cc = (dp[N - 1][0] < dp[N - 1][1]) ? c[N - 1][1] : c[N - 1][0];
if (cc >= R)
e = m-1;
else
s = m;
}
int bakje = s;
s = 0;
e = (1LL << 60);
while (s != e)
{
int m = (s + e) / 2;
dcm rp = { bakje,m };
dp[0][1] = rp;
c[0][1] = 1;
for (i = 1; i < N; i++)
{
dp[i][0] = dp[i - 1][1] + arr[i];
c[i][0] = c[i - 1][1];
if (dp[i][0] < dp[i - 1][0])
{
c[i][0] = c[i - 1][0];
dp[i][0] = dp[i - 1][0];
}
dp[i][1] = dp[i - 1][1] + rp;
c[i][1] = c[i - 1][1] + 1;
if (dp[i][1] < dp[i - 1][0] + rp + arr[i])
{
c[i][1] = c[i - 1][0] + 1;
dp[i][1] = dp[i - 1][0] + rp + arr[i];
}
}
int cc = (dp[N - 1][0] < dp[N - 1][1]) ? c[N - 1][1] : c[N - 1][0];
if (cc >= R)
e = m;
else
s = m+1;
}
dcm x = dp[N - 1][0];
if (x < dp[N - 1][1])
{
x = dp[N - 1][1];
}
for (i = 0; i < R; i++)
{
dcm mi = { -bakje - 1,(1LL << 60) - s };
if (mi.de == (1LL << 60))
{
mi.in++;
mi.de = 0;
}
x =x+mi;
}
if (x.de >= (1LL << 59))
cout << x.in + 1;
else
cout << x.in;
}
댓글