首页 > 代码库 > 2016-11-15NOIP模拟赛

2016-11-15NOIP模拟赛

AM学军OJ

T1 暴力

技术分享
 1 #include<bits/stdc++.h> 2   3 using namespace std; 4   5 typedef long long LL; 6 const int N = 2000000 + 10; 7   8 int len, power; 9  10 int get_next(int x) {11     return x / 10 + x % 10 * power;12 }13  14 int vis[N], clk;15  16 LL calc(int l, int r) {17     LL ans = 0;18     for(int i = l; i <= r; i++) if(vis[i] != clk) {19         int c = 0, x = i;20         for(int j = 0; j < len; j++) {21             if(l <= x && x <= r && vis[x] != clk) {22                 vis[x] = clk, c++;23             }24             //cout << x << endl;25             x = get_next(x);26         }27         //cout << "--" << ans << endl;28         ans += c * (c - 1) / 2;29     }30     return ans;31 }32  33 int main() {34  35     int T;36     scanf("%d", &T);37     while(T--) {38         //memset(vis, 0, sizeof vis);39         clk++;40         int l, r, x;41         scanf("%d%d", &l, &r); x = l;42         for(len = 0, power = 1; x; x /= 10) len++, power *= 10;43         power /= 10;44         //cerr << "!" << endl;45         //printf("%d\n", calc(l, r));46         cout << calc(l, r) << endl;47     }48  49  50     return 0;51 }
View Code

 

T2 最短路 比赛的时候统计方案的时候由u更新v的最短路以后直接把到v的最短路方案赋为1而不是u的方案数。

技术分享
 1 #include<bits/stdc++.h> 2    3 using namespace std; 4    5 const int N = 100 + 5, mod = 1000000009; 6    7 int d[N][N], g[N][N], f[N][N], n; 8 bool done[N][N]; 9   10 int encode(int x, int y) {11     return x << 15 | y;12 }13 void discode(int s, int &x, int &y) {14     x = s >> 15;15     y = s & ((1 << 15) - 1);16 }17   18 typedef pair<int, int> pii;19   20 priority_queue<pii, vector<pii>, greater<pii> > q;21   22 void insert(int x, int y, int z, int k) {23     if(d[x][y] > z) {24         d[x][y] = z;25         f[x][y] = k;26         q.push(pii(z, encode(x, y)));27     } else if(d[x][y] == z) {28         f[x][y] += k;29         if(f[x][y] >= mod) f[x][y] -= mod;30     }31 }32   33 const int dx[] = {0, 0, 1, -1};34 const int dy[] = {1, -1, 0, 0};35   36 bool inmap(int x, int y) {37     return 0 <= x && x < n && 0 <= y && y < n;38 }39   40 void dijkstra() {41     memset(done, 0, sizeof done);42     memset(d, 0x3f, sizeof d);43     insert(0, 0, g[0][0], 1);44     while(!q.empty()) {45         int x, y;46         discode(q.top().second, x, y); q.pop();47         if(done[x][y]) continue;48         done[x][y] = 1;49         if(x + y == n - 1) continue;50         for(int k = 0; k < 4; k++) {51             int xx = x + dx[k], yy = y + dy[k];52             if(!inmap(xx, yy)) continue;53             insert(xx, yy, d[x][y] + g[xx][yy], f[x][y]);54         }55     }56 }57   58 int main() {59     while(~scanf("%d", &n) && n) {60         for(int i = 0; i < n; i++) {61             for(int j = 0; j < n; j++) {62                 scanf("%d", g[i] + j);63                 if(i + j >= n) {64                     int x = n - 1 - j, y = n - 1 - i;65                     //printf("(%d,%d) (%d,%d)\n", i, j, x, y);66                     g[x][y] += g[i][j];67                     g[i][j] = 0;68                 }69             }70         }71         dijkstra();72         int ans = ~0u >> 1, res = 0;73         for(int i = 0; i < n; i++) {74             ans = min(ans, d[i][n - i - 1]);75         }76         for(int i = 0; i < n; i++) {77             if(d[i][n - i - 1] == ans) {78                 (res += f[i][n - i - 1]) %= mod;79             }80         }81         printf("%d\n", res);82     }83     return 0;84 }
View Code

 

T3 题目转化为对于$n$个二元组$(e_1,e_2)e_1,e_2$代表两条边,如果这两条边中的一条加入了图中,则对答案贡献1,图不能成环,求答案的最大值。

如果不是二元组而是一元组也就是一条边,就用最大生成树即可,最大生成树为什么是对的呢?拟阵可以证明。也就是说对于任意一个中间状态,如果这条边能够加进来(即没有自环),那么一定有一种最优解会包含这条边,用在这里也同理。当我们想加入一个二元组的时候,如果$e_1,e_2$中的一条可以直接加进去,那就直接加进去,如果都不能,就考虑删掉环上一条边,而删掉了这条边就要加入那个二元组的另一条边,这类似于二分图最大匹配的过程。

 

PM

T1 二分答案

技术分享
 1 #include<bits/stdc++.h> 2  3 using namespace std; 4  5 const int N = 200000 + 10; 6  7 int L[N], R[N], S[N]; 8 int n; 9 10 bool check(double v) {11     double T = 0;12     for(int i = 0; i < n; i++) {13         T += S[i] / v;14         if(T > R[i]) return 0;15         if(T < L[i]) T = L[i];16     }17     return 1;18 }19 20 int main() {21     freopen("express.in", "r", stdin);22     freopen("express.out", "w", stdout);23 24     scanf("%d", &n);25     for(int i = 0; i < n; i++) {26         scanf("%d%d%d", L + i, R + i, S + i);27     }28     double l = 0, r = 1e15;29     check(0);30     while(r - l > 1e-4) {31         double mid = (l + r) / 2;32         if(check(mid)) r = mid;33         else l = mid;34     }35 36     printf("%.2f\n", l);37     return 0;38 }
View Code

 

T2 dp 在比赛的时候,只写了j <= i而没有写j <= K导致数组溢出,数组只开了101却用到了101这个位置。

技术分享
 1 #include<bits/stdc++.h> 2  3 using namespace std; 4  5 const int N = 500 + 10; 6  7 int n, K; 8  9 char s[N];10 11 int f[N][105][105][2]; // 前i位改变了j个0和k个1,第i位为l12 13 void maxit(int &x, int y) {14     if(x < y) x = y;15 }16 17 int main() {18     freopen("welcome.in", "r", stdin);19     freopen("welcome.out", "w", stdout);20     cerr << ((sizeof f) >> 20) << endl;21 22     scanf("%d%d", &n, &K);23 24     scanf("%s", s + 1);25     for(int i = 1; i <= n; i++) {26         s[i] = s[i] == z;27     }28 29     memset(f, -0x3f, sizeof f);30     if(s[1] == 0) {31         f[1][0][0][0] = 0;32         f[1][1][0][1] = 0;33     }34     else {35         f[1][0][0][1] = 0;36         f[1][0][1][0] = 0;37     }38     for(int i = 1; i < n; i++) {39         for(int j = 0; j <= i && j <= K; j++) {40             for(int k = 0; j + k <= i && k <= K; k++) {41                 int t1 = max(f[i][j][k][0], f[i][j][k][1]),42                     t2 = max(f[i][j][k][0] + 1, f[i][j][k][1]);43                 if(s[i+1] == 0) {44                     maxit(f[i+1][j][k][0], t1);45                     maxit(f[i+1][j+1][k][1], t2);46                 } else {47                     maxit(f[i+1][j][k][1], t2);48                     maxit(f[i+1][j][k+1][0], t1);49                 }50             }51         }52     }53 54     int ans = 0;55 56     for(int i = 0; i <= K; i++) {57         maxit(ans, f[n][i][i][0]);58         maxit(ans, f[n][i][i][1]);59     }60 61     printf("%d\n", ans);62 63     return 0;64 }
View Code

 

T3

题目描述】
A是某公司的CEO,每个月都会有员工把公司的盈利数据送给A,A是个与众不同的怪人,A不注重盈利还是亏本,而是喜欢研究“完美序列”:连续的互不相同的序列。A想知道区间[L,R]之间最长的完美序列。
【输入格式】
第一行两个整数N,M(1<=N,M<=200000),N表示连续N个月,编号为0到N-1,M表示询问的次数。第二行N个整数(绝对值不超过106),第i个数表示该公司第i个月的盈利值。接下来M行每行两个整数L,R(0<=L<=R<=N-1),表示A询问的区间。
【输出格式】
输出M行,每行一个整数对应询问区间内的完美序列的最长长度。
【样例输入】
9 2
2 5 4 1 2 3 6 2 4
0 8
2 6
4 8
【样例输出】
6
5
4

 

这道题网上普遍流传着一个算法,就是统计出以每个位置为前缀的最长长度,这个显然是不减的,然后对于询问区间内的最最长度,前一段可能超过了$L_i$,这时取最靠右的位置,后面一段没有超过,直接询问最大值。

我的做法是在线段树上加上等差数列的标记,并需要离线处理。

技术分享
 1 #include<bits/stdc++.h> 2  3 using namespace std; 4  5 typedef pair<int, int> pii; 6 #define FI first 7 #define SE second 8 const int N = 200000 + 10; 9 10 #define mid ((l + r) >> 1)11 #define ls s << 1, l, mid12 #define rs s << 1 | 1, mid + 1, r13 int tag[N * 4], val[N * 4];14 15 void add_tag(int s, int l, int r, int d) {16     tag[s] = max(tag[s], d);17     val[s] = max(val[s], d);18 }19 20 void down(int s, int l, int r) {21     add_tag(ls, tag[s]);22     add_tag(rs, tag[s] - (mid - l + 1));23 }24 25 void modify(int s, int l, int r, int L, int R) {26     if(L <= l && r <= R) return add_tag(s, l, r, (R - L + 1) - (l - L));27     down(s, l, r);28     if(L <= mid) modify(ls, L, R);29     if(mid < R) modify(rs, L, R);30     val[s] = max(val[s], val[s << 1]);31     val[s] = max(val[s], val[s << 1 | 1]);32 }33 34 int query(int s, int l, int r, int L, int R) {35     if(L <= l && r <= R) return val[s];36     down(s, l, r);37     int res = 0;38     if(L <= mid) res = max(res, query(ls, L, R));39     if(mid < R) res = max(res, query(rs, L, R));40     return res;41 }42 43 int n, m, a[N];44 int ql[N], qr[N], id[N], ans[N];45 bool vis[2000000 + 10];46 47 bool cmp(int a, int b) {48     return qr[a] < qr[b];49 }50 51 int main() {52     freopen("diff.in", "r", stdin);53     freopen("diff.out", "w", stdout);54 55     scanf("%d%d", &n, &m);56     for(int i = 0; i < n; i++) {57         scanf("%d", a + i); a[i] += 1000000;58     }59     for(int i = 0; i < m; i++) {60         scanf("%d%d", ql + i, qr + i);61         id[i] = i;62     }63     sort(id, id + m, cmp);64     for(int l = 0, r = 0, i = 0; r < n; r++) {65         while(vis[a[r]]) {66             vis[a[l++]] = 0;67         }68         vis[a[r]] = 1;69         modify(1, 0, n-1, l, r);70         while(i < m && qr[id[i]] == r) {71             ans[id[i]] = query(1, 0, n-1, ql[id[i]], r);72             i++;73         }74     }75     76     for(int i = 0; i < m; i++) {77         printf("%d\n", ans[i]);78     }79     return 0;80 }
View Code

 

2016-11-15NOIP模拟赛