Wannafly挑战赛4 部分题解

昨天状态迷到不行，B题的TP姿势不好调了整场最后结束了才过sample，心疼自己。万恶的赛后补题。

A:给出n个整数和x，请问这n个整数中是否存在三个数a，b，c使得a*x^2+b*x+c=0，数字可以重复使用。

解法：O(n^2)枚举前2项或者O(n)枚举第一项，后面hash查找。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[1010];
set <LL> s;
int main(){
    LL n, x;
    scanf("%lld%lld",&n,&x);
    for(LL i=1; i<=n; i++) scanf("%lld", &a[i]), s.insert(a[i]);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            LL tt = a[i]*x*x+a[j]*x;
            if(s.find(-tt)!=s.end()) return 0*puts("YES");
        }
    }
    return 0*puts("NO");
}

题意：

小AA找到了一个数列，她想要知道这个数列中所有长度为偶数的区间异或和之和。
后来她发现这个问题太简单了，于是她加了一个限制，要求区间长度在[L,R]之间，
然后她就不会了。。。
请你告诉她问题的答案。

解法：

按位独立考虑，然后Two pointers的时候维护当前区间0,1的个数和当前坐标和左端点的奇偶性，这个用dp[2][2]维护了，然后细节看代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL n, L, R, a[100010];
LL dp[2][2];
int main(){
    scanf("%lld%lld%lld", &n,&L,&R);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), a[i]^=a[i-1];
    LL ans = 0;
    for(int i=0; i<31; i++){
        int k = 1<<i;
        LL now = 0;
        memset(dp, 0, sizeof(dp));
        for(int j=L; j<=n; j++){
            dp[(a[j-L]>>i)&1][(j-L)&1]++;
            now += dp[((a[j]>>i)&1)^1][j&1];
            now %= mod;
            if(j>=R) dp[(a[j-R]>>i)&1][j-R&1]--;
        }
        ans = (ans+1LL*k*now%mod)%mod;
    }
    return 0*printf("%lld\n", ans);
}

C：

题意：

有一块n*m的地，每块地要么长满杂草(用' W'表示)，要么是空地(用' G'表示)，现在有一个人站在(1,1)，面向(1,m),他可以按如下两种方式移动：

1、向面朝的方向移动一格，耗费1单位时间

2、向下移动一格，并反转面朝的方向(右变左，左变右)，耗费1单位时间

现在他想知道清除所有的杂草最少需要多少单位时间(清除完杂草之后不用返回(1,1))

解法：本身是个***题，智商下线卡了我1个小时。直接模拟即可。设置一个标记代表上一行这个人的方向是啥。

#include <bits/stdc++.h>
using namespace std;
char maze[155][155];
int st[155], en[155];
int n, m;
int main(){
    scanf("%d %d", &n,&m);
    for(int i=1; i<=n; i++) scanf("%s", maze[i]+1);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(maze[i][j]=='W'){
                st[i]=j;
                break;
            }
        }
        for(int j=m; j>=1; j--){
            if(maze[i][j]=='W'){
                en[i]=j;
                break;
            }
        }
    }
    int ans = 0, now = 1;
    bool offset = 0;
    while(now < en[1]){
        ++now;
        ++ans;
    }
    offset = 1;
    for(int i=2; i<=n; i++){
        if(offset==1){
            while(now<en[i]&&en[i]){
                ++now;
                ++ans;
            }
            for(int j=i; j<=n; j++){
                if(st[j]){
                    ++ans;
                    break;
                }
            }
            while(now>st[i]&&st[i]){
                --now;
                ++ans;
            }
            offset=0;
        }
        else if(offset==0){
            while(now>st[i]&&st[i]){
                --now;
                ++ans;
            }
            for(int j=i; j<=n; j++){
                if(st[j]){
                    ++ans;
                    break;
                }
            }
            while(now<en[i]&&en[i]){
                ++now;
                ++ans;
            }
            offset=1;
        }
    }
    return 0*printf("%d\n", ans);
}

D：

题意：

wyf非常喜欢树。一棵有根数树上有N个节点，1号点是他的根，每条边都有一个距离，而wyf是个爱问奇怪问题的熊孩子，他想知道对于某个点x,以x为根的子树上，所有与x距离大于等于k的点与x的距离之和。

解法：统计前缀和然后利用DFS序建立线段树即可，当然这个题也可以离线启发式合并，以及可持久化都是可以的。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 200010;
struct edge{
    int to,next;
    LL cost;
}E[maxn*2];
int head[maxn], edgecnt;
void init(){
    memset(head, -1, sizeof(head));
    edgecnt = 0;
}
void add(int u, int v, LL w){
    E[edgecnt].to = v, E[edgecnt].next = head[u], E[edgecnt].cost = w, head[u] = edgecnt++;
}
int L[maxn], R[maxn], dfs_clk;
LL a[maxn], d[maxn];
struct node{
    int l, r;
    LL minn, maxx, sum;
}Tree[maxn<<2];
void dfs(int u, int pre){
    L[u] = ++dfs_clk;
    for(int i=head[u]; ~i; i=E[i].next){
        int v = E[i].to;
        if(v == pre) continue;
        d[v] = d[u] + E[i].cost;
        dfs(v, u);
    }
    R[u] = dfs_clk;
}
void push_up(int rt){
    Tree[rt].maxx = max(Tree[rt*2].maxx, Tree[rt*2+1].maxx);
    Tree[rt].minn = min(Tree[rt*2].minn, Tree[rt*2+1].minn);
    Tree[rt].sum = Tree[rt*2].sum + Tree[rt*2+1].sum;
}
void build(int l, int r, int rt){
    Tree[rt].l = l, Tree[rt].r = r;
    if(l == r){
        Tree[rt].maxx = Tree[rt].minn = Tree[rt].sum = a[l];
        return;
    }
    int mid = l+r>>1;
    build(l, mid, rt*2);
    build(mid+1, r, rt*2+1);
    push_up(rt);
}
LL query(int L, int R, LL s, LL v, int rt){
    if(L<=Tree[rt].l && Tree[rt].r<=R){
        if(Tree[rt].minn>=v) return Tree[rt].sum - 1LL*s*(Tree[rt].r-Tree[rt].l+1);
        if(Tree[rt].maxx<v) return 0;
    }
    int mid = (Tree[rt].l+Tree[rt].r)/2;
    if(R<=mid) return query(L, R, s, v, rt*2);
    else if(L>mid) return query(L, R, s, v, rt*2+1);
    else return query(L, mid, s, v, rt*2) + query(mid+1, R, s, v, rt*2+1);
}
 
int main(){
    init();
    int n;
    scanf("%d", &n);
    for(int i=2; i<=n; i++){
        int p;
        LL x;
        scanf("%d %lld", &p, &x);
        add(p, i, x);
        add(i, p, x);
    }
    dfs(1, -1);
    for(int i=1; i<=n; i++) a[L[i]] = d[i];
    build(1, n, 1);
    int q;
    scanf("%d", &q);
    while(q--){
        int x;
        LL k;
        scanf("%d %lld", &x, &k);
        LL ans = query(L[x], R[x], d[x], d[x]+k, 1);
        printf("%lld\n", ans);
    }
    return 0;
}

E：

题意：

对于一个模意义下的一元二次方程：x^2+a*x+b=0其中 p 是质数。

每次给定一组 a,b,p，问这个方程有没有整数解，有解输出“Yes”，无解输出“No”。

有 T 组询问。

解法：

看到x^2直接想到2次剩余了，利用二次剩余的性质这个题就是傻题了，把二次函数的解写出来发现就是sqrt(a^2-4*b)-a或则sqrt(a^2-4*b)+a是否为偶数，这都是模意义下面的，计算a^2-4*b是否开方后为整数直接利用二次剩余即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL quick_mod(LL a, LL b, LL m)
{
    LL ans = 1;
    a %= m;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % m;
            b--;
        }
        b >>= 1;
        a = a * a % m;
    }
    return ans;
}

struct T
{
    LL p, d;
};

LL w;

//二次域乘法
T multi_er(T a, T b, LL m)
{
    T ans;
    ans.p = (a.p * b.p % m + a.d * b.d % m * w % m) % m;
    ans.d = (a.p * b.d % m + a.d * b.p % m) % m;
    return ans;
}

//二次域上快速幂
T power(T a, LL b, LL m)
{
    T ans;
    ans.p = 1;
    ans.d = 0;
    while(b)
    {
        if(b & 1)
        {
            ans = multi_er(ans, a, m);
            b--;
        }
        b >>= 1;
        a = multi_er(a, a, m);
    }
    return ans;
}

//求勒让德符号
LL Legendre(LL a, LL p)
{
    return quick_mod(a, (p-1)>>1, p);
}

LL mod(LL a, LL m)
{
    a %= m;
    if(a < 0) a += m;
    return a;
}

LL Solve(LL n,LL p)
{
    if(n == 0) return 0;
    if(p == 2) return 1;
    if (Legendre(n, p) + 1 == p)
        return -1;
    LL a = -1, t;
    while(true)
    {
        a = rand() % p;
        t = a * a - n;
        w = mod(t, p);
        if(Legendre(w, p) + 1 == p) break;
    }
    T tmp;
    tmp.p = a;
    tmp.d = 1;
    T ans = power(tmp, (p + 1)>>1, p);
    return ans.p;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        LL a, b, p;
        scanf("%lld%lld%lld", &a,&b,&p);
        if(p!=2){
            LL x = (a*a-4*b)%p;
            if(x<0) x+=p;
            int ans = Solve(x, p);
            if(ans == -1) puts("No");
            else{
                LL y = p-x;
                if((x-a)%2==0||(y-a)%2==0) puts("Yes");
                else puts("No");
            }
        }else{
            if(b%2==0||(1+a+b)%2==0||(4+2*a+b)%2==0)
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}

待补。