A. Roman and Browser
签到.
#include <bits/stdc++.h>
using namespace std; int n, k, a[]; int get(int b)
{
int vis[];
memset(vis, , sizeof vis);
int c = b;
while (c <= n)
{
vis[c] = ;
c += k;
}
c = b - k;
while (c >= )
{
vis[c] = ;
c -= k;
}
int l = , r = ;
for (int i = ; i <= n; ++i) if (!vis[i])
{
if (a[i] == ) ++l;
else ++r;
}
return abs(l - r);
} int main()
{
while (scanf("%d%d", &n, &k) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", a + i);
int res = ;
for (int i = ; i <= n; ++i) res = max(res, get(i));
printf("%d\n", res);
}
return ;
}
B. Build a Contest
签到.
#include <bits/stdc++.h>
using namespace std; #define N 100010
int n, m, a[N];
int cnt[N]; int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = ; i <= m; ++i) scanf("%d", a + i);
int need = n;
memset(cnt, , sizeof cnt);
for (int i = ; i <= m; ++i)
{
if (cnt[a[i]] == )
--need;
++cnt[a[i]];
if (need) putchar('');
else
{
putchar('');
for (int j = ; j <= n; ++j)
{
--cnt[j];
if (!cnt[j])
++need;
}
}
}
puts("");
}
return ;
}
C. NN and the Optical Illusion
签到.
#include <bits/stdc++.h>
using namespace std; const double eps = 1e-;
const double PI = acos(-1.0); int main()
{
int n; double r;
while (scanf("%d%lf", &n, &r) != EOF)
{
double ang1 = 2.0 * PI / n;
double ang2 = (PI - ang1) / ;
double R = (r * sin(ang1) * 1.0) / ( * sin(ang2) - sin(ang1));
printf("%.10f\n", R);
}
return ;
}
D. Dasha and Chess
Upsolved.
题意：
你有一个白王，对方有$666$个黑王
你每次可以八个方向走一步，对方可以任意移动一个黑王的位置
在$2000步以内如果你和某个黑王同行同列，你就赢了$
$给出你必胜的方案$
思路：
先走到中间，再考虑黑王个数最少的那个角落，向它的反方向走就可以了
考虑最差的情况，四个角很平均都有$166个左右$
那么也就是说另外三个角的个数加起来至少是$500个，而从中间走到某一角落只需要499步$
所以一定可以包围一个
#include <bits/stdc++.h>
using namespace std; #define N 1010
#define pii pair <int, int>
#define x first
#define y second
int G[N][N], x, y, cnt[];
pii cor[N]; void Move(int edx, int edy)
{
while (x != edx || y != edy)
{
if (x < edx && G[x + ][y] == ) ++x;
else if (x > edx && G[x - ][y] == ) --x;
if (y < edy && G[x][y + ] == ) ++y;
else if (y > edy && G[x][y - ] == ) --y;
printf("%d %d\n", x, y);
fflush(stdout);
int k, a, b;
scanf("%d%d%d", &k, &a, &b);
if (k == -) exit();
G[cor[k].x][cor[k].y] = ;
cor[k].x = a, cor[k].y = b;
G[cor[k].x][cor[k].y] = ;
}
} int main()
{
while (scanf("%d%d", &x, &y) != EOF)
{
memset(G, , sizeof G);
for (int i = ; i <= ; ++i)
{
scanf("%d%d", &cor[i].x, &cor[i].y);
G[cor[i].x][cor[i].y] = ;
}
Move(, );
memset(cnt, , sizeof cnt);
for (int i = ; i <= ; ++i)
for (int j = ; j <= ; ++j)
if (G[i][j])
{
if (i < x && j < y) ++cnt[];
else if (i < x && j > y) ++cnt[];
else if (i > x && j < y) ++cnt[];
else ++cnt[];
}
if (cnt[] <= ) Move(, );
else if (cnt[] <= ) Move(, );
else if (cnt[] <= ) Move(, );
else Move(, );
}
return ;
}
E. Andrew and Taxi
Upsolved.
题意：
给出一张有向图，求改变一些边使得它没有环
改变一条边的花费是它的边权，要使得最大花费最小
输出最大花费和需要改变的边数
再输出相应的边
思路：
先二分答案，每次check的时候检查一下边权大于limit的边组成的图是否有环
如果有环，那么一定不行，如果没有环，那么一定可以
对于剩下的边，方向自定，拓扑序小的连向拓扑序大的
#include <bits/stdc++.h>
using namespace std; #define N 100010
int n, m;
struct Graph
{
struct node
{
int to, nx, w, id;
node() {}
node (int to, int nx, int w, int id) : to(to), nx(nx), w(w), id(id) {}
}a[N << ];
int head[N], pos;
void init()
{
memset(head, , sizeof head);
pos = ;
}
void add(int u, int v, int w, int id)
{
a[++pos] = node(v, head[u], w, id); head[u] = pos;
}
}G;
#define erp(u) for (int it = G.head[u], v = G.a[it].to, w = G.a[it].w, id = G.a[it].id; it; it = G.a[it].nx, v = G.a[it].to, w = G.a[it].w, id = G.a[it].id) int degree[N], ord[N];
bool check(int x)
{
memset(degree, , sizeof degree);
for (int i = ; i <= n; ++i) erp(i) if (w > x)
++degree[v];
int cnt = ;
queue <int> q;
for (int i = ; i <= n; ++i) if (!degree[i])
q.push(i);
while (!q.empty())
{
++cnt;
int u = q.front(); q.pop();
ord[u] = cnt;
erp(u) if (w > x && --degree[v] == )
q.push(v);
}
return cnt >= n;
} int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
G.init();
for (int i = , u, v, w; i <= m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
G.add(u, v, w, i);
}
int l = , r = (int)1e9, res = -;
while (r - l >= )
{
int mid = (l + r) >> ;
if (check(mid))
{
res = mid;
r = mid - ;
}
else
l = mid + ;
}
vector <int> vec;
check(res);
for (int i = ; i <= n; ++i) erp(i) if (w <= res && ord[i] > ord[v]) vec.push_back(id);
printf("%d %d\n", res, (int)vec.size());
for (int i = , len = vec.size(); i < len; ++i) printf("%d%c", vec[i], " \n"[i == len - ]);
}
return ;
}
F. Ivan and Burgers
Upsolved.
题意：
询问区间任意数异或最大值
思路：
维护前缀线性基，但是要注意将$位置id大的数更换基底$
$因为这样这些基底被用户更新答案的概率就更高$
#include <bits/stdc++.h>
using namespace std; #define N 500010
int n, q, c[N];
int pos[N][], p[N][]; void work(int x)
{
for (int i = ; i <= ; ++i)
{
pos[x][i] = pos[x - ][i];
p[x][i] = p[x - ][i];
}
int tmp = c[x];
int id = x;
for (int i = ; i >= ; --i)
{
if ((tmp >> i) & )
{
if (!p[x][i])
{
p[x][i] = tmp;
pos[x][i] = id;
return;
}
if (pos[x][i] < id)
{
swap(tmp, p[x][i]);
swap(id, pos[x][i]);
}
tmp ^= p[x][i];
}
}
} int ask(int l, int r)
{
int res = ;
for (int i = ; i >= ; --i) if (pos[r][i] >= l && (res ^ p[r][i]) > res)
res ^= p[r][i];
return res;
} int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", c + i);
for (int i = ; i < ; ++i) pos[][i] = p[][i] = ;
for (int i = ; i <= n; ++i) work(i);
scanf("%d", &q);
for (int qq = , l, r; qq <= q; ++qq)
{
scanf("%d%d", &l, &r);
printf("%d\n", ask(l, r));
} }
return ;
}