Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
极限压内存,数组全用bool#include<iostream> #include<stack> #include<string.h> #include<cmath> #include<iomanip> #include<algorithm> #include<climits> #include<cstdio> #include<vector> #include<sstream> #include<ctype.h> #include<set> #include<map> #include<ctime> #include<stdlib.h> #include<queue> #include<bitset> #define usi unsigned int #define ull unsigned long long using namespace std; template<typename TTT>inline void mr(TTT& theNumberToRead) { theNumberToRead = 0; bool prn = false; char c = getchar(); while (!isdigit(c)) { if (c == '-')prn = true; c = getchar(); } while (isdigit(c)) theNumberToRead = 10 * theNumberToRead + (c ^ 48), c = getchar(); if (prn) theNumberToRead = -theNumberToRead; } template<typename TTT>inline TTT mrr() { TTT theNumberToRead = 0; bool prn = false; char c = getchar(); while (!isdigit(c)) { if (c == '-')prn = true; c = getchar(); } while (isdigit(c)) theNumberToRead = 10 * theNumberToRead + (c ^ 48), c = getchar(); return prn ? -theNumberToRead : theNumberToRead; } template<typename T>void my_write(T x) { if (x) my_write(x / 10), putchar(x % 10 ^ 48); } template<typename T>void mw(T x, char mid) { if (x) { if (x < 0) putchar('-'), x = -x; my_write(x); } else putchar(48); if (mid) putchar(mid); } // ******************************************华丽的分割线****************************************** // ******************************************华丽的分割线****************************************** // ******************************************华丽的分割线****************************************** // ******************************************华丽的分割线****************************************** // ******************************************华丽的分割线****************************************** int n; bool a[5000], f[5000]; int solve(int k) { memset(f, 0, sizeof(f)); int res = 0; bool sum = 0; for (int i = 0; i + k <= n; ++i) { if (a[i] != sum) ++res, sum = !sum, f[i] = true; if (i - k + 1 >= 0 && f[i - k + 1]) sum = !sum; } for (int i = n - k + 1; i < n; ++i) { if (a[i] != sum) return INT_MAX; if (i - k + 1 >= 0 && f[i - k + 1]) sum = !sum; } return res; } int main() { int ansK, ansM = INT_MAX; mr(n); for (int i = 0; i < n; ++i) { char c; while (!isalpha(c = getchar())); a[i] = c == 'B'; } for (int k = 1, temp; k <= n; ++k) { temp = solve(k); if (temp < ansM) ansM = temp, ansK = k; } mw(ansK, ' '); mw(ansM, '\n'); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator