Codeforces #480 Tutorial

Problem A,B,C:

简单的模拟，注意A中p mod q时对q=0特殊处理（注意范围）

Problem D:

Brief Intro:

给定长度为N的数组A，将A中所有连续子序列分成最少的组，使得每组任意一对数的积均为完全平方数

求最终分成组数为K的子序列个数，K属于[1,N]

Algorithm:

能推出的性质：若P,Q两数积为完全平方数，则任意一个质因子的次幂的奇偶性必然相同

那么想判断P，Q是否满足条件，只要保留每个质因子的次幂为0或1，再判断P,Q是否相同即可

下面只要考虑如何O(N^2)地判断

为了能O（1）判断新加入的数是否已经出现过，需要预处理出每一个数的上一个“自己”出现的位置

由于数的范围过广，使用map记录一个数在检索到k时最后的位置

Code:

#include <bits/stdc++.h>

using namespace std;

const int MAXN=5000+10;
int n,dat[MAXN],res[MAXN],pre[MAXN];

vector<int> prime;
map<int,int> mp;

bool isprime(int x)
{
    int up_limit=sqrt(x);
    for(int i=2;i<=up_limit;i++)
        if(x%i==0) return false;
    return true;
}

void init()
{
    int up_limit=sqrt(1e8+10);
    for(int i=2;i<=up_limit;i++)
        if(isprime(i)) prime.push_back(i);
}

int trans(int x)
{
    int up_limit=sqrt(abs(x)),ret=x;
    for(int i=0;i<prime.size();i++)
    {
        if(prime[i]>up_limit || ret==1 || ret==-1) break;
        
        int t=ret,cnt=0;
        while(t%prime[i]==0) t/=prime[i],cnt++;
        if(cnt%2==1) ret=t*prime[i];
        else ret=t;
    }
    return ret;
}

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        cin >> dat[i];
        
    init();
    
    for(int i=1;i<=n;i++) //质因数分解
        dat[i]=trans(dat[i]);
        
    for(int i=1;i<=n;i++)  //预处理pre
        if(mp.count(dat[i]))
        {
            pre[i]=mp[dat[i]];
            mp[dat[i]]=i;
        }
        else
        {
            pre[i]=-1;
            mp[dat[i]]=i;
        }
    
    for(int i=1;i<=n;i++)
    {
        bool f=true;int cnt=0;
        for(int j=i;j<=n;j++)
        {
            if(dat[j]) f=false;
            if(pre[j]<i && dat[j]) cnt++,mp[dat[j]]=true; //O（1）判断
            if(!f) res[cnt]++;
            else res[1]++; 
        }
    }
    
    for(int i=1;i<=n;i++) cout << res[i] << " ";
    return 0;
}

Review:

1、特解：0

在看到数据范围后，总要考虑特解。

除非一段全部为0，否则忽略当前遇到的0

2、积为完全平方数的性质：

我当时只想到了传导性，反而忽略了每个质因子次幂奇偶性相同这一性质

从只考虑奇偶性到转化后判断相等的方法值得借鉴

3、求解一串数中不同数的个数的预处理：

求出每一个数前一次出现的位置 常用的预处理方式

Problem E:

一棵树中有N个点，每个点的权值为2^N

要舍去K个点，使得这K个点的权值和最小，且剩下的点连通

Algorithm:

显而易见的贪心策略：

反向求解，寻找n-k个要选的点

由于第n个点的权值 > 1~n-1的权值和，所以从第n个点开始贪心选取即可

为了将复杂度控制在 O(NlogN) ，使用树上倍增查找路径终点

Code:

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1e6+10;
vector<int> G[MAXN],res;
int n,k,f[MAXN][25],vis[MAXN],dep[MAXN];

inline int read()
{
    char ch;int f=0,num;
    while(!isdigit(ch=getchar())) f|=(ch=='-');
    num=ch-'0';
    while(isdigit(ch=getchar())) num=num*10+ch-'0';
    return f?-num:num;
}

void dfs(int cur,int anc) //初始化
{
    dep[cur]=dep[anc]+1;f[cur][0]=anc;
    for(int i=1;i<=19;i++) f[cur][i]=f[f[cur][i-1]][i-1];
    
    for(int i=0;i<G[cur].size();i++)
    {
        int v=G[cur][i];
        if(v==anc) continue;
        dfs(v,cur);
    }
}

int main()
{
    n=read();k=read();
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        G[x].push_back(y);G[y].push_back(x);
    }
    
    dfs(n,0);
    
    memset(vis,0,sizeof(vis));
    vis[n]=vis[0]=1;k=n-k-1;
    for(int i=n-1;i>=1;i--)
    {
        if(vis[i]) continue;
        
        int t=i;
        for(int j=19;j>=0;j--) //倍增找路径
            if(!vis[f[t][j]]) t=f[t][j];
        
        if(dep[i]-dep[t]+1<=k)
        {
            k-=(dep[i]-dep[t]+1);
            t=i;
            while(!vis[t]) vis[t]=1,t=f[t][0];
        }
        else res.push_back(i);
    }
    
    sort(res.begin(),res.end());
    for(int i=0;i<res.size();i++) cout << res[i] << " ";
    return 0;
}

Review:

1、当正向贪心难以实现时，可以尝试反向贪心

2、当要在树上O(logN)搜寻路径时，使用树上倍增法