2019.01.26【NOIP提高组】模拟 A&B 组
ZYC和ZZY太强了
前言
由于A&B组题目相同，所以说一起写，但是貌似……A组第三题不会做
B组部分
JZOJ 1252 洛谷 5194 天平
题目
在个数中选择若干个，使它们的和不超过且最大
分析
倒序dfs，并用前缀和优化
代码
#include <cstdio>
#include <algorithm>
#define rr register
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int n; long long c,a[41],s[41],ans;
inline void dfs(int dep,long long sum){
if (s[dep-1]<=c-sum) ans=max(ans,s[dep-1]+sum);
else{
ans=max(ans,sum);
for (rr int i=dep-1;i;--i)
if (c-sum>=a[i]) dfs(i,sum+a[i]);
}
}
signed main(){
scanf("%d%lld",&n,&c);
for (rr int i=1;i<=n;++i){
scanf("%lld",&a[i]);
if (a[i]>c) i--,n--;
else s[i]=s[i-1]+a[i];
}
dfs(n+1,0);
return !printf("%lld",ans);
}
JZOJ 1274 游历路线
题目
从1号点到号点，不能停留，在每一个周期每条单向路有一定的费用，问到第天的最小费用
代码（线性动态规划）
#include <cstdio>
#include <cstring>
#include <cctype>
#define rr register
using namespace std;
int n,m,w[101][101][21],dp[201][101];
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline signed min(int a,int b){return (a<b)?a:b;}
signed main(){
freopen("lines.in","r",stdin);
freopen("lines.out","w",stdout);
n=iut(); m=iut();
memset(w,127/3,sizeof(w));
for (rr int i=1;i<=n;++i)
for (rr int j=1;j<=n;++j) if (i!=j){
w[i][j][0]=iut();
for (rr int k=1;k<=w[i][j][0];++k){
w[i][j][k]=iut();
if (!w[i][j][k]) w[i][j][k]=707406378;
}
}
memset(dp,127/3,sizeof(dp)); dp[0][1]=0;
for (rr int i=1;i<=m;++i)
for (rr int j=1;j<=n;++j) if (dp[i-1][j]!=707406378)
for (rr int now=1;now<=n;++now) if (j!=now)
dp[i][now]=min(dp[i][now],dp[i-1][j]+w[j][now][(i-1)%w[j][now][0]+1]);
if (dp[m][n]!=707406378) printf("%d",dp[m][n]); else putchar(48);
return 0;
}
A&B组部分
JZOJ 4224 食物
题目
分析
那么只要美味度满足要求的食物大小总和可以用这些工具装好，那么计算工具的最小费用即为答案，为什么呢，因为食物可以拆开，但是不满足部分背包
所以这道题可以分成两部分
- 找到满足美味度的最小的空间
- 求出工具的最小费用
这些都可以通过多重背包(二进制拆分变为01背包)实现，但是问题是直接维护空间很难完成第二步，于是可以玄学的把它反转，设表示空间为的最大美味度，那么容易得到,然后只要那么对取最小值，然后取到这个最小值再用一遍多重背包求得答案
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int M=50000; int f[M+105],dp[M+5];
struct rec{int w,c;}a[1201],b[1201];
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void min(int &a,int b){if (a>b) a=b;}
inline void max(int &a,int b){if (a<b) a=b;}
signed main(){
for (rr int t=iut();t;--t){
rr int n1=iut(),n2=iut(),p=iut(),i1,poi=M+1,ans=M+1;
for (i1=n1,n1=0;i1;--i1){//二进制拆分
rr int w=iut(),c=iut(),t=iut();
for (rr int j=1;t>=j;t-=j,j<<=1)
a[++n1]=(rec){w*j,c*j};
if (t) a[++n1]=(rec){w*t,c*t};
}
for (i1=n2,n2=0;i1;--i1){
rr int c=iut(),w=iut(),t=iut();
for (rr int j=1;t>=j;t-=j,j<<=1)
b[++n2]=(rec){w*j,c*j};
if (t) b[++n2]=(rec){w*t,c*t};
}
fill(f+1,f+M+101,100001); f[0]=0;
for (rr int i=1;i<=n1;++i)
for (rr int j=M+100;j>=a[i].w;--j){//可能还会超过一点点
min(f[j],f[j-a[i].w]+a[i].c);
if (j>=p) min(poi,f[j]);
}
fill(dp+1,dp+M+1,-100001); dp[0]=0;
for (rr int i=1;i<=n2;++i)
for (rr int j=ans;j>=b[i].w;--j){
max(dp[j],dp[j-b[i].w]+b[i].c);
if (dp[j]>=poi) min(ans,j);
}
if (ans>M) printf("TAT\n"); else printf("%d\n",ans);
}
return 0;
}
A组部分
JZOJ 4223 旅游
题目
询问有多少个无序点对至少有一条最大边权不超过的路径
分析
那么这道题适合离线处理，用并查集维护连通块的大小，从小到大排序边权，从小到大排序，然后对于每一个询问，多出来的就是
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
struct node{int x,y,w;}e[100001];
struct rec{int w,rk;}a[5001];
int n,m,q,f[20001],son[20001],ans[5001];
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline signed getf(int u){return (f[u]==u)?u:f[u]=getf(f[u]);}
bool cmp1(node a,node b){return a.w<b.w;}
bool cmp2(rec x,rec y){return x.w<y.w;}
signed main(){
for (rr int t=iut();t;--t){
n=iut(); m=iut(); q=iut();
for (rr int i=1;i<=m;++i) e[i]=(node){iut(),iut(),iut()};
for (rr int i=1;i<=n;++i) son[f[i]=i]=1;
for (rr int i=1;i<=q;++i) a[i]=(rec){iut(),i};
sort(e+1,e+1+m,cmp1); sort(a+1,a+1+q,cmp2); rr int j=1;
for (rr int i=1;i<=q;++i){
ans[a[i].rk]=ans[a[i-1].rk];
while (j<=m&&e[j].w<=a[i].w){
rr int fa=getf(e[j].x),fb=getf(e[j].y);
if (fa!=fb){
ans[a[i].rk]-=son[fa]*(son[fa]-1)+son[fb]*(son[fb]-1);
if (fa>fb) fa^=fb,fb^=fa,fa^=fb;
son[f[fa]=fb]+=son[fa];
ans[a[i].rk]+=son[fb]*(son[fb]-1);
}
++j;
}
}
for (rr int i=1;i<=q;++i) print(ans[i]),putchar(10);
}
return 0;
}
JZOJ 4225 宝藏
题目（简化版）
询问树上一个点到另外一个点的期望长度
分析
未完待续
代码
后续
我明明菜，还不承认