今日头条”杯2018年湖北省赛(网络赛)

所有题目： http://cdn.vo-ov.cn/online_f9ec217.pdf

F: A-maze-ing（tarjan+缩点dfs找最长链）

哇我也是哭了...dfs写错，dfs还用了vis数组，实际上并不需要，WA了N多次...呜呜呜

看出来对图的基本概念还比较生疏，或者说都忘了好多，一开始还在纠结环是不是强连通分量...唉如果能果断点就好了

  1 #include <iostream>
  2 #include <string.h>
  3 #include <cstdio>
  4 #include <queue>
  5 #include <set>
  6 #include <cstring>
  7 #include <algorithm>
  8 
  9 #define SIGMA_SIZE 26
 10 #pragma warning ( disable : 4996 )
 11 
 12 using namespace std;
 13 typedef long long LL;
 14 
 15 inline LL LMax(LL a,LL b)    { return a>b?a:b; }
 16 inline LL LMin(LL a,LL b)    { return a>b?b:a; }
 17 inline int Max(int a,int b) { return a>b?a:b; }
 18 inline int Min(int a,int b) { return a>b?b:a; }
 19 inline int gcd( int a, int b ) { return b==0?a:gcd(b,a%b); }
 20 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm
 21 const int inf  = 0x3f3f3f3f;
 22 const int mod  = 7;
 23 const int maxn = 2e5+5;
 24 const int maxk = 200;
 25 
 26 struct edge {
 27     int to, next;
 28 }edges[maxn];
 29 
 30 struct edg{
 31     int to, next;
 32 }e[maxn];
 33 
 34 int N, M, cnt, sum;
 35 int order, iindex;
 36 int linjie[maxn], linjie_2[maxn], indeg[maxn], LOW[maxn];
 37 int DFN[maxn], belong[maxn], Stack[maxn];
 38 int num[maxn];
 39 bool vis[maxn];
 40 
 41 
 42 void addedge( int u, int v )
 43 {
 44     edges[cnt].to = v; edges[cnt].next = linjie[u]; linjie[u] = cnt++; }
 45 
 46 void addedge_2( int u, int v )
 47 { 
 48     e[cnt].to = v; e[cnt].next = linjie_2[u]; linjie_2[u] = cnt++; }
 49 
 50 void init()
 51 {
 52     cnt = order = iindex = sum = 0;
 53     memset( linjie, -1, sizeof(linjie) );
 54     memset( linjie_2, -1, sizeof(linjie_2) );
 55     memset( indeg, 0, sizeof(indeg) );
 56     memset( LOW, 0, sizeof(LOW) );
 57     memset( DFN, 0, sizeof(DFN) );
 58     memset( belong, 0, sizeof(belong) );
 59     memset( Stack, 0, sizeof(Stack) );
 60     memset( num, 0, sizeof(num) );
 61     memset( vis, 0, sizeof(vis) );
 62 }
 63 
 64 void tarjan( int x )
 65 {
 66     DFN[x] = LOW[x] = ++order;
 67     Stack[++iindex] = x;
 68     vis[x] = true;
 69     for( int i = linjie[x]; i+1; i = edges[i].next )
 70     {
 71         if (!DFN[edges[i].to])
 72         {
 73             tarjan(edges[i].to);
 74             LOW[x] = Min( LOW[x], LOW[edges[i].to] );
 75         }
 76         else if ( vis[edges[i].to] )
 77             LOW[x] = Min( LOW[x], DFN[edges[i].to] );
 78     }
 79 
 80     if ( LOW[x] == DFN[x] )
 81     {
 82         sum++;
 83         while( iindex )
 84         {
 85 
 86             int temp = Stack[iindex--];
 87             vis[temp] = false;
 88             belong[temp] = sum;
 89             if ( temp == x )
 90                 break;
 91         }
 92     }
 93 }
 94 
 95 void solve()
 96 {
 97     cnt = 0;
 98 
 99     for ( int i = 1; i <= N; i++ )
100         num[belong[i]]++;
101 
102     for ( int i = 1; i <= N; i++ )
103         for ( int j = linjie[i]; j+1; j = edges[j].next )
104             if ( belong[i] != belong[edges[j].to] )
105             {
106                 indeg[belong[edges[j].to]] = 1;
107                 addedge_2(belong[i], belong[edges[j].to]);
108             }
109 }
110 
111 void read()
112 {
113     int x, y;
114     for ( int i = 1; i <= M; i++ )
115     { 
116         scanf("%d %d", &x, &y); 
117         addedge(x, y);
118     }
119 }
120 
121 void find( int x )
122 {
123     if ( linjie_2[x] == -1 )
124     {
125         belong[x] = num[x];
126         return;
127     }
128 
129 
130     for ( int i = linjie_2[x]; i+1; i = e[i].next )
131     {
132         if (!belong[e[i].to])
133             find(e[i].to);
134         belong[x] = Max( belong[x], belong[e[i].to]+num[x] );
135     }
136     
137     return;
138 }
139 
140 int main()
141 {
142     while (~scanf("%d %d", &N, &M))
143     {
144         init();
145         read();
146 
147         for (int i = 1; i <= N; i++)
148             if (!DFN[i])
149                 tarjan(i);
150         solve();
151 
152         int ans = 0;
153         memset( belong, 0, sizeof(belong) );
154 
155         for (int i = 1; i <= sum; i++)
156             if (!indeg[i])
157             {
158                 find(i);
159                 ans = Max(ans, belong[i]);
160             }
161 
162         printf("%d
", ans);
163     }
164     return 0;
165 }

View Code

E：Jump a Jump

其实这是一类套路题...比赛时满脑子都是dpdpdp...实际上这类题目应该是用图论来做...这tm谁想到的啊？？

有一道相似的题目UESTC 1633 都是最短路来做，看一下那道题就知道这题该怎么做了，算法一样，只是最后求答案时判断不一样

实际上比如得到的m个数分别为a1~am，再假如x是这m个数构造任意出来的，那么x+a1一定也是可以被构造出来的

因为每个数字可以取无限次，那么只要选取一个最小的数（其实选任意数都可以，不过选最小可以让时间最优），假设是a1，再设一个数组dis[i]，(0=< i <a1)表示构造一个mod（a1）等于i时可得到的最小值

比如一共两个数字a1=3， a2 = 4。那么最小的数min = 3

所以dis[0]等于0，因为a1 mod min = 0

dis[1]等于4，因为4mod min = 1，而4显然可以被构造（虽然7mod min也等于1，而且也可被3和4构造出来，但是7比4大，所以最小的可以被构造的数是4）

dis[2]等于8，因为虽然5mod min = 2，但是5没办法被3和4构造，然后8mod min = 2，8显然可以被构造，所以dis[2]=8

这样做有什么用呢，其实发现只要求了所有dis[i]，那么这些数字全部能构造的数都可以表示成dis[i]+k*a1，自己想想就知道接下来怎么求答案了

  1 #include <iostream>
  2 #include <string.h>
  3 #include <cstdio>
  4 #include <queue>
  5 #include <set>
  6 #include <cstring>
  7 #include <algorithm>
  8 
  9 #define SIGMA_SIZE 26
 10 #pragma warning ( disable : 4996 )
 11 
 12 using namespace std;
 13 typedef long long LL;
 14 
 15 inline LL LMax(LL a,LL b)    { return a>b?a:b; }
 16 inline LL LMin(LL a,LL b)    { return a>b?b:a; }
 17 inline int Max(int a,int b) { return a>b?a:b; }
 18 inline int Min(int a,int b) { return a>b?b:a; }
 19 inline int gcd( int a, int b ) { return b==0?a:gcd(b,a%b); }
 20 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm
 21 const long long INF = 0x3f3f3f3f3f3f3f3f;
 22 const int inf  = 0x3f3f3f3f;
 23 //const int mod  = 7;
 24 const int maxn = 5005;
 25 const int maxk = 5005;
 26 
 27 struct edges {
 28     LL x, d;
 29     edges() { }
 30     edges( LL lg, LL id )
 31         : x(lg), d(id) { }
 32 };
 33 
 34 LL m, M;
 35 LL mod, dis[maxn];
 36 LL num[maxn];;
 37 bool vis[maxn];
 38 
 39 void dijkstra()
 40 {
 41     memset( vis, 0, sizeof(vis) );
 42     for ( int i = 0; i < mod; i++ )
 43         dis[i] = INF;
 44     dis[0] = 0;
 45 
 46     int mark;
 47     LL mindis;
 48     for ( int i = 0; i < mod; i++ )
 49     {
 50         mark = -1; mindis = INF;
 51         for ( int j = 0; j < mod; j++ )
 52             if ( !vis[j] && dis[j] < mindis )
 53             {
 54                 mindis = dis[j];
 55                 mark = j;
 56             }
 57         //cout << mark << endl;
 58 
 59         vis[mark] = true;
 60 
 61         for ( int j = 0; j < m; j++ )
 62             if ( (num[j] + mindis) < dis[(num[j] + mindis) % mod] )
 63             {
 64                 dis[(num[j] + mindis) % mod] = num[j] + mindis;
 65             }
 66     }
 67 }
 68 
 69 int main()
 70 {
 71     while ( ~scanf("%lld", &M ) )
 72     {
 73         cin >> m;
 74 
 75         mod = maxn;
 76         for ( int i = 0; i < m; i++ )
 77         {
 78             scanf( "%lld", &num[i] );
 79             mod = LMin(mod, num[i]);
 80         }
 81 
 82         dijkstra();
 83 
 84 
 85         LL ans = INF;
 86         for ( int i = 0; i < mod; i++ )
 87         {
 88             if ( dis[i] >= M )
 89                 ans = LMin( ans, dis[i] - M );
 90             else
 91             {
 92                 LL x = (M-dis[i])%mod;
 93                 LL y = LMin( x, mod - x );
 94                 ans = LMin( ans, y );
 95             }
 96         }
 97         printf( "%lld
", ans );
 98     }
 99 
100     return 0;
101 }

View Code

H：GSS and OJ Submissions（分块）

 1 #include <iostream>
 2 #include <string.h>
 3 #include <cstdio>
 4 #include <queue>
 5 #include <set>
 6 #include <vector>
 7 #include <cstring>
 8 #include <algorithm>
 9 
10 #define SIGMA_SIZE 26
11 #pragma warning ( disable : 4996 )
12 
13 using namespace std;
14 typedef long long LL;
15 typedef unsigned long long uLL;
16 
17 inline LL LMax(LL a,LL b)    { return a>b?a:b; }
18 inline LL LMin(LL a,LL b)    { return a>b?b:a; }
19 inline int Max(int a,int b) { return a>b?a:b; }
20 inline int Min(int a,int b) { return a>b?b:a; }
21 inline int gcd( int a, int b ) { return b==0?a:gcd(b,a%b); }
22 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm
23 const long long INF = 0x3f3f3f3f3f3f3f3f;
24 const int inf  = 0x3f3f3f3f;
25 const int mod  = 7;
26 const int maxk = 5005;
27 const int maxn = 2e6;
28 const uLL ddiv = 1e14;
29 
30 uLL A, B, L, n, s0;
31 int block[maxn];
32 vector<uLL> vec;
33 
34 int main()
35 {
36     scanf( "%llu%llu%llu%llu%llu", &A,&B,&L,&n,&s0 );
37     uLL tmp = s0;
38 
39     block[tmp/ddiv]++;
40     for ( int i = 1; i < n; i++ )
41     {
42         block[tmp/ddiv]++;
43         tmp = tmp*A + B;        //通过除以一个大数所得到的商不同来分类
44     }
45 
46     uLL l = L, pos = 0;
47     for ( int i = 0; i < maxn; i++ )
48     {
49         if ( L > block[i] )            //因为是递增序列，所以可以遍历一遍求的L在哪个块
50             L -= block[i];
51         else
52         {
53             pos = i;
54             break;
55         }
56     }
57 
58     tmp = s0;
59     for ( int i = 1; i <= n; i++ )
60     {
61         if ( tmp / ddiv == pos )
62             vec.push_back(tmp);
63         tmp = tmp*A + B;
64     }
65 
66     sort( vec.begin(), vec.end() ); 
67     printf( "%llu
", vec[L-1] );
68     
69     return 0;
70 }

View Code