2020-08-07

http://acm.hdu.edu.cn/showproblem.php?pid=1285

Problem Description

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

Output

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

Sample Input

4 3
1 2
2 3
4 3

Sample Output

1 2 4 3

拓扑排序

#include 
#include 
using namespace std;
vector<int>g[600];
int in[600]= {0};
priority_queue<int,vector<int>,greater<int> >que;
queue<int>k;
int n,m,x,y;
int toposort()
{
    for(int i=1; i<=n; i++)
    {
        if(!in[i])
            que.push(i);
    }
    while(!que.empty())
    {
        int now=que.top();
        que.pop();
        k.push(now);
        for(int i=0; i<g[now].size(); i++)
        {
            int t=g[now][i];
            in[t]--;
            if(!in[t])
                que.push(t);
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
            g[i].clear(),in[i]=0;
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&x,&y);
            g[x].push_back(y);
            in[y]++;
        }
        toposort();
        int flag=0;
        while(!k.empty())
        {
            if(!flag)
            {
                printf("%d",k.front());
                flag=1;
            }
            else
            {
                printf(" %d",k.front());
            }
            k.pop();
        }
        printf("n");
    }
    return 0;
}

http://icpc.upc.edu.cn/problem.php?cid=2537&pid=5

题目描述

有一个n×n大小的方形平面，上面有n×n个点，每个点(i,j)的值wij是给定的。

对于点(i,j)，我们称与其横纵下标之差的绝对值都不超过1的点为与其相邻的点。

我们定义一个点的集合S为极大点群（极小点群）当且仅当：
1.S中所有点的值相同。
2.S中所有点都直接或间接相邻。
3.对于任意相邻两点s1,s2，满足s1属于S且s2不属于S，都有s1的值>s2的值（极大点群），或者s1的值 对于给定的平面，你要求出极大点群和极小点群的数量。特别的，如果所有点的值都相同，那么整个平面就既是极大点群，又是极小点群。

由于巨神 ctt 正在和巨神 lzh 互相吊打来吊打去，于是只好把这个任务交给了你。

输入

第一行一个正整数n，表示地图的大小。

接下来一个n×n的矩阵，表示平面上每个点的值。

输出

包含两个数，分别表示极大点群和极小点群的数量。

样例输入

【样例1】
5
2 2 2 1 1
1 1 2 2 1
1 1 1 1 1
1 2 2 1 2
1 2 2 2 2
【样例2】
5
4 6 7 3 1
4 4 6 5 5
5 5 5 2 7
4 6 2 4 7
6 1 0 1 6

样例输出

【样例1】
2 1
【样例2】
3 3

提示

样例1解释：
如下图所示，标蓝的为极大点群，标橙的为极小点群。

样例2解释：
如下图所示，标蓝的为极大点群，标橙的为极小点群。


DFS+标记。

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include 
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
ll a[2000][2000]={0};
ll dx[]={0,1,1,1,0,0,-1,-1,-1};
ll dy[]={0,1,0,-1,1,-1,1,0,-1};
ll vis[2000][2000]={0};
ll vis1[2000][2000]={0};
ll n;
ll sum=1;
ll dfs(ll x,ll y)
{
    vis1[x][y]=vis[x][y];
    for(ll i=1;i<=8;i++)
    {
        ll x1=x+dx[i];
        ll y1=y+dy[i];
        if(x1<=0||x1>n||y1<=0||y1>n)
            continue;
        if(a[x1][y1]==a[x][y]&&vis[x][y]!=vis[x1][y1])
            return -1;
        if(a[x1][y1]==a[x][y]&&vis[x][y]==vis[x1][y1]&&!vis1[x1][y1])
        {
            if(dfs(x1,y1)==-1)
                return -1;
        }
    }
}
int main()
{
    ll l;
    int flagh=0;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=n;j++)
        {
            scanf("%lld",&a[i][j]);
            if(i==1&&j==1)
            {
                l=a[i][j];
            }
            else
            {
                if(l!=a[i][j])
                    flagh=1;
            }
        }
    }
    if(!flagh)
    {
        cout<<1<<' '<<1<<endl;
        return 0;
    }
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=n;j++)
        {
            ll flag1=1;
            ll flag2=1;
            for(ll k=1;k<=8;k++)
            {
                ll x=i+dx[k];
                ll y=j+dy[k];
                if(x>n||x<=0||y>n||y<=0)
                    continue;
                if(a[x][y]>a[i][j])
                {
                    flag1=0;
                }
                if(a[x][y]<a[i][j])
                {
                    flag2=0;
                }
            }
            if(flag1)
            {
                vis[i][j]=1;
            }
            if(flag2)
            {
                vis[i][j]=2;
            }
        }
    }
    ll sum1=0,sum2=0;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=n;j++)
        {
            if(vis[i][j]!=0&&!vis1[i][j])
            {
                if(dfs(i,j)==-1)
                    continue;
                if(vis[i][j]==1)
                    sum1++;
                else
                    sum2++;
            }
        }
    }
    cout<<sum1<<' '<<sum2<<endl;
    return 0;
}

http://icpc.upc.edu.cn/problem.php?cid=2537&pid=1

题目描述

西⽐拉先知系统是⼀个强⼤的⼼灵指数监测⽹絡，能以声像扫描主动监控市⺠的⼼智与精神状态。为了判定出更复杂的⼈类⼼理参数，西⽐拉系统纳⼊了不同于既存⼈类规范的超群⼈格──不会随意和他⼈产⽣共鸣，也不会感情⽤事，能以⾮⼈类的眼光来俯瞰并裁定⼈类。
被纳⼊的超群⼈格会相互影响，共同处理数据。他们之间具体的影响⽅式形如⼀张⽆向图，如果你对⼀个节点进⾏操作，和这个节点相邻的节点也会受到相同的影响。
操作有⼀种：使⼀个节点的权值加上。
同时你还希望询问⼀个节点的权值(每⼀个节点的初始权值为0)。

输入

第⼀⾏读⼊n,m,Q,表⽰节点个数和边数,以及操作和询问的总数。
接下来m⾏，每⾏两个数ui,vi表⽰ui,vi之间有连边。
接下来Q，每⾏先读⼊⼀个type
type=0表⽰⼀个询问，读⼊⼀个x,表⽰询问x节点的权值。
type=1表⽰⼀个操作，读⼊x,y,表⽰将x节点的权值加上y。（与x相邻的节点权值也要加上y）

输出

对于每⼀个询问输出⼀⾏，表⽰该节点的权值。

样例输入

4 4 4
1 2
1 3
1 4
2 3
1 1 1
0 2
1 3 3
0 2

样例输出

1
4

提示

n,m,Q≤3×105，y≤1000

分块法

#include 
using namespace std;
typedef long long ll;
vector<ll>v[1000500];
vector<ll>g[1000500];
vector<ll>b[1000500];
ll c[1000500]={0};
int main()
{
    register ll n,m,q,x,y;
    scanf("%lld%lld%lld",&n,&m,&q);
    register ll k=sqrt(m);
    for(register ll i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    register ll s=n+1;
    for(register ll i=1;i<=n;i++)
    {
        if(v[i].size()>=k)
        {
            register ll t=0;
            for(ll j=0;j<v[i].size();j++)
            {
                t++;
                b[v[i][j]].push_back(s);
                if(t%k==0)
                {
                    g[i].push_back(s);
                    s++;
                    t=0;
                }
            }
            if(t%k)
            {
                g[i].push_back(s);
                s++;
            }
        }
    }
    register ll status;
    for(register ll i=1;i<=q;i++)
    {
        scanf("%lld",&status);
        if(status==0)
        {
            scanf("%lld",&x);
            ll t=c[x];
            for(register ll j=0;j<b[x].size();j++)
            {
                t+=c[b[x][j]];
            }
            printf("%lldn",t);
        }
        else
        {
            scanf("%lld%lld",&x,&y);
            c[x]+=y;
            if(v[x].size()>=k)
            {
                for(register ll j=0;j<g[x].size();j++)
                {
                    c[g[x][j]]+=y;
                }
            }
            else
            {
                for(register ll j=0;j<v[x].size();j++)
                {
                    c[v[x][j]]+=y;
                }
            }
        }
    }
    return 0;
}