首页 > 代码库 > 2016 ICPC 大连网络赛 部分题解

2016 ICPC 大连网络赛 部分题解

  先讲1007,有m个人,n种石头,将n种石头分给m个人,每两个人之间要么是朋友关系,要么是敌人关系,朋友的话他们必须有一种相同颜色的石头,敌人的话他们必须所有石头的颜色都不相同。另外,一个人可以不拥有任何一种石头。求m个人的所有关系是不是都能用n种石头表示出来。比赛当时找的关系是n种石头可以表示n+1个人的关系。但是一直WA,因为考虑不周。

  我们考虑这样的一种情况,我们把人分为左边和右边两部分,每边的人里面都互相为敌人,同时左边的任意一个人和右边的任意一个人都是朋友。举个例子,左边有3人,右边两人。考虑左边第一人,他和右边每一个人都要有相同的至少一种石头,那么他至少要有两种石头,而左边的每一个人的每一个石头都不能一样,那么至少要有3*2=6种石头。通过这个例子我们就可以找出规律来了,总共需要的石头量为左右人数之积。

  那么问题就转化成了,将m个人分成两组,使得乘积最大(这是m个人下的最坏的情况,如果这个情况都能满足,那么其他情况也都能满足了)。显然,将m个人均分一下得到的乘积最大,那么答案就出来了。

  代码如下:

技术分享
 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 typedef long long ll; 6  7 int main() 8 { 9     int n,m;10     while(scanf("%d%d",&n,&m)==2)11     {12         int l = n/2;13         int r = n-n/2;14         if(1LL*l*r > m) puts("F");15         else puts("T");16     }17 }
View Code

 

  1006,当时比赛的时候是乱做弄出来的,只要满足下面3个条件即可:

  假设有n个队伍,

  1.每个队伍的分数都不能超过2*(n-1)。

  2.所有队伍的总分必须等于n*(n-1)。

  3.分数为奇数的队伍数必须是偶数个,每两个队伍之间都有一场平局。

  但是,题解给出的方法似乎是有一个定理的(Landau‘s Theorem

  先将分数从小到大排序一下,那么对任意前i个人的总分,必须不小于他们所能够得到的分数,即i*(i-1),同时总分必须是n*(n-1)。

  另外,如果没有平局,并且只是胜者获得1分,同样可以使用这个定理,只要改变前i个人所能获得的分数即可,即C(i,2),同时,总分也必须等于C(n,2)。

 

  1009,当时比赛的时候m的大小是5500,那么可以在数据规模较小的情况下暴力求补图,数据规模较大的时候找规律来做(因为数据规模较大的时候点数远远大于边数,那么一定是不止一个联通块,规律就是如果与s点相邻,距离就是2,因为可以先到另外一个联通块再到这个点来完成,如果不相邻距离就是1了,因为补图上直接可达)。现在m的数据范围变大了,得采用题解的方法,在补图上bfs。代码如下(直接看代码也是可以看懂的):

技术分享
 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <queue> 5 #include <set> 6 using namespace std; 7 typedef long long ll; 8 const int N = 200000 + 5; 9 10 vector<int> G[N];11 int n,m,s;12 int dis[N];13 14 void addEdge(int u,int v)15 {16     G[u].push_back(v);17 }18 19 void solve()20 {21     set<int> sa,sb;22     // 每次扩展都是向不相邻的边扩展23     // sb保存的是仍未bfs过的点24     queue<int> Q;25     for(int i=1;i<=n;i++) if(i!=s) sa.insert(i);26     Q.push(s);27     memset(dis,-1,sizeof(dis));28     dis[s] = 0;29     while(!Q.empty())30     {31         int x = Q.front();Q.pop();32         for(int i=0;i<G[x].size();i++)33         {34             int v = G[x][i];35             if(!sa.count(v)) continue;36             sa.erase(v);37             sb.insert(v);38         }39         for(set<int>::iterator it = sa.begin();it!=sa.end();it++)40         {41             dis[*it] = dis[x] + 1;42             Q.push(*it);43         }44         sa.swap(sb);45         sb.clear();46     }47     int fir = 0;48     for(int i=1;i<=n;i++)49     {50         if(i!=s)51         {52             if(fir) printf(" ");53             else fir = 1;54             printf("%d",dis[i]);55         }56     }57     puts("");58 }59 60 int main()61 {62     int T;scanf("%d",&T);63     while(T--)64     {65         scanf("%d%d",&n,&m);66         for(int i=1;i<=n;i++) G[i].clear();67         68         for(int i=1;i<=m;i++)69         {70             int u,v;scanf("%d%d",&u,&v);71             addEdge(u,v);72             addEdge(v,u);73         }74         75         scanf("%d",&s);76         solve();77     }78 }
View Code

 

   1008,题意是给一个区间L和R,求a[L]%a[L+1]%a[L+2]...%a[R]。

  一个性质:a%b,如果a小于b,那么a不变,否则,得到的数小于等于a/2(这个性质不知道要怎么证,不过似乎就是这样的样子- -)。

  那么每次取余以后都会减半,那么复杂度就是log级别的了。

  那么,我们每次找出[L+1,R]中第一个不比最左边的数大的数的位置,并不断的缩小区间即可。关于如何找,这里用了线段树来维护一个区间内的最小值,那么我们就可以用线段树找出我们需要的东西了~具体见代码:

技术分享
 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <queue> 5 #include <set> 6 #define t_mid (l+r >> 1) 7 #define ls (o<<1) 8 #define rs (o<<1 | 1) 9 #define lson ls,l,t_mid10 #define rson rs,t_mid+1,r11 using namespace std;12 typedef long long ll;13 const int N = 100000 + 5;14 15 int a[N],c[N<<2],n;16 void build(int o,int l,int r)17 {18     if(l==r) {c[o] = a[l];return;}19     build(lson);20     build(rson);21     c[o] = min(c[ls],c[rs]);22 }23 24 int query(int ql,int qr,int o,int l,int r,int x)25 {26     if(l==r)27     {28         if(c[o] <= x) return l;29         else return -1;30     }31     int ans = -1;32     if(t_mid >= ql && c[ls] <= x)33     {34         ans = query(ql,qr,lson,x);35         if(ans == -1)36         {37             if(t_mid < qr && c[rs] <= x) ans = query(ql,qr,rson,x);38         }39         return ans;40     }41     else if(t_mid < qr && c[rs] <= x) return query(ql,qr,rson,x);42     return -1;43 }44 45 int main()46 {47     int T;scanf("%d",&T);48     while(T--)49     {50         scanf("%d",&n);51         for(int i=1;i<=n;i++) scanf("%d",a+i);52         build(1,1,n);53         54         int q;scanf("%d",&q);55         while(q--)56         {57             int ql,qr;scanf("%d%d",&ql,&qr);58             int now = a[ql];59             while(ql < qr)60             {61                 ql = query(ql+1,qr,1,1,n,now);62                 if(ql == -1) break;63                 now %= a[ql];64             }65             printf("%d\n",now);66         }67     }68 }
线段树维护

当然,也可以使用单调栈来维护,代码如下(只有主程序部分的代码):

技术分享
 1 int a[N],nxt[N]; 2 stack<int> s; 3 int main(){ 4     int T,n,m,l,r; 5     cin >> T; 6     while(T --){ 7         memset(nxt,-1,sizeof(nxt)); 8         while(!s.empty()) s.pop(); 9         cin >> n;10         for(int i = 1 ; i <= n ; i ++) scanf("%d",&a[i]);11         cin >> m;12         for(int i = 1 ; i <= n ; i ++){13             // 单调递增的栈。14             if(s.empty() || a[i] >= a[s.top()]) s.push(i);15             else{16                 while(!s.empty() && a[i] < a[s.top()]){17                     nxt[s.top()] = i;18                     s.pop();19                 }20                 s.push(i);21             }22         }23         while(m --){24             scanf("%d%d",&l,&r);25             int ret = a[l] , tmp = l;26             while(nxt[tmp] <= r && nxt[tmp] != -1){27                 tmp = nxt[tmp];28                 ret = ret % a[tmp];29             }30             cout << ret << endl;31         }32     }33     return 0;34 }
单调栈维护

 

  

 

2016 ICPC 大连网络赛 部分题解