NOIP模拟赛2019.9.21题解

题解"/>

NOIP模拟赛2019.9.21题解

T1 小猫爬山(climb)

1000ms 131072KB

【description】

Freda 和 rainbow 饲养了 N 只小猫，这天们要去爬山 。经历了千辛万苦，小猫们 终于爬上了山顶，但是疲倦的它们再也不想徒步走下（呜咕 ><>< ）。
Freda 和 rainbow 只好 花钱让它们坐 索道 下山。 索道 上的缆车 最大承重量为 W，而 N 只小猫的重量分别是 C1、C2…… CN。当然，每辆缆车上的小猫重量之和不能超过 W。
每 租用一辆缆车 ，Freda 和 rainbow 就要付 1美元 ，所以他们想知道，最少需要付多少美元 能把这 N 只小猫都运送下山？

【input】

第一行 包含两个用空格隔开的整数， N 和 W。
接下来 N 行每一个整数，其中第 i+1行的整数 表示第 i 只小猫的重量 Ci。

【output】

输出 一个整数，最少需要多美元也就是辆缆车 。

【sample input】

input1：
5 1996
1
2
1994
12
29

【sample output】

output1：
2

【Data Constraint】

对于30%的数据，1<=N<=8,1<=Ci<=W<=10^8
对于100%的数据，1<=N<=18，1<=Ci<=W<=10^8

100pts

贪心
对于小猫重量从小到大排序，从后往前扫描，若当前小猫i未被标记过，就标记，并将小猫放进一个新的缆车中,缆车数量加1，再往前二分查找重量最大的小于等于缆车剩余容量w-a[i]的小猫j，并且标记，再找w-a[i]-a[j]…直到这辆车装满。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10005;
int n,a[N],w,sum,tot,v[N],ans;
int read(){int sum=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}return sum*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0');
}
int main(){
//	freopen("climb.in","r",stdin);
//  freopen("climb.out","w",stdout);n=read();w=read();for(int i=1;i<=n;i++){a[i]=read();}sort(a+1,a+n+1);tot=0;sum=0;for(int i=n;i>=1;i--){if(v[i])continue;if(sum<a[i]){tot++;sum=w-a[i];}while(1){int x=upper_bound(a+1,a+i,sum)-a;x--;while(v[x]&&x>0)x--;if(x<=0)break;v[x]=1;sum-=a[x];}}ans=tot;print(ans);return 0;
}

T2 得分(score)

1000ms 256000KB

【description】

现在 yk 手上有 N 道题，他总共有 T 的时间来完成他们中的一些或全部。每道题有一个完成所需时间 t[i]和一个难度系数 c[i]。
如果 yk 在剩余 x 个单位时间的时候开始做题 i，并且能够完成，那么总分加上 x*c[i]。现在 yk 要从这 N 道题中选出一些在 T 个单位时间内完成，并且按照某种顺序依次完成它们（yk 每个单位时间只能做一道题，并且一旦他决定做某题就会一直做直到做完），那么他最多能够拿到多少分呢？

【input】

总共包括 N+1行
第一行，两个用空格隔开的正整数 N 和 T，分别表示题目总数和总时间。
第2到 N+1行，每行包含两个正整数，第 i+1行的两个正整数分别表示 t[i]和 c[i]

【output】

总共包括1行。
一行一个整数，表示最大能够得到的分数。

【sample input】

input1：
3 10
2 1
8 9
2 5
input2:
3 12
3 6
7 5
4 2
【sample output】
output1：
122
output2:
117

【Data Constraint】

对于20%的数据，N≤8，T≤200。
对于40%的数据，N≤15，T≤1000。
对于全部的数据，N≤3000，T≤10000，所有的 ti 和 ci 均不超过100。
保证答案在32位有符号整型范围内。

100pts

01背包＋找规律
对于两道题 i , j i,j i,j
若 i i i排在 j j j前面 那么 j j j少贡献的分（仅考虑 i i i对 j j j的影响）为 t [ i ] ∗ c [ j ] t[i]*c[j] t[i]∗c[j];
若 j j j排在 i i i前面 那么 i i i少贡献的分（仅考虑 j j j对 i i i的影响）为 t [ j ] ∗ c [ i ] t[j]*c[i] t[j]∗c[i];
所以 i能排在j前面，要满足 t [ i ] ∗ c [ j ] < t [ j ] ∗ c [ i ] t[i]*c[j]<t[j]*c[i] t[i]∗c[j]<t[j]∗c[i];
按照这种比较大小的方式对数组排序
然后转化为01背包求最大值问题。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10005;
int n,mt,ans,f[N];
struct node{int t,c;
}a[N];
int read(){int sum=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}return sum*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0');
}
bool comp(node l1,node l2)
{return l1.c*l2.t>l2.c*l1.t;
}
int main(){
//	freopen("score.in","r",stdin);
//	freopen("score.out","w",stdout);n=read();mt=read();for(int i=1;i<=n;i++){a[i].t=read();a[i].c=read();}sort(a+1,a+n+1,comp);for(int i=1;i<=n;i++)for(int j=mt;j>=a[i].t;j--){f[j]=max(f[j],f[j-a[i].t]+(mt-j+a[i].t)*a[i].c);}for(int i=0;i<=mt;i++)ans=max(ans,f[i]);print(ans);return 0;
}

迷路(road)

1000ms 65536KB

【description】

windy 在有向图中迷路了。
该有向图有 N 个节点，windy 从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。
现在给出该有向图，你能告诉 windy 总共有多少种不同的路径吗？
注意：windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

【input】

第一行包含两个整数，N T。
接下来有 N 行，每行一个长度为 N 的字符串。
第 i 行第 j 列为’0’表示从节点 i 到节点 j 没有边。
为’1’到’9’表示从节点 i 到节点 j 需要耗费的时间。

【output】

输出一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。

【sample input】

2 2
11
00

【sample output】

output：
1

【Data Constraint】

30%的数据，满足 2 <= N <= 5； 1 <= T <= 100 。
100%的数据，满足 2 <= N <= 10 ； 1 <= T <= 1000000000 。

100pts

矩阵乘法
f [ i ] [ j ] f[i][j] f[i][j]表示i到j的步数
只考虑
这道题图中的边权为1到9，比较小，所以考虑拆点，把一个点拆成9个点。
即把编号为 i 的点拆为 i9+1~i9+9，并且对于每个点拆成的9个点内部连边权为1的边。
如果 i 到 j 有一条权值为 k 的路径，那么就把矩阵中a[i9+k,j9+1]的值设为1，相当于先从 i ∗ 9 + 1 → i ∗ 9 + k i*9+1→i*9+k i∗9+1→i∗9+k 走过 k-1条长度为1的路径，再在 i ∗ 9 + k → j ∗ 9 + 1 i*9+k→j*9+1 i∗9+k→j∗9+1走过1条长度为1的路径，总长度为 k，跑一遍矩阵快速幂的值即是方案总数。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200,inf=0x3f3f3f3f,mod=2009;
int n,m,len;
char c;
struct mat{int a[N][N];void clear(){memset(a,0,sizeof(a));} 
}ans;
int read(){int sum=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}return sum*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0');
}
mat operator*(mat a,mat b){mat res;res.clear();for(int i=1;i<=len;i++)for(int j=1;j<=len;j++)for(int k=1;k<=len;k++){res.a[i][j]=(res.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;}return res;
}
mat operator^(mat a,int b){mat res;res.clear();for(int i=1;i<=len;i++)res.a[i][i]=1;while(b){if(b&1){res=res*a;}a=a*a; b>>=1;}return res;
}
int main(){
//freopen("road.in","r",stdin);
//freopen("road.out","w",stdout);n=read();m=read();len=n*9;for(int i=0;i<n;i++)for(int j=1;j<=8;j++)ans.a[9*i+j][9*i+j+1]=1;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>c;int x=c-'0';if(x>0)ans.a[i*9+x][j*9+1]=1;}}ans=ans^m;print(ans.a[1][n*9-8]);return 0;
}