Wanafly 练习赛8 题解

题目链接：https://www.nowcoder.com/acm/contest/39#question

A：给个n，求1到n的所有数的约数个数的和~

解法：枚举每个可能的约数，然后答案就是对n/i求和。。这个直接枚举会T，然后发现这个可以分块求。。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
//sinma(n/i)
int main(){
    scanf("%lld", &n);
    LL ans = 0;
    int pos;
    for(int d=1; d<=n; d=pos+1){
        pos=n/(n/d);
        ans+=1LL*(pos-d+1)*(n/d);
    }
    return 0*printf("%lld\n", ans);
}

D：给你一个 n 个点， m 条边的无向图，求至少要在这个的基础上加多少条无向边使得任意两个点可达 ~
解法：答案就是连通块个数减一，DFS或者并查集

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n,m,fa[maxn];
int find_set(int x){
    if(x==fa[x]) return x;
    else return fa[x]=find_set(fa[x]);
}
void union_set(int x,int y){
    int fx=find_set(x), fy=find_set(y);
    if(fx!=fy){
        fa[fx]=fy;
    }
}
bool vis[maxn];
int main(){
    scanf("%d%d",&n,&m);
    int ans=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        union_set(x,y);
    }
    for(int i=1;i<=n;i++){
        int x = find_set(i);
        if(!vis[x]){
            ans++;
            vis[x]=1;
        }
    }
    return 0*printf("%d\n", ans-1);
}

B：

一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。
每次给个区间[l,r],查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？
比如储物点i有x个东西，要运到储物点j，代价为x * dist( i , j )
dist就是储物点间的距离。

解法：维护几个前缀和即可啦。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1000000007;
const int maxn = 200010;
int n,m;
LL a[maxn],b[maxn];
LL sum1[maxn], sum2[maxn], sum3[maxn];
LL cal(int x, int L, int R){
    if(x<=L){
        LL pre = (sum2[R]-sum2[L-1]+mod)%mod*(sum1[x])%mod;
        return ((sum3[R]-sum3[L-1])%mod-pre+mod)%mod;
    }
    else{
        LL pre = (sum2[R]-sum2[L-1]+mod)%mod*sum1[x]%mod;
        return abs(pre-(sum3[R]-sum3[L-1]+mod)%mod+mod)%mod;
    }
}
int main(){
    scanf("%d%d", &n,&m);
    a[1] = 0;
    for(int i=2; i<=n; i++) scanf("%lld", &a[i]);
    for(int i=1; i<=n; i++) scanf("%lld", &b[i]);
    for(int i=2; i<=n; i++) sum1[i]=(sum1[i-1]+a[i])%mod;
    for(int i=1; i<=n; i++) sum2[i]=(sum2[i-1]+b[i])%mod;
    for(int i=1; i<=n; i++) sum3[i] = (sum3[i-1]+b[i]*(sum1[i])%mod)%mod;
    while(m--){
        int x,l,r;
        scanf("%d%d%d", &x,&l,&r);
        if(l>r) swap(l,r);
        LL ans;
        if(l<x&&x<r) ans=cal(x,l,x-1)+cal(x,x+1,r);
        else ans = cal(x,l,r);
        if(ans<0) ans+=mod;
        ans %= mod;
        printf("%lld\n", ans%mod);
    }
}

E：

给出一个集合和一个数m。

集合里面有n个质数。

请你求出从 1 到 m 的所有数中，至少能被集合中的一个数整除的数的个数。

解法：水题，容斥一下。。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m,a[22];
 
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);
    LL ans=0;
    for(int i=1;i<(1<<n);i++){
        LL temp=1;
        int ok=1;
        bool jud = 1;
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                temp*=a[j];
                if(temp>m){
                    jud=0;
                    break;
                }
                ok^=1;
            }
        }
        if(jud==0) continue;
        if(ok)
            ans-=m/temp;
        else
            ans+=m/temp;
    }
    return 0*printf("%lld\n", ans);
}

F：

给一个长为 n 的只含小写字母的字符串

每次查询一个区间 [l,r] 内，有多少子区间可以重排为一个回文串

解法：

考虑一个区间可以重排为回文串，即其中最多只有一个字符出现奇数次

把’a’ -> 1 , ‘b’ -> 2 , ‘c’ -> 4 ... ‘z’ -> 2^25

这样等价于这个区间的xor和为2的整次幂

我们维护一个前缀xor和bi = a1 ^ a2 ^ ... ^ ai，然后等价于查询区间[l,r]中有多少点对(x,y)满足b[x-1]^b[y]为2的整次幂

这个明显可以莫队维护，复杂度O( 27nsqrt( n ) )

#include <bits/stdc++.h>
using namespace std;
const int maxn = 60010;
typedef long long LL;
int n, m, block;
int tot;
char str[maxn];
map <int, int> mp;
LL Ans[maxn], sum;
vector <int> v[maxn];
struct node
{
    int l, r, id;
} q[maxn];
int s[maxn * 27], presum[maxn];
bool cmp(const node&a, const node &b)
{
    if (a.l / block == b.l / block) return a.r < b.r;
    else return a.l / block < b.l / block;
}
inline int rd()
{
    int ret=0,f=1;  char gc=getchar();
    while(gc<'0'||gc>'9') {if(gc=='-')    f=-f;   gc=getchar();}
    while(gc>='0'&&gc<='9')   ret=ret*10+(gc^'0'),gc=getchar();
    return ret*f;
}
int main()
{
    n = rd();
    m = rd();
    mp.clear();
    tot = 0;
    block = sqrt(n);
    scanf("%s", str + 1);
    for (int i = 0; i <= n; i++)
    {
        if (i)
        {
            presum[i] = presum[i - 1] ^ (1 << (str[i] - 'a'));
        }
        if (mp.find(presum[i])==mp.end()) mp[presum[i]] = ++tot;
        v[i].push_back(mp[presum[i]]);
    }
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            if (mp.find(presum[i] ^ (1 << j))!=mp.end()) v[i].push_back(mp[presum[i] ^ (1 << j)]);
        }
    }
    for (int i = 1; i <= m; i++) q[i].l = rd(), q[i].r = rd() , q[i].l--, q[i].id = i;
    sort(q + 1, q + m + 1, cmp);
    int l = 1, r = 0;
    vector <int>::iterator it;
    for (int i = 1; i <= m; i++)
    {
        for (; l > q[i].l; s[v[l][0]]++)
        {
            for (l--, it = v[l].begin(); it != v[l].end(); it++) sum += s[*it];
        }
        for (; r < q[i].r; s[v[r][0]]++)
        {
            for (r++, it = v[r].begin(); it != v[r].end(); it++) sum += s[*it];
        }
        for (; l < q[i].l; l++)
        {
            for (s[v[l][0]]--, it = v[l].begin(); it != v[l].end(); it++) sum -= s[*it];
        }
        for (; r > q[i].r; r--)
        {
            for (s[v[r][0]]--, it = v[r].begin(); it != v[r].end(); it++) sum -= s[*it];
        }
        Ans[q[i].id] = sum;
    }
    for (int i = 1; i <= m; i++) printf("%lld\n", Ans[i]);
}

C：不会。

题意：

给一个长为 n 的只含小写字母的字符串

设总共有 x 个回文连续子串

在这 x 个子串中任选不同的两个，有公共部分的方案数

答案对 1000000007 取模

解法：

考虑容斥一下，求两个不相交的回文子串很好求

枚举一下分割线，然后严格属于两边的回文子串就可以产生贡献

大力差分一下，维护两个前缀和，算算贡献就可以了

O( n )

没看懂这个怎么算的。。谁知道可以教教我啊。。