11.2模拟赛

三道大水题orz

T1 有向图问有多少强连通分量

？？？

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define m(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn=10050;
const int maxm=200050;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();}
    return x*f;
}
int dfn[maxn],low[maxn],st[maxn],top,scc,vis[maxn],now,ind;
int first[maxn],to[maxm],next[maxm],cnt;
void add(int u,int v)
{
    to[++cnt]=v;
    next[cnt]=first[u];
    first[u]=cnt;
}

void Tarjan_dfs(int x)
{
    dfn[x]=low[x]=++ind;vis[x]=1;st[++top]=x;
    for(int i=first[x];i;i=next[i])
    {
        if(!dfn[to[i]])
        {
            Tarjan_dfs(to[i]);
            low[x]=min(low[x],low[to[i]]);
        }
        else if(vis[to[i]])low[x]=min(low[x],dfn[to[i]]);
    }
    if(dfn[x]==low[x])
    {
        now=0,scc++;
        while(now!=x)
        {
            now=st[top--];vis[now]=0;
        }
    }
}

int main()
{
    freopen("net.in","r",stdin);
    freopen("net.out","w",stdout); 
    int T;
    cin>>T;
    int n,m,u,v;
    while(T--)
    {
        m(to);m(next);m(first);
        m(dfn);m(low);m(vis);m(st);
        cnt=top=scc=ind=0;
        n=read(),m=read();
        for(int i=1;i<=m;i++)
        {
            u=read(),v=read();
            add(u,v);
        }
        for(int i=1;i<=n;i++)if(!dfn[i])Tarjan_dfs(i);
        cout<<scc<<endl;
    }
}

像话吗

T2 数学

记T 为一队列，初始时为空，现有n 个总和不超过s 的正整数依次入列。求出n
的最小值，使得无论这些数具体为何值，都能找到一种出队的方式，使得存在某个时刻
队列T 中的数之和恰好为m。

记选出的数为d1,d2,..,dn 他们的前缀和为S1,S2,...,Sn

只需要存在i，j使Si-Sj=m即可

抽屉原理

构造抽屉

(1,m+1),(2,m+2),...

需要注意的是：m+1这个数已经与1匹配了所以匹配完m之后开始匹配2*m+1

剩下的一个数一个抽屉

总数就是抽屉数+1

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
int main()
{
    freopen("queue.in","r",stdin);
    freopen("queue.out","w",stdout);
    int c;int s,m;
    int cnt,rest;
    cin>>c;
    while(c--)
    {
        cnt=0;
        scanf("%d%d",&s,&m);
        int t1=s/(2*m),t2=s%(2*m);
        t1*=m;
        if(t2>=m) t1+=m;
        else t1+=t2+1;
        cout<<t1<<endl;
    }
}

像话吗

T3 dfs？？

给定一个整数，我们需要求出将其分解成若干个非1 正整数的乘积的方案总数。不
分解也算一种方案。
以48 为例，它有如下12 种分解方法。
48 = 2 2 2 2 3
48 = 2 2 2 6
48 = 2 2 3 4
48 = 2 2 12
48 = 2 3 8
48 = 2 4 6
48 = 2 24
48 = 3 4 4
48 = 3 16
48 = 4 12
48 = 6 8
48 = 48

dfs

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
ll dfs(ll x,ll pre)
{
    ll ans=1;
    for(ll i=pre;i*i<=x;i++)if(x%i==0)ans+=dfs(x/i,i);
    return ans;
}
int main()
{
    freopen("factor.in","r",stdin);
    freopen("factor.out","w",stdout);
    ll n;
    scanf("%lld",&n);
    cout<<dfs(n,2);
}

像话吗

好像...AK了吧

Orz