2018.8.19提高B组模拟考试

嗯明天要开始做A组了，因为B组全是原题...题还特别水...

T1 题意简述：jzoj3927

Description

ZPS经过长期的努力争取，终于成为了0901班的领操员，他要带领0901班参加广播操比赛。现在0901班的队伍可以看作是一个n*n的点阵，每个人都站在格点上。现在作为领操员的ZPS站(0,0)点，他想知道如果0901班的队伍站齐了，他能看到多少个人的脸（假设每个人的身高相同，体积相同）。

Input

一个正整数n。

Output

ZPS能看到多少个人的脸（当然他是看不到自己的脸的）。

Data Constraint

40%的数据，n<=1500。
100%的数据，n<=100000。

解题思路：各位大佬有没有觉得这道题很眼熟呀？

没错，这道题和[SDOI2008]仪仗队一模一样...

做过的大佬可以跳过了...

画图观察发现答案即为sum[phi[1]~phi[n-1]]+2。

注意当n=1时要特判。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
ll n,jdg[100001],prime[100001],phi[100001],cnt,ans;
void getphi()
{
    phi[1]=1;jdg[1]=1;
    for(ll i=2;i<=n;i++)
    {
        if(!jdg[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(ll j=1;j<=cnt;j++)
        {
            if(i*prime[j]>n)
                break;
            jdg[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int main()
{
    scanf("%lld",&n);
    if(n==1){printf("0
");return 0;}
    getphi();
    for(int i=1;i<n;i++)
        ans+=phi[i];
    ans=ans*2+1;
    printf("%lld
",ans);
}

T2 题意简述：jzoj3928

Description

有问题，找副连，无聊的时候当然也可以找他啦。小W找到了他的叔叔——东厂厂长——宇宙超级无敌老WS yy。他们叔侄两个商量之后决定用弹弓打破社区里的一些窗户，但是弹弓每秒只能彻底打破一扇窗户。而且如果某户窗户的主人回来了的话，他们就不能进行破坏了（不然会死得很惨的）。因为有的人装的玻璃好，有的人装的玻璃差，有的人装的玻璃高，有的人装的玻璃矮，所以你不能要求他们叔侄两个打破不同的窗户获得的快乐值必须相同。现在他们想知道在能活着的情况下能够获得的最大快乐值。

Input

第一行一个正整数n，表示共有n个窗户。
接下来n行，每行两个整数，第一个为窗子的主人回来的时刻（秒），第二个为破坏该窗户所能获得的快乐值。

Output

最大的快乐值。

Data Constraint

20%的数据，n<=100。
40%的数据，n<=50000。
100%的数据，n<=200000，快乐值的绝对值不超过32767，时刻非负且小于2^31。

解题思路：纯贪心。

把事件按时间从早到晚排序，用一个小根堆维护。

若队列内元素个数小于当前事件时间，则直接加入队列。

否则，把队列中价值最低的元素与当前事件价值对比。

若当前事件价值较大就把堆顶弹出，压入当前事件。

注意特判价值为负以及时间为0的情况。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
ll n,ans;
struct uio{
    ll tim,val;
}win[200001];
priority_queue<ll,vector<ll>,greater<ll> > que;
bool cmp(uio x,uio y)
{
    if(x.tim==y.tim) return x.val>y.val;
    return x.tim<y.tim;
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        scanf("%lld%lld",&win[i].tim,&win[i].val);
    sort(win+1,win+1+n,cmp);
    for(ll i=1;i<=n;i++)
    {
        if(win[i].val<0||win[i].tim==0) continue;
        if(que.size()<win[i].tim){que.push(win[i].val);continue;}
        else if(que.top()<win[i].val){que.pop();que.push(win[i].val);continue;}
    }
    while(!que.empty())
    {
        ans+=que.top();
        que.pop();
    }
    printf("%lld
",ans);
    return 0;
}

T3 题意简述：jzoj3929

Description

上帝手中有着n种被称作“世界元素”的东西，现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素，所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它，这样上帝就可以保持对世界的控制。
由于那个著名的有关于上帝能不能制造一块连自己都不能举起的大石头的二律背反命题，我们知道上帝不是万能的，而且不但不是万能的，他甚至有事情需要找你帮忙——上帝希望知道他最多可以投放多少种世界元素，但是他只会O(2^n)级别的算法。虽然上帝拥有无限多的时间，但是他也是个急性子。你需要帮助上帝解决这个问题。

Input

第一行一个正整数n，表示世界元素的数目。
第二行n个正整数a_1, a_2, ..., a_n。a_i表示第i个世界元素能够限制的世界元素的编号。

Output

最多可以投放的世界元素的数目。

Data Constraint

30%的数据，n<=10。
60%的数据，n<=10^5。
100%的数据，a_i<=n<=10^6。

解题思路：题解中提供了2种思路。这里介绍(懒人专属)贪心做法。

发现题目中给的图是基环森林(树)，因此可以贪心。

类似拓扑排序，找出图中所有入度为0的点，压入队列中。

对于一个点，查询它和它的儿子是否已经计入答案。若均未计入答案则儿子计入答案。

查询当前点的儿子的儿子是否入度为0，若是则压入队列。

最后会剩下一个某些点已被染色的环，按照以上策略再次贪心即可。

另一种做法是dp，想看这种解法的可以去PoPoQQQ大佬那里看看。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int n,ans,son[1000001],head[1000001],d[1000001],vis[1000001];
queue<int> que;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {scanf("%d",&son[i]);d[son[i]]++;}
    for(int i=1;i<=n;i++) if(!d[i]) que.push(i);
    while(!que.empty())
    {
        int now=que.front();que.pop();
        if(!vis[now]&&!vis[son[now]])
        {
            vis[son[now]]=1,ans++;
            d[son[son[now]]]--;
            if(!d[son[son[now]]]) que.push(son[son[now]]);
        }
        vis[now]=1;
    }
    for(int i=1;i<=n;i++) if(!vis[i])
    {
        vis[i]=1;
        int tmp=son[i],cnt=1;
        while(tmp!=i) vis[tmp]=1,tmp=son[tmp],cnt++;
        ans+=cnt/2;
    }
    printf("%d
",ans);
    return 0;
}