11.6 题解报告
2021/11/8 6:40:14
本文主要是介绍11.6 题解报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最后一个题没时间整理了,直接放的std
改天再回来看。(希望能回来)
T1 link
solution
考虑每个数的贡献。
记录每个点需要参与传递的回合数,因为所有点每个回合的传递都是同时完成的,最后对所有点取 \(max\) 就是答案。
一个点 \(i\) 参与的回合有这么几种情况。
设最后的平均值为 \(rev\)
- \(\sum_{j = 1}^{j = i - 1}a_j < rev \times (i - 1) ~\&\& \sum_{j = i + 1}^{j = n}a_j < rev \times (n - i)\)
\(i\) 点要向两边传递,答案就是向两边传递求和。
其他的情况:两边向中间传,从左到右传,从右到左;都是取 \(\max\),因为这些操作都是一步完成的。
code
#include<bits/stdc++.h> #define int long long using namespace std; const int MAXN = 1e5 + 5; int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();} return x * f; } int n, a[MAXN], sum[MAXN], Ans, rev; signed main() { n = read(); for (int i = 1; i <= n; i++) a[i] = read(), sum[i] = sum[i - 1] + a[i]; rev = sum[n] / n; for (int i = 1; i <= n; i++) { int l = sum[i - 1] - rev * (i - 1), r = (sum[n] - sum[i]) - rev * (n - i); if(l < 0 && r < 0) Ans = max(Ans, -l - r); else Ans = max(Ans, max(abs(l), abs(r))); } cout<<Ans; return 0; }
T2 pigeon
solution
所有数的顺序并不影响,按照所有数从小到大排序后可以转化为取倍数问题,设 \(f_i\) 表示最后所取得数是 \(i\) 的最大价值,转移就枚举上一个取得数就好了,用埃氏筛思路可以做到 \(O(nlogn)\)
code
#include<bits/stdc++.h> #define int long long using namespace std; const int MAXN = 1e6 + 5; int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();} return x * f; } int f[MAXN], cnt[MAXN], Ans, n; signed main() { n = read(); for (int i = 1; i <= n; i++) { int x = read(); cnt[x]++, f[x]++; } for (int i = 1; i <= 1000000; i++) { if(cnt[i]) Ans = max(Ans, f[i]); for (int j = i + i; j <= 1000000; j += i) if(cnt[i]) f[j] = max(f[j], f[i] + cnt[j]); } cout<<Ans; return 0; }
T3
solution
二分答案。
每次检验的时候会发现,一组卡牌中的一张选了会导致其他某组卡牌必须选另外一张,从而转化为 2-SAT 问题。
对于 所有卡牌战斗力的最大值减去最小值小于等于 100 的部分分,输出 0。
由于数据范围过大,无法直接 2-SAT 建图,注意到所有的边都是在一个区间里面的边,所以用线段树优化建图。
code
#include<cstdio> #include<cstdlib> #include<cstring> #include<cctype> #include<algorithm> using namespace std; const int BUF_SIZE = 30; char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1; #define PTR_NEXT() \ { \ buf_s ++; \ if (buf_s == buf_t) \ { \ buf_s = buf; \ buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \ } \ } #define readint(_n_) \ { \ while (*buf_s != '-' && !isdigit(*buf_s)) \ PTR_NEXT(); \ bool register _nega_ = false; \ if (*buf_s == '-') \ { \ _nega_ = true; \ PTR_NEXT(); \ } \ int register _x_ = 0; \ while (isdigit(*buf_s)) \ { \ _x_ = _x_ * 10 + *buf_s - '0'; \ PTR_NEXT(); \ } \ if (_nega_) \ _x_ = -_x_; \ (_n_) = (_x_); \ } #define readstr(_s_) \ { \ while (!isupper(*buf_s)) \ PTR_NEXT(); \ char register *_ptr_ = (_s_); \ while (isupper(*buf_s) || *buf_s == '-') \ { \ *(_ptr_ ++) = *buf_s; \ PTR_NEXT(); \ } \ (*_ptr_) = '\0'; \ } #define readlonglong(_n_) \ { \ while (*buf_s != '-' && !isdigit(*buf_s)) \ PTR_NEXT(); \ bool register _nega_ = false; \ if (*buf_s == '-') \ { \ _nega_ = true; \ PTR_NEXT(); \ } \ long long register _x_ = 0; \ while (isdigit(*buf_s)) \ { \ _x_ = _x_ * 10 + *buf_s - '0'; \ PTR_NEXT(); \ } \ if (_nega_) \ _x_ = -_x_; \ (_n_) = (_x_); \ } #define wmt 1,(n<<1),1 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn=200010; const int maxp=maxn+(maxn<<2); const int maxm=maxn+maxp+maxn*40; int n,size,cnt,en,t,dfn[maxp],low[maxp],s[maxp],belong[maxp],pos[maxn]; bool instack[maxp]; struct edge { int e; edge *next; }*v[maxp],ed[maxm]; void add_edge(int s,int e) { en++; ed[en].next=v[s];v[s]=ed+en;v[s]->e=e; } struct rec { int v,p; rec(){} rec(int a,int b) { v=a;p=b; } }z[maxn]; bool operator<(const rec &a,const rec &b) { return a.v<b.v; } void dfs(int p) { t++; dfn[p]=low[p]=t; instack[p]=true; s[++size]=p; for (edge *e=v[p];e;e=e->next) if (!dfn[e->e]) { dfs(e->e); low[p]=min(low[p],low[e->e]); } else { if (instack[e->e]) low[p]=min(low[p],dfn[e->e]); } if (dfn[p]==low[p]) { cnt++; while (s[size]!=p) { belong[s[size]]=cnt; instack[s[size]]=false; size--; } belong[p]=cnt; instack[p]=false; size--; } } void build(int l,int r,int rt) { if (l==r) { add_edge(rt+(n<<1),z[l].p<=n?z[l].p+n:z[l].p-n); return; } int m=(l+r)>>1; build(lson); build(rson); add_edge(rt+(n<<1),(rt<<1)+(n<<1)); add_edge(rt+(n<<1),(rt<<1|1)+(n<<1)); } void insert(int l,int r,int rt,int nowl,int nowr,int p) { if (nowl<=l && r<=nowr) { add_edge(p,rt+(n<<1)); return; } int m=(l+r)>>1; if (nowl<=m) insert(lson,nowl,nowr,p); if (m<nowr) insert(rson,nowl,nowr,p); } bool check(int k) { en=0;cnt=0; memset(v,0,sizeof(v)); memset(dfn,0,sizeof(dfn)); build(wmt); int r=1,l=1; for (int a=1;a<=(n<<1);a++) { int op,p=z[a].p; if (p<=n) op=pos[p+n]; else op=pos[p-n]; while (r<=a && z[r].v <= z[a].v-k) r++; if (r<a && r>=1 && z[r].v > z[a].v-k) { if (op>=r && op<=a-1) { if (op>r) insert(wmt,r,op-1,z[a].p); if (op<a-1) insert(wmt,op+1,a-1,z[a].p); } else insert(wmt,r,a-1,z[a].p); } while (l<=(n<<1) && z[l].v < z[a].v+k) l++; l--; if (l>a && l<=(n<<1) && z[l].v < z[a].v+k) { if (op>=a+1 && op<=l) { if (op>a+1) insert(wmt,a+1,op-1,z[a].p); if (op<l) insert(wmt,op+1,l,z[a].p); } else insert(wmt,a+1,l,z[a].p); } } for (int a=1;a<=(n<<1);a++) if (!dfn[a]) dfs(a); for (int a=1;a<=n;a++) if (belong[a]==belong[a+n]) return false; return true; } int main() { readint(n); int minv=0x3f3f3f3f,maxv=-0x3f3f3f3f; int x=0; for (int a=1;a<=n;a++) { int v1,v2; readint(v1); readint(v2); z[++x]=rec(v1,a); z[++x]=rec(v2,a+n); minv=min(minv,min(v1,v2)); maxv=max(maxv,max(v1,v2)); } if (maxv-minv+1 < n) { printf("0\n"); return 0; } sort(z+1,z+x+1); for (int a=1;a<=(n<<1);a++) pos[z[a].p]=a; int l=0,r=1000000001; while (l+1!=r) { int m=(l+r)>>1; if (check(m)) l=m; else r=m; } printf("%d\n",l); return 0; }
这篇关于11.6 题解报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求