A – Chewbaсca and Number 大于4的倒置，小于等于4的不倒置。注意第一位如果是9则不倒置。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;char s[100];int main(){int len, i;scanf(“%s”,s);len=strlen(s);for(i=0;i<len;i++){if(!(s[i]==’9’&&i==0)&&s[i]>’4′)s[i]=9-(s[i]-‘0′)+’0’;}printf(“%s\n”,s);return 0;}
B – Han Solo and Lazer Gun 遍历并标记与之在同一条直线上的点，注意精度即可。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-12;int vis[2000];struct node{int x, y;}fei[2000];int main(){int n, x0, y0, i, j, flag=0, ans;double k, b;scanf(“%d%d%d”,&n,&x0,&y0);for(i=0;i<n;i++){scanf(“%d%d”,&fei[i].x,&fei[i].y);}memset(vis,0,sizeof(vis));for(i=0;i<n;i++){if(fei[i].x==x0){vis[i]=1;flag=1;}}ans=flag;for(i=0;i<n;i++){if(!vis[i]){vis[i]=1;k=(double)(y0-fei[i].y)/(x0-fei[i].x);b=y0-k*x0;for(j=0;j<n;j++){if(vis[j]) continue ;if(fabs(fei[j].y*1.0-(k*fei[j].x+b))<eqs){vis[j]=1;}}ans++;}}printf(“%d\n”,ans);return 0;}
C – Watto and Mechanism 这题太折磨人了。。第一次直接用的map，被hack。。又加上了hash，结果终测挂了。。应该是字符串哈希写挫了。。也没想到更好的hash方法。于是就改成了字典树+dfs就过了。。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-12;char str[610000];struct node{int flag;node *next[4];};node *newnode(){int i;node *p=new node;p->flag=0;for(i=0;i<3;i++){p->next[i]=NULL;}return p;}void build(node *root, char *s){int i, x, len=strlen(s);node *p=root;for(i=0;i<len;i++){x=s[i]-‘a’;if(p->next[x]==NULL){p->next[x]=newnode();}p=p->next[x];}p->flag=1;}bool dfs(node *p, char *s, int len, int flag, int maxd){int i;if(len==maxd){if(flag&&p->flag) return 1;return 0;}for(i=0;i<3;i++){if(p->next[i]==NULL) continue ;if(i!=s[len]-‘a’){if(flag) continue ;if(dfs(p->next[i],s,len+1,1,maxd))return 1;}else{if(dfs(p->next[i],s,len+1,flag,maxd)) return 1;}}return 0;}int main(){int n, m, len;scanf(“%d%d”,&n,&m);node *root=newnode();while(n–){scanf(“%s”,str);build(root,str);}while(m–){scanf(“%s”,str);len=strlen(str);if(dfs(root,str,0,0,len))puts(“YES”);else puts(“NO”);}return 0;}
D – R2D2 and Droid Army 水题。。。比赛的时候一直在纠结C题。这题没怎么看。。结果赛后20分钟就A了。。sad。。 大体思路是双指针+线段树。 既然是区间最长问题，，那么瞬间就可以想到双指针。然后判断区间内的最大值是否满足条件即可。查询最大值很明显是用线段树来维护。m最大是5，所以可以同时维护m棵线段树。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-12;const ULL B=1e9+7;Max[6][400000], q_max[6], m, ans[6];void PushUp(int f, int rt){Max[f][rt]=max(Max[f][rt<<1],Max[f][rt<<1|1]);}void Update(int f, int p, int x, int l, int r, int rt){if(l==r){Max[f][rt]=x;return ;}int mid=l+r>>1;if(p<=mid) Update(f,p,x,lson);else Update(f,p,x,rson);PushUp(f,rt);}void Query(int ll, int rr, int l, int r, int rt){if(ll<=l&&rr>=r){for(int i=0;i<m;i++){q_max[i]=max(q_max[i],Max[i][rt]);}return ;}int mid=l+r>>1;if(ll<=mid) Query(ll,rr,lson);if(rr>mid) Query(ll,rr,rson);}int main(){int n, k, i, j, max1, l, r, x, flag;LL sum;scanf(“%d%d%d”,&n,&m,&k);for(i=0;i<n;i++){for(j=0;j<m;j++){scanf(“%d”,&x);Update(j,i,x,root);}}l=r=max1=0;for(r=0;r<n;r++){flag=0;while(!flag){memset(q_max,-1,sizeof(q_max));Query(l,r,root);sum=0;for(i=0;i<m;i++){sum+=q_max[i];}if(sum<=k) flag=1;else l++;}if(max1<r-l+1){memcpy(ans,q_max,sizeof(ans));max1=r-l+1;}}for(i=0;i<m;i++){printf(“%d “,ans[i]);}return 0;}
E题暂时还没做掉。等做掉之后马上更新。
人总是珍惜未得到的，而遗忘了所拥有的
