首页 > 代码库 > 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 }
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 }
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 }
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 }
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 }
2016-11-15NOIP模拟赛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。