HDU Group，hdugroup

文章由LinuxBoy分享于2019-03-27 06:03:24热评（592）

HDU Group，hdugroup

Group

题目：

给出n个数，是1-n的排列。要求你每次给你一个区间求出这个区间可以被分成的小区间个数。一个不连续的数可以被分成一个小区间。t-1,t或t,t+1表示连续。

算法:

快速做法应该是线段树。但是，我不会。学了一个块状数组。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

const int MAXN = 100000 + 10;

struct Node{
   int l,r,id,b;

   bool operator < (const Node& rhs) const {
       if(b != rhs.b){
          return b < rhs.b;
       }
       return r < rhs.r;
   }
}query[MAXN];

int seg[MAXN];
bool vst[MAXN];
int n,m,res;
int ans[MAXN];

void cal(int x,int &l,int &r){
    int L = query[x].l, R = query[x].r;
    while(L < l){  //需要将左右区间进行放大，否则可能出现左右游标交错的情况
        --l;
        int t = seg[l];
        vst[t] = 1;
        if(vst[t-1]&&vst[t+1]) --res;
        else if(!vst[t-1]&&!vst[t+1]) ++res;
    }

    while(R > r){
        ++r;
        int t = seg[r];
        vst[t] = 1;
        if(vst[t-1]&&vst[t+1]) --res;
        else if(!vst[t-1]&&!vst[t+1]) ++res;
    }

    while(L > l){
        int t = seg[l];
        vst[t] = 0;
        if(vst[t-1]&&vst[t+1]) ++res;
        else if(!vst[t-1]&&!vst[t+1]) --res;
       ++l;
    }

    while(R < r){
        int t = seg[r];
        vst[t] = 0;
        if(vst[t-1]&&vst[t+1]) ++res;
        else if(!vst[t-1]&&!vst[t+1]) --res;
        --r;
    }
}

void solve(){
   memset(vst,0,sizeof(vst));
   sort(query,query + m);
   res = 0;
   int l = query[0].l, r = query[0].r;
   for(int i = l;i <= r;++i){
       int t = seg[i];
       vst[t] = 1;
       if(vst[t-1] && vst[t+1]) --res;
       else if(!vst[t-1]&&!vst[t+1]) ++res;
   }

   ans[query[0].id] = res;
   for(int i = 1;i < m;++i){
       ans[query[i].id] = (cal(i,l,r),res);
   }

   for(int i = 0;i < m;++i){
      printf("%d\n",ans[i]);
   }

}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);

        for(int i = 1;i <= n;++i){
            scanf("%d",&seg[i]);
        }

        int B = sqrt(1.0*n);
        for(int i = 0;i < m;++i){
            scanf("%d%d",&query[i].l,&query[i].r);
            query[i].b = query[i].l / B;
            query[i].id = i;
        }

        solve();
    }
    return 0;
}

hdu acm 1083 看不懂题意

Consider a group of N students and P courses.
有N个学生，P门课

Each student visits zero,
one or more than one courses.
每一个学生学习一些课程。

Your task is to determine whether it is possible to form a committee of exactly P students that satisfies simultaneously the conditions:
你的任务是判断是否能可能P个学习符合下面的情况。

. every student in the committee represents a different course (a student can represent a course if he/she visits that course)
每一个学生参加不同的课程

. each course has a representative in the committee
每一个课程都有学生参加。

解题报告：因为课程有P个，而且只选择P个学生，每一个学生加参的课程不同，而且每一门课都

有学生参加，这就是说有P个学生和这P门课一一对应，也就是最大二分匹配问题。

#include<stdio.h>
#include<string.h>
int cours[101];
int stu[301];
int adj[101][301];
int m[301];
int p,n;
int DFS(int from)
{
int i;
for(i=1;i<=n;i++)
{
if(adj[from][i]==1&&m[i]==0)
{
m[i]=1;
if(stu[i]==-1||DFS(stu[i]))
{
stu[i]=from;
cours[from]=i;
return 1;
}
}
}
return 0;
}
int main()
{
int i,t,temp,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&p,&n);
memset(cours,-1,sizeof(cours));
memset(stu,-1,sizeof(stu));
memset(adj,0,sizeof(adj));
for(i=1;i<=p;i++)
{
scanf("%d",&temp);
while(temp--)
{
scanf("%d",&j);
adj[i][j]=1;
}
}
for(i=1;i<=p;i++)
......余下全文>>

向大家问几个问题

ACM
ACM(Association for Computing Machinery)国际计算机组织

ACM 是一个国际科学教育计算机组织,它致力于发展在高级艺术、最新科学、工程技术和应用领域中的信息技术。它强调在专业领域或在社会感兴趣的领域中培养、发展开放式的信息交换，推动高级的专业技术和通用标准的发展。

1947年，即世界第一台电子数字计算机(ENIAC)问世的第二年，ACM即成为第一个，也一直是世界上最大的科学教育计算机组织。它的创立者和成员都是数学家和电子工程师，其中之一是约翰.迈克利(John.Mauchly)，他是ENIAC的发明家之一。他们成立这个组织的初衷是为了计算机领域和新兴工业的科学家和技术人员能有一个共同交换信息、经验知识和创新思想的场合。几十年的发展，ACM的成员们为今天我们所称之为“信息时代”作出了贡献。他们所取得的成就大部分出版在ACM印刷刊物上并获得了ACM颁发的在各种领域中的杰出贡献奖。例如：A.M.Turing奖和Grance Murr—ay Hopper奖。

ACM组织成员今天已达到九万人之多，他们大部分是专业人员、发明家、研究员、教育家、工程师和管理人员；三分之二以上的ACM成员，又是属于一个或多个 SIGs(Special Interest Group)专业组织成员。他们都对创造和应用信息技术有着极大的兴趣。有些最大的最领先的计算机企业和信息工业也都是ACM的成员。

ACM就像一个伞状的组织，为其所有的成员提供信息，包括最新的尖端科学的发展，从理论思想到应用的转换，提供交换信息的机会。正象ACM建立时的初衷，它仍一直保持着它的发展“信息技术”的目标，ACM成为一个永久的更新最新信息领域的源泉。

ACM 国际计算机组织有以下主要活动内容：

1. 出版各种有关计算机技术的杂志，日报和书共十大类；

- Communications of the ACM ACM通讯

- Interactions 交互技术

- Standard View 标准

- Multimedia Systems 多媒体系统

- Computing Surveys 计算技术调查

- Computing Reviews 计算技术回顾

- Journal of the ACM ACM日报

- Wireless Networks 无线网络技术

- ACM's Transactions Journals ACM科研项目日报

包括：Computer-Human Interaction 人机交互技术

Computer Systems 计算机系统

Database Systems 数据库系统

Graphics 作图

Information Systems 信息系统

Mathematical Software 数学软件

Modeling and Computer Simulation 建模和计算机模仿

Networking 网络

Programming Languages and Systems 编程语言和系统

Software Engineering & Methodology 软件工程和方法学

- The ACM Press Books Program ACM 出版书四十种

2. ACM 有下属37个专业组织SIGs(Special Interest Group)

(1)、SIGACT: Algorithm & Computational Theory

计算机科学基础理......余下全文>>

推荐文章：

HDU Group，hdugroup