Nowcoder 提高组练习赛-R7

　　https://www.nowcoder.com/acm/contest/179#question

　　中间空了两场，因为实在是太难了...

　　第五场的第二题好像还比较可做，是一个最小生成树的结论题，注意到$2^i$可以认为是二进制下的数，即使把比它小的所有$2^x$全加起来也还是比他小,这一点做题的时候可以用一下.

　　第六场的第一题是一道很奇怪的题目,给图上的每条边赋一个权值,求从每个点出发的最长路以及整条路径上所有数字组成一个高进制数的最大字典序(注意最长路可能有很多条).这道题首先缩点,如果走到环里了就是无限长,求出最长路,然后建反图.按照最长路的长度降序排序,再更新前面的值,但是这么做只有$60$分,因为只考虑了每个点前一条边的数字大小,如果有两条边的数字是一样的,就成了随机选择,但是沿着这条边接着走时可能就会发现两条路径一优一劣了.所以好像还要根据每个点目前的字典序大小对边排序...?好麻烦啊.

　　今天的题看起来好像简单一点?

　　A:https://www.nowcoder.com/acm/contest/179/A

　　题意概述:小清新模拟题.

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <string>
 5 # include <cmath>
 6 # include <algorithm>
 7 # define R register int
 8 # define ll long long
 9  
10 using namespace std;
11  
12 const int dx[]={-1,-1,-1,0,0,1,1,1};
13 const int dy[]={-1,0,1,-1,1,-1,0,1};
14 const int maxn=202;
15 int n,m,k,r,no,T,x,y,w;
16 int act[maxn][maxn],ope[maxn][maxn],vis[maxn][maxn];
17  
18 int main()
19 {
20     scanf("%d%d%d",&n,&m,&k);
21     no=k;
22     for (R i=1;i<=n;++i)
23         for (R j=1;j<=m;++j)
24         {
25             scanf("%d",&r);
26             if(r>0) act[i][j]=r;
27             else act[i][j]=-1;
28         }
29     for (R i=1;i<=n;++i)
30         for (R j=1;j<=m;++j)
31             scanf("%d",&ope[i][j]);
32     scanf("%d",&T);
33     while(T--)
34     {
35         scanf("%d%d",&x,&y);
36         if(ope[x][y]==0)
37         {
38             printf("-1 -1");
39             return 0;
40         }
41         if(vis[x][y])
42         {
43             printf("-1 -1");
44             return 0;
45         }
46         if(no<10&&act[x][y]==-1)
47         {
48             printf("-1 -1");
49             return 0;
50         }
51         if(act[x][y]==-1)
52         {
53             w+=10;
54             no-=10;
55         }
56         else no+=act[x][y];
57         if(no>=k) no=k;
58         vis[x][y]=true;
59         for (R d=0;d<8;++d)
60         {
61             int xx=x+dx[d];
62             int yy=y+dy[d];
63             if(xx<1||xx>n||yy<1||yy>m) continue;
64             ope[xx][yy]=true;
65         }
66     }
67     printf("%d %d",no,w);
68     return 0;
69 }

　　B:https://www.nowcoder.com/acm/contest/179/B

　　题意概述:每个数字有一种颜色，连到以$1$为根的一棵树上，每个点的父亲必须是它的一个因数，同一颜色且连在一起的算一个联通块，求通过合理的连边能制造的最多联通块。

　　看起来像是个很难的题目，但是其实贪心就行，只要能连到颜色不同的父亲上就连，不能连就连到$1$上即可.复杂度$O(Nsqrt{N})$.更合理的做法是对于每一个数字枚举倍数,运用调和级数计算复杂度$O(NlogN)$

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <string>
 5 # include <cmath>
 6 # include <algorithm>
 7 # define R register int
 8 # define ll long long
 9  
10 using namespace std;
11  
12 const int maxn=500005;
13 int n,a[maxn],f[maxn],ans,fa,t;
14  
15 int main()
16 {
17     scanf("%d",&n);
18     ans=1;
19     for (R i=1;i<=n;++i)
20         scanf("%d",&a[i]);
21     for (R i=2;i<=n;++i)
22     {
23         fa=0;
24         for (R j=1;j*j<=i;++j)
25         {
26             if(i%j) continue;
27             t=j;
28             if(fa==0&&a[t]!=a[i])
29                 f[i]=t,ans++,fa=true;
30             if(j==1) continue;
31             t=i/j;
32             if(fa==0&&a[t]!=a[i])
33                 f[i]=t,ans++,fa=true;
34         }
35         if(!fa) f[i]=1;
36     }
37     printf("%d",ans);
38     return 0;
39 }

　　C:https://www.nowcoder.com/acm/contest/179/C

　　题意概述：一个$n$个点$m$条边的无权图，给出多组询问问是否有从$u$到$v$走恰好$l$步的方案数;$n<=100,q<=1000,l<=10^9$

　　非常板子的矩阵乘法!然而跑的非常慢,于是首先按照询问的$l$排序,分段进行矩阵乘法.然而...爆零了!为什么?离线做之后一定要记得还原成原来的顺序输出！！！

　　改过来也过不了,听说改成倍增+$bitset$就过了.最近牛客网怎么总是出这种有点卡常的题目啊.

  1 # include <cstdio>
  2 # include <iostream>
  3 # include <cstring>
  4 # include <string>
  5 # include <cmath>
  6 # include <algorithm>
  7 # define R register int
  8 # define ll long long
  9  
 10 using namespace std;
 11  
 12 const int maxn=104;
 13 int n,m,u,v,q,l,t[1005];
 14 struct mat
 15 {
 16     int a[maxn][maxn];
 17     void init()
 18     {
 19         memset(a,0,sizeof(a));
 20         for (R i=1;i<=n;++i)
 21             a[i][i]=1;
 22     }
 23 }a,ans,y;
 24 struct ask
 25 {
 26     int l,u,v,id;
 27 }s[1005];
 28 bool cmp (ask a,ask b)
 29 {
 30     return a.l<b.l; 
 31 }
 32  
 33 mat mul (mat a,mat b)
 34 {
 35     mat c;
 36     memset(c.a,0,sizeof(c.a));
 37     for (R i=1;i<=n;++i)
 38         for (R j=1;j<=n;++j)
 39             for (R k=1;k<=n;++k)
 40             {
 41                 if(a.a[i][k]&&b.a[k][j]) c.a[i][j]=1;
 42                 if(c.a[i][j]) break;
 43             }
 44     return c;
 45 }
 46  
 47 mat qui (mat a,int b)
 48 {
 49     mat ans;
 50     ans.init();
 51     while(b)
 52     {
 53         if(b&1) ans=mul(ans,a);
 54         a=mul(a,a);
 55         b=b>>1;
 56     }
 57     return ans;
 58 }
 59  
 60 inline char gc()
 61 {
 62   static char now[1<<22],*S,*T;
 63   if (T==S)
 64   {
 65     T=(S=now)+fread(now,1,1<<22,stdin);
 66     if (T==S) return EOF;
 67   }
 68   return *S++;
 69 }
 70 inline int read()
 71 {
 72   R x=0;
 73   register char ch=gc();
 74   while(!isdigit(ch))
 75     ch=gc();
 76   while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=gc();
 77   return x;
 78 }
 79  
 80 int main()
 81 {
 82     n=read(),m=read();
 83     for (R i=1;i<=m;++i)
 84     {
 85         u=read(),v=read();
 86         a.a[u][v]=true;
 87     }
 88     y=a;
 89     q=read();
 90     for (R i=1;i<=q;++i)
 91         s[i].l=read(),s[i].u=read(),s[i].v=read(),s[i].id=i;
 92     sort(s+1,s+1+q,cmp);
 93     ans.init();
 94     for (R i=1;i<=q;++i)
 95     {
 96         int p=s[i].l-s[i-1].l;
 97         if(p)
 98         {
 99             a=qui(y,p);
100             ans=mul(ans,a);        
101         }
102         if(ans.a[ s[i].u ][ s[i].v ]) t[ s[i].id ]=1;
103     }
104     for (R i=1;i<=q;++i)
105         if(t[i]) puts("YES");
106         else puts("NO");
107     return 0;
108 }

　　---shzr