20191101测试总结
咕咕咕
脑残的读错了T1数据范围，T2还没注意常数。。。被卡掉60
T1：WOJ4785
对于第一种情况按照GCD来算就行了，第二种显然判断一下大小就可以了，注意爆int。
T2：WOJ4786
我们发现如果数量相同的字母个数相等，那么就一定可以互换。因此将标本和当前串的相同数量的字母的数量求差的绝对值的和，当和为0的时候就成立了。
T3：WOJ4787
毒瘤题。。。
我们可以发现，每个点的魅力值就是它的子树和它自己的基础魅力值之和，因此一条路径上深度浅的数魅力值一定大。那么可以走的路径的端点就一定在一个节点的不同子树上了，并且满足终点的魅力值小于起点的魅力值（从起点往上走起点的魅力值不可能为最大的）。
因此我们对魅力值进行排序，然后按照数位进行判断。对于每一位，只要判断一下有没有小于它并且不在当前节点的子树上的数这一位是一即可。为了便于统计，我们将所有当前位为1的数的数量减去这棵树的子树上当前位为1的数的数量，就可以计算出这个值了。
脑残的读错了T1数据范围，T2还没注意常数。。。被卡掉60
T1：WOJ4785
对于第一种情况按照GCD来算就行了，第二种显然判断一下大小就可以了，注意爆int。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, q;
long long g, c[700005];
inline int read_int()
{
int x = 0;
char ch = getchar();
while (!isdigit(ch))
ch = getchar();
while (isdigit(ch))
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x;
}
inline long long read_long()
{
long long x = 0;
char ch = getchar();
while (!isdigit(ch))
ch = getchar();
while (isdigit(ch))
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x;
}
inline long long gcd(long long x, long long y)
{
if (!y)
return x;
return gcd(y, x % y);
}
int main()
{
n = read_int();
for (int i = 1; i <= n; ++i)
{
c[i] = read_long();
if (i == 1)
g = c[i];
else
g = gcd(g, c[i]);
}
sort(c + 1, c + n + 1);
q = read_int();
for (int i = 1; i <= q; ++i)
{
long long a;
int b;
a = read_long();
b = read_int();
if (b == 1)
{
if (g % a == 0)
puts("Yes");
else
puts("No");
}
else
{
if (a > 1000000000)
puts("No");
else
{
if (c[1] <= a * a)
puts("No");
else
puts("Yes");
}
}
}
return 0;
}
T2：WOJ4786
我们发现如果数量相同的字母个数相等，那么就一定可以互换。因此将标本和当前串的相同数量的字母的数量求差的绝对值的和，当和为0的时候就成立了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t, n, q, col, cnt[26], tot[26], num[2005], sum[2005];
char s[2005];
inline int read()
{
int x = 0;
char ch = getchar();
while (!isdigit(ch))
ch = getchar();
while (isdigit(ch))
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x;
}
int main()
{
t = read();
for (register int tt = 1; tt <= t; ++tt)
{
n = read();
q = read();
scanf("%s", s + 1);
for (register int ttt = 1; ttt <= q; ++ttt)
{
col = 0;
memset(cnt, 0, sizeof(cnt));
memset(tot, 0, sizeof(tot));
memset(num, 0, sizeof(num));
int l, r, len, ans = 0;
l = read();
r = read();
len = r - l + 1;
for (register int i = l; i <= r; ++i)
++cnt[s[i] - 'a'];
for (int i = 0; i < 26; ++i)
{
++col;
++num[cnt[i]];
}
for (register int i = 1; i <= len; ++i)
++tot[s[i] - 'a'];
for (int i = 0; i < 26; ++i)
{
if (num[tot[i]] <= 0)
++col;
else
--col;
--num[tot[i]];
}
if (!col)
++ans;
for (register int i = len + 1; i <= n; ++i)
{
if (num[tot[s[i - len] - 'a']] >= 0)
++col;
else
--col;
++num[tot[s[i - len] - 'a']];
--tot[s[i - len] - 'a'];
if (num[tot[s[i - len] - 'a']] <= 0)
++col;
else
--col;
--num[tot[s[i - len] - 'a']];
if (num[tot[s[i] - 'a']] >= 0)
++col;
else
--col;
++num[tot[s[i] - 'a']];
++tot[s[i] - 'a'];
if (num[tot[s[i] - 'a']] <= 0)
++col;
else
--col;
--num[tot[s[i] - 'a']];
if (!col)
++ans;
}
printf("%d\n", ans);
}
}
return 0;
}
T3：WOJ4787
毒瘤题。。。
我们可以发现，每个点的魅力值就是它的子树和它自己的基础魅力值之和，因此一条路径上深度浅的数魅力值一定大。那么可以走的路径的端点就一定在一个节点的不同子树上了，并且满足终点的魅力值小于起点的魅力值（从起点往上走起点的魅力值不可能为最大的）。
因此我们对魅力值进行排序，然后按照数位进行判断。对于每一位，只要判断一下有没有小于它并且不在当前节点的子树上的数这一位是一即可。为了便于统计，我们将所有当前位为1的数的数量减去这棵树的子树上当前位为1的数的数量，就可以计算出这个值了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, cap, sum, num;
int b[400005], head[400005], cnt[400005][50];
long long ans[400005], f[400005];
struct node
{
int v;
int nxt;
} a[800005];
struct point
{
int id;
long long f;
} s[400005];
bool cmp(point aa, point bb)
{
return aa.f < bb.f;
}
void ins(int u, int v)
{
++sum;
a[sum].v = v;
a[sum].nxt = head[u];
head[u] = sum;
return;
}
void dfs1(int k, int fa)
{
int d = head[k];
f[k] = b[k];
while (d)
{
if (a[d].v != fa)
{
dfs1(a[d].v, k);
f[k] += f[a[d].v];
}
d = a[d].nxt;
}
s[k].id = k;
s[k].f = f[k];
return;
}
void dfs2(int k, int fa)
{
int d = head[k];
while (d)
{
if (a[d].v != fa)
{
dfs2(a[d].v, k);
for (int i = 0; i < num; ++i)
cnt[k][i] += cnt[a[d].v][i] + ((f[a[d].v] & (1 << i)) != 0);
}
d = a[d].nxt;
}
return;
}
void solve(int k)
{
int x = 0, y = 0;
for (int i = 1; i <= n; ++i)
{
if (s[i].f != s[i - 1].f)
{
x += y;
y = 0;
}
ans[s[i].id] |= (1 << k) * (x > cnt[s[i].id][k]);
y += ((s[i].f & (1 << k)) != 0);
}
return;
}
int main()
{
int size=40<<20;
//__asm__ ("movl %0, %%esp\n"::"r"((char*)malloc(size)+size));//调试用这个
__asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));//提交用这个
scanf("%d%d", &n, &cap);
for (int i = 1; i < n; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
ins(u, v);
ins(v, u);
}
for (int i = 1; i <= n; ++i)
scanf("%d", &b[i]);
dfs1(cap, 0);
sort(s + 1, s + n + 1, cmp);
while (f[cap])
{
++num;
f[cap] >>= 1;
}
dfs2(cap, 0);
for (int i = 0; i < num; ++i)
solve(i);
for (int i = 1; i <= n; ++i)
printf("%lld ", ans[i]);
exit(0);
}
评论
发表评论