http://tyvj.cn/Contest/861
[1.2.2017]
像我这种蒟蒻只做了前6道还有道不会只拿了暴力分
A
![清北冬令营入学测试[ABCDEF]](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pbWdzLzQvOS8zLzUvMzgvOGY5MDBhODljNjM0N2M1NjFmZGYyMTIyZjEzYmU1NjIuanBl.jpe?w=700&webp=1 "清北冬令营入学测试[ABCDEF]")
![清北冬令营入学测试[ABCDEF]](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9pbWdzLzMvMC80LzYvMTQvOTYxZGRlYmViMzIzYTEwZmUwNjIzYWY1MTQ5MjlmYzEuanBl.jpe?w=700&webp=1 "清北冬令营入学测试[ABCDEF]")
描述 这是一道有背景的题目，小A也是一个有故事的人。但可惜的是这里纸张太小，小A无法把故事详细地说给大家听。可能小A自己也讲不清楚自己的故事，因为如果讲清了，也就没有这道题目了…… 小A的问题是这个样子，它找到了n份不同的工作，第i份工作每个月有ai的工资，每份工作需要小A每天工作8小时，一周工作7天。小A想知道性价比最高（一个月的工资除以总时长）的工作的编号是多少。如果有多份，输出编号最小的就可以了。 输入格式 第一行一个数n，表示有n份工作。 接下来n个数表示ai。 输出格式 输出一个数表示答案。 备注 输入样例 5 3 3 4 5 5 输出样例 4 数据范围 对于100%的数据n<=100，1<=ai<=1000。
题解：无脑模拟
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int INF=1e9; inline int read(){ char c=getchar();int x=0,f=1; 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,mx=-INF,mxi; int main(){ n=read(); for(int i=1;i<=n;i++){ a=read(); if(a>mx) mx=a,mxi=i; } printf("%d",mxi); }
B
描述 题目描述 小B生活在一个很奇怪的国家里，这个国家的钱的面值只有可能是25,50,100的。小B最近在做社会实践，这次它选择在一个餐厅里干这件事情。但今天发生了一件有趣的事，这件事情是这个样子的，餐厅里大家都在排队买饭，粗心的打饭阿姨忘记要带零钱，并且所有排队打饭的人只带了一张钱。 具体地，第i个人带了一张面额为ai的钱，为了方便起见，我们规定每个人都想买价值25元的饭盒。阿姨显得不知所措。聪明的小B想到了一个方法，让带了25元的先买饭！这样阿姨就有了更多的零钱去找开一些面值较大的钱。 但这样对于一些人来说仍有可能找不开零钱，小B想知道是否存在一种排队方案，能够对所有人找开零钱。如果可行输出“YES”，否则输出“NO”。 输入格式 第一行一个数n，表示有n个想买饭的人。 接下来一行n个数ai，表示第i个人带着的钱的面额。 输出格式 输出“YES”或者“NO”。 备注 输入样例 3 25 50 100 输出样例 NO 数据范围 对于100%的数据n<=100，ai=25或者50或者100。
题解：显然，找一张50需要一张25，一张100需要三张25 或者 一张50和一张25，记录个数判断就行了
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int INF=1e9; inline int read(){ char c=getchar();int x=0,f=1; 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,x,a,b,c; bool solve(){ if(a<b) return false; int d=a-b; if(d<=b){ if(d>=c) return true; else return false; }else{ if(b+(d-b)/3>=c) return true; else return false; } } int main(){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=n;i++){ x=read(); if(x==25) a++; else if(x==50) b++; else if(x==100) c++; } if(solve()) puts("YES"); else puts("NO"); }
C
描述 题目描述 小C是一名数学家，由于它自制力比较差，经常通宵研究数学问题。 这次它因为这个数学问题已经两天两夜没有睡觉了，再不研究出来就要出人命了！快帮帮它吧！ 这个问题是这样的，有一个数n，将其拆分成若干自然数之和，要求乘积最大！ 如果你以为问题仅仅这么简单，那你就太naive了。 由于小C挑战自己的自我修养，它规定分成的自然数两两之间一定不能相等！ 它请你输出这个乘积最大是多少，但这个答案太大了，小C并没有兴趣看那么长的数字，它只想知道这个数对1000000007取模后的值是多少。 输入格式 一行一个数表示n 输出格式 一个数表示答案 备注 输入样例 6 输出样例 8 数据范围 对于30%的数据n<=10。 对于50%的数据n<=10000。 对于100%的数据1<=n<=1000000000。
题解：
我太navie了.......
拆分不是按数位拆分，是把这个数字大小分成若干正整数
如果可以重复的话，是个很经典的问题，就是不足4就尽量分成3，是4的话显然4比1*3更优
那么不准重复，稍微严(自)格(己)证(瞎)明(猜)一下发现还是尽量分成小的数字(可以手动模拟一下小数看看)，当然一定不能分出1
那么就从2开始不断分,2 3 4 5 6....最后剩下的不够了就开始让分出的最大的+1，再让次大的+1，一直加下去.....最后还可能剩1，再让最大的+1就行了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <set> using namespace std; typedef long long ll; const int INF=1e9,N=1e5,MOD=1000000007; inline int read(){ char c=getchar();int x=0,f=1; 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[N],p; int b[15]={0,1,2,3,4,6,8,12,15,24,30}; ll ans=1; void solve(){ int x=2,t=n; while(t>=x) t-=x,a[++p]=x,x++; int pp=p; while(t){ p=pp; for(;p>=1&&t;t--) a[p]+=1,p--; } for(int i=1;i<=pp;i++) ans=ans*a[i]%MOD; printf("%lld",ans); } int main(){ //freopen("in.txt","r",stdin); n=read(); if(n<=10) printf("%d",b[n]); else solve(); }
D
描述 题目描述 小D是一名魔法师，它最喜欢干的事就是对批判记者了。 这次记者招待会上，记者对于小D的数学很好奇。于是小D找了个方法把记者批判了一番。 它对记者抛出了这么一个问题：我有n点能量，写下数字i(1<=i<=9)需要花费a{i}点能量，我用这n点能量最多能写出什么数来？（当然可以不用光n点能量，具体看样例） 记者们一脸懵逼，于是来求助于你。 输入格式 一行10个数，表示n,a1,a2,a3,…,a9。 输出格式 一个数表示答案。 备注 输入样例1 10 2 2 1 2 2 2 2 2 2 输出样例1 3333333333 输入样例2 10 4 11 11 11 11 11 11 11 10 输出样例2 11 数据范围 对于30%的数据n,ai<=10。 对于60%的数据n,ai<=100。 对于100% 的数据1<=n,ai<=1000000，n>=min{ai}。
题解：
什么是DP渣？就是遇到一道题就想DP还想不出来
本题贪心就好
先长度，全选最便宜的数字，得到最长长度
然后从高位开始(数字比较嘛)，让高位变成能变成的最大数字，在考虑次高位，以此类推
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=1e6,INF=1e9; inline int read(){ char c=getchar();int x=0,f=1; 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[11],mn=INF,mni,cnt,ans[N]; void solve(){ cnt=n/mn; n%=mn; for(int i=1;i<=cnt;i++) ans[i]=mni; for(int i=1;i<=cnt&&n;i++) for(int j=9;j>=ans[i];j--) if(n+a[ans[i]]>=a[j]) n=n+a[ans[i]]-a[j],ans[i]=j; for(int i=1;i<=cnt;i++) printf("%d",ans[i]); } int main(){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=9;i++){ a[i]=read(); if(a[i]<=mn) mn=a[i],mni=i; } solve(); }
E
描述 题目描述 小B生活在一个很奇怪的国家里，这个国家的钱的面值只有可能是25,50,100的。小B最近在做社会实践，这次它选择在一个餐厅里干这件事情。但今天发生了一件有趣的事，这件事情是这个样子的，餐厅里大家都在排队买饭，粗心的打饭阿姨忘记要带零钱，并且所有排队打饭的人只带了一张钱。 具体地，第i个人带了一张面额为ai的钱，为了方便起见，我们规定每个人都想买价值25元的饭盒。阿姨显得不知所措。聪明的小B想到了一个方法，让带了25元的先买饭！这样阿姨就有了更多的零钱去找开一些面值较大的钱。 但这样对于一些人来说仍有可能找不开零钱，小B想知道是否存在一种排队方案，能够对所有人找开零钱。 但这个故事是关于小E的。 所以它并不关心能否有这么一种排队方案，它关心的是存在多少这样的排队方案。对于两个持有25元纸币的人，我们认为他们两个人交换位置仍然是同一种排队方案。（也就是说持有同一种纸币的人都可以看作相同的人） 由于答案很大，你只需输出答案对1000000007取模后的结果就可以了。 输入格式 第一行一个数n，表示有n个想买饭的人。 接下来一行n个数ai，表示第i个人带着的钱的面额。 输出格式 输出一个数表示答案。 备注 输入样例 5 25 25 25 50 100 输出样例 5 数据范围 对于30%的数据n<=8。 对于60%的数据n<=20。 对于100%的数据n<=40，ai=25或者50或者100。
题解：
想了一个DP，都写出来了才发现有的非法情况不能判断，无奈打了爆搜，结果只有20分
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=50,INF=1e9,MOD=1000000007; inline int read(){ char c=getchar();int x=0,f=1; 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,x,a,b,c; bool check(int a,int b,int c){ if(a<b) return false; int d=a-b; if(d<=b){ if(d>=c) return true; else return false; }else{ if(b+(d-b)/3>=c) return true; else return false; } } int ans; void dfs(int d,int x,int y,int z,int rx,int ry){ if(d==n+1){ans++;if(ans>=MOD) ans-=MOD;return;} if(x<a) dfs(d+1,x+1,y,z,rx+1,ry); if(y<b&&rx) dfs(d+1,x,y+1,z,rx-1,ry+1); if(z<c){ if(rx>=3) dfs(d+1,x,y,z+1,rx-3,ry); if(ry>=1&&rx>=1) dfs(d+1,x,y,z+1,rx-1,ry-1); } } int main(){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=n;i++){ x=read(); if(x==25) a++; else if(x==50) b++; else if(x==100) c++; } if(!check(a,b,c)) puts("0"); else {dfs(1,0,0,0,0,0);printf("%d",ans%MOD);} }
[2017-01-13]
我明白为什么20分了，排队排100的有两种找钱方法，但是这两种排队方案是一样的，所以贪心选择一张25一张50就好了
其实DP也很简单，我当时的问题是无法知道还剩下几张25几张50，其实只要加两维状态保存就可以了，数据范围实在太小........
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=42,INF=1e9,MOD=1000000007; inline int read(){ char c=getchar();int x=0,f=1; 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,x,a,b,c; int f[2][N][N][N][N],p,ans; void dp(){ p=0; f[p][0][0][0][0]=1; for(int i=0;i<n;i++,p^=1){ memset(f[p^1],0,sizeof(f[p^1])); for(int j=0;j<=i&&j<=a;j++) for(int k=0;j+k<=i&&k<=b;k++) if(i-j-k<=c) for(int l=0;l<=j;l++) for(int s=0;s<=k;s++){ int now=f[p][j][k][l][s]; if(now==0) continue; if(j+1<=a) (f[p^1][j+1][k][l+1][s]+=now)%=MOD; if(k+1<=b&&l-1>=0) (f[p^1][j][k+1][l-1][s+1]+=now)%=MOD; if(i-j-k+1<=c&&l-1>=0&&s-1>=0) (f[p^1][j][k][l-1][s-1]+=now)%=MOD; else if(i-j-k+1<=c&&l-3>=0) (f[p^1][j][k][l-3][s]+=now)%=MOD; } } for(int l=0;l<=a;l++) for(int s=0;s<=b;s++) ans=(ans+f[p][a][b][l][s])%MOD; printf("%d",ans); } int main(){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=n;i++){ x=read(); if(x==25) a++; else if(x==50) b++; else c++; } dp(); }
F
描述 这个故事是关于小F的，它有一个怎么样的故事呢。 小F是一个田径爱好者，这天它们城市里正在举办马拉松比赛，这个城市可以被看作是n个点m条带权有向边组成的图。马拉松比赛的终点只有一个：点S。 有k个人参加了这场马拉松，小F所在的城市的马拉松与正常的马拉松不一样，每个人的起点都是不相同的，具体地，第i个人从第{ai}个城市出发，并且第i个人的速度是{vi}。每个人当然是会沿着最短路跑到S点，如果一个人跑步的距离是s，速度是v，那么他所花费的时间为s/v。 现在小F想知道，谁是最快到达终点的。若有多个同时到达终点的，就求跑的路最长的，如果有多个同时到达终点且跑的路最长的，就求编号最大的。 小F想知道那个人的编号是多少。 输入格式 第一行3个数字，n,k,m，表示点的个数，跑步的人数，以及路径的条数。 接下来一行m行，每行3个数ai,bi,ci表示有一条从ai到bi长为ci的有向路径。 接下来一行一个数S。 接下来一行k个数，表示每个人的起点xi。 接下来一行k个数，表示每个人的速度vi。 输出格式 输出一个数表示答案。 测试样例1 输入 5 2 10 5 1 9 1 2 81 2 3 30 2 1 46 1 4 45 2 4 48 5 1 93 2 5 61 2 5 21 3 5 45 1 3 5 18 29 输出 2 备注 输入样例 3 2 3 1 2 2 1 3 3 2 3 1 3 2 1 1 3 输出样例 2 数据范围 对于30%的数据n<=5，m<=10。 对于100%的数据n<=300，m<=5000。0<=ci<=100，1<=xi,S<=n，1<=vi<=100，1<=k<=n。
题解：
这不最短路裸题？
为了防止double误差最后排序后用分数判断
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=305,M=5e3+5,INF=2147483647; inline int read(){ char c=getchar();int x=0,f=1; 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,k,m,s,u,v,w; struct person{ int x,id; double d,v,t; bool operator <(const person &r)const{return t<r.t;} }p[N]; struct edge{ int v,ne,w; }e[M<<1]; int h[N],cnt=0; inline void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; } inline void lop(int &x){if(x==N) x=1;else if(x==0) x=N-1;} int d[N],q[N],head,tail,inq[N]; void spfa(int s){ for(int i=1;i<=n;i++) d[i]=INF; head=tail=1; q[tail++]=s;inq[s]=1;d[s]=0; while(head!=tail){ int u=q[head++];inq[u]=0;lop(head); for(int i=h[u];i;i=e[i].ne){ int v=e[i].v,w=e[i].w; if(d[v]>d[u]+w){ d[v]=d[u]+w; if(!inq[v]){ if(d[v]<d[q[head]]) head--,lop(head),q[head]=v; else q[tail++]=v,lop(tail); inq[v]=1; } } } } } bool cmp(person a,person b){ if(a.d==b.d) return a.id>b.id; else return a.d>b.d; } void solve(){ for(int i=1;i<=k;i++) p[i].d=d[p[i].x],p[i].t=p[i].d/p[i].v; sort(p+1,p+1+k); int equ=1; for(int i=2;i<=k;i++){ if(p[i-1].d*p[i].v==p[i].d*p[i-1].v) equ++; else break; } sort(p+1,p+1+equ,cmp); printf("%d",p[1].id); } int main(){ n=read();k=read();m=read(); for(int i=1;i<=m;i++){u=read();v=read();w=read();ins(v,u,w);} s=read(); for(int i=1;i<=k;i++) p[i].x=read(),p[i].id=i; for(int i=1;i<=k;i++) scanf("%lf",&p[i].v); spfa(s); solve(); }