今日份考试，手动滑稽

 

 

 

 

一、FFF团

 

【题目描述】

从前，Shylock和Lucar 幸福的生活在一起。

在情人节前夕，他们出去逛街，遇到了FFF团的成员集体活动，于是他们就被FFF团抓进了地牢，并把他们关进了随机的两个不同的房间里。FFF团的团长打算明天将他们淹没在火海之中。但是团长给了他们一个机会，如果他们其中一个人能到达另一个人的房间（另一个人不动），那么就放过他们，否则就关到第二天然后点火。

地牢里面有n个房间，m条路，每一条路连接两个房间，并且路是有方向的。

现在问Shylock和Lucar是否无论在任何情况下，都满足他们其中一个人能到达另一个人的房间，如果是则输出“I love you my love and our love save us!”，否则输出“Light my fire!”

【输入格式】

本题包含多组数据。

对于每组数据，第一行输入T，表示数据组数。

下面一行两个整数n，m，分别表示房间数和路的数量。

接下来的m行，每行两个整数x,y，表示从第x个房间有一条路可以到达y房间。

每组数据后有一个空行。

【输出格式】

输出一行，如果问Shylock和Lucar是否无论在任何情况下，都满足他们其中一个人能到达另一个人的房间，如果是则输出“I love you my love and our love save us!”，否则输出“Light my fire!”

---

一波强连通缩点，再来个拓扑排序

非常美妙，令人极度舒适

#include
     
      #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=20005,maxm=200005;int T,n,m,k,hd[maxn],dfn[maxn],low[maxn],belong[maxn];int tot,col,fr[maxn],to[maxn],fa[maxn],d[maxn];struct node{    int fr,to,nt;}e[maxm];inline void add(int x,int y){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;e[k].fr=x;}stack
       
        s;inline void tarjan(int x){    s.push(x);    dfn[x]=low[x]=++tot;    for(int i=hd[x];i;i=e[i].nt)    {        int v=e[i].to;        if(!dfn[v])        {            tarjan(v);            low[x]=min(low[x],low[v]);        }        else if(!belong[v])            low[x]=min(low[x],dfn[v]);    }        if(dfn[x]==low[x])    {        ++col;        int v=-1;        while(v!=x)        {            v=s.top();            s.pop();            belong[v]=col;        }    }}inline int find(int x){    re x==fa[x]?x:fa[x]=find(fa[x]);}inline bool topo(){    int cnt=0;    k=0;    inc(i,1,col)hd[i]=0;            inc(i,1,m)    {        int x=belong[e[i].fr];        int y=belong[e[i].to];        if(x!=y)        {            add(x,y);            ++d[y];        }    }        queue
        
         q;        inc(i,1,col)if(!d[i])    {        ++cnt;        q.push(i);    }        while(!q.empty())    {        if(cnt>1)re 1;        int u=q.front();        --cnt;        q.pop();        for(int i=hd[u];i;i=e[i].nt)        {            int v=e[i].to;            --d[v];            if(!d[v])            {                ++cnt;                q.push(v);            }        }    }    re 0;    }int main(){        //freopen("in.txt","r",stdin);    rd(T);    while(T--)    {        rd(n),rd(m);        k=tot=col=0;        inc(i,1,n)        {            dfn[i]=low[i]=belong[i]=0;            d[i]=to[i]=fr[i]=hd[i]=0;            fa[i]=i;            }                int x,y;        inc(i,1,m)        {            rd(x),rd(y);            add(x,y);        }                        inc(i,1,n)        if(!dfn[i])            tarjan(i);                        if(topo())printf("Light my fire!\n");        else printf("I love you my love and our love save us!\n");    }    re 0;}
        
       
      
     

二、maple做数学题

【题目描述】

有一天，maple上数学课，他学会了如何求一个数的因子，于是老师给他布置了一道题，在区间[L,R]里面，找出所有满足下列条件的数字：这个数的第二小的因子为K。找到这些数字以后，maple还要去把这些数加起来，请问最终结果是什么？

【输入格式】

输入数据只有一行，三个数字L,R,K含义如题目描述所示

【输出格式】

一个整数，表示把这些数加起来的和是多少，答案模 mod1e9+7 mod1e9+7

【输入样例1】

1 20 5

【输出样例1】

5

【输入样例2】

2 6 3

【输出样例2】

3

【数据约定】

20%的数据1≤L≤R≤10^5 ,2≤K≤10^5 1≤L≤R≤10^5,2≤K≤10^5

100%的数据1≤L≤R≤10^11 ,2≤K≤10^11 1≤L≤R≤10^11,2≤K≤10^11

---

 

像我这样的数学渣：

咦，数学诶！

思考1min……

不可做，绝对不可做

看了看第三题，又是一道古拉拉级膜法题：数学

暴力，暴力~~~

爆零，爆零~~~

然而坚强的LL成功苟到60pts（鲜花，掌声）

正解（dp）

#include
     
      #define re return#define ll long long#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=16000005,NN=10010,MM=120;const ll mod=1e9+7;ll L,R,K,dp[NN][MM];ll cnt,notprime[320005],prime[320005];inline bool isprime(ll x){    if(x%2==0&&x!=2)re 0;    for(int i=3;i<=sqrt(x);i+=2)    if(!(x%i))re 0;    re 1;}inline void Get_prime()//得到质数 {    notprime[1]=1;    inc(i,2,K)    {        if(!notprime[i])        prime[++cnt]=i;                inc(j,1,cnt)        {            if(prime[j]*i>K)break;            notprime[prime[j]*i]=prime[j];            if(!(i%prime[j]))break;        }    }}inline ll F(ll n,ll m)//F(n,m)表示前i个数，去掉前m个质数的和 {    ll ans;    if(n
       
        
         n)    {        while(m&&prime[m]>n)--m;        //prime[m]>n无意义        //简化         ans=F(n,m);    }    else ans=(F(n,m-1)-prime[m]*F(n/prime[m],m-1)%mod+mod)%mod;    //重点 ：对于(n/prime[m]),比如说5,5的2倍，以及5的3倍都是不成立的     if(n
         
          
           =K&&K>=L)printf("%lld",K%mod); else printf("0"); } else { Get_prime();//得到小于K的所有质数 printf("%lld",(F(R/K,cnt-1)*K%mod-F((L-1)/K,cnt-1)*K%mod+mod)%mod); } re 0;}
          
         
        
       
      
     

 

三、数字

【题目描述】

有一个n个数字的列表，你可以对列表进行两种操作

1.用x的代价删除一个数字

2.用y的代价选择一个数字增加1

两种操作没有次数限制，问使得这个列表所有数字的gcd（最大公因数）大于1的最少花费是多少？

【输入格式】

第一行三个整数表示n、x、y。

第二行有n个整数表示这个列表的数字。

【输出格式】

一个整数表示最少花费。

【输入样例1】

4 23 171 17 17 16

【输出样例1】

40

【输入样例2】

10 6 2100 49 71 73 66 96 8 60 41 63

【输出样例2】

10

【数据约定】

对于30%数据 1<=n<=1000

对于100%数据 1<=n<=500000 ,1<=x,y<=1000000000, 1<=a[i]<=1000000

---

 

突然明白为什么今天早上我错了……

其实由于数据过水，gcd只用枚举50以内

悲伤，雨中肖邦

骗分大法

上

#include
     
      #define re return#define ll long long#define inc(i,l,r) for(register int i=l;i<=r;++i)using namespace std;template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}int prime[100005],notprime[1000005];int n,maxx,cnt,a[500005];inline void Get_prime(){    notprime[1]=1;    inc(i,2,50)    {        if(!notprime[i])        prime[++cnt]=i;        inc(j,1,cnt)        {            if(prime[j]*i>50)break;            notprime[prime[j]*i]=prime[j];            if(i%prime[j])break;        }    }}int main(){    int cx,cy;    rd(n),rd(cx),rd(cy);        inc(i,1,n)    {        rd(a[i]);        maxx=a[i]>maxx?a[i]:maxx;    }        ll ans=99999999999999999;    Get_prime();//获得50以内的质因数    inc(c,1,15)//共有16个    {        int i=prime[c];        ll nowans=0;        inc(j,1,n)        {            ll t=a[j]%i;                if(t)t=(i-t)*(ll)cy;//要成为i的倍数至少还要i-t；                        //需要cy*(i-t)费用                nowans+=cx
       
        ans)break;//剪枝        }        ans=ans