1009 Sparse Graph（hdu5876）

由于每條邊的權值都為1，所以最短路bfs就夠了，只是要求轉置圖的最短路，所以得用兩個set來維護，一個用來存儲上次擴散還沒訪問的點，一個用來存儲這一次擴散還沒訪問的點。

算法：bfs+set

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<string.h> 5 #include<queue> 6 #include<vector> 7 #include<stack> 8 #include<set> 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<int>s,e; 38 set<int>::iterator it; 39 queue<node>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<m;i++){ 74 scanf("%d%d",&u,&v); 75 add(u,v); 76 add(v,u); 77 } 78 int pos; 79 scanf("%d",&pos); 80 bfs(pos); 81 if(n!=pos){ 82 for(int i=1;i<=n;i++) 83 { 84 if(i==pos)continue; 85 if(i!=n) 86 printf("%d ",di[i]!=INF?di[i]:-1); 87 else 88 printf("%d\n",di[i]!=INF?di[i]:-1); 89 } 90 91 }else{ 92 for(int i=1;i<=n-2;i++) 93 { 94 if(1!=(n-1)) 95 printf("%d ",di[i]!=INF?di[i]:-1); 96 else 97 printf("%d\n",di[i]!=INF?di[i]:-1); 98 } 99 100 } 101 } 102 return 0; 103 } View Code

1010 Weak Pair（hdu5877）

題意是要求所有節點的權值與其祖先節點權值相乘小于或等于k的總共有多少對，一開始知道必須得進行dfs，也知道可以馬上建一個數組b[n]來記錄每個節點需要和小于多少的數相乘才會小于看，但是在查詢有多少個祖先節點小于b[i]時沒有找到方法，后來才知道，可以將數據離散化后存進樹狀數組，只保留當前節點的父節點在樹狀數組當中，一旦離開這個節點，就把這個節點的權值在樹狀數組中刪除

算法：dfs+離散化+BIT

1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<string.h> 5 #include<vector> 6 #include<queue> 7 #include<stack> 8 using namespace std; 9 #define ll long long 10 const int maxn=100100; 11 int n; 12 ll k,a[maxn]; 13 vector<int>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<son[rt].size();i++){ 42 int nex=son[rt][i]; 43 ans+=dfs(nex); 44 } 45 Add(ran[rt], -1); 46 ll num=upper_bound(a+1,a+1+n,b[rt])-a-1; 47 ans+=Sum(num); 48 return ans; 49 } 50 int main() 51 { 52 //freopen("input.txt","r",stdin); 53 int t; scanf("%d", &t); 54 while(t--) 55 { 56 scanf("%d%lld",&n,&k); 57 init(n); 58 for(int i=1;i<=n;i++){ 59 scanf("%lld",&a[i]); 60 ran[i] = a[i]; 61 if (a[i] != 0) 62 b[i] = k / a[i]; 63 else 64 b[i] = 0; 65 } 66 67 int u,v; 68 for(int i=1;i<=n-1;i++){ 69 scanf("%d%d",&u,&v); 70 son[u].push_back(v); 71 in[v]++; 72 } 73 sort(a+1,a+1+n); 74 unique(a+1,a+1+n); 75 for(int i=1;i<=n;i++){ 76 ran[i]=lower_bound(a+1,a+n+1,ran[i])-a; 77 } 78 int root=1; 79 for(int i=1;i<=n;i++){ 80 if(in[i]==0) 81 root=i; 82 } 83 ll ans=dfs(root); 84 printf("%lld\n",ans); 85 } 86 return 0; 87 } 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 <bits/stdc++.h> 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 <cstdio> #include <iostream> #include <cstring> #include <vector> #include <stack> #include <set> #include <queue> #include <algorithm> #define lowbit(x) (x & (-x)) using namespace std; typedef __int64 ll; typedef pair<int,int> pii; const int MAXN = 1e5 + 8;int a[MAXN]; int ans[MAXN]; vector<pii> gc[MAXN]; vector<pii> 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 <bits/stdc++.h> #define INF 0x3f3f3f3f #define MOD 1000000007 #define N 1123456 using namespace std; long long n,m,sum,res,flag; int main() {#ifndef ONLINE_JUDGEfreopen("test.txt","r",stdin);#endiflong 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<bits/stdc++.h> 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<i*(i-1)){flag=1;break;}}if(res!=n*(n-1))flag=1;if(flag)printf("F\n");elseprintf("T\n");}} }

1007 friends and emenies

腦洞多一點的人會想到把互為朋友的1對關系當成1對連邊

如果3人互為朋友，那為3人的3對關系找3種珠子不如給3人1種珠子，相當于三元環

所以問題其實是n個點，沒有三元環并且互相連通的圖最多邊數

沒有三元環，就是說可以形成二分圖；最多邊數，就是說2個點集點數相差最小

邊數n/2*(n-n/2)

再比較下實際有的珠子種類數就ok了

#include <bits/stdc++.h> 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 <bits/stdc++.h> 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<int, int> Pair; int ans[maxn], L[maxn]; vector<Pair> R[maxn]; //(L, id) priority_queue<Pair> 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<maxn;++i) R[i].clear();scanf("%d", &n);for(int i=1;i<=n;++i) scanf("%d", &L[i]);int l, r, q;scanf("%d", &q);for(int i=1;i<=q;++i)//把所有右邊界相等的元素歸一起，這是只有區間查詢時的常用策略 {scanf("%d%d", &l, &r);R[r].push_back(make_pair(l, i));}for(int i=1;i<=n;++i){int l, r;//處理能改變結果的查詢，用堆防止過多訪問變成O(n^2)//注意1個左邊界最多得到O(log2n)種結果while(!cal.empty()&&cal.top().first>=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<R[i].size();++j){l = R[i][j].first;ans[R[i][j].second] = L[l];}}for(int i=1;i<=q;++i) printf("%d\n", ans[i]);}return 0; } hdu5875

轉載于:https://www.cnblogs.com/dgutfly/p/5874406.html

總結

以上是生活随笔為你收集整理的2016 ACM/ICPC Asia Regional Dalian Online的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。