CodeForces Good Bye 2016

　　A题，水题略过。

　　B题，也水，但是想复杂了。只要运动超出[0,20000]的范围就算不可能了。

　　C题，我自己的方法是解不等式，然后取最大的答案即可。代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <map>

 #include <vector>

 using namespace std;

 const int N =  + ;

 const int inf = 2e9;

 int main()

 {

     int L = -inf, R = -inf;

     int n; cin >> n;

     //int add = 0;

     int pre = ;

     for(int i=;i<=n;i++)

     {

         int change, d;

         scanf("%d%d",&change, &d);

         //add += change;

         if(d == )

         {

             if(L == -inf) L =  - pre;

             else L = max(L,  - pre);

         }

         else

         {

             if(R == -inf) R =  - pre;

             else R = min(R,  - pre);

         }

         pre += change;

     }

     if(L != -inf && R != -inf && L > R) puts("Impossible");

     else if(L != -inf && R == -inf) puts("Infinity");

     else printf("%d\n",R + pre);

     return ;

 }

　　D题是记忆化搜索，补题的时候没做出来。。代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <map>

 #include <vector>

 #include <set>

 using namespace std;

 const int N =  + ;

 const int inf = 2e9;

 typedef pair<int,int> pii;

 int dirx[] = {,,,,-,-,-,};

 int diry[] = {,,-,-,-,,,};

 int vis[][][N][N];

 int t[], n;

 int mp[N][N];

 void dfs(int pos, int dir, int x, int y)

 {

     if(pos > n || vis[pos][dir][x][y]) return ;

     vis[pos][dir][x][y] = ;

     for(int i=;i<t[pos];i++) mp[x+dirx[dir]*i][y+diry[dir]*i] = ;

     x += dirx[dir] * (t[pos] - );

     y += diry[dir] * (t[pos] - );

     dfs(pos+, (dir+)%, x+dirx[(dir+)%], y+diry[(dir+)%]);

     dfs(pos+, (dir+)%, x+dirx[(dir+)%], y+diry[(dir+)%]);

 }

 int main()

 {

     cin >> n;

     for(int i=;i<=n;i++) scanf("%d",t+i);

     dfs(,,N/,N/);

     int ans = ;

     for(int i=;i<N;i++)

     {

         for(int j=;j<N;j++) ans += mp[i][j];

     }

     cout << ans << endl;

     return ;

 }

　　E题，好题。用0~4分别表示拥有2017的前若干个字母的情况，x[i][j]表示从i状态转移到j状态需要删除几个字符，然后进行转移。并且用线段树进行维护答案。具体见代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <map>

 #include <vector>

 #include <set>

 #define ls (o<<1)

 #define rs (o<<1|1)

 #define t_mid (l+r>>1)

 #define lson ls,l,t_mid

 #define rson rs,t_mid+1,r

 using namespace std;

 const int N =  + ;

 const int inf = 0x3f3f3f3f;

 typedef pair<int,int> pii;

 int n,q;

 char s[N];

 struct node

 {

     int x[][];

     node operator + (const node A) const

     {

         node ans;

         for(int i=;i<;i++)

         {

             for(int j=;j<;j++)

             {

                 ans.x[i][j] = inf;

                 for(int k=;k<;k++) ans.x[i][j] = min(ans.x[i][j], x[i][k] + A.x[k][j]);

             }

         }

         return ans;

     }

 }p[N<<];

 void build(int o,int l,int r)

 {

     if(l == r)

     {

         for(int i=;i<;i++) for(int j=;j<;j++) p[o].x[i][j] = i==j ?  : inf;

         if(s[l] == '')

         {

             p[o].x[][] = ;

             p[o].x[][] = ;

         }

         else if(s[l] == '')

         {

             p[o].x[][] = ;

             p[o].x[][] = ;

         }

         else if(s[l] == '')

         {

             p[o].x[][] = ;

             p[o].x[][] = ;

         }

         else if(s[l] == '')

         {

             p[o].x[][] = ;

             p[o].x[][] = ;

         }

         else if(s[l] == '')

         {

             p[o].x[][] = ;

             p[o].x[][] = ; // 已经有2017，现在多出6，要删掉6

         }

         return ;

     }

     build(lson);

     build(rson);

     // up(o)

     p[o] = p[ls] + p[rs];

 }

 node query(int o,int l,int r,int ql,int qr)

 {

     if(l == ql && r == qr) return p[o];

     if(qr <= t_mid) return query(lson,ql,qr);

     else if(ql > t_mid) return query(rson,ql,qr);

     else return query(lson,ql,t_mid) + query(rson,t_mid+,qr);

 }

 int main()

 {

     cin >> n >> q;

     scanf("%s",s+);

     build(,,n);

     while(q--)

     {

         int l, r;

         scanf("%d%d",&l, &r);

         int ans = query(,,n,l,r).x[][];

         printf("%d\n",ans == inf ? - : ans);

     }

     return ;

 }

巴特西

CodeForces Good Bye 2016

最新文章

热门文章