参赛时间：2018.04.21 13：30--16：30
A 贪玩蓝月
题意 ： 签到题
B 大吉大利
题意 ：
给出一个出生日期，比如：1999-09-09，
问：从出生那一天开始起，到今天2018-04-21为止（包括出生日期和今天），有多少天，年月日都不包含数字4？
题解 ：
当时读题错了，以为是到2018-04-21的天数。结果卡了很久。每年中没有4的天数是固定的，每月减去3天，四月为0天 ，再考虑到闰年的情况。
然后是当前年若有4，这年的就不用算，当前月有4这个月就不算，若天数有4，就减去，若为闰年，且超过3月就加一
情况比较复杂，写起来花了比较多的时间
#include <bits/stdc++.h> using namespace std; int dayy[13]={0,31,28,31,3,31,30,31,31,30,31,30,31}; int cou(int year) { if(year%4==0&&year%100!=0) return 1; else if(year%400==0) return 1; else return 0; } int coo(int ye) { while(ye) { if(ye%10==4)return 1; ye/=10; } return 0; } int solve(int year,int m,int day) { int ans=0; for(int i=1990;i<year;i++) { if(coo(i))continue; if(cou(i)) { ans+=303; } else { ans+=302; } } if(coo(year))return ans; for(int i=1;i<m;i++) ans+=dayy[i]-3; if(m!=4) { if(day>=4&&day<14)ans--; else if(day>=14&&day<24)ans-=2; else if(day>=24)ans-=3; ans+=day; if(cou(year)&&m>=3)ans++; } return ans; } int main() { int year,m,day,n; cin>>n; for(int i=1;i<=n;i++) { scanf("%d-%d-%d",&year,&m,&day); cout<<solve(2018,4,1)-solve(year,m,day-1)<<endl; } }
C 今晚吃鸡
题意：签到题
D SSR
题意 ：签到题
E 消息列表
题意：给出对消息列表的五种操作，分别为收到消息，查看消息，顶置，取消顶置，删除消息，让你输出经过一系列操作后的消息列表。
题解：用第i次操作代表收到消息的时间，定义变量表示顶置，表示删除，再以顶置优先级最高，收到时间次要，进行排序，输出时若为删除的消息就不输出
卡了很久，看样子代码越简介越利于修改。
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #define LL long long using namespace std; const int maxn=1e6+10; struct News { int id; int num,j; int is,de; }news1[maxn]; int cmp(News a,News b) { if(a.is!=b.is) return a.is>b.is; else return a.j>b.j; } int main() { int t,m; cin>>t; for(int i=1;i<=t;i++) { int kk=1; cin>>m; for(int j=0;j<maxn;j++) news1[j].de=news1[j].is=news1[j].num=0; for(int j=1;j<=m;j++) { string comd; int id; cin>>comd>>id; if(comd=="recv") { news1[id].id=id; news1[id].de=1; news1[id].num++; news1[id].j=j; } else if(comd=="view") { news1[id].num=0; } else if(comd=="up") { news1[id].is=1; } else if(comd=="down") { news1[id].is=0; } else if(comd=="delete") { news1[id].de=0; news1[id].is=0; news1[id].num=0; } } sort(news1,news1+maxn,cmp); for(int j=0;j<maxn;j++) { if(news1[j].de==0)continue; printf("%06d %d ",news1[j].id,news1[j].num); } cout<<endl; } }
F 解方程
题意：给出Y求2018 * x ^ 4 + 21 * x + 5 * x ^ 3 + 5 * x ^ 2 + 14 = Y的解
解在1-100，可以为小数，如果在1-100无解就输出-1
题解：最初使用0.0到100.0 每次增加0.0001枚举，对于每个Y枚举1e6，按理说时间是够的，可是精度损失很大，不准确。
到最后都没有做出来。正解是用二分查找，不断减小解的范围，直到误差很小。
#include <iostream> #include <cstdio> #include <cmath> using namespace std; double co(double a) { return 2018*a*a*a*a+21*a+5*a*a*a+5*a*a+14.0; } int main() { double Y; int t; cin>>t; for(int i=1;i<=t;i++) { cin>>Y; if(co(0.0)>=Y||co(100.0)<=Y) { cout<<-1<<endl; } else { double s=0.0,o=100.0,mid=50; while(fabs(co(mid)-Y)>=1e-6) { // cout<<mid<<endl; if(co(mid)>Y) { o=mid; mid=(o+s)/2; } else if(co(mid)<Y) { s=mid; mid=(o+s)/2; } } printf("%.4f ",mid); } } return 0; }
G 小Q的口袋校园
题意：给出一天中的活动的开始与结束时间，和活动的happy值与绩点值
在时间不冲突的情况下，求出最大happy和最大happy的最大绩点值
题解：由于活动的数目最大为20，枚举20种情况为2e20=1e6 完全可行
#include <iostream> #include <cstdio> #define LL long long using namespace std; int maxhapp,maxfen,n; struct th { int a,b,c,d; }th[20]; int isok(int j) { int num[25]; for(int i=1;i<=24;i++) num[i]=0; for(int i=0;i<n;i++) { if((j&(1<<i))!=0) { for(int k=th[i].a;k<th[i].b;k++) num[k]++; } } for(int i=1;i<=24;i++) if(num[i]>1)return 0; return 1; } int cla(int j) { int happ=0,fen=0; for(int i=0;i<n;i++) { if((j&(1<<i))!=0) { happ+=th[i].c; fen+=th[i].d; } } if(happ>maxhapp) { maxhapp=happ; maxfen=fen; } if(happ==maxhapp) maxfen=max(fen,maxfen); return 1; } int main() { int t; cin>>t; for(int i=1;i<=t;i++) { maxfen=maxhapp=-1; cin>>n; for(int j=0;j<n;j++) cin>>th[j].a>>th[j].b>>th[j].c>>th[j].d; for(int j=0;j<(1<<n);j++) { if(isok(j)) { cla(j); } } cout<<maxhapp<<" "<<maxfen<<endl; } return 0; }
H 小P的数学问题
题意：给出n求n的阶乘n的范围是1e9
题解：由于一般的计算机每秒运行的时间小于1e9，所以暴力求解是不可行的
正解是用重定向 freopen（"E:\in.txt","w",stdout）和暴力打好一个表
共110个元素 num[i]代表 i*1e7时的解 这样就将1e9转化成了1e7
#include <iostream> #include <cstdio> #define LL long long const int mod = 1000000007; using namespace std; int main() { int num[]={1,682498929,491101308,76479948,723816384,67347853,27368307,625544428,199888908,888050723,927880474,281863274,661224977,623534362,970055531,261384175,195888993,66404266,547665832,109838563,933245637,724691727,368925948,268838846,136026497,112390913,135498044,217544623,419363534,500780548,668123525,128487469,30977140,522049725,309058615,386027524,189239124,148528617,940567523,917084264,429277690,996164327,358655417,568392357,780072518,462639908,275105629,909210595,99199382,703397904,733333339,97830135,608823837,256141983,141827977,696628828,637939935,811575797,848924691,131772368,724464507,272814771,326159309,456152084,903466878,92255682,769795511,373745190,606241871,825871994,957939114,435887178,852304035,663307737,375297772,217598709,624148346,671734977,624500515,748510389,203191898,423951674,629786193,672850561,814362881,823845496,116667533,256473217,627655552,245795606,586445753,172114298,193781724,778983779,83868974,315103615,965785236,492741665,377329025,847549272,698611116,0}; int n,m; cin>>n; for(int i=1;i<=n;i++) { cin>>m; int mm=m/10000000; LL ans=num[mm]; for(int j=mm*10000000+1;j<=m;j++) { ans=(ans*j)%mod; } cout<<ans<<endl; } return 0; }
I 小P和小Q
题意：给出两个数，两个数如果可以是两个1变化过来就输出yes 否则就输出no
两个数的变化规则是a*k 和b*k*k 或者 a*k*k 和b*k ，每次变化k可以是不同的
题解：将两个数相乘，的到a*b=k*k*k*k1*k1*k1*k2*k2*k2.......枚举2到pow（a*b，1/3）如果
a*b%（k*k*k）==0就让a*b一直除k*k*k直到不能除，经过一系列的除法运算，如果结果为1那么就yes
否则为no
#include <iostream> #include <cstdio> #include <cmath> #define LL long long using namespace std; int co(long long x) { for(LL i=2;i<=pow(x,1/3.0)+1;i++) { while(x%(i*i*i)==0) x/=(i*i*i); } return x; } int main() { LL n,a,b; cin>>n; for(int i=1;i<=n;i++) { cin>>a>>b; if(co(a*b)==1) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
总结：
最近和学长一起打cf的gym，题目比较难，而且是两人合作的，所以题量增长的比较慢，见识上可能比较窄。
遇到很多题目都没有思路。以后要慢慢提高题量，难题也要适当的刷。这次比赛收获比较大，找到了强劲的对手，对我来说也是一种动力。