比赛传送门
作者:WHy
- 签到题
- 1002题 C++ to Python
- 1007题 Snatch Groceries
- 基本题
- 1012题 Luxury cruise ship
题目大意
提取字符串中的数字,逗号和括号。
考察内容
字符串
分析
#include1007题 Snatch Groceriesusing namespace std; const int N=1010; void solve(){ char s[N],ans[N]; scanf("%s",s); int k=0; for(int i=0;i if(s[i]=='('||s[i]==')'||s[i]==','||s[i]=='-'||s[i]>='0'&&s[i]<='9')ans[k++]=s[i]; } for(int i=0;i printf("%c",ans[i]); } printf("n"); } int main(){ int t; scanf("%d",&t); while(t--)solve(); }
题目大意
给定几个区间,求出区间重叠前的区间数。
考察内容
排序
分析
把各个区间按照左端点从小到大排序,依次判断右端点是否超过下一个区间的左端点。
#include基本题 1012题 Luxury cruise shipusing namespace std; const int N=1e5+5; struct range{ long long start,end; }ra[N]; bool cmp(range a,range b){ return (a.start int n,i; cin>>n; for(i=1;i<=n;i++)cin>>ra[i].start>>ra[i].end; sort(ra+1,ra+1+n,cmp); for(i=1;i if(ra[i].end>=ra[i+1].start)break; } if(i==n)cout< int t; cin>>t; while(t--)solve(); }hile(t--)solve(); }
题目大意
将体积为7、31、365的物品装进容量为n的背包,问最少装多少件能装满,不能装满输出-1。
考察内容
dp,背包
分析
当n很小时,直接dp分析。
当n很大时,先用365装填背包至一个较小的范围后dp。
#includeusing namespace std; const int N=1e5; long long dp[N]; void solve(){ int i; long long n,ans=0; cin>>n; if(n>76205){//n很大时,76205为7、31、365的最小公倍数 ans+=(n-76205)/365; n-=ans*365; } if(dp[n]>1e17)cout<<-1< for(int i=1;i<80000;i++)dp[i]=1e18+1; for(int i=365;i<80000;i+=365)dp[i]=dp[i-365]+1; for(int i=31;i<80000;i++)dp[i]=min(dp[i],dp[i-31]+1); for(int i=7;i<80000;i++)dp[i]=min(dp[i],dp[i-7]+1); int t; cin>>t; while(t--)solve(); }