Skip to content

Instantly share code, notes, and snippets.

@HyeonWooKim

HyeonWooKim/1.cpp Secret

Created Jun 29, 2016
Embed
What would you like to do?
2016 SCPC
#include<iostream>
#include<algorithm>
using namespace std;
unsigned long long n,dp[64][2];
void dfs(unsigned long long n, int step)
{
if (step == 64 || (n % 3 == 0 && n > dp[step][1])) return;
dp[step][1] = min(n, dp[step][1]);
if (n > 4 && n % 2 == 0 && (n - 1) % 3 == 0)
dfs((n - 1) / 3, step + 1);
dfs(n * 2, step + 1);
}
int main()
{
dp[0][0] = dp[0][1]=1;
for (int i = 1; i < 64; i++)
dp[i][0] = dp[i - 1][0]*2, dp[i][1] = 1ull<<63;
dfs(1, 0);
int t;
cin >> t;
for (int tc = 1; tc <= t; tc++)
{
cin >> n;
cout << "Case #" << tc << "\n" << dp[n][1] << " " << dp[n][0] << "\n";
}
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long dp[55001][101], total[55001];
bool mine[55001];
const int MAX = 1000000009;
int main()
{
int t;
cin >> t;
for (int tc = 1; tc <= t; tc++)
{
int n, k, l, m;
scanf("%d %d %d", &n, &k, &l);
for (int i = 0; i < l; i++)
{
scanf("%d", &m);
mine[m] = true;
}
total[0] = 1;
for (int i = 1; i <= n; i++)
{
if (mine[i]) continue;
for (int j = 1, pos = i - j; pos >= 0 && j <= k; pos--, j++)
{
dp[i][j] = (total[pos] + MAX - dp[pos][j]) % MAX;
}
for (int j = 1; j <= k; j++)
if(!mine[i])
total[i] += dp[i][j], total[i] %= MAX;
}
cout << "Case #" << tc << "\n" << total[n] % MAX << "\n";
memset(dp, 0, sizeof(dp));
memset(mine, 0, sizeof(mine));
memset(total, 0, sizeof(total));
}
}
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
bool chk[101][101];
int main()
{
int t;
cin >> t;
for (int tc = 1; tc <= t; tc++)
{
int node[101] = { 0 }, k, l, n, m, x, y, trc=0, ans = 0;
bool tr[101] = { 0 };
scanf("%d %d", &k, &l);
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++)
{
scanf("%d %d", &x, &y);
chk[x][y] = chk[y][x] = true;
node[x]++;
node[y]++;
}
while(1)
{
bool f = false;
for (int i = 1; i <= n; i++)
{
if (tr[i])continue;
if (node[i] < k || n - trc - node[i] - 1 < l)
{
f = true;
ans += i;
tr[i] = true;
trc++;
for (int j = 1; j <= n; j++)
{
if (i == j) continue;
if (chk[i][j]) node[j]--;
}
}
}
if (!f)break;
}
cout << "Case #" << tc << "\n" << ans << "\n";
memset(chk, 0, sizeof(chk));
}
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
struct Node
{
int dist, next;
Node(int a, int b){ dist = a, next = b; }
bool operator <(const Node &n) const
{
return next > n.next;
}
};
int dist[100001], parent[100001];
bool visited[100001];
int getParent(int p)
{
if (parent[p] == -1) return p;
return getParent(parent[p]);
}
int main()
{
int t;
cin >> t;
for (int tc = 1; tc <= t; tc++)
{
int n, m, k, x, y, z;
vector<vector<Node> >v;
priority_queue<Node> pq;
scanf("%d %d %d", &n, &m, &k);
v.resize(n + 1);
for (int i = 1; i <= n; i++) dist[i] = 2e9;
for (int i = 0; i < m; i++)
{
scanf("%d %d %d", &x, &y, &z);
v[x].push_back(Node(y, z));
v[y].push_back(Node(x, z));
}
for (int i = 0; i < k; i++)
{
scanf("%d", &x);
parent[x] = -1;
v[0].push_back(Node(x, 0));
}
dist[0] = 0;
pq.push(Node(0, 0));
while (!pq.empty())
{
Node tmp = pq.top();
pq.pop();
if (visited[tmp.dist]) continue;
visited[tmp.dist] = true;
int cur = tmp.dist, len = v[cur].size();
for (int i = 0; i < len; i++)
{
int next = v[cur][i].dist, nextdist = dist[cur] + v[cur][i].next;
if (dist[next] > nextdist)
{
dist[next] = nextdist;
if (parent[next] != -1) parent[next] = getParent(cur);
pq.push(Node(next, dist[next]));
}
else if (dist[next] == nextdist)
if(parent[next] != -1)
parent[next] = min(parent[next], getParent(cur));
}
}
long long sum1 = 0, sum2 = 0;
for (int i = 1; i <= n; i++)
{
int root = parent[i] == -1 ? -1 : parent[i];
sum1 += root == -1 ? 0 : dist[i];
sum2 += root == -1 ? i : root;
}
cout << "Case #" << tc << "\n" << sum1 << "\n" << sum2 << "\n";
memset(parent, 0, sizeof(parent));
memset(visited, 0, sizeof(visited));
}
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<utility>
using namespace std;
struct Shoes
{
int start, end, need;
Shoes(int a, int b, int c) { start = a, end = b, need = c; }
Shoes() {}
};
struct Times
{
int time;
int index;
Times(int a, int b) { time = a, index = b; }
bool operator <(const Times &n) const
{
return time > n.time;
}
};
struct People
{
int start, end;
People(int a, int b) { start = a, end = b;}
People() {}
};
int main()
{
int t;
cin >> t;
for (int tc = 1; tc <= t; tc++)
{
int s, p, pl[100] = { 0 };
bool f = true;
Shoes sh[200];
People po[100];
priority_queue<Times> pq;
scanf("%d %d", &s, &p);
for (int i = 0; i < s; i++)
scanf("%d %d %d", &sh[i].start, &sh[i].end, &sh[i].need);
for (int i = 0; i < p; i++)
{
scanf("%d %d", &po[i].start, &po[i].end);
for (int j = po[i].start; j < po[i].end; j++) pl[j]++;
}
for (int i = 0; i < 100; i++)
{
for (int j = 0; j < s; j++)
{
if (!sh[j].need || sh[j].start > i) continue;
if (i == sh[j].end)
{
f = false;
break;
}
int remain = sh[j].end - i - sh[j].need;
pq.push(Times(remain, j));
}
if (!f)break;
for (int j = 0; j < pl[i] && !pq.empty(); j++)
{
Times tmp = pq.top();
pq.pop();
sh[tmp.index].need--;
}
}
bool ff = !f ? false : true;
for (int i = 0; i < s; i++)
{
if (sh[i].need)
{
ff = false;
break;
}
}
cout << "Case #" << tc << "\n";
if(!ff) cout << "0\n";
else cout << "1\n";
memset(sh, 0, sizeof(sh));
memset(po, 0, sizeof(po));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment