NOIP2014 解题报告·水渣记

Day 1:

第一次参加noip。小激动，小紧张，这些正常的情绪就不用说了。唯一值得一提的是我早上步行去郑大工学院的时候迷路了，直接转进了隔壁的河南农大，绕了半天找不到机房，还给几个同学打了电话可就是没人接……于是就在保安异样的目光下灰溜溜地走出了校门= =...然后还算好，总算提前半个小时来到了考点。。。

然后找座位的时候我遇到了奇怪的事情！！我的座位旁边是夏五岳……同校+同语言……天知道负责人的随机数生成器是出了什么问题= =不过看起来我们似乎没有被监考的志愿者盯上？那就这样吧= =于是，按照平时的习惯，我先敲好了头文件和快速读入……（别问我为什么还有快速读入……我只是懒得每次打scanf又怕cin被卡……）然后……看题……

A: 生活大爆炸版石头剪刀布

给出五种手势的胜负关系，A、B的出拳循环节和总共进行的轮数N，求游戏结束时两人各自的输赢次数。

N <= 200。N <= 200。N <= 200。N <= 200。

QAQ……请告诉我我没有看错数据范围。请告诉我200遍我没有看错数据范围。不对……我是不是走错考场考成普及组了？可是普及组不应该是下午比赛吗……好吧好吧，我再检查200遍题目就开始敲代码。。。

于是开考后三十分钟，我开始了无脑模拟。话说这题要是数据范围再大那么几个零是不是就可以变成数论题了？= = 看来出题人有着特别的送分技巧……就这么敲完了模拟。果断开下一题？算了还是再检查200遍题目吧……万一理解错了呢……

无脑模拟

然后开始了第二题：

B:联合权值

$无向联通图G有n个节点，n-1条边。点从1~n依次编号，编号为i的点权值为W_i，每条边长度均为1.$

$图上两点u,v的距离定义为u,v的最短距离。$

$对于图上的点对(u,v)，若它们的距离为2，则它们之间会产生W_u imes W_v的联合权值。$

$ 请问图上可能产生联合权值的有序点对中，联合权值最大的是多少？所有权值之和是多少？$

$n leq 200000$

好吧我终于敢确定自己没有报成普及组了……

首先看到无向连通图和n-1条边，可知这是一棵树……（可是您把这两条信息都放在开头和直接说这是一棵树的区别在哪里QAQ）

然后很容易就会想到用树分治的方法统计。于是dfs一下，讨论一下兄弟节点和祖孙节点就可……等等。。。没有那么麻烦！我可以直接枚举中点！

因为要求的是树上距离为2的点对，根据树上路径的存在性&唯一性，可知它们有且只有一个公共的邻接点。于是我们可以直接把这个中点拎出来，这时很容易看出它的所有邻接点两两之间都可以产生“联合权值”。那么我们求的所有权值之和就是$$sumlimits_{i=1}^N(sumlimits_{u,v in adj_i, u eq v} W_u imes W_v)$$

但是每个节点的所有邻接点“两两之间的乘积之和”怎么求呢……对于任意一个中点i，我们可以把表达式写成这样：$$S_i = sum_{j in adj_i} (W_j imes (sum_{k in adj_i} W_k) - W_j)$$ 然后合并同类项，就成了$$S_i ={ (sum_{j in adj_i} W_j)} ^ 2 - sum_{j in adj_i} W_j^2$$。这样对于每个中点i的处理就只需$O(|adj_i|)$的时间，而每条边只处在两个节点的邻接表中，因此总时间复杂度为$O(n)$。

然后……为什么数据是个$O(nlogn)$级别的规模呢……表示不解。。。难道我证错了？

1 /*========================================================*/
2 /*======================BY ASM.DEF========================*/
3 /*========================================================*/
4 #include <cstdio>
5 #include <iostream>
6 #include <cctype>
7 #include <cstring>
8 #include <cmath>
9 #include <algorithm>
10 #include <vector>
11 #include <queue>
12 #if defined DEBUG
13 FILE *in = fopen("test", "r");
14 #define out stdout
15 #else
16 FILE *in = fopen("linkb.in", "r");
17 FILE *out = fopen("linkb.out", "w");
18 #endif
19 #define pb push_back
20 #define iter(v) v::iterator
21 template<typename T> inline bool getd(T &x){
22     int c = fgetc(in);
23     bool minus = 0;
24     while(c != '-' && c != EOF && !isdigit(c))c = fgetc(in);
25     if(c == EOF)return 0;
26     if(c == '-'){
27         minus = 1;
28         x = 0;
29     }
30     else x = c - '0';
31     while(isdigit(c = fgetc(in)))x = x * 10 + c - '0';
32     if(minus)x = -x;
33     return 1;
34 }
35 using namespace std;
36 /*==========================================================*/
37 const int maxn = 200000 + 5, mod = 10007;
38 int n, W[maxn], pre[maxn] = {0}, Max = 0, Sum = 0;
39 vector<int> adj[maxn];
40
41 inline bool cmp(int a, int b){return W[a] > W[b];}
42
43 inline void calc(int cur){
44     iter(vector<int>) it;
45     int pow2S = 0, wS = 0;//平方和,权值和(sum_{i=1}^{N}(a_i (sum_{j=1}^N}a_j - a_i)) = wS^2 - pow2S)
46     int firmax = 0, secmax = 0;
47     for(it = adj[cur].begin();it != adj[cur].end();++it){
48         pow2S = (pow2S + W[*it] * W[*it]) % mod;
49         wS = (wS + W[*it]) % mod;
50         if(W[*it] > firmax)secmax = firmax, firmax = W[*it];
51         else if(W[*it] > secmax)secmax = W[*it];
52     }
53     Max = max(Max, firmax * secmax);
54     Sum = (Sum + wS * wS) % mod;
55     Sum = (Sum + mod - pow2S) % mod;
56 }
57
58 inline void work(){
59     int i, u, v;
60     getd(n);
61     for(i = 1;i < n;++i){
62         getd(u), getd(v);
63         adj[u].pb(v);
64         adj[v].pb(u);
65     }
66     for(i = 1;i <= n;++i)getd(W[i]);
67     for(i = 1;i <= n;++i)
68         calc(i);
69     fprintf(out, "%d %d ", Max, Sum);
70 }
71
72 int main(){
73
74     work();
75
76     #if defined DEBUG
77     cout << endl << (double)clock() / CLOCKS_PER_SEC << " sec" << endl;
78     #endif
79     return 0;
80 }

找公式

再然后……第三题改天再和day2一起写吧 ……反正我只写了70分算法= =

好了一周已经过去了......前几天发现我第二天太作死没有分试题建立文件夹，结果第二天的分数直接全0……据说按照我直接交上去的那份代码计算，这次还是可以拿到HA rank3的……这样一来，就相当于省rank3 -> 省三了= =真是醉……

我们再来看day1的第三题：

C:飞扬的小鸟

简化一下Flappy Bird, 在每个位置可以跳多次，跳一次上升$a_i$，如果不跳就下降$b_i$，问至少点击多少次能完成游戏（如果完成不了就输出最多能穿过多少缝隙）。

很容易发现这道题的动态规划性质，然后可以更容易地敲出$O(frac{nm^2}{a_i})$的算法= =然后发现最后三个测试点有可能会超时……因为我在做状态转移的时候对每一个位置都枚举了所有可能到达的上一位置，所以这个复杂度其实是依赖输入的……如果所有的$a_i$都很大，那么这个算法也可以很快求出结果，但如果出题人爱玩codeforces（神脑补），将所有$a_i$都设为1，那我就必然超时了……

好吧说了那么多，说白了还是我太弱。。。结束之后发现这题的转移中的“允许跳多次”其实可以转化为完全背包模型……或者说，在所有高度中“模$a_i$等价类”中的元素的“跳跃次数”是单调递增的= =

然后……这个完全背包的解法我懒得写了= =不过对于山寨版本的随机数据，我的写法跑得还是很快的>_<

  1 /*========================================================*/
  2 /*======================BY ASM.DEF========================*/
  3 /*========================================================*/
  4 #include <cstdio>
  5 #include <iostream>
  6 #include <cctype>
  7 #include <cstring>
  8 #include <cmath>
  9 #include <algorithm>
10 #include <vector>
11 #include <queue>
12 #if defined DEBUG
13 FILE *in = fopen("test", "r");
14 #define out stdout
15 #else
16 FILE *in = fopen("birda.in", "r");
17 FILE *out = fopen("birda.out", "w");
18 #endif
19 #define pb push_back
20 #define iter(v) v::iterator
21 template<typename T> inline bool getd(T &x){
22     int c = fgetc(in);
23     bool minus = 0;
24     while(c != '-' && c != EOF && !isdigit(c))c = fgetc(in);
25     if(c == EOF)return 0;
26     if(c == '-'){
27         minus = 1;
28         x = 0;
29     }
30     else x = c - '0';
31     while(isdigit(c = fgetc(in)))x = x * 10 + c - '0';
32     if(minus)x = -x;
33     return 1;
34 }
35 using namespace std;
36 /*==========================================================*/
37 const int maxn = 10000 + 5, maxm = 1000 + 5, INF = 0x3f3f3f3f;
38 int cnt[2][maxm] = {0};//循环数组
39 int n, m, k, X[maxn], Y[maxn], H[maxn], L[maxn] = {0};
40
41 inline void init(){
42     getd(n), getd(m), getd(k);
43     int i;
44     H[0] = m + 1;
45     for(i = 0;i < n;++i){
46         getd(X[i]), getd(Y[i]);
47         H[i+1] = m + X[i] + 1;//“撞到”？
48     }
49     while(k--){
50         getd(i);
51         getd(L[i]), getd(H[i]);
52     }
53 }
54
55 inline bool safe(int i, int h){
56     if(h >= H[i] || h <= L[i])return 0;
57     return 1;
58 }
59
60 inline void work(){
61     int i, j, k, t, score = 0;
62     bool ok;
63     for(i = 0;i < n;++i){
64         ok = 0;
65         memset(cnt[i&1^1], 0x3f, sizeof(int) * (m+2));
66         if(H[i] <= m)++score;
67         for(j = L[i]+1;j < min(H[i], m+1);++j){
68             if(cnt[i&1][j] != INF)ok = 1;
69             else continue;
70             if(safe(i+1, j-Y[i]))
71                 cnt[i&1^1][j-Y[i]] = min(cnt[i&1^1][j-Y[i]], cnt[i&1][j]);
72             for(k = j + X[i], t = 1;k < H[i+1];k += X[i],++t){
73                 if(k > m)k = m;
74                 if(safe(i+1, k))
75                     cnt[i&1^1][k] = min(cnt[i&1^1][k], cnt[i&1][j] + t);
76                 if(k == m)break;
77             }
78         }
79         if(!ok){
80             fprintf(out, "0 %d ", score - 1);
81             return;
82         }
83     }
84     int ans = INF;
85     for(i = 1;i <= m;++i)//若能到达n-1,则一定能到达n
86         ans = min(ans, cnt[n & 1][i]);
87     fprintf(out, "1 %d ", ans);
88 }
89
90 int main(){
91
92     init();
93
94     work();
95
96     #if defined DEBUG
97     cout << endl << (double)clock() / CLOCKS_PER_SEC << " sec" << endl;
98     #endif
99     return 0;
100 }

动态规划(转移方式稍有优化)

接下来……让我们来看我没有得分的day2:

A、无线网络发射器选址

还是送分题，直接枚举每个矩形然后累加就可以过……不过我强迫症发作写了二维前缀和- -

二维前缀和

B、寻找道路

算是半道送分题吧。。。我的做法是反向dfs预处理出“在路径上”的节点，然后只对这些点做spfa即可。（不过似乎直接反向spfa就可以了……蠢了蠢了....）

  1 /*======================================================*/
  2 /*========================ASM.DEF=======================*/
  3 /*======================================================*/
  4 #include <cstdio>
  5 #include <cctype>
  6 #include <iostream>
  7 #include <cmath>
  8 #include <cstring>
  9 #include <algorithm>
10 #include <vector>
11 #include <queue>
12 #include <deque>
13 #include <list>
14 using namespace std;
15 #if defined WJX_Asm_Def_DEBUG
16 FILE *in = fopen("test", "r");
17 #define out stdout
18 #else
19 FILE *in = fopen("roadb.in", "r");
20 FILE *out = fopen("roadb.out", "w");
21 #endif
22 inline bool getd(int &x){
23     int c = fgetc(in);
24     bool minus = 0;
25     while(c != '-' && c != EOF && !isdigit(c))c = fgetc(in);
26     if(c == EOF)return 0;
27     if(c == '-'){
28         x = 0;
29         minus = 1;
30     }
31     else x = c - '0';
32     while(isdigit(c = fgetc(in)))x = x * 10 - '0' + c;
33     return 1;
34 }
35 #define iter(v) v::iterator
36 #define pb push_back
37 #define pf push_front
38 #define ppf pop_front
39 /*===========================================================*/
40 const int maxn = 10000 + 5, INF = 0x3f3f3f3f;
41 list<int> adj[maxn];
42 vector<int> back[maxn];
43 int n, m, s, t;
44 int dis[maxn];
45 bool in_p[maxn] = {0}, known[maxn] = {0}, linked[maxn] = {0};
46
47 void dfs(int cur){//判断是否与t联通
48     iter(vector<int>) it;
49     for(it = back[cur].begin();it !=back[cur].end();++it){
50         if(!known[*it]){
51             linked[*it] = known[*it] = 1;
52             dfs(*it);
53         }
54     }
55 }
56
57 inline void init(){
58     getd(n), getd(m);
59     int x, y;
60     while(m--){
61         getd(x), getd(y);
62         if(x == y)continue;
63         adj[x].pb(y);
64         back[y].pb(x);
65     }
66     getd(s), getd(t);
67     linked[t] = 1, known[t] = 1, in_p[t] = 1;
68     dfs(t);
69     iter(list<int>) it;
70     for(int i = 1;i <= n;++i){
71         bool ok = 1;
72         for(it = adj[i].begin();it != adj[i].end();++it)
73             if(!linked[*it]){ok = 0;break;}
74         if(ok)in_p[i] = 1;
75         dis[i] = INF;
76     }
77 }
78 deque<int> Q;
79 bool inQ[maxn] = {0};
80 inline void work(){
81     if(!in_p[s]){fprintf(out, "-1 ");return;}
82     Q.pb(s), inQ[s] = 1, dis[s] = 0;
83     int k;
84     iter(list<int>) it;
85     while(!Q.empty()){
86         k = Q.front();inQ[k] = 0;Q.ppf();
87         for(it = adj[k].begin();it != adj[k].end();++it){
88             if(!in_p[*it]){
89                 it = adj[k].erase(it);
90                 --it;
91             }
92             else if(dis[k] + 1 < dis[*it]){
93                 dis[*it] = dis[k] + 1;
94                 if(inQ[*it])continue;
95                 inQ[*it] = 1;
96                 if(Q.empty() || dis[*it] <= dis[Q.front()])Q.pf(*it);//Small Label First
97                 else Q.pb(*it);
98             }
99         }
100     }
101     if(dis[t] == INF)fprintf(out, "-1 ");
102     else fprintf(out, "%d ", dis[t]);
103 }
104
105 int main(){
106     init();
107
108     work();
109
110     #if defined WJX_Asm_Def_DEBUG
111     cout << (double)clock() / CLOCKS_PER_SEC << endl;
112     #endif
113     return 0;
114 }

最短路

C、解方程

这是这次联赛最有水平的一道题…

首先因为我太弱没有写过hash，我以为这题正解是高精度的优化，然后看了好久就是找不到优化点……最后还是直接把高精度敲上了。。（反正也没分。。。）

最后，我看到了金策的题解……（传送门：http://uoj.ac/blog/24）然后照着思路仿写了一份，跑起来果然厉害...

  1 /*======================================================*/
  2 /*========================ASM.DEF=======================*/
  3 /*======================================================*/
  4 #include <cstdio>
  5 #include <cctype>
  6 #include <iostream>
  7 #include <cmath>
  8 #include <cstring>
  9 #include <algorithm>
10 #include <vector>
11 #include <queue>
12 #include <deque>
13 #include <ctime>
14 using namespace std;
15 #if defined WJX_Asm_Def_DEBUG
16 FILE *in = fopen("test", "r");
17 #define out stdout
18 #else
19 FILE *in = fopen("equationa.in", "r");
20 FILE *out = fopen("equationa.out", "w");
21 #endif
22 inline bool getd(int &x){
23     int c = fgetc(in);
24     bool minus = 0;
25     while(c != '-' && c != EOF && !isdigit(c))c = fgetc(in);
26     if(c == EOF)return 0;
27     if(c == '-'){
28         x = 0;
29         minus = 1;
30     }
31     else x = c - '0';
32     while(isdigit(c = fgetc(in)))x = x * 10 - '0' + c;
33     return 1;
34 }
35 #define iter(v) v::iterator
36 #define pb push_back
37 #define pf push_front
38 #define ppf pop_front
39 /*===========================================================*/
40 const int maxn = 100 + 3, maxm = 1000000 + 10, maxl = 10000 + 10;
41 int n, m, len[maxm] = {0}, a[maxn][maxl], amod[maxn] = {0};
42 bool neg[maxn] = {0};
43 int P[maxm], Pcnt = 0, basep;
44 bool not_ans[maxl] = {0};
45
46 inline void euler(){
47     bool not_p[maxl] = {0};
48     int i, j;
49     for(i = 2;i < maxl;++i){
50         if(!not_p[i])P[Pcnt++] = i;
51         for(j = 0;j < Pcnt;++j){
52             if(i * P[j] > maxl)break;
53             not_p[i * P[j]] = 1;
54             if(i % P[j] == 0)break;
55         }
56     }
57 }
58
59 inline void init(){
60     srand(time(NULL));
61     euler();
62     getd(n), getd(m);
63     int i, c;
64     for(i = 0;i <= n;++i){
65         c = fgetc(in);
66         while(!isdigit(c) && c != '-')c = fgetc(in);
67         if(c == '-'){
68             neg[i] = 1;
69             c = fgetc(in);
70         }
71         a[i][len[i]++] = c - '0';
72         while(isdigit(c = fgetc(in)))
73             a[i][len[i]++] = c - '0';
74     }
75 }
76
77 inline bool getamod(int p){
78     int i, j;
79     bool ans = 0;
80     for(i = 0;i <= n;++i){
81         amod[i] = a[i][0] % p;
82         for(j = 1;j < len[i];++j)
83             amod[i] = (amod[i] * 10 + a[i][j]) % p;
84         if(amod[i])ans = 1;
85     }
86     return ans;
87 }
88
89 inline int f(int x, int p){
90     int i, k = 1, ans = 0, t;
91     x %= p;
92     for(i = 0;i <= n;++i){
93         t = neg[i] ? p - amod[i] : amod[i];
94         ans = (ans + k * t) % p;
95         k = (k * x) % p;
96     }
97     return ans;
98 }
99
100 inline void work(){
101     int i, k, p, cnt = m;
102     bool not_A[maxm] = {0};
103     i = lower_bound(P, P + Pcnt, (int)sqrt((double)m * n)) - P;
104     basep = P[i];
105     while(!getamod(basep))basep = P[--i];
106     for(i = 0;i < basep;++i)
107         if(f(i, basep))not_ans[i] = 1;
108     k = 5;
109     while(k || cnt > n){
110         --k;
111         p = P[rand() % Pcnt];
112         while(!getamod(p))p = P[rand() % Pcnt];
113         for(i = 1;i <= m;++i){
114             if(not_A[i])continue;
115             if(not_ans[i % basep]){
116                 not_A[i] = 1;
117                 --cnt;
118                 continue;
119             }
120             if(f(i, p))not_A[i] = 1, --cnt;
121         }
122     }
123     fprintf(out, "%d ", cnt);
124     for(i = 1;i <= m;++i)
125         if(!not_A[i])
126             fprintf(out, "%d ", i);
127 }
128
129 int main(){
130     init();
131
132     work();
133
134     return 0;
135 }

分段,用hash判断