悲剧的div2。。。。。
A
题意：在n * m的矩形平面直角坐标系中，从(x, y)可以到四个点(x - a, y - b)，(x + a, y - b)，(x - a, y + b)，(x + a, y + b)。给定坐标(x, y)和a, b, n, m，求该点走到矩形顶点( (1, m), (n, 1), (n, m), (1, 1)中任意一个)最少需要多少步。如果走不到，返回-1。
解法：枚举一下走到哪个顶点就行了。关键是有两个trick，一个是不能走出矩形边界，另一个是比如(3, 2)，a = b = 1走不到(1, 1)。注意特判就好了。
tag:水题, trick
/*
* Author: Plumrain
* Created Time: 2013-12-18 23:33
* File Name: A.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cctype>
#include <ctime>
#include <utility> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define ALL(t) t.begin(),t.end()
#define INF 999999999999
#define zero(x) (((x)>0?(x):-(x))<eps)
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ; typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef pair<int, int> pii;
typedef long long int64; inline int Mymod (int a, int b) {int x=a%b; if(x<) x+=b; return x;} int n, m, x, y, a, b;
int gao(int x, int y, int ta, int tb)
{
int da = abs(x - ta), db = abs(y - tb);
if (da % a) return maxint;
if (db % b) return maxint; int t1 = da / a, t2 = db / b;
if (abs(t1-t2) & ) return maxint;
if (t1 == t2) return t1;
if (t1 < t2){
if (n < *a) return maxint;
return t2;
}
else{
if (m < *b) return maxint;
return t1;
}
} int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
// std::ios::sync_with_stdio(false);
while (cin >> n >> m >> x >> y >> a >> b){
int ans = min(gao(x, y, , ), gao(x, y, , m));
ans = min(ans, gao(x, y, n, m));
ans = min(ans, gao(x, y, n, ));
if (ans == maxint) cout << "Poor Inna and pony!" << endl;
else cout << ans << endl;
}
return ;
}
B
题意：给一个有'1' - '9'组成的字符串s，可以进行一种操作，就是如果s[i]-‘0’ + s[i+1]-‘0' == 9，可以在s中用'9'替换s[i]和s[i+1]。问在最终得到的字符串s含有9数量最多的前提下，最终操作完成后可能得到多少种字符串。s.size() <= 10^5。
解法：考虑连续几个和都为9的情况，比如34343，如果子串长度为偶数，则只有一种操作方法。否则，有(len+1) / 2种处理方法。每个子串的处理方法数相乘即为答案。
tag:水题
/*
* Author: Plumrain
* Created Time: 2013-12-18 23:44
* File Name: B.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cctype>
#include <ctime>
#include <utility> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define PB push_back
#define SZ(v) ((int)(v).size())
#define ALL(t) t.begin(),t.end()
#define INF 999999999999
#define zero(x) (((x)>0?(x):-(x))<eps)
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ; typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef pair<int, int> pii;
typedef long long int64; inline int Mymod (int a, int b) {int x=a%b; if(x<) x+=b; return x;} int64 two[];
int a[]; int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
// std::ios::sync_with_stdio(false);
two[] = ;
for (int i = ; i < ; ++ i)
two[i] = two[i-] * ; string s;
while (cin >> s){
int n = s.size();
for (int i = ; i < n; ++ i)
a[i] = s[i] - ''; int num = ;
int64 ans = ;
for (int i = ; i < n; ++ i){
if (a[i] + a[i-] == )
num ++;
else{
if (num > && num & ) ans *= (num/+);
num = ;
}
}
if (num > && num & ) ans *= (num/+);
cout << ans << endl;
} return ;
}
C
题意：一个由四个字符——D,I,M,A——组成的n*m的矩阵中，能从写有D的格子走到I，I走到M，M走到A，A走回D。可以从任意写有D的格子开始，问最多能走多少组DIMA。
解法：简单DFS加记忆化。比赛的时候sb了。。。
tag:DFS, memorization
方法比较裸，比完以后我就没补这道题了。
D
题意：给一个数组an[]，然后读入一串数并维护以个队列。若读到0或1，则将它放在队尾；若读到-1，则找到最大的i使得an[i] <= len（当前队列的长度），然后同时在队列中删除位置为an[0], an[1]....an[i]的元素。问最终得到的队列是什么。an.size() <= 10^6，读入的一串数最多10^6，1 <= an[i] <= 10^6。
解法：比赛的时候我写了个用并查集的方法，后来发现是错的。好像可以用后缀数组来做，O(n*logn*logn)的方法。不过我不会。。。。还有神牛写了O(n)的方法。
关键点在于：用扫一遍可以直到，每次将0/1放进去的时候，队列的长度是多少，也即是知道这个数放进去的位置在哪。又即是说，只要提前预处理出每个位置在放了数以后，需要多少个-1操作才能把这一位删掉，这个问题就能得到解决。至于具体操作细节，看代码。
tag:think, dp, good
/*
* Author: Plumrain
* Created Time: 2013-12-24 14:19
* File Name: D.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector> using namespace std; #define clr0(x) memset(x, 0, sizeof(x))
#define pb push_back
#define sz(v) ((int)(v).size())
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<a<<" "
const int inf = / ;
const int N = ;
typedef vector<int> vi; int n, m;
int opt[N];
int an[N], d[N], flag[N]; int bin_search(int x)
{
int l = , r = m-;
while (l <= r){
int mid = (l + r) >> ;
if (an[mid] <= x) l = mid + ;
else r = mid - ;
}
return r;
} int main()
{
while (scanf ("%d%d", &n, &m) != EOF){
clr0 (d); clr0 (flag);
for (int i = ; i < m; ++ i)
scanf ("%d", &an[i]);
int idx = , p = , num = ;
while (idx < m){
if (!idx && p != an[]) d[p] = inf;
else{
if (p == an[idx]){
d[p] = ;
++ num; ++ idx;
}
else d[p] = d[p-num] + ;
}
++ p;
}
for (int i = p; i <= ; ++ i)
d[i] = d[i-num] + ; int len = ;
for (int i = ; i < n; ++ i){
scanf ("%d", &opt[i]);
if (opt[i] == -) len -= + bin_search(len);
else flag[i] = d[++len];
}
vi v;
int cnt = ;
for (int i = n-; i >= ; -- i){
if (opt[i] == -) ++ cnt;
else if (flag[i] > cnt) v.pb (opt[i]);
} if (!sz(v)) printf ("Poor stack!");
else for (int i = sz(v)-; i >= ; -- i)
printf ("%d", v[i]);
printf ("\n");
}
return ;
}
E
没做。