2016 ACM/ICPC Asia Regional Dalian Online

阅读量：7107 次

发布时间：2019-06-28

本文共 10132 字，大约阅读时间需要 33 分钟。

1009 Sparse Graph（hdu5876）

由于每条边的权值都为1，所以最短路bfs就够了，只是要求转置图的最短路，所以得用两个set来维护，一个用来存储上次扩散还没访问的点，一个用来存储这一次扩散还没访问的点。

算法：bfs+set

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              7 #include
             
               8 #include
              
                9 using namespace std; 10 const int maxn=200100; 11 const int INF=0x3f3f3f3f; 12 int t,n,m,u,v; 13 int head[maxn];int tot; 14 int di[maxn]; 15 struct Edge 16 { 17 int to,next; 18 }edge[maxn]; 19 void init() 20 { 21 tot=0; 22 memset(head,-1,sizeof(head)); 23 } 24 void add(int u,int v) 25 { 26 edge[tot].to=v; 27 edge[tot].next=head[u]; 28 head[u]=tot++; 29 } 30 struct node 31 { 32 int num,dis; 33 }; 34 35 void bfs(int beg) 36 { 37 set
               
                s,e; 38 set
                
                 ::iterator it; 39 queue
                 
                  q; 40 for(int i=1;i<=n;i++) 41 s.insert(i),di[i]=INF; 42 node temp,nex; 43 temp.num=beg,temp.dis=0; 44 q.push(temp); 45 s.erase(beg); 46 while(!q.empty()) 47 { 48 temp=q.front();q.pop(); 49 for(int i=head[temp.num];i!=-1;i=edge[i].next) 50 { 51 int v=edge[i].to; 52 if(s.find(v)==s.end()) 53 continue; 54 s.erase(v);e.insert(v); 55 } 56 for(it=s.begin();it!=s.end();it++) 57 { 58 nex.num=*it;nex.dis=temp.dis+1; 59 di[nex.num]=min(nex.dis,di[nex.num]); 60 q.push(nex); 61 } 62 s.swap(e);e.clear(); 63 } 64 } 65 int main() 66 { 67 //freopen("input.txt","r",stdin); 68 scanf("%d",&t); 69 while(t--) 70 { 71 scanf("%d%d",&n,&m); 72 init(); 73 for(int i=0;i

View Code

1010 Weak Pair（hdu5877）

题意是要求所有节点的权值与其祖先节点权值相乘小于或等于k的总共有多少对，一开始知道必须得进行dfs，也知道可以马上建一个数组b[n]来记录每个节点需要和小于多少的数相乘才会小于看，但是在查询有多少个祖先节点小于b[i]时没有找到方法，后来才知道，可以将数据离散化后存进树状数组，只保留当前节点的父节点在树状数组当中，一旦离开这个节点，就把这个节点的权值在树状数组中删除

算法：dfs+离散化+BIT

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 #include
            
              7 #include
             
               8 using namespace std; 9 #define ll long long10 const int maxn=100100;11 int n;12 ll k,a[maxn];13 vector
              
               son[maxn];14 ll ran[maxn];15 ll b[maxn];16 int in[maxn];17 ll B[maxn];18 int low_bit(int x)19 {20 return x&(-x);21 }22 ll Sum(int x){23 ll s1 = 0;24 while (x) s1 += B[x], x -= low_bit(x);25 return s1;26 }27 void Add(int x, int d){28 while (x<=n) B[x] += d,x += low_bit(x);29 }30 void init(int n)31 {32 for(int i=1;i<=n;i++){33 son[i].clear();34 }35 memset(in,0,sizeof(in));36 }37 ll dfs(int rt)38 {39 Add(ran[rt],1);40 ll ans=0;41 for(int i=0;i

View Code

1001 Different Circle Permutation

题意：1条项链有n个珠子，有黑白2种颜色，求任意2个黑珠不相邻的项链的种类数（旋转同构）

由于有黑珠不能相邻的条件，burnside或polya不能套用。不过自己计算不考虑旋转同构的方案数就会发现：

设f(n)为n个珠子涂色使得黑珠左右不相邻的方案数，则f(n)=f(n-1)+f(n-2)其中f(1)=1 f(2)=3

可以理解为前者是1个白珠子接上n-1个珠子，后者是1个黑珠子接上1个白珠子再接n-2个珠子（出现最右1个是黑珠的情况，把最左黑珠与右边互换，还是不同方案）

至于如何求旋转同构时的方案数，把n个珠子按照1,2,3,4...u,1...这个编号平均分成n/u份，每份都是按照原先左右关系连接后满足黑珠不相邻的，所以这部分方案数是f(u)

要满足这个，首先n%u==0，那旋转k个珠子的角度实际上是分割为每份gcd(k,n)

根据burnside引理，n种珠子排布，在k种旋转后相同视为同构，方案数是（这n种珠子排布分别做k种旋转后还是同样排布的数量之和）/k

所以方案数是∑(f( gcd(i,n) ))/n ( 1<=i<=n)

思维出来了，程序也容易写了

由于n可达10的9次方，暴力计算会超时

其实可以合并的，根据欧拉函数的定义可以合并为(1<=i<=n)∑(f( gcd(i,n) ))/n=(d|n)∑f(d)*euler(n/d)

f(d)可以矩阵快速幂得出，euler(d)由于实在太大应该分解质因子做

其实这2种运算都可以在一个合理的范围内打表，小的直接查表得出

欧拉函数也用不着分解到底

算法：矩阵幂+欧拉函数运算

#include 
      
       using namespace std;const long long mod = 1e9+7 ;struct matrix {    long long x1,x2 ;    long long x3,x4 ;};matrix mul(matrix a,matrix b){    matrix ans ;    ans.x1 = (a.x1*b.x1 + a.x2*b.x3)%mod ;    ans.x2 = (a.x1*b.x2 + a.x2*b.x4)%mod ;    ans.x3 = (a.x3*b.x1 + a.x4*b.x3)%mod ;    ans.x4 = (a.x3*b.x2 + a.x4*b.x4)%mod ;    return ans ;}long long quick_matrix(long long x){    x -= 4 ;    matrix ans,cal ;    ans.x1 = ans.x2 = ans.x3 = 1 ; ans.x4 = 0 ;    cal.x1 = cal.x2 = cal.x3 = 1 ; cal.x4 = 0 ;    while (x){        if (x%2)            ans = mul(ans,cal) ;        cal = mul(cal,cal) ;        x >>= 1 ;    }    return (ans.x1*4+ans.x2*3)%mod ;}long long fx(long long x){    if (x == 1)        return 1;    else if (x == 2)        return 3;    else if (x == 3)        return 4;    else return quick_matrix(x) ;}long long quick(long long a,long long n){    long long ans = 1 ;    long long cal = a ;    while (n){        if (n%2)            ans = (ans*cal)%mod ;        cal = (cal*cal)%mod;        n >>= 1;    }    return ans ;}long long euler(long long n){    long long ans = n;    long long i;    for (i = 2; i*i <= n; i++){        if (n%i == 0){            while (n%i == 0)                n /= i;            ans = ans/i*(i-1) ;        }     }    if (n != 1)        ans = ans/n*(n-1);    return ans;}long long solve(long long n){    if (n == 1)        return 2;    long long ans = 0;     long long nn = n ;    long long d;    long long i;    for (i = 1; i*i < n; i++){        if (n%i == 0){            ans = (ans + fx(i)*euler(nn/i) + fx(nn/i)*euler(i))%mod ;         }     }    if (i*i == n)        ans = (ans + fx(i)*euler(i))%mod ;    return (ans*quick(nn,mod-2))%mod;}int main(){    long long n;    while (~scanf("%lld",&n))        printf("%lld\n",solve(n)) ;    return 0 ;}

hdu5868

1002 Different GCD Subarray Query

题意：求Q个区间含有不同的连续序列gcd个数，例如(6,8,12) gcd(6)=6 gcd(8)=8 gcd(12)=12 gcd(6,8)=2 gcd(8,12)=4 gcd(6,8,12)=2 含5种gcd值

固定右边界，左边界越往左，连续序列gcd值越小，并且两个数要么相等，要么至少相差1倍，所以一个右边界最多延伸出logn种gcd值。

题目可以离线做，合并相同右边界的查询，预处理出n个右边界的逆序对应gcd值。

树状数组储存最右出现的gcd值种类数

查询时把相同gcd值最先出现的位置尽量往右移，这样区间查询就不会减去[1,l-1]和[l,r]都含有的并且最先出现在[l,r]的数字

算法：离线+BIT

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define lowbit(x) (x & (-x))using namespace std;typedef __int64 ll;typedef pair
              
                pii;const int MAXN = 1e5 + 8;int a[MAXN];int ans[MAXN];vector
               
                 gc[MAXN];vector
                
                  query[MAXN];int vis[MAXN * 10];int n,q;int __gcd(int a,int b){ return b?__gcd(b,a%b):a;}int sum[MAXN];void treeinit(){memset(sum,0,sizeof(sum));}void update(int x,int v){ while(x <= n){sum[x] += v;x += lowbit(x);}}int getSum(int x){ int ans = 0;while(x){ans += sum[x];x -= lowbit(x);}return ans;}void init(){ for (int i = 0;i <= n;i ++){ gc[i].clear(); query[i].clear(); } memset(vis,0,sizeof(vis)); treeinit();}void input(){ int i,j; for (i = 1;i <= n;i ++) scanf("%d",a + i); //统计不同右边界从右到左的连续相同gcd值，O(nlog2n) //这里还有一种方法，预先处理出RMQ再O(nlog2nlog2n)二重二分 for (i = 1;i <= n;i ++){ int x = a[i]; int y = i; for (j = 0; j < gc[i - 1].size();j ++){ int res = __gcd(gc[i - 1][j].first,x); if (x != res){ gc[i].push_back(make_pair(x,y)); x = res; y = gc[i - 1][j].second; } } gc[i].push_back(make_pair(x,y)); } for (i = 1;i <= q;i ++){ int l,r; scanf("%d%d",&l,&r); query[r].push_back(make_pair(l,i)); } //查询区间不同数的数量，右边界到哪加到哪 for (i = 1;i <= n;i ++){ //这里的思路，不是想着把查询分成1个三角形和一个直角梯形（事实证明这个思路有些复杂） //是把不同种类的数映射位置后放在数组上(若有重复则把数右移），以备区间查询 for (j = 0;j < gc[i].size();j ++){ int res = gc[i][j].first; int ind = gc[i][j].second; if (vis[res])//有相等的数则把数的头标签往右移 update(vis[res],-1); vis[res] = ind; update(ind,1); } for (j = 0;j < query[i].size();j ++){ int l = query[i][j].first; int ind = query[i][j].second; ans[ind] = getSum(i) - getSum(l - 1); } } for (i = 1;i <= q;i++){ printf("%d\n",ans[i]); }}int main(){ while(scanf("%d%d",&n,&q)!=EOF){ init(); input(); } return 0;}

hdu5869

1005 Seats

题意：有m个部门（部门数和分别的学生数不确定），部门学生数不确定，但一定不大于h，整个学校学生数L人，会场一排k个座位且L%k==0。问在任何情况下都能让同部门的学生一定坐一排的最少座位排数。

要让这些学生占据最多的行，就是说每行座位的空位正好无法再坐一个部门，比较简单的做法：先求出部门数较多的情况下空位最少时，每排部门数=k/h，那要让空位最多，并且让1个部门学生多得不能再坐，那能坐满排时1个部门学生数=k/(k/h+1)，让1排空出最多的位需要1个部门有且仅有r=k/(k/h+1)+1，那样每排部门数又是k/h，每排最少要排k-k%r，剩下的人可以另起1行或安排到其他排的空位上（但是他喵的数据错误了，后者的情况下把人塞到其他排会WA）

#include 
     
      #define INF 0x3f3f3f3f#define MOD 1000000007#define N 1123456using namespace std;long long n,m,sum,res,flag;int main(){    #ifndef ONLINE_JUDGE        freopen("test.txt","r",stdin);    #endif    long long i,j,cas,T,t,x,y,z,h,l,k;    while(scanf("%I64d%I64d%I64d",&h,&l,&k)!=EOF)    {        x=k/h;//最大人数时一排几个部门        y=k/(x+1);//多放一个部门时每个部门最多的人数        res=y+1;//加一个人保证不能多放一个部门        printf("%I64d\n",l/(k-k%res)+bool(l%(k-k%res)));//不是正解，数据正确的话会WA    }    return 0;}

1006 football game

题意不多说。

定理什么的，可以理解为n个人比赛，胜得2分平得1分，那n人总分就是n(n-1)

排序，再计算前q人的总分，由于没人的分数是负数，如果前q人总分超q(q-1)就不合理

最后的总分也必须是n(n-1)

#include
     
      using namespace std;const int maxn = 20000+6;int n,a[maxn];int main(){    int T;    while(scanf("%d",&T)!=EOF)    {        while(T--)        {            int res = 0;            scanf("%d",&n);            for(int i = 1;i<=n;i++)                scanf("%d",&a[i]),res+=a[i];            sort(a+1,a+1+n);            int sum = 0;            int flag = 0;            for(int i = 1;i<=n;i++)            {                sum+=a[i];                if(sum

1007 friends and emenies

脑洞多一点的人会想到把互为朋友的1对关系当成1对连边

如果3人互为朋友，那为3人的3对关系找3种珠子不如给3人1种珠子，相当于三元环

所以问题其实是n个点，没有三元环并且互相连通的图最多边数

没有三元环，就是说可以形成二分图；最多边数，就是说2个点集点数相差最小

边数n/2*(n-n/2)

再比较下实际有的珠子种类数就ok了

#include 
     
      using namespace std;typedef long long LL;int main(){    LL m,n;    while(~scanf("%I64d %I64d",&m,&n))    {        LL ans = m/2*(m-m/2);        if( ans <=  n)  puts("T");        else           puts("F");    }    return 0;}

1008 function

与1002差不多，都是那种1个左（右）边界对应logn种（m%n可能是m，也可能是小于m/2的某个数）数的题目

还是一样，离线查询，把所有的区间求出来，注意合并

不过这次不用事先求出所有对

并且储存方式也改为优先队列以防止多余处理（能模到小于原数的要入队，不能的不处理）

在右边界向右推进的同时更新对应左边界对应数

算法：离线+优先队列

#include 
      
       using namespace std;typedef unsigned long long ULL;typedef long long LL;const int INF = 0x3f3f3f3f;const double eps = 1e-9;const int maxn = 100000 + 100;typedef pair
       
         Pair;int ans[maxn], L[maxn];vector
        
          R[maxn];     //(L, id)priority_queue
         
           cal; //(num, pos)int main(){    int T, cas=1, n;    scanf("%d", &T);    while(T--)    {         while(!cal.empty()) cal.pop();        for(int i=0;i
          
           =L[i])            {                l = cal.top().second;                r = i;                L[l] = cal.top().first%L[i];                cal.pop();                cal.push(make_pair(L[l], l));            }            cal.push(make_pair(L[i], i));            for(int j=0;j