碎碎念
两周996，全款拿下air5！
因为没有打多校，打打华为赛弥补一下
虽然只过了四道题，但是第二难的被我过了！
（虽然我觉得这道题真的很简单就是了）
最终rank43，纪念一下~
《第一份兼职》大结局-Day13
今天是最后一天了嘿嘿嘿
吃饭的时候ll就给我发工资了（笑出声）
然后没过多久就花完了emm
晚上是普及组信心赛，结果打到一半有人就快AK了
于是临时加了一道题（
苦的我讲题前几分钟才赶完solution
总的来说，两周的兼职还是很不错哒！
（指工资
--------碎碎念到此结束，下面是正文（手动分割线）--------
A - 95计费法
给一个长度为 n 的序列 a[1..n]，将其分为 m 段（不可为空），使得每段的 95 分位点大小之和最小。
95 分位点：区间第 len−⌊0.05×len⌋ 小的数，len 表示区间长度（元素个数）。
solution
区间dp
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int T,n,m,a[110],b[110],dp[110][110][110],f[110][110][10];
priority_queue<int>q;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
for(int k=i;k<=j;k++)
q.push(a[k]);
int len=int(0.05*(j-i+1))+1;
for(int k=1;k<=len;k++)
f[i][j][k]=q.top(),q.pop();
while(!q.empty())q.pop();
}
dp[1][1][1]=a[1];
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=n;k++)
if(dp[i][j][k]!=-1)
{
if(dp[i+1][j+1][1]==-1)dp[i+1][j+1][1]=dp[i][j][k]+a[i+1];
else dp[i+1][j+1][1]=min(dp[i+1][j+1][1],dp[i][j][k]+a[i+1]);
int len1=int(0.05*k)+1,len2=int(0.05*(k+1))+1;
if(dp[i+1][j][k+1]==-1)dp[i+1][j][k+1]=dp[i][j][k]-f[i-k+1][i][len1]+f[i-k+1][i+1][len2];
else dp[i+1][j][k+1]=min(dp[i+1][j][k+1],dp[i][j][k]-f[i-k+1][i][len1]+f[i-k+1][i+1][len2]);
}
int ans=inf;
for(int i=1;i<=n;i++)
if(dp[n][m][i]!=-1)
ans=min(ans,dp[n][m][i]);
printf("%d\n",ans);
}
return 0;
}B - 客户预警
为了减少用户流失，流失预警就显得尤为重要。我们希望可以引入参数 k1,k2,p，如果一个用户近 k1 个月的平均贡献收入少于近 k2 个月的平均贡献收入的 p%，那么就认为需要给出预警。
具体来说，给定某客户 n 个月贡献的收入，你需要给出一个只含"0""1"的字符串，第 i 个字符表示第 i 个月是否需要给出预警，"1"表示需要，"0"表示不需要。特别地，如果当前的月数不足 k2，则认为不需要给出预警。
solution
模拟
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int T,n,a[1000010],k1,k2,p;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d%d%d",&k1,&k2,&p);
ll x1=0,x2=0;
for(int i=1;i<k2;i++)
printf("0"),x2+=a[i];
for(int i=1;i<=k1;i++)
x1+=a[k2-i];
for(int i=k2;i<=n;i++)
{
x2+=a[i]-a[i-k2];
x1+=a[i]-a[i-k1];
if(100*k2*x1<x2*p*k1)
printf("1");
else printf("0");
// printf("%d %d %d %d %d\n",k2,x1,x2,p,k1);
}
printf("\n");
}
return 0;
}C - 直播
直播网络可以看作是一幅 n 个节点、m 条边的有向无环连通图，1 号节点是该地区的骨干节点，即直播数据到达该地区的第一个节点，其余节点用 vi=0 表示普通路由节点，vi=1 表示 CDN 节点，vi=2 表示观看直播的用户节点。普通路由节点只能做转发工作（任何进入该点的数据都被唯一地转发出去）；CDN 节点可以将收到的直播数据缓存并无限转发；用户节点需要接收自己的数据，同时也可以当作普通路由节点转发其他数据。每条边有一个权值 ci，表示该边的带宽，若有 x 项传输工作使用该边，则每项传输工作在该边的传输速率为 ⌊ci/x⌋。
你需要为每个用户安排一条数据通道（即从 1 号节点到该用户节点的路径）。每个用户观看直播的实际带宽为其数据传输工作在路径上的最小传输速率。由于实际带宽会影响延时，进而对直播效果产生较大影响，你需要使得所有用户的最小实际带宽越大越好。
solution
比赛的时候就想到二分答案，正解是二分答案之后跑网络流
需要注意的点就是cdn点的处理，这里我们需要暴力枚举每一个cdn点取或不取
不取的cdn点直接删去，取的cdn点满足如下性质：
一定有1的流量经过它，之后它可以变为具有源点性质的点
那么自然就会有如下转化：
将cdn点向汇点连一条流量为1的边，从源点向原cdn点能到达的点连一条与原来权值相同的边
然后Dinic一遍，看汇点是否流满了用户节点与cdn节点
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s,t,ans;
int cnt,head[60],edge[1000],to[1000],nxt[1000];
int dep[60],cur[60];
queue<int>q;
int bfs()
{
memset(dep,-1,sizeof(dep));
memcpy(cur,head,sizeof(head));
dep[s]=0,q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i!=-1;i=nxt[i])
{
int v=to[i],w=edge[i];
if(dep[v]!=-1||edge[i]==0)continue;
dep[v]=dep[u]+1,q.push(v);
}
}
return dep[t]!=-1;
}
int dfs(int u,int f)
{
if(u==t)return f;
int ret=f;
for(int i=cur[u];i!=-1&&ret;i=nxt[i])
{
cur[u]=i;
int v=to[i],w=edge[i];
if(w==0||dep[v]<=dep[u])continue;
int r=dfs(v,min(ret,w));
if(r==-1)continue;
ret-=r,edge[i]-=r,edge[i^1]+=r;
}
return f-ret;
}
int opt[60],cnt1,cnt2;
int id[60],co;
//1->CDN,2->Users
int u[210],v[210],w[210];
void add_edge(int u,int v,int w)
{
cnt++,edge[cnt]=w,to[cnt]=v,nxt[cnt]=head[u],head[u]=cnt;
cnt++,edge[cnt]=0,to[cnt]=u,nxt[cnt]=head[v],head[v]=cnt;
}
bool check(int p)
{
int maxx=1<<cnt1;
for(int S=0;S<maxx;S++)
{
int ans=0,coo=0;cnt=-1;
for(int i=s;i<=t;i++)head[i]=-1;
add_edge(s,1,inf);
for(int i=1;i<=n;i++)
if(opt[i]==2)
add_edge(i,t,1);
else if(opt[i]==1)
{
if(S >> id[i] & 1)
add_edge(i,t,1);
}
for(int i=1;i<=m;i++)
{
if(w[i]<p)continue;
if(opt[u[i]]==0||opt[u[i]]==2)
add_edge(u[i],v[i],w[i]/p);
else if(S >> id[u[i]] & 1)
add_edge(s,v[i],w[i]/p);
}
while(bfs())ans+=dfs(s,inf);
if(ans==cnt2+__builtin_popcount(S))return 1;
}
return 0;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
cnt1=0,cnt2=0,co=0,opt[1]=0;
scanf("%d%d",&n,&m),s=0,t=n+1;
for(int i=2;i<=n;i++)
{
scanf("%d",&opt[i]);
if(opt[i]==1)cnt1++,id[i]=co++;
else if(opt[i]==2)cnt2++;
}
for(int i=1;i<=m;i++)
scanf("%d%d%d",&u[i],&v[i],&w[i]);
int l=1,r=1e6,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
l=mid+1,
ans=mid;
else r=mid-1;
}
printf("%d\n",ans);
}
return 0;
}D - 机器人
题意（待更）
solution
题解（待更）
E - 带权子集和
题意（待更）
solution
题解（待更）
F - 信道定向
有一个地区有 n 个用户，标号为 1,⋯,n。他们希望接入网络，但由于该地区较为落后，他们只能规划使用 m 条单向信道，第 i 条信道连接 ui,vi 两个用户，方向未定。
你需要为这些信道定向。定向完毕后，设第 i 个用户的入度为 indgi，出度为 outdgi，他们将会购买流量套餐，第 i 个用户需要支付的费用为 max(indgi,outdgi)。因此你需要求出一种定向方案，使得所有用户的最大费用最小。若有多种方案，任意输出一种即可。
solution
类似于一笔画问题
#include<bits/stdc++.h>
#define N 200010
#define M 1000010
#define MM 2000010
using namespace std;
int T,n,m,d[N],a[M],b[M];
char ans[M];
int cnt,head[N],to[MM],pre[MM],nxt[MM];
inline int read()
{
register int s=0;
register char ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-'0',ch=getchar();
return s;
}
inline void add(int u,int v)
{
to[++cnt]=v;
pre[cnt]=-1,nxt[cnt]=head[u];
pre[head[u]]=cnt,head[u]=cnt;
}
inline void del(int i,int u)
{
if(pre[i]!=-1)nxt[pre[i]]=nxt[i];
if(nxt[i]!=-1)pre[nxt[i]]=pre[i];
if(head[u]==i)head[u]=nxt[i];
}
void dfs(int u)
{
for(int i=head[u];i!=-1;i=nxt[i])
{
while(ans[(i+1)/2]!='&')
{
del(i,u),i=nxt[i];
if(i==-1)return;
}
d[u]--,d[to[i]]--;
ans[(i+1)/2]=(u==b[(i+1)/2]?'1':'0');
del(i,u),dfs(to[i]);return;
}
}
int main()
{
T=read();
while(T--)
{
n=read(),m=read(),cnt=0;
for(int i=1;i<=n;i++)d[i]=0,head[i]=-1;
for(int i=1;i<=m;i++)
{
a[i]=read(),b[i]=read();
d[a[i]]++,d[b[i]]++,ans[i]='&';
add(a[i],b[i]),add(b[i],a[i]);
}
for(int i=1;i<=n;i++)if(d[i]%2)dfs(i);
for(int i=1;i<=n;i++)if(d[i])dfs(i);
for(int i=1;i<=m;i++)putchar(ans[i]);
putchar('\n');
}
return 0;
}G - 三角函数
现在小蒟蒻手上有一个数 m=0，每次操作它可以使用 sin, cos 和 arctan 中的一个作用于 m 得到 m′。小蒟蒻有一个幸运数字 根号下p分之q ，保证 p≤q 且 gcd(p,q)=1。小蒟蒻想知道能否在 2q 次操作内将 m 从 0 变到他的幸运数字呢？如果可以请输出其中任意一种方案，如果无解请输出 Noooooooo!。
为了简化方案的输出，我们记 sin 为 s， cos 为 c， arctan 为 t，输出的第 i 个字符表示第 i 次的操作类型。例如 sct 表示 arctan(cos(sin(0)))。
solution
找到规律之后递归
#include<bits/stdc++.h>
using namespace std;
int T,p,q;
void solve(int x,int y)
{
if(x==y)printf("sc");
else{
if(y-x<x)
{
x=y-x;
solve(x,y-x);
printf("tc");
}
else
{
solve(x,y-x);
printf("ts");
}
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&p,&q);
solve(p,q),putchar('\n');
}
return 0;
}
Comments NOTHING