A. The Child and Homework
注意仔细读题,WA了好多次,=_=
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ; char s[][maxn];
int l[], r[]; bool cmp(int a, int b) { return l[a] < l[b]; } int main()
{
//freopen("in.txt", "r", stdin); for(int i = ; i < ; i++) r[i] = i;
for(int i = ; i < ; i++) scanf("%s", s[i]);
for(int i = ; i < ; i++) { l[i] = strlen(s[i]); l[i] -= ; }
sort(r, r + , cmp); int ans = -;
if(l[r[]] * <= l[r[]]) ans = r[];
if(l[r[]] >= l[r[]] * ) { if(ans == -) ans = r[]; else ans = ; }
if(ans == -) ans = ; printf("%c\n", 'A' + ans); return ;
}
代码君
B. The Child and Set (贪心)
把那些lowbit都算出来,然后从大到小排个序,依次往里面填就好了。
#include <cstdio>
#include <algorithm>
using std::sort;
const int maxn = + ;
int lowbit[maxn], r[maxn], ans[maxn], cnt; bool cmp(int a, int b) { return lowbit[a] > lowbit[b]; } int main()
{
int s, n;
scanf("%d%d", &s, &n); for(int i = ; i <= n; i++) { r[i] = i; lowbit[i] = i & (-i); }
sort(r + , r + + n, cmp);
int t = ;
for(int i = ; i <= n; i++)
{
if(t == s) break;
if(lowbit[r[i]] + t <= s) { t += lowbit[r[i]]; ans[cnt++] = r[i]; }
} if(t != s) { puts("-1"); return ; }
printf("%d\n%d", cnt, ans[]);
for(int i = ; i < cnt; i++) printf(" %d", ans[i]);
puts(""); return ;
}
代码君
C. The Child and Toy (贪心)
最优的删点方式就是从最大的点开始删起。
不妨从边的角度考虑更为方便,最终没有任意两个点事连通的,所以每条边都会被删去。考虑边(u, v),它被删去的时候贡献的一定是uv中较小的权值。
所以算法就是,读进每条边累加它权值较小的那个端点的权值即可。
#include <cstdio>
#include <algorithm>
using std::min; const int maxn = + ;
const int maxm = + ; int a[maxn], u[maxm], v[maxm]; int main()
{
int n, m, ans = ;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
for(int i = ; i < m; i++) { scanf("%d%d", &u[i], &v[i]); ans += min(a[u[i]], a[v[i]]); }
printf("%d\n", ans); return ;
}
代码君
D. The Child and Zoo (贪心 含秩并查集 最大生成树)
给每条边赋一个权值,为两端顶点权值较小的那个,然后将这些边从大到小排序。
一开始图是空的,每加进一条权值为w的边可能会将两个连通分量连通起来,那么对于分别位于这两个连通分量中的(u, v),f(u, v) = w,而这样的f(u, v)一共有 p * q个,其中pq分别为这两个连通分量的秩。
#include <cstdio>
#include <algorithm>
using namespace std; const int maxn = + ;
int a[maxn], u[maxn], v[maxn], w[maxn], r[maxn], cnt[maxn]; int pa[maxn];
int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); } bool cmp(int a, int b) { return w[a] > w[b]; } int main()
{
//freopen("in.txt", "r", stdin); int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
for(int i = ; i <= m; i++) { scanf("%d%d", &u[i], &v[i]); w[i] = min(a[u[i]], a[v[i]]); } for(int i = ; i <= n; i++) { pa[i] = i; cnt[i] = ; }
for(int i = ; i <= m; i++) r[i] = i;
sort(r + , r + + m, cmp); double ans = 0.0;
int c = n;
for(int i = ; i <= m && c > ; i++)
{
int px = findset(u[r[i]]);
int py = findset(v[r[i]]);
if(px != py)
{
ans += (double) cnt[px] * cnt[py] * w[r[i]];
pa[px] = py; cnt[py] += cnt[px];
c--;
}
} printf("%.6f\n", ans * / (n * 1.0 * (n - ))); return ;
}
代码君
E. The Child and Polygon (区间DP 叉积)
不妨将这些点按照逆时针顺序编号0 ~ n-1。d(i, j)表示多边形 i, i+1 ,..., j, i 的三角剖分的方法数。
则有状态转移方程 d(i, j) = sum{ d(i, k) * d(k, j) | i < k < j 且 线段ik在多边形内部 }
可以通过叉积来判断线段是否在多边形内部,具体就是判断 ji × jk 是否为正。
总时间复杂度为O(n)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; typedef long long LL;
const LL MOD = ; const int maxn = + ;
int n; struct Point
{
LL x, y;
Point(LL x = , LL y = ):x(x), y(y) {}
}p[maxn]; Point operator - (const Point& A, const Point& B)
{ return Point(A.x - B.x, A.y - B.y); } LL Cross(const Point& A, const Point& B)
{ return A.x * B.y - A.y * B.x; } LL d[maxn][maxn]; LL dp(int L, int R)
{
if(d[L][R] != -) return d[L][R];
LL& ans = d[L][R];
if(R - L == ) return ans = ;
ans = ;
for(int i = L + ; i < R; i++)
if(Cross(p[L] - p[R], p[i] - p[R]) > )
ans = (ans + dp(L, i) * dp(i, R)) % MOD;
return ans;
} int main()
{
//freopen("in.txt", "r", stdin); scanf("%d", &n);
LL x, y;
for(int i = ; i < n; i++)
{
scanf("%I64d%I64d", &x, &y);
p[i] = Point(x, y);
} LL area = ;
for(int i = ; i + < n; i++)
area += Cross(p[i] - p[], p[i+] - p[]);
if(area < ) reverse(p, p + n); memset(d, -, sizeof(d));
printf("%I64d\n", dp(, n - )); return ;
}
代码君
最后看了下Div1的两道题:
D. The Child and Sequence (线段树 单点修改)
动态询问连续子序列的和。操作有 单点修改 和 将 连续区间的每个数都模上x
重点说一下取模的操作,可以维护一个区间的最大值,当区间的最大值小于x的时候,那么便不用取模了。
而且每个数每次取模以后的值至少要减半,所以每个数取模的次数不会太多。
balabala...
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL; const int maxn = + ;
int n, m, qL, qR, p, op;
LL v;
LL sumv[maxn << ], maxv[maxn << ]; void pushup(int o)
{
sumv[o] = sumv[o<<] + sumv[o<<|];
maxv[o] = max(maxv[o<<], maxv[o<<|]);
} void build(int o, int L, int R)
{
if(L == R) { scanf("%I64d", &sumv[o]); maxv[o] = sumv[o]; return; }
int M = (L + R) / ;
build(o<<, L, M);
build(o<<|, M+, R);
pushup(o);
} void update1(int o, int L, int R)
{
if(L == R) { sumv[o] = maxv[o] = v; return; }
int M = (L + R) / ;
if(p <= M) update1(o<<, L, M);
else update1(o<<|, M+, R);
pushup(o);
} void update2(int o, int L, int R)
{
if(maxv[o] < v) return;
if(L == R) { sumv[o] %= v; maxv[o] %= v; return; }
int M = (L + R) / ;
if(qL <= M) update2(o<<, L, M);
if(qR > M) update2(o<<|, M+, R);
pushup(o);
} LL query(int o, int L, int R)
{
if(qL <= L && qR >= R) return sumv[o];
int M = (L + R) / ;
LL ans = ;
if(qL <= M) ans += query(o<<, L, M);
if(qR > M) ans += query(o<<|, M+, R);
return ans;
} int main()
{
//freopen("in.txt", "r", stdin); cin >> n >> m;
build(, , n);
while( m-- )
{
scanf("%d", &op);
if(op == )
{
scanf("%d%d", &qL, &qR);
printf("%I64d\n", query(, , n));
}
else if(op == )
{
scanf("%d%d%I64d", &qL, &qR, &v);
update2(, , n);
}
else
{
scanf("%d%I64d", &p, &v);
update1(, , n);
}
} return ;
}
代码君
E题看到用什么母函数,多项式求根,FFT,就打算把这道题放一放了,毕竟太弱Q_Q