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¶
Sample Output¶
拓扑排序#include <iostream>
#include <bits/stdc++.h>
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;
}
题目描述¶
有一个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的值<s2的值（极小点群）。 对于给定的平面，你要求出极大点群和极小点群的数量。特别的，如果所有点的值都相同，那么整个平面就既是极大点群，又是极小点群。
由于巨神 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 <bits/stdc++.h>
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;
}
题目描述¶
西⽐拉先知系统是⼀个强⼤的⼼灵指数监测⽹絡，能以声像扫描主动监控市⺠的⼼智与精神状态。为了判定出更复杂的⼈类⼼理参数，西⽐拉系统纳⼊了不同于既存⼈类规范的超群⼈格──不会随意和他⼈产⽣共鸣，也不会感情⽤事，能以⾮⼈类的眼光来俯瞰并裁定⼈类。 被纳⼊的超群⼈格会相互影响，共同处理数据。他们之间具体的影响⽅式形如⼀张⽆向图，如果你对⼀个节点进⾏操作，和这个节点相邻的节点也会受到相同的影响。 操作有⼀种：使⼀个节点的权值加上。 同时你还希望询问⼀个节点的权值(每⼀个节点的初始权值为0)。
输入¶
第⼀⾏读⼊n,m,Q,表⽰节点个数和边数,以及操作和询问的总数。 接下来m⾏，每⾏两个数ui,vi表⽰ui,vi之间有连边。 接下来Q，每⾏先读⼊⼀个type type=0表⽰⼀个询问，读⼊⼀个x,表⽰询问x节点的权值。 type=1表⽰⼀个操作，读⼊x,y,表⽰将x节点的权值加上y。（与x相邻的节点权值也要加上y）
输出¶
对于每⼀个询问输出⼀⾏，表⽰该节点的权值。
样例输入¶
样例输出¶
提示¶
n,m,Q≤3×105，y≤1000
分块法
#include <bits/stdc++.h>
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("%lld\n",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;
}