A.?Inna and Pink Pony

題意：給出如下參數，

? ? ? ? ?n,?m,?i,?j,?a,?b?(1?≤?n,?m?≤?106;?1?≤?i?≤?n;?1?≤?j?≤?m;?1?≤?a,?b?≤?106).

? ? ? ? ?其中n，m表示有一個n*m的grid,起點在(i, j),問從起點移動到四個拐角(1,?m),?(n,?1),?(n,?m),?(1,?1)之一，最少

? ? ? ? ?的步數是多少，如果在位置(x,y) 那么可以移動到?(x?-?a,?y?-?b)?(x?+?a,?y?-?b)?(x?-?a,?y?+?b)?(x?+?a,?y?+?b) 四個

? ? ? ? ? 位置之一。

分析：四種情況（走到一個角）處理的方式相同，首先拐角的行坐標和當前位置的行坐標之差必須是a的倍數，縱坐標

? ? ? ? ?之差是b的倍數，其次a加的次數和b加的次數的奇偶性一定相同，然后a，b的范圍不能越界，最后步數取a和b加

? ? ? ? ?的次數中大的那一個。

/*************************************** * File Name:220a.cpp * Author:sky0917 * Created Time:2013年12月20日 16:17:25 ***************************************/ #include <map> #include <cmath> #include <queue> #include <string> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int INF = 0x1f1f1f1f;int a, b; int n, m;int cal(int x, int y){if (x == 0 && y == 0)return 0; if (a > x && a >= n-x) return INF;if (b > y && b >= m-y)return INF;if (x % a != 0 || y % b != 0){return INF;} if ((x / a) % 2 != (y / b) % 2){return INF;}return max(x/a, y/b); }int main(){int x, y;int res;while (scanf("%d %d %d %d %d %d",&n,&m,&x,&y,&a,&b)!=EOF){res = INF;res = min(res, cal(x-1, y-1));res = min(res, cal(x-1, m-y));res = min(res, cal(n-x, y-1));res = min(res, cal(n-x, m-y));if (res != INF){printf("%d\n",res);}else puts("Poor Inna and pony!");} return 0; } View Code

?

B.Inna and Nine

題意：給出一個長度為n的數字組成的字符串，每次可以對字符串作如下操作：把相鄰的兩個和為9的數替換成一個9。要求

? ? ? ? ?最后字符串中9的個數最多，假設做多為ma,那么有多少沖改變方式可以使得最終9的個數為ma.

思路： 考慮字符串的一個子串，abcdef滿足a+b!=9,b+c=9,c+d=9,d+e=9,e+f!=9那么可以把子串bcde單獨拿出來考慮，

? ? ? ? ? ?它的改變不會影響其他的子串的改變。假設這個子串的長度為m，如果m為偶數，那么變的方式唯一，即變成m/2個9，

? ? ? ? ? 如果m為奇數，那么改變的方式為（m+1)/2 ，因為有一個數不參與變化，這個數是隔一個數出現一次的，最后把每個

? ? ? ? ? ? 子串的情況乘起來即可。

/*************************************** * File Name:220b.cpp * Author:sky0917 * Created Time:2013年12月20日 17:55:52 ***************************************/ #include <map> #include <cmath> #include <queue> #include <string> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100005;char a[maxn]; int main(){long long res; while (scanf("%s",a)!=EOF){int len = strlen(a);res = 1;for (int i=0; i<len; i++){long long tmp = 1;while (i<len-1 && a[i]+a[i+1] - '0' - '0' == 9){tmp += 1; i++;}if (tmp % 2 == 1){res *= tmp/2 + 1;}} printf("%I64d\n",res);} return 0; } View Code

?

C.Inna and Dima

題意：給出一個n*m的方格陣，方格陣中只有D,I,M,A，每次只能從按DIMA的順序走，問最長可以走的單詞個數是

? ? ? ? ? 多少，如果出現循環(huán)，則個數為INF。

分析：d[i][j]表示從(i,j)出發(fā)走的最長單詞數，dfs即可。

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1002; const int INF = 0x1f1f1f1f; int f[8] = {-1, 1, 0, 0, 0, 0, -1, 1}; char g[maxn][maxn]; int d[maxn][maxn]; int v[maxn][maxn]; bool li[333][333]; int n, m; int cnt; int res; bool flag;inline bool ok(int x, int y){return x>=0 && x<n && y>=0 && y<m; }void dfs(int x, int y){v[x][y] = cnt;int dp = 0;d[x][y] = INF;for (int i=0; i<4; i++){int xx = x + f[i];int yy = y + f[i+4];if (ok(xx, yy) && li[g[x][y]][g[xx][yy]]){if (d[xx][yy]){dp = max(dp, d[xx][yy]);} else{dfs(xx, yy);dp = max(dp, d[xx][yy]);}}}d[x][y] = dp+1;res = max(res, d[x][y]); } void solve(){cnt = 0;res = 0;for (int i=0; i<n; i++){for (int j=0; j<m; j++){if (!v[i][j] && g[i][j]=='D'){cnt++;dfs(i, j);}}} if (res > INF){printf("Poor Inna!\n");return;}res /= 4; if (res < 1)printf("Poor Dima!\n");else printf("%d\n",res); } int main(){li['D']['I'] = li['I']['M'] = li['M']['A'] = li['A']['D'] = true;while (scanf("%d %d",&n,&m)!=EOF){for (int i=0; i<n; i++){scanf("%s",g[i]);}solve();} return 0; } View Code

?

D.?Inna and Sequence

題意：給出一個有m個數的的數組，a1,?a2,?...,?am， 表示每次刪除的數為第a1，a2..am個數，前提是這個數存在。

? ? ? ? ? 有n次操作，每次操作如下：

? ? ? ? ? 1 在序列最后加上一個數1,

? ? ? ? ? 0 在序列最后加上一個樹0，

? ? ? ? ? -1最序列進行一次刪除操作。

? ? ? ? ? 輸出n次操作后的數組。

分析：由于每次只追加一個數，那么刪除的次數不可能超過n，刪除第ai個數的時候，用二分+樹狀數組找到刪除的位置。

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1000005;int n, m; int v[maxn]; int a[maxn]; inline int lowbit(int x){return (x) & (-x); } void add(int pos, int x){while (pos <= n){v[pos] += x;pos += lowbit(pos);} } int getsum(int pos){int sum = 0;while (pos > 0){sum += v[pos];pos -= lowbit(pos);}return sum; } int val[maxn]; int sum[maxn];void del(int x){for (int i=0; i<m; i++){if (getsum(x) < a[i]){return;}int l = 1, r = x-1, mid;while (l <= r){mid = (l+r)>>1;int s = getsum(mid);if (s < a[i])l = mid+1;else r = mid-1; }add(l, -1);} } int main(){while (scanf("%d %d",&n,&m)!=EOF){for (int i=0; i<m; i++){scanf("%d",&a[i]);a[i] -= i;}for (int i=1; i<=n; i++){scanf("%d",&val[i]);if (val[i] < 0) del(i);elseadd(i, 1);}sum[0] = 0;for (int i=1; i<=n; i++){sum[i] = getsum(i);if (sum[i] - sum[i-1] == 1){printf("%d",val[i]);}} if (sum[n] == 0){printf("Poor stack!");}puts("");}return 0; } View Code

?

?

轉載于:https://www.cnblogs.com/sky0917/p/3488297.html

總結

以上是生活随笔為你收集整理的Codeforces Round #220 (Div. 2)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。