再见,OIers,退役是新的开始!
2019-11-18 18:55:54 By admin
!!!!!!!!!!!!!本周任务【6月10日—6月16日】
2019-03-22 16:03:44 By admin
【5月27日—6月2日】
周三讲dp中的区间dp,提前看一看以下题目,本周要完成下列题目:
- Zuma https://www.luogu.org/problemnew/show/CF607B
- 石子合并 https://www.luogu.org/problemnew/show/P1880
- 能量项链 https://www.luogu.org/problemnew/show/P1063
- 凸多边形的划分 https://loj.ac/problem/10149
- 祖玛 https://www.luogu.org/problemnew/show/P2145
- 合唱队 https://www.luogu.org/problemnew/show/P3205
- 字符串折叠 https://www.luogu.org/problemnew/show/P4302
- 每天坚持打1个模板
- 周六上午测试
0316测试数据、题解、学生代码、标程下载
2019-03-16 11:31:46 By admin
提取码:8ds3
OJ自测:380,381,382
0309课堂代码
2019-03-09 10:47:30 By admin
p2678 rock 跳石头
#include<bits/stdc++.h>
using namespace std;
int L, N, M, a[50050], ans;
int s=1000000001, t;
int main()
{
cin>>L>>N>>M;
for(int i=1; i<=N; i++)
{
cin>>a[i];
s=min(s, a[i]-a[i-1]); //统计答案的下界
}
t=L/(N-M+1); //计算答案的上界
while(s<=t) //在[s,t]范围内折半查找
{
int m=(s+t)>>1;
int cnt=M, pre=a[0];
for(int i=1; i<=N; i++)
{
if((a[i]-pre)<m) //跨度不够,移石头
cnt--;
else
pre=a[i];
}
if(cnt>=0) s=m+1, ans=m; //当前m可行,在右边查找
else t=m-1; //当前m不行,在左边查找
}
if(!N) cout<<L<<endl; //一个坑,边界情况,N==0
else cout<<ans<<endl;
return 0;
}
p5021 road 赛道修建
#include<bits/stdc++.h>
using namespace std;
int n, m, s=0x7fffffff, t, head[50001], tot, ans, sum;
int fa[50001], c[50001];
struct edge
{
int to, val, next;
}E[100001];
void add(int x, int y, int z)
{
E[++tot].to=y;
E[tot].val=z;
E[tot].next=head[x];
head[x]=tot;
}
void dfs(int x)
{
for(int i=head[x]; i; i=E[i].next)
{
int y=E[i].to;
if(y==fa[x]) continue;
fa[y]=x;
dfs(y);
}
}
int dfs2(int x, int mid)
{
int ans=0;
multiset<int> tj;
for(int i=head[x]; i; i=E[i].next)
{
int y=E[i].to;
if(y==fa[x]) continue;
ans+=dfs2(y, mid);
if(c[y]+E[i].val>=mid) ans++;
else tj.insert(c[y]+E[i].val);
}
c[x]=0;
while(!tj.empty())
{
int u=*tj.begin();
tj.erase(tj.begin());
multiset<int>::iterator p=tj.lower_bound(mid-u);
if(p==tj.end())
{
c[x]=u;
}
else
{
tj.erase(p);
ans++;
}
}
tj.clear();
return ans;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<n; i++)
{
int a, b, l;
scanf("%d%d%d", &a, &b, &l);
add(a, b, l);
add(b, a, l);
s=min(s, l);
sum+=l;
}
t=sum/m;
fa[1]=1;
dfs(1);
while(s<=t)
{
memset(c, 0, sizeof(c));
int mid=(s+t)>>1;
if(dfs2(1, mid)>=m)
{
ans=mid;
s=mid+1;
}
else t=mid-1;
}
printf("%d\n", ans);
return 0;
}
0302Week01自测T1
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
long long a[1000010], n, K, ans1, ans2;
priority_queue<long long, vector<long long>, less<long long> > Q;
int main()
{
freopen("jkl.in", "r", stdin);
freopen("jkl.out", "w", stdout);
scanf("%lld%lld", &n, &K);
for(int i=0; i<n; i++) scanf("%lld", &a[i]), Q.push(a[i]);
sort(a, a+n);
for(int i=0, k2=K; k2; i++)
{
if(a[i])
{
if(k2<=a[i]) ans1+=((a[i]+a[i]-k2+1)*k2/2), k2=0;
else ans1+=((a[i]+1)*a[i]/2), k2-=a[i];
}
}
for(int i=1, t; i<=K; i++)
{
t=Q.top();
ans2+=t;
Q.pop();
Q.push(t-1);
}
printf("%lld %lld\n", ans2, ans1);
return 0;
}
0302Week01自测T2
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n, m, st[100005][65];
int main()
{
freopen("walk.in", "r", stdin);
freopen("walk.out", "w", stdout);
scanf("%lld%lld", &n, &m);
for(ll i=1; i<=n; i++) scanf("%lld", &st[i][0]);
for(ll k=1; k<=60; k++)
for(ll i=1; i<=n; i++)
st[i][k]=st[st[i][k-1]][k-1];
for(ll i=1; i<=m; i++)
{
ll a, b;
scanf("%lld%lld", &a, &b);
for(int i=0; i<63; i++)
{
if(b&1) a=st[a][i];
b>>=1;
}
printf("%lld\n", a);
}
return 0;
}
0302Week01自测T3
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=4e4+5, maxm=2e5+5;
int N, M, mst[maxn], f[maxn], ans;
double tot, avg, min_ans=1e30, dis[maxn], sum[maxn];
struct item
{
int u, v;
double d;
item(int x, int y, double z){u=x, v=y, d=z;}
friend bool operator<(const item &A, const item &R){ return A.d>R.d; }
};
struct edge
{
int t; double w; edge * nxt;
edge(int to, double len, edge * next)
{
t=to, w=len, nxt=next;
}
};
edge *h1[maxn], *h2[maxn];
void add1(int u, int v, double len)
{
h1[u]=new edge(v, len, h1[u]);
}
void add2(int u, int v, double len)
{
h2[u]=new edge(v, len, h2[u]);
}
double prim(int x)
{
memset(dis, 0x7f, sizeof(dis));
priority_queue<item, vector<item>, less<item> > Q;
double ret=0;
int num=1;
mst[x]=1;
for(edge * p=h1[x]; p; p=p->nxt)
if(p->t!=x) Q.push(item(x, p->t, p->w)), dis[p->t]=min(dis[p->t], p->w);
while(!Q.empty() && num!=N)
{
while(!Q.empty() && mst[Q.top().v]) Q.pop();
if(Q.empty()) break;
int t=Q.top().v;
mst[t]=true, ret+=Q.top().d, num++;
add2(Q.top().u, Q.top().v, Q.top().d);
add2(Q.top().v, Q.top().u, Q.top().d);
Q.pop();
for(edge *p=h1[t]; p; p=p->nxt)
if(!mst[p->t] && dis[p->t]>p->w) Q.push(item(t, p->t, p->w));
}
return ret;
}
void dfs(int x)
{
sum[x]=0;
for(edge *p=h2[x]; p; p=p->nxt)
{
if(p->t==f[x]) continue;
f[p->t]=x;
dfs(p->t);
sum[x]=sum[x]+p->w+sum[p->t];
}
}
int main()
{
freopen("mokou.in", "r", stdin);
freopen("mokou.out", "w", stdout);
scanf("%d%d", &N, &M);
for(int i=1, u, v; i<=M; i++)
{
double len;
scanf("%d%d%lf", &u, &v, &len);
add1(u, v, len), add1(v, u, len);
}
tot=prim(1); //求MST
dfs(1); //dfs求子树路径和
for(int i=1; i<=N; i++) //枚举每一个路口求权值
{
double e=0, t_sum=0;
vector<double> t;
for(edge *p=h2[i]; p; p=p->nxt)
{
if(p->t==f[i]) continue;
t.push_back(sum[p->t]+p->w);
t_sum+=sum[p->t]+p->w;
}
if(tot-t_sum>0) t.push_back(tot-t_sum);
avg=tot/(t.size()+1); //求平均值和方差
for(int j=0; j<t.size(); j++) e+=((t[j]-avg)*(t[j]-avg));
if(e<min_ans) min_ans=e, ans=i;
}
printf("%d\n", ans);
return 0;
}
travel AC代码(DFS找特定边删除)
2019-03-04 17:41:40 By admin
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MS=500050;
struct edge { int t; edge * nxt; edge(int to, edge * next){ t=to, nxt=next; } };
edge * h[MS];
int n, m, f[MS], q[MS], cnt, sp, spi, inc[MS], pmax[MS], tmax[MS];
void add(int u, int v) { h[u]=new edge(v, h[u]); }
void dfs1(int x)
{
q[++cnt]=x;
inc[x]=1;
for(edge * p=h[x]; p && !sp; p=p->nxt)
{
if(p->t==f[x]) continue;
if(inc[p->t]) sp=p->t;
else f[p->t]=x, dfs1(p->t);
}
if(!sp) inc[x]=0, cnt--;
}
int clearINC(){ int i=1; while(q[i]!=sp) inc[q[i++]]=0; return i; }
void cut(int u, int v)
{
edge * p=h[u];
if(h[u]->t==v) h[u]=h[u]->nxt; else { while(p->nxt->t!=v) p=p->nxt; p->nxt=p->nxt->nxt; }
}
void dfs3(int x)
{
//cout<<"here: "<<x<<endl;
int nextx;
tmax[x]=inc[x]?0:x;
for(edge *p=h[x]; p; p=p->nxt)
{
if(p->t==f[x]) continue;
if(inc[p->t]) { nextx=p->t; continue; }
f[p->t]=x;
dfs3(p->t);
tmax[x]=max(tmax[x], tmax[p->t]);
}
if(inc[x])
{
pmax[x]=tmax[f[x]];
if(pmax[x]<x) pmax[x]=pmax[f[x]];
//cout<<"Pmax:"<<pmax[x]<<" nextx:"<<nextx<<" tmax:"<<" "<<tmax[x]<<endl;
if((nextx<x || nextx<tmax[x] || (nextx>tmax[x] && nextx<pmax[x]))&&nextx!=sp) f[nextx]=x, dfs3(nextx);
else cut(x, nextx), cut(nextx, x);
}
}
void findAndCut(int x)
{
memset(f, 0, sizeof(f));
if(q[spi+1]<q[cnt]) f[q[spi+1]]=sp, tmax[sp]=q[cnt], dfs3(q[spi+1]); else f[q[cnt]]=sp, tmax[sp]=q[spi+1], dfs3(q[cnt]);
}
void dfs2(int x)
{
printf("%d ", x);
int c=0, temp[MS];
for(edge * p=h[x]; p; p=p->nxt) if(p->t!=f[x]) temp[c++]=p->t;
sort(temp, temp+c);
for(int i=0; i<c; i++) f[temp[i]]=x, dfs2(temp[i]);
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=m; i++){ int u, v; scanf("%d%d", &u, &v); add(u, v); add(v, u); }
if(n==m){ f[1]=1; dfs1(1); spi=clearINC(); findAndCut(1); }
memset(f, 0, sizeof(f));
f[1]=1;
dfs2(1);
return 0;
}