20191102测试总结
咕咕咕
T1被卡常数了,求逆元的时候把ksm换成exgcd就过了,毒瘤出题人
T1:WOJ4790
题目很如学。。。
暴力n^3显然过不去,因此我们想到n^2枚举前两个数,然后log的复杂度内求逆元就可以求出第三个数,接着二分查找即可。
T2:WOJ4791
我们可以贪心的发现取最后几个背包一定是最优解,然后按照最长不下降子序列的思路乱搞一下即可(标答为权值树状数组,不过我的乱搞居然过了)。
T3:WOJ4792
计算出i个节点深度不超过d的有根树数量,然后差分一下即可。
T1被卡常数了,求逆元的时候把ksm换成exgcd就过了,毒瘤出题人
T1:WOJ4790
题目很如学。。。
暴力n^3显然过不去,因此我们想到n^2枚举前两个数,然后log的复杂度内求逆元就可以求出第三个数,接着二分查找即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, p, xx, yy, cnt, a[2505];
long long ans;
struct node
{
int a;
int b;
int num;
} s[2505];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read()
{
int x = 0;
char c = gc();
while (!isdigit(c))
c = gc();
while (isdigit(c))
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = gc();
}
return x;
}
inline bool cmp(node aa, node bb)
{
if (aa.a != bb.a)
return aa.a < bb.a;
return aa.b < bb.b;
}
inline void exgcd(int a, int b)
{
if (b == 0)
{
xx = 1;
yy = 0;
return;
}
exgcd(b, a % b);
int tmp = xx;
xx = yy;
yy = tmp - a / b * yy;
return;
}
int main()
{
n = read();
p = read();
for (register int i = 1; i <= n; ++i)
a[i] = read();
sort(a + 1, a + n + 1);
for (register int i = 1; i <= n; ++i)
if (a[i] != a[i - 1])
{
++cnt;
s[cnt].a = a[i] % p;
s[cnt].b = a[i];
s[cnt].num = 1;
}
else
++s[cnt].num;
sort(s + 1, s + cnt + 1, cmp);
for (register int i = 1; i <= n; ++i)
{
--s[i].num;
for (register int j = i; j <= n; ++j)
{
if (s[j].num <= 0)
continue;
--s[j].num;
exgcd((long long)s[i].a * s[j].a % p, p);
int k = (xx % p + p) % p;
int l = j, r = cnt;
while (l < r)
{
int mid = (l + r) >> 1;
if (k > s[mid].a)
l = mid + 1;
else
r = mid;
}
int x = l;
l = j;
r = cnt;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (k < s[mid].a)
r = mid - 1;
else
l = mid;
}
int y = l;
if (s[x].a != k)
{
++s[j].num;
continue;
}
if (s[x].num <= 0)
++x;
ans += y - x + 1;
++s[j].num;
}
++s[i].num;
}
printf("%lld", ans);
return 0;
}
T2:WOJ4791
我们可以贪心的发现取最后几个背包一定是最优解,然后按照最长不下降子序列的思路乱搞一下即可(标答为权值树状数组,不过我的乱搞居然过了)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int ttt, n, m, ans, len, t[100005], f[100005];
struct node
{
int w;
int v;
}a[100005];
bool cmp(node aa, node bb)
{
if(aa.w != bb.w)
return aa.w < bb.w;
return aa.v < bb.v;
}
int main()
{
scanf("%d", &ttt);
for(int tt = 1; tt <= ttt; ++tt)
{
ans = 0;
len = 0;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d%d", &a[i].w, &a[i].v);
sort(a + 1, a + n + 1, cmp);
scanf("%d", &m);
for(int i = 1; i <= m; ++i)
scanf("%d", &t[i]);
sort(t + 1, t + m + 1);
f[0] = 1000000005;
for(int i = n; i >= 1; --i)
{
if(a[i].v <= f[len])
{
int l = 1, r = m;
while(l < r)
{
int mid = (l + r) >> 1;
if(t[mid] < a[i].w)
l = mid + 1;
else
r = mid;
}
if(t[l] < a[i].w)
continue;
ans = max(ans, min(len + 1, m - l + 1));
if(len + 1 <= m - l + 1)
f[++len] = a[i].v;
continue;
}
int l = 1, r = len;
while(l < r)
{
int mid = (l + r) >> 1;
if(f[mid] < a[i].v)
r = mid;
else
l = mid + 1;
}
int k = l;
l = 1;
r = m;
while(l < r)
{
int mid = (l + r) >> 1;
if(t[mid] < a[i].w)
l = mid + 1;
else
r = mid;
}
if(t[l] < a[i].w)
continue;
ans = max(ans, min(k, m - l + 1));
if(k <= m - l + 1)
f[k] = a[i].v;
}
printf("%d\n", ans);
}
return 0;
}
T3:WOJ4792
计算出i个节点深度不超过d的有根树数量,然后差分一下即可。
#include <iostream>
#include <cstdio>
#define mod 998244353
using namespace std;
int n, k, l, r, a[505], vis[505], f[505][505], c[505][505];
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i <= n; ++i)
{
c[i][0] = 1;
for (int j = 1; j <= i; ++j)
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
for (int i = 1; i <= k; ++i)
{
scanf("%d", &a[i]);
vis[a[i]] = 1;
}
scanf("%d%d", &l, &r);
if (vis[1])
f[1][1] = 0;
else
f[1][1] = 1;
for (int d = 2; d <= n; ++d)
{
for (int i = 1; i <= n; ++i)
{
if (i == 1)
{
f[i][d] = 1;
continue;
}
for (int j = 1; j < i; ++j)
f[i][d] = (f[i][d] + (long long)f[i - j][d] * f[j][d - 1] % mod * c[i - 2][j - 1] % mod) % mod;
}
for (int i = 1; i <= n; ++i)
if (vis[i])
f[i][d] = 0;
}
for (int i = l; i <= r; ++i)
printf("%d ", ((f[n][i] - f[n][i - 1]) % mod + mod) % mod);
return 0;
}
评论
发表评论